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

胡吉朝　黃紅艷

(石家莊經(jīng)濟(jì)學(xué)院信息工程學(xué)院　河北 石家莊 050031)

?

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

胡吉朝黃紅艷

(石家莊經(jīng)濟(jì)學(xué)院信息工程學(xué)院河北 石家莊 050031)

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

關(guān)鍵詞二階段模糊c-Means大數(shù)據(jù)聚類并行入侵檢測

0引言

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

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

1改進(jìn)Mapreduce模型

1.1模型介紹

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

圖1　Mapreduce模型

在Mapreduce模型中問題進(jìn)程被分解為相互獨(dú)立可以并列運(yùn)行的子進(jìn)程，便于充分發(fā)揮計(jì)算機(jī)集群的計(jì)算性能。map和reduce操作框架的構(gòu)建主要是根據(jù)數(shù)據(jù)中的key-value進(jìn)行設(shè)計(jì)和操作：

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

(1)

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

(2)

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

1.2典型個(gè)體操作方案

圖2　數(shù)據(jù)降低策略

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

1.3同步化管理協(xié)議

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

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

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

(3)

其中，Li為進(jìn)程pi到重心的歐氏距離。

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

Step7輸出結(jié)果mID。

2PGR-PFCM聚類算法

2.1模糊c-Means算法

(4)

滿足：

(5)

式(4)中‖·‖代表內(nèi)積范數(shù)。模糊c-Means算法利用下面兩式對vj及uji值進(jìn)行迭代從而實(shí)現(xiàn)最小化目標(biāo)函數(shù)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)的節(jié)點(diǎn)類型，在算法迭代過程中Mapper操作和reduce操作串聯(lián)執(zhí)行，PGR-PFCM算法步驟如下：

Step1輸入?yún)?shù)。中間緩沖聚類數(shù)量Kt，聚類數(shù)量K，數(shù)據(jù)段長度L。

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

(a) 在inValue中加載聚類數(shù)據(jù)，執(zhí)行map操作。

(b) 在outValue數(shù)據(jù)中執(zhí)行PFCM(Kt)映射聚類操作。

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

(d) 輸出(outValue,outKey)。

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

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

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

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

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

3仿真結(jié)果與分析

硬件條件：基于Hadoop框架對算法進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)硬件條件：節(jié)點(diǎn)數(shù)：16(由16臺計(jì)算機(jī)組成)，每臺計(jì)算機(jī)配置：Intel-Core2.0GHz,2GBRAM。

3.1算法加速度和運(yùn)行時(shí)間

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

表1　數(shù)據(jù)集信息

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

圖3　實(shí)驗(yàn)結(jié)果對比

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

3.2KDD CUP 99應(yīng)用測試

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

表2　測試數(shù)據(jù)選取數(shù)量

常用到的入侵檢測評價(jià)指標(biāo)主要是檢測率和錯(cuò)檢率[13]。所謂檢測率是指聚類算法在入侵?jǐn)?shù)據(jù)庫中正確歸類識別的入侵?jǐn)?shù)據(jù)個(gè)數(shù)與數(shù)據(jù)庫中入侵?jǐn)?shù)據(jù)總數(shù)的比值；錯(cuò)檢率是指正常數(shù)據(jù)被錯(cuò)誤歸類的數(shù)量與正常數(shù)據(jù)總量的比值。檢測率和錯(cuò)檢率如下所示[14]：

(8)

(9)

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

表3　分類結(jié)果對比(%)

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

為進(jìn)一步驗(yàn)證PGR-PFCM算法在KDDCUP99測試集上的普適性，選取ISVMID[16]和GANNID[17]兩種算法進(jìn)行對比。實(shí)驗(yàn)對象仍然基于KDDCUP99標(biāo)準(zhǔn)測試數(shù)據(jù)庫，相關(guān)參數(shù)如表2所示，仿真結(jié)果如圖4、圖5所示。

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

圖5　三種算法的錯(cuò)測率對比

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

4結(jié)語

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

參考文獻(xiàn)

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

[2] 王珊,王會(huì)舉,覃雄派.架構(gòu)大數(shù)據(jù):挑戰(zhàn)、現(xiàn)狀與展望[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1741-1752.

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

[4] 趙衛(wèi)中,馬慧芳,傅燕翔.基于云計(jì)算平臺Hadoop的并行K-means聚類算法設(shè)計(jì)研究[J].計(jì)算機(jī)科學(xué),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].計(jì)算機(jī)應(yīng)用,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的網(wǎng)絡(luò)入侵檢測集成學(xué)習(xí)算法[J].計(jì)算機(jī)科學(xué),2014,41(2):196-200.

[17] 陳鴻星.基于遺傳優(yōu)化神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)入侵特征檢測[J].計(jì)算機(jī)工程與應(yīng)用,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。河北省科技廳科技攻關(guān)項(xiàng)目(132101 30)。胡吉朝，講師，主研領(lǐng)域：數(shù)據(jù)挖掘，智能計(jì)算。黃紅艷，講師。

中圖分類號TP312

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

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