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

韓 巖，李 曉

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

0 引 言

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

1 相關(guān)概念

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

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

（3）歐氏距離 （簡稱距離）Euclidean［2］

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

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

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

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

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

圖1 MapReduce執(zhí)行過程

2 改進的K－means算法

2.1 改進算法思想

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

改進算法的思路如下：

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

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

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

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

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

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

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

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

2.2.1 改進算法主要有個兩個主要的步驟

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

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

2.2.2 執(zhí)行流程

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

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

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

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

2）用X 中樣本集計算出與c1歐氏距離式 （1）最遠的點x′j，作為第2個中心點c2；

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

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

4）如果現(xiàn)有聚類中心的個數(shù)r（r＜k），得到了C1＝｛x′1，x′2…x′r｝，即確定第r＋1個中心點：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 個聚類中心，即C1＝ ｛x′1，x′2…x′k｝

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

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

3 實驗與結(jié)果分析

3.1 實驗環(huán)境

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

3.2 實驗結(jié)果與分析

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

3.2.1 實驗1：驗證改進的K－means算法可行性

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

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

實驗1運行結(jié)果見表1。

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

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

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

3.2.2 實驗2：驗證改進的K－means算法有效性

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

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

3.2.3 實驗3：驗證改進算法可以并行執(zhí)行

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

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

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

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

4 結(jié)束語

本文主要通過Hadoop平臺上的MapReduce框架實現(xiàn)K－means算法并行化的聚類操作。實驗結(jié)果表明：這種改進的方法選取了較優(yōu)的初始聚類中心，降低了對初始聚類中心的依賴性，提高了聚類的質(zhì)量及運行效率，加速了聚類的收斂速度。特別是在集群環(huán)境下，數(shù)據(jù)量較大時，完全隨機分布的數(shù)據(jù)有明顯的效果。下一步工作主要在于抽樣數(shù)據(jù)質(zhì)量與優(yōu)化上再進行改進；集群優(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）.［周愛武，崔丹丹，潘勇.一種優(yōu)化初始聚類中心的Kmeans聚類算法 ［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）. ［汪嘉，姜明富，李友國.一種基于改進的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］.計算機技術(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ù)研究與實現(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ù)，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］.下一代計算機系統(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］.北京：機械工業(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）.［田森平，吳文亮.自動獲取K－means聚類參數(shù)k值的算法［J］.計算機工程與設(shè)計，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）. ［周愛武，于亞飛.K－means聚類算法的研究 ［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）.［王秀華.基于隨機抽樣的加速K－均值聚類方法 ［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）.［周涓，熊忠陽，張玉芳，等.基于最大最小距離法的多中心聚類算法 ［J］.計算機應(yīng)用，2006，26 （6）：1425－1427.］