李 斌，李 蓉，周 蕾

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

0 引言

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

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

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

1 K-means和Canopy聚類算法

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

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

1.2 Canopy聚類算法的基本思路

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

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

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

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

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

2 分布式K-means聚類算法設計

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

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

第一步，將數(shù)據(jù)分到不同的節(jié)點上，每個節(jié)點只對本地數(shù)據(jù)進行計算；

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

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

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

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

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

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

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

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

整體流程如如圖1所示。

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

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

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

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

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

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

Map函數(shù)

Reduce函數(shù)

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

Map函數(shù)

Reduce函數(shù)

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

3 實驗驗證

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

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

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

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

3.2 實驗結(jié)果

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

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

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

表2 效率對比Tab.2 Efficiency comparison

4 總結(jié)

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

此外，數(shù)據(jù)挖掘算法的實現(xiàn)是離不開迭代運算的，迭代運算中文件的頻繁存取為 Hadoop帶來很大的壓力，這時基于內(nèi)存的 spark可以更好的緩解這一問題，但是 spark對于機器內(nèi)存要求較高?？v觀行業(yè)背景，實時計算的需求越來越迫切，支持實時計算的storm和基于內(nèi)存的分布式計算環(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]. 計算機技術(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] 余永紅, 向曉軍, 高陽, 等. 面向云服務的數(shù)據(jù)挖掘引擎的研究[J]. 計算機科學與探索, 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] 王書夢, 吳曉松. 大數(shù)據(jù)環(huán)境下基于MapReduce 的網(wǎng)絡輿情熱點發(fā)現(xiàn)[J]. 軟件, 2015, 36(7): 108-113.

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

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

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

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

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

[14] 鄭金志, 鄭金敏, 汪玉琳. 基于優(yōu)化初始聚類中心的改進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.