在第二次掃瞄數據集時會構建一棵FP樹。為構建一棵樹，需要一個容器來保存樹。
12.2.1 創建FP樹的數據結構
本章的FP樹要比書中其他樹更加複雜，因此要創建一個類來保存樹的每一個節點。創建文件fpGrowth.py並加入下列程序中的代碼。
程序清單12-1 FP樹的類定義
class treeNode:
def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue
self.count = numOccur
self.nodeLink = None
self.parent = parentNode
self.children = {}
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)
上面的程序給出了FP樹中節點的類定義。類中包含用於存放節點名字的變量和1個計數值，nodeLink變量用於鏈接相似的元素項（參考圖12-1中的虛線）。類中還使用了父變量parent來指向當前節點的父節點。通常情況下並不需要這個變量，因為通常是從上往下迭代訪問節點的。本章後面的內容中需要根據給定葉子節點上溯整棵樹，這時就需要指向父節點的指針。最後，類中還包含一個空字典變量，用於存放節點的子節點。
程序清單12-1中包括兩個方法，其中inc對count變量增加給定值，而另一個方法disp用於將樹以文本形式顯示。後者對於樹構建來說並不是必要的，但是它對於調試非常有用。
運行一下如下代碼：
>>> import fpGrowth
>>> rootNode = fpGrowth.treeNode(\'pyramid\',9, None)
這會創建樹中的一個單節點。接下來為其增加一個子節點：
>>> rootNode.children[\'eye\']=fpGrowth.treeNode(\'eye\', 13, None)
為顯示子節點，輸入：
>>> rootNode.disp
pyramid 9
eye 13
再添加一個節點看看兩個子節點的展示效果：
>>> rootNode.children[\'phoenix\']=fpGrowth.treeNode(\'phoenix\', 3, None)
>>> rootNode.disp
pyramid 9
eye 13
phoenix 3
現在FP樹所需數據結構已經建好，下面就可以構建FP樹了。
12.2.2 構建FP樹
除了圖12-1給出的FP樹之外，還需要一個頭指針表來指向給定類型的第一個實例。利用頭指針表，可以快速訪問FP樹中一個給定類型的所有元素。圖12-2給出了一個頭指針表的示意圖。
圖12-2 帶頭指針表的FP樹，頭指針表作為一個起始指針來發現相似元素項
這裡使用一個字典作為數據結構，來保存頭指針表。除了存放指針外，頭指針表還可以用來保存FP樹中每類元素的總數。
第一次遍歷數據集會獲得每個元素項的出現頻率。接下來，去掉不滿足最小支持度的元素項。再下一步構建FP樹。在構建時，讀入每個項集並將其添加到一條已經存在的路徑中。如果該路徑不存在，則創建一條新路徑。每個事務就是一個無序集合。假設有集合{z,x,y}和{y,z,r}，那麼在FP樹中，相同項會只表示一次。為了解決此問題，在將集合添加到樹之前，需要對每個集合進行排序。排序基於元素項的絕對出現頻率來進行。使用圖12-2中的頭指針節點值，對表12-1中數據進行過濾、重排序後的數據顯示在表12-2中。
表12-2 將非頻繁項移除並且重排序後的事務數據集
事務ID 事務中的元素項 過濾及重排序後的事務001
r, z, h, j, p
z, r
002
z, y, x, w, v, u, t, s
z, x, y, s, t
003
z
z
004
r, x, n, o, s
x, s, r
005
y, r, x, z, q, t, p
z, x, y, r, t
006
y, z, x, e, q, s, t, m
z, x, y, s, t
在對事務記錄過濾和排序之後，就可以構建FP樹了。從空集（符號為O）開始，向其中不斷添加頻繁項集。過濾、排序後的事務依次添加到樹中，如果樹中已存在現有元素，則增加現有元素的值；如果現有元素不存在，則向樹添加一個分枝。對表12-2前兩條事務進行添加的過程顯示在圖12-3中。
圖12-3 FP樹構建過程的一個示意圖，圖中給出了使用表12-2中數據構建FP樹的前兩步。
通過上面的敘述，我們大致瞭解了從事務數據集轉換為FP樹的基本思想，接下來我們通過代碼來實現上述過程。打開fpGrowth.py文件，加入下面的代碼。
程序清單12-2 FP樹構建函數
def createTree(dataSet, minSup=1):
headerTable = {}
for trans in dataSet
for item in trans:
headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
#❶（以下三行）移除不滿足最小支持度的元素項
for k in headerTable.keys:
if headerTable[k] < minSup:
del(headerTable[k])
freqItemSet = set(headerTable.keys)
#❷ 如果沒有元素項滿足要求，則退出
if len(freqItemSet) == 0: return None, None
for k in headerTable:
headerTable[k] = [headerTable[k], None]
retTree = treeNode(\'Null Set\', 1, None)
for tranSet, count in dataSet.items:
localD = {}
#❸（以下三行）根據全局頻率對每個事務中的元素進行排序
for item in tranSet:
if item in freqItemSet:
localD[item] = headerTable[item][
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)
return retTree, headerTable
def updateTree(items, inTree, headerTable, count):
if items[0] in inTree.children:
inTree.children[items[0]].inc(count)
else:
inTree.children[items[0]] = treeNode(
if headerTable[items[0]][1] == None:
headerTable[items[0]][1] = inTree.
else:
updateHeader(headerTable[items[0]][1],inTree.children[items[0]])
if len(items) > 1:
#❺ 對剩下的元素項迭代調用updateTree函數
updateTree(items[1::], inTree.children[items[0]],headerTable, count)
def updateHeader(nodeToTest, targetNode):
while (nodeToTest.nodeLink != None):
nodeToTest = nodeToTest.nodeLink
nodeToTest.nodeLink = targetNode
上述代碼中包含3個函數。第一個函數createTree使用數據集以及最小支持度作為參數來構建FP樹。樹構建過程中會遍歷數據集兩次。第一次遍歷掃瞄數據集並統計每個元素項出現的頻度。這些信息被存儲在頭指針表中。接下來，掃瞄頭指針表刪掉那些出現次數少於minSup的項❶。如果所有項都不頻繁，就不需要進行下一步處理❷。接下來，對頭指針表稍加擴展以便可以保存計數值及指向每種類型第一個元素項的指針。然後創建只包含空集合O的根節點。最後，再一次遍歷數據集，這次只考慮那些頻繁項❸。這些項已經如表12-2所示那樣進行了排序，然後調用updateTree方法❹。接下來討論函數updateTree。
為了讓FP樹生長1，需調用updateTree，其中的輸入參數為一個項集。圖12-3給出了updateTree中的執行細節。該函數首先測試事務中的第一個元素項是否作為子節點存在。如果存在的話，則更新該元素項的計數；如果不存在，則創建一個新的treeNode並將其作為一個子節點添加到樹中。這時，頭指針表也要更新以指向新的節點。更新頭指針表需要調用函數updateHeader，接下來會討論該函數的細節。updateTree完成的最後一件事是不斷迭代調用自身，每次調用時會去掉列表中第一個元素❺。
1. 這就是FP-growth中的growth（生長）一詞的來源。
程序清單12-2中的最後一個函數是updateHeader，它確保節點鏈接指向樹中該元素項的每一個實例。從頭指針表的nodeLink開始，一直沿著nodeLink直到到達鏈表末尾。這就是一個鏈表。當處理樹的時候，一種很自然的反應就是迭代完成每一件事。當以相同方式處理鏈表時可能會遇到一些問題，原因是如果鏈表很長可能會遇到迭代調用的次數限制。
在運行上例之前，還需要一個真正的數據集。這可以從本書附帶的代碼庫中獲得，或者直接手工輸入。loadSimpDat函數會返回一個事務列表。這和表12-1中的事務相同。後面構建樹時會使用createTree函數，而該函數的輸入數據類型不是列表。其需要的是一部字典，其中項集為字典中的鍵，而頻率為每個鍵對應的取值。createInitSet用於實現上述從列表到字典的類型轉換過程。將下列代碼添加到fpGrowth.py文件中。
程序清單12-3 簡單數據集及數據包裝器
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
好了，下面看看實際的效果。將程序清單12-3中的代碼加入文件fpGrowth.py之後，在Python提示符下輸入命令：
>>> reload(fpGrowth)
<module \'fpGrowth\' from \'fpGrowth.py\'>
首先，導入數據庫實例：
>>> simpDat = fpGrowth.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\']]
接下來為了函數createTree，需要對上面的數據進行格式化處理：
>>> initSet = fpGrowth.createInitSet(simpDat)
>>> initSet
{frozenset([\'e\', \'m\', \'q\', \'s\', \'t\', \'y\', \'x\', \'z\']): 1, frozenset([\'x\',\'s\', \'r\', \'o\', \'n\']): 1, frozenset([\'s\', \'u\', \'t\', \'w\', \'v\', \'y\', \'x\',\'z\']): 1, frozenset([\'q\', \'p\', \'r\', \'t\', \'y\', \'x\', \'z\']): 1,frozenset([\'h\', \'r\', \'z\', \'p\', \'j\']): 1, frozenset([\'z\']): 1}
於是可以通過如下命令創建FP樹：
>>> myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 3)
使用disp方法給出樹的文本表示結果：
>>> 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
上面給出的是元素項及其對應的頻率計數值，其中每個縮進表示所處的樹的深度。讀者可以驗證一下這棵樹與圖12-2中所示的樹是否等價。
現在我們已經構建了FP樹，接下來就使用它進行頻繁項集挖掘。