Hadoop下負載均衡的頻繁項集挖掘算法研究
2016-06-08 06:04:46朱文飛齊建東洪劍珂
計算機應用與軟件 2016年5期
朱文飛 齊建東 洪劍珂
(北京林業大學信息學院 北京 100083)
?
Hadoop下負載均衡的頻繁項集挖掘算法研究
朱文飛齊建東洪劍珂
(北京林業大學信息學院北京 100083)
摘要頻繁項集挖掘FIM(Frequent Itemsets Mining)是關聯規則挖掘算法的重要組成部分。而經典Apriori和FP-Growth算法在海量數據處理時面臨內存占用、計算性能等方面的瓶頸?；贖adoop云計算平臺，提出適用大數據處理的頻繁項集挖掘HBFP(High Balanced parallel FP-growth)算法，設計后綴模式轉換的數據分割及均衡任務分組方案，使計算節點本地擁有計算所依賴的數據，實現不同節點相互獨立的并行數據挖掘方法，并保證算法全局的負載均衡特性。實驗數據表明，HBFP算法能均勻地將計算量分散至不同計算節點，并行且相互獨立地進行FP-Growth挖掘過程，算法效率提高了約12%，算法全局穩定性及效率取得提升。
關鍵詞頻繁項集挖掘FP-Growth算法Hadoop并行計算
0引言
關聯規則挖掘是通過對大數據集數據分析發掘潛在數據關聯特性的過程，主要由頻繁項集挖掘和關聯規則生成兩個階段組成。前者對大規模數據集進行挖掘計算，后者則根據頻繁項集生成目標規則。其中，頻繁項集挖掘算法是影響關聯規則質量和算法效率的主要因素。關聯規則挖掘中的頻繁項集算法可分為搜索算法、層次算法、數據集劃分算法、抽樣算法等[1]。最早關注關聯規則挖掘的Agrawal等人于1994年提出Apriori算法[2]。其多次掃描、建立候選集的特性導致算法具有I/O吞吐量大、內存占用量隨數據集增大而驟升的先天缺陷。Han等人提出FP-Growth算法[3]規避大量候選集引發的內存占用問題，采用FP-Tree結構壓縮原始數據集。通過兩次數據掃描及FP-Growth的遞歸調用完成整個數據挖掘過程，算法執行效率及空間復雜度均有較大改進。
隨著數據規模的不斷膨脹，數據集大小呈指數級增長，大規模數據下的數據挖掘具有其特殊性，頻繁項集挖掘中多種算法受數據規模的影響具有較大的性能差異。改進Apriori和FP-Growth的算法[4-6]圍繞分治與并行化設計方案，對算法在大數據應用方面進行探索。Pruned FP[7]及FPMFI[8]通過構建條件FP樹的優化剪枝策略，減少算法遞歸次數，提升算法效率，但算法對數據平衡分組未展開詳細描述。Li等人提出了FP-Growth并行算法PFP[9]，在MapReduce框架下將數據集和計算任務分配至不同計算節點中，在云計算平臺下實現大數據下頻繁項集挖掘。PFP改進算法[10,12]對原始PFP算法進行優化，通過改進數據分組方式及構建局部頻繁模式樹提高算法效率及適用性。ABH算法[13]利用數組隨機存儲的效率改進FP樹結構，在Hadoop平臺下有效減少了候選集規模，從而改進算法效率。文獻[14]中分布式FP-Growth的動態任務分配原則試圖滿足任務分配的公平性，但由于未考慮不同任務間計算量差異，節點計算量分配具有不同程度的波動性。
面向大數據處理的FIM算法通過在云計算框架下實現數據的特征提取與數據挖掘工作，而其中分布式計算正確性、公平性方面仍有諸多疑問亟需解決。因此本文提出的HBFP算法在Hadoop平臺通過數據分割、計算量預估及任務均衡化分類策略實現計算任務在分布式環境的負載均衡，解決并行算法中計算分配的公平性問題，保證計算結果的正確性，改進海量數據中頻繁項集挖掘算法的性能表現。
1相關概念及描述
設集合I={I1,I2,…,In}，數據事務集D={T1,T2,…,Tt}由多條事務Ti組成，每條事務為多個項Ii的集合，存在Ti?I。
定義2若存在項的集合I，滿足support(I)>Thresh，其中Thresh為支持度閾值，則稱該項集I為頻繁項集；當集合包含k個元素，稱其為頻繁k項集，記為Lk。
定義3候選集Ck表示k項元素組成事務的所有集合。
定義4項Ik的條件模式基表示樹結構中所有Ik元素至根節點的前綴路徑組成的集合，不含節點Ik本身。
Apriori性質[2]任意頻繁項集的非空子集必為頻繁項集，稱為向下封閉性；非頻繁項集的超集必不是頻繁項集。
基于FP的算法依賴于FP-Tree的壓縮結構保存原始事務數據，隨著數據集的不斷增加，當數據量到達一定規模后，形成的FP-Tree的規模將不再擴大，本文稱其為滿FP樹。
滿FP樹(Full FP-Tree)：將I={I1,I2,…,In}中項的所有組合構成的項集作為輸入構建出來的FP樹。
定理1滿FP樹中蘊含的事務總數為2n-1，滿FP樹中非根節點數量亦為2n-1。
(1)
由文獻[3]可得FP樹中包含所有輸入事務的數據，則滿FP樹中包含事務總數為2n-1。
在滿FP樹中從任一非根節點出發，回溯至根節點的路徑即為一條事務，從所有節點回溯至根節點的路徑為該樹結構中蘊含的所有事務。設滿FP樹中節點數量為Nnodes，則Nnodes=Nitemsets，可得滿FP樹中非根節點數量為 2n-1。
定理2當輸入事務數據達到一定規模，FP樹轉變為滿FP樹，新的數據輸入不會改變FP樹規模，稱滿FP樹具有穩定性。
2Hadoop下均衡FP-Growth算法HBFP設計
HBPF算法采用Hadoop的任務調度機制，實現節點多任務的優化調度。同時引入任務計算量預估及分配模式模型，實現不同任務的計算量均衡分配?；诙贪逍臄祿毩⒎纸M策略進一步保證全局算力的均衡分布。主要需解決的問題為分布式計算中如何分配數據以確保計算公平性、如何設計分布式計算模型以保證計算正確性及如何實現全局計算的負載均衡特性等，下面對算法分步驟展開描述。
步驟一數據集分布式存儲，該步驟合理數據預處理是后續算法并行高效執行的基礎。
步驟二頻繁1項集計算，MapReduce任務通過單次數據集掃描實現所有項的并行化計數統計。
步驟三據頻繁1項集對原始數據進行修剪、重排，基于“后綴模式轉換”將原始數據分割為節點獨立計算所依賴的子事務集合。這是節點進行獨立數據挖掘并保證結果正確性的基礎。
步驟四提出任務計算量的預估模型，并基于計算估值采用短板效應策略實現任務分組的均衡化分配。該步驟是實現計算任務保證計算公平性的重要步驟，最大程度保證全局負載的均衡特性。
步驟五分布式節點針對特定的項進行節點獨立的FP-Growth運算，該步驟中節點使用步驟四中分配至該節點的項關聯數據子事務完成本地數據計算，保證了結果正確性。
步驟六匯聚各節點不同項的頻繁項集，將所獲得的大量頻繁項集進行排序篩選，獲取關聯特性最強的前N條頻繁項集。
2.1數據集分布式存儲
分布式計算中原始數據集被切分為多個子數據集，Hadoop平臺HDFS文件系統默認以64 MB為單位分配數據至不同節點。而大量小文件的數據處理時應利用CombineFileInputFormat類進行數據預處理，合并小數據可提高分布式存儲效率[15]。數據分布式存儲的物理切分過程稱為分塊操作。
Map任務數量是計算并行化程度的直接表征，由Hadoop中InputFormat決定，而每個Map實際輸入數據量由式(2)確定：
SplitSize=max(minSize,min(goalSize,blockSize))goalSize=totalSize/mapred.map.tasks
(2)
minSize由mapred-site.xml中mapred.min.split.size設置，goalSize由輸入文件大小和map數量計算所得，blockSize由hdfs-site.xml中dfs.block.size設置。上述操作輸出鍵值對作為后續程序數據輸入，為并行化計算做分布式存儲準備，該過程稱為分片操作。
通過數據分塊和分片操作，大數據集分布式存儲在多個存儲節點中。
2.2頻繁1項集計算
頻繁1項集計算可以歸類為并行化計數統計，這是典型MapReduce任務。Map以數據分片作為輸入，完成數據讀取任務，輸出結果為
利用2.1節中分片及Map任務數量優化配置，并行計算的效率將提高，算法空間及時間復雜度均為O(DB_Shardingsize)。其中DB_Shardingsize為單節點中分片數據量。
2.3修剪重排與數據分組
算法1后綴模式轉換算法
輸入：事務數據Ti，輔助記錄表RecordList
輸出：各項關聯的子事務數據
Procedure: SegmentTask (key, value=Ti)
//修剪、重排
(2)items[] = Split(Ti)
(3)for i=0 to items.length -1 do
//事務分割
(4)if (RecordList.isEmpty == FALSE) then
(5)Output(< items [i], RecordList >)
(6)end
(7)RecordList.add(items [i])
(8)end
算法1正確性分析：頻繁項集挖掘最終結果中，有序排列頻繁項集若包含某項s，僅且存在兩種情況：一類為s是頻繁項的后綴，形如<…，s>；一類為s是頻繁項非后綴，形如<…,s,…>。而對于一條原始事務記錄
經Hadoop的Shuffle處理后具有相同key的子事務將匯聚至同一個Reduce節點處理，從而該節點獲取所有以key為后綴的子事務分組記錄。事務修剪重排與數據分組建立過程包括：修剪與重排、事務分割、事務分組建立，該過程如圖1所示。
圖1 事務修剪重排與分組建立過程
2.4計算量預估與均衡化分組
獲取數據集中每個項的頻繁項所需的精確計算量較為復雜，BPFP算法[10]依據F_List中項e所在的位置進行頻繁項集挖掘所需計算量Cost(e)的估值為：
Cost(e)=Log(P(e,F_List))
(3)
這種估值方式是利用所有項頻次的匯總數據進行粗略估計。本文通過利用事務分組中項的位置信息進行計算量估值，從而在不增加計算的情況下，獲取更精確的計算量預估信息。如由分組信息v,{
(4)
事務分組建立后，為滿足計算均衡化分配，據計算量估值進行分組歸類。假設計算節點數為N，則建立分組記錄表gListN，表中每個分組對應一個計算節點計算所需要的分組數據。基于短板效應的事務分組機制為：先取Cost_List中前N項保存至gListN，將分組列表中各項的計算量之和作為該分組的計算估值；遍歷Cost_List中其余各項，并依次加入gListN中計算估值最小的列表，更新對應分組的計算估值。該過程為基于短板效應負載均衡模型，最大程度實現了各節點分配計算任務的均衡化，其偽碼描述為算法2。
算法2短板效應均衡算法
輸入：按計算量估值降序排列的列表Cost_List，計算節點數N，分組記錄表gList
輸出：分組任務列表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節點獨立的FP-Growth運算
數據分組機制使得節點獲取到與項相關的所有子事務數據。事務數據分組以
受均衡分組機制的作用，Reduce節點會收到不同項的事務分組，在Hadoop的Shuffle機制下，多個分組將依次有序輸入。當新輸入事務的key發生變化時，對已建立的FP樹進行條件FP樹挖掘，計算完成則獲得其頻繁項集，清空FP樹，開始新項的FP樹建立及頻繁項集挖掘，該過程如圖2所示。
圖2 分類事務的頻繁項集挖掘
分布式節點獲取的項關聯的子事務數據也就是完整事務數據建立FP樹后該項對應的條件模式基，而在數據集龐大的前提下是無法進行完整FP樹構建。通過“后綴模式轉換”操作將事務分割，節點級建立條件FP樹、進行條件FP樹的挖掘，最終實現分而治之的分布式挖掘。
根據滿FP樹定理2，當數據量不斷擴充時，節點本地FP規模將趨于穩定。設節點本地FP樹建立后頭節點數量為m，據滿FP樹定理1，則FP樹中節點數量最大為2m-1。由此可得構建此FP樹的空間復雜度為O(2m)，挖掘算法的時間復雜度應小于O(m×2m)。
2.6結果匯聚
分布式節點中FP-Growth的輸出結果形如
3實驗分析
3.1參數設定
實驗集群由九臺高性能計算機組成，包含1臺管理節點，8臺計算節點，節點配置為Intel?CoreTMi7-3770 CPU @ 3.40 GHz型號CPU、4 GB內存、Intel?Q77主板，系統采用Ubuntu 14.04，Hadoop版本0.23，環境中參數設定及變量定義如表1所示。數據集的元數據采用http://fimi.ua.ac.be/data/的retail.data，并以此擴展事務數為105，2×105，4×105，8×105四個級別的測試數據集，記為{D1,D2,D3,D4}。各測試數據集的特征統計信息如表2所示，其中數據集D1的詳細數據頻次分布如圖3所示。
表1 仿真實驗參數設定
表2 數據集的特征統計信息
圖3 數據集D1中項的頻次分布情況
3.2結論分析
算法HBFP在不同數量級事務數據庫下不同數量計算節點的關聯規則挖掘性能表現如圖4所示。橫軸為分布式計算節點數量，縱軸表示計算完成的時間。隨計算節點的增加算法完成時間減少的整體表現與Hadoop分布式計算框架中多節點并行計算的性能優勢相吻合。當計算數據量并不龐大時，分布式框架的任務分配與啟動時間相較于計算時間不可忽視，這將導致計算節點的增加并不會使得計算性能的顯著提升。這是由分布式平臺特性決定的，即分布式算法在大規模的數據計算中性能提升更加顯著。
圖4 HBFP算法在不同樣本量及計算節點數量下的運算
PFP算法[9]是MapReduce下的FP-Growth分布式設計方案，并在Mahout開源項目進行實現。圖5顯示了在同等配置下PFP算法與本文提出的HBFP算法在不同計算節點的執行時間，橫軸表示不同的計算節點，縱軸表示節點算法執行時間(單位：分鐘)。PFP算法隨機任務分配機制使得在不同節點任務完成時間差別較大，圖中2號節點與5號節點的完成時間相差幾倍；HBFP算法利用各分組的任務計算量預估信息進行任務分配,使得各節點任務執行時間基本在6分鐘左右。并行任務的完成時間由各節點中的最大完成時間決定，數據顯示HBFP算法的FP-Growth階段的總體完成時間比PFP快近12%，HBFP算法中各節點執行任務時間相近，證明任務分配更加均衡。
圖5 不同節點任務執行時間差異
(5)
圖6中橫軸表示支持度閾值(單位：%)，縱軸表示任務執行時間的標準差，對比了在三種分布式算法(PFP、BPFP[10]、HBFP)中節點任務分配均勻度情況。由于PFP算法任務分配并未計算不同任務量的差異，支持度閾值較小時計算任務量龐大，任務分配不均勻導致任務執行時間標準差較大；支持度閾值增大時，計算任務量相應減少，由任務分配不均而導致的節點執行時間差異縮小，標準差趨于減小。BPFP算法利用項的頻次信息進行計算量估值的方式一定程度上縮小了計算節點間的任務量差異，但存在支持度閾值變化導致任務分配不均的情況。HBFP算法的短板效應均衡算法使得各節點的任務執行時間基本分布在平均值左右，受支持度閾值影響最小。但也需指出HBFP算法存在隨著支持度閾值增大任務分配均衡性變差，這是由于計算任務數量減少可分配任務的粒度增大，從而導致均衡分組特性有所下降。
圖6 不同支持度閾值下的節點任務執行時間標準差
4結語
本文對大數據規模下的頻繁項集挖掘提出負載均衡的并行設計方案，進一步優化計算分布的均衡化，實現全局計算效率的提升。實驗結果表明，在大規模數據下的頻繁項集挖掘中HBFP算法具有良好的適用性。文中研究的匯聚節點僅為單一節點，在數據量異常龐大時會面臨匯聚緩慢的性能瓶頸，未來需對此進一步擴展研究。
參考文獻
[1] 朱紹文,王泉德,黃浩,等.關聯規則挖掘技術及發展動向[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] 曾志勇,楊呈智,陶冶.負載均衡的FP—growth并行算法研究[J].計算機工程與應用,2010,46(4):125-126.
[5] 鄭麟.一種直接生成頻繁項集的分治Apriori算法[J].計算機應用與軟件,2014,31(4):297-301,326.
[6] 談克林,孫志揮.一種FP樹的并行挖掘算法[J].計算機工程與應用,2006,42(13):155-157.
[7] 楊勇,王偉.一種基于MapReduce的并行FP-growth算法[J].重慶郵電大學學報:自然科學版,2013,25(5):651-657.
[8] 顏躍進,李舟軍,陳火旺.基于FP-Tree有效挖掘最大頻繁項集[J].軟件學報,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].計算機工程與應用,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] 王智鋼,王池社,馬青霞.分布式并行關聯規則挖掘算法研究[J].計算機應用與軟件,2013,30(10):113-115,119.
[15] 袁玉,崔超遠,烏云,等.單機下Hadoop小文件處理性能分析[J].計算機工程與應用,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。國家林業局重點課題(2013-05)；十二五科技支撐課題(2011BAH10B04)。朱文飛，碩士生，主研領域：數據挖掘。齊建東，副教授。洪劍珂，碩士生。
中圖分類號TP311
文獻標識碼A
DOI:10.3969/j.issn.1000-386x.2016.05.010
