[Max Pattern Mining] MaxMiner

MaxMiner

Max pattern을 mining하는 알고리즘이다.

 

Max-pattern

아래 조건을 만족하는 Y가 없을 때 frequent pattern X를 max-pattern이라 한다.

• Y는 X를 포함하는 superset이다.
• Y는 frequent하다. (X의 sup보다 작아도 상관없음)

 

MaxMiner 방법

2번의 DB scan으로 max-pattern을 찾을 수 있다.

1. Scan 1
   • frequent item을 찾고 오름차순으로 정렬한다. (sup 작은 순 → 큰 순)
   • 모든 가능한 2-itemset을 생성하고 potential max-pattern을 찾는다.
     • 생성할 때 내부의 정렬 순서를 지켜야 한다.
     • potential max-pattern
       • 각 item으로 시작할 수 있는 가장 긴 패턴
       • set-enumeration tree를 이용해서 찾을 수 있다.
2. Scan 2
   • 생성한 후보군에 대해서 validate를 한다.
     
     • 2-itemset이 infrequent하다면 그를 포함하는 superset은 확인할 필요 없다. (apriori에서의 downward closure property)
     • potential max-pattern이 frequent하다면 그 것이 max-pattern이기 때문에 그 이하단은 확인하지 않는다.

 

Set-enumeration tree

각 item으로 시작할 수 있는 가장 긴 패턴을 찾을 수 있는 자료 구조

$\Rightarrow$ potential max-pattern을 찾을 수 있다.