ABC_Kmeans聚類算法的MapReduce并行化研究

袁小艷

(四川文理學院 計算機學院，四川 達州　635000)

?

ABC_Kmeans聚類算法的MapReduce并行化研究

袁小艷

(四川文理學院 計算機學院，四川 達州635000)

隨著數(shù)據(jù)的海量增長，數(shù)據(jù)聚類算法的研究面臨著海量數(shù)據(jù)挖掘和處理的挑戰(zhàn)；針對K-means聚類算法對初始聚類中心的依賴性太強、全局搜索能力也差等缺點，將一種改進的人工蜂群算法與K-means算法相結合，提出了ABC_Kmeans聚類算法，以提高聚類的性能；為了提高聚類算法處理海量數(shù)據(jù)的能力，采用MapReduce模型對ABC_Kmeans進行并行化處理，分別設計了Map、Combine和Reduce函數(shù)；通過在多個海量數(shù)據(jù)集上進行實驗，表明ABC_Kmeans算法的并行化設計具有良好的加速比和擴展性，適用于當今海量數(shù)據(jù)的挖掘和處理。

K-means；聚類；人工蜂群；MapReduce

0　引言

聚類分析是當今數(shù)據(jù)挖掘研究的一個重要領域，其目的是把數(shù)據(jù)集按照規(guī)則分成若干個類別，使得同類別的數(shù)據(jù)盡量高內(nèi)聚，不同類別的數(shù)據(jù)盡量低耦合，它是一種無監(jiān)督學習技術[1]。

K_means是常用的一種數(shù)據(jù)聚類算法，具有高效而簡單的特性，但其K值要靠經(jīng)驗確定，結果也容易受初始中心點影響，易陷入局部最優(yōu)解[2]，全局搜索能力較差，魯棒性也低。群體智能優(yōu)化算法是一種把所有個體信息進行交互，從而得到最優(yōu)結果的算法，其全局搜索能力較強，效率也較高，因此很多人都將其融入到K_means算法中進行研究，效果都較理想。

人工蜂群(ABC)算法是2005年根據(jù)蜂群覓食的行為提出的一種群體智能算法，其結構簡單、收斂速度快、容易實現(xiàn)，更適合于計算機編程[3]。本文將一種改進的人工蜂群算法融入到K_means中進行迭代，降低了對初始聚類中心點的依賴，提高了全局尋優(yōu)能力，但在當今海量數(shù)據(jù)的情況下，效率還是堪憂，因此將本文提出的ABC_Kmeans算法采用Hadoop平臺的MapReduce模型進行并行化實現(xiàn)，因為MapReduce模型本身具有并行化結構，編程人員不需要考慮并行化的細節(jié)知識，實現(xiàn)起來也較容易，能夠減少節(jié)點間的通信時間，這樣不僅僅是提高時間效率，同時還可以防止早熟現(xiàn)象。

1　改進的ABC與K_means聚類算法的融合

在基本ABC算法中，蜜蜂有3種類型，即采蜜蜂、觀望蜂和偵察蜂，采蜜蜂與蜜源相對應，負責對相應的蜜源采蜜，觀望蜂通過采蜜蜂的共享蜜源信息選擇最優(yōu)蜜源，若蜜源被采蜜蜂和觀望蜂放棄，則將該蜜源對應的采蜜蜂轉(zhuǎn)化為偵察蜂，進而搜索新的蜜源。本文將改進的ABC算法與K_means迭代相結合，每次迭代都利用改進的ABC算法來優(yōu)化聚類中心點，再利用K_means迭代更新每個聚類中心點，兩種算法交替執(zhí)行，直到聚類達到最優(yōu)為止。下面介紹兩種算法融合后的聚類過程。

(1)設置參數(shù)，并輸入樣本數(shù)據(jù)集。采蜜蜂與觀望蜂的個數(shù)，均為SN，聚類數(shù)為K，最大迭代次數(shù)為LIN，控制參數(shù)為limit。

(2)聚類中心的初始化，本文的聚類中心就是蜜源。在基本ABC算法中，蜜源的初始化隨機性太大，不能保證初始蜜源的均勻分布。本文采用混沌算子和反向?qū)W習算子對聚類中心進行初始化，從而保證初始聚類中心的多樣性，以提高全局搜索的能力。

1)首先生成具有SN個初始解的搜索空間。搜索空間是一個二維矩陣DF=K*d，行數(shù)為K，即聚類個數(shù)，列數(shù)為d，即樣本數(shù)據(jù)集的維數(shù)。搜索空間的值計算如下：

df[1,j]=rand(0,1)

df[s+1,j]=n×df[s,j]×(1-df[s,j])

其中j=1,2,3,……,d，s=1,2,3,……,K-1,n是一個調(diào)節(jié)因子。

2)計算每個初始解的混沌算子和反向?qū)W習算子，計算如下：

nc[i,j]=lg[j]+df[s,j]×(hg[j]-lg[j])

rt[i,j]=lg[j]+hg[j]-nc[i,j])

其中i=1,2,3,……,K，hg[j]、lg[j]是搜索空間第j維的上、下限，nc[i,j]為混沌算子，rt[i,j]為反向?qū)W習算子，混沌算子組成混沌集合NC，反向?qū)W習算子組成反向集合RT。

3)最終的初始聚類中心就是NC和RT兩個集合中適應度最高的SN個最優(yōu)解。本文各聚類中心的適應度采用歐式距離進行計算。

(3)采蜜蜂進行鄰域搜索，采用貪婪機制選擇適應度高的新聚類中心?；続BC中，鄰域搜索范圍的隨機性太大，導致全局搜索能力較好，但局部搜索能力欠缺。本文受DE/best/1的啟發(fā)，鄰域搜索方程改為由最優(yōu)解引導的式子，具體如下：

pi，j=dfbest,j+random(-1,1)×(dfbest,j-dfi，j)

(1)

其中best是適應度最優(yōu)的采蜜蜂的ID。

(4)采蜜蜂完成鄰域搜索后，觀望蜂根據(jù)輪盤賭機制選擇跟隨的聚類中心，其選擇概率為：

其中：dfit(i)是第i個解的適應度。

觀望蜂選擇聚類中心后，繼續(xù)在聚類中心的鄰域采用公式(1)進行搜索，查找適應度更高的聚類中心，以替換舊的聚類中心。

(5)若聚類中心經(jīng)過連續(xù)limit次迭代后，沒有被新的適應度高的新聚類中心替代，說明其陷入了局部最優(yōu)，應該舍棄，該聚類中心對應的采蜜蜂也應該轉(zhuǎn)換為偵察蜂，讓其搜索新的聚類中心?；続BC中，新蜜源的隨機性太大，很容易被淘汰。受粒子群算法的啟示，本文采用一種線性時變檢索空間的策略選擇新聚類中心，即隨著迭代次數(shù)的增加而線性減小偵察蜂的檢索空間，這樣利于擴大探尋邊界[3]，更利于迭代后期快速找到最優(yōu)解，公式如下：

(6)對各聚類中心進行一次K_means迭代，重新計算每個類別的聚類中心，并采用貪婪機制更新蜂群。

(7)將找到的最優(yōu)聚類中心記錄下來，若迭代次數(shù)小于LIN，則轉(zhuǎn)到(3)執(zhí)行下一次迭代；否則將此結果作為最優(yōu)聚類類別進行輸出。

2　MapReduce分布式模型

MapReduce模型是一種并行計算模型，主要用于海量數(shù)據(jù)的并行化處理。該模型能對文件自動分塊，能自動處理節(jié)點間的傳輸、節(jié)點失效[4]和負載均衡等優(yōu)點，并有較好的擴展性和容錯性[4]。MapReduce模型輸入的是一組鍵值對，輸出的是另一組鍵值對，整個過程分成Map(映射)和Reduce(規(guī)約)。

Map映射函數(shù)首先利用Partion過程將輸入的鍵值對(key-value)分割成多個鍵值對，然后對這多個鍵值對進行處理，將處理的結果輸出。Reduce規(guī)約函數(shù)以Map函數(shù)的輸出作為輸入，并處理這些數(shù)據(jù)，輸出一個較小的鍵值對集合。數(shù)據(jù)由Map函數(shù)到Reduce函數(shù)時，中間還要經(jīng)過復制、排序、合并等操作，統(tǒng)稱為Shuffle過程。合并是將具有相同鍵(key)的中間結果歸并在一起，提供給Reduce處理。MapReduce模型的整個處理過程如圖1所示。

圖1　MapReduce模型處理流程

3　ABC_Kmeans聚類算法的MapReduce并行化設計

ABC_Kmeans聚類算法的并行化采用MapReduce并行模型設計，輸入的數(shù)據(jù)是以行的形式存儲，讓數(shù)據(jù)按行分片。ABC_Kmeans的每一次迭代都對應一次MapReduce過程，完成聚類中心適應度和觀望蜂選擇概率的計算，以得到新的聚類中心，具體設計如圖2所示。

圖2　ABC_Kmeans的MapReduce并行化設計

3.1Map函數(shù)的設計

Map函數(shù)的目標是計算每個蜜源的適應度，由此得到觀望蜂的選擇概率，并標記出觀望蜂屬于的新類別，其輸入是樣本數(shù)據(jù)或者上一次迭代的聚類中心，輸入數(shù)據(jù)的形式為(行偏移量，記錄行)[5]這樣的(key,value)鍵值對，其輸出是(key’,value’)，key’是選擇的聚類中心的索引號，value’是當前樣本點的坐標，其函數(shù)的偽代碼如下：

void mapper(key,value)

{

從value中解析出樣本數(shù)據(jù)，記為foods

For iter=0 to k-1 do{

計算每個蜜源的適應度；

計算每個觀望蜂的選擇概率；

觀望蜂選擇聚類中心，并查找更優(yōu)聚類中心；

偵察蜂查找更優(yōu)聚類中心；

if(foods[maxoptidx].opttimes>optmaxtime)

{

Sfoodinit(maxoptidx);

}

}

key’=maxoptidx;

value’=value;

Emit(key’,value’)

}

為了降低算法傳輸過程中的數(shù)據(jù)量和通信代價，ABC_Kmeans算法在Map操作后設計了一個Combine的函數(shù)，把每個Map函數(shù)的最終結果進行本地合并。

3.2Combine函數(shù)的設計

Combine函數(shù)的輸入(key’,value’)中，key’是聚類中心的下標，value’是分配給key’類別的樣本數(shù)據(jù)的坐標值組成的字符串鏈表[6]；輸出的(key,v)中，key是聚類中心的下標，v是包含了樣本總數(shù)和key對應的各坐標值組成的字符串，其偽代碼如下：

void Combiner(key’,value’)

{

Count=0;

While(value’.hasNext){

Point curret=value’.next();

Count+=current.getNum();

for(i=0;i

total[i]+=current.point[i];

}

}

key=key’;

將前面得到的count和total數(shù)組各個分量的信息組成一個字符串，為v;

Emit(key,v);

}

3.3Reduce函數(shù)的設計

Reduce函數(shù)輸入的(key,v)中，key是聚類類別的下標，v是從所有Combine函數(shù)傳過來的結果，其作用是將key對應的樣本點坐標值相加，再除以樣本總數(shù)，得到新的聚類中心坐標。函數(shù)偽代碼如下：

void Reducer(key,v)

{

While(v.hasNext){

Point current=v.next();

total+=current.getValue();

count=current.getCounter();

New=total/count;

}

}

根據(jù)Reduce的結果，得到新的聚類中心坐標，判斷迭代次數(shù)是否小于LIN，若是的話就進入下一次迭代，否則算法收斂。

4　實驗結果與分析

4.1實驗環(huán)境

本文中的實驗是在我們的實驗室搭建的云平臺上運行的。平臺由12臺機器組成，其中一臺是主控節(jié)點master，一臺是JobTracker服務節(jié)點，剩余的10臺是slaves，配置DataNode數(shù)據(jù)節(jié)點和TaskTracker服務節(jié)點。每臺機器的配置為：CPU是2核，內(nèi)存是8 GB，硬盤是2TB，網(wǎng)卡為板載千兆以太網(wǎng)卡，操作系統(tǒng)是紅帽Linux AS 6.0，Hadoop平臺是0.21.0版本，JDK是1.6.0.29版本。

4.2單機處理實驗結果分析

本實驗是將K-means和ABC_Kmeans聚類算法在相同的數(shù)據(jù)條件下，完成聚類的各自需要的迭代次數(shù)。處理的數(shù)據(jù)是分為10類且具有30 000個數(shù)據(jù)集的二維數(shù)據(jù)，兩者數(shù)據(jù)處理的收斂速度如表1所示。

表1　收斂速度的比較

從表1中可以看出，相較于基本K-means聚類算法，本文 的ABC_Kmeans聚類算法具有更好的收斂速度，并且減小了聚類中心對初始值的依賴。

4.2集群加速比性能實驗結果分析

加速比是用來比較并行系統(tǒng)或者并行化程序的性能和擴展性的重要指標，是指相同的任務在單處理器上消耗的時間，與并行處理器系統(tǒng)中消耗的時間的比率。

實驗用的數(shù)據(jù)集是通過程序生成的數(shù)據(jù)，生成了1 G、2 G、4 G、8 G等4個數(shù)據(jù)集，編號分別是A、B、C、D，每個數(shù)據(jù)集由30維數(shù)據(jù)組成，要求生成10個聚類類別。

實驗1 將1、2、4、8、10個節(jié)點參與實驗，觀察節(jié)點在逐漸增加時，算法完成聚類任務的時間，如圖3所示。從圖中可以看到，隨著節(jié)點的增加，A、B、C、D這4個數(shù)據(jù)集運行的時間反而降低，同時相同規(guī)模的數(shù)據(jù)集處理時間也呈線性減少，這說明在MapReduce上執(zhí)行ABC_Kmeans算法的加速比較好，且其加速比隨著數(shù)據(jù)規(guī)模的增大，性能也越來越好。

圖3并行化ABC_Kmeans算法的加速比實驗結果圖

實驗2 分別選擇2、4、6、8個節(jié)點，對應采用A、B、C、D這4個數(shù)據(jù)集計算，實驗結果如圖4所示。在圖中可以看到，當節(jié)點數(shù)與數(shù)據(jù)集的規(guī)模同比例增長時，MapReduce處理數(shù)據(jù)的水平也基本上保持一致，這說明了其有良好的擴展性。

圖4并行化ABC_Kmeans算法的擴展性實驗結果圖

5　結束語

鑒于基本K-means聚類算法過于依賴初始聚類中心，全局搜索能力較差的原因，本文將全局搜索能力較好的人工蜂群算法(ABC)融入其中，并改進了人工蜂群算法的初始蜜源，讓ABC_Kmeans不再依賴于初始中心。為了提高ABC_Kmeans算法的執(zhí)行效率，本文將其利用MapReduce并行化模型實現(xiàn)。實驗表明ABC_Kmeans并行聚類算法比一般的K-means聚類算法，具有更好的聚類性能和更高的時間效率，數(shù)據(jù)量越大，時間效率的優(yōu)勢越好。隨著云計算的興起，數(shù)據(jù)挖掘越演越烈，其中的聚類算法研究也越來越熱烈，本文的研究僅僅起到拋磚引玉的作用。

[1]曹永春，蔡正琦，邵亞斌.基于K_means的改進人工蜂群聚類算法[J].計算機應用，2014，34(1):204-208.

[2]管玉勇.K-means算法與智能算法融合的研究[D].合肥：安徽大學，2014.

[3] 李海生.蜂群算法及其在垂直Web檢索中的應用[D].廣州：廣州大學，2010.

[4]楊國營.基于MapReduce模型文本分類算法的研究[D].沈陽：遼寧大學，2013

[5]虞倩倩,戴月明，李晶晶.基于MapReduce的ACO-K-means并行聚類算法[J].計算機工程與應用，2013，49(16):117-121.

[6]趙衛(wèi)中，馬慧芳，傅燕翔,等.基于云計算平臺Hadoop的并行k-means聚類算法設計研究[J].計算機科學，2011，38(10):166-169

[7]喻金平，鄭杰，梅宏標.基于改進人工蜂群算法的K均值聚類算法[J].計算機應用，2014,34(4):1065-1069

[8]張石磊，武裝.一種基于Hadoop云計算平臺的聚類算法優(yōu)化的研究[J].計算機科學，2012，39(10):115-118

[9]莫贊，羅世雄，楊清平,等.基于K-means算法的改進蟻群聚類算法及其應用[J].系統(tǒng)科學學報，2012,20(3):91-94

[10]江小平，李成華，向文,等.k-means聚類算法的MapReduce并行化實現(xiàn)[J].華中科技大學學報，2011,39(6):120-124

Map Reduce Parallel Study of ABC_Kmeans Clustering Algorithm

Yuan Xiaoyan

(College of computer,Sichuan University of Arts and Science,Dazhou635000,China)

With the massive growth of data, data clustering algorithm research is facing the challenge of mass data mining and processing.For K - means clustering algorithm to the dependence of the initial clustering center is too strong, and poor global search ability shortcomings, will be an improved artificial colony algorithm combined with K - means algorithm, ABC_Kmeans clustering algorithm is proposed, in order to improve the performance of clustering.In order to improve the clustering algorithm’s ability to deal with huge amounts of data, uses the MapReduce model for parallel processing to ABC_Kmeans, design the Map, Combine and Reduce function respectively,Through the experiments on several huge amounts of data collection,show ABC_Kmeans parallel design of algorithm has good speedup and scalability, applicable to today's huge amounts of data mining and processing.

K-means；clustering；artificial bee colony；MapReduce

2015-07-22；

2015-09-07。

四川省教育廳一般項目(15ZB0318)；四川文理學院一般項目(2014Z012Y)；四川文理學院智能計算與物聯(lián)網(wǎng)工程技術中心資助。

袁小艷(1982-)，女，重慶永川人，碩士，講師，主要從事軟件技術及開發(fā)、云教育、知識工程方向的研究。

1671-4598(2016)01-0252-03

10.16526/j.cnki.11-4762/tp.2016.01.070

TP312

A