基于MapReduce模型的并行遺傳k－means聚類算法

賈瑞玉，管玉勇，李亞龍

（安徽大學 計算機科學與技術學院，安徽 合肥230601）

0 引 言

K－means算法是聚類算法中劃分聚類的一種，由于算法簡單且高效，因此得到了普遍的應用。但是k－means算法的聚類結果的準確性不是很高，計算量較大，對初始化中心較為敏感［1］。目前有許多針對k－means算法的研究，文獻［2］主要針對k－means算法對初始聚類中心敏感提出基于密度的改進算法。文獻［3］提出了自動獲取最佳k值的算法。文獻［4］將并行的遺傳算法和k－means算法相結合，優(yōu)化聚類的結果和k值。文獻［5］將k－means算法放在Hadoop平臺下進行并行化設計可以提高算法運行的時間效率以及改善最后的聚類結果。將遺傳算法加入到k－means算法中去可以明顯的改善k－means算法的性能［6］，但是串行的算法會增加程序運行的時間。因此，有必要對其進行并行化設計。

傳統(tǒng)的基于MPI或PVM 的并行化設計，不僅需要對計算機的體系結構有較好地認識，實現(xiàn)起來也比較困難，而且節(jié)點之間的通信開銷會占據(jù)較多的時間［7］。相對于此，MapReduce并行化模型不需要編程人員去考慮體系結構方面的細節(jié)知識，實現(xiàn)起來較為容易，而且節(jié)點之間的通行時間也會減少。因此，目前基于MapReduce模型的并行化設計是當前的研究熱點之一，文獻 ［8－10］分別從不同方面研究了遺傳算法的MapReduce并行化設計，但主要都是基于遺傳算法粗粒度并行化模型進行設計。將遺傳k－means算法進行并行化設計不僅可以提高算法執(zhí)行的時間效率，在一定程度上還可以防止早熟現(xiàn)象的發(fā)生，從而提高聚類的效果。

1 遺傳k－means聚類算法

k－means聚類算法雖然簡單、通用，但是對初始聚類中心的選擇較為敏感，所以需要對初始聚類中心的選擇進行優(yōu)化。遺傳算法是一種智能搜索算法，它不依賴于問題的本身，所需要的僅是通過事先設定的適應度函數(shù)，對算法產(chǎn)生的染色體進行評價，使適應度高的染色體得到更好的繁殖機會。算法的終止條件是事先設定的最大遺傳代數(shù)或者是達到最佳適應度值。將遺傳算法加入到k－means算法中去，利用遺傳算法的優(yōu)勢可以較好地克服k－means算法的一些不足。

遺傳k－means聚類算法具體的做法是：將各個聚類中心坐標作為染色體的基因，染色體的長度等于聚類中心的個數(shù)；然后初始化若干個相異的染色體作為一個種群進行遺傳操作；最后得到適應度最大的染色體，解析出各個中心點的坐標即可以認為是最佳的聚類中心坐標。算法的主要步驟如下：

（1）初始化運行參數(shù) （種群個數(shù)p，聚類個數(shù)k，最大遺傳代數(shù)）。

（2）初始化種群即隨機產(chǎn)生p個染色體，每個染色體表示一個聚類的結果。

（3）對每個染色體進行k－means操作，然后評價其適應度并記錄。

（4）判斷是否達到結束條件 （滿足最大代數(shù)或問題最優(yōu)解），未滿足則進行以下操作：

1）選擇操作

2）交叉操作

3）變異操作

（5）轉到步驟 （3）。

1.1 適應度函數(shù)設計

遺傳聚類算法中的每一個染色體表示一個聚類的結果，而判斷一個聚類結果的好壞標準是要求各個劃分集合之間的聯(lián)系要松散而集合內(nèi)的各個數(shù)據(jù)對象間的聯(lián)系要緊密。所以適應度函數(shù)設計為

其中，分子表示一個染色體中各個聚類中心之間的最大距離；分母表示各個集合中的數(shù)據(jù)點到其中心點的距離總和。

1.2 遺傳算子

選擇算子：為保護最優(yōu)個體可以代代相傳，采用無條件保留種群中的最優(yōu)個體復制到下一代，用來替換新種群中的最差個體。同時對于種群中的其它個體采用概率選擇的方法復制到下一代：適應度較大的個體有較大的機會復制到下一代中。

選擇概率

其中，分子表示個體的適應度值，分母表示種群中所有個體的適應度值之和。

交叉算子：對種群中的n 個個體隨機選擇兩兩配對，進行交叉操作。本文采用基于最短基因距離的單點交叉策略。

變異算子：種群中的個體變異可以維護種群的多樣性，也可在一定程度上防止種群的早熟現(xiàn)象的發(fā)生。變異的概率一般較低，一般在0.001～0.01之間。

2 遺傳k－means聚類算法的并行化實現(xiàn)

遺傳k－means算法雖然提高了聚類效果的準確性，但同時也產(chǎn)生了效率低的問題，尤其是在處理大數(shù)據(jù)集時，這樣的問題顯得尤為突出。考慮到遺傳算法具有的天然并行性，可以將遺傳聚類算法進行并行化設計。這樣不僅提高算法的時間效率而且增加了種群的多樣性，可以防止早熟現(xiàn)象的發(fā)生。

2.1 MapReduce模型

Hadoop平臺下的MapReduce 并行計算模型是模仿Google開發(fā)出的MapReduce 并行計算模型，而且是開源免費的。

MapReduce模型首先對輸入的數(shù)據(jù)有格式的要求，必須以鍵值對＜key，value＞的形式作為輸入，key可以理解為數(shù)據(jù)的編號，value表示數(shù)據(jù)的值。其次數(shù)據(jù)的處理過程主要分為Map過程和Reduce過程。Map過程主要對原始的輸入數(shù)據(jù)進行處理產(chǎn)生中間的＜key'，value'＞，然后根據(jù)相同的key'，對數(shù)據(jù)進行規(guī)約處理，作為Reduce過程的輸入，最后輸出結果。它的計算模型如圖1所示。

圖1 MapReduce簡單計算模型

2.2 種群遷移策略

種群遷移作為遺傳算法的并行化設計是區(qū)別于串行遺傳算法的重要方面，常用的方法是最優(yōu)／最差替換法，即將子種群中的最優(yōu)個體遷出用來替換鄰居種群中的最差個體。在每一個Map過程中，改變滿足條件的染色體的編號從而達到遷移的目的。

2.3 Map和Reduce過程設計

針對MapReduce模型對輸入數(shù)據(jù)的特殊性要求，將本文的輸入數(shù)據(jù)格式化為＜key，value＞的形式，其中key表示子種群的編號，value表示個體的值。此外，將染色體的長度設為k＋1，最后一位用于存儲個體的適應度值，初始化時設為0。個體的初始化、適應度評價和k－means操作可以放在Map過程進行；Reduce過程主要是針對相同的鍵，達到停機條件，輸出各個子種群中最優(yōu)的個體，然后再選出這些最優(yōu)個體中的最優(yōu)個體，根據(jù)每個染色體最后一位的適應度值。否則，完成一個子種群的遺傳操作。

3 實 驗

采用4臺普通的計算機搭建的Hadoop集群系統(tǒng)進行實驗，Hadoop的版本是Hadoop－0.20.2。每臺計算機使用的操作系統(tǒng)是Red Hat Linux 9.0版本。所使用的數(shù)據(jù)集是人工數(shù)據(jù)，維度為2。分別構造了3個數(shù)據(jù)集Data1，Data2，Data3。Data1 包 含100 個 數(shù) 據(jù)，分 為3 類；Data2 包 含1000個數(shù)據(jù)，數(shù)據(jù)類別5；Data3包含了5000個數(shù)據(jù)，類別為10。各數(shù)據(jù)集每個類別中包含的數(shù)據(jù)個數(shù)都是相等的。采用運行20次的平均值作為最終的實驗結果。相關的參數(shù)設置：交叉概率為0.9；變異概率為0.009；種群大小設為40；算法的最大迭代次數(shù)設為50。

由表1可以看出k－means算法即使在處理小的數(shù)據(jù)集時所得到的結果往往也不太理想，再將遺傳算法加入到kmeans算法中，所得到的相應的結果明顯得到了改善。然后再將其進行并行化設計后，隨著處理的數(shù)據(jù)集規(guī)模不斷增大，所得到的聚類結果和串行的算法相比較也會有明顯的改善。這主要是因為并行遺傳算法能夠有效防止早熟現(xiàn)象的發(fā)生從而收斂到較好的結果。

表1 不同算法的聚類性能比較

圖2反映了加速比與節(jié)點數(shù)之間的關系，從圖2可以看出，加速比與節(jié)點數(shù)并不是線性關系或正比例關系，這主要是因為隨著節(jié)點數(shù)的增加，節(jié)點之間的通信開銷也會增大，但對于在相同的節(jié)點數(shù)下面，數(shù)據(jù)集規(guī)模越大，所得到的加速比也會較大。而且對于大數(shù)據(jù)集，隨節(jié)點數(shù)增加，加速比增加的更快一些。這是因為大的數(shù)據(jù)集可以更有效地利用每個節(jié)點的計算性能。

圖2 節(jié)點數(shù)與加速比的關系

圖3主要反映了算法的并行效率，從圖3中可以看出，數(shù)據(jù)規(guī)模較小的并行效率要低于數(shù)據(jù)集較大的并行效率，而且隨著節(jié)點數(shù)的增加，下降會更快一些；而數(shù)據(jù)規(guī)模較大時，下降得更為平緩。這些主要是因為數(shù)據(jù)規(guī)模增大，處理的時間也會增加，節(jié)點數(shù)的增加，節(jié)點之間的通信開銷也會增加。從圖2 和圖3 可以得出并行化后的遺傳kmeans算法具有良好的并行性和可擴展性。

4 結束語

圖3 節(jié)點數(shù)與并行效率的測試結果

將智能算法與聚類算法相結合可以提高聚類算法的聚類結果，但同時又會產(chǎn)生智能算法的低時間效率的問題。遺傳k－means算法在Hadoop平臺下的并行化設計和實現(xiàn)，不僅提高了算法運行的時間效率而且也改善了算法運行的結果。

對于如何改進遺傳算子加速收斂從而縮短達到最優(yōu)的遺傳迭代次數(shù)，以及對k－means算法中如何確定最佳的k值，能否通過可變長的染色體來達到，這些都是有待于以后進行研究的問題。

［1］LI Qun，YUAN Jinsheng.Optimal density text clustering algorithm based on DBSCAN ［J］.Computer Engineering and Design，2012，33 （4）：1409－1413 （in Chinese）. ［李群，袁金生.基于DBSCAN 的最優(yōu)密度文本聚類方法 ［J］.計算機工程與設計，2012，33 （4）：1409－1413.］

［2］LAI Yuxia，LIU Jianping.Optimal study on initial center of kmeans algorithm ［J］.Computer Engineering and Applications，2008，44 （10）：147－149.（in Chinese）［賴玉霞，劉建平.kmeans算法的初始聚類中心的優(yōu)化 ［J］.計算機工程與應用，2008，44 （10）：147－149.］

［3］TIAN Senping，WU Wenliang.Algorithm of automatic gained parameter value k based on dynamic k－means［J］.Computer Engineering and Design，2011，32 （1）：274－276 （in Chinese）.［田森平，吳文亮.自動獲取k－means聚類參數(shù)k值的方法 ［J］.計算機工程與設計，2011，32 （1）：274－276.］

［4］DAI Wenhua，JIAO Cuizhen，HE Tingting.Research of kmeans clustering method based on parallel genetic algorithm［J］.Computer Science，2008，35 （6）：171－174 （in Chinese）.［戴文華，焦翠珍，何婷婷.基于并行遺傳算法的kmeans聚類研究 ［J］.計算機科學，2008，35 （6）：171－174.］

［5］ZHAO Weizhong，MA Huifang，F(xiàn)U Yanxiang，et al.Research on parallel k－means algorithm design based on Hadoop platform ［J］.Computer Science，2011，33 （10）：166－168（in Chinese）.［趙衛(wèi)中，馬慧芳，傅燕翔，等.基于云計算平臺Hadoop的并行k－means聚類算法設計研究 ［J］.計算機科學，2011，33 （10）：166－168.］

［6］LU Linhua，Wang Bo.Improved genetic algorithm－based clustering approach ［J］.Computer Engineering and Application，2007，43 （21）：170－172 （in Chinese）.［陸林華，王波.一種改進的遺傳聚類算法 ［J］.計算機工程與應用，2007，43（21）：170－172.］

［7］ZHAO Jiuling，WEI Haipeng.Design and realization of parallel genetic algorithm based on MPI ［J］.Computer Science，2006，33 （9）：186－189 （in Chinese）. ［趙玖玲，衛(wèi)海鵬.基于MPI的并行遺傳算法的設計與實現(xiàn) ［J］.計算機科學，2006，33 （9）：186－189.］

［8］Verma A，Llora X，Goldberg D E，et al.Scaling genetic algorithms using mapreduce ［C］／／In International Conference on Intelligent Systems Design and Applications，2009.

［9］Jin C，Vecchiola C，Buyya R.Mrpga：An extension of mapreduce for parallelizing genetic algorithms［C］／／IEEE Fourth International Conference on eScience，2008：214－221.

［10］LI Dong，PAN Zhisong.Research on parallel genetic algorithm based on MapReduce ［J］.Computer Science，2012，39 （7）：182－204 （in Chinese）. ［李東，潘志松.一種適用于大規(guī)模變量的并行遺傳算法研究 ［J］.計算機科學，2012，39 （7）：182－204.］