5. FP-growth

Frequent Pattern Growth

• 이전까지는 Apriori algorithm을 사용해서 Freqeunt Pattern Mining을 하는 방법을 봤다
• Apriori의 한계를 개선한 Improving Apriori 방법들도 살펴보았다
  • DIC, Partition, Sampling, DHP
• 그럼에도 여전히 느리다는 문제가 있다
  • Candidate를 생성하고, Test하는 과정 자체가 시간이 오래 걸림(Bottleneck)

 

FP-growth

---

Mining Frequent Patterns without Candidate Generation

• Candidate를 Generate하는 것 자체를 하지 않는 방법
• Local Frequent Item들을 사용해서, 짧은 Pattern으로부터 긴 Pattern을 생성해내는 방법
  • a가 Frequent Pattern이라고 가정한다
  • a가 포함된 Transaction들을 DB|a 라고 하자 (Conditional DB)
  • DB|a에서 b가 Local Frequent Pattern이라면, ab도 Frequent Pattern이다
  • DB|a에서 b도 포함된 DB|ab를 추출
  • 이걸 반복적으로 하다보면, 패턴의 길이가 계속 길어질 것 (Growth)
    • 짧은 길이에서 긴 길이로 계속 길어진다

 

과정 요약

1. Glocal FP-tree를 생성한다
2. 분할정복(Divide and Conquer)을 사용해서, 재귀적으로 들어가서 Frequent Pattern을 찾은 다음 그 결과를 모아서 최종 Frequent Pattern들을 산출한다

 

Construct Global FP-tree from Database

---

Database로부터 Global FP-tree를 생성하는 과정

• DB를 스캔해서 길이가 1인 Frequent Pattern들을 찾는다
• 길이가 1인 Frequent Pattern을 Frequency를 기준으로 내림차순 정렬 해서 F-list를 생성 한다
  • 이때 Frequency가 같은 Item들에 대한 정렬 기준은 나름대로 정하면 되지만, 일관성을 유지해야 한다
  • F-list = f-c-a-b-m-p
• DB를 다시 스캔하면서 각 Transcation들이 Frequent Item만을 갖도록 하고, F-list를 기준으로 정렬한다
• 이렇게 생성된 Frequent Items를 이용해서 FP-tree를 생성한다

• 그 결과 위와 같은 FP-tree가 생성된다
• 이때 각 Item이 들어있는 Node를 가리키는 포인터들이 Linked-list형태로 연결 되어 있어야 한다

 

과정을 조금 더 자세히 보면

• 길이가 1인 Frequent Pattern을 찾고, Frequency를 기준으로 내림차순으로 정렬하여 F-list를 생성한다
• F-list를 기준으로 Transaction들로부터 Frequent Items를 추출한다
• Frequent Items를 트리에 입력해서 FP-tree를 생성한다

 

Benefits of the FP-tree Structure

---

FP-tree의 장점

• Completeness
  • 잃어버리는 Frequent Pattern없이 모든 정보를 온전하게 가진다
• Compactness
  • 불필요한 Infrequent한 Item들은 모두 제거가 된다
  • Frequent가 높은 노드가 루트 근처에 위치하여, 최대한 많이 공유된다
  • Compact하게 만들면, 모두 메인 메모리에 올릴 수 있기 때문에 성능 측면에서 유리하다

 

Ideas with FP-growth

---

그래서 FP-tree로부터 Frequent Pattern을 어떻게 마이닝한다는 건데??

• Frequent Pattern에 새로운 Frequent Item을 재귀적으로 추가함으로써 길이를 늘려간다
• Global FP-tree와 F-list에 대해서
  • Frequent Pattern들을 Disjoint Subset들로 나눈다 (Divide and Conquer)
  • Partitioning을 하기 위해서 F-list의 각 Item을 Base로 해서 Conditional DB를 생성한다
  • 그리고 각각의 Conditional DB에 대해서 Conditional FP-tree를 생성한다
    • Conditional FP-tree에서 Frequent Item을 찾고, 새로운 FP-tree를 생성한다
    • 새로운 Conditional FP-tree를 재귀를 통해 반복적으로 생성하여, Conditional FP-tree가 비어있거나, Single Path를 가진 트리가 될 때까지 반복한다
      • Single Path Tree가 생성되었다면, 해당 Path의 Item에 대해 Sub-path를 생성한다
      • 그 각각의 Sub-path에 Base가 된 Item을 붙이면, Frequent Pattern이 된다

 

으음,, 대충 Divide and Conquer를 사용해서 재귀적으로 길이를 늘려간다는 것은 알겠는데
그래도 아직 잘 모르겠다
더 자세히 살펴보자

 

Partitioning Target Frequent Patterns

---

FP-growth의 일반적인 아이디어

• Frequent Pattern(Database)들이 F-list에 근거하여 Disjoint Subset들로 나눠야져야 한다
• F-list의 역순으로 돌면서 각 Item에 대해 Conditional DB를 생성한다
  • T1: Frequent Pattern 중에 p를 포함하는 Pattern (DB|P)
  • T2: Frequent Pattern 중에 m을 포함하고, p를 포함하지 않는 패턴
  • T3: Frequent Pattern 중에 b를 포함하고, p,m을 포함하지 않는 패턴
  • T4: Frequent Pattern 중에 a를 포함하고, p,m,b를 포함하지 않는 패턴
  • T5: Frequent Pattern 중에 c를 포함하고, p,m,b,a를 포함하지 않는 패턴
  • T6: Frequent Pattern 중에 f를 포함하고, p,m,b,a,c를 포함하지 않는 패턴
    • 즉, 그냥 {f} 이다

 

• Divide and Conquer
  • F-list의 Item들 중에서, 뒤에서부터 하나씩 골라서 Conditional Pattern Base를 생성한다
  • 각각의 Conditional Pattern Base로부터, 모든 Frequent Pattern을 찾아낼 수 있다
    • 이것이 FP-growth algorithm의 핵심이다

 

Constructing P-conditional Pattern Base

---

FP-tree로부터 Conditional Pattern Base를 생성하는 방법

• F-list의 끝에 있는 Item부터 하나씩 돌면서 Conditional Pattern Base를 생성 한다
  • Header table로부터 시작해서 각 Item이 들어있는 위치를 추적한다 (Linked-list)
  • 선택된 Item에 대해서 Header부터 연결된 Link를 돌면서, FP-tree를 Traverse한다
  • 선택된 Item이 들어있는 Path의 Prefix Paths가 해당 Item의 Conditional Pattern Base가 된다
• 예시에서 F-list에서 p가 선택되었다고 하자
  • Header table부터 시작해서 p가 있는 Path들을 추적한다
  • 해당 Path에서 p를 제외한 Prefix Path가 p의 Conditional Pattern Base가 된다
• 이때 m의 Conditional Pattern Base에는 F-list상에서 뒷순서인 p가 포함되지 않는다
  • 이게 FP-growth의 특징

 

Conditional Pattern Base to Conditional FP-tree

---

생성한 Condtional Pattern Base로부터 Conditional FP-tree 생성하기

• 모든 Conditional Database(Pattern Base)에 대해서
  • Global FP-tree를 생성할 때 했던 것을 그대로 똑같이 한다
    • FP-tree를 생성하면서, 각 Item의 Frequency를 축적한다

 

• fcab가 Pattern Base에 있는데 {}-f-c-a까지만 Path가 생성된 이유는 b의 Frequency가 1이기 때문에 Infrequent하기 때문
• Single Path이므로 더 이상의 Recursion은 종료하고, 모든 Sub-path를 찾는다
  • 그 Sub-path들에 Base가 된 Item을 붙이면, 모두 Frequent Pattern이 된다

 

• 한번 끝까지 쭉 해보면 위와 같이 된다
• 모두 빈 트리이거나, Single Path로 형성되었기 때문에 더이상 Recursive하게 들어갈 필요가 없다

 

위의 예시는 모두 Recursion이 아니라, Terminate가 되는 예시였는데
Recursion이 발생하는 예시도 보자

• m의 Conditional Pattern Base를 통해서 Conditonal FP-tree를 생성했더니, Single Path가 아니다
• 그렇기 때문에 Recursive하게 더 들어가야 한다
  • 원래 Base는 m이었는데, Recursive하게 들어가면 Base가 추가된다 
  • am의 Conditional Pattern Base
  • cm의 Conditional Pattern Base
  • fm의 Conditional Pattern Base
  • 각각에 대해서 Condition FP-tree를 생성했더니 모두 Single Path
  • 각 경우에 대해서 Recursion을 종료하고 Frequent Pattern을 찾는다

 

Single Prefix Case

---

Conditional FP-tree가 Single Path를 갖는 경우를 가정해보자

• 이러한 경우에는 더이상 Recursive하게 들어갈 필요가 없다
• Single Path위의 노드들에 대해서 모든 경우의 노드 조합을 생성한다
• 해당 조합의 Union에 Base Item을 붙인 것이 바로 Frequent Pattern이 된다
  • 만약 Item m에 대한 Conditional FP-tree라면, 모든 조합 뒤에 m을 붙인 것이 Frequent Pattern이 된다

 

Pseudo Code

---

FP-growth 알고리즘을 수행하기 위한 Pseudo Code를 보자

procedure FP-Growth (Tree, α)
{
    if Tree contains a single path P then
        for each β = nodes conbination in P do
            pattern = β U α
            support = min(support of the nodes in β)
            /* β에 포함된 Item들 중에 가장 Support가 작은 Item의 Support가 해당 Combination의 Support가 된다 */
    else
        for each ai in the header of Tree do
            pattern β = ai U α
            with support - ai.support
            construct conditional pattern base of β
            TreeB = construct conditional FP-tree of β
            if TreeB != {} then
                call FP-Growth(TreeB, β) // Recursion
}

 

FP-Growth vs Apriori

---

FP-Growth와 Apriori의 성능 비교

• Apriori에서는 Threshold가 낮아지면 Candidate의 수가 많아지기 때문에 성능이 급격하게 떨어진다
• 반면 FP-Growth에서는 Apriori에 비해서 높은 성능을 유지한다

 

Why is FP-Growth Effective?

---

왜 FP-Growth 방식이 효율적인 것일까?

• Divide and Conquer
  • Mining 작업과, Database를 쪼개서 처리하기 때문에 효율적이다
  • 더 작은 Database(Conditional DB)에 대해서 작업을 처리하기 때문
• Other factors
  • Candidate를 생성하고, Test하는 과정이 없다
  • Compact하기 때문에 메모리에 올려서 관리할 수 있다
  • 전체 DB를 계속 Scan할 일이 없다 (2번만 스캔 하면 된다)
    • Scan 1: 처음에 길이가 1인 Frequent Pattern을 찾을 때
    • Scan 2: Global FP-tree를 Construct 할 때