基于Hadoop的多核果蠅—Kmeans聚類算法

李小川 劉媛華

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

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

DOI：10.11907/rjdk.172611

中圖分類號：TP312

文獻標識碼：A 文章編號：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 引言

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

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

1 相關(guān)方法

1.1 Kmeans聚類算法

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

1.3 Hadoop平臺

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

2 基于Hadoop的MKFOA-Kmeans算法

2.1 MKFOA-Kmeans算法與算法編碼

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

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

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

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

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

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

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

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

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

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

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

Step5 對除最佳果蠅個體外的其它果蠅進行迭代尋優(yōu)，啟動MapTask3，以聚類中心索引號作為key輸入，由公式（2）計算移動步長L并作為value輸出；啟動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 仿真實驗結(jié)果及分析

3.1 仿真實驗環(huán)境

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

3.2 仿真實驗1

為驗證本文所提MKFOA-Kmeans算法及其在Hadoop平臺上進行聚類的可行性和準確性，首先選取5個不同大小和維數(shù)的UCI標準數(shù)據(jù)集（如表1所示）進行實驗，每種算法獨立運行20次。

由表2可見，在對4個不同的數(shù)據(jù)集進行聚類時，MKFOA-Kmeans和基于Hadoop平臺的MKFOA-Kmeans的聚類準確性差別不大，但均明顯高于Kmeans算法的聚類準確性，說明本文改進的Kmeans算法在數(shù)據(jù)聚類方面具有較好的可行性。

3.3 仿真實驗2

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

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

4 結(jié)語

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

參考文獻：

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

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

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

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

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

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

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

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

[9] 李宗岳，陳志軍，李名遠.基于改進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] 王彥明，奉國和，薛云.近年來Hadoop國外研究綜述[J].計算機系統(tǒng)應(yīng)用，2013，22（6）：1-5+28.

（責任編輯：劉亭亭）