基于Hadoop二階段并行模糊c-Means聚類(lèi)算法

胡吉朝　黃紅艷

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

?

基于Hadoop二階段并行模糊c-Means聚類(lèi)算法

胡吉朝黃紅艷

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

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

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

0引言

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

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

1改進(jìn)Mapreduce模型

1.1模型介紹

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

圖1　Mapreduce模型

在Mapreduce模型中問(wèn)題進(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í)通過(guò)管理主機(jī)也可以實(shí)時(shí)處理計(jì)算機(jī)故障問(wèn)題。因此允許程序員在沒(méi)有操作經(jīng)驗(yàn)和硬件操作經(jīng)驗(yàn)的前提下較容易地使用大型分布式數(shù)據(jù)資源。

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

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

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

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

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

Step4步驟s時(shí)進(jìn)程i,j進(jìn)行信息交換，包含遠(yuǎn)程和本地pID列表的合并，合并公式為L(zhǎng)i,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可通過(guò)異步發(fā)送貢獻(xiàn)值到本地組與組長(zhǎng)接觸，包括pm對(duì)下一降低操作的貢獻(xiàn)度，以及添加該外部進(jìn)程pm的ID到本地組mID中。如果組長(zhǎng)接受進(jìn)程pm則發(fā)送pID列表給進(jìn)程pm。

Step7輸出結(jié)果mID。

2PGR-PFCM聚類(lèi)算法

2.1模糊c-Means算法

(4)

滿足：

(5)

式(4)中‖·‖代表內(nèi)積范數(shù)。模糊c-Means算法利用下面兩式對(duì)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聚類(lèi)算法描述

使用一種類(lèi)似于組合器(Combiner)的節(jié)點(diǎn)類(lèi)型，在算法迭代過(guò)程中Mapper操作和reduce操作串聯(lián)執(zhí)行，PGR-PFCM算法步驟如下：

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

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

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

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

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

(d) 輸出(outValue,outKey)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(8)

(9)

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

表3　分類(lèi)結(jié)果對(duì)比(%)

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

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

圖4　三種算法的檢測(cè)率對(duì)比

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

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

4結(jié)語(yǔ)

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

參考文獻(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ì)算平臺(tái)Hadoop的并行K-means聚類(lèi)算法設(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的決策樹(shù)算法并行化[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] 譚愛(ài)平,陳浩,吳伯橋.基于SVM的網(wǎng)絡(luò)入侵檢測(cè)集成學(xué)習(xí)算法[J].計(jì)算機(jī)科學(xué),2014,41(2):196-200.

[17] 陳鴻星.基于遺傳優(yōu)化神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)入侵特征檢測(cè)[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ì)算。黃紅艷，講師。

中圖分類(lèi)號(hào)TP312

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

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