摘 要： 隨著大數(shù)據(jù)時(shí)代的到來，傳統(tǒng)的聚類算法很難高效地處理海量數(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ì)。通過實(shí)驗(yàn)，驗(yàn)證了并行化K-means算法適用于較大規(guī)模數(shù)據(jù)集的分析和挖掘。
關(guān)鍵詞： 云計(jì)算；數(shù)據(jù)挖掘；MapReduce編程模型；K-means聚類算法；并行化
0 引言
隨著信息化社會(huì)的發(fā)展，各個(gè)行業(yè)中產(chǎn)生的數(shù)據(jù)都在以爆炸式的速度增長(zhǎng)。典型的聚類算法——K-means算法是基于劃分的聚類算法，因其快速、簡(jiǎn)單的特性而被廣泛應(yīng)用。但在面對(duì)海量數(shù)據(jù)時(shí)，傳統(tǒng)的K-means算法無論是在時(shí)間復(fù)雜度還是空間復(fù)雜度上都遇到了瓶頸[1]，而云計(jì)算技術(shù)的出現(xiàn)為海量數(shù)據(jù)的處理提供了良好的解決方案。
云計(jì)算是一種基于互聯(lián)網(wǎng)的計(jì)算方式。Hadoop則是云計(jì)算技術(shù)的開源實(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聚類算法的并行化設(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)過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ù)來處理。
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上。
為了方便理解，上述過程中數(shù)據(jù)格式的變化如圖2所示。
2 基于MapReduce的并行K-means算法的設(shè)計(jì)
2.1 K-means聚類算法的基本思路
K-means算法是聚類算法中使用最廣泛的基于劃分的算法，其基本思想是：將空間中的n個(gè)對(duì)象集合以K個(gè)點(diǎn)為中心進(jìn)行簇的劃分，歸類到與其距離最近的中點(diǎn)[3]。通過迭代的方式，逐次更新聚類中心的值并重新劃分簇，直至目標(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è)類的中心距離的時(shí)間復(fù)雜度，那么串行實(shí)現(xiàn)K-means算法的時(shí)間復(fù)雜度為n×K×t×O[4]。由此可見，當(dāng)面對(duì)大數(shù)據(jù)時(shí)，算法的時(shí)間復(fù)雜度將成倍地增加。
2.2 K-means聚類算法的MapReduce化的設(shè)計(jì)
K-means算法中，計(jì)算數(shù)據(jù)對(duì)象與聚類中心距離是該算法中反復(fù)進(jìn)行的操作，并且每個(gè)數(shù)據(jù)對(duì)象到聚類中心距離的計(jì)算過程都是相互獨(dú)立的。圖3描述了基于MapReduce的并行K-means算法的設(shè)計(jì)方法，其中數(shù)據(jù)的分片由MapReduce環(huán)境自行完成，只需要編寫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ì)；接著，與保存在全局變量中聚類中心進(jìn)行運(yùn)算，得出數(shù)據(jù)對(duì)象與各個(gè)聚類中心的距離；最后，將數(shù)據(jù)對(duì)象分配給距離最近的類中，產(chǎn)生<聚類ID，數(shù)據(jù)內(nèi)容>鍵值對(duì)作為函數(shù)輸出。Map函數(shù)的偽代碼如下：
void map（LongWritable key，Text point，Context context）{
centerIndex=0；//初始化數(shù)據(jù)對(duì)象所在的類
minDis=MAXDISTANCE；
//初始化數(shù)據(jù)對(duì)象與聚類中心的最小距離
for（int i=0；i<k；i++）{//遍歷各個(gè)聚類中心
tempDis=Dis（point，cluster[i]）；
//計(jì)算數(shù)據(jù)對(duì)象與聚類中心的距離
if（tempDis<minDis）{
//將數(shù)據(jù)對(duì)象分配至距離最近的類
minDis=tempDis；
centerIndex=i；
}
}
context.write（centerIndex+1，point）；
//輸出<類ID，數(shù)據(jù)對(duì)象>鍵值對(duì)
}
2.2.2 Reduce函數(shù)的設(shè)計(jì)
首先，將擁有相同聚類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é)果就是該類新的聚類中心。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）；
//輸出<聚類ID，聚類中心>鍵值對(duì)
}
將本輪reduce函數(shù)輸出的聚類中心與上一輪的聚類中心比較，若目標(biāo)函數(shù)收斂，則算法結(jié)束；否則，本輪的聚類中心將寫入中心文件，作為新的聚類中心。
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ì)初始聚類中心有較強(qiáng)的依賴性，在相同數(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í)間。通過實(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編程模型以及聚類算法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聚類算法研究[J].計(jì)算機(jī)測(cè)量與控制，2014，22（5）：1510-1512.
[2] 冀素琴，石洪波.基于MapReduce的K-means聚類集成[J].計(jì)算機(jī)工程，2013，39（9）：84-87.
[3] 周婷，張君瑛，羅成.基于Hadoop的K-means聚類算法的實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（7）：18-21.
[4] 趙衛(wèi)中，馬慧芳，傅燕翔，等.基于云計(jì)算平臺(tái)Hadoop的并行K-means聚類算法設(shè)計(jì)研究[J].計(jì)算機(jī)科學(xué)與探索，2011，38（10）：166-168，176.