一種基于MapReduce的改進k-means聚類算法研究

郭晨晨，朱紅康

（山西師范大學 數學與計算機科學學院，山西 臨汾 041000）

一種基于MapReduce的改進k-means聚類算法研究

郭晨晨，朱紅康

（山西師范大學 數學與計算機科學學院，山西 臨汾 041000）

傳統k-means算法的聚類中心需要經過多次迭代運算才能最終穩定，而MapReduce計算框架下的k-means聚類算法在處理迭代運算時效率并不理想．針對上述問題，提出一種新的基于MapReduce的k-means聚類算法．該算法對傳統k-means算法進行了改進，通過將k-means聚類問題轉化為Map和Reduce兩階段的k-means++算法聚類問題，并將權值概念和單通道技術引入到傳統k-means++算法中，提升了算法在MapReduce框架中的執行效率．實驗分析表明，該方法較之傳統方法具有更好的加速比和可擴展性．

k-means；MapReduce；兩階段；單通道；并行化；加速比

在數據挖掘中，聚類是重要的數據分析方法之一，它是在大量模式、樣本點以及對象中發現自然分組的過程．在統計學、模式識別、信息檢索、機器學習等廣泛的領域都扮演著重要的角色．

然而，由于大數據體量巨大、元素復雜，傳統的統計工具和管理系統已經很難適應．一方面，數據集主要存儲于主存儲器中，海量的數據規模造成主存儲器無法容納．另一方面，一些經典聚類算法，其時間復雜度并不是線性的．如果聚類目標規模過大，必然造成時間消耗超出可容忍的范圍．為解決上述矛盾，需要建立新的編程模式和處理模型．MapReduce是目前公認的比較成熟的分布式編程模型．基于其簡單的編程范式、線性架構和自動的可擴展性等特點使之成為大數據處理的理想工具．k-means及其改進算法的時間復雜度是線性的，因此可以內置于MapReduce中．但k-means算法在MapReduce中的實際運行存在明顯不足，一方面，來源于k-means算法自身的缺陷，即需要預先估計類的數量，高度依賴初始樣本點的選取，迭代次數無法估計，缺乏收斂性的保證等；另一方面，來源于MapReduce框架自身的局限性．k-means算法是一個迭代算法，為了得到相對理想的聚類結果，迭代可能需進行多次．而MapReduce本身不支持迭代和遞歸，需要驅動擴展程序輔助完成運算．該擴展程序通過重復執行算法操作來模擬迭代過程，并且每次迭代過程，整個待處理的數據集都需要加載到內存中，且輸出結果需要寫入到文件系統中去．這樣MapReduce框架中的迭代過程常常伴隨著大量的I/O及數據的序列化工作，導致整個系統進程被拖慢．

k-means是最經典的聚類算法之一，改進版本眾多．其中包括針對k-means算法運行效率不高提出的并行k-means算法[1-3]，Zhao等提出的一種基于MapReduce的k-means聚類的解決方案[4]．針對k-means算法對初始點選取的依賴性，Bahmani等提出的一種可擴展的k-means算法[5]．另外，還有建立于GraphLab并行框架之上分布式k-means++算法[6]．然而，以上方法在解決迭代問題時都是以整個數據集為迭代對象，因而并不適合MapReduce框架．Hadian等提出一種并行化和單通道技術結合的技術用以解決并行共享存儲器的問題[7]，但并沒有以MapReduce為框架．目前，也存在一些MapReduce的擴展框架，如Spark[8]、Tw ister[9]、Haloop[10]等．它們都提供了處理迭代和遞歸問題的能力，k-means算法也能夠在這些擴展框架中執行．但這些框架對數據集的規模有嚴格的限定，并不適合海量數據的處理．

基于此，提出一種MapReduce框架上的k-means改進算法，稱為msk-means算法．該算法主要解決了迭代次數作為乘數導致的時間復雜度和空間復雜度的激增，使得系統運行效率大大提升．

1 準備工作

1.1 傳統k-means算法

若一個樣本集包含n個樣本點，d種屬性，那么該樣本集可以表示為矩陣Mn×d．mi,j表示矩陣M中i行j列的元素．第i行的元素可以表示為向量mi．假定C=C1,C2,……Ck為樣本集的一個劃分，那么產生的若干個聚類應該滿足以下2個條件：

則k-means算法可以簡化表示為下面的步驟：

2）將每個點分配到距離初始中心點最近的簇中，并更新中心點；

2個樣本間的相似性度量用下面的公式計算：

1.2 k-means++算法

k-means++算法[11]是k-means算法的一個非常重要的改進算法．它主要解決了k-means算法中存在的2大缺陷，即需要預先規定樣本集中類的數量和初始種子樣本點的隨機選?。?/p>

k-means++算法可簡化為下面的步驟：

1）從輸入的數據點集合中隨機選擇一個點Ci作為第1個聚類中心．

2）對于數據集中的每一個點mi，計算它與最近聚類中心（指已選擇的聚類中心）的距離D mi．

4）重復步驟2）和3）直到k個聚類中心被選出來．

5）利用這k個初始的聚類中心來運行標準的k-means算法．

這里定義的另一個屬性是聚類中心，它是一個聚類的最佳代表．計算方法由下面的式子給出：

1.3 單通道技術

單通道技術即引用“分而治之”的聚類處理方法[14]．對于k-means聚類問題，設n個點組成的點集，并且存在1個權值函數w:．聚類問題可轉化為最小化函數，其中D x,C表示點x到其最近聚類C中點的距離．C=k表示子集數量．

定義1 給定一個關于 k-means的算法A，令 c表示符合樣本集的函數（從若干輸入樣本估計得到），表示符合樣本的最優函數．則競爭比定義為最壞情況下的比率，則算法A稱為b逼近算法．

定義2 算法B為b逼近算法算法，若輸入樣本包含ak個聚類中心，且滿足a＞1，b＞1，則該算法可稱為a,b 逼近算法．

為了之后說明的簡化，假設樣本空間Rd中的任意一點所占內存為O 1．單通道技術“分而治之”的思想如下：

2 msk-means

2.1 msk-means算法描述

本節主要對msk-means進行詳細描述．該方法的基本思路：將一定規模的數據集分割成Chunk，分別存儲在每臺計算機的主存儲器中．然后進行2階段的工作：Map階段，每臺計算機對分得的數據塊運用k-means++算法進行初始階段的聚類，提取出包含少量聚類中心的數據集，稱為中間集；Reduce階段，將每臺計算機產生的中間集通過重組技術形成1個較大的中間集并保存到1臺未使用的計算機上，再次使用k-means++算法，對重組后的中間集進行聚類，得到最后的聚類中心．在2階段，都使用k-means++算法，用于每個Chunk的中間集的提取．如果有c個數據塊，每塊產生k個聚類中心，那么將產生一組k c的中間集．但實際情況比較復雜，每個Chunk中的每個聚類中心都是由不同數量的樣本點產生的，樣本點的數量多少反映出該聚類中心的重要性的差異．因此，對于Map階段產生的中間集中的元素不能統一對待，需要在傳統的k-means++算法中引入權值概念，Map階段在產生若干聚類中心的同時，相應地產生相同數量的權值，以表示每個聚類中心對于整個數據集的影響力，思想來源于文獻 [13]．msk-means算法中關于聚類中心的計算和k-means++算法中的概率公式在文獻 [13]所提算法的基礎上進行了一定的改動，若W mi表示mi的權值，則中心點的計算公式如式 (3)

那么，k-means++算法中的選取概率公式可得

msk-means算法如下．

Map階段：

2）對于B中的每一個Bi，生成1個Map任務并執行k-means++算法，得到1組包含k個加權中心的輸出結果．

Reduce階段：

1）將Map階段產生的輸出結果作為Reduce階段的輸入．

2）再一次執行k-means++算法得到包含k個中心的最終結果．

2.2 msk-means的競爭比

令M表示測試樣本集，B為Chunk集，Ti表示由Bi中提取的一系列聚類中心點集，為msk-means產生的最終中心點集，產生X中到樣本p的最近樣本，表示Chunk Bi中分配tj個中心點．對msk-means算法進行如下推導

利用三角不等式定理

現在，只需要“+”前后的2部分分別推導即可．

假設Chunk Bi分配的最優聚類中心集為，可得

第2部分：

綜合2部分可得，msk-means算法是O log2k逼近算法．

2.3 msk-means聚類質量的度量指標

本文采用SSE（Sum of Squared Errors）評估函數，該函數顯示出聚類的緊湊程度，并且緊湊程度與函數值大小成反相關，即函數值越小，聚類越緊湊，效果越好．評估函數定義如下．

其中cj表示C中的任意聚類中心．

得到評估函數標準形式

2.4 Chunk大小的調整

msk-means算法的輸入除了數據集還需要2個輸入參數，一個是聚類數量k，一個是Chunk大小c．理論上ck,n，n表示數據集樣本數．區間兩邊的值實際均無法取到．實驗證明最有效的內存塊為，因為較小的Chunk表示可以從數據集中提取較多的中間集元素，有利于聚類結果更符合原始數據集的規則．因此，Chunk設定的大小原則：通常情況下設置為，如果數據集規模較小或者較大的中間集不適合硬件環境，那么可以將Chunk調整為更小的值，如log n或10k等．

2.5 復雜度分析

通常，衡量聚類算法效率主要有3個量度：時間復雜度、I/O復雜度、空間復雜度．由于msk-means包含2階段的任務，因而在衡量算法復雜度時，也必須分為2個階段分別考慮．

若k表示聚類數量，n表示數據集中樣本數量，c表示Chunk的大小，p表示Chunk的并行數，I表示迭代次數．設定單個樣本處理的時間復雜度為O I，包括樣本的計算和存儲．由于整個數據集僅從存儲器中讀取1次，因此I=1．則Map階段的I/O復雜度為O n/p，Reduce階段的空間復雜度O k n/c．如果， msk-means算法的I/O復雜度為．

msk-means的空間復雜度主要受Chunk大小c和并行數量p共同影響．Map階段要保證大小為c的Chunk以p并行，則產生的空間復雜度為O c p．Reduce階段，為了存儲Map階段產生的中間集，需要產生O k n/c的空間復雜度．因此msk-means的空間復雜度為O p c+k n/c．最優情況是，當，空間復雜度表示為．

由于msk-means算法“單遍”的特點，因此在I/O復雜度方面是最優的．以下主要討論該算法在時間復雜度和空間復雜度上的優勢．

為了更好的比較，選取幾種有影響力算法進行對比．包括可測k-means++算法[5]，即k-means‖算法以及流式k-means逼近算法[12]，即SKMA算法．以及并行k-means算法和并行k-means++，如表1所示．

表1 msk-means與其他算法的復雜度對比Tab.1 Contrast between msk-means and other algorithms

由表1所示結果可得，msk-means比SKMA算法時間效率上快log k倍，k-means‖算法雖然具有迭代性，但如果聚類數量較大，并且最大迭代數目設置較低（即k的值較大，I的值較低），那么相比SKMA算法來說效率更高．對于msk-means與k-means‖的比較相對復雜．假設k-means‖的時間效率更好，那么可以用下面的式子表示

但實際的MapReduce環境中，處理器的數量p不過是幾千這樣的數量級，而聚類的數量k顯然遠遠小于數據集中樣本的數量n．因此，在MapReduce運行環境中上述不等式是不成立的，即msk-means的時間效率要優于k-means‖算法．

本文所提方法的待改進的方面是較為寬松的誤差逼近邊界，最優結果相比其他算法效率要低一些，但這并不是實際情況的反映，是理論上存在的理想情況．

3 實驗和結果分析

3.1 實驗環境

本文采用的分布式實驗框架是由40臺計算機組成的私有云．每臺計算機操作系統為Ubuntu Linux 12.04，CPU為雙核2.4GHz Xeon處理器，內存為12GB．實驗所用的主要軟件包括ApacheHadoop1.2，OpenJDK等．

3.2 單機處理比較實驗

本節通過在單機上運行msk-means算法和其他算法來展示不同算法在Hadoop集群中的1個計算節點上的性能對比．使用單機是由于大多數UCI數據集規模并不大，單機的處理能力可以完成．在單機實驗使用真實世界的數據集，從時間效率和聚類質量（SSE）2方面衡量幾種算法的性能．文獻 [5，12]表明在處理小規模數據集時k-means‖與SKMA比k-means++的性能要弱，因此，本實驗并沒有將其加入對比．在實驗中分別設置每個數據集的聚類數量k為10、50、100，birth數據集由于其自身的聚類數量是100，因而沒有考慮其他情況．實驗數據采用國際公認的UCI數據集，詳情如表2所示．

表2 實驗數據集匯總表Tab.2 Summary of experimental data sets

實驗1結果如表3所示．

表3 msk-means與其他算法單機環境的性能對比實驗Tab.3 Performance comparison of single machine environment with msk-means and other algorithms

從表3可知，msk-means在聚類質量上基本與k-means算法持平，略低于k-means++算法．雖然本次實驗實在單機上完成的，但msk-means算法執行效率很高，特別在規模較大的數據集中體現的尤為明顯．

3.3 集群加速比性能實驗

加速比是衡量系統可擴展性優劣的可靠指標，本節所做的集群加速比性能實驗主要考察算法2個方面的性能，實驗1是測試當Hadoop集群中的計算節點增加，處理相同規模數據時，系統運行速度是如何提升的．實驗2是在40個計算節點滿負荷運行時，隨著待處理數據集的增加，運行時間相應的變化．由于需要的數據量巨大，本實驗采用實驗室開發的聚類數據生成器生成的40GB人工數據集進行實驗。該數據集從5維邊長為500的超立方體中生成，要求生成50個類別，加入的數據點服從標準差為10的高斯分布，初始聚類中心隨機產生．

實驗1首先選擇1個計算節點參與計算，并分別選擇2、4、8、16、24、32、40個節點參與計算．考察在逐漸增加計算節點的情況下，分布式系統中完成任務所用的時間，實驗結果如圖1所示．從圖中可以看出：隨著計算節點的線性增加，系統運行速度與單機運行速度相比呈現線性變化．如圖1所示．

圖1 加速比與計算節點數量的關系Fig.1 The relationship between speedup and calculation of the number of nodes

實驗2人工生成6個數據集，分別包含10、20、40、60、80、100億條數據．分別將它們加入系統參與計算，實驗結果表明隨著待處理數據規模的增加，運行時間的增速亦在可接受的范圍，表現出msk-means良好的可擴展性．如圖2所示．

圖2 數據集大小與運行時間的關系Fig.2 The relationship between the size of dataset and running time

3.4 Chunk大小對算法精度的影響實驗

在MapReduce分布式框架中，Chunk大小對結果有一定的影響，本節實驗通過調整Chunk大小展示對msk-means算法聚類精度的影響．實驗數據采用了USCensus和KDD04數據集進行實驗，將Chunk大小從k log n到取值若干，實驗結果如表4所示．

表4 Chunk大小對實驗結果的影響Tab.4 The effect of chunk size on quality of results

從表4可得，對于USCensus數據集，chunk大小對實驗結果的影響很小，但對于KDD04數據集影響很大．特別地，當簇數為10時，隨著chunk逐漸增大，聚類質量顯著下降．原因在于KDD04數據集規模較小，而chunk大小較大時，中間集會相對較小，不能充分代表原始數據集．而簇數為50和100的測試顯示，chunk大小對實驗結果影響較小，因為這時的中間集為k n/c，較大的k使得中間集可以很好的代表原始數據集．因此，可以得到這樣的結論：當數據集規模巨大，選擇為chunk大小更為合理．

3.5 Mahout框架下的對比實驗

Apache Mahout是當下十分流行的機器學習與數據挖掘的開源框架，本節旨在通過Mahout框架下完成算法運行效率的比較試驗，進一步說明 msk-means算法的優越性．實驗數據采用了同3.3節人工合成數據集．實驗結果如表5所示．

表5 Mahout框架的聚類質量與效率的比較實驗Tab.5 Comparison of quality and efficiency under Mahout

從表5可知，msk-means算法在聚類質量和時間效率方面都有很大的提高．

4 結論

本文提出一種基于MapReduce的改進k-means聚類算法msk-means，該算法利用單通道思想優化迭代算法的執行過程，并引入基于權的k-means算法相關內容，突出了不同聚類中心對于整體數據集影響力的差異性．搭建Hadoop云計算平臺，分別進行了單計算節點和多計算節點的模擬實驗，并且為了更好的說明算法的可行性，在Mahout框架下進行性能比較實驗．結果表明，msk-means算法在MapReduce并行化后部署在Hadoop集群上運行，具有良好的加速比和可擴展性，在信息量激增、傳統統計工具失效的背景下，所做工作具有一定的現實意義．

[1]Nickolls J，Buck I，Garland M，et al．Scalable parallel programming with cuda[J]．ACM Queue，2008，6（2）：40-53．

[2]趙衛中，馬慧芳，傅燕翔，等．基于云計算平臺Hadoop的并行k-means聚類算法設計研究 [J]．計算機科學，2011，38（10）：166-168．

[3]江小平，李成華，向文，等．k-means聚類算法的MapReduce并行化實現 [J]．華中科技大學學報（自然科學版），2011，39（S1）：120-124．

[4]Zhao Wei-zhong，Ma Hui-fang，He Qing．Parallel k-means clustering based on MapReduce[M]．Germany：Springer Berlin Heidelberg，2009：674-679．

[5]Bahmani B，Moseley B，Vattani A，et al．Scalable k-means++[J]．Proceedings of the Vldb Endowment，2012，5（7）：622-633．

[6]Low Y，Bickson D，Gonzalez J，et al．Distributed graphlab：a framework for machine learning and data mining in the cloud[J]．Proceedings of the Vldb Endowment，2012，5（8）：716-727．

[7]Hadian A，Shahrivari S．High performance parallel k-means clustering for disk-resident datasets on multi-core CPUs[J]．Journal of Supercomputing，2014，69（2）：845-863．

[8]Zaharia M，Chowdhury M，Senker S，et al．Spark：cluster computing with working sets[C]//Usenix Conference on Hot Topics in Cloud Computing，2010，15（1）：1765-1773．

[9]Ekanayake J，Li Hui，Gunarathne T，et al．Twister：a runtime for iterative MapReduce[C]//Acm International Symposium on High Performance Distributed Computing，2010：810-818．

[10]Lin Yi-an．Map-Reduce for machine learning on multicore[J]．Advances in Neural Information Processing Systems，2006，19（1）：281-288．

[11]Arthur D，Vassilvitskii S．K-means++：the advantages of careful Seeding[C]//The Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics，2007：1027-1035．

[12]Ailon N，Jaiswal R，Monteleoni C．Streaming k-means approximation[J]．Advances in Neural Information Processing Systems，2009：10-18．

[13]Kerdprasop K，Kerdprasop N，Sattayatham P．Lecture notes in computer science[M]．Germany：Springer Berlin Heidelberg，2005：488-497．

[14]Guha S，Meyerson A，Mishra N，et al．Clustering data streams：theory and practice[J]．IEEE Transactions on Knowledge and Data Engineering，2003，15（3）：515-528．

[責任編輯 田 豐 夏紅梅]

An improved k-means clustering algorithm based on MapReduce

GUO Chenchen，ZHU Hongkang

(School of Mathematics and Computer Science,Shanxi Normal University,Shanxi Linfen 041000,China)

The clustering centers of the traditional K-means algorithm need many iterations to be stable,and the efficiency of the K-means clustering algorithm in the MapReduce computing framework is not ideal.In view of the above problems, a new K-means clustering algorithm based on MapReduce is proposed.This algorithm has improved the traditional K-means algorithm.By sing-pass method,the K-means clustering problem is transformed into Map and Reduce two stages of k-mean algorithm clustering problem.And the concept of the weights is introduced into the traditional k-means++algorithm,which improves the efficiency of the algorithm in the MapReduce framework.Experimental results show that the proposed method is better than the traditional method and has a better speedup and scalability.

k-means;MapReduce;two stages;single pass;parallelization;speedup

TP18

A

1007-2373(2016)05-0035-09

10.14081/j.cnki.hgdxb.2016.05.006

2016-09-27

山西省自然科學基金（2015011040）

郭晨晨（1992-）男（漢族），碩士生．通訊作者：朱紅康（1975-），男（漢族），副教授，博士．