郭晨晨，朱紅康

（山西師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西 臨汾 041000）

一種基于MapReduce的改進(jìn)k-means聚類算法研究

郭晨晨，朱紅康

（山西師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西 臨汾 041000）

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

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

在數(shù)據(jù)挖掘中，聚類是重要的數(shù)據(jù)分析方法之一，它是在大量模式、樣本點(diǎn)以及對(duì)象中發(fā)現(xiàn)自然分組的過程．在統(tǒng)計(jì)學(xué)、模式識(shí)別、信息檢索、機(jī)器學(xué)習(xí)等廣泛的領(lǐng)域都扮演著重要的角色．

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

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

基于此，提出一種MapReduce框架上的k-means改進(jìn)算法，稱為msk-means算法．該算法主要解決了迭代次數(shù)作為乘數(shù)導(dǎo)致的時(shí)間復(fù)雜度和空間復(fù)雜度的激增，使得系統(tǒng)運(yùn)行效率大大提升．

1 準(zhǔn)備工作

1.1 傳統(tǒng)k-means算法

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

則k-means算法可以簡(jiǎn)化表示為下面的步驟：

2）將每個(gè)點(diǎn)分配到距離初始中心點(diǎn)最近的簇中，并更新中心點(diǎn)；

2個(gè)樣本間的相似性度量用下面的公式計(jì)算：

1.2 k-means++算法

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

k-means++算法可簡(jiǎn)化為下面的步驟：

1）從輸入的數(shù)據(jù)點(diǎn)集合中隨機(jī)選擇一個(gè)點(diǎn)Ci作為第1個(gè)聚類中心．

2）對(duì)于數(shù)據(jù)集中的每一個(gè)點(diǎn)mi，計(jì)算它與最近聚類中心（指已選擇的聚類中心）的距離D mi．

4）重復(fù)步驟2）和3）直到k個(gè)聚類中心被選出來．

5）利用這k個(gè)初始的聚類中心來運(yùn)行標(biāo)準(zhǔn)的k-means算法．

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

1.3 單通道技術(shù)

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

定義1 給定一個(gè)關(guān)于 k-means的算法A，令 c表示符合樣本集的函數(shù)（從若干輸入樣本估計(jì)得到），表示符合樣本的最優(yōu)函數(shù)．則競(jìng)爭(zhēng)比定義為最壞情況下的比率，則算法A稱為b逼近算法．

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

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

2 msk-means

2.1 msk-means算法描述

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

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

msk-means算法如下．

Map階段：

2）對(duì)于B中的每一個(gè)Bi，生成1個(gè)Map任務(wù)并執(zhí)行k-means++算法，得到1組包含k個(gè)加權(quán)中心的輸出結(jié)果．

Reduce階段：

1）將Map階段產(chǎn)生的輸出結(jié)果作為Reduce階段的輸入．

2）再一次執(zhí)行k-means++算法得到包含k個(gè)中心的最終結(jié)果．

2.2 msk-means的競(jìng)爭(zhēng)比

令M表示測(cè)試樣本集，B為Chunk集，Ti表示由Bi中提取的一系列聚類中心點(diǎn)集，為msk-means產(chǎn)生的最終中心點(diǎn)集，產(chǎn)生X中到樣本p的最近樣本，表示Chunk Bi中分配tj個(gè)中心點(diǎn)．對(duì)msk-means算法進(jìn)行如下推導(dǎo)

利用三角不等式定理

現(xiàn)在，只需要“+”前后的2部分分別推導(dǎo)即可．

假設(shè)Chunk Bi分配的最優(yōu)聚類中心集為，可得

第2部分：

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

2.3 msk-means聚類質(zhì)量的度量指標(biāo)

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

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

得到評(píng)估函數(shù)標(biāo)準(zhǔn)形式

2.4 Chunk大小的調(diào)整

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

2.5 復(fù)雜度分析

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

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

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

由于msk-means算法“單遍”的特點(diǎn)，因此在I/O復(fù)雜度方面是最優(yōu)的．以下主要討論該算法在時(shí)間復(fù)雜度和空間復(fù)雜度上的優(yōu)勢(shì)．

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

表1 msk-means與其他算法的復(fù)雜度對(duì)比Tab.1 Contrast between msk-means and other algorithms

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

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

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

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

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

本文采用的分布式實(shí)驗(yàn)框架是由40臺(tái)計(jì)算機(jī)組成的私有云．每臺(tái)計(jì)算機(jī)操作系統(tǒng)為Ubuntu Linux 12.04，CPU為雙核2.4GHz Xeon處理器，內(nèi)存為12GB．實(shí)驗(yàn)所用的主要軟件包括ApacheHadoop1.2，OpenJDK等．

3.2 單機(jī)處理比較實(shí)驗(yàn)

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

表2 實(shí)驗(yàn)數(shù)據(jù)集匯總表Tab.2 Summary of experimental data sets

實(shí)驗(yàn)1結(jié)果如表3所示．

表3 msk-means與其他算法單機(jī)環(huán)境的性能對(duì)比實(shí)驗(yàn)Tab.3 Performance comparison of single machine environment with msk-means and other algorithms

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

3.3 集群加速比性能實(shí)驗(yàn)

加速比是衡量系統(tǒng)可擴(kuò)展性優(yōu)劣的可靠指標(biāo)，本節(jié)所做的集群加速比性能實(shí)驗(yàn)主要考察算法2個(gè)方面的性能，實(shí)驗(yàn)1是測(cè)試當(dāng)Hadoop集群中的計(jì)算節(jié)點(diǎn)增加，處理相同規(guī)模數(shù)據(jù)時(shí)，系統(tǒng)運(yùn)行速度是如何提升的．實(shí)驗(yàn)2是在40個(gè)計(jì)算節(jié)點(diǎn)滿負(fù)荷運(yùn)行時(shí)，隨著待處理數(shù)據(jù)集的增加，運(yùn)行時(shí)間相應(yīng)的變化．由于需要的數(shù)據(jù)量巨大，本實(shí)驗(yàn)采用實(shí)驗(yàn)室開發(fā)的聚類數(shù)據(jù)生成器生成的40GB人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集從5維邊長(zhǎng)為500的超立方體中生成，要求生成50個(gè)類別，加入的數(shù)據(jù)點(diǎn)服從標(biāo)準(zhǔn)差為10的高斯分布，初始聚類中心隨機(jī)產(chǎn)生．

實(shí)驗(yàn)1首先選擇1個(gè)計(jì)算節(jié)點(diǎn)參與計(jì)算，并分別選擇2、4、8、16、24、32、40個(gè)節(jié)點(diǎn)參與計(jì)算．考察在逐漸增加計(jì)算節(jié)點(diǎn)的情況下，分布式系統(tǒng)中完成任務(wù)所用的時(shí)間，實(shí)驗(yàn)結(jié)果如圖1所示．從圖中可以看出：隨著計(jì)算節(jié)點(diǎn)的線性增加，系統(tǒng)運(yùn)行速度與單機(jī)運(yùn)行速度相比呈現(xiàn)線性變化．如圖1所示．

圖1 加速比與計(jì)算節(jié)點(diǎn)數(shù)量的關(guān)系Fig.1 The relationship between speedup and calculation of the number of nodes

實(shí)驗(yàn)2人工生成6個(gè)數(shù)據(jù)集，分別包含10、20、40、60、80、100億條數(shù)據(jù)．分別將它們加入系統(tǒng)參與計(jì)算，實(shí)驗(yàn)結(jié)果表明隨著待處理數(shù)據(jù)規(guī)模的增加，運(yùn)行時(shí)間的增速亦在可接受的范圍，表現(xiàn)出msk-means良好的可擴(kuò)展性．如圖2所示．

圖2 數(shù)據(jù)集大小與運(yùn)行時(shí)間的關(guān)系Fig.2 The relationship between the size of dataset and running time

3.4 Chunk大小對(duì)算法精度的影響實(shí)驗(yàn)

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

表4 Chunk大小對(duì)實(shí)驗(yàn)結(jié)果的影響Tab.4 The effect of chunk size on quality of results

從表4可得，對(duì)于USCensus數(shù)據(jù)集，chunk大小對(duì)實(shí)驗(yàn)結(jié)果的影響很小，但對(duì)于KDD04數(shù)據(jù)集影響很大．特別地，當(dāng)簇?cái)?shù)為10時(shí)，隨著chunk逐漸增大，聚類質(zhì)量顯著下降．原因在于KDD04數(shù)據(jù)集規(guī)模較小，而chunk大小較大時(shí)，中間集會(huì)相對(duì)較小，不能充分代表原始數(shù)據(jù)集．而簇?cái)?shù)為50和100的測(cè)試顯示，chunk大小對(duì)實(shí)驗(yàn)結(jié)果影響較小，因?yàn)檫@時(shí)的中間集為k n/c，較大的k使得中間集可以很好的代表原始數(shù)據(jù)集．因此，可以得到這樣的結(jié)論：當(dāng)數(shù)據(jù)集規(guī)模巨大，選擇為chunk大小更為合理．

3.5 Mahout框架下的對(duì)比實(shí)驗(yàn)

Apache Mahout是當(dāng)下十分流行的機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘的開源框架，本節(jié)旨在通過Mahout框架下完成算法運(yùn)行效率的比較試驗(yàn)，進(jìn)一步說明 msk-means算法的優(yōu)越性．實(shí)驗(yàn)數(shù)據(jù)采用了同3.3節(jié)人工合成數(shù)據(jù)集．實(shí)驗(yàn)結(jié)果如表5所示．

表5 Mahout框架的聚類質(zhì)量與效率的比較實(shí)驗(yàn)Tab.5 Comparison of quality and efficiency under Mahout

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

4 結(jié)論

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

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

[2]趙衛(wèi)中，馬慧芳，傅燕翔，等．基于云計(jì)算平臺(tái)Hadoop的并行k-means聚類算法設(shè)計(jì)研究 [J]．計(jì)算機(jī)科學(xué)，2011，38（10）：166-168．

[3]江小平，李成華，向文，等．k-means聚類算法的MapReduce并行化實(shí)現(xiàn) [J]．華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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．

[責(zé)任編輯 田 豐 夏紅梅]

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

山西省自然科學(xué)基金（2015011040）

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