基于MapReduce的網(wǎng)格化優(yōu)化CURE算法的實現(xiàn)

郎福通，王 鵬

(成都信息工程學院軟件工程學院，四川成都610255)

0 引言

隨著大數(shù)據(jù)時代的來臨，如何更加高效、準確地劃分數(shù)據(jù)，已成為聚類研究的一大熱點。面對日益增長的海量信息數(shù)據(jù)，現(xiàn)有的聚類算法在伸縮性和擴展性方面存在著一定的局限性。而分布式聚類算法由于能夠充分利用集群伸縮性和擴展性，因此能很好地解決這一問題，已成為當前聚類算法研究的重點之一[1]。目前，在已存在的分布式聚類算法的研究中，基于層次聚類[2]的CURE(Clustering Using Representative)算法[3]相較于基于劃分聚類的K-means算法[4]，具有處理任意形狀的數(shù)據(jù)分布的優(yōu)勢;相較于基于密度聚類的DBSCAN算法[5]以及利用動態(tài)模型的CHAMELEO算法[6]和基于小波變換的WaveCluster算法[7]具有算法實現(xiàn)簡單，可聚類任意形狀的族分布等優(yōu)點。因此CURE算法的并行化研究也成為分布式聚類算法研究的一大熱點[8]。

CURE算法通常采用隨機抽樣和劃分的方法來處理大數(shù)據(jù)集。而大數(shù)據(jù)時代的數(shù)據(jù)集具有數(shù)據(jù)體量大，價值密度低和要求響應(yīng)時間快等特點，通過少量的數(shù)據(jù)抽樣可能無法滿足大數(shù)據(jù)要求獲得較準確聚類結(jié)果的需求，采樣更多數(shù)據(jù)或全部數(shù)據(jù)來提高聚類效果的準確度，卻需要處理大量的數(shù)據(jù)。針對該問題，借用網(wǎng)格聚類思想[9]和MapReduce計算框架[10]，提出Grid-CURE分布式聚類算法。該算法首先對數(shù)據(jù)集進行快速網(wǎng)格聚類處理。然后采用MapReduce并行框架對CURE算法進行并行擴展，使算法能夠充分利用集群的計算和存儲能力，以加速算法的聚類過程。

1 背景

1.1 CURE 算法

CURE算法是層次聚類算法的一種，通常使用隨機抽樣與劃分的方法處理大數(shù)據(jù)集，在質(zhì)心和周圍的異常點之間的區(qū)域進行聚類。通常情況下，選擇c個較分散點代表一個類，并通過收縮因子向類的質(zhì)心收縮，收縮之后的分散點就代表了這個類的形狀。然后，CURE算法將合并最相近的類對，并將降低異常點對聚類的影響[11－12]。CURE算法的步驟:

(1)從源數(shù)據(jù)集中抽取一個隨機樣本S。

(2)將樣本S分割為一組劃分。

(3)對每個劃分局部的聚類。

(4)通過隨機取樣剔除孤立點。如果一個類增長太慢，就去掉它。

(5)對局部的簇進行聚類。

(6)用相應(yīng)的簇標簽標記數(shù)據(jù)。

1.2 Grid Cluster 和 MapReduce

Grid Cluster(網(wǎng)格聚類)網(wǎng)格聚類是多種聚類方法[13]中的一種，是將數(shù)據(jù)空間劃分為網(wǎng)格單元，聚類過程在網(wǎng)格上進行;當網(wǎng)格足夠小時，落入到同一個網(wǎng)格中的數(shù)據(jù)點是相似的，應(yīng)屬于同一個聚類。若一個網(wǎng)格單元中數(shù)據(jù)對象的個數(shù)大于給定的密度閾值，則認為其是高密度單元;否則視其為低密度單元，通常視低密度單元中的數(shù)據(jù)對象為孤立點或噪聲數(shù)據(jù)將其丟棄。該算法的處理時間僅依賴于量化空間中每一維上的單元數(shù)目而獨立于對象數(shù)目，具有聚類速度快且能發(fā)現(xiàn)任意形狀、大小的類的優(yōu)點[14]。

MapReduce是一種并行編程模型，用以大規(guī)模數(shù)據(jù)集的計算。其主要采用了分而治之的思想，把大的問題分割為一個個小的問題并行處理[15]。模型中兩項任務(wù)Map和Reduce，Map用來把一組鍵/值對映射成一個新的鍵值對，Reduce對Map輸出結(jié)果進行規(guī)約處理，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。

2 Grid-CURE算法介紹

Grid-CURE算法是一種優(yōu)化的CURE算法。核心思想為:針對某一數(shù)據(jù)集，將數(shù)據(jù)對象空間量化為有限數(shù)目的網(wǎng)格單元，根據(jù)單元格內(nèi)數(shù)據(jù)對象的個數(shù)對原始數(shù)據(jù)集進行初始化聚類;通過MapReduce框架把初始化的類數(shù)據(jù)分割到一個個數(shù)據(jù)塊中，再將數(shù)據(jù)塊分發(fā)到集群中各個數(shù)據(jù)節(jié)點上，并行地計算出每個類與其最近的類之間的距離，Reduce階段凝聚兩者之間距離最短的類對。改進的算法總的來說可分為兩個階段:第一階段借用網(wǎng)格聚類算法的思想，利用MapReduce框架對原始數(shù)據(jù)集進行Grid Cluster預處理;第二階段采用MapReduce框架來實現(xiàn)CURE算法的并行性擴展，擴展后的算法聚類過程將在Map與Reduce階段通過合并距離最相近的類對完成。

2.1 Grid Cluster預處理階段

根據(jù)數(shù)據(jù)集中包含數(shù)據(jù)對象的個數(shù)n和數(shù)據(jù)對象擁有屬性的個數(shù)r，定義數(shù)據(jù)集O={o1，o2，…，on}，數(shù)據(jù)對象的維度空間A={A1，A2，…，Ar}。將A的每一維進行M等分，則可將A分割為Mr個網(wǎng)格單元。通過MapReduce計算框架，將原始數(shù)據(jù)集中的對象在Map階段映射到對應(yīng)的網(wǎng)格單元內(nèi)，在Reduce階段依據(jù)每個單元格內(nèi)的數(shù)據(jù)對象的數(shù)目進行相應(yīng)的初始化聚類處理。分析上面的處理過程:將數(shù)據(jù)集中對象映射到對應(yīng)的網(wǎng)格單元內(nèi)的操作與其他數(shù)據(jù)對象是無關(guān)聯(lián)的;依據(jù)網(wǎng)格單元內(nèi)的數(shù)據(jù)對象數(shù)目進行初始化聚類的處理亦與其他單元格無關(guān)，因此使用MapReduce框架的Map和Reduce操作完成數(shù)據(jù)集的初始化聚類是可行的。首先，通過MapReduce框架把存儲在文件中的數(shù)據(jù)集分割為一個個等同大小的數(shù)據(jù)塊，并把數(shù)據(jù)塊分發(fā)到各個datanode數(shù)據(jù)節(jié)點上。其次，啟動各個datanode上的Map任務(wù)，把該節(jié)點上數(shù)據(jù)塊中的數(shù)據(jù)對象映射到對應(yīng)的網(wǎng)格單元中，并把單元格ID和數(shù)據(jù)對象分別作為Map任務(wù)的key和value輸出，以作為Reduce階段的輸入。然后，在Map任務(wù)完成后，啟動Reduce任務(wù)，把key值相同的value視為同一單元格中value，統(tǒng)計同一單元格中value對象的數(shù)目確定該單元格的類型(稀疏單元格，均勻單元格和密集單元格)，根據(jù)單元格的類型進行不同處理:對稀疏單元格中數(shù)據(jù)進行刪除處理;對均勻單元格中每個數(shù)據(jù)分別初始化為一個類處理;對密集單元格中全部數(shù)據(jù)初始化為一個類處理。接著，只把各個類的中心點和代表點作為該類的標識存入HDFS上特征類文件中。最后，將類的標識(中心點和代表點)和類中的對象分別作為Reduce任務(wù)的key和value輸出。

2.2 MapReduce并行化擴展CURE算法處理階段

CURE算法聚類過程概括來說核心操作有3部分:計算距離最短的類對;合并距離最短的類對;判斷聚類是否結(jié)束。分析這些操作過程發(fā)現(xiàn):類之間最短距離的計算與計算順序無關(guān)且與類中的數(shù)據(jù)對象無關(guān);合并最短距離的類對是在計算簇間最短距離之后且其他類無需合并;判斷聚類是否結(jié)束，可作為主程序的迭代執(zhí)行1和2的終止條件。因此，CURE算法是可以采用MapReduce框架進行并行性擴展的。詳細處理步驟如下:首先，通過MapReduce框架把上階段產(chǎn)生的初始聚類結(jié)果數(shù)據(jù)集分割為等同大小的數(shù)據(jù)塊，并分發(fā)到各個datanode上。其次，啟動Map任務(wù)讀取HDFS上特征類文件，得到所有類的標識存入list列表中，計算節(jié)點上的類與list中除該類外的類之間的距離，距離的計算可，而距離的計算方法可以采用歐幾里德距離、曼哈頓距離或拉格朗日距離等，兩個類M、N之間的距離定義如(1)式所示的形式，其中p和q分別為屬于M和N的代表點，把計算結(jié)果最短距離和該類的標識(代表點和均值)分別作為Map任務(wù)的key和value輸出。然后，在Map任務(wù)結(jié)束后，啟動Reduce任務(wù)，選取最小key值對應(yīng)的一對value(兩者之間距離值為key的類對)合并，其余value不處理，因此只需一個Reduce任務(wù)。接著，只把各個類的標識存入HDFS上特征類文件，并把類標識和類分別作為Reduce的key和value輸出。最后，主程序讀取HDFS上特征類文件獲取類個數(shù)R，比較R與實際類個數(shù)K的大小，以判斷聚類是否結(jié)束。未結(jié)束則刪除增長過慢的類，否則迭代上面操作。

Grid-CURE算法的框架流程圖如圖1所示。描述如下:

(1)啟動第一階段Map-Reduce迭代任務(wù)，通過MapReduce框架讀取數(shù)據(jù)集，并把數(shù)據(jù)分割為一個個等同大小的數(shù)據(jù)塊，分發(fā)到各個數(shù)據(jù)節(jié)點上。

(2)利用MapReduce框架的Map操作，將數(shù)據(jù)節(jié)點上的數(shù)據(jù)映射到對應(yīng)網(wǎng)格單元內(nèi)。

(3)利用MapReduce框架的Reduce操作，刪除稀疏網(wǎng)格單元的數(shù)據(jù)，將均勻網(wǎng)格中每個數(shù)據(jù)對象初始化為一個類，將稠密網(wǎng)格單元中所有數(shù)據(jù)初始化為一個類。

(4)啟動第二階段Map-Reduce迭代任務(wù)，主程序判斷聚類是否結(jié)束，若是則輸出聚類結(jié)果數(shù)據(jù)并結(jié)束程序;否則，刪除出生長過慢的類，然后執(zhí)行步驟5。

(5)利用MapReduce框架的Map操作，計算出數(shù)據(jù)節(jié)點上的類與其他所有類之間的最短距離dist，并將dist和該類的標識(中心點和代表點)作為Map任務(wù)的輸出。

(6)利用MapReduce框架的Reduce操作，只合并最小key鍵對應(yīng)的value對，將合并得到的新類和其他的類的標識存儲到HDFS上特征類文件中，最后把這些類的標識和這些類輸出，然后執(zhí)行步驟4。

圖1 Grid-CURE算法框架流程圖

3 實驗及結(jié)果分析

3.1 實驗環(huán)境

實驗實施在由Apache開源項目Hadoop[16]搭建的集群上。實驗硬件環(huán)境:6個服務(wù)器節(jié)點，每個節(jié)點的配置均為:Cpu IntelR○CoreTMi3-2100 3.10GHz，內(nèi)存4G，硬盤為500G;軟件環(huán)境:每個節(jié)點均為CeontOS Linux6.3操作系統(tǒng)，Hadoop 版本為0.20.2，Java 開發(fā)工具包為 JDK1.6－0－27 版本，程序開發(fā)工具為 MyEclipse10.0，算法全部由Java語言實現(xiàn)。

3.2 實驗數(shù)據(jù)集

實驗數(shù)據(jù)選取兩組數(shù)據(jù)集，第一組來源于聯(lián)合程序開發(fā)網(wǎng)站的測試數(shù)據(jù)集[18]，包含10000個二維數(shù)據(jù)的點，聚類個數(shù)為3;第二組來源于Matlab生成的人工數(shù)據(jù)集，包含20000個二維數(shù)據(jù)點，聚類個數(shù)為3。使用兩組數(shù)據(jù)集測試CURE算法和Grid-CURE算法處理數(shù)據(jù)的效率。

3.3 實驗

為驗證MapReduce框架和網(wǎng)格化聚類預處理能夠解決CURE算法的效率問題，將使用以上兩組數(shù)據(jù)集(不使用隨機抽樣與劃分)測試CURE算法和Grid-CURE算法的執(zhí)行效率，并在不同規(guī)模的Hadoop集群上運行Grid-CURE算法，測試集群的規(guī)模大小對Grid-CURE算法的影響。因為實驗數(shù)據(jù)集為平面二維數(shù)據(jù)，因此聚類距離選擇歐幾里德距離進行計算。實驗結(jié)果如下:

圖2顯示了隨著集群規(guī)模動態(tài)變化Grid-CURE算法運行的時間的狀況。可以看到:隨著集群規(guī)模的增加，Grid-CURE算法的運行時間逐漸縮短，但運行時間的縮短速率逐漸降低;Grid-CURE算法處理第二組數(shù)據(jù)集的時間要短與處理第一組數(shù)據(jù)集的時間。

分析原因:(1)隨著集群規(guī)模的增長，更多計算資源和存儲等資源被放入hadoop平臺資源池中，集群計算能力和存儲能力也變得更強，Grid-CURE算法通過MapReduce框架充分利用集群的計算和存儲能力，使其處理數(shù)據(jù)的能力也得以加強。但隨著集群規(guī)模的增加，集群中任務(wù)的調(diào)度會把任務(wù)分配到更多的集群節(jié)點上，節(jié)點間的通信時間消耗也會以指數(shù)形式增加，所以隨集群規(guī)模的增長計算力對算法處理速度的優(yōu)化會變得越來越弱，因此節(jié)點數(shù)目有個最優(yōu)配置。(2)雖然第二組數(shù)據(jù)集的規(guī)模要大于第一組數(shù)據(jù)集，但其數(shù)據(jù)分布圖4(a)類似3個環(huán)型，數(shù)據(jù)分布呈現(xiàn)密集集中的特征。使用Grid-CURE算法處理符合該特征分布的數(shù)據(jù)集，可充分發(fā)揮該算法的網(wǎng)格化預處理優(yōu)勢:篩選掉稀疏網(wǎng)格中的數(shù)據(jù)，凝聚稠密網(wǎng)格中的數(shù)據(jù)，以加速算法的處理效率。

在單臺服務(wù)器節(jié)點上使用CURE算法分別處理兩組數(shù)據(jù)集，運行結(jié)果顯示:處理第一組數(shù)據(jù)需大約4.3×106毫秒，處理第二組數(shù)據(jù)需大約5.8×107毫秒。結(jié)合圖2進行分析可以發(fā)現(xiàn):CURE算法處理第二組數(shù)據(jù)集消耗時間遠比第一組數(shù)據(jù)集長。處理第一組數(shù)據(jù)集，4節(jié)點上運行的Grid-Crue算法比CURE算法高效的多，而單節(jié)點上運行的Grid-CURE算法與CURE算法效率相似。

分析原因:(1)CURE算法的時間復雜度為O(n2logn)[17]，伴隨數(shù)據(jù)量的增長，運行時間成指數(shù)增長。(2)啟動MapReduce框架需要消耗掉一些時間，但Grid-Crue算法有一步數(shù)據(jù)集網(wǎng)格預聚類處理步驟，提升算法的執(zhí)行效率，所以單節(jié)點上Grid-CURE算法和CURE算法效率相似。隨著節(jié)點數(shù)目的增多，Grid-CURE充分利用MapReduce框架的并行處理計算能力，大大降低了算法的運行時間，所以比CURE效率高。

圖2 Grid-CURE算法運行時間圖

圖3 第一組數(shù)據(jù)實驗結(jié)果圖

圖4 第二組數(shù)據(jù)實驗結(jié)果圖

圖3(a)為第一組數(shù)據(jù)的二維平面圖。圖3(b)和圖3(c)分別為使用第一組測試數(shù)據(jù)運行CURE算法和Grid-CURE算法產(chǎn)生的結(jié)果圖。由圖3(b)和3(c)中星射線的外緣點為類的代表點，星射線的中心點為類的均值，而中心點和代表點周圍的點為該類中的數(shù)據(jù)點，從圖3(b)和3(c)可以看出聚類結(jié)果為3個類。亦可看到使用Grid-CURE算法處理后的類中數(shù)據(jù)點比較密集，噪聲點比較少。原因為Grid-CURE算法對數(shù)據(jù)集進行了網(wǎng)格化預聚類處理，把網(wǎng)格密度較低的數(shù)據(jù)點剔除掉了，降低了噪聲點對聚類結(jié)果的影響。圖4(a)為第二組數(shù)據(jù)的二維平面圖。圖4(b)和圖4(c)分別為使用第一組測試數(shù)據(jù)運行CURE算法和Grid-CURE算法產(chǎn)生的聚類結(jié)果圖。觀察圖4(b)和圖4(c)與圖3(b)和3(c)顯示出同樣的結(jié)果:Grid-CURE算法產(chǎn)生的簇中數(shù)據(jù)點較密集并且噪聲點較少。

通過以上分析，可以得出Grid-CURE具有較好聚類效率和較強的抗噪聲能力結(jié)論。

4 結(jié)束語

為解決海量數(shù)據(jù)的聚類效率問題，基于原CURE聚類算法做了一些改進:對原始數(shù)據(jù)進行了網(wǎng)格化聚類的處理，剔除一些孤立點同時合并一些密集區(qū)的點;使用MapReduce框架對CURE算法進行了并行化擴展，同時在多個節(jié)點上計算類之間距離最短的類對。通過對原始數(shù)據(jù)集進行網(wǎng)格化聚類處理，加速了算法的聚類速度并提高了算法的抗噪聲能力，采用MapReuce框架對CURE算法并行化擴展，同時在多個節(jié)點計算類之間距離最短的類對，提升了算法的處理效率。在構(gòu)造的實驗環(huán)境下，通過不斷的試驗與對算法的改進，使算法的聚類效率得到了大幅度提升，初步證明Grid-CURE算法在集群環(huán)境下具有較高的聚類效率和抗噪聲能力。方法適用于大規(guī)模數(shù)據(jù)集的處理，如根據(jù)網(wǎng)絡(luò)日志數(shù)據(jù)劃分不同的興趣用戶群。

[1] 李應(yīng)安.基于MapReduce的聚類算法的并行化研究[D].廣州:中山大學，2010.

[2] Han Jiawei，Kamber M.Data mining:concepts and techniques[M].San Francisco:Morgan Kaufmann Publishers，2000.

[3] Guha S，Rastogi R，Shim K.CURE:An Efficient Clustering Algorithm for Large Database[C].In:Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data，Seattle，Washington，1998.73－84.

[4] 吳夙慧，成穎，鄭彥寧，等.k-means算法研究綜述[J].現(xiàn)代圖書情報技術(shù)，2011，(5):28－35.

[5] 馮少榮，肖文俊.DBSCNA的研究與改進[J].中國礦業(yè)大學學報，2008，37(1):105－111.

[6] Karypis G，Han E H，Kumar V.CHAMELEON:A hierarchical clustering algorithm using dynamic modeling[J].Computer，1999，(32):68－75.

[7] Sheikholeslami G，Chatterjee S，Zhang A.WaveCluster:A Multi-Resolution Clustering Approach for Very Large Spatial Databases[C].In:Proceedings of the 24th VLDB Conference.New York，USA:[s.n.]，1998:428－439.

[8] 毛典輝.基于MapReduce的Canopy-Kmeans改進算法[J].計算機工程與應(yīng)用，2012，48(27):22－27.

[9] 趙慧，劉希玉，崔海青.網(wǎng)格聚類算法.計算機技術(shù)與發(fā)展[J].2010，20(9):83－89.

[10] 李玉林，董晶.基于Hadoop的MapReduce模型的研究與改進[J].計算機工程與設(shè)計，2012，33(8):110－3117.

[11] 王民，尹超，王稚慧，等.Binary-Positive下的并行化CURE算法[J].計算機工程與應(yīng)用，2012，50(11):58－61.

[12] 魏桂英，鄭玄軒.層次聚類方法的CURE算法研究[J].科技和產(chǎn)業(yè)，2005，5(11):22－24.

[13] 賀玲，吳玲達，蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述[J].計算機應(yīng)用研究，2007(1):10－13.

[14] 張真，周志強.數(shù)據(jù)挖掘中網(wǎng)格聚類算法研究[J].科技信息，2010，25:20－21.

[15] 李建江，崔健，王聃，等.MapReduce并行編程模型研究綜述[J].電子學報，2011，(11):2635－2642.

[16] White T.Hadoop權(quán)威指南[M].曾大聃，周傲英，譯.北京:清華大學出版社，2010:68.

[17] adrian.聚類的測試數(shù)據(jù)集[DB/OL].http://www.pudn.com/downloads78/sourcecode/math/detail297600.html，2014－05－10.

[18] 董健康.數(shù)據(jù)挖掘中CURE聚類算法研究[J].電腦與電信，2007，(4):14－15.