資料挖掘算法之關聯規則挖掘（二）FPGrowth算法

版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。 https://blog.csdn.net/qq1010885678/article/details/45244829

之前介紹的apriori算法中因為存在許多的缺陷，例如進行大量的全表掃描和計算量巨大的自然連接配接，是以現在幾乎已經不再使用

在mahout的算法庫中使用的是PFP算法，該算法是FPGrowth算法的分布式運作方式，其内部的算法結構和FPGrowth算法相差并不是十分巨大

是以這裡首先介紹在單機記憶體中運作的FPGrowth算法

還是使用apriori算法的購物車資料作為例子，如下圖所示：

TID為購物車項的編号，i1-i5為商品的編号

FPGrowth算法的基本思想是，首先掃描整個購物車資料表，計算每個商品的支援度，并從大到小從上往下排序，得到如下表所示

從底部最小支援度開始，逐一建構FP樹

建構過程如下圖：

最終建構出的FP樹如下圖

将這個FP樹和支援度表關聯起來如下圖：

支援度表中的每一項都有一個存放指向FP樹中對應節點的指針，例如第一行指向i2:7；第二行指向i1:4，因為i1節點還出現在FP樹中的其他位置，所謂i1:4節點中還存放着指向i1:2節點的指針

通過少數的全表掃描建構好的FP樹将購物車沒有規律的資料變成了一個有迹可循的樹形結構，并且省去了進行巨大的自然連接配接的運算

通過FP樹挖掘出關聯規則：

通過上圖的FP樹，我們可以根據每個商品得到該商品對應的條件模式基，條件FP樹和産生的頻繁模式

例如i5

在FP樹中可以看到，從根節點到i5:1的路徑有兩條：

i2:7-->i1:4-->i5:1

i2:7-->i14-->i3:2-->i5:1

i2:7-->i1:4和i2:7-->i14-->i3:2就是i5的條件模式基，因為最終到達的節點肯定是i5，是以将i5省略

記為{i2,i1:1}{i2,i1,i3:1}，為什麼每個條件模式基的計數為1呢？雖然i2和i1的計數都很大，但是由于i5的計數為1，最終到達i5的重複次數也隻能為1。是以條件模式基的計數是根據路徑中節點的最小計數來決定的

根據條件模式基，我們可以得到該商品的條件FP樹，例如i5：

根據條件FP樹，我們可以進行全排列組合，得到挖掘出來的頻繁模式（這裡要将商品本身，如i5也算進去，每個商品挖掘出來的頻繁模式必然包括這商品本身）

根據FP樹得到的全表如下：

至此，FPGrowth算法輸出的結果就是産生的頻繁模式，FPGrowth算法使用的是分而治之的方式，将一顆可能十分巨大的樹形結構通過構建構條件FP子樹的方式分别處理

但是在商品資料十分巨大的情況下，FPGrowth算法所建構的FP樹可能會大到計算機記憶體都無法加載，這時就要使用分布式的FPGrowth，PFP算法來進行計算

本文參考書：《資料挖掘概念與技術》