分布式K-means聚類算法研究與實(shí)現(xiàn)

李 斌，李 蓉，周 蕾

（國網(wǎng)寧夏電力公司信息通信公司，寧夏 銀川 750001）

0 引言

隨著互聯(lián)網(wǎng)數(shù)據(jù)量呈指數(shù)增長，傳統(tǒng)的數(shù)據(jù)挖掘算法已經(jīng)不能適應(yīng)海量數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)挖掘算法使用數(shù)據(jù)倉庫模型把所有數(shù)據(jù)匯總到中心節(jié)點(diǎn)，并在匯總數(shù)據(jù)的基礎(chǔ)上運(yùn)行數(shù)據(jù)挖掘算法[1]。這種方式存在很多局限的，比如中心節(jié)點(diǎn)的性能瓶頸、數(shù)據(jù)隱私泄露等問題。為了緩解這些問題，分布式數(shù)據(jù)挖掘成為了熱點(diǎn)研究領(lǐng)域[2]。分布式數(shù)據(jù)挖掘方法是為了解決在合理時(shí)間內(nèi)無法在單機(jī)環(huán)境完成某些復(fù)雜問題而存在的[3]。分布式數(shù)據(jù)挖掘具有單機(jī)數(shù)據(jù)挖掘無法達(dá)到的優(yōu)點(diǎn)：首先，有效地解決了數(shù)據(jù)增多帶來地存儲(chǔ)、計(jì)算方面壓力，其次，降低計(jì)算瓶頸，將復(fù)雜的計(jì)算工作改為局部實(shí)現(xiàn)再匯總的形式。

現(xiàn)有主流的分布式數(shù)據(jù)挖掘技術(shù)的實(shí)現(xiàn)方法大體可以分為以下幾類：基于MPI的并行數(shù)據(jù)挖掘算法研究[4]，是在消息傳遞接口MPI集群基礎(chǔ)上實(shí)現(xiàn)的分布式數(shù)據(jù)挖掘算法，以多線程調(diào)用的形式實(shí)現(xiàn)多機(jī)調(diào)用執(zhí)行，但無法有效地協(xié)調(diào)節(jié)點(diǎn)之間任務(wù)的調(diào)度以及節(jié)點(diǎn)的存儲(chǔ)和任務(wù)分配[5]；基于 Agent主體的非集中式數(shù)據(jù)挖掘技術(shù)，是以本節(jié)點(diǎn)的數(shù)據(jù)為基礎(chǔ)運(yùn)行數(shù)據(jù)讀寫任務(wù)，對(duì)于本地?cái)?shù)據(jù)有一定的安全性保護(hù)，但同時(shí)也引出了關(guān)鍵問題：局部結(jié)果的整合[6]。對(duì)這一問題的研究，專家設(shè)計(jì)并給出多種解決方案。典型的解決方案包括：PADMA(parallel data mining agents)、BODHI( Beseizing knowledge through distributed heterogeneous induction)、JAM(Java agents for meta-learning)等；基于網(wǎng)格的分布式數(shù)據(jù)挖掘方法[7]，提供了可以用來計(jì)算和數(shù)據(jù)管理的基礎(chǔ)設(shè)施，為在分布式環(huán)境下運(yùn)行數(shù)據(jù)挖掘算法提供了必備的硬件條件，然而基于網(wǎng)格的數(shù)據(jù)挖掘方法的資源調(diào)度和作業(yè)分配是離不開人為干預(yù)的；基于云的分布式數(shù)據(jù)挖掘算法，側(cè)重于使用虛擬化技術(shù)為用戶提供個(gè)性化平臺(tái)、服務(wù)、資源等。近年來，基于云計(jì)算的數(shù)據(jù)挖掘算法是當(dāng)今分布式數(shù)據(jù)挖掘最為流行的發(fā)展方向，已經(jīng)投入使用的Hadoop平臺(tái)為分布式數(shù)據(jù)挖掘算法的實(shí)現(xiàn)奠定了堅(jiān)實(shí)基礎(chǔ)[8-9]。

K-means算法是一種常用的數(shù)據(jù)挖掘算法，在數(shù)值聚類[10]、地圖聚類[11]、文本聚類[12]、圖像聚類[13-14]方面都有廣泛的應(yīng)用。但是串行K-means的時(shí)間復(fù)雜度比較高，處理能力存在局限性，此外，K-means算法固有的缺點(diǎn)，即需要事先確定聚類個(gè)數(shù)K，且K的確定容易受主觀因素影響，會(huì)造成局部最優(yōu)，導(dǎo)致聚類質(zhì)量的下降。本文利用分布式計(jì)算環(huán)境 Hadoop2.x中的 MapReduce編程模型對(duì)K-means進(jìn)行分布式研究和實(shí)現(xiàn)，且利用Canopy算法對(duì)K-means進(jìn)行優(yōu)化，Canopy算法無需實(shí)現(xiàn)確定聚類個(gè)數(shù)，而是通過計(jì)算對(duì)象間的相似度進(jìn)行劃分，可以解決K-means聚類個(gè)數(shù)主觀確定的缺點(diǎn)。

1 K-means和Canopy聚類算法

1.1 K-means聚類算法的基本思路

K-Means在隨機(jī)選取K個(gè)簇中心點(diǎn)的基礎(chǔ)上，計(jì)算樣本中其他點(diǎn)與這K個(gè)簇中心點(diǎn)的距離，實(shí)現(xiàn)樣本點(diǎn)的分類，分到同一類的樣本點(diǎn)再更新簇中心點(diǎn)。由此不斷循環(huán)直到K個(gè)簇中心不變。K個(gè)簇中心點(diǎn)是k-Means算法中的輸入?yún)?shù)，新的簇中心會(huì)根據(jù)當(dāng)前分類的簇按照歐拉公式來計(jì)算得到。k-Means算法的目的是讓每個(gè)簇內(nèi)的數(shù)據(jù)點(diǎn)盡量靠近本簇中心，遠(yuǎn)離其他簇中心。在迭代計(jì)算的時(shí)候，k-Means把每個(gè)數(shù)據(jù)點(diǎn)分配給距離最近的簇中心群，直至新計(jì)算出的簇中心點(diǎn)與上一步生成的簇中心點(diǎn)一致，停止迭代，輸出所屬類別。

1.2 Canopy聚類算法的基本思路

Canopy算法是一種快速的聚類算法，但在準(zhǔn)確度方面比較遜色，作為一種“粗”聚類，其流程可以概述為：

①對(duì)于數(shù)據(jù)集S，有閾值t1和t2，且t1>t2，②S中任選一點(diǎn)x，作為Canopy的候選點(diǎn)，從數(shù)據(jù)集S中刪除點(diǎn)x，

③計(jì)算數(shù)據(jù)集中所有點(diǎn)到x的距離，

④距離小于t1的點(diǎn)歸為x，距離小于t2的點(diǎn)歸于x類并從數(shù)據(jù)集S中刪除，距離大于t1的點(diǎn)，新建Canopy，從數(shù)據(jù)集S刪除，

⑤重復(fù)第二步到第五步直至數(shù)據(jù)集S為空或者滿足最大迭代次數(shù)要求。

2 分布式K-means聚類算法設(shè)計(jì)

2.1 分布式K-means聚類算法設(shè)計(jì)與實(shí)現(xiàn)

分布式數(shù)據(jù)挖掘算法k-Means聚類算法的實(shí)現(xiàn)思想為：

第一步，將數(shù)據(jù)分到不同的節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)只對(duì)本地?cái)?shù)據(jù)進(jìn)行計(jì)算；

第二步，根據(jù)全局變量計(jì)算本地?cái)?shù)據(jù)所屬的簇；

第三步，根據(jù)各個(gè)數(shù)據(jù)點(diǎn)所屬的簇，計(jì)算出該簇的中心，若與全局簇中心點(diǎn)一致，則輸出分類結(jié)果；若不一致則用新計(jì)算出的簇中心來更新全局簇中心點(diǎn)，則重復(fù)第二步，直至新計(jì)算出的簇中心點(diǎn)與全局簇中心點(diǎn)一致。

可見，在分布式K-means聚類算法中，每次迭代的算法執(zhí)行相同的操作，因此，可通過MapReduce編程模型加以實(shí)現(xiàn)，分別執(zhí)行相同的 Map操作和Reduce操作。分為3部分函數(shù)：Map函數(shù)、Combine函數(shù)和Reduce函數(shù)：

Map函數(shù)對(duì)數(shù)據(jù)集分塊，并計(jì)算各個(gè)數(shù)據(jù)點(diǎn)到K個(gè)中心點(diǎn)的距離，重新標(biāo)記每個(gè)點(diǎn)的所屬類別。輸入為數(shù)據(jù)記錄文件，輸出為每個(gè)數(shù)據(jù)點(diǎn)的所屬類別：

輸入：聚類文件split輸出：<所屬類別，數(shù)據(jù)點(diǎn)>獲取簇中心信息；計(jì)算本地文件中每一個(gè)數(shù)據(jù)點(diǎn)到簇中心的距離；得到data所屬的簇id:。

Combine函數(shù)根據(jù)Map函數(shù)的結(jié)果完成對(duì)本地文件中的簇中心的重新計(jì)算。輸入為<類別，數(shù)據(jù)記錄>，輸出為<類別，局部類中心>：

輸入：輸出：根據(jù)cluster_id計(jì)算屬于該簇的數(shù)據(jù)點(diǎn)個(gè)數(shù)求得 value的平均值，記錄為

Reduce函數(shù)是匯總所有節(jié)點(diǎn)的結(jié)果，根據(jù)類別id對(duì)重新計(jì)算新的簇中心：

整體流程如如圖1所示。

2.2 改進(jìn)的分布式K-means聚類算法設(shè)計(jì)與實(shí)現(xiàn)

K-Means算法存在的不足主要有：聚類個(gè)數(shù)K根據(jù)經(jīng)驗(yàn)判斷，沒有理論依據(jù)，對(duì)于初學(xué)者難以準(zhǔn)確判斷；初始簇中心選取是隨機(jī)的，會(huì)造成局部最優(yōu)解；離群點(diǎn)對(duì)聚類結(jié)果的干擾，造成聚類質(zhì)量的下降。基于這些不足的存在，加入Canopy算法進(jìn)行優(yōu)化，Canopy算法的輸出為 k-cluster，可以為k-Means算法確定K個(gè)聚類及其類中心點(diǎn)。Canopy算法執(zhí)行過程中，通過對(duì) Canopy的建立，可以刪除包含數(shù)據(jù)點(diǎn)數(shù)目較少的Canopy，這些點(diǎn)往往是離群點(diǎn)。

改進(jìn)的分布式 k-Means聚類算法是將 Canopy算法作為k-Means算法輸入，為k-Means算法確定k值、初始聚類點(diǎn)、離散點(diǎn)，來提高 k-Means聚類算法的質(zhì)量。其算法流程是：對(duì)于數(shù)據(jù)集，首先進(jìn)行數(shù)據(jù)集劃分成若干子集，然后在每個(gè)子集內(nèi)計(jì)算

中心點(diǎn)并按照距離重新進(jìn)行劃分，進(jìn)而確定簇?cái)?shù)以及初始簇心；之后利用K-means算法進(jìn)行迭代計(jì)算，收斂出聚類結(jié)果。如圖2所示。

圖1 分布式k-Means算法流程圖Fig.1 The flow of distributed K-means algorithm

利用 MapReduce模型，Canopy中心點(diǎn)生成的Map函數(shù)和Reduce函數(shù)設(shè)計(jì)如下：

Map函數(shù)

Reduce函數(shù)

利用MapReduce模型，K-means的Map函數(shù)和Reduce函數(shù)設(shè)計(jì)如下：將得到的key-value對(duì)按照相同key進(jìn)行匯總，計(jì)算相同key下value的平均值，若與上一步簇中心一致則結(jié)束聚類，否則更新全局簇中心文件，繼續(xù)循環(huán)執(zhí)行。

Map函數(shù)

Reduce函數(shù)

圖2 改進(jìn)的分布式K-means算法流程Fig.2 The flow of improved distributed K-means algorithm

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

實(shí)驗(yàn)是在實(shí)驗(yàn)室搭建的Hadoop平臺(tái)上運(yùn)行的。平臺(tái)由四臺(tái)虛擬機(jī)構(gòu)成的虛擬化平臺(tái)，使用XenServer的服務(wù)器虛擬化平臺(tái)來管理計(jì)算機(jī)。每臺(tái)機(jī)器的部署環(huán)境如表1所示。

表1 系統(tǒng)部署環(huán)境Tab.1 System deployment environment

實(shí)驗(yàn)采用的數(shù)據(jù)是阿里巴巴天池比賽中新浪微博互動(dòng)預(yù)測大賽的數(shù)據(jù)[15]，該數(shù)據(jù)包括 2014年 7月至2014年12月期間的微博用戶轉(zhuǎn)發(fā)數(shù)、點(diǎn)贊數(shù)、評(píng)論數(shù)以及對(duì)應(yīng)的微博博文內(nèi)容。實(shí)驗(yàn)中構(gòu)造了40 M、80 M、160 M、320 M、400 M等5個(gè)不同大小的數(shù)據(jù)集。

3.2 實(shí)驗(yàn)結(jié)果

根據(jù)本文搭建的Hadoop平臺(tái)，包括一個(gè)master,三個(gè)slave。首先，確定k-Means聚類算法的K個(gè)簇初始點(diǎn)，將樣本數(shù)據(jù)分配給各slave節(jié)點(diǎn)，將數(shù)據(jù)分塊，在每一個(gè)節(jié)點(diǎn)計(jì)算局部Canopy，各局部Canopy經(jīng) reduce函數(shù)匯總計(jì)算得到全局?jǐn)?shù)據(jù) Canopy。將Canopy文件在master上為各slave端發(fā)送，將其作為整體簇中心初始點(diǎn)，同時(shí)這些初始簇中心創(chuàng)立全局文件并廣播給所有 slave節(jié)點(diǎn)，全局文件包括cluster_id,cluster_center，data_number；slave根據(jù)接收到的全局文件，判斷本機(jī)數(shù)據(jù)所屬的簇類別即cluster_id，每一個(gè) slave將其數(shù)據(jù)按照的形式保存，然后將在同一個(gè) slave上執(zhí)行 combiner操作，輸出的形式；Reduce階段將經(jīng)過combiner操作的結(jié)果中系統(tǒng)的 key即相同類別數(shù)據(jù)進(jìn)行處理，得到 k個(gè)的結(jié)果，將這 k個(gè)作為新的整體簇中心初始點(diǎn)，繼續(xù)重復(fù)以上步驟，直至Reduce的 k個(gè)結(jié)果與整體簇中心初始點(diǎn)一致，即全局簇中心穩(wěn)定時(shí)結(jié)束迭代。

表2為改進(jìn)的分布式k-Means聚類和傳統(tǒng)k-Means聚類在40 M、80 M、160 M、320 M、400 M等5個(gè)不同大小的數(shù)據(jù)集的效率對(duì)比。

從表2可以看出，分布式k-Means聚類算法由于其算法的迭代運(yùn)算很多，在新計(jì)算出來的簇中心與原來全局變量簇中心不一致的情況下，需要重復(fù)迭代運(yùn)算。因此，在執(zhí)行小文件的分布式 k-Means聚類算法時(shí)無法體現(xiàn)其性能上的優(yōu)越性。而一旦數(shù)據(jù)集規(guī)模加大，在單機(jī)執(zhí)行大文件k-Means算法時(shí)，很容易造成電腦崩潰，而分布式k-Means算法卻可以通過多臺(tái)主機(jī)同時(shí)運(yùn)行來進(jìn)行聚類運(yùn)算，體現(xiàn)出分布式的性能優(yōu)勢。

表2 效率對(duì)比Tab.2 Efficiency comparison

4 總結(jié)

本文利用MapReduce模型研究與實(shí)現(xiàn)了分布式K-means聚類算法。分別在單機(jī)環(huán)境和分布式環(huán)境進(jìn)行了效率對(duì)比，可以得出結(jié)論：分布式數(shù)據(jù)挖掘算法在小數(shù)據(jù)量時(shí)無法顯示優(yōu)越性，而對(duì)大文件進(jìn)行處理時(shí)，其優(yōu)越性明顯。具體原因是：當(dāng)有小文件需要處理的時(shí)候，每次map只會(huì)處理少量的數(shù)據(jù)，但是會(huì)存在大量的Map任務(wù)，對(duì)Hadoop平臺(tái)的運(yùn)行是不利的。但在應(yīng)對(duì)大數(shù)據(jù)量時(shí)，分布式K-means算法就會(huì)體現(xiàn)出巨大的優(yōu)勢。

此外，數(shù)據(jù)挖掘算法的實(shí)現(xiàn)是離不開迭代運(yùn)算的，迭代運(yùn)算中文件的頻繁存取為 Hadoop帶來很大的壓力，這時(shí)基于內(nèi)存的 spark可以更好的緩解這一問題，但是 spark對(duì)于機(jī)器內(nèi)存要求較高?？v觀行業(yè)背景，實(shí)時(shí)計(jì)算的需求越來越迫切，支持實(shí)時(shí)計(jì)算的storm和基于內(nèi)存的分布式計(jì)算環(huán)境spark將成為今后研究的重要方向。

[1] M M Sufyan Beg& C P Ravikumar. Application of Parallel and Distributed Data Mining in e-Commerce[J]. Iete Technical Review, 2015, 17(4): 189-195.

[2] Kargupta H, Park B.Dary H, et al Collective data mining.a new perspective toward distributed data analysis[M]. Advances in Distributed and Parallel Knowledge Discovery.[S.1.]: AAAI/MIT Press.1999: 133-184.

[3] Ninama H. DISTRIBUTED DATA MINING USING MESSAGE PASSING INTERFACE [J]. Review of Research, 2013.

[4] 呂婉琪, 鐘誠, 唐印滸, 等. Hadoop分布式架構(gòu)下大數(shù)據(jù)集的并行挖掘[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2014(01): 22-25.

[5] Stankovski V, Swain M, Kravtsov V, et al. Grid-enabling data mining applications with DataMiningGrid: An architectural perspective[J]. Future Generation Computer Systems, 2008,24(4): 259–279.

[6] 余永紅, 向曉軍, 高陽, 等. 面向云服務(wù)的數(shù)據(jù)挖掘引擎的研究[J]. 計(jì)算機(jī)科學(xué)與探索, 2012, 06(1): 46-57.

[7] Mario C, Hiram G P, Alessia S. Data mining and life sciences applications on the grid[J]. Wiley Interdisciplinary Reviews Data Mining & Knowledge Discovery, 2013, 3(3):216-238.

[8] 王書夢(mèng), 吳曉松. 大數(shù)據(jù)環(huán)境下基于MapReduce 的網(wǎng)絡(luò)輿情熱點(diǎn)發(fā)現(xiàn)[J]. 軟件, 2015, 36(7): 108-113.

[9] 李冠辰. 一個(gè)基于hadoop 的并行社交網(wǎng)絡(luò)挖掘系統(tǒng)[J].軟件, 2013, 34(12): 127-131.

[10] 杜淑穎. 基于大型數(shù)據(jù)集的聚類算法研究[J]. 軟件, 2016,37(01): 132-135.

[11] 楊婷婷, 王雪梅. 基于百度地圖的改進(jìn)的K-means 算法研究[J]. 軟件, 2016, 37(01): 76-80.

[12] 陳磊磊. 不同距離測度的K-Means 文本聚類研究[J]. 軟件,2015, 36(1): 56-61.

[13] 陳慧, 龍飛, 段智云. 一種基于小波零樹編碼和K-mean聚類的圖像壓縮的實(shí)現(xiàn)[J]. 軟件, 2016, 37(02): 33-34.

[14] 鄭金志, 鄭金敏, 汪玉琳. 基于優(yōu)化初始聚類中心的改進(jìn)WFCM 圖像分割算法[J]. 軟件, 2015, 36(4): 136-142.

[15] https://tianchi.aliyun.com/competition/raceOssFileDownload.do?spm=5176.100068.555.1.tPkxq4&file=weibo_predict_dat a(new).zip&raceId=5.http://www.cnblogs.com/ywl925/archi ve/2013/08/16/3262209.html.