[Frequent Pattern Mining] CHARM (using Vertical Data Format)

CHARM

Vertical data format을 이용하여 mining하는 방법이다.

 

Vertical Format

Vertical format이란 $t(AB) = \{T_{11}, T_{25}, ...\}$와 같은 형태이다.

$t(AB)$는 itemset AB를 포함하는 모든 transaction의 tid-list를 의미한다.

 

* 지금까지 표현한 transaction DB는 horizontal format이다.

 

방법

• Horizontal format을 vertical format으로 바꾼다.
• k=1부터 시작해서 frequent k-itemset으로부터 cadidate (k+1)-itemset을 생성한다.
  • TID-sets intersection과 apriori property를 이용한다.
  • A와 B를 가지고 있는 transaction = {A를 가진 transactions $\cap$ B를 가진 transactions} $\Rightarrow$ 단순 교집합(intersection)
  • Apriori property
    • Downward closure property
    • frequent itemset의 subset은 모두 frequent하다.
• 위 과정을 k를 1씩 증가시키며 frequent itemset이 더이상 찾아지지 않을 때 까지 반복한다.

 

장단점

• 장점
  • DB를 한번만 scan하면 되기 때문에 easy하다.
  • item의 수가 transaction의 수보다 훨씬 적기 때문에 easy하다. (practical)
• 단점
  • TID set의 길이가 길어질 수 있다. → intersection 시 large space가 필요해진다.