基于Hadoop二階段并行模糊c-Means聚類算法

胡吉朝　黃紅艷

(石家莊經濟學院信息工程學院　河北 石家莊 050031)

?

基于Hadoop二階段并行模糊c-Means聚類算法

胡吉朝黃紅艷

(石家莊經濟學院信息工程學院河北 石家莊 050031)

摘要針對Mapreduce機制下算法通信時間占用比過高，實際應用價值受限的情況，提出基于Hadoop二階段并行c-Means聚類算法用來解決超大數據的分類問題。首先，改進Mapreduce機制下的MPI通信管理方法，采用成員管理協議方式實現成員管理與Mapreduce降低操作的同步化；其次，實行典型個體組降低操作代替全局個體降低操作，并定義二階段緩沖算法；最后，通過第一階段的緩沖進一步降低第二階段Mapreduce操作的數據量，盡可能降低大數據帶來的對算法負面影響。在此基礎上，利用人造大數據測試集和KDD CUP 99入侵測試集進行仿真，實驗結果表明，該算法既能保證聚類精度要求又可有效加快算法運行效率。

關鍵詞二階段模糊c-Means大數據聚類并行入侵檢測

0引言

如何從海量數據中排除干擾提取到有用數據，是一項有意義的工作[1]，而算法的運行效率是影響算法實際應用效果的關鍵因素[2,3]。聚類算法作為一種典型的數據挖掘算法，對大數據并行聚類算法的研究較多。文獻[4]設計并實現了Hadoop云計算平臺下基于Mapreduce模型的并行K-Means聚類算法；文獻[5]利用常值系數加權實現混合K-center和K-median加速并行聚類算法，并利用采樣來簡化樣本，思路不錯但單純的隨機樣本無法確保選中的數據充分代表整體數據，精度不理想；文獻[6]研究了協同聚類機制，并基于Hadoop平臺實現了大型分布數據的協同聚類；文獻[7]結合遺傳算法固有的并行特點，基于Hadoop平臺設計了并行遺傳K-Means聚類算法；文獻[8]的設計思想是以提高K-Means算法性能為目的，提高并行后K-Means算法聚類效果和性能。并行化K-Means算法已有諸多研究成果，相比而言c-Means算法并行化研究較少。

Hadoop平臺下的Mapreduce模型并行化算法加快了運行效率，但數據量過大時，Mapreduce模型采用的MPI通信模型存在較高的通信消耗。某種程度上抵消了并行所帶了的算法效率提升，對此提出一種成員管理協議來改進MPI通信模型，并利用個體貢獻值確定進行reduce操作的典型個體，以此改善文獻[5]隨機采樣的不具有代表性的弱點。本文的設計思想主要是通過上述方式并結合同步化管理協議實現c-Means算法的并行化設計，提出基于Hadoop二階段并行模糊c-Means聚類算法PGR-PFCM(Protocolgroup-reduceparallelfuzzyc-Meansclustingalgorithm)。

1改進Mapreduce模型

1.1模型介紹

Mapreduce模型是目前比較成熟的大數據分布式計算模型，同時也是大數據并行聚類算法實現的主要執行框架。Mapreduce名稱來源于該框架的兩個主要操作：map和reduce操作。map操作類似一種映射操作，是針對數據集所有成員的一種操作，map操作后返回結果列表。reduce操作針對map操作反饋的結果執行并行化的算法。Mapreduce模型如圖1所示。

圖1　Mapreduce模型

在Mapreduce模型中問題進程被分解為相互獨立可以并列運行的子進程，便于充分發揮計算機集群的計算性能。map和reduce操作框架的構建主要是根據數據中的key-value進行設計和操作：

Map:(k1,v1)→[(k2,v2)]

(1)

Reduce:(k2,[v2])→[(k3,v3)]

(2)

系統運行時管理主機會根據輸入數據斷點情況實時調度參與并行計算的計算機數量，同時通過管理主機也可以實時處理計算機故障問題。因此允許程序員在沒有操作經驗和硬件操作經驗的前提下較容易地使用大型分布式數據資源。

1.2典型個體操作方案

圖2　數據降低策略

文獻[10]提出這種基于組的典型個體降低策略可以通過定義在組上的MPI通信函數實現信息的交流。但是因為操作過程標識符列表會隨著迭代的進行不斷變化，即進行組降低的對象組合不斷改變，每次迭代都需要更改過程標識符列表。這樣通過MPI通信函數方式會增加過多的通信開銷。因為隨著迭代的增加重心能夠更好地接近聚類的中心，所以首先考慮只有一個重心并且只有一個過程子集的聚類模式。同時為了解決MPI通信函數時間占用比過高的問題，對傳統MPI通信模型設計了同步化的組成員管理協議來取代，并且這種基于組降低的操作可以并行相互獨立的在過程子集中同步進行，適合于并行算法的嵌入。

1.3同步化管理協議

典型個體動態分組成員管理協議(protocolgroup-reduce)通過將動態組成員管理的控制信息封裝在操作信息中。將pID列表進行廣播，并且隨著每個組降低操作進行同步修改，無需增加算法的額外通信開銷。protocolgroup-reduce操作步驟如下：

Step4步驟s時進程i,j進行信息交換，包含遠程和本地pID列表的合并，合并公式為Li,s + 1=Li,s⊕Lj,s。

Step5若進程pi貢獻值gi低于閾值Tmin則將該進程從pID列表中剔除。貢獻值[10]：

(3)

其中，Li為進程pi到重心的歐氏距離。

Step6外部的進程pm可通過異步發送貢獻值到本地組與組長接觸，包括pm對下一降低操作的貢獻度，以及添加該外部進程pm的ID到本地組mID中。如果組長接受進程pm則發送pID列表給進程pm。

Step7輸出結果mID。

2PGR-PFCM聚類算法

2.1模糊c-Means算法

(4)

滿足：

(5)

式(4)中‖·‖代表內積范數。模糊c-Means算法利用下面兩式對vj及uji值進行迭代從而實現最小化目標函數J的目的：

(6)

(7)

程序1PFCM算法偽代碼

1: %模糊c-Means算法(PFCM)偽代碼

2:FunctionP=PFCM();

3:randomisemy_uOld[j][i]foreachx[i]

4:do{

5:maxErr=0;

6:forj=1toc

7:myUsum[j]=0;

8:resetvectorsmy_v[j]to0;

9:resetmy_u[j][i]to0;

10:endfor;

11:fori=myid*(n/P)+1to(myid+1)*(n/P)

12:forj=1toc

13:updatemyUsum[j];

14:updatevectorsmy_v[j];

15:endfor;

16:endfor;

17:forj=1toc

18:Allreduce(myUsum[j],Usum[j],SUM);

19:Allreduce(my_v[j],v[j],SUM);

20:v[j] =v[j]/Usum[j];

21:endfor;

22:fori=myid*(n/P)+1to(myid+1)*(n/P)

23:forj=1toc

24:updatemy_u[j][i];

25:maxErr=max{|my_u[j][i]-my_uOld[j][i]|};

26:my_uOld[j][i] =my_u[j][i];

27:endfor;

28:endfor;

29:Allreduce(maxErr,Err,MAX);

30:}while(Err>=epsilon)

2.2PGR-PFCM聚類算法描述

使用一種類似于組合器(Combiner)的節點類型，在算法迭代過程中Mapper操作和reduce操作串聯執行，PGR-PFCM算法步驟如下：

Step1輸入參數。中間緩沖聚類數量Kt，聚類數量K，數據段長度L。

Step2Mapper操作。執行map(inValue,inKey,outValue,outKey)操作：

(a) 在inValue中加載聚類數據，執行map操作。

(b) 在outValue數據中執行PFCM(Kt)映射聚類操作。

(c) 按照聚類結果重新格式化outValue值。

(d) 輸出(outValue,outKey)。

Step3Reducer操作。執行同步化管理協議protocolgroup-reduce操作 (inValue,inKey,outValue,outKey)操作。

(a) 在inValue中加載Mapper操作的聚類中間結果，并執行protocolgroup-reduce操作。

(b) 在protocolgroup-reduce操作的聚類中間結果上執行PFCM(K)聚類操作。

(c) 輸出最終的聚類結果。

上述步驟中，參數Kt的取值直接決定了PGR-PFCM算法的運行速度和聚類質量。PGR-PFCM算法的第一個階段通過定義一個中間緩沖聚類數量Kt起到壓縮數據數量的作用。參數Kt的大小決定了PGR-PFCM算法第二階段輸入數據的大小，進而影響算法的運行速度和精度，Kt越大速度越慢精度越高，Kt越小速度越快精度越高。

3仿真結果與分析

硬件條件：基于Hadoop框架對算法進行仿真實驗，實驗硬件條件：節點數：16(由16臺計算機組成)，每臺計算機配置：Intel-Core2.0GHz,2GBRAM。

3.1算法加速度和運行時間

下面我們通過實驗方法研究PGR-PFCM算法的并行特性。對于給定的數據尺寸m×n，采用IBM數據生成器生成7組合成數據集[9]，表1給出了這些人造測試數據集的具體信息。

表1　數據集信息

首先對比不同數據集大小、不同尺寸、以及不同節點數的算法加速比及每次迭代所需時間。從表1可以看出測試數據集的大小從64MB至2048MB不等，小數據集形如d2其數據集大小為64MB。這樣的數據集可以加載到單一機器中進行處理時間消耗并不是很大，但是超大數據集如d30和d31，采用一臺機器進行數據處理則處理能力無法滿足要求。實驗采用算法加速度和每次迭代時間為主要指標，仿真結果如圖3所示。

圖3　實驗結果對比

圖3(a)反映的是算法每步迭代所需要的時間，顯然該時間隨著數據量及節點數的變化而變化，數據量越大處理速度越慢，節點數越多計算速度越快，但是并非呈線性關系，而是隨著節點的增加速度提升的效果越來越差，最后趨于平衡。圖3(b)反映的是加速度與節點數的關系，圖中顯示的是隨著節點數的增加，加速度增大，算法的運行時間縮短。圖3(c)反映的是加速度與數據集的關系，圖中看出節點數較小時算法的加速度隨數據維數的增加變化幅度不大，而節點數較多時，加速度隨數據集大小的變化趨勢逐漸明顯，從側面說明本文所提算法在多節點大數據集上運行的優勢。

3.2KDD CUP 99應用測試

在對上述提出的并行聚類算法進行評價時，這里借用入侵檢測的KDDCUP99數據庫[11,12]作為仿真對象。通過對該數據庫入侵數據的聚類檢測結果，來對比算法性能。KDDCUP99數據庫主要含有4種典型的網絡入侵數據：DOS、Probe、U2R和U2L。上述四種類型網絡入侵數據信息如表2所示。

表2　測試數據選取數量

常用到的入侵檢測評價指標主要是檢測率和錯檢率[13]。所謂檢測率是指聚類算法在入侵數據庫中正確歸類識別的入侵數據個數與數據庫中入侵數據總數的比值；錯檢率是指正常數據被錯誤歸類的數量與正常數據總量的比值。檢測率和錯檢率如下所示[14]：

(8)

(9)

對于表2選取的KDDCUP99測試集，選取K-meansⅡ、FPCM[15]及PGR-PFCM三種算法進行仿真對比，所有實驗運行30次求平均值。仿真結果如表3所示。

表3　分類結果對比(%)

表3分類結果對比分別給出K-meansⅡ、FPCM及PGR-PFCM三種算法，在KDDCUP99測試集上的聚類識別檢測率和錯檢率對比結果。由此可看出，在該測試數據庫的四種數據類別聚類識別中，PGR-PFCM算法在檢測率和錯檢率兩項評價指標上均要優于K-meansⅡ和FPCM算法。而K-meansⅡ和FPCM兩種算法相比，K-meansⅡ算法在U2R和U2L兩種數據上的聚類識別成功率要比FPCM算法高，而FPCM算法在U2L和DOS兩種數據上的聚類識別成功率要比K-meansⅡ算法高。綜合指標評價上，K-meansⅡ和FPCM兩種算法性能近似。因此，單純從聚類識別算法角度，PGR-PFCM算法是可行的，聚類性能要好于K-meansⅡ和FPCM算法。

為進一步驗證PGR-PFCM算法在KDDCUP99測試集上的普適性，選取ISVMID[16]和GANNID[17]兩種算法進行對比。實驗對象仍然基于KDDCUP99標準測試數據庫，相關參數如表2所示，仿真結果如圖4、圖5所示。

圖4　三種算法的檢測率對比

圖5　三種算法的錯測率對比

圖4分別給出PGR-PFCM、ISVMID和GANNID三種算法在KDDCUP99測試集上的入侵數據檢測率對比情況。可以看出，PGR-PFCM算法在KDDCUP99測試集四種類型數據上的檢測準確率要比ISVMID和GANNID兩種算法要高。而ISVMID和GANNID兩種算法相比，在DOS和U2R兩種入侵類型中，ISVMID要優于GANNID算法，而在U2L和Probe兩種入侵類型中，GANNID要優于ISVMID算法。圖5給出PGR-PFCM、ISVMID和GANNID三種算法錯檢率對比結果。可以看出，PGR-PFCM算法在DOS、Probe、U2R和U2L四種數據上的錯檢率要低于ISVMID和GANNID算法，其中在U2R、Probe和U2L三種入侵數據中，ISVMID算法錯檢率高于GANNID算法。通過對比分析可知，PGR-PFCM算法對入侵數據檢測是高效的。

4結語

本文建立了基于Hadoop二階段并行模糊c-Means聚類算法用來處理大數據聚類，并采用基于協議的組典型個體降低策略來改善Mapreduce的MPI通信模型的算法時間復雜度，以提高算法的整體運行效率。通過有選擇的組降低算法能夠有效排除不良數據項的干擾，因而PGR-PFCM算法具有更高的運行效率和聚類成功率。在并行率和加速比方面，PGR-PFCM算法在大規模數據集上的并行率和加速比都優于小型數據集上的表現，說明了PGR-PFCM算法能夠實時根據數據量的大小對自身進行調整。最后通過在KDDCUP99入侵數據測試集上的對比仿真結果，表明PGR-PFCM算法同樣適用處理實際環境下的大數據聚類問題。

參考文獻

[1]DaiL,ChenT,XuHK.ResearchontestingTechniqueofbigdata[J].ApplicationResearchofComputers,2014,31(6):1606-1611.

[2] 王珊,王會舉,覃雄派.架構大數據:挑戰、現狀與展望[J].計算機學報,2011,34(10):1741-1752.

[3]MeglerVM,MaierD.Whenbigdataleadstolostdata[C]//Procofthe5thInternationalConferenceonInformationandKnowledgeManagement.NewYork:ACMPress,2012:1-8.

[4] 趙衛中,馬慧芳,傅燕翔.基于云計算平臺Hadoop的并行K-means聚類算法設計研究[J].計算機科學,2011,38(10):166-169.

[5]EneA,ImS,MoseleyB.FastclusteringusingMapRe-duce[C]//Procofthe17thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining,California,USA:ACMPress,2011:681-689.

[6]PapadimitriouS,SunJ.DisCo:DistributedCo-clusteringwithMap-Reduce:ACaseStudyTowardsPetabyte-ScaleEnd-to-EndMining[C]//Procofthe8thIEEEInterna-tionalConferenceonDataMining.Pisa,Italy:IEEEPress,2008:512-521.

[7] 陸秋,程小輝.基于Mapreduce的決策樹算法并行化[J].計算機應用,2012,32(9):2463-2465.

[8]BahmaniB,MoseleyB,VattaniA.Scalablek-means++[J].ProceedingsoftheVLDBEndowment,2012,5(7):622-633.

[9]MiaoYQ,ZhangJX,FengH.AFastAlgorithmforClusteringwithMapreduce[J].AdvancesinNeuralNet-works,2013,17(11):532-538.

[10]DavidP,GiuseppeDF.EfficientGroupCommunicationforLarge-ScaleParallelClustering[J].IntelligentDistributedComputing,2013,446:155-164.

[11]MengYX,LiWJ.Towardsadaptivecharacterfrequency-basedexclusivesignaturematchingschemeanditsapplicationsindistributedintrusiondetection[J].ComputerNetworks,2013,57(17):3630-3640.

[12]HassanzadehA,XuZY,RaduS.PRIDE:PracticalIntrusionDetectioninResourceConstrainedWirelessMeshNetworks[J].InformationandCommunicationsSecurity,2013,23(3):213-228.

[13]ShakshukiEM,SheltamiTR.EAACK—ASecureIntrusion-DetectionSystemforMANETs[J].IEEETransactionsonIndustrialElectronics,2013,60(3):1089-1098.

[14]ChiragM,DhirenP,BhaveshB.Asurveyofintrusiondetectiontechniquesincloud[J].JournalofNetworkandComputerApplications,2013,36(1):42-57.

[15]TerenceK,KateS,SebastianL.ParallelFuzzyc-MeansClusteringforLargeDataSets[C]//8thInternationalEuro-ParConferencePaderborn,Germany:Springer,2002:27-30.

[16] 譚愛平,陳浩,吳伯橋.基于SVM的網絡入侵檢測集成學習算法[J].計算機科學,2014,41(2):196-200.

[17] 陳鴻星.基于遺傳優化神經網絡的網絡入侵特征檢測[J].計算機工程與應用,2014,50(14):78-81.

HADOOP-BASED TWO-STAGE PARALLEL FUZZY C-MEANS CLUSTERING ALGORITHM

Hu JichaoHuang Hongyan

(School of Information Engineering,Shijiazhuang University of Economics,Shijiazhuang 050031,Hebei,China)

AbstractAiming at the problem of too high occupancy of communication time and limited applying value of the algorithm under the mechanism of Mapreduce, we put forward a Hadoop-based two-stage parallel c-Means clustering algorithm to deal with the problem of extra-large data classification. First, we improved the MPI communication management method in Mapreduce mechanism, and used membership management protocol mode to realise the synchronisation of members management and Mapreduce reducing operation. Secondly, we implemented typical individuals group reducing operation instead of global individual reducing operation, and defined the two-stage buffer algorithm. Finally, through the buffer in first stage we further reduced the data amount of Mapreduce operation in second stage, and reduced the negative impact brought about by big data on the algorithm as much as possible. Based on this, we carried out the simulation by using artificial big data test set and KDD CUP 99 invasion test data.Experimental result showed that the algorithm could both guarantee the clustering precision requirement and speed up effectively the operation efficiency of algorithm.

KeywordsTwo-stageFuzzy c-MeansBig dataClusteringParallelIntrusion detection

收稿日期：2014-11-10。河北省科技廳科技攻關項目(132101 30)。胡吉朝，講師，主研領域：數據挖掘，智能計算。黃紅艷，講師。

中圖分類號TP312

文獻標識碼A

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