FP-growth算法

優(yōu)點：一般要快于Apriori。

缺點：實現(xiàn)比較困難，在某些數(shù)據(jù)集上性能會下降。

適用數(shù)據(jù)類型：標(biāo)稱型數(shù)據(jù)。

FP-growth算法將數(shù)據(jù)存儲在一種稱為FP樹的緊湊數(shù)據(jù)結(jié)構(gòu)中。FP代表頻繁模式（Frequent Pattern)。一棵FP樹看上去與計算機(jī)科學(xué)中的其他樹結(jié)構(gòu)類似，但是它通過鏈接(link)來連接相似元素，被連起來的元素項可以看成一個鏈表。圖1給出了FP樹的一個例子。

圖1 一棵FP樹，看上去和一般的樹沒什么兩樣，包含著連接相似節(jié)點的鏈接

同搜索樹不同的是，一個元素項可以在一棵FP樹中出現(xiàn)多次。FP樹會存儲項集的出現(xiàn)頻率，而每個項集會以路徑的方式存儲在樹中。存在相似元素的集合會共享樹的一部分。只有當(dāng)集合之間完全不同時，樹才會分叉。樹節(jié)點上給出集合中的單個元素及其在序列中的出現(xiàn)次數(shù)，路徑會給出該序列的出現(xiàn)次數(shù)。上面這一切聽起來可能有點讓人迷糊，不過不用擔(dān)心，稍后就會介紹FP樹的構(gòu)建過程。

相似項之間的鏈接即節(jié)點鏈接（node link），用于快速發(fā)現(xiàn)相似項的位置。為了打消讀者的疑惑，下面通過一個簡單例子來說明。表1給出了用于生成圖1中所示FP樹的數(shù)據(jù)。

表1 用于生成圖1 中FP樹的事務(wù)數(shù)據(jù)樣例

在圖1中，元素項z出現(xiàn)了5次，集合{r,z}出現(xiàn)了1次。于是可以得出結(jié)論：z一定是自己本身或者和其他符號一起出現(xiàn)了4次。我們再看下z的其他可能性。集合{t,s,y,x,z}出現(xiàn)了2次，集合{t,r,y,x,z}出現(xiàn)了1次。元素項z的右邊標(biāo)的是5，表示z出現(xiàn)了5次，其中剛才已經(jīng)給出了4次出現(xiàn)，所以它一定單獨出現(xiàn)過1次。通過觀察表1看看剛才的結(jié)論是否正確。前面提到{t,r,y,x,z}只出現(xiàn)過1次，在事務(wù)數(shù)據(jù)集中我們看到005號記錄上卻是{y,r,x,z,q,t,p}。那么，q和p去哪兒了呢?

這里使用支持度定義，該指標(biāo)對應(yīng)一個最小閾值，低于最小閾值的元素項被認(rèn)為是不頻繁的。如果將最小支持度設(shè)為3，然后應(yīng)用頻繁項分析算法，就會獲得出現(xiàn)3次或3次以上的項集。上面在生成圖1中的FP樹時，使用的最小支持度為3，因此q和p并沒有出現(xiàn)在最后的樹中。

FP-growth算法的工作流程如下。首先構(gòu)建FP樹，然后利用它來挖掘頻繁項集。為構(gòu)建FP樹，需要對原始數(shù)據(jù)集掃描兩遍。第一遍對所有元素項的出現(xiàn)次數(shù)進(jìn)行計數(shù)。記住Apriori原理，即如果某元素是不頻繁的，那么包含該元素的超集也是不頻繁的，所以就不需要考慮這些超集。數(shù)據(jù)庫的第一遍掃描用來統(tǒng)計出現(xiàn)的頻率，而第二遍掃描中只考慮那些頻繁元素。

FP-growth的一般流程

（1）收集數(shù)據(jù)：使用任意方法。

（2）準(zhǔn)備數(shù)據(jù)：由于存儲的是集合，所以需要離散數(shù)據(jù)。如果要處理連續(xù)數(shù)據(jù)，需要將它們量化為離散值。

（3）分析數(shù)據(jù)：使用任意方法。

（4）訓(xùn)練算法：構(gòu)建一個FP樹，并對樹進(jìn)行挖據(jù)。

（5）測試算法：沒有測試過程。

（6）使用算法：可用于識別經(jīng)常出現(xiàn)的元素項，從而用于制定決策、推薦元素或進(jìn)行預(yù)測等應(yīng)用中。

責(zé)任編輯：admin