FP-growth 算法簡介
- 一種非常好的發現頻繁項集算法。
- 基於Apriori算法構建,但是數據結構不同，使用叫做 FP樹 的數據結構結構來存儲集合。下面我們會介紹這種數據結構。
FP-growth 算法步驟
- 基於數據構建FP樹
- 從FP樹種挖掘頻繁項集
FP樹 介紹
- FP樹的節點結構如下:
class treeNode:
def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue # 節點名稱
self.count = numOccur # 節點出現次數
self.nodeLink = None # 不同項集的相同項通過nodeLink連接在一起
# needs to be updated
self.parent = parentNode # 指向父節點
self.children = {} # 存儲葉子節點
FP-growth 原理
基於數據構建FP樹
步驟1:
- 遍歷所有的數據集合，計算所有項的支持度。
- 丟棄非頻繁的項。
- 基於 支持度 降序排序所有的項。
- 遍歷所有的數據集合，計算所有項的支持度
- 所有數據集合按照得到的順序重新整理。
- 重新整理完成後，丟棄每個集合末尾非頻繁的項。
步驟2: 6. 讀取每個集合插入FP樹中，同時用一個頭部鏈表數據結構維護不同集合的相同項。
最終得到下面這樣一棵FP樹
從FP樹中挖掘出頻繁項集
步驟3:
- 對頭部鏈表進行降序排序
- 對頭部鏈表節點從小到大遍歷，得到條件模式基，同時獲得一個頻繁項集。
- 如上圖，從頭部鏈表 t 節點開始遍歷，t 節點加入到頻繁項集。找到以 t 節點為結尾的路徑如下:
- 去掉FP樹中的t節點，得到條件模式基[z,x,y,s,t]:2，[z,x,y,r,t]:1 。條件模式基的值取決於末尾節點 t ，因為 t 的出現次數最小，一個頻繁項集的支持度由支持度最小的項決定。所以 t 節點的條件模式基的值可以理解為對於以 t 節點為末尾的前綴路徑出現次數。
- 條件模式基繼續構造條件 FP樹， 得到頻繁項集，和之前的頻繁項組合起來，這是一個遞歸遍歷頭部鏈表生成FP樹的過程，遞歸截止條件是生成的FP樹的頭部鏈表為空。 根據步驟 2 得到的條件模式基 [z,x,y,s,t]:2，[z,x,y,r,t]:1 作為數據集繼續構造出一棵FP樹，計算支持度，去除非頻繁項，集合按照支持度降序排序，重複上面構造FP樹的步驟。最後得到下面 t-條件FP樹 :
- 然後根據 t-條件FP樹 的頭部鏈表進行遍歷，從 y 開始。得到頻繁項集 ty 。然後又得到 y 的條件模式基，構造出 ty的條件FP樹，即 ty-條件FP樹。繼續遍歷ty-條件FP樹的頭部鏈表，得到頻繁項集 tyx，然後又得到頻繁項集 tyxz. 然後得到構造tyxz-條件FP樹的頭部鏈表是空的，終止遍歷。我們得到的頻繁項集有 t->ty->tyz->tyzx，這只是一小部分。
- 條件模式基:頭部鏈表中的某一點的前綴路徑組合就是條件模式基，條件模式基的值取決於末尾節點的值。
- 條件FP樹:以條件模式基為數據集構造的FP樹叫做條件FP樹。
FP-growth 算法優缺點:
* 優點： 1. 因為 FP-growth 算法只需要對數據集遍歷兩次，所以速度更快。
2. FP樹將集合按照支持度降序排序，不同路徑如果有相同前綴路徑共用存儲空間，使得數據得到了壓縮。
3. 不需要生成候選集。
4. 比Apriori更快。
* 缺點： 1. FP-Tree第二次遍歷會存儲很多中間過程的值，會佔用很多內存。
2. 構建FP-Tree是比較昂貴的。
* 適用數據類型：標稱型數據(離散型數據)。
FP-growth 代碼講解
完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/12.FrequentPattemTree/fpGrowth.py
main 方法大致步驟:
if __name__ == "__main__":
simpDat = loadSimpDat() #加載數據集。
initSet = createInitSet(simpDat) #對數據集進行整理，相同集合進行合併。
myFPtree, myHeaderTab = createTree(initSet, 3)#創建FP樹。
freqItemList = []
mineTree(myFPtree, myHeaderTab, 3, set([]), freqItemList) #遞歸的從FP樹中挖掘出頻繁項集。
print freqItemList
大家看懂原理，再仔細跟蹤一下代碼。基本就沒有問題了。
來源：mikechengwei / ApacheCN ，只作分享，不作任何商業用途，版權歸原作者所有
分享到:
閱讀更多 科科大數據 的文章
