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:
對頭部鏈表進行降序排序對頭部鏈表節點從小到大遍歷,得到條件模式基,同時獲得一個頻繁項集。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 ,只作分享,不作任何商業用途,版權歸原作者所有