FP-growth算法
優點：一般要快於Apriori 缺點：實現比較困難，在某些數據集上性能會下降 適用數據類型：標稱型數據
FP-growth算法將數據存儲在一種稱為FP樹的緊湊數據結構中。FP代表頻繁模式（Frequent Pattern）。一棵FP樹看上去與計算機科學中的其他樹結構類似，但是它通過鏈接（link）來連接相似元素，被連起來的元素項可以看成一個鏈表。圖12-1給出了FP樹的一個例子。
圖12-1 一棵FP樹，看上去和一般的樹沒什麼兩樣，包含著連接相似節點的鏈接
同搜索樹不同的是，一個元素項可以在一棵FP樹中出現多次。FP樹會存儲項集的出現頻率，而每個項集會以路徑的方式存儲在樹中。存在相似元素的集合會共享樹的一部分。只有當集合之間完全不同時，樹才會分叉。 樹節點上給出集合中的單個元素及其在序列中的出現次數，路徑會給出該序列的出現次數。上面這一切聽起來可能有點讓人迷糊，不過不用擔心，稍後就會介紹FP樹的構建過程。
相似項之間的鏈接即節點鏈接（node link），用於快速發現相似項的位置。為了打消讀者的疑惑，下面通過一個簡單例子來說明。表12-1給出了用於生成圖12-1中所示FP樹的數據。
表12-1 用於生成圖12-1中FP樹的事務數據樣例
事務ID 事務中的元素項001
r, z, h, j, p
002
z, y, x, w, v, u, t, s
003
z
004
r, x, n, o, s
005
y, r, x, z, q, t, p
006
y, z, x, e, q, s, t, m
在圖12-1中，元素項z出現了5次，集合{r,z}出現了1次。於是可以得出結論：z一定是自己本身或者和其他符號一起出現了4次。我們再看下z的其他可能性。集合{t,s,y,x,z}出現了2次，集合{t,r,y,x,z}出現了1次。元素項z的右邊標的是5，表示z出現了5次，其中剛才已經給出了4次出現，所以它一定單獨出現過1次。通過觀察表12-1看看剛才的結論是否正確。前面提到{t,r,y,x,z}只出現過1次，在事務數據集中我們看到005號記錄上卻是{y,r,x,z,q,t,p}。那麼，q和p去哪兒了呢？
這裡使用第11章給出的支持度定義，該指標對應一個最小閾值，低於最小閾值的元素項被認為是不頻繁的。如果將最小支持度設為3，然後應用頻繁項分析算法，就會獲得出現3次或3次以上的項集。上面在生成圖12-1中的FP樹時，使用的最小支持度為3，因此q和p並沒有出現在最後的樹中。
FP-growth算法的工作流程如下。首先構建FP樹，然後利用它來挖掘頻繁項集。為構建FP樹，需要對原始數據集掃瞄兩遍。第一遍對所有元素項的出現次數進行計數。記住第11章中給出的Apriori原理，即如果某元素是不頻繁的，那麼包含該元素的超集也是不頻繁的，所以就不需要考慮這些超集。數據庫的第一遍掃瞄用來統計出現的頻率，而第二遍掃瞄中只考慮那些頻繁元素。
FP-growth的一般流程
- 收集數據：使用任意方法。
- 準備數據：由於存儲的是集合，所以需要離散數據。如果要處理連續數據，需要將它們量化為離散值。
- 分析數據：使用任意方法。
- 訓練算法：構建一個FP樹，並對樹進行挖據。
- 測試算法：沒有測試過程。
- 使用算法：可用於識別經常出現的元素項，從而用於制定決策、推薦元素或進行預測等應用中。