當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

机器学习实战-FP-growth算法

發布時間：2024/1/1 编程问答 30 豆豆

生活随笔收集整理的這篇文章主要介紹了机器学习实战-FP-growth算法小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

本章內容

發現事物數據中的公共模式
FP-growth算法
發現Twitter源中共現詞

搜索引擎自動補全查詢此項，可以找出互聯網上經常一塊出現的詞對。這需要一種高效發現頻繁項集的方法。FP-growth比上一章討論的Apriori算法要快，它基于Apriori構建，但在完成任務時采用不同的技術。這里的任務是將數據集存儲在一個特定的稱作FP樹的結構之后發現頻繁項集或者頻繁項對，即常在一塊出現的元素項的集合FP樹。與Apriori相比，此算法執行速度要快兩個數量級以上。但是，只能高效地發現頻繁項集，不能用于發現關聯規則。

FP-growth算法只需要對數據庫進行兩次掃描，而Apriori對于每個潛在的頻繁項集都會掃描數據集判定給定模式是否頻繁，因此FP-growth性能更好，它發現頻繁項集的基本過程如下：

構建FP樹

從FP樹種挖掘頻繁項集

一、FP樹：用于編碼數據集的有效方式

FP-growth算法將數據存儲在FP樹這種緊湊數據結構中。FP代表頻繁模式（Frequent Pattern）。一顆FP樹與計算機科學中其他樹結構類似，但它通過鏈接（link）來連接相似元素。

圖1　一顆FP樹，包含著連接相似點的鏈接

同搜索樹不同的是，一個元素項可以在一棵FP樹中出現多次。FP樹會存儲項集的出現頻率，而每個項集會以路徑的方式存儲在樹中。存在相似元素的集合會共享樹的一部分。只有當集合之間完全不同時，樹才會分叉。樹節點上給出集合中單個元素及其在序列中的出現次數，路徑會給出該序列的出現次數。

相似項之間的鏈接，即節點鏈接（node link），用于快速發現相似項的位置。上圖FP樹可由下表中的數據生成。

表1　用于生成上圖中FP樹的事物數據樣例

事物ID事物中的元素項

001	r,z,h,j,p
002	z,y,x,w,v,u,t,s
003	z
004	r,x,n,o,s
005	y,r,x,z,q,t,p
006	y,z,x,e,q,s,t,m

在上圖中，元素項z出現了5次，集合{r, z}出現了1次。集合{t, s, y, x, z}出現了2次，集合{t, r, y, x, z}出現了1次。元素項z的右邊是5，表示z出現了5次，剛才已經給出了四次出現，所以它一定單獨出現過1次。005號記錄是{y, r, x, z, q, t, p}，那么q、p去哪兒了呢？

這里使用第11章給出的支持度定義，該指標對應一個最小閾值，低于最小閾值的元素項被認為是不頻繁的。若將最小支持度設為3，然后應用頻繁項分析算法，就會獲得出現3次或3次以上的項集。圖中FP樹的最小支持度是3，因此p、q并沒有出現在樹中。

FP-growth算法的工作流程：首先構建FP樹，然后利用它來挖掘頻繁項集。為了構建FP樹，需要對原始數據集掃描兩遍。第一遍對所有元素項的出現次數進行計數。Apriori原理，即如果某元素是不頻繁的，那么包含該元素的超集也是不頻繁的，所以就不需要考慮超集。數據庫的第一遍掃描用來統計出現的頻率，第二遍掃描中只考慮哪些頻繁元素。

二、構建FP樹

使用一個容器來保存FP樹。

2-1 創建FP樹的數據結構

要創建一個類來保存樹的每個節點。創建fpGrowth.py，加入下列代碼。

# coding=utf-8class treeNode :def __init__(self, nameValue, numOccur, parentNode) :# 節點名稱self.name = nameValueself.count = numOccur# 用于鏈接相似的元素項self.nodeLink = None# 當前節點的父節點self.parent = parentNode# 用于存放節點的子節點self.children = {}# 對count變量增加給定值def inc(self, numOccur) :self.count += numOccur# 將樹以文本的形式顯示def disp(self, ind=1) :print ' '*ind, self.name, ' ', self.countfor child in self.children.values() :child.disp(ind+1)

運行程序結果：

>>> import ml.fpGrowth as fpGrowth >>> rootNode = fpGrowth.treeNode('pyramid',9,None) >>> rootNode.children['eye'] = fpGrowth.treeNode('eye',13,None) >>> rootNode.disp()pyramid 9eye 13 >>> rootNode.children['phoenix']=fpGrowth.treeNode('phoenix',3,None) >>> rootNode.disp()pyramid 9eye 13phoenix 3

2-2 構建FP樹

除圖1給出的FP樹之外，還需要一個頭指針表來指向給定類型的第一個實例。利用頭指針表，可快速訪問FP樹中一個給定類型的所有元素。下圖2給出了一個頭指針表的示意圖。

圖2　帶頭指針表的FP樹，頭指針表作為一個起始指針來發現相似元素項

這里使用一個字典來保存頭指針表。除了存放指針外，頭指針表還可以用來保存FP樹中每類元素的總數。

第一次遍歷數據集獲得每個元素項的出現頻率。接著，去掉不滿足最小支持度的元素項，再構建FP樹。在構建時，讀入每個項集并將其添加到一條已經存在的路徑中。如果該路徑不存在，則創建一條新路徑。每個事務就是一個無序集合。假設有集合{z, x, y}和{y, z, r}，那么在FP樹中，相同項會只表示一次。為了解決此問題，在將集合添加到樹之前，需要對每個集合進行排序。排序基于元素項的絕對出現頻率來進行。使用圖2中頭指針節點值，對表1中數據進行過濾，重排序后的數據顯示在表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樹了。從空集（符號為?）開始，向其中不斷添加頻繁項集。過濾、排序后的事務依次添加到樹中，如果樹中已存在現有元素，則增加現有元素的值；如果現有元素不存在，則向樹添加一個分枝。對表2前兩條事務進行添加的過程顯示在圖3中。

圖3　FP樹構建過程的一個示意圖，圖中給出了使用表2中數據構建FP樹的前兩步

下面代碼用于實現上述過程。

# FP樹構建函數 # 使用數據集以及最小支持度作為參數來構建FP樹。樹構建過程會遍歷數據集兩次。 def createTree(dataSet, minSup=1) :headerTable = {}# 第一次遍歷掃描數據集并統計每個元素項出現的頻度。這些信息被保存在頭指針中。for trans in dataSet :for item in trans :headerTable[item] = headerTable.get(item, 0) + dataSet[trans]# 接著掃描頭指針表刪除那些出現次數小于minSup的項。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][0]if len(localD) > 0 :orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p : p[1], reverse=True)]# 排序后，調用updateTree()方法updateTree(orderedItems, retTree, headerTable, count)return retTree, headerTable# 為了讓FP樹生長，需調用updateTree函數。 def updateTree(items, inTree, headerTable, count) :# 該函數首先測試事務中的第一個元素項是否作為子節點存在。if items[0] in inTree.children :# 如果存在，則更新該元素項的計數inTree.children[items[0]].inc(count)else :# 如果不存在，則創建一個新的treeNode并將其作為一個子節點添加到樹中，這時，頭指針表也要更新以指向新的節點。inTree.children[items[0]] = treeNode(items[0], count, inTree)if headerTable[items[0]][1] == None :headerTable[items[0]][1] = inTree.children[items[0]]else :# 更新頭指針表需要調用函數updateHeaderupdateHeader(headerTable[items[0]][1], inTree.children[items[0]])# updateTree()完成的最后一件事是不斷迭代調用自身，每次調用時會去掉列表中的第一個元素if len(items) > 1 :updateTree(items[1::], inTree.children[items[0]], headerTable, count)# 確保節點鏈接指向樹中該元素項的每一個實例，從頭指針的nodeLink開始，一直沿著nodeLink直到到達鏈表末尾。 # 當處理樹的時候，一種自然的反應就是迭代完整每一件事。當以相同方式處理鏈表時可能會遇到一些問題， # 原因是如果鏈表很長可能會遇到迭代調用的次數限制 def updateHeader(nodeToTest, targetNode) :while (nodeToTest.nodeLink != None) :nodeToTest = nodeToTest.nodeLinknodeToTest.nodeLink = targetNode

運行上例之前，需要一個真正的數據集，使用下面代碼裝入數據：

# 載入數據集 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)] = 1return retDict

上面代碼運行結果：

>>> reload(fpGrowth) <module 'ml.fpGrowth' from 'C:\Python27\ml\fpGrowth.pyc'> >>> 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']] >>> 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, frozen set(['q', 'p', 'r', 't', 'y', 'x', 'z']): 1, frozenset(['h', 'r', 'z', 'p', 'j'] ): 1, frozenset(['z']): 1} >>> myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 3) >>> myFPtree.disp()Null Set 1x 1s 1r 1z 5x 3y 3s 2t 2r 1t 1r 1 >>>

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

有了FP樹后，就可以抽取頻繁項集了，思路與Apriori算法大致類似，首先從單元素項集合開始，然后在此基礎上逐步構建更大的集合。從FP樹中抽取頻繁項集的三個基本步驟如下：

從FP樹中獲得條件模式基；

利用條件模式基，構建一個條件FP樹；

迭代重復步驟1、2，直到樹包含一個元素項為止。

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

3-1 抽取條件模式基

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

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

表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樹。為了獲得這些前綴路徑，可以對樹進行窮舉式搜索，直到獲得想要的頻繁項為止，或使用一個更有效的方法來加速搜索過程?？梢岳孟惹皠摻ǖ念^指針來得到一種更有效的方法。頭指針表包含相同類型元素鏈表的起始指針。一旦到達了每一個元素項，就可以上溯這棵樹直到根節點為止。下面代碼給出了如何發現前綴路徑。

def ascendTree(leafNode, prefixPath) :# 迭代上溯整棵樹if leafNode.parent != None :prefixPath.append(leafNode)ascendTree(leafNode.parent, prefixPath)# 遍歷鏈表直到到達結尾。每遇到一個元素項都會調用ascendTree()來上溯FP樹，并收集所有遇到的元素項的名稱。 # 該列表返回之后添加到條件模式基字典condPats中 def findPrefixPath(basePat, treeNode) :condPats = {}while treeNode != None :prefixPath = []ascendTree(treeNode, prefixPath)if len(prefixPath) > 1 :condPats[frozenset(prefixPath[1:])] = treeNode.counttreeNode = treeNode.nodeLinkreturn condPats

運行效果：

>>> reload(fpGrowth) <module 'ml.fpGrowth' from 'C:\Python27\ml\fpGrowth.pyc'> >>> 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}

3-2 創建條件FP樹

對于每個頻繁項，都創建一棵條件FP樹。我們會為z、x以及其他頻繁項構建條件樹?？梢允褂脛偛虐l現的條件模式基作為輸入數據，并通過相同的建樹代碼來構建這些樹。然后，我們會遞歸地發現頻繁項、發現條件模式基，以及發現另外的條件樹。舉個例子，假定為頻繁項 t 創建一個條件FP樹，然后對{t, y}、{t, x}、……重復該過程。元素項t的條件FP樹的構建過程如圖4所示。

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

在圖4中，元素項s、r是條件模式基的一部分，但它們并不屬于條件FP樹。單獨來看它們都是頻繁項，但是在t的條件樹中，它們卻不是頻繁的，也就是說{t, r}、{t, s}是不頻繁的。

接下來，對集合{t, z}、{t, x}、{t, y}來挖掘對應的條件樹。這會產生更復雜的頻繁項集。該過程重復進行，直到條件樹中沒有元素為止，然后就可以停止了。實現代碼很直觀，使用一些遞歸加上之前寫的代碼即可。具體如下：

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中freqItemList.append(newFreqSet)# 使用findPrefixPath()創建條件基condPattBases = findPrefixPath(basePat, headerTable[basePat][1])# 將條件基condPattBases作為新數據集傳遞給createTree()函數# 這里為函數createTree()添加足夠的靈活性，確保它可以被重用于構建條件樹myCondTree, myHead = createTree(condPattBases, minSup)# 如果樹中有元素項的話，遞歸調用mineTree()函數if myHead != None :print 'conditional tree for: ', newFreqSetmyCondTree.disp()mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)

代碼運行效果：

>>> reload(fpGrowth) <module 'ml.fpGrowth' from 'C:\Python27\ml\fpGrowth.pyc'> >>> freqItems = [] # 顯示所有條件樹 >>> fpGrowth.mineTree(myFPtree, myHeaderTab, 3, set([]), freqItems) conditional tree for: set(['y'])Null Set 1x 3z 3 conditional tree for: set(['y', 'z'])Null Set 1x 3 conditional tree for: set(['s'])Null Set 1x 3 conditional tree for: set(['t'])Null Set 1y 3x 3z 3 conditional tree for: set(['x', 't'])Null Set 1y 3 conditional tree for: set(['z', 't'])Null Set 1y 3x 3 conditional tree for: set(['x', 'z', 't'])Null Set 1y 3 conditional tree for: set(['x'])Null Set 1z 3 # 檢查返回的項集是否與條件樹匹配 >>> freqItems [set(['y']), set(['y', 'x']), set(['y', 'z']), set(['y', 'x', 'z']), 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'])]

5 示例：從新聞網站點擊流中挖掘

>>> parsedDat = [line.split() for line in open('c:\python27\\kosarak.dat').readlines()] >>> initSet = fpGrowth.createInitSet(parsedDat) >>> myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 100000) >>> myFreqList = [] >>> fpGrowth.mineTree(myFPtree, myHeaderTab, 100000, set([]), myFreqList) conditional tree for: set(['1'])Null Set 16 107404 conditional tree for: set(['3'])Null Set 111 97186 18628911 117401 conditional tree for: set(['11', '3'])Null Set 16 117401 conditional tree for: set(['11'])Null Set 16 261773 >>> len(myFreqList) 9 >>> myFreqList [set(['1']), set(['1', '6']), set(['3']), set(['11', '3']), set(['11', '3', '6'] ), set(['3', '6']), set(['11']), set(['11', '6']), set(['6'])]

6 小結

FP-growth算法是一種用于發現數據集中頻繁模式的有效方法。FP-growth算法利用Apriori原則，執行更快。Apriori算法產生候選項集，然后掃描數據集來檢查它們是否頻繁。由于只對數據集掃描兩次，因此FP-growth算法執行更快。在FP-growth算法中，數據集存儲在FP樹中。FP樹構建完成后，可以通過查找元素項的條件基，及構建條件FP樹來發現頻繁項集。該過程不斷以更多元素作為條件重復進行，直到FP樹只包含一個元素為止。

可以使用FP-growth算法在多種文本文檔中查找頻繁單詞。

總結

以上是生活随笔為你收集整理的机器学习实战-FP-growth算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：船舶航速优化文献阅读
下一篇：如果Windows下Quick软件运行时