朱文飛　齊建東　洪劍珂

(北京林業(yè)大學(xué)信息學(xué)院　北京 100083)

?

Hadoop下負(fù)載均衡的頻繁項集挖掘算法研究

朱文飛齊建東洪劍珂

(北京林業(yè)大學(xué)信息學(xué)院北京 100083)

摘要頻繁項集挖掘FIM(Frequent Itemsets Mining)是關(guān)聯(lián)規(guī)則挖掘算法的重要組成部分。而經(jīng)典Apriori和FP-Growth算法在海量數(shù)據(jù)處理時面臨內(nèi)存占用、計算性能等方面的瓶頸?；贖adoop云計算平臺，提出適用大數(shù)據(jù)處理的頻繁項集挖掘HBFP(High Balanced parallel FP-growth)算法，設(shè)計后綴模式轉(zhuǎn)換的數(shù)據(jù)分割及均衡任務(wù)分組方案，使計算節(jié)點本地?fù)碛杏嬎闼蕾嚨臄?shù)據(jù)，實現(xiàn)不同節(jié)點相互獨立的并行數(shù)據(jù)挖掘方法，并保證算法全局的負(fù)載均衡特性。實驗數(shù)據(jù)表明，HBFP算法能均勻地將計算量分散至不同計算節(jié)點，并行且相互獨立地進(jìn)行FP-Growth挖掘過程，算法效率提高了約12%，算法全局穩(wěn)定性及效率取得提升。

關(guān)鍵詞頻繁項集挖掘FP-Growth算法Hadoop并行計算

0引言

關(guān)聯(lián)規(guī)則挖掘是通過對大數(shù)據(jù)集數(shù)據(jù)分析發(fā)掘潛在數(shù)據(jù)關(guān)聯(lián)特性的過程，主要由頻繁項集挖掘和關(guān)聯(lián)規(guī)則生成兩個階段組成。前者對大規(guī)模數(shù)據(jù)集進(jìn)行挖掘計算，后者則根據(jù)頻繁項集生成目標(biāo)規(guī)則。其中，頻繁項集挖掘算法是影響關(guān)聯(lián)規(guī)則質(zhì)量和算法效率的主要因素。關(guān)聯(lián)規(guī)則挖掘中的頻繁項集算法可分為搜索算法、層次算法、數(shù)據(jù)集劃分算法、抽樣算法等[1]。最早關(guān)注關(guān)聯(lián)規(guī)則挖掘的Agrawal等人于1994年提出Apriori算法[2]。其多次掃描、建立候選集的特性導(dǎo)致算法具有I/O吞吐量大、內(nèi)存占用量隨數(shù)據(jù)集增大而驟升的先天缺陷。Han等人提出FP-Growth算法[3]規(guī)避大量候選集引發(fā)的內(nèi)存占用問題，采用FP-Tree結(jié)構(gòu)壓縮原始數(shù)據(jù)集。通過兩次數(shù)據(jù)掃描及FP-Growth的遞歸調(diào)用完成整個數(shù)據(jù)挖掘過程，算法執(zhí)行效率及空間復(fù)雜度均有較大改進(jìn)。

隨著數(shù)據(jù)規(guī)模的不斷膨脹，數(shù)據(jù)集大小呈指數(shù)級增長，大規(guī)模數(shù)據(jù)下的數(shù)據(jù)挖掘具有其特殊性，頻繁項集挖掘中多種算法受數(shù)據(jù)規(guī)模的影響具有較大的性能差異。改進(jìn)Apriori和FP-Growth的算法[4-6]圍繞分治與并行化設(shè)計方案，對算法在大數(shù)據(jù)應(yīng)用方面進(jìn)行探索。Pruned FP[7]及FPMFI[8]通過構(gòu)建條件FP樹的優(yōu)化剪枝策略，減少算法遞歸次數(shù)，提升算法效率，但算法對數(shù)據(jù)平衡分組未展開詳細(xì)描述。Li等人提出了FP-Growth并行算法PFP[9]，在MapReduce框架下將數(shù)據(jù)集和計算任務(wù)分配至不同計算節(jié)點中，在云計算平臺下實現(xiàn)大數(shù)據(jù)下頻繁項集挖掘。PFP改進(jìn)算法[10,12]對原始PFP算法進(jìn)行優(yōu)化，通過改進(jìn)數(shù)據(jù)分組方式及構(gòu)建局部頻繁模式樹提高算法效率及適用性。ABH算法[13]利用數(shù)組隨機(jī)存儲的效率改進(jìn)FP樹結(jié)構(gòu)，在Hadoop平臺下有效減少了候選集規(guī)模，從而改進(jìn)算法效率。文獻(xiàn)[14]中分布式FP-Growth的動態(tài)任務(wù)分配原則試圖滿足任務(wù)分配的公平性，但由于未考慮不同任務(wù)間計算量差異，節(jié)點計算量分配具有不同程度的波動性。

面向大數(shù)據(jù)處理的FIM算法通過在云計算框架下實現(xiàn)數(shù)據(jù)的特征提取與數(shù)據(jù)挖掘工作，而其中分布式計算正確性、公平性方面仍有諸多疑問亟需解決。因此本文提出的HBFP算法在Hadoop平臺通過數(shù)據(jù)分割、計算量預(yù)估及任務(wù)均衡化分類策略實現(xiàn)計算任務(wù)在分布式環(huán)境的負(fù)載均衡，解決并行算法中計算分配的公平性問題，保證計算結(jié)果的正確性，改進(jìn)海量數(shù)據(jù)中頻繁項集挖掘算法的性能表現(xiàn)。

1相關(guān)概念及描述

設(shè)集合I={I1,I2,…,In}，數(shù)據(jù)事務(wù)集D={T1,T2,…,Tt}由多條事務(wù)Ti組成，每條事務(wù)為多個項Ii的集合，存在Ti?I。

定義2若存在項的集合I，滿足support(I)>Thresh，其中Thresh為支持度閾值，則稱該項集I為頻繁項集；當(dāng)集合包含k個元素，稱其為頻繁k項集，記為Lk。

定義3候選集Ck表示k項元素組成事務(wù)的所有集合。

定義4項Ik的條件模式基表示樹結(jié)構(gòu)中所有Ik元素至根節(jié)點的前綴路徑組成的集合，不含節(jié)點Ik本身。

Apriori性質(zhì)[2]任意頻繁項集的非空子集必為頻繁項集，稱為向下封閉性；非頻繁項集的超集必不是頻繁項集。

基于FP的算法依賴于FP-Tree的壓縮結(jié)構(gòu)保存原始事務(wù)數(shù)據(jù)，隨著數(shù)據(jù)集的不斷增加，當(dāng)數(shù)據(jù)量到達(dá)一定規(guī)模后，形成的FP-Tree的規(guī)模將不再擴(kuò)大，本文稱其為滿FP樹。

滿FP樹(Full FP-Tree)：將I={I1,I2,…,In}中項的所有組合構(gòu)成的項集作為輸入構(gòu)建出來的FP樹。

定理1滿FP樹中蘊含的事務(wù)總數(shù)為2n-1，滿FP樹中非根節(jié)點數(shù)量亦為2n-1。

(1)

由文獻(xiàn)[3]可得FP樹中包含所有輸入事務(wù)的數(shù)據(jù)，則滿FP樹中包含事務(wù)總數(shù)為2n-1。

在滿FP樹中從任一非根節(jié)點出發(fā)，回溯至根節(jié)點的路徑即為一條事務(wù)，從所有節(jié)點回溯至根節(jié)點的路徑為該樹結(jié)構(gòu)中蘊含的所有事務(wù)。設(shè)滿FP樹中節(jié)點數(shù)量為Nnodes，則Nnodes=Nitemsets，可得滿FP樹中非根節(jié)點數(shù)量為 2n-1。

定理2當(dāng)輸入事務(wù)數(shù)據(jù)達(dá)到一定規(guī)模，F(xiàn)P樹轉(zhuǎn)變?yōu)闈MFP樹，新的數(shù)據(jù)輸入不會改變FP樹規(guī)模，稱滿FP樹具有穩(wěn)定性。

2Hadoop下均衡FP-Growth算法HBFP設(shè)計

HBPF算法采用Hadoop的任務(wù)調(diào)度機(jī)制，實現(xiàn)節(jié)點多任務(wù)的優(yōu)化調(diào)度。同時引入任務(wù)計算量預(yù)估及分配模式模型，實現(xiàn)不同任務(wù)的計算量均衡分配。基于短板效應(yīng)的數(shù)據(jù)獨立分組策略進(jìn)一步保證全局算力的均衡分布。主要需解決的問題為分布式計算中如何分配數(shù)據(jù)以確保計算公平性、如何設(shè)計分布式計算模型以保證計算正確性及如何實現(xiàn)全局計算的負(fù)載均衡特性等，下面對算法分步驟展開描述。

步驟一數(shù)據(jù)集分布式存儲，該步驟合理數(shù)據(jù)預(yù)處理是后續(xù)算法并行高效執(zhí)行的基礎(chǔ)。

步驟二頻繁1項集計算，MapReduce任務(wù)通過單次數(shù)據(jù)集掃描實現(xiàn)所有項的并行化計數(shù)統(tǒng)計。

步驟三據(jù)頻繁1項集對原始數(shù)據(jù)進(jìn)行修剪、重排，基于“后綴模式轉(zhuǎn)換”將原始數(shù)據(jù)分割為節(jié)點獨立計算所依賴的子事務(wù)集合。這是節(jié)點進(jìn)行獨立數(shù)據(jù)挖掘并保證結(jié)果正確性的基礎(chǔ)。

步驟四提出任務(wù)計算量的預(yù)估模型，并基于計算估值采用短板效應(yīng)策略實現(xiàn)任務(wù)分組的均衡化分配。該步驟是實現(xiàn)計算任務(wù)保證計算公平性的重要步驟，最大程度保證全局負(fù)載的均衡特性。

步驟五分布式節(jié)點針對特定的項進(jìn)行節(jié)點獨立的FP-Growth運算，該步驟中節(jié)點使用步驟四中分配至該節(jié)點的項關(guān)聯(lián)數(shù)據(jù)子事務(wù)完成本地數(shù)據(jù)計算，保證了結(jié)果正確性。

步驟六匯聚各節(jié)點不同項的頻繁項集，將所獲得的大量頻繁項集進(jìn)行排序篩選，獲取關(guān)聯(lián)特性最強的前N條頻繁項集。

2.1數(shù)據(jù)集分布式存儲

分布式計算中原始數(shù)據(jù)集被切分為多個子數(shù)據(jù)集，Hadoop平臺HDFS文件系統(tǒng)默認(rèn)以64 MB為單位分配數(shù)據(jù)至不同節(jié)點。而大量小文件的數(shù)據(jù)處理時應(yīng)利用CombineFileInputFormat類進(jìn)行數(shù)據(jù)預(yù)處理，合并小數(shù)據(jù)可提高分布式存儲效率[15]。數(shù)據(jù)分布式存儲的物理切分過程稱為分塊操作。

Map任務(wù)數(shù)量是計算并行化程度的直接表征，由Hadoop中InputFormat決定，而每個Map實際輸入數(shù)據(jù)量由式(2)確定：

SplitSize=max(minSize,min(goalSize,blockSize))goalSize=totalSize/mapred.map.tasks

(2)

minSize由mapred-site.xml中mapred.min.split.size設(shè)置，goalSize由輸入文件大小和map數(shù)量計算所得，blockSize由hdfs-site.xml中dfs.block.size設(shè)置。上述操作輸出鍵值對作為后續(xù)程序數(shù)據(jù)輸入，為并行化計算做分布式存儲準(zhǔn)備，該過程稱為分片操作。

通過數(shù)據(jù)分塊和分片操作，大數(shù)據(jù)集分布式存儲在多個存儲節(jié)點中。

2.2頻繁1項集計算

頻繁1項集計算可以歸類為并行化計數(shù)統(tǒng)計，這是典型MapReduce任務(wù)。Map以數(shù)據(jù)分片作為輸入，完成數(shù)據(jù)讀取任務(wù)，輸出結(jié)果為形式鍵值對，經(jīng)Shuffle階段完成相同項的聚集和分發(fā)，Reduce以形式數(shù)據(jù)作為輸入，統(tǒng)計輸出項對應(yīng)的頻次。該步驟額外完成對數(shù)據(jù)集所有項的統(tǒng)計，將其按頻次降序排列并去除不滿足支持度的項后，序列記為F_List。

利用2.1節(jié)中分片及Map任務(wù)數(shù)量優(yōu)化配置，并行計算的效率將提高，算法空間及時間復(fù)雜度均為O(DB_Shardingsize)。其中DB_Shardingsize為單節(jié)點中分片數(shù)據(jù)量。

2.3修剪重排與數(shù)據(jù)分組

算法1后綴模式轉(zhuǎn)換算法

輸入：事務(wù)數(shù)據(jù)Ti，輔助記錄表RecordList

輸出：各項關(guān)聯(lián)的子事務(wù)數(shù)據(jù)

Procedure: SegmentTask (key, value=Ti)

//修剪、重排

(2)items[] = Split(Ti)

(3)for i=0 to items.length -1 do

//事務(wù)分割

(4)if (RecordList.isEmpty == FALSE) then

(5)Output(< items [i], RecordList >)

(6)end

(7)RecordList.add(items [i])

(8)end

算法1正確性分析：頻繁項集挖掘最終結(jié)果中，有序排列頻繁項集若包含某項s，僅且存在兩種情況：一類為s是頻繁項的后綴，形如<…，s>；一類為s是頻繁項非后綴，形如<…,s,…>。而對于一條原始事務(wù)記錄而言，其按照后綴模式轉(zhuǎn)換后與s相關(guān)的信息均包含在{s,}及{v,}這兩條子事務(wù)記錄中，不同子事務(wù)按照2.4節(jié)及2.5節(jié)分配至不同節(jié)點進(jìn)行計算，經(jīng)2.6節(jié)完成匯聚后結(jié)果一致，算法正確性得以保證。

經(jīng)Hadoop的Shuffle處理后具有相同key的子事務(wù)將匯聚至同一個Reduce節(jié)點處理，從而該節(jié)點獲取所有以key為后綴的子事務(wù)分組記錄。事務(wù)修剪重排與數(shù)據(jù)分組建立過程包括：修剪與重排、事務(wù)分割、事務(wù)分組建立，該過程如圖1所示。

圖1　事務(wù)修剪重排與分組建立過程

2.4計算量預(yù)估與均衡化分組

獲取數(shù)據(jù)集中每個項的頻繁項所需的精確計算量較為復(fù)雜，BPFP算法[10]依據(jù)F_List中項e所在的位置進(jìn)行頻繁項集挖掘所需計算量Cost(e)的估值為：

Cost(e)=Log(P(e,F_List))

(3)

這種估值方式是利用所有項頻次的匯總數(shù)據(jù)進(jìn)行粗略估計。本文通過利用事務(wù)分組中項的位置信息進(jìn)行計算量估值，從而在不增加計算的情況下，獲取更精確的計算量預(yù)估信息。如由分組信息v,{,}，可確定位置信息為P(e,T)={5,4}，據(jù)式(4)進(jìn)行該項的計算量Cost(e)的估值計算，其中P(e,Ti)為數(shù)據(jù)事務(wù)Ti中e的位置，n為包含e的數(shù)據(jù)事務(wù)總數(shù)，將F_List按此估值降序排列為Cost_List。

(4)

事務(wù)分組建立后，為滿足計算均衡化分配，據(jù)計算量估值進(jìn)行分組歸類。假設(shè)計算節(jié)點數(shù)為N，則建立分組記錄表gListN，表中每個分組對應(yīng)一個計算節(jié)點計算所需要的分組數(shù)據(jù)?；诙贪逍?yīng)的事務(wù)分組機(jī)制為：先取Cost_List中前N項保存至gListN，將分組列表中各項的計算量之和作為該分組的計算估值；遍歷Cost_List中其余各項，并依次加入gListN中計算估值最小的列表，更新對應(yīng)分組的計算估值。該過程為基于短板效應(yīng)負(fù)載均衡模型，最大程度實現(xiàn)了各節(jié)點分配計算任務(wù)的均衡化，其偽碼描述為算法2。

算法2短板效應(yīng)均衡算法

輸入：按計算量估值降序排列的列表Cost_List，計算節(jié)點數(shù)N，分組記錄表gList

輸出：分組任務(wù)列表gList

Procedure: TaskSplit (Cost_List, N, gList)

(1)for i = 0 to N-1 do

(2)gList(i).add(Cost_List(i))

(3)gList (i).cost += Cost_List(i).cost

(4)end

(5)for i = N to F_List.length -1 do

(6)minNode = findMin(gList)

(7)minNode. add(Cost_List(i))

(8)minNode. cost +=Cost_List(i). cost

(9)end

2.5節(jié)點獨立的FP-Growth運算

數(shù)據(jù)分組機(jī)制使得節(jié)點獲取到與項相關(guān)的所有子事務(wù)數(shù)據(jù)。事務(wù)數(shù)據(jù)分組以作為輸入，節(jié)點據(jù)此事務(wù)分組局部構(gòu)建條件FP樹，并遞歸調(diào)用FP-Growth算法[3]進(jìn)行各項關(guān)聯(lián)的頻繁項集挖掘。

受均衡分組機(jī)制的作用，Reduce節(jié)點會收到不同項的事務(wù)分組，在Hadoop的Shuffle機(jī)制下，多個分組將依次有序輸入。當(dāng)新輸入事務(wù)的key發(fā)生變化時，對已建立的FP樹進(jìn)行條件FP樹挖掘，計算完成則獲得其頻繁項集，清空FP樹，開始新項的FP樹建立及頻繁項集挖掘，該過程如圖2所示。

圖2　分類事務(wù)的頻繁項集挖掘

分布式節(jié)點獲取的項關(guān)聯(lián)的子事務(wù)數(shù)據(jù)也就是完整事務(wù)數(shù)據(jù)建立FP樹后該項對應(yīng)的條件模式基，而在數(shù)據(jù)集龐大的前提下是無法進(jìn)行完整FP樹構(gòu)建。通過“后綴模式轉(zhuǎn)換”操作將事務(wù)分割，節(jié)點級建立條件FP樹、進(jìn)行條件FP樹的挖掘，最終實現(xiàn)分而治之的分布式挖掘。

根據(jù)滿FP樹定理2，當(dāng)數(shù)據(jù)量不斷擴(kuò)充時，節(jié)點本地FP規(guī)模將趨于穩(wěn)定。設(shè)節(jié)點本地FP樹建立后頭節(jié)點數(shù)量為m，據(jù)滿FP樹定理1，則FP樹中節(jié)點數(shù)量最大為2m-1。由此可得構(gòu)建此FP樹的空間復(fù)雜度為O(2m)，挖掘算法的時間復(fù)雜度應(yīng)小于O(m×2m)。

2.6結(jié)果匯聚

分布式節(jié)點中FP-Growth的輸出結(jié)果形如,Num}>，為使得最終挖掘結(jié)果意義清晰，該匯聚過程再進(jìn)行一組MapReduce操作。Map以2.5的輸出作為輸入，輸出形式為,Num}>的運算結(jié)果。Reduce中對項e進(jìn)行排序操作后將項集ItemSets有序輸出，為最終滿足支持度閾值要求的頻繁項集。

3實驗分析

3.1參數(shù)設(shè)定

實驗集群由九臺高性能計算機(jī)組成，包含1臺管理節(jié)點，8臺計算節(jié)點，節(jié)點配置為Intel?CoreTMi7-3770 CPU @ 3.40 GHz型號CPU、4 GB內(nèi)存、Intel?Q77主板，系統(tǒng)采用Ubuntu 14.04，Hadoop版本0.23，環(huán)境中參數(shù)設(shè)定及變量定義如表1所示。數(shù)據(jù)集的元數(shù)據(jù)采用http://fimi.ua.ac.be/data/的retail.data，并以此擴(kuò)展事務(wù)數(shù)為105，2×105，4×105，8×105四個級別的測試數(shù)據(jù)集，記為{D1,D2,D3,D4}。各測試數(shù)據(jù)集的特征統(tǒng)計信息如表2所示，其中數(shù)據(jù)集D1的詳細(xì)數(shù)據(jù)頻次分布如圖3所示。

表1　仿真實驗參數(shù)設(shè)定

表2　數(shù)據(jù)集的特征統(tǒng)計信息

圖3　數(shù)據(jù)集D1中項的頻次分布情況

3.2結(jié)論分析

算法HBFP在不同數(shù)量級事務(wù)數(shù)據(jù)庫下不同數(shù)量計算節(jié)點的關(guān)聯(lián)規(guī)則挖掘性能表現(xiàn)如圖4所示。橫軸為分布式計算節(jié)點數(shù)量，縱軸表示計算完成的時間。隨計算節(jié)點的增加算法完成時間減少的整體表現(xiàn)與Hadoop分布式計算框架中多節(jié)點并行計算的性能優(yōu)勢相吻合。當(dāng)計算數(shù)據(jù)量并不龐大時，分布式框架的任務(wù)分配與啟動時間相較于計算時間不可忽視，這將導(dǎo)致計算節(jié)點的增加并不會使得計算性能的顯著提升。這是由分布式平臺特性決定的，即分布式算法在大規(guī)模的數(shù)據(jù)計算中性能提升更加顯著。

圖4　HBFP算法在不同樣本量及計算節(jié)點數(shù)量下的運算

PFP算法[9]是MapReduce下的FP-Growth分布式設(shè)計方案，并在Mahout開源項目進(jìn)行實現(xiàn)。圖5顯示了在同等配置下PFP算法與本文提出的HBFP算法在不同計算節(jié)點的執(zhí)行時間，橫軸表示不同的計算節(jié)點，縱軸表示節(jié)點算法執(zhí)行時間(單位：分鐘)。PFP算法隨機(jī)任務(wù)分配機(jī)制使得在不同節(jié)點任務(wù)完成時間差別較大，圖中2號節(jié)點與5號節(jié)點的完成時間相差幾倍；HBFP算法利用各分組的任務(wù)計算量預(yù)估信息進(jìn)行任務(wù)分配,使得各節(jié)點任務(wù)執(zhí)行時間基本在6分鐘左右。并行任務(wù)的完成時間由各節(jié)點中的最大完成時間決定，數(shù)據(jù)顯示HBFP算法的FP-Growth階段的總體完成時間比PFP快近12%，HBFP算法中各節(jié)點執(zhí)行任務(wù)時間相近，證明任務(wù)分配更加均衡。

圖5　不同節(jié)點任務(wù)執(zhí)行時間差異

(5)

圖6中橫軸表示支持度閾值(單位：%)，縱軸表示任務(wù)執(zhí)行時間的標(biāo)準(zhǔn)差，對比了在三種分布式算法(PFP、BPFP[10]、HBFP)中節(jié)點任務(wù)分配均勻度情況。由于PFP算法任務(wù)分配并未計算不同任務(wù)量的差異，支持度閾值較小時計算任務(wù)量龐大，任務(wù)分配不均勻?qū)е氯蝿?wù)執(zhí)行時間標(biāo)準(zhǔn)差較大；支持度閾值增大時，計算任務(wù)量相應(yīng)減少，由任務(wù)分配不均而導(dǎo)致的節(jié)點執(zhí)行時間差異縮小，標(biāo)準(zhǔn)差趨于減小。BPFP算法利用項的頻次信息進(jìn)行計算量估值的方式一定程度上縮小了計算節(jié)點間的任務(wù)量差異，但存在支持度閾值變化導(dǎo)致任務(wù)分配不均的情況。HBFP算法的短板效應(yīng)均衡算法使得各節(jié)點的任務(wù)執(zhí)行時間基本分布在平均值左右，受支持度閾值影響最小。但也需指出HBFP算法存在隨著支持度閾值增大任務(wù)分配均衡性變差，這是由于計算任務(wù)數(shù)量減少可分配任務(wù)的粒度增大，從而導(dǎo)致均衡分組特性有所下降。

圖6　不同支持度閾值下的節(jié)點任務(wù)執(zhí)行時間標(biāo)準(zhǔn)差

4結(jié)語

本文對大數(shù)據(jù)規(guī)模下的頻繁項集挖掘提出負(fù)載均衡的并行設(shè)計方案，進(jìn)一步優(yōu)化計算分布的均衡化，實現(xiàn)全局計算效率的提升。實驗結(jié)果表明，在大規(guī)模數(shù)據(jù)下的頻繁項集挖掘中HBFP算法具有良好的適用性。文中研究的匯聚節(jié)點僅為單一節(jié)點，在數(shù)據(jù)量異常龐大時會面臨匯聚緩慢的性能瓶頸，未來需對此進(jìn)一步擴(kuò)展研究。

參考文獻(xiàn)

[1] 朱紹文,王泉德,黃浩,等.關(guān)聯(lián)規(guī)則挖掘技術(shù)及發(fā)展動向[J].計算機(jī)工程,2000,26(9):4-6.

[2] Agrawal R,Srikant R.Fast algorithms for mining association rules[C]//Proceedings of the 20th International Conference on Very Large Data Bases,Santiago:Morgan Kaufmann Publ,1994:487-499.

[3] Han J,Pei J,Yin Y,et al.Mining frequent patterns without candidate generation:A Frequent-Pattern Tree Approach[J].Data Mining & Knowledge Discovery,2004,8(1):53-87.

[4] 曾志勇,楊呈智,陶冶.負(fù)載均衡的FP—growth并行算法研究[J].計算機(jī)工程與應(yīng)用,2010,46(4):125-126.

[5] 鄭麟.一種直接生成頻繁項集的分治Apriori算法[J].計算機(jī)應(yīng)用與軟件,2014,31(4):297-301,326.

[6] 談克林,孫志揮.一種FP樹的并行挖掘算法[J].計算機(jī)工程與應(yīng)用,2006,42(13):155-157.

[7] 楊勇,王偉.一種基于MapReduce的并行FP-growth算法[J].重慶郵電大學(xué)學(xué)報:自然科學(xué)版,2013,25(5):651-657.

[8] 顏躍進(jìn),李舟軍,陳火旺.基于FP-Tree有效挖掘最大頻繁項集[J].軟件學(xué)報,2005,16(2):215-222.

[9] Li H,Wang Y,Zhang D,et al.Pfp:parallel fp-growth for query recommendation[C]//Proceedings of the 2008 ACM conference on Recommender systems,New York:ACM,2008:107-114.

[10] Zhou L,Zhong Z,Chang J,et al.Balanced parallel fp-growth with mapreduce[C]//Information Computing and Telecommunications (YC-ICT),2010 IEEE Youth Conference on,Beijing:IEEE,2010:243-246.

[11] 章志剛,吉根林.一種基于FP-Growth的頻繁項目集并行挖掘算法[J].計算機(jī)工程與應(yīng)用,2014,50(2):103-106.

[12] Vu L,Alaghband G.Novel parallel method for association rule mining on multi-core shared memory systems[J].Parallel Computing,2014,8(3):1-18.

[13] Feng S R,Ye L B,Lin Z Y.Research on Parallel Association Rules Mining Algorithm Based on Hadoop[J].Applied Mechanics and Materials,2014,543(1):3625-3631.

[14] 王智鋼,王池社,馬青霞.分布式并行關(guān)聯(lián)規(guī)則挖掘算法研究[J].計算機(jī)應(yīng)用與軟件,2013,30(10):113-115,119.

[15] 袁玉,崔超遠(yuǎn),烏云,等.單機(jī)下Hadoop小文件處理性能分析[J].計算機(jī)工程與應(yīng)用,2013,49(3):57-60.

RESEARCH ON LOAD BALANCED FREQUENT ITEMSETS MINING ALGORITHM BASED ON HADOOP

Zhu WenfeiQi JiandongHong Jianke

(SchoolofInformation,BeijingForestryUniversity,Beijing100083,China)

AbstractFrequent itemsets mining (FIM) is an important component of association rules mining algorithms. However, classical Apriori and FP-Growth algorithms face the bottleneck of memory occupation and computation performance when processing massive data. Based on Hadoop cloud computing platform, we proposed the HBFP algorithm of frequent itemsets mining applicable for big data processing, and designed the data partitioning with suffix mode conversion and the balanced tasks grouping scheme. This makes the nodes possess locally the data relyed on by the computation and realises the parallel data mining method with different nodes independent each other, and ensures the global load balancing characteristic of the algorithm. Experimental data indicated that the HBFP algorithm could distribute the calculation load to different computation node uniformly and run FP-Growth mining progress parallelly and mutual-independently. The efficiency of the algorithm raised about 12%, and the global stabilisation and efficiency of the algorithm were promoted as well.

KeywordsFrequent itemsets miningFP-GrowthHadoopParallel computing

收稿日期：2014-11-09。國家林業(yè)局重點課題(2013-05)；十二五科技支撐課題(2011BAH10B04)。朱文飛，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘。齊建東，副教授。洪劍珂，碩士生。

中圖分類號TP311

文獻(xiàn)標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.010