Association Rules - 2

지난 게시글에 Naïve한 Frequent Associatoin Rule Algorithm은 2의 n승만큼의 연산이 필요하다고 했었다.

   

이는 만일 데이터의 크기가 10개라면… 1024번의 연산이 필요하다는 의미이다.

(아이템이 중복되어도 10개인 것이다. 같은 것이 있어도 또 세고 넘어가야 한다.)

   

이를 해결하기 위한 알고리즘으로 Apriori 알고리즘을 소개한다.

Apriori 알고리즘의 중요한 원칙은 다음과 같다.

원칙: Frequent하지 않은 item set은 그 superset 역시 Frequent 하지 않다.

이 간단한 원칙 하나로, 연산의 수를 크게 줄일 수 있다.

참고 논문 : R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules", VLDB 1994. 
PDF   ps.gz   Abstract   Google Scholar  

Expanded version: IBM RJ 9839, June 1994. ps.gz  

 

   

복잡한 설명은 넘기고, 실제로 Apriori Algorithm을 이용하여 Frequent Association Rule을 구해 보자.

Table 1 - Database D

ID	items
10	a, c, d, f
20	b, c, e
30	a, b, c, e
40	b, e
50	a, f

Minimum support = 2

이제 D를 스캔하여 후보자(Candidates)를 뽑는다.

Table 2 - Frequent Association Rule의 후보자

Item set	Support
a	3
b	3
c	3
d	1
e	3
f	2

   

추려진 후보자에서, minimum support를 만족하지 못하는 item set은 삭제한다.

(위의 경우는 d에 해당하는 라인이 지워진다.)

Table 3 - Frequent 1 Item set

Item set	Support
a	3
b	3
c	3
e	3
f	2

   

Table3로부터 item의 수가 2개인 item set candidates테이블을 만들어 보자. Item이 모두 5개니까.. 가능한 조합은

모두 4+3+2+1이다. (설명하긴 좀 그렇고… 고등학교 순열과 조합부분을 참고하자.)

Table 4 - 2 candidates

Item set

ab

ac

ae

af

bc

be

bf

ce

cf

ef

이제 D를 한번 더 스캔하여 각 item set이 몇 나타났는지 support를 계산한다.

Table 5 - 2 candidates의 support

Item set	Support
ab	1
ac	2
ae	1
af	2
bc	2
be	3
bf	0
ce	2
cf	0
ef	0

여기서, minimum support를 만족하지 못하는 item set을 지워 Frequent 2 – item set을 구한다.

Table 6 - Frequent 2 - item sets

Item set	Support
ac	2
af	2
bc	2
be	3
ce	2

여기서 item set의 크기가 3인 candidates를 구하면

Table 7 - item set size가 3인 candidates

Item set

acf

bce

   

이렇게 해서 찾은 가장 큰 크기를 가지는 item set은

Item set	Support
bce	2

   

이런 식으로 Frequent한 item set을 찾아내는 것이 Apriori Algorithm이다.