基于MapReduce的DHP算法并行化研究
2016-07-19 02:07:19周國軍吳慶軍
計算機應用與軟件 2016年6期
周國軍 吳慶軍
(玉林師范學院數(shù)學與信息科學學院 廣西 玉林 537000)
?
基于MapReduce的DHP算法并行化研究
周國軍吳慶軍
(玉林師范學院數(shù)學與信息科學學院廣西 玉林 537000)
摘要針對DHP(direct hashing and pruning)算法對大數(shù)據(jù)挖掘關聯(lián)規(guī)則存在執(zhí)行時間過長、效率不高的問題，對DHP算法的并行化策略進行了研究。根據(jù)云計算平臺Hadoop的MapReduce并行編程模型，設計了一種并行DHP算法，給出了算法的總體流程和Map函數(shù)、Reduce函數(shù)的算法描述。與DHP算法相比，并行算法利用了Hadoop集群強大的計算能力，提高了從大數(shù)據(jù)集中挖掘關聯(lián)規(guī)則的效率。通過實例分析了并行DHP算法的執(zhí)行過程，在多個數(shù)據(jù)集上進行了實驗。實驗結果表明：并行DHP算法對大數(shù)據(jù)具有較好的加速比和可擴展性。
關鍵詞MapReduce Hadoop DHP算法關聯(lián)規(guī)則
0引言
關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領域的一個重要研究方向，其目標是從事務數(shù)據(jù)庫中發(fā)現(xiàn)項與項之間的相關聯(lián)系。如何高效地找出所有的頻繁項集是關聯(lián)規(guī)則挖掘算法要解決的主要問題。DHP算法[1]在Apriori算法[2]的基礎上利用哈希技術修剪候選項集和事務數(shù)據(jù)庫，提高了生成頻繁項集的效率，是公認的非常有效的算法。由于DHP算法具有很好的性能，在文本數(shù)據(jù)挖掘[3]、Web遍歷路徑挖掘[4]等方面得到了廣泛應用。已經有較多的文獻對DHP算法的Hash函數(shù)選取、Hash表結構優(yōu)化、冗余事務的修剪策略等進行了研究和改進，這些改進算法進一步提高了發(fā)現(xiàn)頻繁項集的效率。但是，DHP算法是一種時間復雜度較高的算法，受單機存儲空間和計算能力的限制，DHP算法及其改進的串行算法對大數(shù)據(jù)集挖掘關聯(lián)規(guī)則存在執(zhí)行時間太長、效率較低的性能瓶頸問題。
云計算[5]是近年來興起的一種計算模式，優(yōu)勢是提供了海量的存儲空間和強大的計算能力，將云計算技術應用于數(shù)據(jù)挖掘領域是一個新的發(fā)展趨勢[6]。Google公司提出的MapReduce[7]是一種簡潔高效的并行編程模型，該模型屏蔽了底層實現(xiàn)細節(jié)，降低了編程難度。MapReduce模型將復雜的處理任務抽象成Map函數(shù)和Reduce函數(shù)，Map、Reduce函數(shù)在分布式集群的節(jié)點上并行執(zhí)行，從而達到了對大規(guī)模計算任務進行高效處理的要求[8]。Apache軟件基金會開發(fā)的Hadoop[9]是一個開源的分布式計算平臺，該平臺以高可靠性、高擴展性等優(yōu)點得到了學術界的認可和工業(yè)界的廣泛應用。Hadoop實現(xiàn)了MapReduce模型，用戶可以在大量廉價設備組成的Hadoop集群上運行MapReduce應用程序。
本文根據(jù)Hadoop平臺的MapReduce模型，對DHP算法的并行化方法進行了分析，設計了一種并行DHP算法。該算法利用Hadoop集群中各節(jié)點的計算能力，縮短了對大數(shù)據(jù)集挖掘關聯(lián)規(guī)則的時間，具有較好的加速比和可擴展性。最后，通過實驗驗證了并行DHP算法的性能。
1Hadoop平臺的MapReduce模型
Hadoop的MapReduce框架處理大數(shù)據(jù)集的一般過程是：將大數(shù)據(jù)集分解成許多數(shù)據(jù)分片，JobTracker進程將MapReduce任務分配給TaskTracker節(jié)點，TaskTracker進程讀取一個(或多個)數(shù)據(jù)分片、并執(zhí)行MapReduce任務。
在Hadoop中,MapReduce應用程序的基本結構包括主函數(shù)、Map函數(shù)和Reduce函數(shù)。主函數(shù)對每個MapReduce作業(yè)所需的參數(shù)進行配置，并在作業(yè)啟動后對程序的執(zhí)行流程進行控制。Map函數(shù)定義為一個類(稱為Mapper類)，在Mapper類中可以定義setup、map和cleanup等方法。對于每個Map任務，setup方法只在任務開始之前調用一次，cleanup方法只在任務結束之前調用一次。相應地，Reduce函數(shù)定義為一個稱為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)是數(shù)據(jù)分片的一條記錄經過MapReduce框架解析后的鍵/值對表示形式，list(K2,V2)、list(K3,V3)分別是map和reduce方法輸出的鍵/值對列表。
2DHP算法的并行化策略
文獻[1]給出了DHP算法的詳細描述，DHP算法的三個部分都能采用MapReduce模型將其并行化，說明如下：
第一部分對候選1-項集的支持度計數(shù)、哈希表的桶計數(shù)進行并行化。與詞頻統(tǒng)計方法相似，Map函數(shù)對數(shù)據(jù)分片的每個事務t分解出所有項ij，計算出所有2-項子集x的哈希桶地址addr=h2[x]，輸出
第二部分對事務數(shù)據(jù)庫Dk的修剪、候選k-項集的支持度計數(shù)和哈希表的桶計數(shù)進行并行化。該部分是一個迭代計算頻繁k項集Lk的過程，每次迭代過程由一個MapReduce任務完成，需要解決3個主要問題。①控制迭代次數(shù)。簡單的方法是在主函數(shù)中由循環(huán)條件 (|{x|Hk[x]≥s}|≥LARGE) 控制MapReduce任務迭代的次數(shù)。②Map函數(shù)如何讀取所有頻繁(k-1)-項集Lk-1和哈希表Hk以生成所有候選k-項集Ck。在主函數(shù)中將Lk-1和Hk設置為分布式緩存文件，由Hadoop的MapReduce框架將Lk-1和Hk分發(fā)到執(zhí)行Map任務的TaskTracker節(jié)點就解決了這個問題。③如何輸出修剪后的事務數(shù)據(jù)庫Dk+1。簡單的方法是在Hadoop的文件系統(tǒng)HDFS中創(chuàng)建一個目錄，Map函數(shù)將修剪后的數(shù)據(jù)分片以文件形式寫入到HDFS中。該方法的優(yōu)點是：第k+1次迭代只需在主函數(shù)中設置MapReduce任務的輸入路徑為Dk+1的目錄，Map函數(shù)便可讀取Dk+1的數(shù)據(jù)分片。
第三部分對事務數(shù)據(jù)庫Dk的修剪和候選k-項集的支持度計數(shù)進行并行化。在該部分中，主函數(shù)除了控制程序流程之外，還需要完成以下計算：在第一個MapReduce任務執(zhí)行前生成所有候選k-項集Ck,即執(zhí)行gen_candidate(Lk-1,Hk,Ck)，并將Ck分發(fā)給執(zhí)行Map任務的節(jié)點。在每個MapReduce任務結束后執(zhí)行Ck+1=apriori_gen(Lk)，并在下一次迭代前分發(fā)Ck+1。
3并行DHP算法設計與描述
3.1算法的總體流程及描述
并行DHP算法的總體流程如圖1所示，其中s是最小支持度閾值，LARGE是預定義的閾值。
圖1 并行DHP算法流程圖
與DHP算法相對應，并行DHP算法也分為三部分。算法的流程控制由主函數(shù)實現(xiàn)，各部分的并行計算由Map和Reduce函數(shù)實現(xiàn)。Map函數(shù)和Reduce函數(shù)描述如下：
Part1的Map函數(shù)：
//TID是事務編號，t是事務的項列表
map(key=TID,value=t){
foreach項ij∈t
output(
foreach2-項子集x∈t{
addr=h2(x);
//“*”是哈希地址addr的前綴字符
output(<*addr,1>);
}
}
Part1的Reduce函數(shù)：
reduce(key=ij或key=*addr,values=list(1)){
count=0;
foreach1invalues
count++;
/* 輸出滿足條件的頻繁1-項集及支持度、
輸出哈希表的桶地址及計數(shù)值 */
if(count≥s)output(
}
Part2的Map函數(shù)：
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]++;
}
}
//刪除數(shù)據(jù)分片中不必要的事務
}
}
cleanup(){
在HDFS中創(chuàng)建一個目錄inputk+1；
將Dk+1分片保存在inputk+1目錄的一個文件中；
}
Part2的Reduce函數(shù)：
reduce(key=c或key=*addr,values=list(1)){
count=0;
foreach1invalues
count++;
/* 輸出滿足條件的頻繁k-項集及支持度、
輸出哈希表的桶地址及計數(shù)值 */
if(count≥s)output(
}
Part3的Map函數(shù)：
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++)
//刪除數(shù)據(jù)分片中不必要的事務
}
cleanup(){
在HDFS中創(chuàng)建一個目錄inputk+1；
將Dk+1分片保存在inputk+1目錄的一個文件中；
}
Part3的Reduce函數(shù)：
reduce(key=c,values=list(1)){
count=0;
foreach1invalues
count++;
//輸出滿足條件的頻繁k-項集及支持度
if(count≥s)output(
}
3.2算法的實例分析
下面通過一個實例來說明并行DHP算法的執(zhí)行過程，如圖2所示。
圖2 并行DHP算法執(zhí)行過程示例
在該實例中，使用文獻[1]給出的示例數(shù)據(jù)庫。假定Map、Reduce任務數(shù)各為2，選取s=2、LARGE=3，選取的Hash函數(shù)定義如下：
hk({i1,i2,…,ik})=((order(i1)+order(i2)+…+order(ik-1))×10+order(ik))modp
對于該實例，算法的執(zhí)行過程需要3個MapReduce任務去完成。第1個MapReduce任務執(zhí)行Part1的過程，得到L1和H2。由于條件 |{x|H2[x]≥s}|≥LARGE成立，第2個MapReduce任務執(zhí)行Part2的過程，得到L2、H3和D3。由于條件 |{x|H3[x]≥s}|≥LARGE不成立，第3個MapReduce任務執(zhí)行Part3的過程，得到L3和D4。由于|D4|=0，算法結束。
算法的執(zhí)行結果與文獻[1]的結果相同，可見，本文設計的并行DHP算法是正確的。
4實驗結果及分析
4.1實驗環(huán)境與實驗數(shù)據(jù)
實驗環(huán)境是7臺配置相同的計算機組成的Hadoop集群，其中1臺作為JobTracker節(jié)點,6臺作為TaskTracker節(jié)點。計算機的配置是：雙核2.93GHzCPU、2GB內存和100M網(wǎng)卡。使用的軟件是：Ubuntu12.04LTS、Hadoop1.2.1、JDK1.7.0_51。
使用Java語言實現(xiàn)了文獻[1]提出的DHP算法和本文設計的并行DHP算法，并對數(shù)據(jù)集進行了3組實驗，分別測試算法的運行時間、加速比和可擴展性。實驗選取的數(shù)據(jù)集來自網(wǎng)站http://fimi.ua.ac.be/data/。為了便于測試算法的可擴展性，從數(shù)據(jù)集webdocs中分別隨機抽取1×105、2×105、3×105、4×105、5×105、6×105條記錄作為6個實驗數(shù)據(jù)集。
4.2算法的運行時間測試
使用4個數(shù)據(jù)集測試算法的運行時間，retail、kosarak是稀疏型數(shù)據(jù)集，設置了較小的支持度閾值，accidents、pumsb是稠密型數(shù)據(jù)集，設置了較大的支持度閾值。為了便于與DHP算法比較，分別使用1個和2個TaskTracker節(jié)點測試并行DHP算法的運行時間。實驗結果如表1所示。
表1 DHP算法與并行DHP算法的執(zhí)行時間
從表1可以看出，使用1個TaskTracker節(jié)點，并行DHP算法在4個數(shù)據(jù)集上的運行時間都大于DHP算法；使用2個節(jié)點，除retail之外，并行DHP算法在其余3個數(shù)據(jù)集上的運行時間均小于DHP算法。retail是一個較小(4.2MB)的稀疏型數(shù)據(jù)集，對該數(shù)據(jù)集挖掘頻繁項集的計算時間較小。但是，并行DHP算法需要5個MapReduce任務才能完成對retail的數(shù)據(jù)處理，每個任務的初始化和啟動所用的時間相對于計算時間有較大的比重，所以總的運行時間要大于DHP算法。
由此可見，并行DHP算法不適合對計算量小的數(shù)據(jù)集挖掘頻繁項集；對于計算規(guī)模較大的數(shù)據(jù)集，并行DHP算法顯著減少了挖掘頻繁項集的時間，提高了算法的執(zhí)行效率。
4.3算法的加速比測試
加速比是評價并行算法性能的重要指標之一，文獻[11]給出了加速比的計算公式，定義如下：
Sp=t1/tp
(1)
其中，t1、tp分別表示在1個節(jié)點和p個節(jié)點上的執(zhí)行時間。
使用表1列出的4個數(shù)據(jù)集和最小支持度測試并行DHP算法的加速比，實驗結果如圖3所示。從圖3可以看出，對于計算規(guī)模較小的數(shù)據(jù)集retail和kosarak，算法表現(xiàn)出很低的加速比，這是因為隨著計算節(jié)點數(shù)的增加，在節(jié)點之間的通信開銷相對于計算時間的比重顯著增大，不能取得較好的加速比；對于計算規(guī)模較大的數(shù)據(jù)集accidents和pumsb，算法取得了較好的加速比。
圖3 并行DHP算法的加速比
4.4算法的可擴展性測試
可擴展性是指算法能否隨節(jié)點數(shù)的增加而按比例提高。文獻[12]給出了等速度可擴展性的計算公式，定義如下：
(2)
其中，w、p是問題規(guī)模和處理機規(guī)模，w′、p′是擴展后的問題規(guī)模和處理機規(guī)模。
對從webdocs中隨機抽取的6個數(shù)據(jù)集(數(shù)據(jù)規(guī)模成倍增加)進行可擴展性測試，實驗結果如圖4所示。實驗結果表明，對于兩種不同的最小支持度，并行DHP算法都能取得較好的可擴展性。
圖4 并行DHP算法的可擴展性
5結語
DHP算法是一種經典的關聯(lián)規(guī)則挖掘算法，受單機計算能力和內存的限制，DHP算法對大數(shù)據(jù)挖掘頻繁項集存在執(zhí)行時間過長、效率不高的問題。針對該問題，本文根據(jù)Hadoop平臺的MapReduce并行編程模型對DHP算法的并行化策略進行了研究，設計了一種基于MapReduce模型的并行DHP算法，通過實例分析了算法的執(zhí)行過程和正確性。與DHP算法相比，本文設計的并行算法利用了Hadoop集群強大的計算能力，縮短了對大數(shù)據(jù)集挖掘頻繁項集的時間，具有較高的執(zhí)行效率。在多個數(shù)據(jù)集上對算法進行了測試，實驗結果表明：并行DHP算法對大數(shù)據(jù)集具有較好的加速比和可擴展性。
參考文獻
[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] 周麗娟,王翔.云環(huán)境下關聯(lián)規(guī)則算法的研究[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] 陳軍,莫則堯,李曉梅,等.大規(guī)模并行應用程序的可擴展性研究[J].計算機研究與發(fā)展,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。廣西高?？茖W技術研究立項項目(LX20 14300)。周國軍，講師，主研領域：數(shù)據(jù)挖掘，云計算。吳慶軍，副教授。
中圖分類號TP311.1
文獻標識碼A
DOI:10.3969/j.issn.1000-386x.2016.06.012
