加速大數據聚類K－means算法的改進

韓 巖，李 曉

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

0 引 言

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

1 相關概念

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

（2）最大最小距離法：具體詳細內容參見文獻 ［11］。

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

（4）加權聚類準則函數。

聚類準則函數［2］：

由于是對大數據進行聚類，防止孤立點對Jc值的影響，采用加權聚類準則函數

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

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

圖1 MapReduce執行過程

2 改進的K－means算法

2.1 改進算法思想

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

改進算法的思路如下：

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

（1）適當選擇k個類的初始中心；

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

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

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

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

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

2.2 改進算法的執行流程

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

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

（2）實現海量數據的K－means算法并行化計算。

2.2.2 執行流程

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

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

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

1）先從抽樣數據X′隨機選擇一個樣本x′i，作為抽樣數據聚類中心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）如果現有聚類中心的個數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）重復4），直到獲得k 個聚類中心，即C1＝ ｛x′1，x′2…x′k｝

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

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

3 實驗與結果分析

3.1 實驗環境

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

3.2 實驗結果與分析

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

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

首先才用人工標注的20條測試數據進行測試，數據分布如圖2所示。

圖2 標注數據分布

實驗1運行結果見表1。

表1 不同方法不同聚類個數聚類結果

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

圖3 不同聚類個數與Jc趨勢

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

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

表2 單機下聚類結果

3.2.3 實驗3：驗證改進算法可以并行執行

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

表3 集群下運行結果

通過表2得出以下結論：當數據量較小時，最大最小距離法Jc的值最小且執行時間最短；隨著數據量的增加，最大最小距離法計算聚類中心時間增加導致計算時間過長；繼續增加數據量時，這種方法將不在適合聚類運算。大數據量時，這種改進的方法執行時間大大減少了且加權準則函數值也降低了，提高聚類的質量。

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

4 結束語

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

［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）.［周愛武，崔丹丹，潘勇.一種優化初始聚類中心的Kmeans聚類算法 ［J］.微型機與應用，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］.農業網絡信息，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］.計算機技術與發展，2011，21 （7）：54－57.］

［4］QIAN Yanjiang.Research and realization of large－scale data clustering techniques ［D］.Chengdu：Chengdu University，2009 （in Chinese）.［錢彥江.大規模數據聚類技術研究與實現 ［D］.成都：電子科技大學，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］.電腦知識與技術，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解決云端的科學計算問題 ［J］.下一代計算機系統，2012，39 （11）：184－192.］

［7］HAN Jiawei，kamber.Data mining：Concepts and techniques［M］.Beijing：Mechanical Industry Press，2008：288－375 （in Chinese）.［韓家煒，坎伯.數據挖掘概念與技術 ［M］.北京：機械工業出版社，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聚類參數k值的算法［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）. ［周愛武，于亞飛.K－means聚類算法的研究 ［J］.計算機技術與發展，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］.計算機與現代化，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］.計算機應用，2006，26 （6）：1425－1427.］