上一章介紹了發(fā)現(xiàn)頻繁項(xiàng)集與關(guān)鍵規(guī)則的算法绢记，本章將繼續(xù)關(guān)注發(fā)現(xiàn)頻繁項(xiàng)集這一任務(wù)柳洋。我們會深入探索該任務(wù)的解決方法叔汁，并應(yīng)用FP-growth算法進(jìn)行處理傻挂。這種算法雖然能更為高效地發(fā)現(xiàn)頻繁項(xiàng)集乘碑，但不能用于發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。

FP-growth算法
優(yōu)點(diǎn)：一般要快于Apriori
缺點(diǎn)：實(shí)現(xiàn)比較困難金拒，在某些數(shù)據(jù)集上性能會下降
適用數(shù)據(jù)類型：標(biāo)稱型數(shù)據(jù)

FP-growth算法講數(shù)據(jù)存儲在一種稱為FP樹的緊湊數(shù)據(jù)結(jié)構(gòu)中兽肤。FP代表頻繁模式，F(xiàn)requent pattern绪抛。同搜索樹不同的是资铡，一個(gè)元素項(xiàng)可以在一棵FP樹中出現(xiàn)多次。FP樹會存儲項(xiàng)集的出現(xiàn)頻率幢码，而每個(gè)項(xiàng)集會以路徑的方式存儲在樹中笤休。
相似點(diǎn)之間的鏈接即節(jié)點(diǎn)鏈接（node link），用于快速發(fā)現(xiàn)相似的位置症副。
本章的FP樹比書中的其他樹更加復(fù)雜店雅，因此要?jiǎng)?chuàng)建一個(gè)類來保存樹的每一個(gè)節(jié)點(diǎn)：

#FP樹
class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue
        self.count = numOccur#計(jì)數(shù)器
        self.nodeLink = None#用于鏈接相似的元素項(xiàng)
        self.parent = parentNode#指向父節(jié)點(diǎn)，需要被更新
        self.children = {} #存放子節(jié)點(diǎn)
    
    def inc(self, numOccur):
        self.count += numOccur
        
    def disp(self, ind=1):
        print '  '*ind, self.name, ' ', self.count
        for child in self.children.values():
            child.disp(ind+1)

先創(chuàng)建樹中的一個(gè)單節(jié)點(diǎn)：

In [45]: import fpGrowth
    ...: rootNode = fpGrowth.treeNode('pyramid',9,None)

接下來增加一個(gè)子節(jié)點(diǎn)：

In [46]: rootNode.children['eye'] = fpGrowth.treeNode('eye',13,None)

顯示子節(jié)點(diǎn)：

In [47]: rootNode.disp()
   pyramid   9
     eye   13

再增加一個(gè)節(jié)點(diǎn)看看子節(jié)點(diǎn)的展示效果：

In [48]: rootNode.children['phoenix']=fpGrowth.treeNode('phoenix',3,None)
    ...: rootNode.disp()
    ...: 
   pyramid   9
     eye   13
     phoenix   3

除了剛剛給出的FP樹以外瓦糕，還需要一個(gè)頭指針表來指向給定類型的第一個(gè)實(shí)例底洗。這里使用一個(gè)字典作為數(shù)據(jù)結(jié)構(gòu)，來保存頭指針表咕娄。除了存放指針外亥揖，頭指針表還可以用來存放FP樹中每類元素的總數(shù)。
接下來，我們通過代碼來實(shí)現(xiàn)上述過程：

def createTree(dataSet, minSup=1): #數(shù)據(jù)集费变，最小支持度
    headerTable = {}
    #遍歷數(shù)據(jù)集兩次
    for trans in dataSet:#統(tǒng)計(jì)
        for item in trans:
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
    for k in headerTable.keys():  #移除不滿足最小支持度的元素項(xiàng)
        if headerTable[k] < minSup: 
            del(headerTable[k])
    freqItemSet = set(headerTable.keys())
    #print 'freqItemSet: ',freqItemSet
    if len(freqItemSet) == 0: return None, None  #都不滿足摧扇，則退出
    for k in headerTable:
        headerTable[k] = [headerTable[k], None] #修改為下一步準(zhǔn)備
    #print 'headerTable: ',headerTable
    retTree = treeNode('Null Set', 1, None) #根節(jié)點(diǎn)
    for tranSet, count in dataSet.items():  #第二次遍歷
        localD = {}
        for item in tranSet:  #排序
            if item in freqItemSet:
                localD[item] = headerTable[item][0]
        if len(localD) > 0:
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]
            updateTree(orderedItems, retTree, headerTable, count)#用排序后的頻率項(xiàng)進(jìn)行填充
    return retTree, headerTable 

def updateTree(items, inTree, headerTable, count):
    if items[0] in inTree.children:#檢查第一個(gè)元素是否作為子節(jié)點(diǎn)存在
        inTree.children[items[0]].inc(count) #更新計(jì)數(shù)
    else:   #新建一個(gè)子節(jié)點(diǎn)添加到樹中
        inTree.children[items[0]] = treeNode(items[0], count, inTree)
        if headerTable[items[0]][1] == None: 
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
    if len(items) > 1:#對剩下的元素項(xiàng)迭代調(diào)用，每一次奧調(diào)用去掉第一個(gè)元素
        updateTree(items[1::], inTree.children[items[0]], headerTable, count)
        
def updateHeader(nodeToTest, targetNode):   #確保節(jié)點(diǎn)鏈接指向樹中該元素項(xiàng)的每一個(gè)實(shí)例
    while (nodeToTest.nodeLink != None):    #直達(dá)鏈尾
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode

下面將數(shù)據(jù)集和數(shù)據(jù)包裝器加入代碼中：

def loadSimpDat():
    simpDat = [['r', 'z', 'h', 'j', 'p'],
               ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
               ['z'],
               ['r', 'x', 'n', 'o', 's'],
               ['y', 'r', 'x', 'z', 'q', 't', 'p'],
               ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
    return simpDat

def createInitSet(dataSet):
    retDict = {}
    for trans in dataSet:
        retDict[frozenset(trans)] = 1
    return retDict

首先挚歧，導(dǎo)入數(shù)據(jù)庫實(shí)例：

In [2]: import fpGrowth
   ...: simpDat = fpGrowth.loadSimpDat()
   ...: 

In [3]: simpDat
Out[3]: 
[['r', 'z', 'h', 'j', 'p'],
 ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
 ['z'],
 ['r', 'x', 'n', 'o', 's'],
 ['y', 'r', 'x', 'z', 'q', 't', 'p'],
 ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]

接下來為了函數(shù)createTree()扛稽，需要對上面的數(shù)據(jù)進(jìn)行格式化處理：

In [4]: initSet = fpGrowth.createInitSet(simpDat)
   ...: initSet
   ...: 
Out[4]: 
{frozenset({'e', 'm', 'q', 's', 't', 'x', 'y', 'z'}): 1,
 frozenset({'n', 'o', 'r', 's', 'x'}): 1,
 frozenset({'z'}): 1,
 frozenset({'s', 't', 'u', 'v', 'w', 'x', 'y', 'z'}): 1,
 frozenset({'p', 'q', 'r', 't', 'x', 'y', 'z'}): 1,
 frozenset({'h', 'j', 'p', 'r', 'z'}): 1}

于是可以通過如下 命令創(chuàng)建FP樹：

In [10]: myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 3)
    ...: myFPtree.disp()
    ...: 
   Null Set   1
     x   1
       s   1
         r   1
     z   5
       x   3
         y   3
           s   2
             t   2
           r   1
             t   1
       r   1

上面給出的是元素項(xiàng)及其對應(yīng)的頻率計(jì)數(shù)值，其中每個(gè)縮進(jìn)表示所處的樹的深度滑负。
現(xiàn)在我們已經(jīng)構(gòu)建了FP樹在张，接下來就使用它進(jìn)行數(shù)據(jù)挖掘。
從FP樹中抽取頻繁項(xiàng)集的三個(gè)基本步驟如下：
（1）從FP樹中獲取條件模式基矮慕；
（2）利用條件模式基帮匾，構(gòu)建一個(gè)條件FP樹；
（3）迭代重復(fù)步驟（1）和步驟（2）痴鳄，直到樹包含一個(gè)元素項(xiàng)為止瘟斜。

首先從上一節(jié)發(fā)現(xiàn)的已經(jīng)保存在頭指針表中的單個(gè)頻繁元素項(xiàng)開始。對于每一個(gè)元素項(xiàng)痪寻，獲得其對于的條件模式基（conditional pattern base）螺句。條件模式基是以所查找元素項(xiàng)為結(jié)尾的路徑集合。每一條路徑其實(shí)都是一條前綴路徑（prefixpath）橡类。簡而言之蛇尚，一條前綴路徑是介于所查找元素項(xiàng)與樹根節(jié)點(diǎn)之間的所有內(nèi)容。
下面的程序清單給出了前綴路徑發(fā)現(xiàn)的代碼：

def ascendTree(leafNode, prefixPath): #迭代回溯整棵樹
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)
   
#遍歷鏈表直到到達(dá)結(jié)尾顾画，每遇到一個(gè)元素項(xiàng)都會調(diào)用ascendTree()函數(shù)來上溯FP樹佣蓉，ing收集所有遇到的元素項(xiàng)的名稱    
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

使用之前構(gòu)建的樹來看一下實(shí)際的運(yùn)行效果：

In [4]: import fpGrowth
   ...: fpGrowth.findPrefixPath('x',myHeaderTab['x'][1])
   ...: 
Out[4]: {frozenset({'z'}): 3}

In [5]: fpGrowth.findPrefixPath('z',myHeaderTab['z'][1])
Out[5]: {}

In [6]: fpGrowth.findPrefixPath('r',myHeaderTab['r'][1])
Out[6]: {frozenset({'s', 'x'}): 1, frozenset({'z'}): 1, frozenset({'x', 'y', 'z'}): 1}

下面繼續(xù)補(bǔ)充完整程序：

def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
    bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])]#對頭指針表的元素項(xiàng)按照其出現(xiàn)的頻率進(jìn)行排序
    for basePat in bigL:  #從頭指針的底端開始
        newFreqSet = preFix.copy()
        newFreqSet.add(basePat)
        freqItemList.append(newFreqSet)
        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
        myCondTree, myHead = createTree(condPattBases, minSup)
        if myHead != None: #遞歸調(diào)用
            print 'conditional tree for: ',newFreqSet
            myCondTree.disp(1)      
            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)

接下來運(yùn)行mineTree()，顯示出所有的條件樹：

In [14]: import fpGrowth
    ...: freqItems = []
    ...: 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(['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', 't'])
   Null Set   1
     y   3
conditional tree for:  set(['x'])
   Null Set   1
     z   3

下面檢查一下返回的項(xiàng)集是否與條件樹匹配：

In [15]: freqItems
Out[15]: 
[{'y'},
 {'y', 'z'},
 {'x', 'y', 'z'},
 {'x', 'y'},
 {'s'},
 {'s', 'x'},
 {'t'},
 {'t', 'z'},
 {'t', 'y', 'z'},
 {'t', 'x', 'z'},
 {'t', 'x', 'y', 'z'},
 {'t', 'x'},
 {'t', 'x', 'y'},
 {'t', 'y'},
 {'r'},
 {'x'},
 {'x', 'z'},
 {'z'}]