Apriori algorithm

* Apriori : A candidate generation-and-test approach

 

- method: 1-itemset 을 시작으로 itemset 의 크기를 하나하나 늘여가면서 freqeunt itemset 을 찾아가는 방법

 

  1) Initially, scan DB once to get frequent 1-itemset

 

  2) Generate length (k+1) candidate itemset from length k frequent itemset

 

  3) Test the candidate against the minimum support requirement

 

  4) Terminate when no frequent or candidate set can be generated

 

 

ex)

 

   

 

 

 

 

- Apriori 알고리즘이 극복해야 하는 부분은 1) 데이터베이스를 여러번 스캔해야 하는 점 2) 후보군이 너무 많다는 점이다.

   itemset 을 찾고 support 를 세는 작업은 아무래도 tedious 하게 느껴진다. 위의 예에서 A~E 로 만들 수 있는 itemset의 크기는 2^5 -1 개 이다.