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

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

（華北理工大學信息工程學院，河北唐山 063009）

?

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

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

（華北理工大學信息工程學院，河北唐山 063009）

摘 要：針對傳統FP－Growth算法在大規模數據環境下存在的挖掘效率低和內存溢出問題，在傳統FP－Growth算法的基礎上，提出一種新的并行FP－Growth算法，并在分布式計算框架Hadoop 的MapReduce編程模式下實現并行化處理。實驗數據表明，并行的FP－Growth算法與傳統的FPGrowth算法相比，具有相同數據量下計算時間短，相同時間內處理數據量增大的優點，并在一定條件下解決了大數據挖掘的內存溢出問題。

關鍵詞：并行處理；分布式；數據挖掘；閉頻繁項集；Hadoop；FP－Growth

E－mail：youzhenadd＠163．com

張振友，孫 燕，丁鐵凡，等．一種新型的基于Hadoop框架的分布式并行FP－Growth算法［J］．河北工業科技，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．

關聯規則挖掘的基本算法主要有Apriori算法和FP－Growth算法。1993年，AGRAWAL等在美國IBM Almaden Research Center首先提出了關聯規則的概念，用于挖掘顧客交易數據庫中的頻繁模式。至此，諸多的研究人員對關聯規則的挖掘問題進行了大量的研究［1］。AGRAWAL提出了經典的Apriori算法來挖掘數據集中的頻繁模式，從而挖掘出數據項集之間的關聯規則。為了更好地提高挖掘效率，研究人員提出了基于Hash表的項集計數技術（利用Hash表提高項集計數效率），基于事務壓縮的算法（壓縮進一步迭代掃描的事務數），基于分區的算法（對原始數據進行劃分各找候選項集），基于事務抽樣技術的算法（關聯挖掘在數據樣本上而不是整個數據集上進行）以及動態項集計數的算法（在掃描的不同點添加候選項集）等的改進算法［2］。但是這些算法都需要反復地掃描數據庫，并且產生大量候選項集，這些缺點會增大系統的開銷［3］。于是出現了挖掘全部頻繁項集卻不產生大量候選項集的頻繁模式增長，即FP－Growth（Frequent Pattern－Growth）算法［4－5］。

隨著大數據時代的到來，大規模數據的產生從存儲和計算兩方面考驗了單機處理能力，而在處理海量數據時單機環境已遠遠不能滿足。因此，并行計算環境成為了研究者們的新問題。有研究者提出的基于多線程的并行算法，在很大程度上緩解了存儲及計算的壓力，但是內存資源的局限性成為了算法擴展的瓶頸［6］；有研究人員在MPI并行環境的基礎上，使用進程間通信的方式協調并行計算，結果計算效率較低，內存開銷大，并且不能夠實現多節點的橫向擴展［7－8］；為了在某種程度上降低并行計算時的通信消耗，鄒翔等［9］提出了一種基于前綴樹的并行算法。

針對海量數據的數據挖掘問題，本文提出了一種改進FP－Growth算法。通過分布式計算框架Hadoop的MapReduce編程模式對改進FPGrowth算法的各個步驟并行化［10］，不僅提高了挖掘效率，而且有效地解決了內存不足的問題，并針對算法在挖掘FP－Tree中產生大量的頻繁項集的問題，提出了在挖掘過程中發現閉項集就對搜索空間進行剪枝的方法。

1 FP－Growth算法

Apriori算法是關聯規則模式挖掘的經典算法，其尋找最大項集的基本思想是：算法需要進行多個步驟處理數據集。第1步，簡單統計所有含有1個元素的項集出現的頻率，并找出不小于最小支持度的項集。第2步，開始數據處理直到再沒有最大項集生成［11－13］。Apriori算法在數據量較小的情況下能夠大大壓縮候選閉頻繁項集的大小，但是由于它需要反復訪問事務數據庫，并且在對長模式挖掘時會產生大量的候選項集。針對Apriori算法的I／O頻繁訪問和存儲空間大的主要性能瓶頸，提出了FP－Growth算法來減少全量掃描事務數據庫的次數，并且不產生候選項集［14－15］。FP－Growth算法使用了一種稱為頻繁模式樹FP－Tree的數據結構，并直接從該結構中提取頻繁項集。FP－Tree是一種特殊的前綴樹，由頻繁項頭表和項前綴樹構成［16－17］。所謂前綴樹，是一種存儲候選項集的數據結構，樹的分支用項名標志，樹的節點存儲后綴項，路徑表示項集［18］。

假設I＝｛I1，I2，…，Im｝是項的集合。給定一個訂單數據庫ORDER，其中每個事務R是P的非空子集，即，每一個訂單都與一個唯一的標志符RID相對應，如表1所示。

表1　事務數據表Tab．1 Transaction data table

FP－Growth算法的具體步驟［19］如下。

1）第1次全量掃描事務數據庫，統計導出k＝1項集以及對應的支持度計數，并且按照支持度計算降序排序，結果記為L。支持度設置為2，則L＝｛｛P2：7｝，｛P1：6｝，｛P3：6｝，｛P4：2｝，｛P5：2｝｝。

2）再次全量掃描事務數據庫，按照每個事物中出現的頻繁項建立FP－Tree。首先創建樹的根節點，記為root。處理每條事務數據按照L頻繁項集添加到FP－Tree中的一個分支。

①掃描訂單R100的事務“P1，P2，P5”，按照L中的順序將該事務進行排序為“P2，P1，P5”，構造FP－Tree的第1個分支，如圖1所示。

圖1　事務R100數據形成的FP－TreeFig．1 FP－Tree built from R100transaction data

②掃描訂單R200“P2，P4”，排序為“P2，P4”，與R100共享節點｛P2｝，因此將樹中節點｛P2｝的計數加1，同時在｛P2｝節點上創建一個｛P4：1｝的分支，如圖2所示。

圖2　事務R200數據形成的FP－TreeFig．2 FP－Tree built from R200transaction data

③以此類推，將事務數據庫中的所有訂單都添加到FP－Tree中。

如此，遍歷整個事務數據庫，每條訂單數據排序，創建對應的路徑，但是，如果創建路徑時遇到相同的節點，該節點計數就增加1。為了使形成的FP－Tree能夠方便被遍歷，創建一個項頭表，表的字段項為ID、支持度計數、節點鏈。所以，經過上述建立FP－Tree的過程，最終FP－Tree結構如圖3所示。

圖3　存儲頻繁模式信息的FP－TreeFig．3 FP－Tree of store frequent patterns information

FP－Growth算法最后一步為挖掘FP－Tree。挖掘過程如下：遍歷L頻繁項集，構建每個項的條件模式基（即子數據庫），通過它的前綴路徑來構建條件FP－Tree樹，根據項頭表至底向上遞歸挖掘，鏈接后綴模式與條件FP－Tree生成的頻繁模式為最終的頻繁項集。表2為FP－Tree挖掘過程的總結。

表2　FP－Tree挖掘過程Tab．2 FP－Tree mining process

綜上所述，FP－Growth算法主要分為建立FPTree和挖掘FP－Tree，從而在不產生候選項集的條件下實現頻繁項集的挖掘。同時，把數據壓縮成樹形結構，大大減少了存儲空間。傳統FP－Growth算法有分治策略，為下面提出的分布式計算提供了可能。

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

傳統的FP－Growth算法有如下優點：具有分治策略，可以分解挖掘任務或事務數據庫；不需產生候選項集，并且產生樹形結構，大大減少了存儲空間；不需要反復掃描數據庫，降低了I／O訪問，提高了性能［20］。為了優化FP－Growth算法的性能，本文采用項合并策略進行剪枝優化。

該策略定義如下：如果包含頻繁項集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，它的真超集的支持度計數都不等于它本身的支持度計數，則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的直接超集的支持度計數都不等于它本身的支持度計數。所以A是一個閉項集。由已知條件，A是一個頻繁項集，所以A是一個閉頻繁項集。A∪B＝A自然也是一個閉頻繁項集。

由于B＝A，最后不必再搜索包含A但不包含B的任何項集，命題得證。

通過項合并策略能夠大大減少搜索空間，提高挖掘頻繁樹的效率，也在很大程度上減少了頻繁項集的數量，產生少量的頻繁閉項集。

FP－Growth算法主要分為2步。

1）通過掃描整個事務數據庫，計算出L頻繁項集，并且按項的頻繁計數從大到小排序，記為L－List。再次全量查詢事務數據庫，遍歷每條事務數據，根據L－List做一次升序排序，然后創建節點名root為FP樹的根節點，按照建立FP－Tree的流程（見圖4）生成一顆完備的模式樹。

圖4　創建FP－Tree的流程圖Fig．4 Flow chart of FP－Tree establishment

2）開始挖掘上一步建立的FP－Tree，提出了項合并的策略來減少挖掘FP－Tree時產生的條件模式基，從而達到剪枝的效果。整個挖掘FP－Tree的流程如圖5所示。

挖掘FP－Tree的步驟如下。

1）自底向上的方式遍歷生成的FP－Tree的項頭表，從而得到此節點的所有前綴路徑，以此節點為后綴模式，得到FP－Tree中所有包含此節點的路徑。

2）如果上一步得到單條路徑，前綴路徑的每個元素和后綴模式合并生成頻繁項集。否則，需找前綴路徑中是否存在項合并策略中的情況，若存在，剪枝后合并。

圖5　改進的挖掘FP－Tree的流程圖Fig．5 Flow chart of improved mining FP－Tree

3）以上述得到的路徑作為新的數據庫，重新按照創建FP－Tree的流程創建一棵新的FP－Tree，但是此時樹的根節點為后綴模式，即挖掘的項。

4）把生成的樹作為第1步輸入數據源，反復迭代，直到最后只生成1條路徑。

通過上述過程，整個FP－Tree挖掘的過程結束，挖掘出來的頻繁項集都是閉頻繁項集。整個過程對搜索閉項集的空間做了相應的優化，減少了樹的路徑，從而提高了算法的計算速度。

3 基于Hadoop的并行FP－Growth實現

面對大規模數據集，傳統的FP－Growth計算的速度有所降低，雖然有研究人員提出多線程的方式來緩解計算數據的壓力，但是當數據量達到一定程度時，單臺計算機的內存限制成為FP－Growth算法的瓶頸。為了更好地解決單機版FP－Growth算法存在的各種問題，利用Hadoop自身處理大數據的各種優勢，本研究提出基于分布式計算框架Hadoop并行計算的FP－Growth算法，很好地解決了傳統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）統計L頻繁項集

統計L頻繁項集是并行算法的第1步。該步驟的主要任務是統計每個項在數據庫中出現的次數，并且過濾出現次數小于設置的最小支持度的項，再把剩余的項通過出現的次數進行降序排序，最終得到L－List集合。其中L－List集合中不僅存儲了項的唯一標志，而且也存儲了項出現的頻率，即項的計數。

統計L項集的具體處理步驟。

①Map過程：第1次全量掃描事務數據庫，輸入的key為每行的偏移量，value為每條事務數據。針對value的值進行分割后，輸出的key為每個項，value為每個項首次出現的計數為1。

②Combiner過程：在集群的每個節點上本地化的對每個項進行1次相加統計，輸出的key依舊是項，value變為本節點上項出現的次數，即計數。此過程提高了計算性能。

③Reduce過程：收集Map階段輸出的中間結果，統計每個項在整個事務數據庫中出現的頻率。輸出的key為項的標志符，value為數據中出現的頻率。圖7是統計L項集的數據樣式圖。

圖7　L項集的數據樣式圖Fig．7 Data style figure of Litemsets

統計L頻繁項集階段得出的結果就是整個數據庫的1頻繁項集。通過每個項的計數由高到低排序后，就形成了L－List集合，并且把L－List集合存入Hadoop的分布式緩存，如此在整個集群中可以共享該文件，從而方便事務數據庫分發數據，減少相應的I／O操作。為了達到每組數據的平衡和獨立，利用L－List集合中的L項進行分組。

2）并行FP－Growth

圖8為并行FP－Growth算法的實現步驟。通過圖8可知，并行FP－Growth算法的具體過程如下。

分組和Map過程：將分布式緩存中的L－List集合存入Map中，并且對項對應的一個編號進行映射，記為i。第2次全量訪問事務數據庫，遍歷每條事務數據中的項，通過L－List表中的L頻繁項集得到一個組標志符（記為變量g），從而得到了G－List集合。

圖8　并行FP－Growth算法的過程圖Fig．8 Process chart of the parallel FP－Growth algorithm

其中，分組策略首先要得到每組中項的個數，記為m。

式中：m為每組中項的個數；｜F｜為L－List集合的模，即集合中項的個數；n為設定的組數。

如果式（1）不能整除，m就加上1取整數。

遍歷每條事務數據中的項，依照L－List集合，先做1次排序，然后在映射表中找到項的映射數字，即i。這樣，此項每組標志符計算公式如式（2）所示：

式中：g為此項將分入的組號；i為項在L－List集合中的排序號；m為每組中項的個數。

通過上述策略找到每個項對應的組，聚合每個組，從而得到G－List集合。

Map過程：在此Map階段輸出的key值為g，value為整條數據的子項集（事務序列P的子序列）。這樣分組不僅均衡了整個數據庫的投影數據，同時保證了挖掘過程中數據的完備性。

Combiner過程：本地聚合每組中的事務數據，形成壓縮的事務數據。

Reduce過程：此階段是整個算法中關鍵的一步，也是并行FP－Growth算法中具體對數據挖掘的一步，是在集群節點上運行本地化的本文改進的FP－Growth算法，但數據已不是整個事務數據庫，而是子數據庫。先建立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次排序并且選取頻繁項集共同出現的頻率最大的K項頻繁項集。

Reduce過程：收集Combiner過程產生的局部最大的K項頻繁項集，再次做排序，選取整個數據庫中計數最大的K項閉頻繁項集。

至此，整個分布式的FP－Growth算法完成。縱觀整個分布式算法實現過程，其實是MapReduce編程模式的完美體現。這個過程清晰，但是在每一步的關鍵部分是被封裝的，如果對一些策略要進行性能上的提升，可通過Hadoop中MapReduce計算框架的參數設定來實現性能的調優。

為了性能的提升和計算速率的提高，在整個過程中運用了分布式緩存和本地化聚合等策略。分布式的改進FP－Growth算法在處理大量的數據時速度有明顯提升，這也是整個分布式計算框架最大的特性。但在處理小數據方面花費的時間要長些，所以在實現分布式的同時也為本地算法提供了具體的API，這樣不僅能通過內存算法來計算小量數據，同時也可以利用并行算法來計算大規模的數據。

4 實驗過程與結果

為了驗證提出改進的FP－Growth算法性能，利用mushroom．dat數據來進行驗證實驗。mushroom．dat數據來自于Frequent Itemset Mining Data Repository［22］。實驗通過FP－Growth算法和改進的FP－Growth算法在相同的最小支持度下挖掘同一份數據的速率來做比較，其中結果的橫坐標數值為支持度閾值，那么最小支持度為整個mushroom．dat數據中包含的事務數據條數乘于支持度閾值，即min＿support＝transactions．number＊threshold。圖10為該實驗的比較圖。

圖10　挖掘速率比較圖Fig．10 Mining rate comparison chart

從圖10中可以看出，改進的FP－Growth算法在計算速度上有明顯提高，性能較好。說明通過項合并的策略減少了搜索FP－Tree的迭代次數，實現了對搜索空間的剪枝。隨著閾值的變大，相應的最小支持度計數也變大，從而得到的頻繁項集的總量在減少，搜索代價也隨之降低，所以改進的FPGrowth算法和FP－Growth算法在挖掘速度上很接近。因此，改進的FP－Growth算法挖掘出來的閉頻繁項集數量遠遠少于總量的頻繁項集。

驗證實驗的挖掘速度隨著數據量的增加，挖掘速度急劇下降，到一定程度就會內存溢出。為了測試分布式改進的FP－Growth算法對大規模數據量處理能力是否提升，改進實驗的數據為訂單數據，此數據量最大為10 000萬條。其中本實驗所采用的分布式計算環境包含master，slave1，slave2，slave3 共4個節點的Hadoop集群，其中每個節點為Inter XEON Pcs（E3－1220LCPU，32GB RAM），Hadoop版本為Hadoop1．2。該實驗分別從2方面來做測試。

為了反映各個數據量下分布式算法的計算速度，分別選取了10萬數量級中10萬和50萬，100萬數量級中100萬和500萬，1 000萬數量級的1 000萬，3 000萬，5 000萬，7 000萬和10 000萬。實驗結果如圖11所示。

圖11　數據量與計算速率的折線圖Fig．11 Line chart of data volume and computing rate

為了展示在同樣數量級的數據中挖掘最大的K項頻繁項集花費的時間情況，選取了K＝3，5，8，10和12項頻繁項集。實驗顯示每一步的CPU計算時間的情況，使得結果更加清晰，實驗結果如圖12所示。

圖12　K項與計算速率的折線圖Fig．12 Line chart of Kand computing rate

通過實驗可知：在不同數量級下基于分布式的改進FP－Growth算法的計算時間是不同的，首先是第1步在數據集的規模劇增時花費的時間相對緩慢，其次是第3步，最后是第2步，其是整個分布式算法當中最為關鍵的一步，也是最消耗時間的一步，這步的計算任務是非常繁重的，但在大規模數據下消耗的時間是可以接受的。至少不會出現單機運行大規模數據時出現內存溢出的情況。

實驗說明了在挖掘不同最大K項頻繁項集時花費的時間差距是不大的，每一步花費的時間都比較緩慢。說明分布式算法充分利用了集群的性能和內存空間，能夠很好地完成大規模數據的頻繁項集挖掘。

5 結 語

改進的FP－Growth算法在性能上有著明顯提升，主要原因是在挖掘FP－Tree的時候通過項合并的策略來剪枝，大大減少了挖掘樹迭代的次數。同時，生成的閉頻繁項集相對于頻繁項集的總量小了很多，減少了需在內存中占用的空間。此外，分布式改進的FP－Growth算法在處理大規模的數據量時有相當大的優勢，分而治之的策略充分利用了集群的資源來實現單機無法達到的結果。

參考文獻／References：

［1］ 付冬梅，王志強．基于FP－tree和約束概念格的關聯規則挖掘算法及應用研究［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］ 何月順．關聯規則挖掘技術的研究及應用［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算法的研究與實現［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］ 鄒翔，張巍，劉洋，等．分布式序列模式發現算法的研究［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］馮漢超，周凱東．分布式系統下大數據存儲結構優化研究［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］任家東，王倩，王蒙．一種基于頻繁模式有向無環圖的數據流頻繁模式挖掘算法［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的頻繁項集發現算法［J］．計算機技術與發展，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算法的實現方法研究［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］．計算機系統應用，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．數據挖掘：概念與技術［M］．第3版．范明，孟小峰譯．北京：機械工業出版社，2013．

［22］ANONYMOUS．Frequent Itemset Mining Dataset Repository ［EB／OL］．http：／／fimi．ua．ac．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—），男，河北唐山人，副教授，碩士，主要從事數據庫及其應用方面的研究。

收稿日期：2015－11－11；修回日期：2015－12－30；責任編輯：陳書欣

文章編號：1008－1534（2016）02－0169－09

中圖分類號：TP311．1

文獻標志碼：A

doi：10．7535／hbgykj．2016yx02013