[Frequent Pattern Mining] FP-Growth (using FP-Tree)

FP-Growth

= Frequent Pattern Growth

 

Candidate genration 과정 없이 frequent pattern mining을 수행한다.

FP-Growth는 transaction DB를 FP-Tree로 만들고 통해 이를 이용해서 frequent pattern을 만든다.

 

FP-Tree를 생성해서 frequent pattern을 구하기 때문에 DB scan은 2번만 발생한다.

 

기본 원리

Local frequent item을 이용해서 짧은 것을 통해 긴 패턴을 생성해낸다.

즉, frequent pattern을 recursion을 통해 점진적으로 증가시키는 원리이다.

 

기존에 발견된 frequent pattern(A)를 가지고 있는 transaction들 안에서 새로운 frequent pattern(B)를 찾으면 A와 B를 concat 한다.

즉, 새로운 frequent item을 recursive하게 더해가면서 frequent pattern을 증가시킨다.

 

DB|abc에서 d가 local frequent하다고 판단되었으면 abcd도 frequent pattern이다.

* DB|abc : DB에서 a, b, c가 모두 포함된 모든 transactions

 

방법

1. 각 frequent item에 대해서 conditional pattern-base와 conditional FP-tree를 생성한다.
2. 새로 생성된 conditional FP-tree에 대해서 위 과정을 반복한다.
3. FP-tree가 비거나 single-path가 남으면 반복을 중단한다.
   • single-path가 남을 경우 그 안에서의 모든 조합을 구하면 된다.

 

장점

complete하게 compact하여 전체 frequent 정보가 메모리에 올라갈 수 있다.

• Completeness
  • frequent에 대한 손실이 없이 정보를 complete하게 유지한다.
  • long pattern을 깨지 않고 그대로 보존할 수 있다.
• Compactness
  • 불필요한 정보를 제거한다.
  • 더 frequent한 item을 위쪽으로 배치함으로써 더 자주 발생하는 것이 더 많이 share되게 한다. 이를 통해 더 적은 표현으로 전체를 표현할 수 있다.
  • 원래의 DB보다 커지지 않는다.
    • 보통 약 1/100의 크기로 줄어든다.

 

FP-Growth가 더 빠른 이유

• Divide-and-conquer
  • 지금까지 찾은 freqeunt pattern을 기준으로 전체 mining task와 전체 transaction DB를 disjoint하게 나눠서 확인한다.
  • 작은 DB를 focused search를 할 수 있다.
• candidate generation/test가 없다.
• compressed database = FP-tree
  • 전체 transaction DB를 compact하게 메모리에 올려서 확인한다.
• basic operation만 수행
  • local frquent iterm counting
  • sub FP-tree 생성
  • no pattern search/matching

 

vs. Apriori

Support threshold(minimum support)가

• 크면 : apriori와의 차이가 크게 없다.
  • threshold가 크면 더 엄격해져서 frequent하기 힘들다.
  • 이 경우 긴 패턴을 찾기 어렵고 candidate의 수도 많지 않다.
  • 따라서 apriori에서 DB scan의 횟수가 적어진다.
• 작으면 : apriori에 비해 월등히 빠르다.
  • threshold가 작으면 pattern들이 frequent하기 쉽다.
  • 이 경우 긴 패턴이 많아질 가능성이 크다.
  • 따라서 apriori에서의 DB scan 횟수가 많아진다.
  • 반면 FP-growth는 FP-tree를 통해 transaction DB를 compact하게 main memory에 올려서 수행하기 때문에 DB scan 수가 적다.

 

---

FP-Tree 생성

Transaction DB를 FP-Tree로 나타내면 사이즈가 compact해진다.

이렇게 됨으로써 큰 사이즈의 DB가 메모리에 올라올 수 있게 된다.

 

방법

1. DB를 scan하면서 frequent 1-itemset을 찾는다.
2. support를 기준으로 내림차순(높은→낮은 순)으로 정렬하여 header table을 생성한다.
   • header table에는 infrequent item을 넣지 않는다.
   • 정렬된 1-itemset에 따라 DB에서 infrequent item을 제거하고 frequency(support)에 따라 item들을 정렬한다.
3. DB를 다시 scan하면서 FP-tree를 생성한다.
   • 높은 frequent부터 시작해서 아래로 순차적인 tree를 형성한다.

 

예시

 

---

Conditional Pattern, Conditional FP-Tree

Partition Patterns

Frequent pattern은 disjoint하게 나뉠 수 있다.

이 때 completeness를 보장하면서도 redundancy(불필요한 중복)은 없다.

 

위에서 F-list는 f-c-a-b-m-p 였으므로 아래와 같이 나뉠 수 있다.

• p를 포함하는 패턴
• p를 포함하지 않고 m을 포함하는 패턴
• p와 m을 포함하지 않고 b를 포함하는 패턴
• p, m, b를 포함하지 않고 a를 포함하는 패턴
• p, m, b, a를 포함하지 않고 c를 포함하는 패턴
• p, m, b, a, c를 포함하지 않고 f를 포함하는 패턴 $\Rightarrow$ f

 

Conditional Pattern

Conditional pattern이란 특정 item이 속해있는 패턴을 말한다.

예를 들어, p-conditional pattern은 p를 포함하는 패턴이다.

 

위 예제에서 각 item에 대한 conditional pattern은 아래와 같다.

 

Conditional FP-Tree

Conditional pattern은 FP-tree를 통해 쉽게 구할 수 있고, fp-tree로 나타낼 수 있다.

 

Single Prefix Path in FP-Tree

FP-tree 중에서 single prefix-path를 공유하고 있다면 그 부분을 분리해서 고려할 수 있다.

Single prefix-path에 대한 모든 가능한 조합을 구하고 그렇지 않은 부분에 대해서 conditional path를 구하면 된다.

 

아래와 같은 single prefix-path에 대해서는 $a_1, a_1a_2, a_1a_2a_3$가 가능한 조합이다.