本來老師是想讓我學Hadoop的，也裝了Ubuntu，配置了Hadoop，一時間卻不知從何學起，加之自己還是想先看點自己喜歡的算法，學習Hadoop也就暫且擱置了，不過還是想問一下園子里的朋友有什么學習Hadoop好點的資料，求推薦~言歸正傳，繼Apriori算法之后，今天來學習FP-growth算法。

和Apriori算法相比，FP-growth算法只需要對數據庫進行兩次遍歷，從而高效發現頻繁項集。對于搜索引擎公司而言，他們需要通過查看互聯網上的用詞來找出經常在一塊出現的詞對，因此這些公司就需要能夠高效的發現頻繁項集的方法，今天要學習的FP-growth算法就可以完成此重任。

一 FP-growth算法

1.概述

FP-growth算法是基于Apriori原理的，通過將數據集存儲在FP(Frequent Pattern)樹上發現頻繁項集，但不能發現數據之間的關聯規則。FP-growth算法只需要對數據庫進行兩次掃描，而Apriori算法在求每個潛在的頻繁項集時都需要掃描一次數據集，所以說Apriori算法是高效的。其中算法發現頻繁項集的過程是：

(1)構建FP樹；

(2)從FP樹中挖掘頻繁項集。

2. 構建FP樹

FP表示的是頻繁模式，其通過鏈接來連接相似元素，被連起來的元素可以看成是一個鏈表。將事務數據表中的各個事務對應的數據項按照支持度排序后，把每個事務中的數據項按降序依次插入到一棵以 NULL為根節點的樹中，同時在每個結點處記錄該結點出現的支持度。

FP-growth算法的流程為：首先構造FP樹，然后利用它來挖掘頻繁項集。在構造FP樹時，需要對數據集掃描兩邊，第一遍掃描用來統計頻率，第二遍掃描至考慮頻繁項集。下面舉例對FP樹加以說明。

假設存在的一個事務數據樣例為,構建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

結合Apriori算法中最小支持度的閾值，在此將最小支持度定義為3，結合上表中的數據，那些不滿足最小支持度要求的將不會出現在最后的FP樹中，據此構建FP樹，并采用一個頭指針表來指向給定類型的第一個實例，快速訪問FP樹中的所有元素，構建的帶頭指針的FP樹如下:

結合繪制的帶頭指針表的FP樹，對表中數據進行過濾，排序如下：

事務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樹了，從NULL開始，向其中不斷添加過濾排序后的頻繁項集。過程可表示為：

根據該思想就可以實現FP樹的構建，下面就采用Python進行實現。我們知道，在第二次掃描數據集時會構建一棵FP樹，并采用一個容器來保存樹。首先創建一個類來保存樹的每一個節點，代碼如下：

#coding:utf-8

from numpy import *

classtreeNode:def __init__(self, nameValue, numOccur, parentNode):

self.name=nameValue

self.count=numOccur

self.nodeLink=None

self.parent= parentNode #needs to be updated

self.children ={}definc(self,numOccur):

self.count+=numOccurdef disp(self,ind = 1):print ' '*ind,self.name,' ',self.countfor child inself.children.values():

child.disp(ind+1)'''#test

rootNode = treeNode('pyramid',9,None)

rootNode.children['eye'] = treeNode('eye',13,None)

a = rootNode.disp()

print a'''

這樣，FP樹對應的數據結構就建好了，現在就可以構建FP樹了，FP樹的構建函數如下:

#FP構建函數

def createTree(dataSet,minSup = 1):

headerTable={}for trans indataSet:for item intrans:

headerTable[item]= headerTable.get(item,0) + dataSet[trans]#記錄每個元素項出現的頻度

for k inheaderTable.keys():if headerTable[k] freqItemSet=set(headerTable.keys())if len(freqItemSet) == 0:#不滿足最小值支持度要求的除去returnNone,Nonefor k inheaderTable:headerTable[k]=[headerTable[k],None]retTree= treeNode('Null Set',1,None)for tranSet,count indataSet.items():localD={}for item intranSet:if item infreqItemSet: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)returnretTree,headerTabledefupdateTree(items, inTree, headerTable, count):if items[0] ininTree.children:inTree.children[items[0]].inc(count)else: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:updateTree(items[1::], inTree.children[items[0]], headerTable, count)defupdateHeader(nodeToTest, targetNode):while (nodeToTest.nodeLink !=None):nodeToTest=nodeToTest.nodeLinknodeToTest.nodeLink= targetNode在運行上例之前還需要一個真正的數據集，結合之前的數據自定義數據集：defloadSimpDat():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']]returnsimpDatdefcreateInitSet(dataSet):retDict={}for trans indataSet:retDict[frozenset(trans)]= 1return retDict運行：#testsimpDat =loadSimpDat()initSet=createInitSet(simpDat)myFPtree,myHeaderTab= createTree(initSet,3)a=myFPtree.disp()print a這樣就構建了FP樹，接下來就是使用它來進行頻繁項集的挖掘。3. 從FP樹中挖掘頻繁項集在構建了FP樹之后，就可以抽取頻繁項集了，這里的思想和Apriori算法大致類似，首先從氮元素項集合開始，然后在此基礎上逐步構建更大的集合。大致分為三個步驟：(1)從FP樹中獲得條件模式基；(2)利用條件模式基，構建一個條件FP樹；(3)迭代重復(1)和(2)，直到樹包含一個元素項為止。首先，獲取條件模式基。條件模式基是以所查找元素項為結尾的路徑集合，表示的是所查找的元素項與樹根節點之間的所有內容。結合構建FP樹繪制的圖，r的前綴路徑就是{x,s}、{z,x,y}和{z},其中的每條前綴路徑都與一個計數值有關，該計數值表示的是每條路徑上r的數目。為了得到這些前綴路徑，結合之前所得到的頭指針表，頭指針表中包含相同類型元素鏈表的起始指針，根據每一個元素項都可以上溯到這棵樹直到根節點為止。該過程對應的代碼如下：def ascendTree(leafNode, prefixPath): #ascends from leaf node to rootif leafNode.parent !=None:prefixPath.append(leafNode.name)ascendTree(leafNode.parent, prefixPath)def findPrefixPath(basePat, treeNode): #treeNode comes from header tablecondPats ={}while treeNode !=None:prefixPath=[]ascendTree(treeNode, prefixPath)if len(prefixPath) > 1:condPats[frozenset(prefixPath[1:])] =treeNode.counttreeNode=treeNode.nodeLinkreturncondPats#testsimpDat =loadSimpDat()initSet=createInitSet(simpDat)myFPtree,myHeaderTab= createTree(initSet,3)a=myFPtree.disp()b= findPrefixPath('x',myHeaderTab['x'][1])print b運行代碼，與所給數據一致。接下來就可以創建條件FP樹了。對于每一個頻繁項，都需要創建一棵條件FP樹，使用剛才創建的條件模式基作為輸入，采用相同的建樹代碼來構建樹，相應的遞歸發現頻繁項、發現條件模式基和另外的條件樹。對應的遞歸查找頻繁項集的函數如下：defmineTree(inTree, headerTable, minSup, preFix, freqItemList):bigL= [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])]#(sort header table)for basePat inbigL:newFreqSet=preFix.copy()newFreqSet.add(basePat)freqItemList.append(newFreqSet)condPattBases= findPrefixPath(basePat, headerTable[basePat][1])myCondTree, myHead=createTree(condPattBases, minSup)if myHead !=None:mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)結合之前的數據驗證發現無誤。二 ?從新聞網站點擊流中挖掘上述在自定義的數據中隊算法進行了驗證，現在選取實際的數據進行測試。在這個數據集合中，包含了100萬條記錄，文件中的每一行包含某個用戶瀏覽過的新聞報道，用來尋找那些至少被10萬人瀏覽過的報道。代碼如下：#從新聞網站點擊流中挖掘parsedData = [line.split() for line in open('kosarak.dat').readlines()]initSet=createInitSet(parsedData)myFPtree,myHeaderTab= createTree(initSet,100000)myFreqList=[]a= mineTree(myFPtree,myHeaderTab,100000,set([]),myFreqList)b=len(myFreqList)printbprint myFreqList這樣就實現了此功能。以上是我自己的總結和理解，難免有錯，還望各位朋友不吝賜教~

總結

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

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