FP-growth算法發現頻繁項集——發現頻繁項集
上篇介紹瞭如何構建FP樹,FP樹的每條路徑都滿足最小支持度,我們需要做的是在一條路徑上尋找到更多的關聯關系。
抽取條件模式基
首先從FP樹頭指針表中的單個頻繁元素項開始。對於每一個元素項,獲得其對應的條件模式基(conditional pattern base),單個元素項的條件模式基也就是元素項的關鍵字。條件模式基是以所查找元素項為結尾的路徑集合。每一條路徑其實都是一條前輟路徑(perfix path)。簡而言之,一條前綴路徑是介於所査找元素項與樹根節點之間的所有內容。
下圖是以{s:2}或{r:1}為元素項的前綴路徑:
{s}的條件模式基,即前綴路徑集合共有兩個:{{z,x,y,t}, {x}};{r}的條件模式基共三個:{{z}, {z,x,y,t}, {x,s}}。
尋找條件模式基的過程實際上是從FP樹的每個葉子節點回溯到根節點的過程。我們可以通過頭指針列表headTable開始,通過指針的連接快速訪問到所有根節點。下表是上圖FP樹的所有條件模式基:
創建條件FP樹
為瞭發現更多的頻繁項集,對於每一個頻繁項,都要創建一棵條件FP樹。可以使用剛才發現的條件模式基作為輸入數據,並通過相同的建樹代碼來構建這些樹。然後,遞歸地發現頻繁項、發現條件模式基,以及發現另外的條件樹。
以頻繁項r為例,構建關於r的條件FP樹。r的三個前綴路徑分別是{z},{z,x,y,t},{x,s},設最小支持度minSupport=2,則y,t,s被過濾掉,剩下{z},{z,x},{x}。y,s,t雖然是條件模式基的一部分,但是並不屬於條件FP樹,即對於r來說,它們不是頻繁的。如下圖所示,y→t→r和s→r的全局支持度都為1,所以y,t,s對於r的條件樹來說是不頻繁的。
過濾後的r條件樹如下:
重復上面步驟,r的條件模式基是{z,x},{x},已經沒有能夠滿足最小支持度的路徑, 所以r的條件樹僅有一個。需要註意的是,雖然{z,x},{x}中共存在兩個x,但{z,x}中,z是x的父節點,在構造條件FP樹時不能直接將父節點移除,僅能從子節點開始逐級移除。
代碼如下:
def ascendTree(leafNode, prefixPath): if leafNode.parent != None: prefixPath.append(leafNode.name) ascendTree(leafNode.parent, prefixPath) def findPrefixPath(basePat, headTable): condPats = {} treeNode = headTable[basePat][1] while treeNode != None: prefixPath = [] ascendTree(treeNode, prefixPath) if len(prefixPath) > 1: condPats[frozenset(prefixPath[1:])] = treeNode.count treeNode = treeNode.nodeLink return condPats def mineTree(inTree, headerTable, minSup=1, preFix=set([]), freqItemList=[]): # order by minSup asc, value asc bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: (p[1][0],p[0]))] for basePat in bigL: newFreqSet = preFix.copy() newFreqSet.add(basePat) freqItemList.append(newFreqSet) # 通過條件模式基找到的頻繁項集 condPattBases = findPrefixPath(basePat, headerTable) myCondTree, myHead = createTree(condPattBases, minSup) if myHead != None: print('condPattBases: ', basePat, condPattBases) myCondTree.disp() print('*' * 30) mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) simpDat = loadSimpDat() dictDat = createInitSet(simpDat) myFPTree,myheader = createTree(dictDat, 3) myFPTree.disp() condPats = findPrefixPath('z', myheader) print('z', condPats) condPats = findPrefixPath('x', myheader) print('x', condPats) condPats = findPrefixPath('y', myheader) print('y', condPats) condPats = findPrefixPath('t', myheader) print('t', condPats) condPats = findPrefixPath('s', myheader) print('s', condPats) condPats = findPrefixPath('r', myheader) print('r', condPats) mineTree(myFPTree, myheader, 2)
控制臺信息:
總結
本篇文章就到這瞭,本例可以發現兩個頻繁項集{z,x}和{x}。取得頻繁項集後,可以根據置信度發現關聯規則,這一步較為簡單,可參考上篇的相關內容,不在贅述。希望能夠給你帶來幫助,也希望您能夠多多關註WalkonNet的其他精彩內容!