王鵬，王睿婕

（長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

隨著計(jì)算機(jī)網(wǎng)絡(luò)通信技術(shù)的迅速發(fā)展，如今已經(jīng)進(jìn)入了大數(shù)據(jù)時(shí)代。大體上講，大數(shù)據(jù)（Big Data）是指在一定時(shí)間內(nèi)，不能夠使用常規(guī)計(jì)算機(jī)和軟硬件工具對(duì)其進(jìn)行感知、獲取、管理、處理和服務(wù)的數(shù)據(jù)集合［1］?？焖僭鲩L(zhǎng)的大數(shù)據(jù)，在處理復(fù)雜度與存儲(chǔ)規(guī)模上對(duì)現(xiàn)有的計(jì)算機(jī)體系架構(gòu)提出了嚴(yán)峻的考驗(yàn)，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)并行管理技術(shù)在擴(kuò)展性方面遇到了巨大的障礙［2］。MapReduce編程模型則可以很好地處理這一問(wèn)題，提高數(shù)據(jù)挖掘算法的執(zhí)行效率。劉義等人［3］提出了MapReduce框架下R-樹(shù)的k-近鄰連接算法，顧榮等人［4］提出了MapReduce框架下預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)鏈路的實(shí)現(xiàn)，饒君等人［5］提出了高效可擴(kuò)展語(yǔ)義推理引擎的MapReduce模型實(shí)現(xiàn)。MapReduce是Google提出的可在Hadoop分布式云集群上并行處理海量數(shù)據(jù)集的編程模型［6］，具有良好的容錯(cuò)性與擴(kuò)展性，Map和Reduce的概念，即映射與化簡(jiǎn)，是借鑒于函數(shù)式的編程語(yǔ)言，這也是該模型的重要思想。它將大數(shù)據(jù)“分而治之”地分解為多個(gè)小規(guī)模數(shù)據(jù)，并分布到多個(gè)集群節(jié)點(diǎn)中去，共同完成對(duì)大數(shù)據(jù)的處理。這樣可以提高運(yùn)行效率，降低每一部分的運(yùn)算強(qiáng)度，最終達(dá)到節(jié)省時(shí)間的目的。

聚類分析是處理大數(shù)據(jù)的常用算法，常常被用于市場(chǎng)分析、圖像分割、語(yǔ)音識(shí)別等科研領(lǐng)域，為了提高對(duì)大規(guī)模數(shù)據(jù)的聚類效率，很多并行算法相繼被提出，呂奕清等人［7］提出了基于MPI的并行PSO混合K-均值聚類算法，張軍偉等人［8］提出了二分K-均值聚類算法，陶冶等人［9］提出了基于消息傳遞接口的并行K均值算法。本文將K-均值聚類算法應(yīng)用于MapReduce編程框架中，并在Hadoop分布式云計(jì)算平臺(tái)上進(jìn)行對(duì)大規(guī)模數(shù)據(jù)聚類實(shí)驗(yàn)。

1 MapReduce編程模型

MapReduce模型因其簡(jiǎn)單、高效、易寫(xiě)等優(yōu)勢(shì)，近年來(lái)被廣泛運(yùn)用于并行處理海量數(shù)據(jù)集，可實(shí)現(xiàn)于Hadoop開(kāi)源分布式云計(jì)算平臺(tái)之上。在Hadoop集群中，執(zhí)行MapReduce任務(wù)的節(jié)點(diǎn)分為Job-Tracker和 TaskTracker兩個(gè)角色［10］，JobTracker負(fù)責(zé)分配、調(diào)節(jié)任務(wù)，TaskTracker負(fù)責(zé)執(zhí)行任務(wù)，一個(gè)集群中只有一個(gè)JobTracker節(jié)點(diǎn)。每一個(gè)MapReduce任務(wù)會(huì)經(jīng)歷兩個(gè)階段：Map階段與Reduce階段。用戶可按需定義Map函數(shù)和Reduce函數(shù)，數(shù)據(jù)文件首先被分割成多個(gè)split，以＜key，value＞對(duì)的形式輸入至Map函數(shù)，經(jīng)多個(gè)Map函數(shù)并行處理后，得到新的＜key，value＞對(duì)，作為中間結(jié)果，系統(tǒng)將包含相同Key值的＜key，value＞對(duì)合并后排序，形成諸如＜key，list＜value＞＞形式的中間結(jié)果，并輸入到Reduce函數(shù)，最后將各個(gè)Reduce函數(shù)并行處理后形成的結(jié)果整合，得到最終結(jié)果。MapReduce計(jì)算流程圖如圖1所示。

2 K-均值聚類的MapReduce模型實(shí)現(xiàn)

2.1 K-均值聚類

K-均值算法簡(jiǎn)潔和高效的優(yōu)點(diǎn)，使之成為最著名的劃分聚類算法，并獲得了廣泛的應(yīng)用。用戶給定一個(gè)數(shù)據(jù)點(diǎn)集合D和需要的聚類數(shù)目K，在對(duì)樣本類別不清晰的情況下，根據(jù)已有樣本特征向量對(duì)樣本進(jìn)行類別劃分，K-均值算法根據(jù)距離函數(shù)反復(fù)的將數(shù)據(jù)點(diǎn)劃分成K類，并返回給用戶劃分結(jié)果［11］。

其中k表示聚類數(shù)目，Cw表示第w個(gè)聚類數(shù)目，mw是聚類Cw的聚類中心，即Cw聚類中所有數(shù)據(jù)點(diǎn)均值向量，dist（x，mw）表示點(diǎn)x與聚類中心mw的距離。

K-均值算法適用于均值能被計(jì)算的數(shù)據(jù)集

定義1 包含在某一聚類中所有數(shù)據(jù)點(diǎn)的均值，即為聚類中心。

定義2 設(shè)數(shù)據(jù)點(diǎn)的集合為D，D=｛x1,x2,x3,…,xn｝，其中 xi=(Xi1,Xi2,Xi3,...,Xir)，是實(shí)數(shù)空間X?Rr中的向量，r表示數(shù)據(jù)空間的維度，在這里指數(shù)據(jù)點(diǎn)的屬性數(shù)目。該算法將給定的數(shù)據(jù)點(diǎn)集劃分為K個(gè)聚類，每個(gè)聚類有一個(gè)聚類中心，通常用聚類中心來(lái)表示這一聚類，又因?yàn)楣矂澐譃镵個(gè)聚類，所以該算法的名字為K-均值聚類算法。

算法的描述如下：

（1）Algorithm K-均值（K，D）

（2）隨機(jī)選得K個(gè)數(shù)據(jù)點(diǎn)作為聚類中心

（3）Repeat

（4）For 獲取集合D中的每一個(gè)數(shù)據(jù)點(diǎn)X do

（5）計(jì)算數(shù)據(jù)點(diǎn)x到K個(gè)聚類中心的距離

（6）選擇與x距離最小的聚類，將x歸為此聚類

（7）End for

（8）在當(dāng)前劃分的情況下，計(jì)算新的聚類中心

（9）Until停止規(guī)則出現(xiàn) 返回結(jié)果

其中停止規(guī)則可以是以下任何一個(gè)：

a.不再有數(shù)據(jù)點(diǎn)被重新分配，或者有在規(guī)定很小數(shù)量?jī)?nèi)的數(shù)據(jù)點(diǎn)被重新分配；

b.不再有聚類中心發(fā)生變化，或者有在規(guī)定很小數(shù)量?jī)?nèi)的數(shù)據(jù)中心發(fā)生變化；

c.誤差平方和（SSE）局部最小。誤差平方和的計(jì)算公式如下：上。在歐式空間中，可以用下面的公式計(jì)算聚類均值：

圖1 MapReduce計(jì)算流程圖

2.2 K-均值聚類的MapReduce模型實(shí)現(xiàn)方法

MapReduce框架并不適合所有算法，只有具備可伸縮性的算法才適用。MapReduce框架在處理大規(guī)模數(shù)據(jù)時(shí)采用分-總的方式進(jìn)行并行計(jì)算，Map函數(shù)負(fù)責(zé)對(duì)數(shù)據(jù)進(jìn)行“分布計(jì)算”，各個(gè)Mapper節(jié)點(diǎn)在工作時(shí)不能夠?qū)崟r(shí)的交互，只有中間結(jié)果生成完畢才能得到最終的結(jié)果，這一點(diǎn)也要求必須保證分到每一個(gè)Mapper節(jié)點(diǎn)的工作相互獨(dú)立且相同，無(wú)論任務(wù)大小，工作方法都不改變。Reduce函數(shù)負(fù)責(zé)對(duì)中間結(jié)果進(jìn)行處理，以得到最終結(jié)果。完整的MapReduce框架程序由Main函數(shù)、Map函數(shù)和Reduce函數(shù)組成。

K-均值算法是迭代式運(yùn)行，數(shù)據(jù)運(yùn)行完一遍后，判斷是否滿足終止條件，從而決定是否停止下一次迭代，本算法以第一種終止規(guī)則為例，即判斷是否存在重新分配的點(diǎn)，若不存在，則停止迭代。

該算法運(yùn)行過(guò)程如下：

（1）Main函數(shù)負(fù)責(zé)生成隨機(jī)的聚類中心，并發(fā)送到每一個(gè)Mapper節(jié)點(diǎn)上。

（2）Map函數(shù)負(fù)責(zé)計(jì)算數(shù)據(jù)點(diǎn)與聚類中心的距離。輸入＜Key，Value＞對(duì)應(yīng)于＜數(shù)據(jù)分片中的行號(hào)，數(shù)據(jù)記錄＞。輸出＜Key，Value＞對(duì)應(yīng)于＜數(shù)據(jù)點(diǎn)的唯一標(biāo)識(shí)，聚類中心編號(hào)+該數(shù)據(jù)點(diǎn)與該聚類中心的距離＞。Map函數(shù)偽代碼如下：

輸入：數(shù)據(jù)點(diǎn)集；

輸出：數(shù)據(jù)點(diǎn)與各個(gè)聚類中心的距離；

1.Key：數(shù)據(jù)文件行號(hào) Value：數(shù)據(jù)記錄

2.For each datapoint in DataPointDS

3.For i←0 To K//K為聚類數(shù)

4.設(shè)置Key：數(shù)據(jù)點(diǎn) Value：i_distance（數(shù)據(jù)點(diǎn)，cluster［i］）

//使用公式3，求出數(shù)據(jù)點(diǎn)到每個(gè)聚類中心的距離

5.輸出（Key，Value）

（3）Reduce函數(shù)負(fù)責(zé)比較出距每個(gè)數(shù)據(jù)點(diǎn)最近的聚類中心。輸入＜Key，Value＞與Map函數(shù)的輸出一致。輸出＜Key，Value＞對(duì)應(yīng)于＜數(shù)據(jù)點(diǎn)的唯一標(biāo)識(shí)，與該數(shù)據(jù)點(diǎn)距離最近聚類中心編號(hào)＞。Reduce函數(shù)偽代碼如下：

輸入：數(shù)據(jù)點(diǎn)到各個(gè)聚類中心的距離列表

輸出：數(shù)據(jù)點(diǎn)、與該數(shù)據(jù)點(diǎn)距離最近的聚類中心

1.Key：數(shù)據(jù)點(diǎn) Values：Iterator（1_distance_1，2_distance_2，…，K_distance_K）

2.設(shè)置MinDistance：MAX_VALUE

3.For i←0 To K

4.IF distance_i＜MinDistance

5.設(shè)置MinDistance：distance_i

6.設(shè)置Value：MinDistance

7.輸出（Key，Value）

（4）Main函數(shù)最后將數(shù)據(jù)點(diǎn)分配給各個(gè)聚類，判斷是否有數(shù)據(jù)點(diǎn)被重新劃分，若劃分情況沒(méi)有改變，則說(shuō)明算法已完成，程序結(jié)束，返回聚類中心及分類情況，否則重新計(jì)算聚類中心，啟動(dòng)下一次迭代。

根據(jù)上述思路，設(shè)計(jì)出基于MapReduce框架的分布式K-均值聚類算法，運(yùn)行過(guò)程流程圖如圖2所示。

圖2 K-均值算法分布式流程圖

2.3 理論性能分析

MapReduce編程模型運(yùn)行所在的Hadoop平臺(tái)使用HDFS分布式文件系統(tǒng)作為數(shù)據(jù)存儲(chǔ)方式，將大規(guī)模待聚類數(shù)據(jù)分片存儲(chǔ)，降低了計(jì)算機(jī)存儲(chǔ)量，K-均值聚類算法中每迭代一次都要計(jì)算出數(shù)據(jù)點(diǎn)與每個(gè)聚類中心的距離，對(duì)于屬性數(shù)量較多的數(shù)據(jù)集，是個(gè)龐大的工作量。而在Hadoop集群中，每個(gè)節(jié)點(diǎn)僅需對(duì)所分配Split數(shù)據(jù)進(jìn)行處理，少量數(shù)據(jù)被裝入CPU進(jìn)行計(jì)算，減少了CPU的工作量，提高了數(shù)據(jù)處理效率，設(shè)集群中TaskTracker工作節(jié)點(diǎn)數(shù)為n，忽略啟動(dòng)MapReduce任務(wù)所耗時(shí)間，則集群節(jié)點(diǎn)CPU工作量為原單機(jī)環(huán)境下CPU工作量的1/n，處理效率提高了n倍。

3 實(shí)驗(yàn)結(jié)果與分析

該試驗(yàn)運(yùn)行所需的云平臺(tái)由實(shí)驗(yàn)室5臺(tái)電腦組成，每臺(tái)電腦裝有3臺(tái)虛擬機(jī)，共15個(gè)節(jié)點(diǎn)。Hadoop分布式云計(jì)算集群中各點(diǎn)配置如下：Intel Core i7-2630CPU、3.1GHz、2048MB Memory，并采用Centos6.0操作系統(tǒng)、jdk-8u20-linux-i586版本的jdk、hadoop-1.1.2版本的Hadoop。其中一個(gè)作為Master節(jié)點(diǎn)，其余作為Slave節(jié)點(diǎn)。

實(shí)驗(yàn)樣本仿真于淘寶用戶購(gòu)買(mǎi)商品類別記錄，設(shè)商品種類為8種（服飾、學(xué)習(xí)用品、廚房用品等），每個(gè)樣本有8個(gè)屬性，每個(gè)屬性值為購(gòu)買(mǎi)某類商品的數(shù)量。分別生成106（數(shù)據(jù)大小為20M）、107（數(shù)據(jù)大小為200M）和108（數(shù)據(jù)大小為2000M）個(gè)樣本構(gòu)造成數(shù)據(jù)集，現(xiàn)將用戶分為7類（初級(jí)主婦，在校學(xué)生，高級(jí)廚神等），即聚類數(shù)K設(shè)置為7。本實(shí)驗(yàn)主要內(nèi)容為：比較K-均值聚類算法在相同硬件環(huán)境支持下單機(jī)運(yùn)行時(shí)間，與在Hadoop不同數(shù)量節(jié)點(diǎn)集群上運(yùn)行時(shí)間的長(zhǎng)短、加速比。實(shí)驗(yàn)結(jié)果如圖4所示。

由圖3（a）可看出，單機(jī)運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)少于并行運(yùn)行的時(shí)間，這歸因于以下兩個(gè)方面：

（1）MapReduce類庫(kù)將文件分為大小為64M得塊，由于該數(shù)據(jù)量小于64M，所以無(wú)需分割，每個(gè)Mapper節(jié)點(diǎn)可運(yùn)行兩個(gè)Mapper任務(wù)，在此只需執(zhí)行一個(gè)Mapper任務(wù)，所以直接分給一個(gè)Mapper節(jié)點(diǎn)運(yùn)行，節(jié)點(diǎn)數(shù)的增加與否并不影響執(zhí)行時(shí)間。

（2）單機(jī)環(huán)境下運(yùn)行小規(guī)模數(shù)據(jù)集時(shí)較為靈活，而初始MapReduce任務(wù)需要耗費(fèi)一定的時(shí)間，因此單機(jī)比并行所花費(fèi)的時(shí)間少。由此可得出結(jié)論，處理小規(guī)模的數(shù)據(jù)不適合將其在MapReduce框架中并行計(jì)算。

由圖3（b）可看出，隨著數(shù)據(jù)量的增大，并行計(jì)算的優(yōu)勢(shì)慢慢顯露出來(lái)，200M會(huì)分為4個(gè)分片，因此需要兩個(gè)節(jié)點(diǎn)來(lái)進(jìn)行并行計(jì)算。節(jié)點(diǎn)數(shù)在增加到2時(shí)，加速比有了明顯的提高。節(jié)點(diǎn)數(shù)大于2后，計(jì)算節(jié)點(diǎn)數(shù)的增加對(duì)執(zhí)行時(shí)間已無(wú)影響。

由圖3（c）可以看出，當(dāng)數(shù)據(jù)規(guī)模足夠大時(shí)，運(yùn)行時(shí)間隨著集群中節(jié)點(diǎn)數(shù)目的增加在不斷減少，這里數(shù)據(jù)大小為2000M，可分為32個(gè)分片，也就是說(shuō)當(dāng)節(jié)點(diǎn)數(shù)達(dá)到16個(gè)時(shí)，運(yùn)行時(shí)間最短。

比較得出，當(dāng)數(shù)據(jù)量較小時(shí)，使用云計(jì)算平臺(tái)執(zhí)行任務(wù)沒(méi)有單機(jī)環(huán)境下執(zhí)行效率高，當(dāng)數(shù)據(jù)規(guī)模足夠大時(shí)，并且每一個(gè)數(shù)據(jù)分片都在進(jìn)行處理工作時(shí)，集群的效率最高。

由實(shí)驗(yàn)可得出結(jié)論，將算法改造為MapReduce模型算法后，運(yùn)行結(jié)果與理論性能相符合，降低了CPU的工作量，提高了處理數(shù)據(jù)效率，降低了對(duì)大數(shù)據(jù)的聚集工作復(fù)雜度。

4 結(jié)論與展望

本文首先介紹了當(dāng)前處理大數(shù)據(jù)的重要性，為了提高大規(guī)模數(shù)據(jù)處理效率，提出了解決該問(wèn)題的思路，即對(duì)傳統(tǒng)算法進(jìn)行MapReduce編程框架的實(shí)現(xiàn)，本文將K-均值算法應(yīng)用于MapReduce編程模型中，并用實(shí)驗(yàn)驗(yàn)證該方法的可行性。當(dāng)數(shù)據(jù)量較小時(shí)，單機(jī)處理相對(duì)比較簡(jiǎn)單快捷，但數(shù)據(jù)量較大時(shí)，用此方法可以提高運(yùn)行效率，節(jié)省運(yùn)行時(shí)間。

圖3 K-均值聚類算法在不同數(shù)量級(jí)的樣本運(yùn)行時(shí)間及加速比

將算法并行運(yùn)行于Hadoop集群中雖然提高的執(zhí)行效率，但仍然存在一些問(wèn)題需要改進(jìn)。首先，K-均值算法需要反復(fù)迭代，對(duì)于大規(guī)模數(shù)據(jù)而言，每一次迭代都要花費(fèi)很長(zhǎng)時(shí)間，如何控制迭代次數(shù)需要好好研究。其次，在分布式計(jì)算中，根據(jù)特定樣本，如何選取初始聚類中心也是一個(gè)很關(guān)鍵的問(wèn)題，這將直接影響運(yùn)行的效率與結(jié)果的準(zhǔn)確性，需要在未來(lái)進(jìn)一步研究，加以完善。

［1］李國(guó)杰，程學(xué)旗.大數(shù)據(jù)研究：未來(lái)科技及經(jīng)濟(jì)社會(huì)發(fā)展的重大戰(zhàn)略領(lǐng)域——大數(shù)據(jù)的研究現(xiàn)狀與科學(xué)思考［J］.中國(guó)科學(xué)院院刊，2012，27（6）：647-657.

［2］覃雄派，王會(huì)舉，杜小勇，等.大數(shù)據(jù)分析——RDBMS與 MapReduce的競(jìng)爭(zhēng)與共生［J］.軟件學(xué)報(bào)，2012，23（1）：32-45.

［3］劉義，景寧，陳犖，等.MapReduce框架下基于R-樹(shù)的k-近鄰連接算法［J］.軟件學(xué)報(bào)，2013，24（8）：1836-1851.

［4］顧榮，王芳芳，袁春風(fēng)，等.YARM：基于 MapReduce的高效可擴(kuò)展的語(yǔ)義推理引擎［J］.計(jì)算機(jī)學(xué)報(bào)，2014，37（24）：1-13.

［5］饒君，吳斌，東昱曉.MapReduce環(huán)境下的并行復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)［J］.軟件學(xué)報(bào)，2012，23（12）：3175-3186.

［6］Zhang Shufen，Yan Hongcan，Chen Xuebin.Proceedings of 2010 International Conference on Future Information Technology and Computing（FITC 2010）［C］.Beijing University，Intelligent Information Technology Application Research Association，Beijing，2010.

［7］呂奕清，林錦賢.基于MPI的并行PSO混合K均值聚類算法［J］.計(jì)算機(jī)應(yīng)用，2011，31（2）：428-431+437.

［8］張軍偉，王念濱，黃少濱，等.二分K均值聚類算法優(yōu)化及并行化研究［J］.計(jì)算機(jī)工程，2011，37（17）：23-25.

［9］陶冶，曾志勇，余建坤，等.并行k均值聚類算法的完備性證明與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程，2010，36（22）：72-74.

［10］Polo J，Carrera D，Becerra Y，et al.Performance-Driven task co-scheduling for MapReduce environments［J］//Network Operationsand Management Symposium（NOMS）：IEEE，2010：373-380.

［11］Bing Liu.Web數(shù)據(jù)挖掘［M］.北京：清華大學(xué)出版社，2012：89-91.