李小川 劉媛華

摘 要：針對(duì)Kmeans算法對(duì)海量數(shù)據(jù)聚類效率過(guò)低的不足，基于Hadoop的分布式架構(gòu)思想，提出一種多核果蠅-Kmeans聚類算法（MKFOA-Kmeans）。以每次迭代后果蠅位置為聚類中心進(jìn)行一次Kmeans聚類算法，綜合了果蠅優(yōu)化算法強(qiáng)全局搜索能力以及Kmeans算法強(qiáng)局部搜索能力的優(yōu)點(diǎn)。MapReduce框架簡(jiǎn)化了算法執(zhí)行過(guò)程，避免了由于存儲(chǔ)空間不足而造成的算法失效。在由普通硬件搭建的Hadoop平臺(tái)下進(jìn)行仿真實(shí)驗(yàn)，表明MKFOA-Kmeans算法對(duì)大數(shù)據(jù)的聚類準(zhǔn)確率高，并且隨著數(shù)據(jù)量的增加，聚類效率優(yōu)勢(shì)也愈加明顯。

關(guān)鍵詞：大型數(shù)據(jù)聚類；Hadoop；果蠅算法；多核；Kmeans算法

DOI：10.11907/rjdk.172611

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）004-0051-03

Abstract：In order to overcome the disadvantage of low efficiency of massive data clustering of the Kmeans algorithm， a multi-kernel FOA-Kmeans clustering algorithm based on Hadoop is proposed. Using the positions of artificial flys as the clustering center， the new algorithm combines the strong global searching ability of the fly optimization algorithm and the strong local searching ability of the Kmeans algorithm. The MapReduce programming framework simplifies the execution of the algorithm and avoids the failure of the algorithm due to insufficient storage space of computer. Simulations on Hadoop platform constructed by common computers show that MKFOA-Kmeans algorithm has high accuracy for massive data clustering， and the clustering efficiency becomes more obvious with the increase of data.

Key Words：massive data clustering； Hadoop； fly optimization algorithm； multiple kernels； Kmeans Algorithm

0 引言

隨著移動(dòng)互聯(lián)網(wǎng)等信息科技的快速發(fā)展，數(shù)據(jù)量級(jí)呈爆炸式增長(zhǎng)，如何挖掘并利用有效數(shù)據(jù)成為各界關(guān)注的熱點(diǎn)。聚類是數(shù)據(jù)挖掘中一個(gè)重要的方向，通過(guò)無(wú)監(jiān)督學(xué)習(xí)確定合適的聚類中心，使其類內(nèi)間距盡量小而類間間距盡量大。Kmeans算法因原理簡(jiǎn)單、局部搜索能力強(qiáng)等優(yōu)點(diǎn)而成為經(jīng)典的聚類算法，但其全局搜索能力較差，容易陷入局部最優(yōu)值，尤其在對(duì)大型數(shù)據(jù)聚類時(shí)效率過(guò)低，算法滯慢劣勢(shì)明顯。很多學(xué)者對(duì)Kmeans算法進(jìn)行了改進(jìn)，文獻(xiàn)[2]在粒子群算法中引入小概率變異事件，以有效克服Kmeans算法后期收斂速度慢的缺陷。文獻(xiàn)[3]將蟻群算法的搜索方向性與Kmeans算法結(jié)合，成功應(yīng)用在系統(tǒng)協(xié)同分類中，但搜索速度較慢。文獻(xiàn)[4]提出一種基于人工蜂群的Kmeans算法，提高了全局搜索能力，但在處理大型數(shù)據(jù)時(shí)效率較低。近年來(lái)，針對(duì)海量數(shù)據(jù)的Kmeans算法改進(jìn)研究越來(lái)越多，文獻(xiàn)[5]提出了基于Hadoop平臺(tái)的Canopy和Kmeans混合算法，在處理大型新聞數(shù)據(jù)時(shí)取得了較好的效果。文獻(xiàn)[6]提出一種基于改進(jìn)蜂群的Kmeans算法，在Hadoop平臺(tái)下運(yùn)行具有良好的可擴(kuò)展性。

果蠅算法是一種基于生物學(xué)仿生的新型智能優(yōu)化算法，具有參數(shù)少、收斂快、全局搜索能力強(qiáng)等優(yōu)點(diǎn)，目前已經(jīng)成功應(yīng)用在函數(shù)優(yōu)化、紡絲性能預(yù)測(cè)[7]、作業(yè)車間調(diào)度[8]、變壓器故障診斷[9]等領(lǐng)域。本文采用自適應(yīng)步長(zhǎng)改進(jìn)果蠅算法與Kmeans算法結(jié)合，根據(jù)MapReduce編程模型設(shè)計(jì)適合在Hadoop平臺(tái)運(yùn)行的算法流程，綜合了果蠅算法的強(qiáng)全局搜索能力，Kmeans算法的強(qiáng)局部搜索能力以及Hadoop分布式框架的并行搜索效率，為海量數(shù)據(jù)的聚類方法提供了一種新思路。

1 相關(guān)方法

1.1 Kmeans聚類算法

1.2 果蠅優(yōu)化算法

1.3 Hadoop平臺(tái)

Hadoop平臺(tái)是由多個(gè)普通硬件構(gòu)成的分布式運(yùn)行環(huán)境，其目標(biāo)是建立一個(gè)并行處理大數(shù)據(jù)的可擴(kuò)展軟件框架[13]，運(yùn)行環(huán)境主要包括HDFS和MapReduce組件。HDFS是Google分布式文件系統(tǒng)，具有低成本、高容量、高穩(wěn)定性等特點(diǎn)；MapReduce是一個(gè)編程模型，以計(jì)算機(jī)集群為平臺(tái)，編寫處理大數(shù)據(jù)的并行化程序。Map Reduce執(zhí)行過(guò)程分為Map和Reduce兩個(gè)階段，Map對(duì)輸入的鍵值對(duì)（key-value）進(jìn)行分割并處理后輸出結(jié)果，Reduce以Map的輸出作為輸入進(jìn)行程序處理后輸出最終結(jié)果，MapReduce的執(zhí)行模型如圖1所示：

2 基于Hadoop的MKFOA-Kmeans算法

2.1 MKFOA-Kmeans算法與算法編碼

果蠅優(yōu)化算法中，當(dāng)果蠅群體完成靠嗅覺(jué)覓食的階段后，所有果蠅飛向味道濃度最大的果蠅，將味道濃度最大的果蠅抽象為一個(gè)中心點(diǎn)，則該過(guò)程可以理解為果蠅群體向中心聚集。

根據(jù)上述觀點(diǎn)，對(duì)果蠅算法進(jìn)行改進(jìn)，選取味道濃度總和最大的k只果蠅作為聚類中心，其它果蠅以距離判定準(zhǔn)則劃分到相應(yīng)的類中，提出基于多核果蠅-Kmeans算法。設(shè)樣本數(shù)據(jù)為S={sDi|i=1，2，…n}，從中隨機(jī)選取k個(gè)數(shù)據(jù)作為初始果蠅種群，編碼方式如下：

2.2 適應(yīng)度函數(shù)

采用Kmeans算法聚類時(shí)，類內(nèi)數(shù)據(jù)個(gè)數(shù)多且類內(nèi)間距小的聚類結(jié)果較優(yōu)，由此構(gòu)造如下適應(yīng)度函數(shù)：

式（8）～（9）中，CNi為第i個(gè)類內(nèi)的數(shù)據(jù)個(gè)數(shù)，CDi為第i個(gè)類內(nèi)數(shù)據(jù)與聚類中心之間的距離和，V為聚類結(jié)果評(píng)價(jià)量。

2.3 基于Hadoop的MKFOA-Kmeans算法步驟

果蠅-Kmeans算法在對(duì)大型數(shù)據(jù)進(jìn)行聚類時(shí)仍存在計(jì)算內(nèi)存不足、收斂速度慢等問(wèn)題，為解決以上問(wèn)題，根據(jù)MapReduce編程模型對(duì)算法進(jìn)行并行化處理，計(jì)算步驟如下：

Step1初始化各參數(shù)，輸入待聚類數(shù)據(jù)樣本，設(shè)置聚類數(shù)k，最大迭代次數(shù)G，果蠅基本步長(zhǎng)ld，當(dāng)前迭代t=1。

Step2 隨機(jī)選擇樣本中的k個(gè)數(shù)據(jù)作為初始果蠅群體。

Step3 啟動(dòng)MapTask1，以樣本數(shù)據(jù)索引號(hào)以及聚類中心（果蠅群體坐標(biāo)）索引號(hào)作為key輸入，樣本數(shù)據(jù)距各聚類中心距離作為value輸出；啟動(dòng)ReduceTask1，以MapTask1的輸出作為輸入，根據(jù)距離判斷原則進(jìn)行聚類，輸出聚類結(jié)果。

Step4 啟動(dòng)MapTask2，以聚類中心索引號(hào)作為key輸入，根據(jù)公式（8）計(jì)算每個(gè)類的適應(yīng)值作為value輸出；ReduceTask2以MapTask2的輸出作為輸入，輸出最佳果蠅個(gè)體，記錄最佳果蠅個(gè)體和聚類結(jié)果評(píng)價(jià)量V。

Step5 對(duì)除最佳果蠅個(gè)體外的其它果蠅進(jìn)行迭代尋優(yōu)，啟動(dòng)MapTask3，以聚類中心索引號(hào)作為key輸入，由公式（2）計(jì)算移動(dòng)步長(zhǎng)L并作為value輸出；啟動(dòng)ReduceTask3，以MapTask3的輸出作為輸入，由公式（2）更新果蠅的位置。

Step6 令t=t+1，轉(zhuǎn)Step3，若V（t）>V（t-1），則執(zhí)行Step5，否則果蠅群體回滾到t-1代的果蠅群體后執(zhí)行Step5。

Step7 若t>G，則算法結(jié)束，輸出聚類結(jié)果，否則轉(zhuǎn)Step3繼續(xù)迭代。

3 仿真實(shí)驗(yàn)結(jié)果及分析

3.1 仿真實(shí)驗(yàn)環(huán)境

本文算法運(yùn)行環(huán)境為四臺(tái)單核處理器，4GB內(nèi)存，300GB硬盤，CentOS7.0操作系統(tǒng)的PC機(jī)搭建的Hadoop計(jì)算機(jī)集群，Hadoop版本為2.6.0，JDK版本為1.7.0。其中一臺(tái)作為NameNode，另外3臺(tái)作為DataNode。

3.2 仿真實(shí)驗(yàn)1

為驗(yàn)證本文所提MKFOA-Kmeans算法及其在Hadoop平臺(tái)上進(jìn)行聚類的可行性和準(zhǔn)確性，首先選取5個(gè)不同大小和維數(shù)的UCI標(biāo)準(zhǔn)數(shù)據(jù)集（如表1所示）進(jìn)行實(shí)驗(yàn)，每種算法獨(dú)立運(yùn)行20次。

由表2可見(jiàn)，在對(duì)4個(gè)不同的數(shù)據(jù)集進(jìn)行聚類時(shí)，MKFOA-Kmeans和基于Hadoop平臺(tái)的MKFOA-Kmeans的聚類準(zhǔn)確性差別不大，但均明顯高于Kmeans算法的聚類準(zhǔn)確性，說(shuō)明本文改進(jìn)的Kmeans算法在數(shù)據(jù)聚類方面具有較好的可行性。

3.3 仿真實(shí)驗(yàn)2

通過(guò)實(shí)驗(yàn)1已經(jīng)驗(yàn)證了MKFOA-Kmeans和Hadoop-MKFOA-Kmeans的聚類可行性與準(zhǔn)確性，但是測(cè)試集數(shù)據(jù)量均相對(duì)較小，為了更好地驗(yàn)證Hadoop-MKFOA-Kmeans在對(duì)海量數(shù)據(jù)進(jìn)行聚類的優(yōu)勢(shì)，本文隨機(jī)生成6個(gè)類數(shù)和維數(shù)相同但數(shù)據(jù)量不同的數(shù)據(jù)集（如表3所示）進(jìn)行實(shí)驗(yàn)，并與文獻(xiàn)[6]所提的ACO-Kmeans算法聚類結(jié)果進(jìn)行對(duì)比，每種算法獨(dú)立運(yùn)行20次。

由表4可知，對(duì)于DataBase1與DataBase2而言，基于Hadoop平臺(tái)的并行算法運(yùn)行時(shí)間要大于Kmeans和MCFOA-Kmeans，這是因?yàn)閷?duì)于較小數(shù)據(jù)集的聚類，Hadoop分布式計(jì)算機(jī)集群不斷讀寫花費(fèi)的時(shí)間要大于算法實(shí)際運(yùn)行時(shí)間。隨著數(shù)據(jù)量的不斷增大，基于Hadoop平臺(tái)并行計(jì)算的效率優(yōu)勢(shì)也愈發(fā)明顯。對(duì)于DataBase5與DataBase6，由于計(jì)算機(jī)內(nèi)存溢出導(dǎo)致Kmeans和MCFOA-Kmeans算法失效，基于Hadoop平臺(tái)的兩種算法均可執(zhí)行聚類過(guò)程，但本文提到的基于Hadoop的MCFOA-Kmeans算法平均運(yùn)行時(shí)間要略少于文獻(xiàn)[6]所提到的算法。總體而言，本文所提的基于Hadoop的MCFOA-Kmeans算法在對(duì)海量數(shù)據(jù)進(jìn)行聚類時(shí)表現(xiàn)出了較優(yōu)的性能。

4 結(jié)語(yǔ)

本文首次將果蠅算法應(yīng)用在數(shù)據(jù)聚類領(lǐng)域，重新設(shè)計(jì)了擁有多個(gè)互相獨(dú)立的最優(yōu)果蠅多核果蠅優(yōu)化算法，并將其與Kmeans算法結(jié)合，提出了基于Hadoop平臺(tái)的多核果蠅-Kmeans算法，解決了Kmeans算法對(duì)海量數(shù)據(jù)聚類效率低甚至失效的不足。在Hadoop搭建的計(jì)算機(jī)集群上對(duì)UCI庫(kù)中的數(shù)據(jù)集和隨機(jī)生成的不同規(guī)模數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，表明本文所提算法在處理海量數(shù)據(jù)時(shí)具有較高的效率與準(zhǔn)確性，為海量數(shù)據(jù)有效聚類提供了一種思路。

參考文獻(xiàn)：

[1] 周麗娟，王慧，王文伯，等.面向海量數(shù)據(jù)的并行KMeans算法[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，40（S1）：150-152.

[2] 陶新民，徐晶，楊立標(biāo)，等.一種改進(jìn)的粒子群和K均值混合聚類算法[J].電子與信息學(xué)報(bào)，2010，32（1）：92-97.

[3] 莫贊，羅世雄，楊清平，等.基于K-means算法的改進(jìn)蟻群聚類算法及其應(yīng)用[J].系統(tǒng)科學(xué)學(xué)報(bào)，2012，20（3）：91-95.

[4] 喻金平，鄭杰，梅宏標(biāo).基于改進(jìn)人工蜂群算法的K均值聚類算法[J].計(jì)算機(jī)應(yīng)用，2014，34（4）：1065-1069+1088.

[5] 趙慶.基于Hadoop平臺(tái)下的Canopy-Kmeans高效算法[J].電子科技，2014，27（2）：29-31.

[6] 虞倩倩，戴月明，李晶晶.基于MapReduce的ACO-Kmeans并行聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（16）：117-120+136.

[7] 郭凡，丁永生，郝礦榮，等.基于果蠅算法優(yōu)化支持向量回歸機(jī)的紡絲性能預(yù)測(cè)[J].系統(tǒng)仿真學(xué)報(bào)，2014，26（10）：2360-2364.

[8] 潘玉霞，謝光，桑紅燕，等.雙目標(biāo)流水線調(diào)度的動(dòng)態(tài)雙子群離散果蠅算法[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（12）：140-146.

[9] 李宗岳，陳志軍，李名遠(yuǎn).基于改進(jìn)FOA-LSSVM的變壓器故障診斷[J].水電能源科學(xué)，2016，34（4）：194-197.

[10] 沈泓，劉順.基于K-means聚類算法的數(shù)據(jù)分析模型應(yīng)用研究[J].軟件導(dǎo)刊，2017，16（3）：103-107.

[11] PAN W T.Using modified fruit fly optimisation algo-rithm to perform the function test and case studies[J].Connection Science，2013，25（2/3）：151-160.

[12] YUAN X F，DAI X，ZHAO J Y，et al.On a novel multi-swarm fruit fly optimization algorithm and its application[J].Applied Mathematics and Computation，2014，233（5）：260-271.

[13] 王彥明，奉國(guó)和，薛云.近年來(lái)Hadoop國(guó)外研究綜述[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2013，22（6）：1-5+28.

（責(zé)任編輯：劉亭亭）