云環(huán)境下K-means算法的并行化

何佩佩，謝穎華（1.數(shù)字化紡織服裝技術(shù)教育部工程研究中心，上海 201620；2.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620）

云環(huán)境下K-means算法的并行化

何佩佩1，2，謝穎華1，2
（1.數(shù)字化紡織服裝技術(shù)教育部工程研究中心，上海 201620；2.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620）

隨著大數(shù)據(jù)時(shí)代的到來，傳統(tǒng)的聚類算法很難高效地處理海量數(shù)據(jù)，而云計(jì)算平臺憑借負(fù)載均衡、網(wǎng)絡(luò)存儲、虛擬化等技術(shù)，有效地突破了耗時(shí)耗能的瓶頸，為海量數(shù)據(jù)的處理提供了良好的解決方案。主要研究了Hadoop平臺下的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ù)集的分析和挖掘。

云計(jì)算；數(shù)據(jù)挖掘；MapReduce編程模型；K-means聚類算法；并行化

0 引言

隨著信息化社會的發(fā)展，各個(gè)行業(yè)中產(chǎn)生的數(shù)據(jù)都在以爆炸式的速度增長。典型的聚類算法——K-means算法是基于劃分的聚類算法，因其快速、簡單的特性而被廣泛應(yīng)用。但在面對海量數(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ò)、跨平臺等優(yōu)勢。它主要包含兩個(gè)部分：分布式文件系統(tǒng)（HDFS）和MapReduce編程模型。本文在基于 Hadoop云計(jì)算平臺，利用MapReduce編程模型實(shí)現(xiàn)了傳統(tǒng)K-means聚類算法的并行化設(shè)計(jì)，并進(jìn)行了相關(guān)實(shí)驗(yàn)的驗(yàn)證。

1 Ma p Re d u c e編程模型

MapReduce編程模型，顧名思義，由Map（映射）階段和Reduce（規(guī)約）階段組成，分別用兩個(gè)函數(shù)表示，即Map函數(shù)和Reduce函數(shù)［2］。MapReduce作業(yè)流程如圖1所示。

圖1 MapReduce作業(yè)流程圖

Map階段：Map任務(wù)運(yùn)行在集群的從節(jié)點(diǎn)上，多個(gè)Map任務(wù)相互間是獨(dú)立運(yùn)行的。原始數(shù)據(jù)在進(jìn)入 Map函數(shù)前，會將原始大數(shù)據(jù)集劃分并格式化為＜key1，value1＞鍵值對的形式。經(jīng)過Map函數(shù)的運(yùn)算處理后產(chǎn)生一個(gè)或多個(gè)中間鍵值對＜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由同一個(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)生鍵值對＜key3，value3＞作為結(jié)果，并將結(jié)果輸出到HDFS上。

為了方便理解，上述過程中數(shù)據(jù)格式的變化如圖2所示。

圖2 MapReduce程序數(shù)據(jù)變化的基本模型

2基于MapReduce的并行K-means算法的設(shè)計(jì)

2.1 K-means聚類算法的基本思路

K-means算法是聚類算法中使用最廣泛的基于劃分的算法，其基本思想是：將空間中的n個(gè)對象集合以K個(gè)點(diǎn)為中心進(jìn)行簇的劃分，歸類到與其距離最近的中點(diǎn)［3］。通過迭代的方式，逐次更新聚類中心的值并重新劃分簇，直至目標(biāo)函數(shù)收斂。K-means算法采用距離作為相似性的評價(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ù)對象，計(jì)劃劃分為K個(gè)簇，t為迭代次數(shù)，O為一次迭代中計(jì)算某一對象到各個(gè)類的中心距離的時(shí)間復(fù)雜度，那么串行實(shí)現(xiàn)K-means算法的時(shí)間復(fù)雜度為n×K×t×O［4］。由此可見，當(dāng)面對大數(shù)據(jù)時(shí)，算法的時(shí)間復(fù)雜度將成倍地增加。

2.2 K-means聚類算法的MapReduce化的設(shè)計(jì)

K-means算法中，計(jì)算數(shù)據(jù)對象與聚類中心距離是該算法中反復(fù)進(jìn)行的操作，并且每個(gè)數(shù)據(jù)對象到聚類中心距離的計(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ù)對象，記錄為＜行號，數(shù)據(jù)內(nèi)容＞鍵值對；接著，與保存在全局變量中聚類中心進(jìn)行運(yùn)算，得出數(shù)據(jù)對象與各個(gè)聚類中心的距離；最后，將數(shù)據(jù)對象分配給距離最近的類中，產(chǎn)生＜聚類ID，數(shù)據(jù)內(nèi)容＞鍵值對作為函數(shù)輸出。Map函數(shù)的偽代碼如下：

圖3 基于MapReduce的并行K-means算法

2.2.2 Reduce函數(shù)的設(shè)計(jì)

首先，將擁有相同聚類ID的數(shù)據(jù)對象分配給同一個(gè)Reduce任務(wù)；接著，Reduce函數(shù)將記錄所接收到的樣本個(gè)數(shù)并將數(shù)據(jù)對象各個(gè)維坐標(biāo)分別累加；最后，將各維坐標(biāo)之和除以樣本個(gè)數(shù)得到各個(gè)維坐標(biāo)的均值，計(jì)算結(jié)果就是該類新的聚類中心。Reduce函數(shù)的偽代碼如下：

將本輪 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算法對初始聚類中心有較強(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平臺上啟動、分配任務(wù)以及進(jìn)行作業(yè)間的交互卻需要耗費(fèi)固定的資源。但隨著數(shù)據(jù)集規(guī)模的增大，計(jì)算任務(wù)所占用的資源的比例將不斷增大，使并行化算法的優(yōu)勢得以體現(xiàn)，其運(yùn)行時(shí)間的增長速度遠(yuǎn)小于串行算法。另外，由于串行算法所消耗的資源快速地增長，系統(tǒng)將會報(bào)告內(nèi)存不足。

表1 實(shí)驗(yàn)結(jié)果

4 結(jié)論

本文對 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ì)算效率。

［1］謝雪蓮，李蘭友.基于云計(jì)算的并行 K-means聚類算法研究［J］.計(jì)算機(jī)測量與控制，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ì)算平臺 Hadoop的并行 K-means聚類算法設(shè)計(jì)研究［J］.計(jì)算機(jī)科學(xué)與探索，2011，38（10）：166-168，176.

圖7 課程顯示界面

界面代碼執(zhí)行流程如下：

（1）用戶點(diǎn)擊主界面課程表模塊，軟件跳轉(zhuǎn)至課程顯示界面，軟件通過查詢校歷獲取當(dāng)前周次以及星期，默認(rèn)顯示當(dāng)天的課表；

（2）用戶點(diǎn)擊某節(jié)課程信息，跳轉(zhuǎn)至該節(jié)次課程詳情界面；

（3）用戶點(diǎn)擊右上角周次選擇按鈕，彈出周次選擇面板，用戶可以選擇周次，查詢所選周次課表情況。

4.3 自習(xí)室模塊

自習(xí)室模塊提供用戶自習(xí)室查詢功能，用戶可以通過選擇日期、教學(xué)區(qū)域查詢自習(xí)室信息。自習(xí)室查詢界面如圖8所示。

圖8 自習(xí)室查詢界面

5 結(jié)論

在整個(gè)軟件開發(fā)中注重軟件的可用性、易用性以及可持續(xù)性，努力提升用戶的操作體驗(yàn)。由于需求的不斷更新和技術(shù)的不斷發(fā)展，軟件還需要進(jìn)一步完善，需要在以后的使用反饋中不斷進(jìn)行優(yōu)化升級。

參考文獻(xiàn)

［1］李曉.基于Android平臺的手持終端應(yīng)用功能開發(fā)與設(shè)計(jì)［D］.武漢：湖北大學(xué)，2010.

［2］陳昱，江蘭帆.基于 Google Android平臺的移動開發(fā)研究［J］.福建電腦，2008（11）：156-157.

［3］姜波.嵌入式數(shù)據(jù)庫SQLite調(diào)試器的研究與實(shí)現(xiàn)［D］.昆明：昆明理工大學(xué)，2012.

［4］岑冬梅.基于 SQLite的空間數(shù)據(jù)庫存儲技術(shù)的研究與實(shí)現(xiàn)［D］.武漢：武漢科技大學(xué)，2009.

［5］初雅莉，陳昌穩(wěn)，崔召金.基于 Android的智慧校園手機(jī)系統(tǒng)［J］.微型機(jī)與應(yīng)用，2013，32（15）：15-17.

［6］張立.一種基于 Android系統(tǒng)網(wǎng)絡(luò)模塊功耗的評估和分析［J］.計(jì)算機(jī)科學(xué)，2012，39（6）：289-292.

（收稿日期：2015-07-30）

作者簡介：

盧照（1983-），男，碩士，主要研究方向：并行處理，智能算法。

K-means algorithm parallelization in Cloud environment

He Peipei1，2，Xie Yinghua1，2
（1.Engineering Research Center of Digitized Textile＆amp；Apparel Technology，Ministry of Education，Shanghai 201620，China；2.Information Science and Technology College，Donghua University，Shanghai 201620，China）

The era of big data is coming and the current clustering algorithms are ineffecicient.The Cloud computing platform breaks the state of consuming energy through load balance，network storage and virtualization technology.The paper analyzed the MapReduce programming model in Hadoop Cloud computing platform and the traditional K-means algorithm.The parallel K-means algorithm based on MapReduce was designed including Map function and Reduce function.The result of experiments shows that it fits to data mining on massive datasets.

Cloud computing；data mining；MapReduce；K-means algorithm；parallel algorithm

TP311

A

1674-7720（2015）24-0025-03

何佩佩，謝穎華.云環(huán)境下K-means算法的并行化［J］.微型機(jī)與應(yīng)用，2015，34（24）：25-27，31.

2015-07-23）

何佩佩（1991-），通信作者，女，碩士研究生，主要研究方向：數(shù)據(jù)分析、數(shù)據(jù)挖掘。E-mail：hpp1991_06@126.com。

謝穎華（1972-），女，博士，副教授，主要研究方向：通信與信息系統(tǒng)、智能信息處理、無線網(wǎng)絡(luò)。