Frequent Pattern Mining : CLOSET / MaxMiner

본 개념은 Data Mining: Concepts and Techniques (Jiawei Han, ‎Jian Pei, ‎Micheline Kamber)서적을 바탕으로 합니다.

 

Data Mining: Concepts and Techniques (Jiawei Han, ‎Jian Pei, ‎Micheline Kamber) 

 

저번 포스팅에서 Apriori와 FP-Growth를 보았습니다.

이번 포스팅엔 빈발 패턴을 구할 때 계산량을 줄이기 위한 알고리즘인 MaxMiner 과 CLOSET에 관해 알아보도록 하겠습니다.

 

설명하기 이전에 Closed Pattern과 Max-Pattern의 기본 개념에 관해 잠깐 알아보도록 하겠습니다.

 

아래는 Closed Pattern과 Max-Pattern을 잘 설명하는 그림입니다.

*Closed Pattern : An itemset X is closed if X is frequent and there exists no super-pattern Y כ X, with the same support as X (proposed by Pasquier, et al. @ ICDT’99) 

: 어떤 아이템 셋 X가 자주 발생하며 X를 포함하는 슈퍼 셋 (상위 셋) Y 중에서 X와 같은 support를 가지는 슈퍼 셋이 존재하지 않으면 X는 closed 패턴입니다.

 

*Max-Pattern : An itemset X is a max-pattern  if X is frequent and there exists no frequent super-pattern Y כ X, with the same support as X (proposed by Bayardo @ SIGMOID'98) 

: 어떤 아이템 셋 X가 자주 발생하며 X를 포함하는 슈퍼 셋 (상위 셋) Y 중에서 X와 같은 support를 가지는 빈발 슈퍼 셋이 존재하지 않으면 X는 closed 패턴입니다.

 

Max-Pattern은 긴 빈발 집합 항목을 만들 때 유용합니다. 위 그림에서 Max-Pattern을 찾아보면 min_support=2 보다 큰 아이템 셋을 찾는데 아이템 요소가 큰 집합부터 보면 {S1, S2, S3}와  {S2, S3, S4}가 해당됩니다. 여기서 가장 중요한 Max Pattern의 특징은 Max-Pattern으로 선정된 아이템의 셋의 부분 아이템 셋은 당연히 min_support 보다 크기 때문에 {S1, S2, S3} 와  {S2, S3, S4}가 Max-Pattern에 해당됩니다.

 

Closed Pattern은 자신을 포함하는 상위 집합 중에 자신보다 큰 support가 없는 경우, {S1, S3}와 {S2, S3} 그리고 {S2}, {S3}, {S4}가 Closed Pattern에 해당됩니다. 

두 가지의 패턴을 가지고 마이닝하는 방법이 바로 MaxMiner와 CLOSET입니다.

먼저, MaxMiner 알고리즘 수행과정을 보겠습니다.

1. 1차 scan : 빈발 itemset을 찾고 오름차순 정렬. (e.g. A, B, C, D, E)
2. 2차 scan : Max-pattern과 함께 2-itemset의 지지도 구하기.

MaxMiner의 장점은 다음 단계에서 많은 후보자들을 줄인다는 점입니다. 

예를들면, BCDE가 Max-pattern이기 때문에 BCD, BDE, CDE는 다음 scan에서 확인할 필요가 없습니다.

또한, AC가 빈번하지 않으면, ABC는 다음 scan에서 확인해 줄 필요가 없습니다. 이로써 알고리즘의 효율성이 증대하는 것이죠.

 

다음은 CLOSET 알고리즘 수행과정을 보겠습니다.

이 알고리즘은 빈발 패턴을 찾기위해 FP-Tree를 사용합니다.

(FP-Tree의 개념을 모르시면 아래의 링크로 포스팅을 보시고 오시면 됩니다^__^ )

http://2bdbest-ds.tistory.com/5 

 

FP-Tree는 서포트를 오름차순으로 빈발 itemset을 정렬한 리스트입니다. 분할 검색 공간을 사용합니다.

1. 먼저 모든 Frequent itemset을 찾습니다.

2. 그리고 superset의 support 값이 작은 close itemset을 찾습니다. 그것들이 close frequent itemset 입니다.