唐 浩，楊余旺，辛智斌

(1.南京理工大學 計算機科學與工程學院，江蘇 南京 210094；2.淮海集團工業(yè)有限公司，山西 長治 046000)

基于MapReduce的單遍K-means聚類算法

唐 浩1，楊余旺1，辛智斌2

(1.南京理工大學 計算機科學與工程學院，江蘇 南京 210094；2.淮海集團工業(yè)有限公司，山西 長治 046000)

K-means應用于MapReduce框架的大數(shù)據(jù)處理可顯著提高K-means對大數(shù)據(jù)集的處理能力。但K-means聚類算法需要進行多次迭代才能達到可接受的效果，并將每次迭代作為一個獨立map作業(yè)執(zhí)行，需要讀寫整個數(shù)據(jù)集，從而導致顯著的I/O消耗，與MapReduce框架的設計理念不符。為此，提出了一個基于MapReduce的單遍K-means算法(MRSK)。該算法采用流數(shù)據(jù)單遍算法讀取數(shù)據(jù)，聚類時采用K-means++初始化seeding算法得到初始聚類中心。在理論分析MRSK算法復雜度的基礎上，進行了MRSK算法的測試驗證和相關分析。驗證實驗結果表明，相對于基于MapReduce和基于數(shù)據(jù)流的K-means聚類算法，所提出的MRSK算法在執(zhí)行速度和聚類效果方面具有更好的優(yōu)勢。

MapReduce框架；數(shù)據(jù)聚類；K-means++；Mahout；單遍技術

0 引 言

K-means[1]聚類算法是數(shù)據(jù)挖掘領域中的一種重要方法，由于計算簡單、收斂速度快，在機器學習、圖像處理等領域應用廣泛。近年來，隨著數(shù)據(jù)量的不斷攀升，傳統(tǒng)的K-means聚類分析方法已無法滿足大數(shù)據(jù)[2]的需求，所以亟需對傳統(tǒng)的K-means方法做出改進以支持大規(guī)模數(shù)據(jù)分析。

MapReduce[3]是由谷歌提出的一種大數(shù)據(jù)并行計算框架。MapReduce的3個主要特點：模型使用方便、適用于大型數(shù)據(jù)處理、可擴展并內(nèi)置容錯，使其成為一種理想的大數(shù)據(jù)處理框架[4]。如今，K-means已經(jīng)成功地應用在了MapReduce框架中。

Zhao W等提出的基于MapReduce的K-means聚類算法，是一種快速聚類方案，利用了運行在Hadoop[5]框架上的Mahout[6]項目，稱之為PKMeans[7]。艾隆等提出的基于數(shù)據(jù)流的K-means算法，利用了基于數(shù)據(jù)流的單通技術[8]，稱之為SKMA[9]。

上述解決方案為了達到可接受的結果，都需要對整個數(shù)據(jù)集進行多次迭代，而MapReduce本質(zhì)上不支持迭代。在每次迭代中，整個數(shù)據(jù)集必須從磁盤加載到內(nèi)存中，數(shù)據(jù)集經(jīng)過處理后，輸出時必須再一次寫入磁盤，因此，每一次迭代都會產(chǎn)生大量和I/O相關的操作，如磁盤I/O、數(shù)據(jù)序列化等等，嚴重影響了程序的執(zhí)行速度。所以這些方案并不適合MapReduce框架。Hadian和Shahrivari為了共享內(nèi)存，實現(xiàn)并行計算，提出了一種并行的單遍聚類算法[10]，但是該算法沒有使用MapReduce框架。

為此，文中提出一種基于MapReduce的單遍K-means聚類算法(MRSK)。該算法利用流數(shù)據(jù)單遍算法讀取數(shù)據(jù)，在數(shù)據(jù)聚類過程的map階段采用K-means++初始化Seeding算法[11]得到中間簇中心集；在reduce階段，采用支持權重的K-means++初始化Seeding改進算法進行中間簇中心集處理，并獲得初始聚類中心，再利用K-means進行聚類計算，得到最終聚類結果。

1 K-means++與單遍算法

1.1K-means++初始化Seeding

K-means是一種簡單快速且高效的聚類算法[12]。質(zhì)心的計算如下：

(1)

初始聚類中心的選取對K-means影響很大，但是K-means隨機選取初始聚類中心，無法保證聚類效果。K-means++通過初始化Seeding算法[13]，可以提供一個較好的初始聚類中心。

通過式(2)初始聚類中心：

(2)

初始化Seeding算法的步驟為：

算法1：K-means++中心初始化。

1:執(zhí)行K-means++(M,k)；

5:end while

7:結束

1.2單遍算法

單遍算法[14]是流式數(shù)據(jù)聚類的經(jīng)典方法。該算法依據(jù)數(shù)據(jù)輸入順序依次處理數(shù)據(jù)，依據(jù)當前數(shù)據(jù)與現(xiàn)有類的匹配度大小，判定該數(shù)據(jù)歸入已有類或另外創(chuàng)建一個新類。

利用歐氏距離作為匹配度判定依據(jù)，歐式距離公式如下：

2 MRSK算法

2.1算法流程

提出MRSK方法，是為了解決現(xiàn)有基于MapReduce方案中因多次迭代而引起的I/O消耗問題。在MRSK方法中，將整個數(shù)據(jù)集分割成更小的，可存于每臺機器內(nèi)存的數(shù)據(jù)塊，并分發(fā)這些數(shù)據(jù)塊到可用的機器。然后，每個塊由所處的機器獨立聚簇，每個塊經(jīng)過并行處理后產(chǎn)生若干中間簇中心，之后將中間簇中心的集合從每臺機器中抽取出來作為一個更小的數(shù)據(jù)集裝載進單獨一臺機器的主存中，最終的聚類中心從中間簇中心集中通過重新聚類產(chǎn)生。

每個塊所在的機器在處理數(shù)據(jù)時采用單遍法，對當前到達的數(shù)據(jù)進行聚類，依據(jù)匹配度大小，將數(shù)據(jù)判為已有類或創(chuàng)建一個新類。采用單遍算法，計算過程中整個數(shù)據(jù)集只被讀取了一次。

由于每個塊的處理是相互獨立的，每個塊可以在一個專用的map任務中處理。也就是說，每個map任務選擇一個數(shù)據(jù)集分塊，并在數(shù)據(jù)塊上執(zhí)行K-means++初始化Seeding算法，得到中間簇中心和每個簇中心的權重，然后各聚類中心和各中心的權重作為結果輸出。Map過程完成后，所有加權中心形成中間簇中心集，并作為map輸出。這個中間簇中心集會分配給一個單獨的reduce任務。Reduce任務得到中間簇中心和它們的權重后，會采用改進的支持權重的K-means++初始化Seeding算法得到初始簇中心，然后通過改進的K-means算法得到最終的聚類中心。MRSK算法的完整流程如算法2所示。

算法2:MRSK算法。

1：執(zhí)行MRSK(M,k)

2：Map過程：

3：將數(shù)據(jù)集M分割為?塊，構成集合M=M1,M2,…,M?；

4：對于集合M中的每個Mi執(zhí)行步驟5；

8：end while

10：Map任務結束；

11：Reduce任務：

12：Map任務的輸出構成中間簇中心集Cw；

16：end while

20：結束

2.2MRSK聚類

把整個執(zhí)行過程放在MapReduce框架中。數(shù)據(jù)塊處理放在map階段，中間簇中心集的處理放在reduce階段。如前所述，提出方案的主要優(yōu)勢是使用了數(shù)據(jù)流單遍算法，降低了迭代過程中的I/O消耗，同時也提高了執(zhí)行速度。

在這兩個階段中，均使用了K-means++算法，這是因為K-means++的初始化Seeding算法有助于提高算法的聚類效果。對于每個數(shù)據(jù)塊，利用K-means++算法取得在此數(shù)據(jù)塊上的k個聚類中心。因此，如果有c個數(shù)據(jù)塊，在每個數(shù)據(jù)塊上使用K-means++后，將會生成一個擁有k·c個元素的中間簇中心集合。這個集合就是map階段的輸出。

此外，使用聚類中心的權重來幫助提高MRSK的精確度。每個聚類中心分配的數(shù)據(jù)項的個數(shù)表明了該中心的重要性。因此，對于獲得中間簇中心，必須拓展K-means++算法以支持加權。為了達到此目的，需要改進初始化聚類中心計算方法(式2)和聚類中心計算方法(式1)。

在K-means++算法中，利用式(4)初始化聚類中心，在之后的迭代過程中，使用式(5)計算簇中心。

(4)

初始化簇中心利用式(5)：

(5)

之后的迭代過程中，簇中心的選取使用式(6)：

(6)

3 算法復雜度分析

典型的聚類算法有三種類型的復雜度：時間復雜度、I/O復雜度和空間復雜度。MRSK有兩個過程：map階段處理數(shù)據(jù)塊和reduce階段在中間簇中心集上運行K-means++算法。為確定每一種類型的復雜度，必須考慮這兩個階段。對于MRSK復雜性的分析，提出了以下假設：k為簇的個數(shù)，n為數(shù)據(jù)集中數(shù)據(jù)項的數(shù)量，c為每個數(shù)據(jù)塊的大小，p為可以并行處理的數(shù)據(jù)塊數(shù)，I為直到收斂為止總的迭代次數(shù)。值得注意的是，假設計算和存儲一個數(shù)據(jù)項的時間復雜度為O(1)(在大部分相似的文獻中也都做了這樣的假設)。3.1數(shù)據(jù)塊大小設定

為了實現(xiàn)聚類，MRSK需要兩個重要的參數(shù)：聚簇個數(shù)k和數(shù)據(jù)塊大小c。如何設置塊大小需要考慮，理論上，塊大小最小為k，最大為n，但這兩個極端值都并不切合實際。

但是如果數(shù)據(jù)集不是非常大，塊大小可以被設置為較小的值，如k·logn或者k的倍數(shù)。因為塊較小，可以產(chǎn)生更多的中間簇中心，從而可以更好地代表原始數(shù)據(jù)集，得到的聚類結果也會更好。

3.2I/O復雜度

3.3空間復雜度

3.4時間復雜度

3.5與相關工作進行復雜度對比

在前面提到的PKMeans和SKMA中，PKMeans利用了Apache Hadoop Mahout項目，是標準K-means在MapReduce框架中的實現(xiàn)；SKMA算法將原始數(shù)據(jù)集分割為多個小的子集，在每個子集上利用K-means#算法選擇k個中心構成中間簇中心集，然后利用K-means++算法[11]從中間簇中心集中選出最終的k個中心。

表1分別列出了PKMeans、SKMA和MRSK的三種復雜度。在大數(shù)據(jù)集中，數(shù)據(jù)量n很大，所以聚類算法要達到收斂，需要經(jīng)過多次迭代，從而導致I很大，而且容易得到n?I>k>p。可以發(fā)現(xiàn)，在I/O復雜度上，PKMeans最高，MRSK與SKMA相當；但是在時間復雜度和空間復雜度上MRSK均比其他兩種算法低。通過比較可以得出，相對于另外兩種算法，MRSK復雜度最低。

表1 復雜度比較

4 實驗與結果分析

4.1實驗設置

實驗中，使用6臺服務器搭建Hadoop集群，每臺機器CPU為Intel Xeon E5520*2，內(nèi)存16 G。機器上安裝Centos6.5(64位)系統(tǒng)，Open JDK 7，CDH5(Cloudera Hadoop 5)和Mahout0.8。

主要目標是比較MRSK算法和另外兩種算法的執(zhí)行速度和精確度。為了比較三種算法對于大數(shù)據(jù)集的處理能力和效果，生成了四個大型合成數(shù)據(jù)集，分別包括10，50，100，和500個簇。每個數(shù)據(jù)集擁有10億數(shù)據(jù)項。每個數(shù)據(jù)項有5個特征，標準偏差為10，因此，最優(yōu)聚類時，SSE大約為5·1011。

4.2評價指標

在實驗中，主要比較在相同情況下三種算法的執(zhí)行速度和聚類效果。執(zhí)行速度通過執(zhí)行時間來比較。聚類效果通過誤差平方和函數(shù)SSE(Sum of Squares for Error)來比較。SSE顯示簇的緊湊性，SSE值低，意味著聚類效果更好。SSE計算公式如下：

(7)

4.3實驗結果分析

標準K-means和SKMA算法，利用Apache Mahout項目中基于MapReduce框架的版本。圖1為k增加時PKMeans、SKMA和MRSK的執(zhí)行時間變化圖。圖2為k增加時三種算法的SEE變化圖。

圖1 k和時間的關系

從圖1的結果可以看出，相對于其他方案，MRSK的速度更快。尤其是k大于100時，MRSK的速度遠快于另外兩種算法。在圖2中，MRSK的聚類效果也比另外兩種算法要好，隨著k值增大，SSE越來越接近5·1011，而5·1011正是預估的理論值。圖中，PKMeans的聚類效果一直比另外兩種算法差。k=10時，SKMA和MRSK的SSE值大小相當，k大于10時，MRSK的SSE值逐漸低于SKMA。而且，隨著簇的增加，MRSK一直保持著較低的SSE值。

圖2 k和SSE的關系

實驗結果表明，MRSK在保證聚類效果的前提下，降低了I/O開銷，提高了執(zhí)行速度。

5 結束語

針對K-means的迭代性質(zhì)并不能在MapReduce框架中被模型化，需要反復讀寫磁盤導致極高I/O開銷的問題，提出了基于MapReduce的單遍K-means算法。理論分析和實驗結果均表明，MRSK有效提高了算法執(zhí)行速度，降低了I/O開銷，為處理大數(shù)據(jù)集上的大量聚簇問題提供了一個有益的解決思路和方案。下一步的研究重點是利用包括k-d樹在內(nèi)的臨近搜索方法，進一步降低算法的時間復雜度。

[1] Wang L,Tao J, Ranjan R,et al. G-Hadoop:MapReduce across distributed data centers for data-intensive computing[J].Future Generation Computer Systems,2013,29(3):739-750.

[2] 王 珊,王會舉,覃雄派,等.架構大數(shù)據(jù):挑戰(zhàn)、現(xiàn)狀與展望[J].計算機學報,2011,34(10):1741-1752.

[3] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[C]//Conference on symposium on operating systems design & implementation.[s.l.]:USENIX Association,2004:107-113.

[4] Dean J,Ghemawat S.MapReduce:a flexible data processing tool[J].Communications of the ACM,2010,53(1):72-77.

[5] White T.Hadoop:the definitive guide[M].[s.l.]:[s.n.],2010.

[6] Thangavel S K,Thampi N S,Johnpaul C I.Performance analysis of various recommendation algorithm using apache Hadoop and mahout[J].International Journal of Scientific & Engineering Research,2013,4(12):279-287.

[7] Zhao W,Ma H,He Q.Parallel k-means clustering based on MapReduce[C]//IEEE international conference on cloud computing.[s.l.]:IEEE,2009:674-679.

[8] 謝國富,王文成.單遍數(shù)據(jù)讀取的GPU上的多片元效果繪制[J].計算機學報,2011,34(3):473-481.

[9] Ailon N,Jaiswal R,Monteleoni C.Streaming k-means approximation[C]//Conference on neural information processing systems.Vancouver,British Columbia,Canada:[s.n.],2009:10-18.

[10] 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.

[11] Arthur D,Vassilvitskii S.k-means++:the advantages of careful seeding[C]//Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms.[s.l.]:Society for Industrial and Applied Mathematics,2007:1027-1035.

[12] Hartigan J A,Wong M A.A K-means clustering algorithm[J].Applied Statistics,2013,28(1):100-108.

[13] Bahmani B,Moseley B,Vattani A,et al.Scalable k-means++[J].Proceedings of the VLDB Endowment,2012,5(7):622-633.

[14] 張培偉.基于改進Single-Pass算法的熱點話題發(fā)現(xiàn)系統(tǒng)的設計與實現(xiàn)[D].武漢:華中師范大學,2015.

A Single-passK-means Clustering Algorithm with MapReduce

TANG Hao1,YANG Yu-wang1,XIN Zhi-bin2

(1.School of Computer Science and Technology,Nanjing University of Science and Technology,Nanjing 210094,China；2.Huaihai Industrial Group Co.,Ltd.,Changzhi 046000,China)

The application of fittingK-means into MapReduce framework can greatly improve the processing ofK-means on large datasets.ButK-means achieves an acceptable clustering effect through multiple iterations.Each iteration is executed as an independent map job,in which the whole dataset must be read and wrote to slow disks,resulting in high I/O overhead,and it is not consistent with the design concept of the MapReduce framework.Therefore,a single-passK-means clustering algorithm based on MapReduce,called MRSK,is proposed.It reads the data by single-pass and uses theK-means++ seeding algorithm to get the initial cluster center.On the basis of theoretically analyzing the complexity of the MRSK,a series of test and analysis for MRSK is conducted.The experimental results show that compared with the available MapReduce-based and stream-basedK-means variants,MRSK performs both faster execution times and higher quality of clustering results.

MapReduce framework;data clustering;K-means++;Mahout;single-pass

2016-11-04

：2017-03-09 < class="emphasis_bold">網(wǎng)絡出版時間

時間：2017-07-11

國家自然科學基金資助項目(61640020)；江蘇省科技支撐計劃(BE2012386，BE2011342)；江蘇省農(nóng)業(yè)自主創(chuàng)新項目(CX(13)3054，CX(16)1006)；江蘇省重點研發(fā)計劃(BE2016368-1)；深圳市戰(zhàn)略性新興產(chǎn)業(yè)發(fā)展專項資金項目(JCYJ20130331151710105)

唐 浩(1990-)，男，碩士生，研究方向為云計算和大數(shù)據(jù)處理；楊余旺，教授，研究方向為云計算和大數(shù)據(jù)處理、網(wǎng)絡編碼、傳感器網(wǎng)絡。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1457.086.html

TP301.6

:A

:1673-629X(2017)09-0026-05

10.3969/j.issn.1673-629X.2017.09.006