Frequent Pattern Mining #2

■ Apriori Algorithm

- Market Basket Problem의 두 가지 방식 중 frequent Itemsets를 찾는데에 가장 보편적인 알고리즘이다. 알고리즘 없이 frequent Itemsets를 찾으려 하면 브루트 포스법을 사용하여 전체를 모두 뒤져야한다. 작은 Data에서는 가능할 수 있겠지만 데이터마이닝을 사용할 정도의 Big-Data에서는 어마어마하게 비효율적일 수 있다.

 

※ 기본적인 처리 과정

   itemset generation의 후보자 선정 -> Frequent Itemset을 선택

 

※ Downward Closure Property

- Any superset of an itemset X cannot have higher support than X

-> if an itemset X is frequent then any subset of X should be frequent

 

 

★ Candidate Itemset Generation

 

Two steps : 후보자를 줄이자!!! - 후보자가 많으면 복잡함

1. selective joining

• K 사이즈 itemset을 만드려면 (K-1) 사이즈 2개를 더해야한다.

ex) 4 사이즈 itemset을 만드려면 3 사이즈 itemset 2개를 더해야한다. -> 이게 가장 효율적임

 

2. Apriori pruning

=> K 사이즈 itemset의 후보자를 조사 : K-1 사이즈 subset을 조사해서 frequent 하지 않은 것이 하나라도 있으면 후보자에서 제외시킨다. - 미리 후보자가 될 수 없는 요소를 제거시켜 효율 극대화

 

 

★ Apriori Algorithm

 

min support = 2

ID	items
1	A,C,D
2	B,C,E
3	A,B,C,E
4	B,E

 

C1

Itemset	Sup
{A}	2
{B}	3
{C}	3
{D}	1
{E}	3

min support보다 작은 {D}를 삭제

 

L1

Itemset	Sup
{A}	2
{B}	3
{C}	3
{E}	3

 

C2

Itemset	Sup
{A,B}	1
{A,C}	2
{A,E}	1
{B,C}	2
{B,E}	3
{C,E}	2

min support보다 작은 {A,B}와 {A,E}를 삭제

 

L2

Itemset	Sup
{A,C}	2
{B,C}	2
{B,E}	3
{C,E}	2

여기서 부터 selective joining을 사용한다. 3사이즈의 itemset을 만들기 위해 2사이즈의 itemset 두개를 합친다. 애초에 {A,B}와 {A,E} 조합은 후보자에서 삭제 되었으므로 두 조합의 경우는 제외하고 합치게 된다. 

여기서는 가능한 조합이 itemset 중 {B,C,E}만 가능하다.

 

C3

Itemset	Sup
{B,C,E}	2

L3

Itemset	Sup
{B,C,E}	2

 

★ Summary of Apriori Algorithm

 

- Reducing search space by downward closure property

- Multiple scan of transaction database -> Reducing transaction database scans(Downward closure property)

- Huge number of candidates -> Shrinking number of candidates(pruning)

- Tedious workload of support counting -> Facilitating support counting