李 斌,李 蓉,周 蕾
(國網(wǎng)寧夏電力公司信息通信公司,寧夏 銀川 750001)
隨著互聯(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ù)主觀確定的缺點。
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ù)點分配給距離最近的簇中心群,直至新計算出的簇中心點與上一步生成的簇中心點一致,停止迭代,輸出所屬類別。
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ù)要求。
分布式數(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ù)記錄>,輸出為<類別,局部類中心>:
輸入:
Reduce函數(shù)是匯總所有節(jié)點的結(jié)果,根據(jù)類別id對重新計算新的簇中心:
整體流程如如圖1所示。
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對
Map函數(shù)
Reduce函數(shù)
圖2 改進的分布式K-means算法流程Fig.2 The flow of improved distributed K-means algorithm
實驗是在實驗室搭建的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ù)集。
根據(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ù)按照
表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
本文利用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.