前言

??上一篇文章介紹了用來挖掘發(fā)現(xiàn)強關(guān)聯(lián)規(guī)則的Apriori算法。同時也知道了Apriori算法在實現(xiàn)過程中由于需要頻繁的掃描數(shù)據(jù)集導致效率較低。

??FP-growth算法基于Apriori構(gòu)建，但采用了高級的數(shù)據(jù)結(jié)構(gòu)減少掃描次數(shù)，大大加快了算法速度。FP-growth算法只需要對數(shù)據(jù)庫進行兩次掃描，而Apriori算法對于每個潛在的頻繁項集都會掃描數(shù)據(jù)集判定給定模式是否頻繁，因此FP-growth算法的速度要比Apriori算法快。

FP-growth算法優(yōu)缺點

• 優(yōu)點：

因為 FP-growth 算法只需要對數(shù)據(jù)集遍歷兩次，所以速度更快。

FP樹將集合按照支持度降序排序，不同路徑如果有相同前綴路徑共用存儲空間，使得數(shù)據(jù)得到了壓縮。

不需要生成候選集。

比Apriori更快。

• 缺點：

FP-Tree第二次遍歷會存儲很多中間過程的值，會占用很多內(nèi)存。

構(gòu)建FP-Tree是比較昂貴的。
適用數(shù)據(jù)類型：標稱型數(shù)據(jù)(離散型數(shù)據(jù))。

FP-growth算法發(fā)現(xiàn)頻繁項集的基本過程如下：

構(gòu)建FP樹

從FP樹中挖掘頻繁項集

為構(gòu)建FP樹，需要對原始數(shù)據(jù)集掃描兩遍。第一遍對所有元素項的出現(xiàn)次數(shù)進行計數(shù)。數(shù)據(jù)庫的第一遍掃描用來統(tǒng)計出現(xiàn)的頻率，而第二遍掃描中只考慮那些頻繁元素。

FP樹 介紹

• FP樹的節(jié)點結(jié)構(gòu)如下:

class treeNode:def __init__(self, nameValue, numOccur, parentNode):self.name = nameValue # 節(jié)點名稱self.count = numOccur # 節(jié)點出現(xiàn)次數(shù)self.nodeLink = None # 不同項集的相同項通過nodeLink連接在一起# needs to be updatedself.parent = parentNode # 指向父節(jié)點self.children = {} # 存儲葉子節(jié)點

FP-growth 原理

基于數(shù)據(jù)構(gòu)建FP樹

步驟1:

1. 遍歷所有的數(shù)據(jù)集合，計算所有項的支持度。
2. 丟棄非頻繁的項。
3. 基于 支持度 降序排序所有的項。

4. 所有數(shù)據(jù)集合按照得到的順序重新整理。
5. 重新整理完成后，丟棄每個集合末尾非頻繁的項。

步驟2:

1. 讀取每個項集插入FP樹中，同時用一個頭部鏈表數(shù)據(jù)結(jié)構(gòu)維護不同集合的相同項。

最終得到下面這樣一棵FP樹

步驟3:

從FP樹中挖掘出頻繁項集

1. 對頭部鏈表進行降序排序
2. 對頭部鏈表節(jié)點從小到大遍歷，得到條件模式基，同時獲得一個頻繁項集。

如上圖，從頭部鏈表 t 節(jié)點開始遍歷，t 節(jié)點加入到頻繁項集。找到以 t 節(jié)點為結(jié)尾的路徑如下:

??去掉FP樹中的t節(jié)點，得到條件模式基（[路徑]:值），[z,x,y,s,t]:2，[z,x,y,r,t]:1 。條件模式基的值取決于末尾節(jié)點 t ，因為 t 的出現(xiàn)次數(shù)最小，一個頻繁項集的支持度由支持度最小的項決定。所以 t 節(jié)點的條件模式基的值可以理解為對于以 t 節(jié)點為末尾的前綴路徑出現(xiàn)次數(shù)。

3. 條件模式基繼續(xù)構(gòu)造條件 FP樹， 得到頻繁項集，和之前的頻繁項組合起來，這是一個遞歸遍歷頭部鏈表生成FP樹的過程，遞歸截止條件是生成的FP樹的頭部鏈表為空。

根據(jù)步驟 2 得到的條件模式基 [z,x,y,s,t]:2，[z,x,y,r,t]:1 作為數(shù)據(jù)集繼續(xù)構(gòu)造出一棵FP樹，計算支持度，去除非頻繁項，集合按照支持度降序排序，重復上面構(gòu)造FP樹的步驟。最后得到下面 t-條件FP樹 :

據(jù) t-條件FP樹 的頭部鏈表進行遍歷，從 y 開始。得到頻繁項集 [t,y] 。然后又得到 y 的條件模式基，構(gòu)造出 [t,y] 的條件FP樹，即 ty-條件FP樹。繼續(xù)遍歷ty-條件FP樹的頭部鏈表，得到頻繁項集 [t,y,x] ，然后又得到頻繁項集 [t,y,x,z] 。 然后得到構(gòu)造 tyxz-條件FP樹 的頭部鏈表是空的，終止遍歷。我們得到的頻繁項集有 $[t]\to [t,y]\to [t,y,z]\to [t,y,z,x]$，這只是一小部分。

• 條件模式基:頭部鏈表中的某一點的前綴路徑組合就是條件模式基，條件模式基的值取決于末尾節(jié)點的值。
• 條件FP樹:以條件模式基為數(shù)據(jù)集構(gòu)造的FP樹叫做條件FP樹。

FP-growth 代碼講解

完整代碼地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/12.FrequentPattemTree/fpGrowth.py

main 方法大致步驟:

if __name__ == "__main__":simpDat = loadSimpDat() #加載數(shù)據(jù)集。initSet = createInitSet(simpDat) #對數(shù)據(jù)集進行整理，相同集合進行合并。myFPtree, myHeaderTab = createTree(initSet, 3)#創(chuàng)建FP樹。freqItemList = []mineTree(myFPtree, myHeaderTab, 3, set([]), freqItemList) #遞歸的從FP樹中挖掘出頻繁項集。print freqItemList

大家看懂原理，再仔細跟蹤一下代碼?；揪蜎]有問題了。

參考文章：https://github.com/apachecn/AiLearning/blob/dev/blog/ml/12.使用FP-growth算法來高效發(fā)現(xiàn)頻繁項集.md

總結(jié)

以上是生活随笔為你收集整理的【机器学习】数据挖掘算法——关联规则（三），FP-growth算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。