基于MapReduce的DHP算法并行化研究
2016-07-19 02:07:19周國軍吳慶軍
計算機應用與軟件 2016年6期
周國軍 吳慶軍
(玉林師范學院數學與信息科學學院 廣西 玉林 537000)
?
基于MapReduce的DHP算法并行化研究
周國軍吳慶軍
(玉林師范學院數學與信息科學學院廣西 玉林 537000)
摘要針對DHP(direct hashing and pruning)算法對大數據挖掘關聯規則存在執行時間過長、效率不高的問題，對DHP算法的并行化策略進行了研究。根據云計算平臺Hadoop的MapReduce并行編程模型，設計了一種并行DHP算法，給出了算法的總體流程和Map函數、Reduce函數的算法描述。與DHP算法相比，并行算法利用了Hadoop集群強大的計算能力，提高了從大數據集中挖掘關聯規則的效率。通過實例分析了并行DHP算法的執行過程，在多個數據集上進行了實驗。實驗結果表明：并行DHP算法對大數據具有較好的加速比和可擴展性。
關鍵詞MapReduce Hadoop DHP算法關聯規則
0引言
關聯規則挖掘是數據挖掘領域的一個重要研究方向，其目標是從事務數據庫中發現項與項之間的相關聯系。如何高效地找出所有的頻繁項集是關聯規則挖掘算法要解決的主要問題。DHP算法[1]在Apriori算法[2]的基礎上利用哈希技術修剪候選項集和事務數據庫，提高了生成頻繁項集的效率，是公認的非常有效的算法。由于DHP算法具有很好的性能，在文本數據挖掘[3]、Web遍歷路徑挖掘[4]等方面得到了廣泛應用。已經有較多的文獻對DHP算法的Hash函數選取、Hash表結構優化、冗余事務的修剪策略等進行了研究和改進，這些改進算法進一步提高了發現頻繁項集的效率。但是，DHP算法是一種時間復雜度較高的算法，受單機存儲空間和計算能力的限制，DHP算法及其改進的串行算法對大數據集挖掘關聯規則存在執行時間太長、效率較低的性能瓶頸問題。
云計算[5]是近年來興起的一種計算模式，優勢是提供了海量的存儲空間和強大的計算能力，將云計算技術應用于數據挖掘領域是一個新的發展趨勢[6]。Google公司提出的MapReduce[7]是一種簡潔高效的并行編程模型，該模型屏蔽了底層實現細節，降低了編程難度。MapReduce模型將復雜的處理任務抽象成Map函數和Reduce函數，Map、Reduce函數在分布式集群的節點上并行執行，從而達到了對大規模計算任務進行高效處理的要求[8]。Apache軟件基金會開發的Hadoop[9]是一個開源的分布式計算平臺，該平臺以高可靠性、高擴展性等優點得到了學術界的認可和工業界的廣泛應用。Hadoop實現了MapReduce模型，用戶可以在大量廉價設備組成的Hadoop集群上運行MapReduce應用程序。
本文根據Hadoop平臺的MapReduce模型，對DHP算法的并行化方法進行了分析，設計了一種并行DHP算法。該算法利用Hadoop集群中各節點的計算能力，縮短了對大數據集挖掘關聯規則的時間，具有較好的加速比和可擴展性。最后，通過實驗驗證了并行DHP算法的性能。
1Hadoop平臺的MapReduce模型
Hadoop的MapReduce框架處理大數據集的一般過程是：將大數據集分解成許多數據分片，JobTracker進程將MapReduce任務分配給TaskTracker節點，TaskTracker進程讀取一個(或多個)數據分片、并執行MapReduce任務。
在Hadoop中,MapReduce應用程序的基本結構包括主函數、Map函數和Reduce函數。主函數對每個MapReduce作業所需的參數進行配置，并在作業啟動后對程序的執行流程進行控制。Map函數定義為一個類(稱為Mapper類)，在Mapper類中可以定義setup、map和cleanup等方法。對于每個Map任務，setup方法只在任務開始之前調用一次，cleanup方法只在任務結束之前調用一次。相應地，Reduce函數定義為一個稱為Reducer的類，在Reducer類中可以定義setup、reduce和cleanup等方法，對于每個Reduce任務，setup和cleanup方法只調用一次。map、reduce方法的一般形式[10]表示如下：
map：(K1,V1) →list(K2,V2)
reduce：(K2,list(V2)) →list(K3,V3)
其中，(K1,V1)是數據分片的一條記錄經過MapReduce框架解析后的鍵/值對表示形式，list(K2,V2)、list(K3,V3)分別是map和reduce方法輸出的鍵/值對列表。
2DHP算法的并行化策略
文獻[1]給出了DHP算法的詳細描述，DHP算法的三個部分都能采用MapReduce模型將其并行化，說明如下：
第一部分對候選1-項集的支持度計數、哈希表的桶計數進行并行化。與詞頻統計方法相似，Map函數對數據分片的每個事務t分解出所有項ij，計算出所有2-項子集x的哈希桶地址addr=h2[x]，輸出
第二部分對事務數據庫Dk的修剪、候選k-項集的支持度計數和哈希表的桶計數進行并行化。該部分是一個迭代計算頻繁k項集Lk的過程，每次迭代過程由一個MapReduce任務完成，需要解決3個主要問題。①控制迭代次數。簡單的方法是在主函數中由循環條件 (|{x|Hk[x]≥s}|≥LARGE) 控制MapReduce任務迭代的次數。②Map函數如何讀取所有頻繁(k-1)-項集Lk-1和哈希表Hk以生成所有候選k-項集Ck。在主函數中將Lk-1和Hk設置為分布式緩存文件，由Hadoop的MapReduce框架將Lk-1和Hk分發到執行Map任務的TaskTracker節點就解決了這個問題。③如何輸出修剪后的事務數據庫Dk+1。簡單的方法是在Hadoop的文件系統HDFS中創建一個目錄，Map函數將修剪后的數據分片以文件形式寫入到HDFS中。該方法的優點是：第k+1次迭代只需在主函數中設置MapReduce任務的輸入路徑為Dk+1的目錄，Map函數便可讀取Dk+1的數據分片。
第三部分對事務數據庫Dk的修剪和候選k-項集的支持度計數進行并行化。在該部分中，主函數除了控制程序流程之外，還需要完成以下計算：在第一個MapReduce任務執行前生成所有候選k-項集Ck,即執行gen_candidate(Lk-1,Hk,Ck)，并將Ck分發給執行Map任務的節點。在每個MapReduce任務結束后執行Ck+1=apriori_gen(Lk)，并在下一次迭代前分發Ck+1。
3并行DHP算法設計與描述
3.1算法的總體流程及描述
并行DHP算法的總體流程如圖1所示，其中s是最小支持度閾值，LARGE是預定義的閾值。
圖1 并行DHP算法流程圖
與DHP算法相對應，并行DHP算法也分為三部分。算法的流程控制由主函數實現，各部分的并行計算由Map和Reduce函數實現。Map函數和Reduce函數描述如下：
Part1的Map函數：
//TID是事務編號，t是事務的項列表
map(key=TID,value=t){
foreach項ij∈t
output(
foreach2-項子集x∈t{
addr=h2(x);
//“*”是哈希地址addr的前綴字符
output(<*addr,1>);
}
}
Part1的Reduce函數：
reduce(key=ij或key=*addr,values=list(1)){
count=0;
foreach1invalues
count++;
/* 輸出滿足條件的頻繁1-項集及支持度、
輸出哈希表的桶地址及計數值 */
if(count≥s)output(
}
Part2的Map函數：
setup(){
//生成候選k-項集
gen_candidate(Lk-1,Hk,Ck);
Dk+1= ?;
}
map(key=TID,value=t){
foreacht的k-項子集c(=ti1...tik)
if(c∈Ck) {
output(
for(j=1;j≤k;j++)a[ij]++;
}
//刪除t中不必要的項
for(i=0,j=0;i<|t|;i++)
if(x的所有k-項子集y都滿足Hk[hk(y)]≥s){
addr=hk+1(x);
output(<*addr,1>);
for(j=1;j≤k+1;j++)a[ij]++;
}
}
//刪除數據分片中不必要的事務
}
}
cleanup(){
在HDFS中創建一個目錄inputk+1；
將Dk+1分片保存在inputk+1目錄的一個文件中；
}
Part2的Reduce函數：
reduce(key=c或key=*addr,values=list(1)){
count=0;
foreach1invalues
count++;
/* 輸出滿足條件的頻繁k-項集及支持度、
輸出哈希表的桶地址及計數值 */
if(count≥s)output(
}
Part3的Map函數：
setup(){
讀取Ck;
Dk+1= ?;
}
map(key=TID,value=t){
foreacht的k-項子集c(=ti1...tik)
if(c∈Ck) {
output(
for(j=1;j≤k;j++)a[ij]++;
}
//刪除t中不必要的項
for(i=0,j=0;i<|t|;i++)
//刪除數據分片中不必要的事務
}
cleanup(){
在HDFS中創建一個目錄inputk+1；
將Dk+1分片保存在inputk+1目錄的一個文件中；
}
Part3的Reduce函數：
reduce(key=c,values=list(1)){
count=0;
foreach1invalues
count++;
//輸出滿足條件的頻繁k-項集及支持度
if(count≥s)output(
}
3.2算法的實例分析
下面通過一個實例來說明并行DHP算法的執行過程，如圖2所示。
圖2 并行DHP算法執行過程示例
在該實例中，使用文獻[1]給出的示例數據庫。假定Map、Reduce任務數各為2，選取s=2、LARGE=3，選取的Hash函數定義如下：
hk({i1,i2,…,ik})=((order(i1)+order(i2)+…+order(ik-1))×10+order(ik))modp
對于該實例，算法的執行過程需要3個MapReduce任務去完成。第1個MapReduce任務執行Part1的過程，得到L1和H2。由于條件 |{x|H2[x]≥s}|≥LARGE成立，第2個MapReduce任務執行Part2的過程，得到L2、H3和D3。由于條件 |{x|H3[x]≥s}|≥LARGE不成立，第3個MapReduce任務執行Part3的過程，得到L3和D4。由于|D4|=0，算法結束。
算法的執行結果與文獻[1]的結果相同，可見，本文設計的并行DHP算法是正確的。
4實驗結果及分析
4.1實驗環境與實驗數據
實驗環境是7臺配置相同的計算機組成的Hadoop集群，其中1臺作為JobTracker節點,6臺作為TaskTracker節點。計算機的配置是：雙核2.93GHzCPU、2GB內存和100M網卡。使用的軟件是：Ubuntu12.04LTS、Hadoop1.2.1、JDK1.7.0_51。
使用Java語言實現了文獻[1]提出的DHP算法和本文設計的并行DHP算法，并對數據集進行了3組實驗，分別測試算法的運行時間、加速比和可擴展性。實驗選取的數據集來自網站http://fimi.ua.ac.be/data/。為了便于測試算法的可擴展性，從數據集webdocs中分別隨機抽取1×105、2×105、3×105、4×105、5×105、6×105條記錄作為6個實驗數據集。
4.2算法的運行時間測試
使用4個數據集測試算法的運行時間，retail、kosarak是稀疏型數據集，設置了較小的支持度閾值，accidents、pumsb是稠密型數據集，設置了較大的支持度閾值。為了便于與DHP算法比較，分別使用1個和2個TaskTracker節點測試并行DHP算法的運行時間。實驗結果如表1所示。
表1 DHP算法與并行DHP算法的執行時間
從表1可以看出，使用1個TaskTracker節點，并行DHP算法在4個數據集上的運行時間都大于DHP算法；使用2個節點，除retail之外，并行DHP算法在其余3個數據集上的運行時間均小于DHP算法。retail是一個較小(4.2MB)的稀疏型數據集，對該數據集挖掘頻繁項集的計算時間較小。但是，并行DHP算法需要5個MapReduce任務才能完成對retail的數據處理，每個任務的初始化和啟動所用的時間相對于計算時間有較大的比重，所以總的運行時間要大于DHP算法。
由此可見，并行DHP算法不適合對計算量小的數據集挖掘頻繁項集；對于計算規模較大的數據集，并行DHP算法顯著減少了挖掘頻繁項集的時間，提高了算法的執行效率。
4.3算法的加速比測試
加速比是評價并行算法性能的重要指標之一，文獻[11]給出了加速比的計算公式，定義如下：
Sp=t1/tp
(1)
其中，t1、tp分別表示在1個節點和p個節點上的執行時間。
使用表1列出的4個數據集和最小支持度測試并行DHP算法的加速比，實驗結果如圖3所示。從圖3可以看出，對于計算規模較小的數據集retail和kosarak，算法表現出很低的加速比，這是因為隨著計算節點數的增加，在節點之間的通信開銷相對于計算時間的比重顯著增大，不能取得較好的加速比；對于計算規模較大的數據集accidents和pumsb，算法取得了較好的加速比。
圖3 并行DHP算法的加速比
4.4算法的可擴展性測試
可擴展性是指算法能否隨節點數的增加而按比例提高。文獻[12]給出了等速度可擴展性的計算公式，定義如下：
(2)
其中，w、p是問題規模和處理機規模，w′、p′是擴展后的問題規模和處理機規模。
對從webdocs中隨機抽取的6個數據集(數據規模成倍增加)進行可擴展性測試，實驗結果如圖4所示。實驗結果表明，對于兩種不同的最小支持度，并行DHP算法都能取得較好的可擴展性。
圖4 并行DHP算法的可擴展性
5結語
DHP算法是一種經典的關聯規則挖掘算法，受單機計算能力和內存的限制，DHP算法對大數據挖掘頻繁項集存在執行時間過長、效率不高的問題。針對該問題，本文根據Hadoop平臺的MapReduce并行編程模型對DHP算法的并行化策略進行了研究，設計了一種基于MapReduce模型的并行DHP算法，通過實例分析了算法的執行過程和正確性。與DHP算法相比，本文設計的并行算法利用了Hadoop集群強大的計算能力，縮短了對大數據集挖掘頻繁項集的時間，具有較高的執行效率。在多個數據集上對算法進行了測試，實驗結果表明：并行DHP算法對大數據集具有較好的加速比和可擴展性。
參考文獻
[1]ParkJS,ChenMS,YuPS.Aneffectivehash-basedalgorithmforminingassociationrules[C]//Proceedingsofthe1995ACMSIGMODInternationalConferenceonManagementofData.NewYork:ACM,1995,24(2):175-186.
[2]AgrawalR,SrikantR.Fastalgorithmsforminingassociationrules[C]//Proceedingsofthe20thInternationalConferenceonVeryLargeDataBases.Santiago,Chile,1994:487-499.
[3]HoltJD,ChungSM.Efficientminingofassociationrulesintextdatabases[C]//ProceedingsoftheEighthInternationalConferenceonInformationandKnowledgeManagement.NewYork:ACM,1999:234-242.
[4] 王濤偉,周必水.基于DHP的頻繁遍歷路徑挖掘算法[J].杭州電子科技大學學報,2005,25(5):60-63.
[5]ArmbrustM,FoxA,GriffithR,etal.Abovetheclouds:aBerkeleyviewofcloudcomputing[R/OL].2009-02-10[2015-02-15].http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.html.
[6] 周麗娟,王翔.云環境下關聯規則算法的研究[J].計算機工程與設計,2014,35(2):499-503.
[7]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM,2008,51(1):107-113.
[8] 李建江,崔健,王聃,等.MapReduce并行編程模型研究綜述[J].電子學報,2011,39(11):2635-2642.
[9]TheApacheSoftwareFoundation.Hadoop[EB/OL].2014-12-12[2015-02-15].http://hadoop.apache.org/.
[10] 黃立勤,柳燕煌.基于MapReduce并行的Apriori算法改進研究[J].福州大學學報(自然科學版),2011,39(5):680-685.
[11] 陳興蜀,張帥,童浩,等.基于布爾矩陣和MapReduce的FP-Growth算法[J].華南理工大學學報(自然科學版),2014,42(1):135-141.
[12] 陳軍,莫則堯,李曉梅,等.大規模并行應用程序的可擴展性研究[J].計算機研究與發展,2000,37(11):1382-1388.
RESEARCH ON PARALLELISATION OF DHP ALGORITHM BASED ON MAPREDUCE
Zhou GuojunWu Qingjun
(School of Mathematics and Information Science,Yulin Normal University,Yulin 537000,Guangxi,China)
AbstractDHP algorithm is confronted with the problems in association rules mining for big data such as long execution time and low efficiency,etc.In order to solve the problems,we studied the parallelisation strategy of DHP algorithm.According to MapReduce parallel programming model of cloud computing platform Hadoop,we designed a parallel DHP algorithm,presented the overall flow of the algorithm and the algorithm descriptions of Map function and Reduce function.Compared with DHP algorithm,the parallel DHP algorithm makes use of the powerful computing capacity of Hadoop cluster,improves the efficiency of mining association rules from big data.We analysed the execution process of parallel DHP algorithm by example,and carried out experiments on a couple of datasets.Experimental results showed that the parallel DHP algorithm has good speedup and scalability on big data.
KeywordsMapReduceHadoopDHP algorithmAssociation rules
收稿日期：2015-03-03。廣西高校科學技術研究立項項目(LX20 14300)。周國軍，講師，主研領域：數據挖掘，云計算。吳慶軍，副教授。
中圖分類號TP311.1
文獻標識碼A
DOI:10.3969/j.issn.1000-386x.2016.06.012
