第12章 使用FP-growth算法來(lái)高效發(fā)現(xiàn)頻繁項(xiàng)集
前言
在 第11章 時(shí)我們已經(jīng)介紹了用 Apriori 算法發(fā)現(xiàn) 頻繁項(xiàng)集 與 關(guān)聯(lián)規(guī)則。
本章將繼續(xù)關(guān)注發(fā)現(xiàn) 頻繁項(xiàng)集 這一任務(wù)相叁，并使用 FP-growth 算法更有效的挖掘 頻繁項(xiàng)集。
FP-growth 算法簡(jiǎn)介
- 一種非常好的發(fā)現(xiàn)頻繁項(xiàng)集算法业汰。
- 基于Apriori算法構(gòu)建,但是數(shù)據(jù)結(jié)構(gòu)不同歹颓，使用叫做
FP樹(shù)的數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)來(lái)存儲(chǔ)集合铜秆。下面我們會(huì)介紹這種數(shù)據(jù)結(jié)構(gòu)。
FP-growth 算法步驟
- 基于數(shù)據(jù)構(gòu)建FP樹(shù)
- 從FP樹(shù)種挖掘頻繁項(xiàng)集
FP樹(shù) 介紹
- FP樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)如下:
class treeNode:
def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue # 節(jié)點(diǎn)名稱
self.count = numOccur # 節(jié)點(diǎn)出現(xiàn)次數(shù)
self.nodeLink = None # 不同項(xiàng)集的相同項(xiàng)通過(guò)nodeLink連接在一起
# needs to be updated
self.parent = parentNode # 指向父節(jié)點(diǎn)
self.children = {} # 存儲(chǔ)葉子節(jié)點(diǎn)
FP-growth 原理
基于數(shù)據(jù)構(gòu)建FP樹(shù)
步驟1:
- 遍歷所有的數(shù)據(jù)集合芥炭，計(jì)算所有項(xiàng)的支持度漓库。
- 丟棄非頻繁的項(xiàng)。
-
基于 支持度 降序排序所有的項(xiàng)园蝠。
步驟1-3 - 所有數(shù)據(jù)集合按照得到的順序重新整理渺蒿。
-
重新整理完成后，丟棄每個(gè)集合末尾非頻繁的項(xiàng)彪薛。
步驟4-5
步驟2:
- 讀取每個(gè)集合插入FP樹(shù)中茂装，同時(shí)用一個(gè)頭部鏈表數(shù)據(jù)結(jié)構(gòu)維護(hù)不同集合的相同項(xiàng)。
步驟6-1
最終得到下面這樣一棵FP樹(shù)
從FP樹(shù)中挖掘出頻繁項(xiàng)集
步驟3:
對(duì)頭部鏈表進(jìn)行降序排序
-
對(duì)頭部鏈表節(jié)點(diǎn)從小到大遍歷善延，得到條件模式基少态，同時(shí)獲得一個(gè)頻繁項(xiàng)集。
步驟6-2如上圖易遣，從頭部鏈表 t 節(jié)點(diǎn)開(kāi)始遍歷彼妻，t 節(jié)點(diǎn)加入到頻繁項(xiàng)集。找到以 t 節(jié)點(diǎn)為結(jié)尾的路徑如下:
步驟7-1去掉FP樹(shù)中的t節(jié)點(diǎn)豆茫，得到條件模式基<左邊路徑,左邊是值>[z,x,y,s,t]:2侨歉，[z,x,y,r,t]:1 。條件模式基的值取決于末尾節(jié)點(diǎn) t 揩魂，因?yàn)?t 的出現(xiàn)次數(shù)最小幽邓，一個(gè)頻繁項(xiàng)集的支持度由支持度最小的項(xiàng)決定。所以 t 節(jié)點(diǎn)的條件模式基的值可以理解為對(duì)于以 t 節(jié)點(diǎn)為末尾的前綴路徑出現(xiàn)次數(shù)火脉。
-
條件模式基繼續(xù)構(gòu)造條件 FP樹(shù)牵舵， 得到頻繁項(xiàng)集柒啤，和之前的頻繁項(xiàng)組合起來(lái)，這是一個(gè)遞歸遍歷頭部鏈表生成FP樹(shù)的過(guò)程畸颅，遞歸截止條件是生成的FP樹(shù)的頭部鏈表為空担巩。
根據(jù)步驟 2 得到的條件模式基 [z,x,y,s,t]:2，[z,x,y,r,t]:1 作為數(shù)據(jù)集繼續(xù)構(gòu)造出一棵FP樹(shù)重斑，計(jì)算支持度兵睛，去除非頻繁項(xiàng)，集合按照支持度降序排序窥浪，重復(fù)上面構(gòu)造FP樹(shù)的步驟。最后得到下面 t-條件FP樹(shù) :
步驟7-2然后根據(jù) t-條件FP樹(shù) 的頭部鏈表進(jìn)行遍歷笛丙，從 y 開(kāi)始漾脂。得到頻繁項(xiàng)集 ty 。然后又得到 y 的條件模式基胚鸯，構(gòu)造出 ty的條件FP樹(shù)骨稿，即 ty-條件FP樹(shù)。繼續(xù)遍歷ty-條件FP樹(shù)的頭部鏈表姜钳，得到頻繁項(xiàng)集 tyx坦冠，然后又得到頻繁項(xiàng)集 tyxz. 然后得到構(gòu)造tyxz-條件FP樹(shù)的頭部鏈表是空的，終止遍歷哥桥。我們得到的頻繁項(xiàng)集有 t->ty->tyz->tyzx辙浑，這只是一小部分。
- 條件模式基:頭部鏈表中的某一點(diǎn)的前綴路徑組合就是條件模式基拟糕，條件模式基的值取決于末尾節(jié)點(diǎn)的值判呕。
- 條件FP樹(shù):以條件模式基為數(shù)據(jù)集構(gòu)造的FP樹(shù)叫做條件FP樹(shù)。
FP-growth 算法優(yōu)缺點(diǎn):
* 優(yōu)點(diǎn)： 1. 因?yàn)?FP-growth 算法只需要對(duì)數(shù)據(jù)集遍歷兩次送滞，所以速度更快侠草。
2. FP樹(shù)將集合按照支持度降序排序，不同路徑如果有相同前綴路徑共用存儲(chǔ)空間犁嗅，使得數(shù)據(jù)得到了壓縮边涕。
3. 不需要生成候選集。
4. 比Apriori更快褂微。
* 缺點(diǎn)： 1. FP-Tree第二次遍歷會(huì)存儲(chǔ)很多中間過(guò)程的值功蜓，會(huì)占用很多內(nèi)存。
2. 構(gòu)建FP-Tree是比較昂貴的蕊梧。
* 適用數(shù)據(jù)類型：標(biāo)稱型數(shù)據(jù)(離散型數(shù)據(jù))霞赫。
FP-growth 代碼講解
完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/12.FrequentPattemTree/fpGrowth.py
main 方法大致步驟:
if __name__ == "__main__":
simpDat = loadSimpDat() #加載數(shù)據(jù)集。
initSet = createInitSet(simpDat) #對(duì)數(shù)據(jù)集進(jìn)行整理肥矢，相同集合進(jìn)行合并端衰。
myFPtree, myHeaderTab = createTree(initSet, 3)#創(chuàng)建FP樹(shù)叠洗。
freqItemList = []
mineTree(myFPtree, myHeaderTab, 3, set([]), freqItemList) #遞歸的從FP樹(shù)中挖掘出頻繁項(xiàng)集。
print freqItemList
大家看懂原理旅东，再仔細(xì)跟蹤一下代碼灭抑。基本就沒(méi)有問(wèn)題了抵代。
- 作者：mikechengwei
- GitHub地址: https://github.com/apachecn/MachineLearning
- 版權(quán)聲明：歡迎轉(zhuǎn)載學(xué)習(xí) => 請(qǐng)標(biāo)注信息來(lái)源于 ApacheCN
