用FP-growth算法發現頻繁項集

這篇文章主要講解了“用FP-growth算法發現頻繁項集”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“用FP-growth算法發現頻繁項集”吧！

抽取條件模式基

　　首先從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)

　　控制臺信息：

感謝各位的閱讀，以上就是“用FP-growth算法發現頻繁項集”的內容了，經過本文的學習后，相信大家對用FP-growth算法發現頻繁項集這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！