目錄
- 抽取條件模式基
- 創(chuàng)建條件FP樹(shù)
- 總結(jié)
上篇介紹了如何構(gòu)建FP樹(shù)，F(xiàn)P樹(shù)的每條路徑都滿足最小支持度，我們需要做的是在一條路徑上尋找到更多的關(guān)聯(lián)關(guān)系。
抽取條件模式基
首先從FP樹(shù)頭指針表中的單個(gè)頻繁元素項(xiàng)開(kāi)始。對(duì)于每一個(gè)元素項(xiàng)，獲得其對(duì)應(yīng)的條件模式基（conditional pattern base)，單個(gè)元素項(xiàng)的條件模式基也就是元素項(xiàng)的關(guān)鍵字。條件模式基是以所查找元素項(xiàng)為結(jié)尾的路徑集合。每一條路徑其實(shí)都是一條前輟路徑（perfix path）。簡(jiǎn)而言之，一條前綴路徑是介于所査找元素項(xiàng)與樹(shù)根節(jié)點(diǎn)之間的所有內(nèi)容。
下圖是以{s:2}或{r:1}為元素項(xiàng)的前綴路徑：
{s}的條件模式基，即前綴路徑集合共有兩個(gè)：{{z,x,y,t}, {x}}；{r}的條件模式基共三個(gè)：{{z}, {z,x,y,t}, {x,s}}。
尋找條件模式基的過(guò)程實(shí)際上是從FP樹(shù)的每個(gè)葉子節(jié)點(diǎn)回溯到根節(jié)點(diǎn)的過(guò)程。我們可以通過(guò)頭指針列表headTable開(kāi)始，通過(guò)指針的連接快速訪問(wèn)到所有根節(jié)點(diǎn)。下表是上圖FP樹(shù)的所有條件模式基：
創(chuàng)建條件FP樹(shù)
為了發(fā)現(xiàn)更多的頻繁項(xiàng)集，對(duì)于每一個(gè)頻繁項(xiàng)，都要?jiǎng)?chuàng)建一棵條件FP樹(shù)。可以使用剛才發(fā)現(xiàn)的條件模式基作為輸入數(shù)據(jù)，并通過(guò)相同的建樹(shù)代碼來(lái)構(gòu)建這些樹(shù)。然后，遞歸地發(fā)現(xiàn)頻繁項(xiàng)、發(fā)現(xiàn)條件模式基，以及發(fā)現(xiàn)另外的條件樹(shù)。
以頻繁項(xiàng)r為例，構(gòu)建關(guān)于r的條件FP樹(shù)。r的三個(gè)前綴路徑分別是{z},{z,x,y,t},{x,s}，設(shè)最小支持度minSupport=2，則y,t,s被過(guò)濾掉，剩下{z},{z,x},{x}。y,s,t雖然是條件模式基的一部分，但是并不屬于條件FP樹(shù)，即對(duì)于r來(lái)說(shuō)，它們不是頻繁的。如下圖所示，y→t→r和s→r的全局支持度都為1，所以y,t,s對(duì)于r的條件樹(shù)來(lái)說(shuō)是不頻繁的。
過(guò)濾后的r條件樹(shù)如下：
重復(fù)上面步驟，r的條件模式基是{z,x},{x}，已經(jīng)沒(méi)有能夠滿足最小支持度的路徑， 所以r的條件樹(shù)僅有一個(gè)。需要注意的是，雖然{z,x},{x}中共存在兩個(gè)x，但{z,x}中，z是x的父節(jié)點(diǎn)，在構(gòu)造條件FP樹(shù)時(shí)不能直接將父節(jié)點(diǎn)移除，僅能從子節(jié)點(diǎn)開(kāi)始逐級(jí)移除。
代碼如下：
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)
# 通過(guò)條件模式基找到的頻繁項(xiàng)集
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)
控制臺(tái)信息：
總結(jié)
本篇文章就到這了，本例可以發(fā)現(xiàn)兩個(gè)頻繁項(xiàng)集{z,x}和{x}。取得頻繁項(xiàng)集后，可以根據(jù)置信度發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，這一步較為簡(jiǎn)單，可參考上篇的相關(guān)內(nèi)容，不在贅述。希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的其他精彩內(nèi)容！
您可能感興趣的文章:- FP-growth算法發(fā)現(xiàn)頻繁項(xiàng)集——構(gòu)建FP樹(shù)
- FP-Growth算法的Java實(shí)現(xiàn)+具體實(shí)現(xiàn)思路+代碼
- 詳解Java如何實(shí)現(xiàn)FP-Growth算法
- Java編程實(shí)現(xiàn)A*算法完整代碼
- python+pyqt5實(shí)現(xiàn)24點(diǎn)小游戲
