[Frequent Pattern Mining] Apriori Algorithm

Apriori Algorithm

A Candidate Generation-and-Test Approach

 

Candidate를 만들고 테스트하는 과정을 거치며 frequent pattern을 찾는 알고리즘이다.

다만 과정 중에 pruning을 통해 경우의 수를 줄인다.

 

Pruning Principle

Downward closure property의 대우를 이용한다.

Frequent 하지 않은(infrequent) itemset을 포함하는 superset은 generation/test하지 않는다.

 

과정

1. DB를 scan하며 1개짜리 frequent itmeset을 생성한다.
2. k-frequent($L_k$)를 이용하여 (k+1) 길이의 candidate itmesets($C_{k+1}$)을 생성한다.
   1. Self-joining : $L_k$를 self-joining하여 candidate $C_{k+1}$를 생성한다.
   2. Pruning : 이 때 infrequent한 subset을 포함한 itemset은 pruning한다.
3. DB를 scan하며 candidate들을 테스트하고 통과한 itemset을 (k+1)-frequent($L_{k+1}$)로 하여 2를 반복한다.
4. 더이상 frequent나 candidate set이 생성되지 않으면 종료한다.

 

문제점

• Transaction DB를 너무 많이 scan한다. → frequent pattern의 최대 길이만큼 DB scan이 발생한다.
• pruning함에도 불구하고 너무 많은 수의 candidate가 생성된다.
• 각 candidate의 support counting에서 overhead가 발생한다.

 

위 문제를 각각 개선해야 한다.

• transaction database의 scan 수를 줄인다.
• candidate의 수를 줄인다.
• candidate support counting을 개선한다.

 

---

예시

$L_k \rightarrow C_{k+1}$을 생성할 때 k-1개의 요소가 중복되는 itemset 2개를 선택해서 조합할 수 있다.

다만 이렇게 만들어진 조합 안에서 $L_k$에 포함되지 않는 subset을 가지는 조합은 $C_{k+1}$이 될 수 없다. (pruning)

 

아래 예시에서 L2 $\rightarrow$ C3로 갈 때 1개의 요소가 중복되는 itemset들은 $\{\{B,C\},\{B,E\}\} / \{ \{A, C \}, \{ B, C \} \} / \{\{A,C\},\{C,E\}\} / \{\{B,C\},\{C,E\}\} / \{\{B,E\},\{C,E\}\}$가 있다.

 

$\{\{A,C\},\{B,C\}\}$을 조합하면 $\{ A,B,C \}$가 생성된다.

그런데 이 때 $\{A, B\}$는 L2에 포함되지 않으므로 pruning되어 버려진다.

 

따라서 결국 남는 것은 $\{B, C, E\}$밖에 없다.

 

 

---

Pesudo Code

$C_k$ : Candidate itemset of size k

$L_k$ : Frequent itemset of size k