加速大數(shù)據(jù)聚類K－means算法的改進(jìn)

韓 巖，李 曉

（1.中國(guó)科學(xué)院新疆理化技術(shù)研究所，新疆 烏魯木齊830011；2.中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)與控制學(xué)院，北京100049）

0 引 言

聚類分析是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要分支，研究者針對(duì)各個(gè)領(lǐng)域提出了不同的改進(jìn)聚類算法：劃分聚類、層次聚類、基于密度的聚類、基于網(wǎng)格的聚類、基于模型的聚類等算法［1－3］。尤其K－means算法使用最為廣泛，但Kmeans算法對(duì)初始的k個(gè)中心依賴性很大，初始中心選擇不當(dāng)，容易造成局部最優(yōu)解，增加迭代次數(shù)，降低執(zhí)行效率。由于數(shù)據(jù)規(guī)模越來(lái)越大，而傳統(tǒng)的聚類算法在處理大規(guī)模數(shù)據(jù)時(shí)無(wú)論從系統(tǒng)資源還是從實(shí)時(shí)性效率的角度，都不能提供很好的解決方案［4］。為解決上述問(wèn)題，本文提出一種先抽樣再用最大最小距離方法計(jì)算聚類中心的聚類分析方法。

1 相關(guān)概念

（1）K－means算法思想：以空間中k 個(gè)點(diǎn)為中心進(jìn)行聚類，對(duì)最靠近他們的對(duì)象歸類。通過(guò)迭代的方法，逐次更新各聚類中心的值，直至得到聚類中心收斂為止［1］。

（2）最大最小距離法：具體詳細(xì)內(nèi)容參見(jiàn)文獻(xiàn) ［11］。

（3）歐氏距離 （簡(jiǎn)稱距離）Euclidean［2］

（4）加權(quán)聚類準(zhǔn)則函數(shù)。

聚類準(zhǔn)則函數(shù)［2］：

由于是對(duì)大數(shù)據(jù)進(jìn)行聚類，防止孤立點(diǎn)對(duì)Jc值的影響，采用加權(quán)聚類準(zhǔn)則函數(shù)

式中：X——樣本類別，Mj——樣本均值，n——所有樣本數(shù)目。

（5）MapReduce編程模型的基本思路：將大數(shù)據(jù)集分解成千上百個(gè)小數(shù)據(jù)集，每個(gè)小數(shù)據(jù)集分別由集群中的1個(gè)節(jié)點(diǎn)并行執(zhí)行Map計(jì)算任務(wù)并生成中間結(jié)果，然后這些中間結(jié)果多節(jié)點(diǎn)并行執(zhí)行Reduce計(jì)算任務(wù)，形成最終結(jié)果。MapReduce執(zhí)行過(guò)程如圖1所示。

圖1 MapReduce執(zhí)行過(guò)程

2 改進(jìn)的K－means算法

2.1 改進(jìn)算法思想

K－means算法屬于劃分聚類算法之一，它有算法簡(jiǎn)單，速度快等優(yōu)點(diǎn)；它也有對(duì)初始聚類中心依賴較大、對(duì)異常偏離數(shù)據(jù)敏感、只適合處理數(shù)值的數(shù)據(jù)等缺點(diǎn)。下文將針對(duì)優(yōu)化初始聚類中心和并行化提出解決辦法。

改進(jìn)算法的思路如下：

設(shè)數(shù)據(jù)集X＝ ｛x1，x2...xn｝，且xi∈Od其中n為樣本個(gè)數(shù)，d為樣本維度，k為聚類個(gè)數(shù)，m 為迭代次數(shù)。傳統(tǒng)K－means算法如下［7］：

（1）適當(dāng)選擇k個(gè)類的初始中心；

（2）在第m 次迭代中，對(duì)任意一個(gè)樣本，求其到k個(gè)中心的距離，將該樣本歸到距離最短的中心所在的類；

（3）利用均值等方法更新該類的中心值；

（4）對(duì)于所有的k個(gè)聚類中心，如果利用式 （2）、式（3）的迭代法更新后，值保持不變，則迭代結(jié)束，否則繼續(xù)迭代。

本文算法是首先結(jié)合隨機(jī)抽樣方法從樣本集X 中抽取一個(gè)規(guī)模較小的工作集X′，設(shè)｜X′｜＝｜X｜/s，其中s為抽樣因子，一般取值在5～100之間 （即抽樣數(shù)據(jù)是原始數(shù)據(jù)1%～20%），取值視原始數(shù)據(jù)量而定。然后，用最大最小距離法計(jì)算抽樣數(shù)據(jù)的聚類中心C1，再以C1作為據(jù)的聚類中心C，由于K－means之間的計(jì)算相互獨(dú)立的，所以，可以使用MapReduce框架實(shí)現(xiàn)計(jì)算的并行化，提高計(jì)算的效率。然后再計(jì)算新的聚類中心C′與C 距離是否小于設(shè)定的閥值Y，如果小于執(zhí)行結(jié)束，返回新的聚類中心與聚類結(jié)果。否則用新的聚類中心C′重新聚類，直到兩個(gè)聚類中心距離小于設(shè)定閥值為止。

通過(guò)個(gè)流程可以分析出整個(gè)程序的時(shí)間復(fù)雜度為：O（nk （1/s＋t）/ （M＊N））其中n是樣本集的個(gè)數(shù)，k是聚類個(gè)數(shù)，t是全局?jǐn)?shù)據(jù)的迭代次數(shù)，M 是執(zhí)行作業(yè)的Map個(gè)數(shù)，N 是集群中執(zhí)行該任務(wù)的結(jié)點(diǎn)數(shù)。

2.2 改進(jìn)算法的執(zhí)行流程

2.2.1 改進(jìn)算法主要有個(gè)兩個(gè)主要的步驟

（1）確定初始化聚類的中心。

（2）實(shí)現(xiàn)海量數(shù)據(jù)的K－means算法并行化計(jì)算。

2.2.2 執(zhí)行流程

設(shè)數(shù)據(jù)集為X＝ ｛x1，x2，…，xn｝，其中xi∈Od，抽樣因子為s，聚類個(gè)數(shù)為k，閥值參數(shù)為Y。

（1）從數(shù)據(jù)集X 中隨機(jī)抽取n/s個(gè)樣本數(shù)據(jù)構(gòu)成抽樣樣本X′＝ ｛x′1，x′2...x′m｝；得到｜X′｜＝｜X｜/s。

（2）用最大最小距離方法計(jì)算抽樣數(shù)據(jù)X′的k個(gè)聚類中心：

1）先從抽樣數(shù)據(jù)X′隨機(jī)選擇一個(gè)樣本x′i，作為抽樣數(shù)據(jù)聚類中心C1第1個(gè)中心點(diǎn)c1；

2）用X 中樣本集計(jì)算出與c1歐氏距離式 （1）最遠(yuǎn)的點(diǎn)x′j，作為第2個(gè)中心點(diǎn)c2；

3）用X 中樣本集計(jì)算出與C1 中樣本集之間的歐氏距離：

在所有模式中選擇 ｛min（di1，di2）i＝1，2…n；｝中最大的作為第3 個(gè)中心點(diǎn)c3；即min（dj1，dj2）＝max ｛min（di1，di2）i＝1，2…n；｝j＝1，2…n；則c3＝x′j；

4）如果現(xiàn)有聚類中心的個(gè)數(shù)r（r＜k），得到了C1＝｛x′1，x′2…x′r｝，即確定第r＋1個(gè)中心點(diǎn)：min（dj1，dj2…djr）＝max ｛min （di1，di2…dir）i＝1，2…n；｝j＝1，2…n；則cr＋1＝x′j；

5）重復(fù)4），直到獲得k 個(gè)聚類中心，即C1＝ ｛x′1，x′2…x′k｝

（3）用C1作為全局?jǐn)?shù)據(jù)的初始聚類中心C＝ ｛x1，x2…xk｝，使用MapReduce框架實(shí)現(xiàn)K－means算法的并行運(yùn)算并求出新的聚類中心C′。

（4）計(jì)算出新的聚類中心C′與C 的距離是否小于閥值Y，如果小于Y，則返回聚類中心C 及聚類結(jié)果；否則用C′作為新的聚類中心重新聚類，直到新的聚類中心與上一次聚類中心之間的距離小于Y 時(shí)，聚類結(jié)束，返回聚類的中心與聚類結(jié)果。

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

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

硬件：2.5GHZ 的雙核CPU，硬盤500G。軟件：操作系統(tǒng)CentOS5，hadoop1.0.4，Eclipse4.2，單機(jī)偽分布式與集群完全分布式環(huán)境。

3.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)說(shuō)明：方法都是基于MapReduce的并行運(yùn)算，普通K－means方法 （S）：代表隨機(jī)選擇k個(gè)聚類中心后用Kmeans方法；最大最小距離的K－means（MM）：最大最小距離法計(jì)算出k個(gè)聚類中心后再用K－means方法；抽樣加最大最小距離的K－means（MMS）：①先采用最大最小距離方法計(jì)算出抽樣數(shù)據(jù)k個(gè)初聚類中心C；②使用聚類中心C作為全局?jǐn)?shù)據(jù)的初始聚類中心；③再使用并行化的Kmeans方法計(jì)算出聚類的結(jié)果。記錄數(shù)為n，聚類個(gè)數(shù)為k，終止條件為Y，方法為M，加權(quán)準(zhǔn)則函數(shù)為Jc，迭代次數(shù)t，執(zhí)行時(shí)間T。以下的結(jié)果是運(yùn)行5次的平均結(jié)果。

3.2.1 實(shí)驗(yàn)1：驗(yàn)證改進(jìn)的K－means算法可行性

首先才用人工標(biāo)注的20條測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，數(shù)據(jù)分布如圖2所示。

圖2 標(biāo)注數(shù)據(jù)分布

實(shí)驗(yàn)1運(yùn)行結(jié)果見(jiàn)表1。

表1 不同方法不同聚類個(gè)數(shù)聚類結(jié)果

從表1 與圖3 的結(jié)果中得出使用最大最小距離法Kmeans聚類取得了相同優(yōu)化的解，而且在5 次實(shí)驗(yàn)中保持了穩(wěn)定性，且性能明顯優(yōu)于隨機(jī)選擇聚類中心的K－means，但于海量數(shù)據(jù)的聚類用最大最小距離方法來(lái)計(jì)算聚類中心很浪費(fèi)時(shí)間的，甚至造成內(nèi)存不足，所以提出了這種折中的方法用抽樣數(shù)據(jù)中心代替全局?jǐn)?shù)據(jù)初始聚類中心的聚類方法。

圖3 不同聚類個(gè)數(shù)與Jc趨勢(shì)

3.2.2 實(shí)驗(yàn)2：驗(yàn)證改進(jìn)的K－means算法有效性

實(shí)驗(yàn)說(shuō)明：用隨機(jī)產(chǎn)生的記錄數(shù)來(lái)驗(yàn)證方法的有效性，記錄數(shù)n （單位：萬(wàn)）分別是1、10、100，環(huán)境：?jiǎn)螜C(jī)偽分布條件下，方法同上，聚類為100時(shí)結(jié)果見(jiàn)表2。

表2 單機(jī)下聚類結(jié)果

3.2.3 實(shí)驗(yàn)3：驗(yàn)證改進(jìn)算法可以并行執(zhí)行

在虛擬機(jī)下4 臺(tái)均是裝有CentOS5 操作系統(tǒng)，內(nèi)存512 M，硬盤100G，2.5Ghz雙核CPU，其中一臺(tái)是master，三臺(tái)是Slave。數(shù)據(jù)：使用實(shí)驗(yàn)2中數(shù)據(jù)。聚類為100時(shí)在集群的運(yùn)行結(jié)果見(jiàn)表3。

表3 集群下運(yùn)行結(jié)果

通過(guò)表2得出以下結(jié)論：當(dāng)數(shù)據(jù)量較小時(shí)，最大最小距離法Jc的值最小且執(zhí)行時(shí)間最短；隨著數(shù)據(jù)量的增加，最大最小距離法計(jì)算聚類中心時(shí)間增加導(dǎo)致計(jì)算時(shí)間過(guò)長(zhǎng)；繼續(xù)增加數(shù)據(jù)量時(shí)，這種方法將不在適合聚類運(yùn)算。大數(shù)據(jù)量時(shí)，這種改進(jìn)的方法執(zhí)行時(shí)間大大減少了且加權(quán)準(zhǔn)則函數(shù)值也降低了，提高聚類的質(zhì)量。

表3與表2對(duì)比，在同樣的條件下，執(zhí)行的時(shí)間明顯是降低的，但并沒(méi)成比例的降低。原因如下：①實(shí)驗(yàn)3中4臺(tái)虛擬機(jī)總內(nèi)存和實(shí)驗(yàn)2中1臺(tái)虛擬機(jī)內(nèi)存是相同的；②實(shí)驗(yàn)中隨機(jī)數(shù)據(jù)和抽樣數(shù)據(jù)導(dǎo)致迭代次數(shù)不一樣，但在平均執(zhí)行一次的時(shí)間，集群運(yùn)行效率要比單機(jī)時(shí)效率要高。這也說(shuō)明了同樣條件下，并行化操作提高了運(yùn)行效率。尤其是在執(zhí)行時(shí)間上提高了2～3倍。

4 結(jié)束語(yǔ)

本文主要通過(guò)Hadoop平臺(tái)上的MapReduce框架實(shí)現(xiàn)K－means算法并行化的聚類操作。實(shí)驗(yàn)結(jié)果表明：這種改進(jìn)的方法選取了較優(yōu)的初始聚類中心，降低了對(duì)初始聚類中心的依賴性，提高了聚類的質(zhì)量及運(yùn)行效率，加速了聚類的收斂速度。特別是在集群環(huán)境下，數(shù)據(jù)量較大時(shí)，完全隨機(jī)分布的數(shù)據(jù)有明顯的效果。下一步工作主要在于抽樣數(shù)據(jù)質(zhì)量與優(yōu)化上再進(jìn)行改進(jìn)；集群優(yōu)化與負(fù)載均衡等。

［1］ZHOU Aiwu，CUI Dandan，PAN Yong.An optimization initial clustering center of K－means clustering algorithm ［J］.Microcomputer ＆Its Applications，2011，30 （13）：1－3 （in Chinese）.［周愛(ài)武，崔丹丹，潘勇.一種優(yōu)化初始聚類中心的Kmeans聚類算法 ［J］.微型機(jī)與應(yīng)用，2011，30 （13）：1－3.］

［2］WANG Jia，JIANG Mingfu，LI Youguo.A cluster analysis method based on improved K－means algorithm ［J］.Agriculture Network Information，2009，10：120－122 （in Chinese）. ［汪嘉，姜明富，李友國(guó).一種基于改進(jìn)的K－Means算法的聚類分析方法 ［J］.農(nóng)業(yè)網(wǎng)絡(luò)信息，2009，10：120－122.］

［3］HUANG Tao，LIU Shenghui，TAN Yanna.Research of clustering algorithm based on K－means［J］.Computer Technology and Development，2011，21 （7）：54－57 （in Chinese）. ［黃韜，劉勝輝，譚艷娜.基于K－means聚類算法的研究 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21 （7）：54－57.］

［4］QIAN Yanjiang.Research and realization of large－scale data clustering techniques ［D］.Chengdu：Chengdu University，2009 （in Chinese）.［錢彥江.大規(guī)模數(shù)據(jù)聚類技術(shù)研究與實(shí)現(xiàn) ［D］.成都：電子科技大學(xué)，2009.］

［5］WANG Xiuhua.A parallel speeding K－means clustering method［J］.Computer Knowledge and Technology，2013，9 （18）：4299－4302 （in Chinese）.［王秀華.一種并行的加速K－均值聚類方法 ［J］.電腦知識(shí)與技術(shù)，2013，9 （18）：4299－4302.］

［6］Srirama SN，Jakovits P，Vainikko E.Adapting scientific computing problems to clouds using MapReduce ［J］.Future Generations Computer Systems，2012，39 （11）：184－192 （in Chinese）. ［Srirama SN，Jakovits P，Vainikko E.使用MapReduce解決云端的科學(xué)計(jì)算問(wèn)題 ［J］.下一代計(jì)算機(jī)系統(tǒng)，2012，39 （11）：184－192.］

［7］HAN Jiawei，kamber.Data mining：Concepts and techniques［M］.Beijing：Mechanical Industry Press，2008：288－375 （in Chinese）.［韓家煒，坎伯.數(shù)據(jù)挖掘概念與技術(shù) ［M］.北京：機(jī)械工業(yè)出版社，2008：288－375.］

［8］TIAN Shenping， 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）.［田森平，吳文亮.自動(dòng)獲取K－means聚類參數(shù)k值的算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32 （1）：274－276.］

［9］ZHOU Aiwu，YU Yafei.The research about clustering algorithm of K－means ［J］.Computer Technology and Development，2011，21 （2）：62－65 （in Chinese）. ［周愛(ài)武，于亞飛.K－means聚類算法的研究 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21 （2）：62－65.］

［10］WANG Xiuhua.A speeding K－means clustering method based on sampling ［J］.Computer and Modernization，2013 （12）：27－29 （in Chinese）.［王秀華.基于隨機(jī)抽樣的加速K－均值聚類方法 ［J］.計(jì)算機(jī)與現(xiàn)代化，2013 （12）：27－29.］

［11］ZHOU Juan，XIONG Zhongyang，ZHANG Yufang.Multiseed clustering algorithm based on max－min distance means［J］.Computer Applications，2006，26 （6）：1425－1427 （in Chinese）.［周涓，熊忠陽(yáng)，張玉芳，等.基于最大最小距離法的多中心聚類算法 ［J］.計(jì)算機(jī)應(yīng)用，2006，26 （6）：1425－1427.］