Skip to content

Machine Learning › 非監督式學習 › 關聯規則 › FP-Growth

FP-Growth ​

找頻繁項目集的另一種演算法,結果與 Apriori 完全相同,但通常快很多。它不逐層產生大量候選組合,而是先把交易壓縮成一棵 FP-tree(共享前綴的樹),再從樹上遞迴挖掘頻繁模式。

text
1. 掃描一次:計算每個項目的 support,刪掉不頻繁的項目
2. 再掃描一次:每筆交易依項目頻率排序後插入 FP-tree(共同前綴共用節點)
3. 從樹上對每個項目建立條件樹 (conditional FP-tree),遞迴找頻繁模式

用法(mlxtend) ​

python
from mlxtend.frequent_patterns import fpgrowth, association_rules

# df:TransactionEncoder 產生的布林矩陣(見 Apriori 筆記)
itemsets = fpgrowth(df, min_support=0.6, use_colnames=True)     # 和 apriori 的結果相同
rules = association_rules(itemsets, num_itemsets=len(df), metric="lift", min_threshold=1.0)

Apriori vs FP-Growth ​

AprioriFP-Growth
候選項目集逐層產生大量候選不產生
掃描資料次數多次(每層一次)兩次
速度項目多、資料密集時很慢通常快很多
記憶體候選集合可能很大FP-tree 在資料稀疏、前綴少共用時也可能很大
理解難度低較高
結果相同相同

什麼時候用 ​

情境選擇
項目多、交易多、資料密集FP-Growth
教學、小資料任一皆可
資料大到單機放不下Spark MLlib 的 FPGrowth

無論哪個演算法,min_support、confidence、lift 的門檻都要謹慎設定,見 關聯規則。