[Data Science] Association Rule Mining (2) - Apriori principle

 

 

Review of Frequent Itemset Mining by Brute-force approach

Figure 1. item 개수가 $d$라면, $M=2^d$이다.

Brute-force에서 우리가 시간을 줄일 수 있는 방법을 살펴보자.

(1) $M$ 줄이기

pruning을 이용하여 필요없는 후보 itemset을 지워버린다.

 

(2) $N$ 줄이기

DHP알고리즘이나 vertical-based mining algorithm으로 해결할 수 있다.

그러나 교재에서 다루지 않으므로 생략.

 

(3) $MN$ 줄이기

해시테이블과 같은 효율적인 자료구조를 이용하여 candidate나 transaction을 저장한다. 

모든 candidate를 모든 transaction과 비교할 이유가 없다.

 

Apriori principle

어떤 itemset이 frequent하다면, 그 부분집합 subset도 반드시 frequent하다.

\[ \forall X, Y: (X \subseteq Y) \Rightarrow s(X) \ge s(Y) \]

이는 support의 anti-monotone property을 수식으로 나타낸 것이다.

 

Figure 2. Anti-monotone property

만일 itemset {A, B}가 이미 infrequent하다면, AB가 포함된 모든 집합들 역시 infrequent하다는 것을 이용하여 탐색 prunning을 할 수 있다.

 

보다 구체적인 예시 상황을 보자.

1-itemset과 minimum support(minimum_support = 3)가 주어졌을 때, 탐색하게되는 k-itemset을 찾아보자.

초기 상태

frequent itemsets	Description	candidate itemsets
	min_sup이 3이 안되는 Coke과 Eggs는 prunned된다. 나머지 item인 Bread, Milk, Beer, Diaper로 2-itemsets을 구성한다.
	min_sup이 3이 안되는 {Bread, Beer}, {Milk, Beer}는 prunned된다.  나머지 2-itemset인 {Bread, Milk}, {Bread, Diaper}, {Milk, Diaper}, {Beer, Diaper}로 3-itemsets을 구성한다.
	min_sup이 3이 안되는 itemsets을 삭제하면 $\varnothing$ 이므로 더이상 rule을 생성할 item이 없다. end loop

frequent k-itemsets을 $L_k$,  Candidate itemsets을 $C_k$라 하면 apriori-algorithm은 다음과 같이 계속 $L_1 \to C_2 \to L_2 \to C_3 \to \cdots$ 을 반복한다. 

즉 $L_k$는 $C_k$에서 만들어지고, 그 $C_k$는 이전단계인 $L_{k-1}$에서 만들어진다.

이를 알고리즘으로 표현하면 다음과 같다.

Apriori Algorithm

apriori-gen()의 step1 - self joining

apriori-gen()의 step2 - pruning

Candidate Generation ($L_{k-1} \to C_k$)

1. Self-joining $L_{k-1}$
   1. 2개의 $L_{k-1}$를 각각 $p, q$라 하자.
   2. $(k-2)$개의 중복되는 itemset에 중복되지 않는 1개의 item을 추가한다. (추가된 item은 $(k-1)$번째 item이 된다)
   3. 이렇게 생긴 모든 원소들을 (임시로) $C_k$에 저장한다.
2. Pruning
   1. 위에서 생성된 (임시) $C_k$의 원소의 부분집합이 $L_{k-1}$에 속하지 않는다면 해당 원소는 $C_k$에서 삭제한다.

예시로 $L_3 = \{abc, abd, acd, ace, bcd\}$로부터 $C_4$를 만들어보자.

(1) Self-joining: $abcd, acde$가 추가된다. ($abc, abd \to abcd$, $acd, ace \to acde$)

(2) Pruning: $acde$의 경우, $ade$는 $L_3$에 존재하지 않는다. 따라서 $acde$는 삭제한다.

(3) $C_4 = \{ abcd \}$

 

 

※ Apriori algorithm이 제시된 논문

Rakesh Agrawal and Ramakrishnan Srikant.Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.

 

※ 참고 및 추가 설명

https://trivia-starage.tistory.com/181

[CS246] Frequent Itemsets Mining & Association Rules

https://trivia-starage.tistory.com/182

[CS246] A-Priori Algorithm: Finding Frequent Itemsets