張振友,孫 燕,丁鐵凡,劉鵬飛
(華北理工大學信息工程學院,河北唐山 063009)
?
一種新型的基于Hadoop框架的分布式并行FP-Growth算法
張振友,孫 燕,丁鐵凡,劉鵬飛
(華北理工大學信息工程學院,河北唐山 063009)
摘 要:針對傳統(tǒng)FP-Growth算法在大規(guī)模數(shù)據(jù)環(huán)境下存在的挖掘效率低和內(nèi)存溢出問題,在傳統(tǒng)FP-Growth算法的基礎上,提出一種新的并行FP-Growth算法,并在分布式計算框架Hadoop 的MapReduce編程模式下實現(xiàn)并行化處理。實驗數(shù)據(jù)表明,并行的FP-Growth算法與傳統(tǒng)的FPGrowth算法相比,具有相同數(shù)據(jù)量下計算時間短,相同時間內(nèi)處理數(shù)據(jù)量增大的優(yōu)點,并在一定條件下解決了大數(shù)據(jù)挖掘的內(nèi)存溢出問題。
關鍵詞:并行處理;分布式;數(shù)據(jù)挖掘;閉頻繁項集;Hadoop;FP-Growth
E-mail:youzhenadd@163.com
張振友,孫 燕,丁鐵凡,等.一種新型的基于Hadoop框架的分布式并行FP-Growth算法[J].河北工業(yè)科技,2016,33(2):169-177.
ZHANG Zhenyou,SUN Yan,DING Tiefan,et al.A novel distributed parallel FP-Growth algorithm based on Hadoop framework[J].Hebei Journal of Industrial Science and Technology,2016,33(2):169-177.
關聯(lián)規(guī)則挖掘的基本算法主要有Apriori算法和FP-Growth算法。1993年,AGRAWAL等在美國IBM Almaden Research Center首先提出了關聯(lián)規(guī)則的概念,用于挖掘顧客交易數(shù)據(jù)庫中的頻繁模式。至此,諸多的研究人員對關聯(lián)規(guī)則的挖掘問題進行了大量的研究[1]。AGRAWAL提出了經(jīng)典的Apriori算法來挖掘數(shù)據(jù)集中的頻繁模式,從而挖掘出數(shù)據(jù)項集之間的關聯(lián)規(guī)則。為了更好地提高挖掘效率,研究人員提出了基于Hash表的項集計數(shù)技術(利用Hash表提高項集計數(shù)效率),基于事務壓縮的算法(壓縮進一步迭代掃描的事務數(shù)),基于分區(qū)的算法(對原始數(shù)據(jù)進行劃分各找候選項集),基于事務抽樣技術的算法(關聯(lián)挖掘在數(shù)據(jù)樣本上而不是整個數(shù)據(jù)集上進行)以及動態(tài)項集計數(shù)的算法(在掃描的不同點添加候選項集)等的改進算法[2]。但是這些算法都需要反復地掃描數(shù)據(jù)庫,并且產(chǎn)生大量候選項集,這些缺點會增大系統(tǒng)的開銷[3]。于是出現(xiàn)了挖掘全部頻繁項集卻不產(chǎn)生大量候選項集的頻繁模式增長,即FP-Growth(Frequent Pattern-Growth)算法[4-5]。
隨著大數(shù)據(jù)時代的到來,大規(guī)模數(shù)據(jù)的產(chǎn)生從存儲和計算兩方面考驗了單機處理能力,而在處理海量數(shù)據(jù)時單機環(huán)境已遠遠不能滿足。因此,并行計算環(huán)境成為了研究者們的新問題。有研究者提出的基于多線程的并行算法,在很大程度上緩解了存儲及計算的壓力,但是內(nèi)存資源的局限性成為了算法擴展的瓶頸[6];有研究人員在MPI并行環(huán)境的基礎上,使用進程間通信的方式協(xié)調(diào)并行計算,結果計算效率較低,內(nèi)存開銷大,并且不能夠實現(xiàn)多節(jié)點的橫向擴展[7-8];為了在某種程度上降低并行計算時的通信消耗,鄒翔等[9]提出了一種基于前綴樹的并行算法。
針對海量數(shù)據(jù)的數(shù)據(jù)挖掘問題,本文提出了一種改進FP-Growth算法。通過分布式計算框架Hadoop的MapReduce編程模式對改進FPGrowth算法的各個步驟并行化[10],不僅提高了挖掘效率,而且有效地解決了內(nèi)存不足的問題,并針對算法在挖掘FP-Tree中產(chǎn)生大量的頻繁項集的問題,提出了在挖掘過程中發(fā)現(xiàn)閉項集就對搜索空間進行剪枝的方法。
Apriori算法是關聯(lián)規(guī)則模式挖掘的經(jīng)典算法,其尋找最大項集的基本思想是:算法需要進行多個步驟處理數(shù)據(jù)集。第1步,簡單統(tǒng)計所有含有1個元素的項集出現(xiàn)的頻率,并找出不小于最小支持度的項集。第2步,開始數(shù)據(jù)處理直到再沒有最大項集生成[11-13]。Apriori算法在數(shù)據(jù)量較小的情況下能夠大大壓縮候選閉頻繁項集的大小,但是由于它需要反復訪問事務數(shù)據(jù)庫,并且在對長模式挖掘時會產(chǎn)生大量的候選項集。針對Apriori算法的I/O頻繁訪問和存儲空間大的主要性能瓶頸,提出了FP-Growth算法來減少全量掃描事務數(shù)據(jù)庫的次數(shù),并且不產(chǎn)生候選項集[14-15]。FP-Growth算法使用了一種稱為頻繁模式樹FP-Tree的數(shù)據(jù)結構,并直接從該結構中提取頻繁項集。FP-Tree是一種特殊的前綴樹,由頻繁項頭表和項前綴樹構成[16-17]。所謂前綴樹,是一種存儲候選項集的數(shù)據(jù)結構,樹的分支用項名標志,樹的節(jié)點存儲后綴項,路徑表示項集[18]。
假設I={I1,I2,…,Im}是項的集合。給定一個訂單數(shù)據(jù)庫ORDER,其中每個事務R是P的非空子集,即,每一個訂單都與一個唯一的標志符RID相對應,如表1所示。
表1 事務數(shù)據(jù)表Tab.1 Transaction data table
FP-Growth算法的具體步驟[19]如下。
1)第1次全量掃描事務數(shù)據(jù)庫,統(tǒng)計導出k=1項集以及對應的支持度計數(shù),并且按照支持度計算降序排序,結果記為L。支持度設置為2,則L={{P2:7},{P1:6},{P3:6},{P4:2},{P5:2}}。
2)再次全量掃描事務數(shù)據(jù)庫,按照每個事物中出現(xiàn)的頻繁項建立FP-Tree。首先創(chuàng)建樹的根節(jié)點,記為root。處理每條事務數(shù)據(jù)按照L頻繁項集添加到FP-Tree中的一個分支。
①掃描訂單R100的事務“P1,P2,P5”,按照L中的順序將該事務進行排序為“P2,P1,P5”,構造FP-Tree的第1個分支,如圖1所示。
圖1 事務R100數(shù)據(jù)形成的FP-TreeFig.1 FP-Tree built from R100transaction data
②掃描訂單R200“P2,P4”,排序為“P2,P4”,與R100共享節(jié)點{P2},因此將樹中節(jié)點{P2}的計數(shù)加1,同時在{P2}節(jié)點上創(chuàng)建一個{P4:1}的分支,如圖2所示。
圖2 事務R200數(shù)據(jù)形成的FP-TreeFig.2 FP-Tree built from R200transaction data
③以此類推,將事務數(shù)據(jù)庫中的所有訂單都添加到FP-Tree中。
如此,遍歷整個事務數(shù)據(jù)庫,每條訂單數(shù)據(jù)排序,創(chuàng)建對應的路徑,但是,如果創(chuàng)建路徑時遇到相同的節(jié)點,該節(jié)點計數(shù)就增加1。為了使形成的FP-Tree能夠方便被遍歷,創(chuàng)建一個項頭表,表的字段項為ID、支持度計數(shù)、節(jié)點鏈。所以,經(jīng)過上述建立FP-Tree的過程,最終FP-Tree結構如圖3所示。
圖3 存儲頻繁模式信息的FP-TreeFig.3 FP-Tree of store frequent patterns information
FP-Growth算法最后一步為挖掘FP-Tree。挖掘過程如下:遍歷L頻繁項集,構建每個項的條件模式基(即子數(shù)據(jù)庫),通過它的前綴路徑來構建條件FP-Tree樹,根據(jù)項頭表至底向上遞歸挖掘,鏈接后綴模式與條件FP-Tree生成的頻繁模式為最終的頻繁項集。表2為FP-Tree挖掘過程的總結。
表2 FP-Tree挖掘過程Tab.2 FP-Tree mining process
綜上所述,F(xiàn)P-Growth算法主要分為建立FPTree和挖掘FP-Tree,從而在不產(chǎn)生候選項集的條件下實現(xiàn)頻繁項集的挖掘。同時,把數(shù)據(jù)壓縮成樹形結構,大大減少了存儲空間。傳統(tǒng)FP-Growth算法有分治策略,為下面提出的分布式計算提供了可能。
傳統(tǒng)的FP-Growth算法有如下優(yōu)點:具有分治策略,可以分解挖掘任務或事務數(shù)據(jù)庫;不需產(chǎn)生候選項集,并且產(chǎn)生樹形結構,大大減少了存儲空間;不需要反復掃描數(shù)據(jù)庫,降低了I/O訪問,提高了性能[20]。為了優(yōu)化FP-Growth算法的性能,本文采用項合并策略進行剪枝優(yōu)化。
該策略定義如下:如果包含頻繁項集A的每個事務都包含項集B,但不包含B的任何真超集,則A∪B形成一個閉頻繁項集,并且不必再搜索包含A但不包含B的任何項集[21]。
首先明確幾個概念。
1)超集:如果一個集合S2中的每一個元素都在集合S1中,且集合S1中可能包含S2中沒有的元素,則集合S1就是S2的一個超集。
2)真超集:S1是S2的超集,若S1中一定有S2中沒有的元素,則S1是S2的真超集,S2是S1的真子集。
3)閉項集:如果一個項集X,它的真超集的支持度計數(shù)都不等于它本身的支持度計數(shù),則X為閉項集。
4)閉頻繁項集:如果閉項集的支持度大于等于最小支持度閾值,則稱為閉頻繁項集。
①證明A∪B=A=B。首先證明“包含頻繁項集A的每個事務都包含項集B”意味著A是B的超集。如果B中含有一個項b,b?A,則必存在一個只由項集A的項所構成的事務,它不包含項b,從而也就不包含項集B,與已知相矛盾。
②證明“但不包含B的任何真超集”意味著A=B。如果A≠B,且A是B的超集,則A是B的真超集。再由“包含頻繁項集A的每個事務都包含項集B”可知,每個事務都包含項集B的真超集,與已知條件矛盾。故A∪B=A=B。即:包含頻繁項集A的每個事務都不包含A的任何真超集。這意味著包含頻繁項集A的每個事務都由A且僅由A構成,不包含A的任何直接超集。所以,A的直接超集的支持度計數(shù)都不等于它本身的支持度計數(shù)。所以A是一個閉項集。由已知條件,A是一個頻繁項集,所以A是一個閉頻繁項集。A∪B=A自然也是一個閉頻繁項集。
由于B=A,最后不必再搜索包含A但不包含B的任何項集,命題得證。
通過項合并策略能夠大大減少搜索空間,提高挖掘頻繁樹的效率,也在很大程度上減少了頻繁項集的數(shù)量,產(chǎn)生少量的頻繁閉項集。
FP-Growth算法主要分為2步。
1)通過掃描整個事務數(shù)據(jù)庫,計算出L頻繁項集,并且按項的頻繁計數(shù)從大到小排序,記為L-List。再次全量查詢事務數(shù)據(jù)庫,遍歷每條事務數(shù)據(jù),根據(jù)L-List做一次升序排序,然后創(chuàng)建節(jié)點名root為FP樹的根節(jié)點,按照建立FP-Tree的流程(見圖4)生成一顆完備的模式樹。
圖4 創(chuàng)建FP-Tree的流程圖Fig.4 Flow chart of FP-Tree establishment
2)開始挖掘上一步建立的FP-Tree,提出了項合并的策略來減少挖掘FP-Tree時產(chǎn)生的條件模式基,從而達到剪枝的效果。整個挖掘FP-Tree的流程如圖5所示。
挖掘FP-Tree的步驟如下。
1)自底向上的方式遍歷生成的FP-Tree的項頭表,從而得到此節(jié)點的所有前綴路徑,以此節(jié)點為后綴模式,得到FP-Tree中所有包含此節(jié)點的路徑。
2)如果上一步得到單條路徑,前綴路徑的每個元素和后綴模式合并生成頻繁項集。否則,需找前綴路徑中是否存在項合并策略中的情況,若存在,剪枝后合并。
圖5 改進的挖掘FP-Tree的流程圖Fig.5 Flow chart of improved mining FP-Tree
3)以上述得到的路徑作為新的數(shù)據(jù)庫,重新按照創(chuàng)建FP-Tree的流程創(chuàng)建一棵新的FP-Tree,但是此時樹的根節(jié)點為后綴模式,即挖掘的項。
4)把生成的樹作為第1步輸入數(shù)據(jù)源,反復迭代,直到最后只生成1條路徑。
通過上述過程,整個FP-Tree挖掘的過程結束,挖掘出來的頻繁項集都是閉頻繁項集。整個過程對搜索閉項集的空間做了相應的優(yōu)化,減少了樹的路徑,從而提高了算法的計算速度。
面對大規(guī)模數(shù)據(jù)集,傳統(tǒng)的FP-Growth計算的速度有所降低,雖然有研究人員提出多線程的方式來緩解計算數(shù)據(jù)的壓力,但是當數(shù)據(jù)量達到一定程度時,單臺計算機的內(nèi)存限制成為FP-Growth算法的瓶頸。為了更好地解決單機版FP-Growth算法存在的各種問題,利用Hadoop自身處理大數(shù)據(jù)的各種優(yōu)勢,本研究提出基于分布式計算框架Hadoop并行計算的FP-Growth算法,很好地解決了傳統(tǒng)FP-Growth算法的問題。圖6為分布式FPGrowth算法的流程圖。
圖6 分布式FP-Growth算法的流程圖Fig.6 Flow chart of distributed FP-Growth algorithm
通過圖6可知:分布式FP-Growth算法完美結合了MapReduce的編程思想,利用三步串行的MapReduce任務來完成,其中,結合分布式緩存機制來存儲L-List表能夠提高訪問效率,降低相應的I/O操作。分布式FP-Growth算法的主要步驟詳細描述如下。
1)統(tǒng)計L頻繁項集
統(tǒng)計L頻繁項集是并行算法的第1步。該步驟的主要任務是統(tǒng)計每個項在數(shù)據(jù)庫中出現(xiàn)的次數(shù),并且過濾出現(xiàn)次數(shù)小于設置的最小支持度的項,再把剩余的項通過出現(xiàn)的次數(shù)進行降序排序,最終得到L-List集合。其中L-List集合中不僅存儲了項的唯一標志,而且也存儲了項出現(xiàn)的頻率,即項的計數(shù)。
統(tǒng)計L項集的具體處理步驟。
①Map過程:第1次全量掃描事務數(shù)據(jù)庫,輸入的key為每行的偏移量,value為每條事務數(shù)據(jù)。針對value的值進行分割后,輸出的key為每個項,value為每個項首次出現(xiàn)的計數(shù)為1。
②Combiner過程:在集群的每個節(jié)點上本地化的對每個項進行1次相加統(tǒng)計,輸出的key依舊是項,value變?yōu)楸竟?jié)點上項出現(xiàn)的次數(shù),即計數(shù)。此過程提高了計算性能。
③Reduce過程:收集Map階段輸出的中間結果,統(tǒng)計每個項在整個事務數(shù)據(jù)庫中出現(xiàn)的頻率。輸出的key為項的標志符,value為數(shù)據(jù)中出現(xiàn)的頻率。圖7是統(tǒng)計L項集的數(shù)據(jù)樣式圖。
圖7 L項集的數(shù)據(jù)樣式圖Fig.7 Data style figure of Litemsets
統(tǒng)計L頻繁項集階段得出的結果就是整個數(shù)據(jù)庫的1頻繁項集。通過每個項的計數(shù)由高到低排序后,就形成了L-List集合,并且把L-List集合存入Hadoop的分布式緩存,如此在整個集群中可以共享該文件,從而方便事務數(shù)據(jù)庫分發(fā)數(shù)據(jù),減少相應的I/O操作。為了達到每組數(shù)據(jù)的平衡和獨立,利用L-List集合中的L項進行分組。
2)并行FP-Growth
圖8為并行FP-Growth算法的實現(xiàn)步驟。通過圖8可知,并行FP-Growth算法的具體過程如下。
分組和Map過程:將分布式緩存中的L-List集合存入Map中,并且對項對應的一個編號進行映射,記為i。第2次全量訪問事務數(shù)據(jù)庫,遍歷每條事務數(shù)據(jù)中的項,通過L-List表中的L頻繁項集得到一個組標志符(記為變量g),從而得到了G-List集合。
圖8 并行FP-Growth算法的過程圖Fig.8 Process chart of the parallel FP-Growth algorithm
其中,分組策略首先要得到每組中項的個數(shù),記為m。
式中:m為每組中項的個數(shù);|F|為L-List集合的模,即集合中項的個數(shù);n為設定的組數(shù)。
如果式(1)不能整除,m就加上1取整數(shù)。
遍歷每條事務數(shù)據(jù)中的項,依照L-List集合,先做1次排序,然后在映射表中找到項的映射數(shù)字,即i。這樣,此項每組標志符計算公式如式(2)所示:
式中:g為此項將分入的組號;i為項在L-List集合中的排序號;m為每組中項的個數(shù)。
通過上述策略找到每個項對應的組,聚合每個組,從而得到G-List集合。
Map過程:在此Map階段輸出的key值為g,value為整條數(shù)據(jù)的子項集(事務序列P的子序列)。這樣分組不僅均衡了整個數(shù)據(jù)庫的投影數(shù)據(jù),同時保證了挖掘過程中數(shù)據(jù)的完備性。
Combiner過程:本地聚合每組中的事務數(shù)據(jù),形成壓縮的事務數(shù)據(jù)。
Reduce過程:此階段是整個算法中關鍵的一步,也是并行FP-Growth算法中具體對數(shù)據(jù)挖掘的一步,是在集群節(jié)點上運行本地化的本文改進的FP-Growth算法,但數(shù)據(jù)已不是整個事務數(shù)據(jù)庫,而是子數(shù)據(jù)庫。先建立FP-Tree,然后通過本文改進的挖掘算法得到頻繁項集。輸出的key為組號,value為挖掘出來的頻繁項集。
3)聚合
圖9為分布式FP-Growth算法的最后一步。
圖9 挖掘K項最大的閉頻繁項集的過程圖Fig.9 Process diagram of mining the biggest closed frequent itemsets of Kitems
挖掘K項最大的閉頻繁項集的具體步驟如下。
Map過程:本過程輸入的value為挖掘出來的頻繁項集。遍歷頻繁項集中的元素,輸出的key為此元素的項,value為此頻繁項集。
Combiner過程:本地化對每個項的相應頻繁項集做1次排序并且選取頻繁項集共同出現(xiàn)的頻率最大的K項頻繁項集。
Reduce過程:收集Combiner過程產(chǎn)生的局部最大的K項頻繁項集,再次做排序,選取整個數(shù)據(jù)庫中計數(shù)最大的K項閉頻繁項集。
至此,整個分布式的FP-Growth算法完成??v觀整個分布式算法實現(xiàn)過程,其實是MapReduce編程模式的完美體現(xiàn)。這個過程清晰,但是在每一步的關鍵部分是被封裝的,如果對一些策略要進行性能上的提升,可通過Hadoop中MapReduce計算框架的參數(shù)設定來實現(xiàn)性能的調(diào)優(yōu)。
為了性能的提升和計算速率的提高,在整個過程中運用了分布式緩存和本地化聚合等策略。分布式的改進FP-Growth算法在處理大量的數(shù)據(jù)時速度有明顯提升,這也是整個分布式計算框架最大的特性。但在處理小數(shù)據(jù)方面花費的時間要長些,所以在實現(xiàn)分布式的同時也為本地算法提供了具體的API,這樣不僅能通過內(nèi)存算法來計算小量數(shù)據(jù),同時也可以利用并行算法來計算大規(guī)模的數(shù)據(jù)。
為了驗證提出改進的FP-Growth算法性能,利用mushroom.dat數(shù)據(jù)來進行驗證實驗。mushroom.dat數(shù)據(jù)來自于Frequent Itemset Mining Data Repository[22]。實驗通過FP-Growth算法和改進的FP-Growth算法在相同的最小支持度下挖掘同一份數(shù)據(jù)的速率來做比較,其中結果的橫坐標數(shù)值為支持度閾值,那么最小支持度為整個mushroom.dat數(shù)據(jù)中包含的事務數(shù)據(jù)條數(shù)乘于支持度閾值,即min_support=transactions.number*threshold。圖10為該實驗的比較圖。
圖10 挖掘速率比較圖Fig.10 Mining rate comparison chart
從圖10中可以看出,改進的FP-Growth算法在計算速度上有明顯提高,性能較好。說明通過項合并的策略減少了搜索FP-Tree的迭代次數(shù),實現(xiàn)了對搜索空間的剪枝。隨著閾值的變大,相應的最小支持度計數(shù)也變大,從而得到的頻繁項集的總量在減少,搜索代價也隨之降低,所以改進的FPGrowth算法和FP-Growth算法在挖掘速度上很接近。因此,改進的FP-Growth算法挖掘出來的閉頻繁項集數(shù)量遠遠少于總量的頻繁項集。
驗證實驗的挖掘速度隨著數(shù)據(jù)量的增加,挖掘速度急劇下降,到一定程度就會內(nèi)存溢出。為了測試分布式改進的FP-Growth算法對大規(guī)模數(shù)據(jù)量處理能力是否提升,改進實驗的數(shù)據(jù)為訂單數(shù)據(jù),此數(shù)據(jù)量最大為10 000萬條。其中本實驗所采用的分布式計算環(huán)境包含master,slave1,slave2,slave3 共4個節(jié)點的Hadoop集群,其中每個節(jié)點為Inter XEON Pcs(E3-1220LCPU,32GB RAM),Hadoop版本為Hadoop1.2。該實驗分別從2方面來做測試。
為了反映各個數(shù)據(jù)量下分布式算法的計算速度,分別選取了10萬數(shù)量級中10萬和50萬,100萬數(shù)量級中100萬和500萬,1 000萬數(shù)量級的1 000萬,3 000萬,5 000萬,7 000萬和10 000萬。實驗結果如圖11所示。
圖11 數(shù)據(jù)量與計算速率的折線圖Fig.11 Line chart of data volume and computing rate
為了展示在同樣數(shù)量級的數(shù)據(jù)中挖掘最大的K項頻繁項集花費的時間情況,選取了K=3,5,8,10和12項頻繁項集。實驗顯示每一步的CPU計算時間的情況,使得結果更加清晰,實驗結果如圖12所示。
圖12 K項與計算速率的折線圖Fig.12 Line chart of Kand computing rate
通過實驗可知:在不同數(shù)量級下基于分布式的改進FP-Growth算法的計算時間是不同的,首先是第1步在數(shù)據(jù)集的規(guī)模劇增時花費的時間相對緩慢,其次是第3步,最后是第2步,其是整個分布式算法當中最為關鍵的一步,也是最消耗時間的一步,這步的計算任務是非常繁重的,但在大規(guī)模數(shù)據(jù)下消耗的時間是可以接受的。至少不會出現(xiàn)單機運行大規(guī)模數(shù)據(jù)時出現(xiàn)內(nèi)存溢出的情況。
實驗說明了在挖掘不同最大K項頻繁項集時花費的時間差距是不大的,每一步花費的時間都比較緩慢。說明分布式算法充分利用了集群的性能和內(nèi)存空間,能夠很好地完成大規(guī)模數(shù)據(jù)的頻繁項集挖掘。
改進的FP-Growth算法在性能上有著明顯提升,主要原因是在挖掘FP-Tree的時候通過項合并的策略來剪枝,大大減少了挖掘樹迭代的次數(shù)。同時,生成的閉頻繁項集相對于頻繁項集的總量小了很多,減少了需在內(nèi)存中占用的空間。此外,分布式改進的FP-Growth算法在處理大規(guī)模的數(shù)據(jù)量時有相當大的優(yōu)勢,分而治之的策略充分利用了集群的資源來實現(xiàn)單機無法達到的結果。
參考文獻/References:
[1] 付冬梅,王志強.基于FP-tree和約束概念格的關聯(lián)規(guī)則挖掘算法及應用研究[J].計算機應用研究,2014,31(4):1013-1015.FU Dongmei,WANG Zhiqiang.Mining algorithm of association rule based on FP-tree and constrained concept lattice and application research[J].Application Research of Computers,2014,31(4):1013-1015.
[2] 何月順.關聯(lián)規(guī)則挖掘技術的研究及應用[D].南京:南京航空航天大學,2010.HE Yueshun.Research and Application on the Technologies in Mining Association Rules[D].Nanjing:Nanjing University of Aeronautics and Astronautics,2010.
[3] 施亮,錢雪忠.基于Hadoop的并行FP-Growth算法的研究與實現(xiàn)[J].微電子學與計算機,2015,32(4):150-154.SHI Liang,QIAN Xuezhong.Research and implementation of parallel FP-Growth algorithm based on Hadoop[J].Microelectronics &Computer,2015,32(4):150-154.
[4] LAN V,ALAGHBAND G.Novel parallel method for association rule mining on multi-core shared memory systems[J].Parallel Computing,2014,40(10):768-785.
[5] 楊勇,王偉.一種基于MapReduce的并行FP-growth算法[J].重慶郵電大學學報(自然科學版),2013,25(5):651-657.YANG Yong,WANG Wei.A parallel FP-growth algorithm based on MapReduce[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2013,25(5):651-657.
[6] LIU Li,LI Eric,ZHANG Yiming,et al.Optimization of frequent itemset mining on multiple-core processor[C]//Proceedings of the 33rdInternational Conference on Very Large Data Bases.Vienna:[s.n.],2007:1275-1285.
[7] AOUAD L M,LE-KHAC N A,KECHADI T M.Distributed frequent itemsets mining in heterogeneous platforms[J].Journal of Engineering,2007(2):1-12.
[8] MOHAMMAD E,OSMAR R.Parallel leap:Large-scale maximal pattern mining in a distributed environment[C]//Proceedings of the 12th International Conference on Parallel and Distributed Systems.Minneapolis:Conference Publications,2006:135-142.
[9] 鄒翔,張巍,劉洋,等.分布式序列模式發(fā)現(xiàn)算法的研究[J].軟件學報,2005,16(7):1262-1269.ZOU Xiang,ZHANG Wei,LIU Yang,et al.Study on distributed sequential pattern discovery algorithm[J].Journal of Software,2005,16(7):1262-1269.
[10]馮漢超,周凱東.分布式系統(tǒng)下大數(shù)據(jù)存儲結構優(yōu)化研究[J].河北工程大學學報(自然科學版),2014,31(4):69-73.FENG Hanchao,ZHOU Kaidong.Research on optimizing big data storage structure in distributed system[J].Journal of Hebei University of Engineering(Natural Science Edition),2014,31(4):69-73.
[11]任家東,王倩,王蒙.一種基于頻繁模式有向無環(huán)圖的數(shù)據(jù)流頻繁模式挖掘算法[J].燕山大學學報,2011,35(2):115-120.REN Jiadong,WANG Qian,WANG Meng.An algorithm based on frequent patterns directed acyclic graph for mining frequent patterns form data stream[J].Journal of Yanshan University,2011,35(2):115-120.
[12]劉步中.基于頻繁項集挖掘算法的改進與研究[J].計算機應用研究,2012,29(2):475-477.LIU Buzhong.Improved apriori mining frequent items algorithm[J].Application Research of Computers,2012,29(2):475-477.
[13]HAN Jiawei,PEI Jian,YIN Yinwen,et al.Mining frequent patterns without candidate generation:A frequent-pattern tree approach[J].Data Mining and Knowledge Discovery,2004,8(1):53-87.
[14]LEE D,PARK S H,MOON S,et al.Utility-based association rule mining:A marketing solution for cross-selling[J].Expert Systems with Applications,2013,40(7):2715-2725.
[15]何中勝,莊燕濱.基于Apriori &FP-growth的頻繁項集發(fā)現(xiàn)算法[J].計算機技術與發(fā)展,2008,18(7):45-47.HE Zhongsheng,ZHUANG Yanbin.Algorithm of mining frequent itemset based on Apriori and FP-growth[J].Computer Technology and Development,2008,18(7):45-47.
[16]NAHAR J,IMAM T,TICKLE K S,et al.Association rule mining to detect factors which contribute to heart disease in males and females[J].Expert Systems with Applications,2013,40(4):1086-1093.
[17]楊云,羅艷霞.FP-Growth算法的改進[J].計算機工程與設計,2010,31(7):1506-1509.YANG Yun,LUO Yanxia.Improved algorithm based on FPGrowth[J].Computer Engineering and Design,2010,31(7):1506-1509.
[18]王新宇,杜孝平,謝坤青.FP-Growth算法的實現(xiàn)方法研究[J].計算機工程與應用,2004,40(9):174-176.WANG Xinyu,DU Xiaoping,XIE Kunqing.Research on implementation of the FP-Growth algorithm[J].Computer Engineering and Applications,2004,40(9):174-176.
[19]陳興蜀,張帥,童浩,等.基于布爾矩陣和MapReduce的FPGrowth算法[J].華南理工大學學報(自然科學版),2014,42(1):135-141.CHEN Xingshu,ZHANG Shuai,TONG Hao,et al.FPGrowth algorithm based on Boolean matrix and MapReduce [J].Journal of South China University of Technology(Natural Science Edition),2014,42(1):135-141.
[20]晏杰,亓文娟.基于Apriori &FP-growth算法的研究[J].計算機系統(tǒng)應用,2013,22(5):122-125.YAN Jie,QI Wenjuan.Research based on Aprior &FP-growth algorithm[J].Computer Systems &Applications,2013,22(5):122-125.
[21]HAN Jiawei,KAMBER M.數(shù)據(jù)挖掘:概念與技術[M].第3版.范明,孟小峰譯.北京:機械工業(yè)出版社,2013.
[22]ANONYMOUS.Frequent Itemset Mining Dataset Repository [EB/OL].http://fimi.ua.a(chǎn)c.be/data,2012-10-21.
A novel distributed parallel FP-Growth algorithm based on Hadoop framework
ZHANG Zhenyou,SUN Yan,DING Tiefan,LIU Pengfei
(School of Information Engineering,North China University of Science and Technology,Tangshan,Hebei 063009,China)
Abstract:Aiming at the low mining efficiency and memory overflow problems of the traditional FP-Growth algorithm,on the basis of the traditional FP-Growth algorithm,a novel parallel FP-Growth algorithm is proposed,which can realize parallel processing in MapReduce programming mode of Hadoop distributed computing framework.The tested data shows that compared to the traditional algorithm,the parallel FP-Growth algorithm has great advantages:the calculation time is greatly reduced when processing the same amount of data;processed data volume is greatly increased under the same time;and memory overflow problem in large scale data mining is solved under certain conditions.
Keywords:parallel processing;distributed;data mining;closed frequent itemsets;Hadoop;FP-Growth
作者簡介:張振友(1964—),男,河北唐山人,副教授,碩士,主要從事數(shù)據(jù)庫及其應用方面的研究。
收稿日期:2015-11-11;修回日期:2015-12-30;責任編輯:陳書欣
文章編號:1008-1534(2016)02-0169-09
中圖分類號:TP311.1
文獻標志碼:A
doi:10.7535/hbgykj.2016yx02013