頻繁項集挖掘算法之FPGrowth

背景：

頻繁項集挖掘算法用於挖掘經常一起出現的item集合（稱為頻繁項集），通過挖掘出這些頻繁項集，當在一個事務中出現頻繁項集的其中一個item，則可以把該頻繁項集的其他item作為推薦。比如經典的購物籃分析中啤酒、尿布故事，啤酒和尿布經常在用戶的購物籃中一起出現，通過挖掘出啤酒、尿布這個啤酒項集，則當一個用戶買了啤酒的時候可以為他推薦尿布，這樣用戶購買的可能性會比較大，從而達到組合營銷的目的。

常見的頻繁項集挖掘算法有兩類，一類是Apriori算法，另一類是FPGrowth。Apriori通過不斷的構造候選集、篩選候選集挖掘出頻繁項集，需要多次掃描原始數據，當原始數據較大時，磁盤I/O次數太多，效率比較低下。FPGrowth算法則隻需掃描原始數據兩遍，通過FP-tree數據結構對原始數據進行壓縮，效率較高。

FPGrowth算法主要分為兩個步驟：FP-tree構建、遞歸挖掘FP-tree。FP-tree構建通過兩次數據掃描，將原始數據中的事務壓縮到一個FP-tree樹，該FP-tree類似於前綴樹，相同前綴的路徑可以共用，從而達到壓縮數據的目的。接著通過FP-tree找出每個item的條件模式基、條件FP-tree，遞歸的挖掘條件FP-tree得到所有的頻繁項集。算法的主要計算瓶頸在FP-tree的遞歸挖掘上，下麵詳細介紹FPGrowth算法的主要步驟。

FPGrowth的算法步驟：

FP-tree構建

1. 第一遍掃描數據，找出頻繁1項集L，按降序排序
2. 第二遍掃描數據：
  - 對每個transaction，過濾不頻繁集合，剩下的頻繁項集按L順序排序
  - 把每個transaction的頻繁1項集插入到FP-tree中，相同前綴的路徑可以共用
  - 同時增加一個header table，把FP-tree中相同item連接起來，也是降序排序
  - ==>

頻繁項挖掘
1. 從header table的最下麵的item開始，構造每個item的條件模式基（conditional pattern base）
  - 順著header table中item的鏈表，找出所有包含該item的前綴路徑，這些前綴路徑就是該item的條件模式基（CPB）
  - 所有這些CPB的頻繁度（計數）為該路徑上item的頻繁度（計數）
  - 如包含p的其中一條路徑是fcamp，該路徑中p的頻繁度為2，則該CPB fcam的頻繁度為2
2. 構造條件FP-tree（conditional FP-tree）
  - 累加每個CPB上的item的頻繁度（計數），過濾低於閾值的item，構建FP-tree
  - 如m的CPB{<fca:2>, <fcab:1>}，f:3, c:3, a:3, b:1, 閾值假設為3，過濾掉b
3. FP-Growh：遞歸的挖掘每個條件FP-tree，累加後綴頻繁項集，直到找到FP-tree為空或者FP-tree隻有一條路徑（隻有一條路徑情況下，所有路徑上item的組合都是頻繁項集）