什麼是 FP-Growth？
FP-Growth（Frequent Pattern Growth）是一種高效的關聯規則挖掘演算法，由 Han 等人於 2000 年提出。它通過構建一棵頻繁模式樹（FP-Tree），避免了 Apriori 演算法反覆掃描數據庫和產生大量候選項集的缺點，僅需掃描兩次數據庫即可完成頻繁項集挖掘。
核心流程
- 第一次掃描：統計各單項頻度，過濾掉低於最小支持度的項，按支持度降序排列得到頻繁項集列表（F-List）。
- 構建 FP-Tree：
- 創建根節點（標記為 null）。
- 第二次掃描數據庫，對每條事務記錄，按 F-List 順序過濾並排序後，插入樹中。相同前綴共享路徑，節點計數器累加。
- 維護頭指針表，鏈接同項目節點，便於後續條件模式基構建。
- 遞歸挖掘：從頻繁項集列表末尾（支持度最低）開始，對每個項目：
- 沿頭指針表找到所有該項目節點，收集其前綴路徑構成條件模式基。
- 根據條件模式基構建條件 FP-Tree。
- 遞歸挖掘條件樹，得到包含該項目的所有頻繁項集。
關鍵優勢
- 無候選項集生成：直接從壓縮樹中挖掘，大幅減少內存與計算開銷。
- 兩次掃描：適合大規模數據集。
- 壓縮存儲：共享前綴路徑，樹規模遠小於原始數據。
適用場景與限制
適用於高頻、長模式的數據集。若數據極其稀疏或最小支持度極低，FP-Tree 可能接近原始數據大小，優勢減弱。此外，遞歸深度可能較大，需注意棧溢出。
學習建議
- 手動推演一個小數據集（如 5 條事務）的樹構建與挖掘過程。
- 對比 Apriori 的候選生成-剪枝流程，理解「無候選」的含義。
- 參考經典論文《Mining Frequent Patterns without Candidate Generation》（Han et al., 2000）。
