2023年第十三屆MathorCup高校數(shù)學(xué)建模挑戰(zhàn)賽

資料思路分享Q群：714452621

算法介紹

FP-Tree算法全稱是FrequentPattern Tree算法，就是頻繁模式樹算法，他與Apriori算法一樣也是用來挖掘頻繁項(xiàng)集的，不過不同的是，F(xiàn)P-Tree算法是Apriori算法的優(yōu)化處理，他解決了Apriori算法在過程中會產(chǎn)生大量的候選集的問題，而FP-Tree算法則是發(fā)現(xiàn)頻繁模式而不產(chǎn)生候選集。但是頻繁模式挖掘出來后，產(chǎn)生關(guān)聯(lián)規(guī)則的步驟還是和Apriori是一樣的。

常見的挖掘頻繁項(xiàng)集算法有兩類，一類是Apriori算法，另一類是FP-growth。Apriori通過不斷的構(gòu)造候選集、篩選候選集挖掘出頻繁項(xiàng)集，需要多次掃描原始數(shù)據(jù)，當(dāng)原始數(shù)據(jù)較大時，磁盤I/O次數(shù)太多，效率比較低下。FPGrowth不同于Apriori的“試探”策略，算法只需掃描原始數(shù)據(jù)兩遍，通過FP-tree數(shù)據(jù)結(jié)構(gòu)對原始數(shù)據(jù)進(jìn)行壓縮，效率較高。

FP代表頻繁模式（Frequent Pattern) ，算法主要分為兩個步驟：FP-tree構(gòu)建、挖掘頻繁項(xiàng)集。

FP樹表示法

　　FP樹通過逐個讀入事務(wù)，并把事務(wù)映射到FP樹中的一條路徑來構(gòu)造。由于不同的事務(wù)可能會有若干個相同的項(xiàng)，因此它們的路徑可能部分重疊。路徑相互重疊越多，使用FP樹結(jié)構(gòu)獲得的壓縮效果越好；如果FP樹足夠小，能夠存放在內(nèi)存中，就可以直接從這個內(nèi)存中的結(jié)構(gòu)提取頻繁項(xiàng)集，而不必重復(fù)地掃描存放在硬盤上的數(shù)據(jù)。

　　一顆FP樹如下圖所示： 　　

通常，F(xiàn)P樹的大小比未壓縮的數(shù)據(jù)小，因?yàn)閿?shù)據(jù)的事務(wù)常常共享一些共同項(xiàng)，在最好的情況下，所有的事務(wù)都具有相同的項(xiàng)集，F(xiàn)P樹只包含一條節(jié)點(diǎn)路徑；當(dāng)每個事務(wù)都具有唯一項(xiàng)集時，導(dǎo)致最壞情況發(fā)生，由于事務(wù)不包含任何共同項(xiàng)，F(xiàn)P樹的大小實(shí)際上與原數(shù)據(jù)的大小一樣。

　　FP樹的根節(jié)點(diǎn)用φ表示，其余節(jié)點(diǎn)包括一個數(shù)據(jù)項(xiàng)和該數(shù)據(jù)項(xiàng)在本路徑上的支持度；每條路徑都是一條訓(xùn)練數(shù)據(jù)中滿足最小支持度的數(shù)據(jù)項(xiàng)集；FP樹還將所有相同項(xiàng)連接成鏈表，上圖中用藍(lán)色連線表示。

　　為了快速訪問樹中的相同項(xiàng)，還需要維護(hù)一個連接具有相同項(xiàng)的節(jié)點(diǎn)的指針列表（headTable），每個列表元素包括：數(shù)據(jù)項(xiàng)、該項(xiàng)的全局最小支持度、指向FP樹中該項(xiàng)鏈表的表頭的指針。 　　

構(gòu)建FP樹

　　現(xiàn)在有如下數(shù)據(jù)：

FP-growth算法需要對原始訓(xùn)練集掃描兩遍以構(gòu)建FP樹。

　　第一次掃描，過濾掉所有不滿足最小支持度的項(xiàng)；對于滿足最小支持度的項(xiàng)，按照全局最小支持度排序，在此基礎(chǔ)上，為了處理方便，也可以按照項(xiàng)的關(guān)鍵字再次排序。

第二次掃描，構(gòu)造FP樹。

　　參與掃描的是過濾后的數(shù)據(jù)，如果某個數(shù)據(jù)項(xiàng)是第一次遇到，則創(chuàng)建該節(jié)點(diǎn)，并在headTable中添加一個指向該節(jié)點(diǎn)的指針；否則按路徑找到該項(xiàng)對應(yīng)的節(jié)點(diǎn)，修改節(jié)點(diǎn)信息。具體過程如下所示：

　從上面可以看出，headTable并不是隨著FPTree一起創(chuàng)建，而是在第一次掃描時就已經(jīng)創(chuàng)建完畢，在創(chuàng)建FPTree時只需要將指針指向相應(yīng)節(jié)點(diǎn)即可。從事務(wù)004開始，需要創(chuàng)建節(jié)點(diǎn)間的連接，使不同路徑上的相同項(xiàng)連接成鏈表。

實(shí)現(xiàn)代碼

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:
? ? ? ?fset = frozenset(trans)
? ? ? ?retDict.setdefault(fset, 0)
? ? ? ?retDict[fset] += 1
? ?return retDict

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)


def createTree(dataSet, minSup=1):
? ?headerTable = {}
? ?#此一次遍歷數(shù)據(jù)集， 記錄每個數(shù)據(jù)項(xiàng)的支持度
? ?for trans in dataSet:
? ? ? ?for item in trans:
? ? ? ? ? ?headerTable[item] = headerTable.get(item, 0) + 1

? ?#根據(jù)最小支持度過濾
? ?lessThanMinsup = list(filter(lambda k:headerTable[k] < minSup, headerTable.keys()))
? ?for k in lessThanMinsup: del(headerTable[k])

? ?freqItemSet = set(headerTable.keys())
? ?#如果所有數(shù)據(jù)都不滿足最小支持度，返回None, None
? ?if len(freqItemSet) == 0:
? ? ? ?return None, None

? ?for k in headerTable:
? ? ? ?headerTable[k] = [headerTable[k], None]

? ?retTree = treeNode('φ', 1, None)
? ?#第二次遍歷數(shù)據(jù)集，構(gòu)建fp-tree
? ?for tranSet, count in dataSet.items():
? ? ? ?#根據(jù)最小支持度處理一條訓(xùn)練樣本，key:樣本中的一個樣例，value:該樣例的的全局支持度
? ? ? ?localD = {}
? ? ? ?for item in tranSet:
? ? ? ? ? ?if item in freqItemSet:
? ? ? ? ? ? ? ?localD[item] = headerTable[item][0]

? ? ? ?if len(localD) > 0:
? ? ? ? ? ?#根據(jù)全局頻繁項(xiàng)對每個事務(wù)中的數(shù)據(jù)進(jìn)行排序,等價(jià)于 order by p[1] desc, p[0] desc
? ? ? ? ? ?orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: (p[1],p[0]), reverse=True)]
? ? ? ? ? ?updateTree(orderedItems, retTree, headerTable, count)
? ?return retTree, headerTable


def updateTree(items, inTree, headerTable, count):
? ?if items[0] in inTree.children: ?# check if orderedItems[0] in retTree.children
? ? ? ?inTree.children[items[0]].inc(count) ?# incrament count
? ?else: ?# add items[0] to inTree.children
? ? ? ?inTree.children[items[0]] = treeNode(items[0], count, inTree)
? ? ? ?if headerTable[items[0]][1] == None: ?# update header table
? ? ? ? ? ?headerTable[items[0]][1] = inTree.children[items[0]]
? ? ? ?else:
? ? ? ? ? ?updateHeader(headerTable[items[0]][1], inTree.children[items[0]])

? ?if len(items) > 1: ?# call updateTree() with remaining ordered items
? ? ? ?updateTree(items[1:], inTree.children[items[0]], headerTable, count)


def updateHeader(nodeToTest, targetNode): ?# this version does not use recursion
? ?while (nodeToTest.nodeLink != None): ?# Do not use recursion to traverse a linked list!
? ? ? ?nodeToTest = nodeToTest.nodeLink
? ?nodeToTest.nodeLink = targetNode

simpDat = loadSimpDat()
dictDat = createInitSet(simpDat)
myFPTree,myheader = createTree(dictDat, 3)
myFPTree.disp()

上面的代碼在第一次掃描后并沒有將每條訓(xùn)練數(shù)據(jù)過濾后的項(xiàng)排序，而是將排序放在了第二次掃描時，這可以簡化代碼的復(fù)雜度。

　　控制臺信息：

?

2023年第十三屆MathorCup高校數(shù)學(xué)建模挑戰(zhàn)賽

資料思路分享Q群：714452621