[Closed Pattern Mining] CLOSET

CLOSET

Closed pattern을 mining하는 방법이다.

 

Closed Pattern

아래 조건을 만족하는 itemset Y가 존재하지 않을 때 X는 closed pattern이다.

• Y는 X의 superset이다.
• Y의 support와 X의 support가 같다.

 

Navie한 방법

모든 frequent itemset을 찾고 각 itemset에 대해 그 superset과 같은 support를 가지는 itemset을 제거한다.

그러나 frequent pattern의 수는 많기 때문에 freqent pattern을 찾는 것, 그 superset을 찾고 support를 비교하는 것 등 모든 것에 대해 cost가 비싸다.

 

방법

FP-tree를 이용하면 낮은 cost로 closed itemset만 recursive하게 찾을 수 있다.

"d를 가지는 모든 transaction이 cfa도 가지고 있다면 cfa는 closed pattern이 아니고, cfad는 closed pattern일 수도 있다."는 것을 이용한다.