聚類分析的并行化實(shí)現(xiàn)技術(shù)研究

齊 浩， 馬 力

（1.西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121；2.西安郵電大學(xué) 數(shù)字藝術(shù)學(xué)院，陜西 西安 710061）

根據(jù)美國風(fēng)險(xiǎn)基金KPCB（kleiner perkins caufield&byers）在2013年的《互聯(lián)網(wǎng)趨勢報(bào)告》中的統(tǒng)計(jì)和預(yù)測，互聯(lián)網(wǎng)上的數(shù)據(jù)在過去五年間增長了9倍，在過去的8年中（2005-2013），數(shù)據(jù)量幾乎嚴(yán)格按照摩爾定律預(yù)測的速度在不停的增長。2013年的全網(wǎng)數(shù)據(jù)量（包括文件、圖片、視頻等）將達(dá)到4 ZB。在數(shù)據(jù)量急劇爆發(fā)的同時(shí)，如何能更高效、更深入地利用這些數(shù)據(jù)，是數(shù)據(jù)挖掘技術(shù)所面臨的新一輪挑戰(zhàn)。由此也產(chǎn)生了許多并行編程語言及模型，如PARLOG及信息傳遞接口（Message Passing Interface，MPI）等，但這些方法并不能將一個(gè)特定的算法顯式的表現(xiàn)出來。當(dāng)前大部分的研究是對某個(gè)特定的傳統(tǒng)算法的發(fā)展和優(yōu)化，這些技術(shù)已遠(yuǎn)遠(yuǎn)不能滿足現(xiàn)實(shí)的數(shù)據(jù)挖掘要求及分布式技術(shù)的發(fā)展。2007年，Chu C等人提出了在多核處理器的計(jì)算機(jī)上實(shí)現(xiàn)部分?jǐn)?shù)據(jù)挖掘算法的方法[1]，為分布式系統(tǒng)中的數(shù)據(jù)挖掘奠定了基礎(chǔ)。隨著分布式技術(shù)的不斷發(fā)展、網(wǎng)絡(luò)數(shù)據(jù)量爆發(fā)式的增長，如何更好地利用分布式系統(tǒng)進(jìn)行數(shù)據(jù)挖掘成了人們迫切的現(xiàn)實(shí)需求。

1 分布式編程模型MapReduce

MapReduce是在2004年由Google的Jeffrey Dean和Sanjay Ghemawat提出的一種分布式編程模型[2]，起初的目標(biāo)是用于大于1TB的大規(guī)模數(shù)據(jù)集的計(jì)算。MapReduce解決了在分布式集群中進(jìn)行并行計(jì)算、分發(fā)數(shù)據(jù)、處理失效的問題時(shí)所遇到的種種復(fù)雜問題。它將并行、容錯(cuò)、數(shù)據(jù)分布和負(fù)載均衡等散亂的細(xì)節(jié)包含在一個(gè)庫里面，從而使程序員將注意力可以集中在如何表達(dá)所要執(zhí)行的運(yùn)算中，而無需考慮到運(yùn)算過程中所涉及的每個(gè)細(xì)節(jié)。

MapReduce使用Map和Reduce兩個(gè)函數(shù)來表達(dá)整個(gè)計(jì)算過程。

首先將用戶將數(shù)據(jù)源中的記錄 （如數(shù)據(jù)庫中的某條記錄）轉(zhuǎn)為鍵值對的形式，提交給自定義的Map函數(shù)，產(chǎn)生一組或多組中間鍵值對。然后再把所有擁有相同鍵的中間鍵值對匯總，產(chǎn)生中間鍵值對列表，結(jié)束Map作業(yè)，返回。

在Map作業(yè)執(zhí)行完畢之后，Reduce函數(shù)利用Map的輸出作為輸入，把列表中鍵值對的value值合并在一起，構(gòu)造一個(gè)擁有更小value值的集合。一般情況下，每次調(diào)用Reduce函數(shù)會輸出零或一個(gè)value值。中間value值通過一個(gè)迭代器提供給用戶的Reduce函數(shù)，以避免因太大而無法適應(yīng)內(nèi)存的value值列表的出現(xiàn)。

在分布式架構(gòu)中，Map函數(shù)從不同的數(shù)據(jù)源中讀取不同的輸入，并創(chuàng)建不同的中間值。Reduce函數(shù)同樣可以并行執(zhí)行，而每個(gè)Reduce作業(yè)僅接收key值相同的中間值對，換言之，每個(gè)Reduce作業(yè)所接收的key值都是不同的。根據(jù)MapReduce的分布式工作原理可以看出，每個(gè)數(shù)據(jù)源中的數(shù)據(jù)均是獨(dú)立處理的[3]。（圖1）

圖1 MapReduce的工作原理Fig.1 Working principle of MapReduce

2 傳統(tǒng)聚類算法的MapReduce并行化

聚類是數(shù)據(jù)挖掘中的重要組成部分，它是將數(shù)據(jù)對象根據(jù)事先未知的特征分成多個(gè)類或簇的過程，其特征是在同一個(gè)簇中的數(shù)據(jù)有著較高的相似度，而不在同一個(gè)簇中的數(shù)據(jù)對象有著明顯的差異[4]。通常根據(jù)距離來判斷數(shù)據(jù)對象的相似度。在30多年的發(fā)展中已經(jīng)提出了許多種聚類算法。

2.1 K-means算法

K－means算法是最著名及最常用的基于劃分的方法之一，也是最早被學(xué)者進(jìn)行并行化研究算法之一[5]。它需要預(yù)先輸入?yún)?shù)k，將n個(gè)對象劃分為k個(gè)簇，簇內(nèi)的任意對象之間相似度高，而位于不同簇中的對象有著較低的相似度。相似度根據(jù)簇內(nèi)所有對象的均值度量，可以看作簇的質(zhì)心。其算法流程如下：

1）在數(shù)據(jù)樣本中隨機(jī)選取k個(gè)點(diǎn)作為聚類中心點(diǎn)；

2）對待聚類的點(diǎn)進(jìn)行遍歷，找到距離各自最近的中心點(diǎn)，并加入到該簇中，產(chǎn)生一個(gè)初始的聚類結(jié)果，完成第一次迭代過程；

3）每個(gè)簇重新計(jì)算距離的均值，并將這個(gè)均值作為新的聚類中心；

4）重復(fù)進(jìn)行步驟2）3），直到聚類結(jié)果趨于收斂。

利用MapReduce實(shí)現(xiàn)K－means算法時(shí)，Map函數(shù)將每個(gè)待聚類的點(diǎn)分配給最接近的聚類中心點(diǎn)，Reduce函數(shù)負(fù)責(zé)將更新新的聚類中心點(diǎn)。

Map函數(shù)的輸入是來自數(shù)據(jù)源中的鍵值對，每一個(gè)鍵值對代表數(shù)據(jù)源中的一條記錄。其中的鍵表示當(dāng)前數(shù)據(jù)片距離數(shù)據(jù)起始點(diǎn)的位置偏移，其值為當(dāng)前數(shù)據(jù)片中所包含的字符串。此時(shí)，整個(gè)數(shù)據(jù)集已被分割成M片，同時(shí)提交給M個(gè)Map任務(wù)，從而進(jìn)行并行的距離計(jì)算。對于每個(gè)Map任務(wù)，分布式K－means算法會將簇的ID作為鍵，將計(jì)算得出的聚類中心及包含的樣本數(shù)量作為值，保存到中間鍵值對中，提交給Reduce函數(shù)。

在Map過程中會產(chǎn)生大量的數(shù)據(jù)，中間數(shù)據(jù)被存儲在各節(jié)點(diǎn)主機(jī)的本地磁盤，可以節(jié)約網(wǎng)絡(luò)通信成本。Reduce函數(shù)將對各個(gè)Combine函數(shù)的輸出值進(jìn)行計(jì)算，包括迭代次數(shù)、簇的ID、新的聚類中心、簇的大小、以及迭代是否可以繼續(xù)等信息。

2.2 PAM算法

PAM（Partitioning Around Medoids）算法，是一種基于中心點(diǎn)或中心對象進(jìn)行劃分的k中心點(diǎn)算法。是最早提出的k中心點(diǎn)算法之一。它首先在數(shù)據(jù)集中確定k個(gè)初始對象作為代表進(jìn)行聚類，找出每個(gè)簇中最好的對象的集合作為下次迭代中的的代表對象。n次迭代后，最終集合中的代表對象即為簇的代表中心點(diǎn)。其算法流程如下：

1）在數(shù)據(jù)集中隨機(jī)選擇k個(gè)對象作為初始中心點(diǎn)；

2）將數(shù)據(jù)集中的每個(gè)對象分配到距離它最近的中心點(diǎn)所構(gòu)成的簇中，形成k個(gè)簇；

3）重新計(jì)算每個(gè)簇的中心位置，選擇最靠近中心的對象作為新的中心點(diǎn)；

4）重復(fù) 2）、3）步，直至各簇不再變化，說明各簇已趨于穩(wěn)定。

利用MapReduce實(shí)現(xiàn)PAM算法時(shí)，Map函數(shù)為每個(gè)對象尋找最近的中心點(diǎn)，并將對象分配給對應(yīng)的簇，其輸入為<簇id，對象>，輸出為<新簇id，對象>。Reduce函數(shù)負(fù)責(zé)查找簇中的新的中心點(diǎn)，并將其制定為下次迭代中新的聚類中心，其輸入為<簇id，簇中所有對象>，輸出為<簇id，新的聚類中心>。

與K－means算法類似，每次迭代完成后都要啟動一個(gè)新的MapReduce任務(wù)，由Map來計(jì)算每個(gè)對象所屬的簇，而由Reduce找出每個(gè)簇的中心，直到簇中心點(diǎn)不再改變?yōu)橹埂?/p>

2.3 CLARA算法

CLARA（Clustering Large Application）算法是 k－中心點(diǎn)算法針對與大數(shù)據(jù)集合的一種變種，其思想是基于抽樣的，即不考慮整個(gè)數(shù)據(jù)集合，僅在部分抽樣中選取中心點(diǎn)。如果抽樣是以非常隨機(jī)的方式選取時(shí)，那么它對原有的數(shù)據(jù)集應(yīng)有較高的代表性。其算法流程如下：

1）從數(shù)據(jù)庫中隨機(jī)抽樣，調(diào)用PAM方法從抽樣中選取k個(gè)最優(yōu)中心點(diǎn)；

2）將k個(gè)中心點(diǎn)應(yīng)用在整個(gè)數(shù)據(jù)庫中，進(jìn)行聚類；

3）計(jì)算上一步中的聚類總代價(jià)，若該值小于當(dāng)前最小值，則替換當(dāng)前最小值，保留當(dāng)前聚類結(jié)果作為當(dāng)前最優(yōu)聚類結(jié)果；

4）循環(huán)執(zhí)行1）～3）步，直到聚類總代價(jià)小于預(yù)定最小值或達(dá)到預(yù)定迭代次數(shù)。

與K－means算法和PAM算法不同，在MapReduce中實(shí)現(xiàn)CLARA算法時(shí)，可以將算法步驟轉(zhuǎn)換為兩個(gè)MapReduce作業(yè)，同時(shí)執(zhí)行不同的任務(wù)。

第一個(gè)MapReduce作業(yè)是從數(shù)據(jù)源中隨機(jī)選取子集，分別用PAM進(jìn)行聚類，輸出結(jié)果，即聚類中心點(diǎn)k。在此作業(yè)中，Map函數(shù)對所有對象附加一個(gè)隨機(jī)的鍵random-key。Reduce函數(shù)僅讀取前n個(gè)對象，以random-key的升序進(jìn)行排列，由于random-key是隨機(jī)分配的，因此此時(shí)對象的排序是完全隨機(jī)的。對這n個(gè)對象執(zhí)行PAM聚類，找到k個(gè)不同的候選中心點(diǎn)。

第二個(gè)MapReduce作業(yè)是將k放在整個(gè)數(shù)據(jù)集中，對其進(jìn)行聚類質(zhì)量計(jì)算，并完成本次迭代。在此作業(yè)中，Map函數(shù)為每個(gè)對象找到其最接近的中心點(diǎn)，并計(jì)算相對距離，并產(chǎn)生一個(gè)輸出，以<候選集ID，距離列表>的形式傳遞給Reduce函數(shù)。在Reduce函數(shù)中，將候選集ID一樣的輸出結(jié)果相加，得到Reduce的輸出結(jié)果。即在一個(gè)候選集內(nèi)，每個(gè)對象到與最近的中心點(diǎn)的距離之和。最小的輸出結(jié)果所對應(yīng)的候選集便是最佳的聚類結(jié)果。

2.4 小結(jié)

以上3種算法中，K-means算法和PAM算法類似，都需要在每次迭代后重新從文件系統(tǒng)中讀取輸入數(shù)據(jù)，而每次迭代都啟動一個(gè)新的MapReduce作業(yè)，作業(yè)數(shù)量是隨著迭代次數(shù)的增加線性增長的。而CLARA算法中，執(zhí)行不同任務(wù)的MapReduce作業(yè)總是2個(gè)，因此CLARA算法能夠更好地適應(yīng)MapReduce框架。

同時(shí)，也有一些不適合MapReduce進(jìn)行分布式化的算法存在，如共軛梯度法等，這些算法的一個(gè)普遍特征是迭代復(fù)雜，每次迭代都需要執(zhí)行一個(gè)或者更多個(gè)MapReduce作業(yè)，當(dāng)?shù)螖?shù)增加時(shí)，需要調(diào)度的MapReduce任務(wù)也越來越多，造成了大量的時(shí)間開銷，而真正用于計(jì)算的時(shí)間卻相對較少。對此，Seo S等人對MapReduce進(jìn)行了優(yōu)化，提出了一種有效的解決辦法[6]。

3 實(shí)驗(yàn)分析

在本節(jié)中，我們將上述算法在MapReduce框架中進(jìn)行了實(shí)現(xiàn)，并對節(jié)點(diǎn)數(shù)量對算法性能的影響進(jìn)行了評估。由于各個(gè)算法本身所具有的性質(zhì)不同，因此對于同樣的數(shù)據(jù)集，其聚類速度和聚類結(jié)果有著固有的差異。在這里我們僅將數(shù)據(jù)集大小和節(jié)點(diǎn)數(shù)目作為變量，對各算法進(jìn)行縱向?qū)Ρ龋⒉魂P(guān)注各算法本身的性能差異。為驗(yàn)證節(jié)點(diǎn)數(shù)對算法性能的影響，我們對3個(gè)算法均使用500 KB，50 MB，1 GB的數(shù)據(jù)源在節(jié)點(diǎn)的數(shù)量從1到4的條件下進(jìn)行聚類。所有實(shí)驗(yàn)均在Hadoop平臺中進(jìn)行，使用的Hadoop版本為1.2.1，Java版本為6u33。

由以上實(shí)驗(yàn)結(jié)果可以看出，對于同一個(gè)數(shù)據(jù)集，隨著分布式系統(tǒng)中的節(jié)點(diǎn)數(shù)量的增加，對該數(shù)據(jù)集的聚類速度越快，但每增加一個(gè)節(jié)點(diǎn)所帶來的速度提升就越少。這是因?yàn)殡S著節(jié)點(diǎn)的增多，在網(wǎng)絡(luò)通信、任務(wù)調(diào)度上所帶來的開銷就越大。因此可以推定，增加k個(gè)節(jié)點(diǎn)最多只能提升k倍的效率，并且在k趨于某一臨界值時(shí)，效率提升趨于0。由圖2、圖3、圖4中可以看出，對于無論哪種算法，當(dāng)數(shù)據(jù)集越大時(shí)，節(jié)點(diǎn)增加所帶來的速度提升越明顯；同時(shí)，當(dāng)節(jié)點(diǎn)數(shù)目不變時(shí)，越大的數(shù)據(jù)集速度提升的越多。

圖2 K-means算法實(shí)驗(yàn)結(jié)果Fig.2 K-means algorithm results

圖3 PAM 算法實(shí)驗(yàn)結(jié)果Fig.3 PAM algorithm results

圖4 CLARA算法實(shí)驗(yàn)結(jié)果Fig.4 CLARA algorithm results

4 結(jié)束語

隨著云計(jì)算的快速發(fā)展以及人們對互聯(lián)網(wǎng)數(shù)據(jù)分析的迫切需要，使得分布式技術(shù)成為了數(shù)據(jù)挖掘的必備工具。本文介紹了當(dāng)下廣泛應(yīng)用的分布式計(jì)算模型MapReduce的工作原理，討論了3種傳統(tǒng)數(shù)據(jù)聚類算法的并行化實(shí)現(xiàn)原理，并分別進(jìn)行了實(shí)驗(yàn)分析，討論了影響算法并行效率的相關(guān)因素。后續(xù)我們將進(jìn)一步對更多的傳統(tǒng)聚類算法的分布化進(jìn)行實(shí)驗(yàn)，并對其算法復(fù)雜度的分析和優(yōu)化進(jìn)行更深入的研究。

[1]Chu C，Kim S K，Lin Y A，et al.Map-reduce for machine learning on multicore[J].Advances in neural information processing systems，2007（19）:281.

[2]Dean J，Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）:107-113.

[3]Gordon S.Linoff， MapReduce and K-Means Clustering，[EB/OL]，（2008-02-09）， [2014-3-5]http://blog.data-miners.com/2008/02/mapreduce-and-k-means-clustering.html.

[4]Jiawei H，Kamber M.數(shù)據(jù)挖掘：概念與技術(shù)[M].范明，孟小峰.北京：機(jī)械工業(yè)出版社，2001.

[5]Zhao W，Ma H，He Q.Parallel k-means clustering based on mapreduce[C]//Cloud Computing.Springer Berlin Heidelberg，2009:674-679.

[6]Seo S，Yoon E J，Kim J，et al.Hama:An efficient matrix computation with the mapreduce framework[C]//Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on.IEEE，2010:721-726.