讀古今文學網 > 機器學習實戰 > 12.3 從一棵FP樹中挖掘頻繁項集 >

12.3 從一棵FP樹中挖掘頻繁項集

實際上，到現在為止大部分比較困難的工作已經處理完了。接下來寫的代碼不會再像12.2節那樣多了。有了FP樹之後，就可以抽取頻繁項集了。這裡的思路與Apriori算法大致類似，首先從單元素項集合開始，然後在此基礎上逐步構建更大的集合。當然這裡將利用FP樹來做實現上述過程，不再需要原始數據集了。

從FP樹中抽取頻繁項集的三個基本步驟如下：

  1. 從FP樹中獲得條件模式基；
  2. 利用條件模式基，構建一個條件FP樹；
  3. 迭代重複步驟1和步驟2，直到樹包含一個元素項為止。

接下來重點關注第1步，即尋找條件模式基的過程。之後，為每一個條件模式基創建對應的條件FP樹。最後需要構造少許代碼來封裝上述兩個函數，並從FP樹中獲得頻繁項集。

12.3.1　抽取條件模式基

首先從上一節發現的已經保存在頭指針表中的單個頻繁元素項開始。對於每一個元素項，獲得其對應的條件模式基（conditional pattern base）。條件模式基是以所查找元素項為結尾的路徑集合。每一條路徑其實都是一條前綴路徑（prefix path）。簡而言之，一條前綴路徑是介於所查找元素項與樹根節點之間的所有內容。

回到圖12-2，符號r的前綴路徑是{x,s}、{z,x,y}和{z}。每一條前綴路徑都與一個計數值關聯。該計數值等於起始元素項的計數值，該計數值給了每條路徑上r的數目。表12-3列出了上例當中每一個頻繁項的所有前綴路徑。

表12-3　每個頻繁項的前綴路徑

　 頻 繁 項 前綴路徑 z {}5 r {x,s}1, {z,x,y}1, {z}1 x {z}3, {}1 y {z,x}3 s {z,x,y}2, {x}1 t {z,x,y,s}2, {z,x,y,r}1

前綴路徑將被用於構建條件FP樹，但是現在暫時先不需要考慮這件事。為了獲得這些前綴路徑，可以對樹進行窮舉式搜索，直到獲得想要的頻繁項為止，或者使用一個更有效的方法來加速搜索過程。可以利用先前創建的頭指針表來得到一種更有效的方法。頭指針表包含相同類型元素鏈表的起始指針。一旦到達了每一個元素項，就可以上溯這棵樹直到根節點為止。

下面的程序清單給出了前綴路徑發現的代碼，將其添加到文件fpGrowth.py中。

程序清單12-4　發現以給定元素項結尾的所有路徑的函數 

def ascendTree(leafNode, prefixPath):
    #❶ 迭代上溯整棵樹 
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)

def findPrefixPath(basePat, treeNode):
    condPats = {}
    while treeNode != None:
        prefixPath = 
        ascendTree(treeNode, prefixPath)
        if len(prefixPath) > 1:
            condPats[frozenset(prefixPath[1:])] = treeNode.count
        treeNode = treeNode.nodeLink
    return condPats

上述程序中的代碼用於為給定元素項生成一個條件模式基，這通過訪問樹中所有包含給定元素項的節點來完成。當創建樹的時候，使用頭指針表來指向該類型的第一個元素項，該元素項也會鏈接到其後續元素項。函數findPrefixPath遍歷鏈表直到到達結尾。每遇到一個元素項都會調用ascendTree來上溯FP樹，並收集所有遇到的元素項的名稱❶。該列表返回之後添加到條件模式基字典condPats中。

使用之前構建的樹來看一下實際的運行效果： 

>>> reload(fpGrowth)
<module \'fpGrowth\' from \'fpGrowth.py\'>
>>> fpGrowth.findPrefixPath(\'x\', myHeaderTab[\'x\'][1])
{frozenset([\'z\']): 3}
>>> fpGrowth.findPrefixPath(\'z\', myHeaderTab[\'z\'][1])
{}
>>> fpGrowth.findPrefixPath(\'r\', myHeaderTab[\'r\'][1])
{frozenset([\'x\', \'s\']): 1, frozenset([\'z\']): 1,frozenset([\'y\', \'x\', \'z\']): 1}

讀者可以檢查一下這些值與表12-3中的結果是否一致。有了條件模式基之後，就可以創建條件FP樹。

12.3.2　創建條件FP樹

對於每一個頻繁項，都要創建一棵條件FP樹。我們會為z、x以及其他頻繁項構建條件樹。可以使用剛才發現的條件模式基作為輸入數據，並通過相同的建樹代碼來構建這些樹。然後，我們會遞歸地發現頻繁項、發現條件模式基，以及發現另外的條件樹。舉個例子來說，假定為頻繁項t創建一個條件FP樹，然後對{t,y}、{t,x}重複該過程，…。元素項t的條件FP樹的構建過程如圖12-4所示。

圖12-4　t的條件FP樹的創建過程。最初樹以空集作為根節點。接下來，原始的集合{y,x,s,z}中的集合{y,x,z}被添加進來。因為不滿足最小支持度要求，字符s並沒有加入進來。類似地，{y,x,z}也從原始集合{y,x,r,z}中添加進來

在圖12-4中，注意到元素項s以及r是條件模式基的一部分，但是它們並不屬於條件FP樹。原因是什麼？如果討論s以及r的話，它們難道不是頻繁項嗎？實際上單獨來看它們都是頻繁項，但是在t的條件樹中，它們卻不是頻繁的，也就是說，{t,r}及{t,s}是不頻繁的。

接下來，對集合{t,z}、{t,x}以及{t,y}來挖掘對應的條件樹。這會產生更複雜的頻繁項集。該過程重複進行，直到條件樹中沒有元素為止，然後就可以停止了。實現代碼相對比較直觀，使用一些遞歸加上之前寫的代碼就可以完成。打開fpGrowth.py，將下面程序中的代碼添加進去。

程序清單12-5　遞歸查找頻繁項集的mineTree函數 

def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
    #❶ 從頭指針表的底端開始
    bigL = [v[0] for v in sorted(headerTable.items,key=lambda p: p[1])]
    for basePat in bigL:
        newFreqSet = preFix.copy
        newFreqSet.add(basePat)
        freqItemList.append(newFreqSet)
        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
        #❷ 從條件模式基來構建條件FP樹
        myCondTree, myHead = createTree(condPattBases,minSup)
        #❸ 挖掘條件FP樹
        if myHead != None:
            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)

創建條件樹、前綴路徑以及條件基的過程聽起來比較複雜，但是代碼起來相對簡單。程序首先對頭指針表中的元素項按照其出現頻率進行排序。（記住這裡的默認順序是按照從小到大。）❶然後，將每一個頻繁項添加到頻繁項集列表freqItemList中。接下來，遞歸調用程序清單12-4中的findPrefixPath函數來創建條件基。該條件基被當成一個新數據集輸送給createTree函數。❷這裡為函數createTree添加了足夠的靈活性，以確保它可以被重用於構建條件樹。最後，如果樹中有元素項的話，遞歸調用mineTree函數 ❸。

下面將整個程序合併到一塊看看代碼的實際運行效果。將程序清單12-5中的代碼添加到文件fpGrowth.py中並保存，然後在Python提示符下輸入： 

>>> reload(fpGrowth)
<module \'fpGrowth\' from \'fpGrowth.py\'>

下面建立一個空列表來存儲所有的頻繁項集： 

>>> freqItems =

接下來運行mineTree，顯示出所有的條件樹： 

>>> fpGrowth.mineTree(myFPtree, myHeaderTab, 3, set(), freqItems)
conditional tree for: set([\'y\'])
    Null Set   1
      x   3
        z   3
conditional tree for: set([\'y\', \'z\'])
    Null Set   1
      x   3
conditional tree for: set([\'s\'])
    Null Set   1
      x   3
conditional tree for: set([\'t\'])
    Null Set   1
      y    3
        x   3
          z   3
conditional tree for: set([\'x\', \'t\'])
    Null Set   1
      y   3
conditional tree for: set([\'z\', \'t\'])
    Null Set   1
      y   3
        x   3
conditional tree for: set([\'x\', \'z\', \'t\'])
    Null Set   1
      y   3
conditional tree for: set([\'x\'])
    Null Set   1
      z   3

為了獲得類似於前面代碼的輸出結果，我在函數mineTree中添加了兩行： 

print \'conditional tree for: \',newFreqSet
myCondTree.disp(1)

這兩行被添加到程序中語句if myHead != None:和mineTree函數調用之間。

下面檢查一下返回的項集是否與條件樹匹配： 

>>> freqItems
[set([\'y\']), set([\'y\', \'z\']), set([\'y\', \'x\', \'z\']), set([\'y\', \'x\']),set([\'s\']), set([\'x\', \'s\']), set([\'t\']), set([\'y\', \'t\']), set([\'x\',\'t\']), set([\'y\', \'x\', \'t\']), set([\'z\', \'t\']), set([\'y\', \'z\', \'t\']),set([\'x\', \'z\', \'t\']), set([\'y\', \'x\', \'z\', \'t\']), set([\'r\']), set([\'x\']),set([\'x\', \'z\']), set([\'z\'])]

正如我們所期望的那樣，返回項集與條件FP樹相匹配。到現在為主，完整的FP-growth算法已經可以運行，接下來在一個真實的例子上看一下運行效果。我們將看到是否能從微博網站Twitter中獲得一些常用詞。

    機器學習實戰