使用FP-growth算法高效發現頻繁項集
1. 介紹
FP-growth（Frequent Pattern Tree，頻繁模式樹）算法是為了解決 Apriori 算法每次增加頻繁項集得大小都要周遊整個資料庫的缺點，特别是當資料集很大時。FP-growth 算法基于 Apriori 建構，但采用了進階的資料結構減少了掃描次數，加快了算法速度。
FP-growth 算法的任務是：将資料集存儲在一個特定的稱為 FP 樹的結構之後發現頻繁項集或者頻繁項對，雖然它能夠高效地發現頻繁項集，但是不能用來發現關聯規則，也就是隻優化了 Apriori 算法兩個功能中的前一個功能。
FP-growth 算法隻需要對資料集進行兩次掃描，是以即使資料集很大時也不會花費太多的時間在掃描資料集上。該算法發現頻繁項集的基本過程如下：
1）建構 FP 樹
2）從 FP 樹中挖掘頻繁項集
2. 算法詳解
2.1 FP-growth 的一般流程如下：
- 先掃描一遍資料集，得到頻繁項為 1 的項目集，定義最小支援度 min_support（項目出現最少次數），删除掉那些小于最小支援度的項目，然後将原資料集中的條目按項目集降序排列。
- 第二次掃描，建立項頭表（從上往下降序），以及 FP 樹。
- 對于每一個項目（可以按照從下往上的順序）找到其條件模式基（CPB，conditional pattern base），遞歸調用樹結構，删除小于最小支援度的項。如果最終呈現單一路徑的樹結構，則直接列舉所有組合；非單一路徑的，則繼續調用樹結構，直到形成單一路徑即可。
2.2 示例說明
如下表示的資料清單（第一列為事務 ID，第二列為事務中的元素項）：
| 事務 ID | 事務中的元素項 |
|---|---|
| 1 | r，z，h，j，p |
| 2 | z，y，x，w，v，u，t，s |
| 3 | z |
| 4 | r，x，n，o，s |
| 5 | y，r，x，z，q，t，p |
| 6 | y，z，x，e，q，s，t，m |
第一步：建構 FP 樹
建構 FP 樹是算法的第一步，在 FP 樹的基礎之上再對頻繁項集進行挖掘。為了建構 FP 樹，要對資料集掃描兩次，對一次對所有元素項出現的次數進行計數，記住：如果一個元素不是頻繁的，那麼包含該元素的超集也不是頻繁的，是以不需要考慮這些超集；第一次掃描隻考慮那些頻繁項集。
- 掃描資料集，對每個事務進行統計：
| r | z | h | j | p | y | x | w | v | u | t | s | n | o | q | e | m |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 5 | 1 | 1 | 2 | 3 | 4 | 1 | 1 | 1 | 3 | 3 | 1 | 1 | 2 | 1 | 1 |
- 假若設定最小支援度（即事務最小出現次數）為 3，删除低于最小支援度的事務，按照降序重新排列資料集：
| z | x | y | r | s | t |
|---|---|---|---|---|---|
| 5 | 4 | 3 | 3 | 3 | 3 |
- 根據項目出現次數重新調整事務項：
| 事務 ID | 事務中的事務項 | 重新排序的事務項 |
|---|---|---|
| 1 | r，z，h，j，p | z，r |
| 2 | z，y，x，w，v，u，t，s | z，x，y，s，t |
| 3 | z | z |
| 4 | r，x，n，o，s | x，s，r |
| 5 | y，r，x，z，q，t，p | z，x，y，r，t |
| 6 | y，z，x，e，q，s，t，m | z，x，y，s，t |
-
建構 FP 樹
依次加入各條清單{（z，r）,（z，x，y，s，t）,…,（z，x，y，s，t）}，出現相同的節點進行累加，最終得到 FP 樹：
關聯分析——FP-growth算法使用FP-growth算法高效發現頻繁項集1. 介紹2. 算法詳解
第二步：從 FP 樹中挖掘頻繁項集
從 FP 樹中抽取頻繁項集的三個基本步驟：
1）從 FP 樹中獲得條件模式基；
2）利用條件模式基，建構一個條件FP樹；
3）疊代重複步驟1）、2）直到樹隻包含一個元素項為止。
1）抽取條件模式基
首先從頭指針表中的每個頻繁元素項開始，對每個元素項，獲得其對應的條件模式基（conditional pattern base）。條件模式基是以所查找元素項為結尾的路徑集合。每一條路徑其實都是一條字首路徑（prefix path）。簡而言之，一條字首路徑是介于所查找元素項與樹根節點之間的所有内容。
則每一個頻繁元素項的所有字首路徑（條件模式基）為：
| 頻繁項 | 字首路徑(條件模式基) |
|---|---|
| z | {}:5 |
| x | {z}:3,{}:1 |
| y | {z,x}:3 |
| s | {z,x,y}:2,{x}:1 |
| r | {z,x,y}:1,{x,s}:1,{z}:1 |
| t | {z,x,y,s}:2,{z,x,y,r}:1 |
2）建構條件 FP 樹
按照從下往上的順序，對于每一個頻繁項，根據其條件模式基，建立一棵條件 FP 樹，然後根據最小支援度删除一些節點，最後得到該元素的頻繁項集。
例如，對于 t，根據其條件模式基 {z,x,y,s}:2，{z,x,y,r}:1，構造條件 FP 樹如下，删除小于支援度的節點：
3）遞歸查找頻繁項集
上例形成單路徑後，元素 t 與其條件 FP 樹中各元素進行組合，得到 t 的頻繁項集：{ {tz:3}，{tx:3}，{ty:3}，{tzx:3}，{tzy:3}，{txy:3}，{tzxy:3} }。
接下來考慮其他元素，依照上述方法執行，即可得到每個元素的頻繁項集。
整個過程如下圖：
根據 FP-growth 算法，最終得到的支援度不小于3的頻繁項集如下：
| item | 條件模式基 | 條件 FP 樹 | 産生的頻繁項集 |
|---|---|---|---|
| z | {}:5 | {} | {z:5} |
| x | {z:3},{}:1 | {z:3} | {x:4}，{x,z:3} |
| y | {z,x:3} | {z:3,x:3} | {y:3}，{y,z:3},{y,x:3},{y,z,x:3} |
| s | {z,x,y:2},{x:1} | {x:3} | {s:3}，{s,x:3} |
| r | {z,x,y:1},{x,s:1},{z:1} | {} | {r:3} |
| t | {z,x,y,s:2},{z,x,y,r:1} | {z:3,x:3,y:3} | {t:3}，{t,z:3}，{t,x:3}，{t,y:3}，{t,z,x:3}，{t,z,y:3}，{t,x,y:3}，{t,z,x,y:3} |
注意：當條件 FP 樹不是單一路徑時，則需要遞歸查找頻繁項集。
舉例：如果某節點 I3，得到其條件模式基 {I2,I1:3}、{I2:1}、{I1:3} 構造條件 FP 樹，由于此樹不是單一路徑，是以需要遞歸挖掘 I3。，遞歸考慮 I3，此時得到 I1 的條件模式基 {I2:2},即 I1I3 的條件模式基為 {I2:2}，構造條件 FP 樹，由此得到節點 I3 的頻繁項目集 {I3:6},{{I3,I2:4},{I3,I1:6},{I2,I1,I3:3}}。