張友海，李鋒剛

(1.安徽職業(yè)技術(shù)學(xué)院，安徽 合肥 230011；2.合肥工業(yè)大學(xué)，安徽 合肥 230009)

基于MapReduce的Canopy-Kmeans算法的并行化

張友海1，李鋒剛2

(1.安徽職業(yè)技術(shù)學(xué)院，安徽 合肥 230011；2.合肥工業(yè)大學(xué)，安徽 合肥 230009)

數(shù)據(jù)挖掘的聚類算法Canopy-Kmeans是分析數(shù)據(jù)內(nèi)在價值的常用工具之一，傳統(tǒng)的基于集中控制的方式算法執(zhí)行效率，在今天大數(shù)據(jù)環(huán)境下，有待改進(jìn)。文章數(shù)據(jù)源為某省運(yùn)營商在2014年7月經(jīng)過脫敏后的話單信令數(shù)據(jù)，通過傳統(tǒng)的集中控制方式和基于MapReduce的方式。通過實(shí)驗(yàn)，我們可以看出使用MapReduce方式具有良好的可行性，而且執(zhí)行效率也得到明顯改善〔1〕。

聚類算法；Canopy-kmeans ；MapReduce

Hadoop是一個開源的分布式大數(shù)據(jù)解決方案，它實(shí)現(xiàn)對海量數(shù)據(jù)高效，可伸縮的存儲和分析功能。Hadoop架構(gòu)的核心包含三個部分，分布式文件存儲系統(tǒng)HDFS，DFS是一個設(shè)計用于在低成本硬件上運(yùn)行的高度容錯的分布式文件系統(tǒng)，適合存儲大文件。YARN是有Hadoop提供的一個資源調(diào)度系統(tǒng)，用于為上層應(yīng)用提供統(tǒng)一的資源調(diào)度和管理功能，提高資源利用率。MapReduce，一個并行計算編程框架，可以用于編寫處理海量數(shù)據(jù)的應(yīng)用。

1 Canopy-Kmeans算法

Kmeans算法簡單且易于實(shí)現(xiàn)，是運(yùn)用非常廣泛的聚類算法。但存在很多缺點(diǎn)，如需事先確定初始聚類數(shù)目，另外聚類中心的選擇具有較大差異，易受主觀因素影響而使得結(jié)果陷入局部最優(yōu)。而Canopy-Kmeans算法是一種Kmeans的優(yōu)化算法，其思想是對特定數(shù)據(jù)集，設(shè)置一個Canopy初始中心點(diǎn)與范圍半徑，將數(shù)據(jù)集快速地劃分成若干可重疊的Canopy，使得所有記錄均分布在Canopy所覆蓋范圍內(nèi)，并對發(fā)布同一范圍內(nèi)的記錄，重新計算得出新中心點(diǎn)指標(biāo)并根據(jù)記錄坐標(biāo)與新中心點(diǎn)之間的距離值重新劃分記錄所屬區(qū)域。循環(huán)執(zhí)行上述過程，直到k個中心點(diǎn)的不再發(fā)生變化為止。傳統(tǒng)的Kmeans算法計算復(fù)雜性是O(dkt)，其中d為記錄數(shù)量，t為算法迭代次數(shù)，k為類的數(shù)量。在運(yùn)用Canopy方法對Kmeans算法進(jìn)行優(yōu)化的條件下，由于在劃分Canopies時是可重復(fù)劃分的，在忽略某些記錄屬于多個Canopy情況，聚類需比較dkt/c次，其中c是Canopies的數(shù)量?？梢奀anopy方法可以顯著提高算法效率。

2 Canopy-Kmeans的MapReduce并行化〔2〕實(shí)現(xiàn)

Canopy-Kmeans的MapReduce并行化實(shí)現(xiàn)〔3〕思路如下：首先將所有數(shù)據(jù)集合按特定特征劃分為每類的成員的特征相同的K個類。初始數(shù)據(jù)會根據(jù)數(shù)據(jù)存儲的節(jié)點(diǎn)位置及數(shù)據(jù)分塊個數(shù)將其劃分為劃分成N個數(shù)據(jù)集，每個數(shù)據(jù)集可由一個Mapper獨(dú)立處理完成，并且Mapper可以重復(fù)利用，多個數(shù)據(jù)集可以在同一個Mapper上進(jìn)行處理。Canopy-Kmeans的聚類過程分兩個階段執(zhí)行：第一步：近似和快速地將數(shù)據(jù)分成若干的Canopy，然后對每個Canopy內(nèi)的記錄再進(jìn)行聚類。在這兩個階段過程中，使用不同的相似距離的度量方法，最終創(chuàng)建好可重疊的Canopy。第二步：對于Canopy 內(nèi)的記錄，這里使用Kmeans 算法進(jìn)行聚類。由于這里只要對Canopy內(nèi)的點(diǎn)完成精確地聚類，從而避免了像傳統(tǒng)kmeans算法那樣要對數(shù)據(jù)集合中所有的記錄進(jìn)行迭代精確計算，另外由于算法允許有重疊Canopy，這起到了消除孤立點(diǎn)作用，提高了算法的容錯性。在MapReduce編程模型下，Canopy-Kmeans算法的并行化實(shí)現(xiàn)可分解為若干子Job，流程如圖1所示，每個方框均表示一個完整的MapReduce任務(wù)。

其實(shí)現(xiàn)步驟說明如下：

1)Canopy中心點(diǎn)生成過程：針對于大數(shù)據(jù)量，生成Canopy中心點(diǎn)的過程會很耗時。這里同樣利用MapRduce進(jìn)行優(yōu)化這個過程。首先由單節(jié)點(diǎn)程序?qū)π×康挠涗浬蒀anopy中心點(diǎn)，再由分布式的Map程序過濾其他記錄，去除掉落在已有Canopy范圍內(nèi)的記錄。對于剩下的記錄迭代執(zhí)行這個過程，直到所有記錄都被處理。該步驟將產(chǎn)生所有Canopy中心點(diǎn)的集合。

圖1 Canopy-Kmeans 算法流程

2)輸入向量標(biāo)注：這個步驟的目的是標(biāo)注Canopy的記錄文本，這個步驟只需要Mapper過程，不需要reduce過程，Mapper的功能是將待聚類的記錄與所有Canopy中心點(diǎn)比較，輸出記錄及其對應(yīng)的Canopy中心點(diǎn)信息。

3)Kmeans算法MapReduce并行化思路如下：

(1)Map每讀取一條數(shù)據(jù)就與中心做對比，求出該條記錄對應(yīng)的中心，然后以中心的id為Key，該條數(shù)據(jù)為value將數(shù)據(jù)輸出。

(2)利用Reduce的歸并功能將相同的Key歸并到一起，集中與該Key對應(yīng)的數(shù)據(jù)，再求出這些數(shù)據(jù)的平均值，輸出平均值。

(3)對比Reduce求出的平均值與原來的中心，如果不相同，這將清空原中心的數(shù)據(jù)文件，將Reduce的結(jié)果寫到中心文件中。(中心的值存在一個HDFS的文件中)刪掉Reduce的輸出目錄以便下次輸出。繼續(xù)運(yùn)行任務(wù)。

(4)對比Reduce求出的平均值與原來的中心，如果相同。則刪掉Reduce的輸出目錄，運(yùn)行一個沒有Reduce的任務(wù)將中心ID與值對應(yīng)輸出。

3 實(shí)驗(yàn)分析與總結(jié)

本文采用的實(shí)驗(yàn)數(shù)據(jù)是某省運(yùn)營商在2014年7月經(jīng)過脫敏后的話單信令數(shù)據(jù)，數(shù)據(jù)包含內(nèi)容有：源標(biāo)識，源運(yùn)營商標(biāo)識，目的標(biāo)識，目的運(yùn)營標(biāo)識，源區(qū)域標(biāo)識，目的區(qū)域標(biāo)識，時間戳，持續(xù)時間等34個字段，涉及用戶量4215.9萬。

接下來將對Canopy-Kmeans的MapReduce的聚類效果、并行化加速比，分別設(shè)計實(shí)驗(yàn)進(jìn)行驗(yàn)證。

1)聚類效果分析

在這里我們引入最小誤差平方即：

表1 聚類效果實(shí)驗(yàn)結(jié)果數(shù)據(jù)

由表1可知，并行化實(shí)現(xiàn)的聚類算法和單機(jī)實(shí)現(xiàn)的聚類算法在聚類效果方面差異不大。

2)實(shí)驗(yàn)二：并行加速比分析

加速比描述在集群中實(shí)現(xiàn)并行化通過減少運(yùn)行時間而獲得的性能提升，其定義為性能相同的節(jié)點(diǎn)并行運(yùn)算所耗費(fèi)的時間除以單節(jié)點(diǎn)進(jìn)行運(yùn)算所耗費(fèi)的時間。本實(shí)驗(yàn)將從3個節(jié)點(diǎn)增加節(jié)點(diǎn)8個節(jié)點(diǎn)的分別計算加速比差異如圖2所示。

圖 2 Canopy-KMeans算法加速比實(shí)驗(yàn)結(jié)果

從圖2可以看出隨著節(jié)點(diǎn)的增加性能均有所提升，證明基于MapReduce實(shí)現(xiàn)的算法具有提高執(zhí)行效率的作用。

可以看出，利用MapReduce并行計算框架來實(shí)現(xiàn)聚類算法Canopy-Kmeans，具有良好的可行性，在集群環(huán)境下，隨著業(yè)務(wù)節(jié)點(diǎn)的增加，執(zhí)行性能將有較大提高〔4〕。

〔1〕趙慶.基于Hadoop 平臺下的 Canopy-Kmeans 高效算法〔J〕.電子科技，2014.27(2):29-31.

〔2〕毛嘉莉.聚類K-means算法及并行化研究〔D〕.重慶：重慶大學(xué)，2003.

〔3〕霍可棟.基于Hadoop平臺下的Canopy-Kmeans算法實(shí)現(xiàn)〔J〕.科技展望，2015， (33):12.

〔4〕張石磊，武裝.一種基于Hadoop云計算平臺的聚類算法優(yōu)化的研究〔J〕.計算機(jī)科學(xué)2012.39.

Parallelized Canopy-kmeans algorithm based on MapReduce

ZHANG You-hai1， LI Feng-gang2

(1.AnhuiVocationalandtechnicalCollegeHefei23001; 2.HefeiUniversityoftechnology,Anhui,hefei230009,China)

The Canopy-kmeans clustering algorithm for data mining is one of the common tools which we usually used to analyze the intrinsic value of data. Under current big data environment, the traditional algorithm based on centralized control need to be improved. In this paper, the data source is gathered July 2014 from the desensitized signal data, and billed by traditional centralized control and the method based on MapReduce. Through the experiment we know it has good feasibility to use the MapReduce way, and the executive efficiency has been improved.

Clustering algorithm; Canopy-kmeans; MapReduce

10.3969/j.issn.1008-3723.2017.01.002

(j)cnki 1008-3723 2017.01.002

2016-11-26

張友海(1980-)，男，皖壽縣人，安徽職業(yè)技術(shù)學(xué)院講師，合肥工業(yè)大學(xué)在職工程碩士.研究方向：計算機(jī)應(yīng)用技術(shù).

TP311.13

A