一種新型的基于Hadoop框架的分布式并行FP－Growth算法

張振友，孫 燕，丁鐵凡，劉鵬飛

（華北理工大學信息工程學院，河北唐山 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)閉項集就對搜索空間進行剪枝的方法。

1 FP－Growth算法

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算法有分治策略，為下面提出的分布式計算提供了可能。

2 FP－Growth算法中FP－Tree挖掘過程的改進

傳統(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)化，減少了樹的路徑，從而提高了算法的計算速度。

3 基于Hadoop的并行FP－Growth實現(xiàn)

面對大規(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ù)。

4 實驗過程與結果

為了驗證提出改進的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ù)的頻繁項集挖掘。

5 結 語

改進的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