武霞，董增壽，孟曉燕

(太原科技大學電子信息工程學院，太原市 030024)

基于大數據平臺hadoop的聚類算法K值優(yōu)化研究

武霞，董增壽，孟曉燕

(太原科技大學電子信息工程學院，太原市 030024)

針對最大最小值原則的Kmeans聚類算法運行在Hadoop平臺時需要多次遍歷所有數據的問題，提出了一種改進的初始聚類中心的選擇算法稱為M+Kmeans算法。該算法只需要遍歷一次全局數據極大的縮減了算法并行運算時消耗的時間。多組實驗測試結果顯示，設計的M+Kmeans算法適合運行在大規(guī)模集群Hadoop平臺上，并且加速比和擴展率較原始算法有明顯提高。

聚類;大數據;Hadoop;Kmeans

聚類分析是數據挖掘領域的一個熱門的研究分支。聚類思想就是數據歸類:“相似同類，相異不同”［1］。K-means算法是聚類分析中經典的算法。算法計算收斂速度快，易于實現但是思想卻不簡單，于是受到廣泛的研究和使用。算法本身存在缺陷，因為聚類之前對要求劃分的類是未知的，因此需要人為的事先確定聚類數目即K的值，還要事先確定種子中心點，這樣使聚類的結果會產生局部最優(yōu)解，而且不正確的K值設定也會對最終數據產生很大的影響。例如數據本該分為4類，而卻被人為的分成了3類，這樣本身就是不恰當的。在K值的選取上面，已有不少前人做了研究，如canopykmeans算法、最大最小值算法等都是針對K值的選取提出和優(yōu)化的。但是canopy的劃分是粗略的，容易重復覆蓋。最大最小值算法在計算K值時要重復的遍歷數據，造成時間浪費。本文針對最大最小值算法的不足，根據“最大值原則”提出了改進的算法在中心點選取和K值的確定方面進行優(yōu)化，這里稱改進后的算法為M+Kmeans算法，并且將M+ Kmeans算法運用到Hadoop大數據平臺上。

目前國外大數據的理論已經趨于成熟，企業(yè)已經將成熟的框架方案運用在商業(yè)上［2］。自從Google提出云計算的概念以來，很多企業(yè)都已經陸續(xù)擁有了屬于自己特色的云產品。例如微軟、蘋果、Facebook先后建立了自己的云平臺;SUN、HP、Intel、yahoo等公司也開啟了云計算之旅［3］。在國內，大數據云計算作為新興的產業(yè)，由于發(fā)展較晚，目前在理論及應用方面相對不成熟，正處于積極探索和研究階段，主要集中在試商用階段和學術層面。當然國內一些大的企業(yè)也已經嘗試對大數據應用研究探索。中國移動率先搭建了云平臺“Blue-Carrier”，并在此基礎上完成了PEMiner數據挖掘平臺的架構。另外淘寶、中國電信、華為等多家大型企業(yè)也在著手開發(fā)自己的云產品。

Hadoop大數據平臺是Apache開發(fā)的開源的計算機集群分布式實現框架。Hadoop的一個關鍵組成部分是HDFS——分布式文件系統(tǒng)(Hadoop Distributed File System)［4］。HDFS是用于存儲輸入和輸出數據的應用程序，有高容錯性和高傳輸率的特點［5］。

1 改進的M+K-means算法

1.1 “最大最小值原則”的K-means算法介紹

最大最小值原則的基本原理是首先隨機選取一個種子點作為中心點A，然后計算集合C中剩余點到A點的距離，選取距離最大的點作為第二個種子點B，再計算C中剩余點到這兩個種子點的距離，得出到兩個中心距離最小的點min(dA，dB)，找到該距離的最大值max(min(dA，dB))，迭代條件若滿足:

其中dA、dB表示點到A、B點的距離，若滿足則點為第三個種子點，按照此方法一直迭代直到無法滿足條件，于是種子點就全部得出，并且得到了K的值。但此法有一個缺陷就是每確定一個種子點就要遍歷一遍集合中所有的數據，如果數據量大的話，無疑更是災難性的時間浪費［6］。

1.2 M+K-means算法的思想介紹

M+K-means算法是基于最大值原則在K參數的選取上進行優(yōu)化的K-means聚類算法，算法思想為:首先任意選取一個點A作為種子中心點。然后遍歷一次數據，計算出集合C中剩余點到種子點的距離值，將得到的點和距離dn，dn-1d1存入數組中，設d1到dn為從小到大的距離。選取距離最大的點即dn處作為第二個種子中心點B，接下來選擇距離A為dn-1處的點(可不為1)，并計算其與B距離DistB，若DistB大于dn-1則設為種子點C，否則為普通點。迭代條件為:

依次選取距離A為distm的點，若這點與dist (m+1)的所有點的距離都不小于distm，則這點設為新種子中心點，否則為普通點。這樣可以選擇出A點各個方向上的最大值點，防止漏選。這樣便可得出初始的種子中心點和K的值。接下來再進行傳統(tǒng)的聚類即可，這樣可以省掉每次遍歷數據浪費的時間。

其基本步驟描述如下:

a)聚類中心A1的選擇:從數據集合D中任意選取一個點作為種子中心A1.

b)計算剩余點到A1點的距離，在集合D中選取離A1距離值最大的點標記為第二個中心點A2，設dn為此處最大距離，設點為dn點。

c)并行選取數組中dm-1的所有點，計算與dm所有點的距離，若滿足距離不小于dm-1則標記為種子中心點。

d)若點不滿足設置的條件則設為普通點。

e)重復步驟c和d，直到無法滿足條件就結束，得出符合條件的中心點。

f)鄰近類中心合并。

g)將得到的K值和聚類中心點賦予經典的K-means算法，接下來就是傳統(tǒng)的算法計算過程。

此時改進的算法在尋找中心點和確定K值是只需要遍歷一次集合中的數據，大大節(jié)省了數據挖掘的時間。

2 M+K-means算法

2.1 M+K-means算法的并行實現

MapReduce模型是谷歌公司開發(fā)的用抽象的Map和Reduce函數的分布式編程框架，執(zhí)行并行計算［7］。本文在Hadoop平臺實現M+K-means算法的MapReduce并行化。將分為兩個MapReduce階段，具體框架圖如下:

圖1 M+K-means算法的mapreduce流程圖Fig.1 Mapreduce flow chart of M+Kmeans algorithm

算法的第一個步驟是初始K值的選擇，由兩個Map和一個Reduce來實現。這里設計兩個Mapper過程和一個Reduce過程，可以縮短shuffle階段的時間和reduce階段節(jié)點間的數據拉取過程所需的時間［8］。其中第一個Map過程主要負責找出隨機中心點，遍歷數據，計算出剩余點和中心點間距離。接下來第二個Map過程負責計算dn-2的點與所有dn-1的點的距離，執(zhí)行循環(huán)，直到得出M個種子中心，傳輸給Reduce。Reduce部分得到的結果是來自不同的獨立Map的結果，所以有可能種子中心點是相鄰的，所以Reduce過程負責將鄰近的聚類中心合并［9］。

第二個階段是由一個MapReduce過程來完成。將第一個階段產生的初始聚類中心K值賦予傳統(tǒng)K-means算法，算法重復計算每個簇的質心直到收斂。聚類過程就完成了。Map過程主要利用歐氏距離對原數據集合中的所有對象進行劃分。Reduce過程負責計算并更新各個簇中新的聚類中心，并予以輸出，方便其作為下一次迭代的輸入，直到聚類中心不再發(fā)生變化算法結束。由于初始聚類中心的選擇是通過優(yōu)化算法得到的，不再是人為設置的，這樣第二階段的MapReduce過程能較快的結束迭代，算法能夠較快的收斂。

對于改進后的算法整體來說，一方面減少了遍歷數據的次數，大大提高了執(zhí)行速度;另一方面由于聚類中心是由算法執(zhí)行得到的，而且無需事先人為設定聚類數目，減少了主觀因素對聚類結果的影響。

2.2 M+K-means算法的復雜度

傳統(tǒng)的K-means聚類的復雜計算程度為O (dkt)，其中d為文獻數量，k為類的數量，t為迭代次數［10］。這里設原始數據規(guī)模為D，計算并行程度為m.所以map過程所用的時間為:

Reduce階段合并x個聚類種子中心所用時間:

接下來的mapreduce過程為傳統(tǒng)K-means計算，所需時間為:

因為x的值非常小，遠遠小于D，所以算法的復雜計算程度為O(Dkd/m).

3 實驗結果及分析

3.1 Hadoop平臺搭建

實驗環(huán)境配置，Hadoop集群一共有5臺機器，并將一臺設為Jobtracker.每臺機器內存4 G，硬盤空間460 G，CPU為2.70 Ghz，雙核，操作系統(tǒng)是WindowXP，每臺機子安裝了Cygwin虛擬機模擬Linux環(huán)境，安裝eclipse3.3.2運行Hadoop0.20.2，java版本1.6.0_43.配置Hadoop為完全分布模式，根據集群拓撲結構和IP地址對Hadoop的conf下的core-site.xml，hdfs-site.xml，mapred.site.xml和mapred-queues.xml等文件進行配置。在Cygwin中格式化namenode，start-all.sh指令啟動Hadoop.在eclipse中創(chuàng)建MapReduce工程，將文件導入HDFS.

3.2 實驗結果分析

為了檢驗算法的可行性和有效性，分別計算優(yōu)化后的算法和傳統(tǒng)最大最小值原則K-means算法的并行時間開銷。測試了M+K-means算法的擴展率和加速比。做5次實驗取結果的平均值制圖。圖2為兩個算法處理的時間消耗，圖3為加速比，圖4為擴展率。

在時間消耗的測試上，我們選擇了4種類別的數據，分別測試了處理1維、2維和4維數據的時間。從圖2可以看出，在數據是1維時，兩個算法運行時間相當，是因為1維數據處理比較簡單，兩種算法對1維數據迭代次數差不多。但運行2維和4維數據時，數據運算量增大，原始的最大最小原則在尋找初始中心點時需要遍歷所有數據并且迭代次數也有所增加。而設計的M+kmeans算法在尋找初始中心點時只需要遍歷一次所有數據和簡單的迭代。所以設計的算法在處理n維數據的運行時間上優(yōu)于最大最小值Kmeans算法。

圖2 兩個算法時間消耗Fig.2 Two algorithms of time consumption

圖3 M+Kmeans算法加速比Fig.3 M+Kmeans algorithms speedup

加速比測試選取了三組大小不同的數據，分為1 G，2 G和4 G的數據。從圖3的加速比上可以看出，設計的算法的加速比基本上成線性的。而且處理的數據量越大加速比越好。這是因為第一:數據量大時，節(jié)點的運行效率增加了，更易發(fā)揮每個節(jié)點的計算能力了;第二:算法在reduce階段之前加入了combine，使得節(jié)點之間拉取數據的效率提高了，而且數據量越大，這種效率提高的越多［11］。因此mapreduce框架更適合于大量數據的處理，而設計的算法也可以很好的將大數據處理運行在框架上。

圖4 算法擴展率Fig.4 Algorithms expansion ratio

擴展率的測試選取了三組數據，1 G、2 G、4 G為一組，2 G、4 G、8 G為一組，4 G、8 G、16 G為一組，并且每組數據從小到大分別運行在1個節(jié)點、3個節(jié)點和5個節(jié)點上。從圖4可以看出隨著節(jié)點的增加，運行效率也減小了，這是因為多節(jié)點運行時，節(jié)點之間的數據傳送也會耗費資源。但是據圖發(fā)現，5個節(jié)點時運行16 G的數據明顯比運行8 G數據運行效率高。這是因為數據量增加，節(jié)點更易充分發(fā)揮它的計算能力，所以節(jié)點利用率高了。

4 結束語

對經典的K-means聚類算法進行了深入研究，針對最大最小值原理的中心值選取方法進行了改進，并移植到Hadoop平臺上。改進的算法運用了最大值原則進行計算，將一次遍歷數據的距離存入數組中進行map并行計算，減小了遍歷數據的次數，然后將并行的map結果進行種子點合并再傳送給reduce，節(jié)省了Map的資源，得到了優(yōu)化的K值。

通過多組實驗表明，改進的算法可以有效利用Hadoop平臺強大的并行計算能力，更適合計算多維的大數據。但是不管是mapreduce框架的設計，還是算法到平臺的移植都會有不斷的新的問題出現。效率和時間消耗問題仍然是不變的改進重點，還需要不斷的努力和探究。

［1］毛典輝.基于MapReduee的Canopy-kmeans改進算法［J］.計算機工程與應用，2012，48(27):22-26.

［2］朱為盛，王鵬.基于Hadoop云計算平臺的大規(guī)模圖像檢索方案［J］.計算機應用，2014，34(3):695-699.

［3］JINSON ZHANG，MAO LINHUANG.5WS Model for BigData Analysis and Visualization［C］∥IEEE 16th International Conference on Computational Science and Engineering，Sydney，NSW，IEEE，2013:1021-1028.

［4］ROSANGELA DE FáTIMA PEREIRA，MARCELO RISSE DE ANDRADE，ARTUR CARVALHO ZUCCHI，et al.Distributed processing from large scale sensor network using Hadoop［C］∥IEEE International Congress on Big Data，Santa Clara CA，IEEE，2013:417-418.

［5］李偉衛(wèi)，趙航，張陽，等.基于MapReduce的海量數據挖掘技術研究［J］.計算機工程與應用，2013，49(20):112-117.

［6］趙慶.基于Hadoop平臺下的Canopy-Kmeans高效算法［J］.2014，27(2):29-31.

［7］WEIKUAN YU，YANDONG WANG.Design and Evaluation of Network-Levitated Merge for Hadoop Acceleration［C］∥IEEE Transactions on Parallel and Distributed Systems，Washington DC，2014:602-611.

［8］亓開元，趙卓峰，房俊，等.針對高速數據流的大規(guī)模數據實時處理方法［J］.計算機學報，2012，35(3):477-490.

［9］汪麗，張露.基于分布式數據挖掘方法的研究與應用［J］.武漢理工大學學報:信息與管理工程版，2013，35(1):40-43.

［10］賴桃桃，馮少榮.聚類算法中的相似性度量方法研究［J］.心智與計算，2008，18(2):176-181.

［11］曲朝陽，朱莉，張士林.基于Hadoop的廣域測量系統(tǒng)數據處理［J］.電力系統(tǒng)自動化，2013，37(4):92-97.

Clustering Algorithm K-value Optimization Research Based on Hadoop Platform

WU Xia，DONG Zeng-shou，MENG Xiao-yan
(School of Electronic information engineering，Taiyuan University of Science and Technology，Taiyuan 030024，China)

An initial clustering center selection algorithm called M+Kmeans algorithm was presented because the maximum-minimum principle of Kmeans clustering algorithm running on Hadoop platform needs to traverse all data for many times.This algorithm only needs to traverse a global data，thus greatly reducing the time of the algorithm and parallel computing.Multiple sets of experimental test results show that the design of M+Kmeans algorithm is suitable for operation on large Hadoop cluster platform，and the speed ratio can obviously improve the expansion rate than the original algorithm.

big data，cluster，Hadoop，kmeans

TP301.6

A

10.3969/j.issn.1673-2057.2015.02.003

1673-2057(2015)02-0092-05

2014-09-26

山西省自然科學基金(2012011015-4)

武霞(1988-)，女，碩士研究生，主要研究方向為大數據數據挖掘。