Vertical Data Format으로 FP 찾기: CHARM

지금까지 소개한 방법들은 데이터를 horizontal format으로 읽어 frequent pattern 등을 찾았다.

CHARM은, 데이터를 vertical format으로 읽어 frequent pattern을 찾는 방법이다.

 

Vertical Format

먼저 어떤 것이 Vertical Format인지 이해해보자.

우리에게 익숙한 format은 각 행이 transaction 하나하나, 행을 구성하는 열이 transaction ID와 해당 transaction ID에 속한 itemset이다.

Vertical Fomat은, 각 행이 item 하나하나, 행을 구성하는 열에는 item의 ID와 해당 item을 포함하고 있는 transaction ID의 집합이 저장되어 있다.

예를 들면 이런 형식일 것이다.

itemset	TID_set
I1	{T100, T400, T500, T700, T900}
I2	{T100, T200, T300, T400, T600, T800}
I3	{T200, T400}
I4	{T100, T800}

각 itemset이 포함되어 있는 transaction의 id들이 TID_set으로 저장되어 있음을 확인하자.

 

itemset은 아래와 같이 집합으로도 표현할 수 있다.

{I1, I2}	{T100, T400}
{I2, I4}	{T100, T800}
...	...

두 item을 모두 포함하고 있는 transaction ID set을 값으로 하는 vertical format의 데이터셋이다.

(처음 table의 교집합이라고 생각하면 쉽다.)

 

---

CHARM의 알고리즘

CHARM이 어떻게 동작하는지 아래 순서를 따라가며 살펴보자.

 

1. horizontal foramt의 데이터를 vertical format으로 바꾼다. (scan1)

* item 종류의 수가 transaction의 수 보다 적을 것이기 때문에, 행의 수가 적어져 다루기 쉬워진다.

2. k=1부터 시작하여, k+1 길이의 itemset candidate를 만들고, 검사하여 추려낸다. (table교집합 + Apriori Property)

※ table의 교집합: apriori에서 다룬 self joining과 흡사하다. 두 테이블을 합쳐 만들 수 있는 길이 k+1의 itemset 조합과, 해당 itemset이 포함되어 있는 TID Table (교집합)이 Candidate다.

※ Apriori Property: itemset이 fp라면, 그 subset도 모두 fp라는 원칙이다. apriori에서 다루었던 pruning과정을 생각하자.

3. 더 이상의 frequent itemset을 찾을 수 없을 때까지 2를 반복한다.

 

dataset의 형태만 다를 뿐 원리는 apriori와 유사함을 확인하자.

 

---

 

CHARM의 장점

CHARM의 가장 중요한 장점은 길이 k+1짜리 itemset의 support 계산을 위해 database를 스캔할 필요가 없다는 것이다.

즉, TID_set의 길이가 곧 해당 itemset의 support와 같기 때문에, support 계산이 필요가 없다.

또한 단순 교집합 연산 (intersection operation)으로 길이 k+1짜리 candidate 생성이 가능하다는 면에서 연산이 적다.