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