Frequent Pattern Mining #3

Frequent Pattern Mining 세 번째 시간이다. 오늘은 Charm Algorithm에 다루어 보겠다.

 

■ Redundant rule

앞서 Frequent Pattern Mining #1 시간에 알아 본 Market Basket Problem에서 우리는 두 가지 과정을 거쳐 문제가 해결된다는 것을 알게 되었다. 

1) Find frequent itemsets

2) Find association rules 

 

이 두 가지 과정이 해결되어야 문제를 해결 할 수 있었는데, 지난 Frequent Pattern Mining #2 시간에 알아본 Apriori algorithm 은 1) 과정을 해결 하는데에 탁월한 성능을 보였다. 이번 시간에 알아 보려고 하는 Charm algorithm은 2) 과정을 해결하는데 탁월한 성능을 보이는 알고리즘이다.

 

우리는 Association rule들을 찾을 때 이미 이전에 찾은 redundant rule들을 중복해서 계속 찾게 되는 비효율적인 문제가 있음을 알 수 있다. 이러한 중복을 미리 제거하여 효율적인 방식을 택하는 알고리즘이 바로 Charm algorithm이다.

 

한 가지 예시를 들어보자.

1) {beer} -> {nuts} : {40% support, 75% confidence}

2) {beer} -> {nuts, diapers} : {40% support, 75% confidence}

 

이러한 결과를 찾게 되었다고 한다면, 우리는 1) 경우를 굳이 할 필요가 있을까? Superset인 2) 경우만 조사해도 같은 결과가 나오는데 1) 경우를 조사하고 또 2) 경우를 조사하고 이 과정이 반복되면 굳이 필요 없는 작업을 거치게 되어 비효율적이라는 것을 알 수 있다. 여기서 1) 경우가 redundant rule이 된다.

 

■ Frequent Closed Itemsets  

- closed if there exists no supersets of X with the same support as X.

(같은 support를 가지는 X가 superset을 가지지 않을 경우 = Closed 하다.)

 

★ 공식

• X1 ⊆ X2 -> t(X1) ⊇ t(X2)
• Y1 ⊆ Y2 -> i(Y1) ⊇ i(Y2)
• X ⊆ i(t(X)), Y ⊆ t(i(Y))

i : T->I i(Y) : itemset that is contained in all transations in Y (Y->X)

t : I->T t(X) : set of transations that contain all items in X (X->Y)

 

★ Closed 

- An itemset X is closed if X = C it(X) = i(t(X))

- A tid-set Y is closed if Y = C ti(Y) = t(i(Y))

 

※ if closed 한 상태라면 superset 일 경우 support 값이 더 작다.

 

■ Charm Algorithm

- Efficient frequent closed itemset analysis

- Non-redundant rule generation

- Early pruning strategy for infrequent and non-closed itemsets

 

※ Process of Charm algorithm

1) Computing the frequency of their union set

  - Tid-set(transaction set) of the union of two itemsets, X1 and X2

  - Intersection of two tid-sets : t(X1 ∪ X2) = t(X1) ∩ t(X2)

 

2) Pruning all infrequent and non-closed branches

 

X1 ≤ X2 라고 가정

 

(1) t(X1) = t(X2) -> t(X1) ∩ t(X2) = t(X1) = t(X2) -> replace X1 with (X1 ∪ X2), and prune X2

(2) t(X1) ⊂ t(X2) ->  t(X1) ∩ t(X2) = t(X1) ≠ t(X2) -> replace X1 with (X1 ∪ X2), and keep X2

(3) t(X1) ⊃ t(X2) ->  t(X1) ∩ t(X2) = t(X2) ≠ t(X1) -> replace X2 with (X1 ∪ X2), and keep X1

(4) t(X1) ≠ t(X2) -> t(X1) ∩ t(X2) ≠ t(X1) ≠ t(X2) -> keep X1 and X2

 

(2),(3)의 경우를 주목해야한다. 작은 것으로 replace하고 큰 것은 keep한다.

 

ex1)

{A} = {1345}, {C} = {123456}   ==> {AC} = {1345} 

(2)의 경우와 일치 한다. 더 작은 것 {A}는 replace 삭제하고, {C}는 keep 남긴다.

 

ex2) 

{AC} = {1345}, {CT} = {1356}  ==> {ACT} = {135}

(4)의 경우와 일치한다. X1 ≠ X2 이므로 둘 다 keep한다.

 

이렇게 (1)~(4)의 경우를 계속 비교하여 최종적으로 제거되지 않고 남은 itemsets들이 최종적인 frequent & closed itemsets가 된다. frequent(min-support ↑) & closed(no supersets) itemsets를 선택하는 것이 Charm algorithm이다.

 

※ Advantages

• No need multiple scan of transaction database -> Apriori algorithm의 발전, 향상
• No loss of information

 

Charm algorithm에 대해서 알아보았다. 점점 효율적인 알고리즘을 찾아가는 것이 주된 Data Mining의 목적인 만큼 알고리즘들을 공부하면서 점점 효율적인 알고리즘들을 공부하게 된다는 것이 눈에 보이게 되는 것 같다.