背景：
頻繁項集挖掘算法用于挖掘經常一起出現的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項集l，按降序排序
第二遍掃描資料：
對每個transaction，過濾不頻繁集合，剩下的頻繁項集按l順序排序
把每個transaction的頻繁1項集插入到fp-tree中，相同字首的路徑可以共用
同時增加一個header table，把fp-tree中相同item連接配接起來，也是降序排序
==>
頻繁項挖掘
從header table的最下面的item開始，構造每個item的條件模式基（conditional pattern base）
順着header table中item的連結清單，找出所有包含該item的字首路徑，這些字首路徑就是該item的條件模式基（cpb）
所有這些cpb的頻繁度（計數）為該路徑上item的頻繁度（計數）
如包含p的其中一條路徑是fcamp，該路徑中p的頻繁度為2，則該cpb fcam的頻繁度為2
構造條件fp-tree（conditional fp-tree）
累加每個cpb上的item的頻繁度（計數），過濾低于門檻值的item，建構fp-tree
fp-growh：遞歸的挖掘每個條件fp-tree，累加字尾頻繁項集，直到找到fp-tree為空或者fp-tree隻有一條路徑（隻有一條路徑情況下，所有路徑上item的組合都是頻繁項集）
注意點：
fp-tree中header table按item降序排序原因
共用字首：不排序會造成不能共用字首
更多的共用字首：頻繁的item會在樹的上層，可以被更多的共享；升序排序會造成那些頻繁出現的item出現在樹的分支中，不能更多的共用字首
參考文獻：
<a target="_blank" href="https://cwiki.apache.org/confluence/display/mahout/parallel+frequent+pattern+mining">mahout并行化fpgrowth實作</a>