摘 要： 隨著大數(shù)據(jù)時(shí)代的到來(lái),，傳統(tǒng)的聚類(lèi)算法很難高效地處理海量數(shù)據(jù)，而云計(jì)算平臺(tái)憑借負(fù)載均衡,、網(wǎng)絡(luò)存儲(chǔ),、虛擬化等技術(shù),，有效地突破了耗時(shí)耗能的瓶頸，為海量數(shù)據(jù)的處理提供了良好的解決方案,。主要研究了Hadoop平臺(tái)下的MapReduce編程模型及傳統(tǒng)K-means算法,，提出了一種基于MapReduce的并行化K-means算法的設(shè)計(jì)方案，包括Map函數(shù)和Reduce函數(shù)的設(shè)計(jì),。通過(guò)實(shí)驗(yàn),，驗(yàn)證了并行化K-means算法適用于較大規(guī)模數(shù)據(jù)集的分析和挖掘。
關(guān)鍵詞： 云計(jì)算,；數(shù)據(jù)挖掘,；MapReduce編程模型；K-means聚類(lèi)算法,；并行化
0 引言
隨著信息化社會(huì)的發(fā)展,，各個(gè)行業(yè)中產(chǎn)生的數(shù)據(jù)都在以爆炸式的速度增長(zhǎng)。典型的聚類(lèi)算法——K-means算法是基于劃分的聚類(lèi)算法,，因其快速,、簡(jiǎn)單的特性而被廣泛應(yīng)用。但在面對(duì)海量數(shù)據(jù)時(shí),，傳統(tǒng)的K-means算法無(wú)論是在時(shí)間復(fù)雜度還是空間復(fù)雜度上都遇到了瓶頸[1],，而云計(jì)算技術(shù)的出現(xiàn)為海量數(shù)據(jù)的處理提供了良好的解決方案。
云計(jì)算是一種基于互聯(lián)網(wǎng)的計(jì)算方式,。Hadoop則是云計(jì)算技術(shù)的開(kāi)源實(shí)現(xiàn),，具有高容錯(cuò)、跨平臺(tái)等優(yōu)勢(shì),。它主要包含兩個(gè)部分：分布式文件系統(tǒng)（HDFS）和MapReduce編程模型,。本文在基于Hadoop云計(jì)算平臺(tái)，利用MapReduce編程模型實(shí)現(xiàn)了傳統(tǒng)K-means聚類(lèi)算法的并行化設(shè)計(jì),，并進(jìn)行了相關(guān)實(shí)驗(yàn)的驗(yàn)證,。
1 MapReduce編程模型
MapReduce編程模型，顧名思義,，由Map（映射）階段和Reduce（規(guī)約）階段組成,，分別用兩個(gè)函數(shù)表示，即Map函數(shù)和Reduce函數(shù)[2],。MapReduce作業(yè)流程如圖1所示,。
Map階段：Map任務(wù)運(yùn)行在集群的從節(jié)點(diǎn)上，多個(gè)Map任務(wù)相互間是獨(dú)立運(yùn)行的,。原始數(shù)據(jù)在進(jìn)入Map函數(shù)前,，會(huì)將原始大數(shù)據(jù)集劃分并格式化為<key1,，value1>鍵值對(duì)的形式,。經(jīng)過(guò)Map函數(shù)的運(yùn)算處理后產(chǎn)生一個(gè)或多個(gè)中間鍵值對(duì)<key2,，value2>。
Shuffle階段：它由Partition（數(shù)據(jù)分割）和Combine（數(shù)據(jù)合并）組成,。Combine就是將Map任務(wù)輸出的中間結(jié)果中有相同key2的<key2,，value2>對(duì)合并成一對(duì)。Partition則是采用默認(rèn)hash函數(shù)將中間結(jié)果按照key2值的范圍分成R份,，發(fā)送并保證某一范圍內(nèi)的key2由同一個(gè)Reduce任務(wù)來(lái)處理,。
Reduce階段：每個(gè)Reduce任務(wù)需要從多個(gè)Map任務(wù)節(jié)點(diǎn)取得其負(fù)責(zé)的key2區(qū)間內(nèi)的中間結(jié)果。Reduce函數(shù)接收到形如<key2,，（list of value2）>形式的輸入,，進(jìn)行處理后產(chǎn)生鍵值對(duì)<key3，value3>作為結(jié)果,，并將結(jié)果輸出到HDFS上,。
為了方便理解，上述過(guò)程中數(shù)據(jù)格式的變化如圖2所示,。
2 基于MapReduce的并行K-means算法的設(shè)計(jì)
2.1 K-means聚類(lèi)算法的基本思路
K-means算法是聚類(lèi)算法中使用最廣泛的基于劃分的算法,，其基本思想是：將空間中的n個(gè)對(duì)象集合以K個(gè)點(diǎn)為中心進(jìn)行簇的劃分，歸類(lèi)到與其距離最近的中點(diǎn)[3],。通過(guò)迭代的方式,，逐次更新聚類(lèi)中心的值并重新劃分簇，直至目標(biāo)函數(shù)收斂,。K-means算法采用距離作為相似性的評(píng)價(jià)指標(biāo),，其目標(biāo)函數(shù)可表示為：
其中，xi表示數(shù)據(jù)集X={x1,，x2,，…，xN}中第i個(gè)樣本,，N為樣本總數(shù),；Cj表示第j個(gè)簇，K為簇的總個(gè)數(shù),，zj則表示第j個(gè)簇的中心,。
假設(shè)共有n個(gè)數(shù)據(jù)對(duì)象，計(jì)劃劃分為K個(gè)簇,，t為迭代次數(shù),，O為一次迭代中計(jì)算某一對(duì)象到各個(gè)類(lèi)的中心距離的時(shí)間復(fù)雜度，那么串行實(shí)現(xiàn)K-means算法的時(shí)間復(fù)雜度為n×K×t×O[4],。由此可見(jiàn),，當(dāng)面對(duì)大數(shù)據(jù)時(shí)，算法的時(shí)間復(fù)雜度將成倍地增加。
2.2 K-means聚類(lèi)算法的MapReduce化的設(shè)計(jì)
K-means算法中,，計(jì)算數(shù)據(jù)對(duì)象與聚類(lèi)中心距離是該算法中反復(fù)進(jìn)行的操作,，并且每個(gè)數(shù)據(jù)對(duì)象到聚類(lèi)中心距離的計(jì)算過(guò)程都是相互獨(dú)立的。圖3描述了基于MapReduce的并行K-means算法的設(shè)計(jì)方法,，其中數(shù)據(jù)的分片由MapReduce環(huán)境自行完成,，只需要編寫(xiě)Map函數(shù)和Reduce函數(shù)的實(shí)現(xiàn)代碼即可。
2.2.1 Map函數(shù)的設(shè)計(jì)
首先,，Map函數(shù)逐行掃描數(shù)據(jù)段,，按行作為數(shù)據(jù)對(duì)象，記錄為<行號(hào),，數(shù)據(jù)內(nèi)容>鍵值對(duì),；接著，與保存在全局變量中聚類(lèi)中心進(jìn)行運(yùn)算,，得出數(shù)據(jù)對(duì)象與各個(gè)聚類(lèi)中心的距離,；最后，將數(shù)據(jù)對(duì)象分配給距離最近的類(lèi)中,，產(chǎn)生<聚類(lèi)ID,，數(shù)據(jù)內(nèi)容>鍵值對(duì)作為函數(shù)輸出。Map函數(shù)的偽代碼如下：
void map（LongWritable key,，Text point,，Context context）{
centerIndex=0；//初始化數(shù)據(jù)對(duì)象所在的類(lèi)
minDis=MAXDISTANCE,；
//初始化數(shù)據(jù)對(duì)象與聚類(lèi)中心的最小距離
for（int i=0,；i<k；i++）{//遍歷各個(gè)聚類(lèi)中心
tempDis=Dis（point,，cluster[i]）,；
//計(jì)算數(shù)據(jù)對(duì)象與聚類(lèi)中心的距離
if（tempDis<minDis）{
//將數(shù)據(jù)對(duì)象分配至距離最近的類(lèi)
minDis=tempDis；
centerIndex=i,；
}
}
context.write（centerIndex+1,，point）；
//輸出<類(lèi)ID,，數(shù)據(jù)對(duì)象>鍵值對(duì)
}
2.2.2 Reduce函數(shù)的設(shè)計(jì)
首先,，將擁有相同聚類(lèi)ID的數(shù)據(jù)對(duì)象分配給同一個(gè)Reduce任務(wù)；接著,，Reduce函數(shù)將記錄所接收到的樣本個(gè)數(shù)并將數(shù)據(jù)對(duì)象各個(gè)維坐標(biāo)分別累加,；最后，將各維坐標(biāo)之和除以樣本個(gè)數(shù)得到各個(gè)維坐標(biāo)的均值,，計(jì)算結(jié)果就是該類(lèi)新的聚類(lèi)中心,。Reduce函數(shù)的偽代碼如下：
void reduce（IntWritable key，Iterable<Text>value，Context context）{
int colnum=value.get（0）.size（）,；//數(shù)據(jù)對(duì)象的屬性個(gè)數(shù)
for（int i=0,；i<colnum；i++）{
double sum=0,；
int rownum=value.size（）；//獲取數(shù)據(jù)對(duì)象的個(gè)數(shù)
for（int j=0,；j<rownum,；j++）{//計(jì)算每列的平均值
sum+=value.get（j）.get（i）；
}
avg[i] = sum/rownum,；
}
context.write（key,，avg）；
//輸出<聚類(lèi)ID,，聚類(lèi)中心>鍵值對(duì)
}
將本輪reduce函數(shù)輸出的聚類(lèi)中心與上一輪的聚類(lèi)中心比較,，若目標(biāo)函數(shù)收斂，則算法結(jié)束,；否則,，本輪的聚類(lèi)中心將寫(xiě)入中心文件，作為新的聚類(lèi)中心,。
3 實(shí)驗(yàn)與分析
實(shí)驗(yàn)?zāi)康氖潜容^在相同的硬件配置下,，Hadoop集群中1個(gè)運(yùn)算節(jié)點(diǎn)和普通計(jì)算機(jī)分別使用并行K-means算法和傳統(tǒng)串行K-means處理相同規(guī)模數(shù)據(jù)的能力?？紤]到K-means算法對(duì)初始聚類(lèi)中心有較強(qiáng)的依賴(lài)性,，在相同數(shù)據(jù)集的條件下重復(fù)進(jìn)行實(shí)驗(yàn)10次，取平均值作為最終的實(shí)驗(yàn)數(shù)據(jù),，實(shí)驗(yàn)結(jié)果如表1所示,。
表1中，t1表示使用傳統(tǒng)串行K-means算法處理數(shù)據(jù)集所花的時(shí)間,；t2表示使用并行化K-means算法處理數(shù)據(jù)集所花的時(shí)間,。通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn)，當(dāng)數(shù)據(jù)集的規(guī)模較小時(shí),，串行K-means算法的執(zhí)行效率優(yōu)于并行化K-means算法的執(zhí)行效率,，這是由于數(shù)據(jù)量小時(shí)，其計(jì)算任務(wù)所消耗的資源較少,，但是在Hadoop平臺(tái)上啟動(dòng),、分配任務(wù)以及進(jìn)行作業(yè)間的交互卻需要耗費(fèi)固定的資源。但隨著數(shù)據(jù)集規(guī)模的增大,，計(jì)算任務(wù)所占用的資源的比例將不斷增大,，使并行化算法的優(yōu)勢(shì)得以體現(xiàn)，其運(yùn)行時(shí)間的增長(zhǎng)速度遠(yuǎn)小于串行算法。另外,，由于串行算法所消耗的資源快速地增長(zhǎng),，系統(tǒng)將會(huì)報(bào)告內(nèi)存不足。
4 結(jié)論
本文對(duì)Hadoop的MapReduce編程模型以及聚類(lèi)算法K-means進(jìn)行了研究,，給出了基于MapReduce的并行化K-means算法的設(shè)計(jì)方案并進(jìn)行了實(shí)驗(yàn)驗(yàn)證,。實(shí)驗(yàn)結(jié)果表明，基于MapReduce的并行化K-means算法適用于處理較大規(guī)模的數(shù)據(jù)挖掘任務(wù),，并且具有較好的計(jì)算效率,。
參考文獻(xiàn)
[1] 謝雪蓮，李蘭友.基于云計(jì)算的并行K-means聚類(lèi)算法研究[J].計(jì)算機(jī)測(cè)量與控制,，2014,，22（5）：1510-1512.
[2] 冀素琴，石洪波.基于MapReduce的K-means聚類(lèi)集成[J].計(jì)算機(jī)工程,，2013,，39（9）：84-87.
[3] 周婷，張君瑛,，羅成.基于Hadoop的K-means聚類(lèi)算法的實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,，2013，23（7）：18-21.
[4] 趙衛(wèi)中,，馬慧芳,，傅燕翔，等.基于云計(jì)算平臺(tái)Hadoop的并行K-means聚類(lèi)算法設(shè)計(jì)研究[J].計(jì)算機(jī)科學(xué)與探索,，2011,，38（10）：166-168，176.