[4-1] FP-Growth

앞 강의에 썼던 방법들은 그래도 후보를 먼저 generate 해야 한다는 점이 있어서 그거를 없애려고 한다. 

“이미 찾은 frequent pattern을 조건으로 하는 작은 DB들”에서 패턴을 재귀적으로 확장해 가는 방법

DB|a = a를 포함하는 transaction만 남긴 conditional database.. 그 안에서 “b”가 local frequent item이면 ab도 frequent pattern이 된다.

 

support가 3 이상인 frequent 1-item만 남기고 빈도 내림차순으로 List 만든다! 그리고 정렬해서 FP-tree 를 만든다.

Benefits of the FP-tree Structure

1. Completeness (정보 손실없다)

❑ Preserve complete (i.e., lossless) information for frequent pattern mining

❑ Never break a long pattern of any transaction

2. Compactness (효율적이다)

❑ Remove irrelevant info—infrequent items are gone

❑ Items in frequency descending order: the more frequently occurring, the more likely to be shared

❑ Much reduced size, can be uploaded on memory

 

Ideas with FP-Growth

❑Grow frequent patterns by adding a new frequent item recursively

Given the global FP-tree and F-list,

❑ It follows divide-and-conquer: it partitions the frequent patterns into disjoint subsets (targets)

❑ For the partitioning, it uses each item of F-list. For each item, it constructs conditional pattern-base, and then construct its conditional FP-tree to find the targeted frequent items.

▪ Find a frequent item on the conditional FP-tree, construct a new FPtree conditioned by it, and grow the pattern.

▪ Recursevily repeat the process on each newly created conditional FPtree, until the resulting conditional FP-tree is empty, or it contains only a single path

▪ A single path will generate all the combinations of its sub-paths

▪ Each of the combinations is a frequent pattern

item마다 conditional pattern base와 conditional FP-tree를 만들고,이걸 재귀적으로 반복한다!

 

 

패턴을 중복 없게 나눈다. 그리고 conditional pattern base 를 만든다 and they don't have to think about others because they are disjoint!!

 

해당 item이 등장하는 모든 prefix path를 모아 놓는 것! and the result for each data base is disjoint. p must be loacated below m. it can't be included!

각 item count를 누적하고 frequent한 것만 남겨 그걸로 FP-tree를 만든다

 

이 페이지는 그냥 frequent pattern 를 어떻게 쓰는지? 그냥 간단함

 

 

 

와.. 진짜 recursive 으로 하고 있다! 조건부 FP-tree에서 다시 item을 하나 골라 그 item을 기준으로 또 recursive mining을 하는 구조

 

 

좀 헷가린다잉 ㅠㅠ

트리가 single path면:

• path의 모든 node combination β에 대해
• pattern = β ∪ α
• support = β 안 노드 support의 최소값

이게 왜 minimum이냐면 한 path 안에서 조합의 support는 그 path에서 가장 작은 count에 의해 결정되기 때문이야.

 

근데 single path가 아니면 아까 말했다시피 item 하나를 고르고, 그 item을 붙인 패턴 β를 만든 뒤, 그 β에 대한 조건부 트리를 만들어 다시 같은 일을 반복한다.

 

minimum support 가 작다라는게 canditate 많이 만든다는 뜻. 그럴 때는 지금 이 방법이 좋다

 

 

 

Why Is FP-Growth Effective?

Divide-and-conquer:

❑ Decompose both the mining task and a database according to the frequent patterns obtained so far

❑ Leads to focused search of smaller databases

전체 DB를 계속 보는 게 아니라 더 작은 DB만 보게 되므로 검색이 집중되고 효율적임

Other factors

❑ No candidate generation and no candidate test

❑ Compressed database: FP-tree structure (managed on memory)

❑ No repeated scans of the entire database: just twice

▪ 1: Counting the frequency of each item

▪ 2: Building the global FP-tree

 

정리하면 후보 생성이 없고, DB를 압축하고, 전체 DB를 두 번만 읽으며, divide-and-conquer로 작은 문제를 푸는 구조이다.