雙MapReduce改進(jìn)的Canopy-Kmeans算法

劉寶龍，蘇 金

(西安工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，西安 710021)

?

雙MapReduce改進(jìn)的Canopy-Kmeans算法

劉寶龍，蘇 金

(西安工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，西安 710021)

由于傳統(tǒng)的Canopy-Kmeans算法在中心點的選取存在隨機(jī)性，其迭代過程的冗余計算降低了算法的運行效率.文中基于“最小最大原則”和三角不等式原理，在Hadoop平臺上提出了一種基于雙MapReduce改進(jìn)的Canopy-Kmeans算法.實驗結(jié)果表明：設(shè)計的并行算法精確率在不同大小的數(shù)據(jù)集上平均提高了15.3%，加速比和擴(kuò)展性隨著數(shù)據(jù)規(guī)模和節(jié)點的不斷增加也相應(yīng)的提高了1.5～3倍，解決了Canopy中心點選中存在的問題和迭代過程中冗余的距離計算.

Canopy-Kmeans；冗余計算；Hadoop平臺；雙MapReduce

常用的K-means算法是一種基于劃分的聚類挖掘算法，該算法的思路簡單、收斂速度快，使用廣泛且易于實現(xiàn)，但在K值及中心點的選取上仍然存在很大的隨機(jī)性和不科學(xué)性，容易使聚類結(jié)果陷入局部最優(yōu)，且在迭代過程中存在大量的冗余計算，并行處理能力差，缺乏可伸縮性，大大降低了算法的運行效率.文獻(xiàn)[1]針對傳統(tǒng)的K-means算法提出了Canopy改進(jìn)策略，避免了K值選取的盲目性，進(jìn)一步提高聚類算法的準(zhǔn)確率和穩(wěn)定性.文獻(xiàn)[2-3]應(yīng)用三角不等式原理對傳統(tǒng)的K-means算法進(jìn)行了改進(jìn)，避免了算法中冗余計算，提高了收斂速度和降低了內(nèi)存開銷，但并行性不高，缺乏擴(kuò)展性.文獻(xiàn)[4]提出了K-meansCan算法，其先對數(shù)據(jù)進(jìn)行多次隨機(jī)采樣，再進(jìn)行K-means預(yù)聚類，然后將來自不同簇的聚類點進(jìn)行合并，最終實現(xiàn)聚類，在很大程度上提高了聚類結(jié)果的質(zhì)量和算法的效率.文獻(xiàn)[5]提出了一種基于初始聚類中心改進(jìn)的選擇算法M+Kmeans，在初始中心點及K值的選取上進(jìn)行了細(xì)致的優(yōu)化.文獻(xiàn)[6]提出了一種基于MPI的并行計算的層次聚類算法，它雖然從某種程度上利用集中式存儲方式提高了算法的正確性和時效性，但是該算法只能運行在單節(jié)點上，在處理大數(shù)據(jù)任務(wù)時，算法的效率還不夠高；文獻(xiàn)[7]利用遺傳算法的粗粒度并行化設(shè)計思想提出了在Hadoop平臺下將遺傳K-means聚類算法進(jìn)行并行化設(shè)計，提高了K-means算法的效率.文獻(xiàn)[8]用MapReduce模型實現(xiàn)傳統(tǒng)K-means算法的設(shè)計，在處理大數(shù)據(jù)集上，獲得了較好的加速比和良好的擴(kuò)展性.文獻(xiàn)[9]通過ACO算法對K-means算法進(jìn)行了改進(jìn)，并利用MapReduce并行化K-means算法來處理海量數(shù)據(jù)中存在的嚴(yán)重內(nèi)存不足問題，使得聚類算法的可擴(kuò)展性、收斂性以及在聚類計算時的內(nèi)存泄漏問題上均得到了顯著的改善.文獻(xiàn)[10-11]提出了基于Hadoop集群平臺的并行化MapReduce編程模型，其借助于開源的MapReduce編程技術(shù)和當(dāng)前流行的分布式技術(shù)充分滿足了算法并行化執(zhí)行的需求，實現(xiàn)了K-means分布式聚類[12-14]，提高了聚類算法的加速比和運行效率.文獻(xiàn)[15]主要采用Spark和Hadoop技術(shù)進(jìn)行混合式的框架設(shè)計，實現(xiàn)了具有迭代式性能的分布式K-means聚類算法，提高算法的加速比、吞吐量和可擴(kuò)展性.文獻(xiàn)[16]針對分布式Canopy-Kmeans算法中的Canopy選取的隨機(jī)性問題進(jìn)行了改進(jìn)，避免了Canopy選取的盲目性.

鑒于傳統(tǒng)K-means算法的不足，本文采用三角不等式原理[2-3]和“最小最大原則”[1,16]，在Hadoop云計算平臺上提出了一種基于雙MapReduce分布式編程模型改進(jìn)的Canopy-Kmeans算法.

1 Canopy-Kmeans算法

原始的Canopy-Kmeans算法是在K-means算法的基礎(chǔ)上提出的一種優(yōu)化，其基本思想是首先通過Canopy算法進(jìn)行聚類，以確定簇數(shù)以及初始簇心，接著通過K-means算法進(jìn)行迭代運算，收斂出最后的聚類結(jié)果.具體描述如下：對于任意的數(shù)據(jù)集合V,預(yù)先設(shè)定Canopy算法的兩個區(qū)域半徑(即閾值)，通過粗糙距離計算方法計算集合中各對象的相似性，按照各對象的相似性可把數(shù)據(jù)劃分成若干可重疊的小集合(即Canopy)，經(jīng)過一系列的計算后，最終可使得所有的對象均落在Canopy覆蓋的范圍內(nèi)；對落在同一區(qū)域內(nèi)的對象，利用K-means算法重新迭代計算出新中心點，并根據(jù)對象與新中心點之間的距離重新劃分對象所屬區(qū)域；循環(huán)迭代執(zhí)行“劃分Canopy-計算中心點”的過程，直到k中心點的位置不再發(fā)生變化，即達(dá)到一種穩(wěn)定的聚類狀態(tài)為止.由上述介紹可知，K-means算法雖然在開始時使用Canopy算法進(jìn)行了預(yù)處理，無需再人為設(shè)置初始的聚類中心點及聚類個數(shù)K，但Canopy在初始中心點的選取上容易受到區(qū)域半徑的主觀影響，具有較大的盲目性和隨機(jī)性.而該算法對K-means算法本身并未作出任何的改進(jìn)，聚類迭代次數(shù)依然繁瑣，存在大量的冗余計算.針對以上存在的問題，本文同時從以下兩個方面的對原始的Canopy-Kmeans算法進(jìn)行了改進(jìn).

1.1 Canopy算法的改進(jìn)

定義1(Canopy) 給定任意數(shù)據(jù)集合V={vi|i=1,2,…,n}，對于?xi∈V，若其滿足如下公式{Cj|?||xi-Cj||≤T1,Cj?V,i≠j}，則稱xi為Canopy集合，Cj為VCanopy中心點，T1為Canopy集合半徑.

定義2(Canopy中心點) 給定數(shù)據(jù)集合V={vi|i=1,2,…,n}，對于?xi∈V，若其滿足如下公式{Cm|?||xi-Cm||≤T2,T2

很明顯，從以上的定義可知，Canopy算法執(zhí)行的效率受Canopy區(qū)域半徑T1、T2影響較大，當(dāng)T1過大時，會使同一點屬于多Z個Canopy，增加了計算開銷；當(dāng)T2過大時，會減少聚類的個數(shù)，使得聚類過程陷入局部最優(yōu).這樣就導(dǎo)致了Canopy算法對初始中心點的選取上具有較大的盲目性和隨意性.因此，為了解決Canopy區(qū)域半徑T1、T2以及初始中心點的隨機(jī)選取問題，本文采用了一種基于“最小最大原則”改進(jìn)的Canopy算法來提高聚類結(jié)果的準(zhǔn)確性[16].

為了避免在聚類過程陷入局部最優(yōu)，應(yīng)該使Canopy獲得的中心點間距盡可能大.最小最大的基本原理[14]是首先隨機(jī)選取一個種子點作為中心點A，然后計算集合C中剩余點到A點的距離，選取距離最大的點作為第二個種子點B，再計算C中剩余數(shù)據(jù)點到這兩個種子點的距離，得出到這兩個種子點的距離，得出到這兩個中心距離最小的點Min(dA,dB)，找到這些距離最小者中的最大值Max(Min(dA,dB))，迭代條件若滿：

其中dA、dB為數(shù)據(jù)點到A、B點的距離，若滿足以上條件則該數(shù)據(jù)點為第三個種子點，按照上述方法迭代，最終可以確定所有的中心點，得到K值.

基于上述原理改進(jìn)的Canopy中心點選取方法避免了區(qū)域半徑T2的設(shè)置(T2為非Canopy中心點區(qū)域半徑，當(dāng)所有中心點確定后，該值就無需設(shè)置)[16].另外，“最小最大原則”Canopy中心點選擇方法在具體應(yīng)用中呈現(xiàn)如下規(guī)律：Canopy個數(shù)低于或者超過類別真實值時，DistC變化呈現(xiàn)較小幅度；當(dāng)Canopy個數(shù)臨近或達(dá)到類別真實值時，該距離呈現(xiàn)較大突變[16-17].因此，為了確定Canopy中心點的最優(yōu)個數(shù)以及區(qū)域半徑T1，參照文獻(xiàn)[16,18]中的邊界識別思想，引入了表示DistC變化幅度的深度指標(biāo)Depth(i)，其定義為

Depth(i)=|Distmin(i)-Distmin(i-1)|+|Distmin(i+1)-Distmin(i)|

當(dāng)i達(dá)到最優(yōu)聚類時，深度值Depth(i)取得最大值.由以上定義可知，此時Canopy中心點集合中前i個記錄即為最優(yōu)的聚類初始中心點，同時為了保證最終的聚類中心點均落在Canopy范圍內(nèi)，可設(shè)區(qū)域半徑T1=Distmin(i).則基于“最小最大原則”可將Canopy算法進(jìn)一步改進(jìn)為

定義3(Canopy) 給定任意數(shù)據(jù)集合V={vi|i=1,2,…,n}，對于?xi∈V，若其滿足如下公式{Cj|?||xi-Cj||≤Distmin(i),Cj?V,i≠j},則稱xi為Canopy集合，Cj為Canopy中心點且?Cj∈U.Distmin(i)表示數(shù)據(jù)點xi為所有最小距離中的最大者.

定義4(Canopy中心點) 給定數(shù)據(jù)集合V={vi|i=1,2,…,n}，對于?xi∈V，若其滿足如下公式

{Cm|?||xi-Cm||

Cm?V,i≠m}

則稱Cm為非Canopy候選中心點集合.Distmin(i)為數(shù)據(jù)點xi為所有最小距離中的最大者.

經(jīng)過以上的分析可知，經(jīng)過改進(jìn)的Canopy算法，解決了人為設(shè)置區(qū)域半徑T1、T2以及中心點和K值選取的盲目性問題，為聚類結(jié)果的準(zhǔn)確性提供了可靠的理論依據(jù).

1.2 K-means算法的改進(jìn)

定義6 假設(shè)U為所有已聚類中心的集合，當(dāng)?x∈X,?u∈U，使得d(x,u)=mind(x,U),那么u為向量x的聚類中心.

公理1 任意一個三角型，兩邊之和大于第三邊，兩邊之差小于第三邊.由于歐式距離滿足三角不等式特性，我們可以將它擴(kuò)展到多維的歐幾里得空間[19-21].對于任意三個向量 x、b、u，其滿足以下兩個不等式：

d(x,b)+d(b,u)≥d(x,u)；

d(x,b)-d(b,u)≤d(x,u)

根據(jù)以上定義及公理，我們可以得到以下應(yīng)用：假設(shè)xp是數(shù)據(jù)集當(dāng)中任一個向量，ui是向量xp當(dāng)前的類中心，d(xp,ui)已知且uj是剩余中心點中除ui外任意的一個，如果2d(xp,ui)≤d(ui,uj)，則有2d(xp,ui)-d(xp,ui)≤d(ui,uj)-d(xp,ui)，化簡可得：

d(xp,ui)≤d(ui,uj)-d(xp,ui)

(1)

由公理1中歐式空間的三角不等式特性可得

d(ui,uj)-d(xp,ui)≤d(xp,uj)

(2)

因此，聯(lián)立式(1)、(2)可得到如下結(jié)論：

d(xp,ui)≤d(xp,uj)，即向量點xp屬于聚類中心點ui.

由以上推導(dǎo)可知，對于傳統(tǒng)的K-means算法，若能在距離迭代計算之前進(jìn)行一次篩選，則可避免很多的冗余計算.若用d1(xp,uj)表示xp到uj上界約束，用d2(xp,uj)表示xp到uj下界約束，則基于三不等式角原理改進(jìn)的K-means算法，可以進(jìn)一步描述為：

定義7 (K-means) 將定義3得到的Canopy中心點集合U中的元素作為K個聚類質(zhì)心點u1,u2,…,uk∈Rn， 對于Canopy子集中的任意數(shù)據(jù)點xp：若滿足2d1(xp,ui)≤d(ui,uj)，則數(shù)據(jù)點xp屬于聚類中心點ui，不需進(jìn)行任何距離迭代計算；若滿足2d1(xp,ui)≥d(ui,uj)且d2(xp,uj)≤d1(xp,uj)時，需要對數(shù)據(jù)點xp進(jìn)行迭代計算.具體迭代步驟如下：

① 計算數(shù)據(jù)點xp應(yīng)該屬于的類

② 對于每一個類k，重新計算該類的質(zhì)心

③ 循環(huán)執(zhí)行①、②，直到聚類準(zhǔn)則函數(shù)

收斂為止，其中c(p)為數(shù)據(jù)點p到k個類中距離最近的類.通過以上的改進(jìn)可知，基于三角不等式原理改進(jìn)的K-means算法能夠大幅度地減少迭代過程中不必要的距離計算，從而進(jìn)一步提高原算法的運行速度.

2 雙MapReduce設(shè)計的Canopy-Kmeans算法

針對定義3、定義4及定義7的改進(jìn)理論，本文在Hadoop平臺上采用了雙MapReduce編程技術(shù)，將改進(jìn)的整個算法分成兩個MapReduce子任務(wù)來完成，并用第一個MapReduce子任務(wù)的輸出結(jié)果作為下一個MapReduce子任務(wù)的輸入.算法設(shè)計的整體方案如圖1所示.

圖1 基于雙MapReduce改進(jìn)的Canopy-Kmeans并行算法流程

第一個子任務(wù)是在MapReduce編程模型中利用“最小最大原則”對Canopy聚類算法進(jìn)行“粗糙”聚類.通過計算數(shù)據(jù)的相似性來對全體數(shù)據(jù)集進(jìn)行相似性劃分，最終可得到各個分組(Canopy子集)及所需的中心點集合和k值.這樣下一步的初始中心點的選擇就不至于因為隨機(jī)選擇而偏離實際中心點太遠(yuǎn)，同時也避免了初始K值設(shè)定的盲目性；第二個MapReduce子任務(wù)采用基于距離三角不等式原理改進(jìn)的K-means算法對得到的各個分組(Canopy子集)進(jìn)行“精細(xì)”聚類.在每一次迭代計算之前，通過對各個數(shù)據(jù)點距離計算的篩選，可減少許多不必要的計算，進(jìn)一步優(yōu)化了傳統(tǒng)的聚類算法；最后通過Driver對象將以上兩個MapReduce子任務(wù)作業(yè)按線性方式順序鏈接并自動化地生成一個可執(zhí)行序列交給Hadoop平臺處理，并將最終得到的聚類結(jié)果存入HDFS中.

2.1 Canopy與K-means算法

將待處理數(shù)據(jù)上傳到HDFS中，并將數(shù)據(jù)分片存儲到若干臺DataNode中.為了得到K-means算法初始的聚類中心點及K值，第一個MapReduce子任務(wù)將Canopy算法分為兩個階段來完成，即Map階段和Reduce階段.在Map階段，根據(jù)“最小最大”原則及邊界意識對輸入的鍵值對進(jìn)行Canopy聚類迭代，然后將各個DataNode在Map階段進(jìn)行Canopy聚類得到的局部中心點集合Pi作為Reduce階段的輸入；在Reduce階段，合并所有DataNode輸出的Canopy中心點集合Pi，把合并結(jié)果存入集合P中，接下來在集合P中進(jìn)行全局Canopy“粗糙”聚類，重復(fù)上述過程，直到數(shù)據(jù)集List為空.最后輸出聚類中心點個數(shù)K及全局Canopy中心點集合U.

第二個MapReduce子任務(wù)主要將K-means算法分為三個階段來完成，即Map階段、Combine階段和Reduce階段.在Map階段，將第一次MapReduce子任務(wù)輸出的K值及聚類中心點集合U作為本次改進(jìn)K-means算法的初始簇的個數(shù)K及聚類質(zhì)心，并將這K個質(zhì)心存儲到HDFS上作為一個全局變量.利用距離三角不等式原理對canopy子集中得到數(shù)據(jù)點進(jìn)行重新劃分；在Combine階段，由于在Map階段每個數(shù)據(jù)節(jié)點輸出的中間結(jié)果比較大，勢必會造成多次溢寫的發(fā)生，消耗大量的系統(tǒng)資源，為了進(jìn)一步提高算法的運行效率，本算法在不改變最終計算結(jié)果的情況下，引進(jìn)了Combine()函數(shù)來優(yōu)化MapReduce的中間結(jié)果，其將鍵值對中具有相同key值的value合并起來，可大幅度地減少溢寫到磁盤的數(shù)據(jù)量.另外，本階段還把最后由Combine()函數(shù)合并的結(jié)果作為Reduce階段的輸入，進(jìn)一步減輕了Reduce階段再次合并中間結(jié)果的負(fù)擔(dān)，提高了原算法的執(zhí)行速度；在Reduce階段，首先讀取出從每個Combine中處理的數(shù)據(jù)樣本個數(shù)和每個數(shù)據(jù)樣本各維的坐標(biāo)值，并將對應(yīng)的各維累加值分別對應(yīng)相加，再除以總的樣本個數(shù)，所得的結(jié)果即為新的中心點坐標(biāo).然后把Reduce階段輸出的結(jié)果，作為新一輪迭代計算的中心點坐標(biāo)并將其上傳到HDFS中進(jìn)行下一輪迭代，最后直到算法收斂為止.

2.2 算法時間復(fù)雜度

串行的Canopy-Kmeans算法的時間復(fù)雜為o(nkf2t1/c)，其中n為數(shù)據(jù)量，k為類的數(shù)量，t1是迭代次數(shù)，c為Canopy的數(shù)量，f代表一個數(shù)據(jù)點被劃分到多個Canopy重疊區(qū)域內(nèi).由于在Hadoop平臺中是由多個DataNode數(shù)據(jù)節(jié)點同時進(jìn)行數(shù)據(jù)處理的，并且主從節(jié)點之間需要彼此通信協(xié)同工作.假設(shè)實驗中有m個DataNode數(shù)據(jù)節(jié)點并行工作，則并行的Canopy-Kmeans算法的時間復(fù)雜度為o(nkf2t2/mc)，理論上，相比較串行算法而言，復(fù)雜度降低了(mt1/t2)倍，其中t2遠(yuǎn)小于t1.這是是因為經(jīng)改進(jìn)的算法，減少了許多的冗余計算和算法的迭代次數(shù)，提高了數(shù)據(jù)處理的性能.

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

3.1 Hadoop集群環(huán)境

Hadoop集群一共包括五臺計算機(jī)，分別通過局域網(wǎng)進(jìn)行連接，每臺計算機(jī)的CPU為Intel(R)i5雙核2.3 GHz，內(nèi)存4 G,硬盤500 G,操作系統(tǒng)是windows7 64位.并在每臺機(jī)器上安裝Cygwin虛擬機(jī)用它來模擬Linux環(huán)境.配置SSH免密碼登錄，安裝Hadoop v2.0，配置分布式的Hadoop集群，并將其中一臺機(jī)器角色設(shè)置為Jobtracker和NameNode服務(wù)節(jié)點，其余四臺機(jī)器角色均設(shè)置為DataNode和TaskTracker服務(wù)節(jié)點.JDK版本為1.8.0-i586，安裝MyEclipse10.0并在MyEclipse10.0中創(chuàng)建雙MapReduce工程，然后通過driver對象進(jìn)行順序化鏈接執(zhí)行，最后將要處理的數(shù)據(jù)集導(dǎo)入到HDFS中.

為了測試本文算法的性能及可行性，主要采用了以下幾個衡量指標(biāo)：準(zhǔn)確率(樣本正確的個數(shù)/樣本總數(shù))、加速比以及算法的擴(kuò)展性，并將實驗結(jié)果分別與傳統(tǒng)的K-means算法和原始的Canopy-Kmeans算法進(jìn)行了比較.另外，算法中的實驗數(shù)據(jù)均選自UCI數(shù)據(jù)集中的真實數(shù)據(jù)( http://archive.ics.uci.edu/ml/datasets.html).

3.2 算法的準(zhǔn)確性分析

由表1實驗結(jié)果可知：從總體上看，改進(jìn)的Canopy-Kmeans算法準(zhǔn)確性明顯高于其余兩個算法，這個容易理解，因為在數(shù)據(jù)預(yù)處理階段，Canopy算法采用“最小最大”原則對大數(shù)據(jù)集進(jìn)行了“粗糙”聚類，避免了隨機(jī)指定K值、T1、T2、初始中心點的盲目性，大大提高了聚類結(jié)果的精確性，同時也減少了K-means算法收斂時的迭代次數(shù)；另外，當(dāng)數(shù)據(jù)規(guī)模與維數(shù)成線性增加時，聚類的個數(shù)K值也在逐漸變大，這對于一個數(shù)據(jù)向量來講，需要計算的數(shù)據(jù)向量與類中心之間的距離就變得相當(dāng)多，而基于三角不等式原理改進(jìn)的K-means算法對數(shù)據(jù)向量的距離計算進(jìn)行了預(yù)先篩選，減少了迭代過程中的距離計算次數(shù)，避免了過多的冗余計算，大幅度地提高了算法的運行效率.

表1 三種算法在Hadoop平臺上的結(jié)果對比

3.3 算法在Hadoop平臺上的加速比分析

為了測試本文算法的加速比，實驗數(shù)據(jù)從UCI數(shù)據(jù)集中的Poker Hand數(shù)據(jù)集隨機(jī)選取了3個樣本數(shù)據(jù)，樣本數(shù)分別為100萬條，400萬條，1600萬條如圖2～4所示.

圖2 數(shù)據(jù)規(guī)模為100萬條時的加速比曲線圖

從圖2到圖4可以看出，設(shè)計的算法加速比基本上是成線性的，當(dāng)數(shù)據(jù)規(guī)模越大時，改進(jìn)的Canopy-Kmeans并行算法加速比就越接近線性增長.隨著DataNode數(shù)據(jù)節(jié)點的增加，三種算法的加速比增長速度也逐漸趨于減緩，主要是因為當(dāng)數(shù)據(jù)規(guī)模相同時，節(jié)點的增加會導(dǎo)致各個節(jié)點之間通信開銷變大，占用一部分必要的時間.另外，可以清晰的看到，無論數(shù)據(jù)規(guī)模大小與否，改進(jìn)后的Canopy-Kmeans并行算法的加速比均明顯高于其它兩個算法，這是因為文中算法在K-means算法階段增加了Combine函數(shù)的設(shè)計，其對Map階段產(chǎn)生的大量中間結(jié)果進(jìn)行了本地化Reduce預(yù)處理，減少了DataNode數(shù)據(jù)節(jié)點之間的I/O傳輸，大大節(jié)省了算法運行的成本，尤其是當(dāng)數(shù)據(jù)規(guī)模越大時，效果就越明顯.

圖3 數(shù)據(jù)規(guī)模為400萬條時的加速比曲線圖

圖4 數(shù)據(jù)規(guī)模為1600萬條時加速比曲線圖

3.4 算法在Hadoop平臺上的擴(kuò)展性分析

為了測試本文算法的擴(kuò)展性，分別在不同的DataNode數(shù)據(jù)節(jié)點個數(shù)下，對不同大小的數(shù)據(jù)集進(jìn)行了實驗.實驗中的數(shù)據(jù)來源于UCI數(shù)據(jù)集中的SIFT10M Data Set 數(shù)據(jù)集,并從中隨機(jī)抽取了四組樣本數(shù)據(jù)，其樣本數(shù)分別為200萬條，400萬條，800萬條，1600萬條,如圖5所示.

圖5 Hadoop平臺上的擴(kuò)展率曲線圖

從圖5中可以看出，在不同規(guī)模的測試數(shù)據(jù)集上，隨著DataNode數(shù)據(jù)節(jié)點的遞增，算法的運行效率整體上在逐漸下降.這是因為當(dāng)Hadoop平臺上有多個DataNode運行時，在Reduce階段各節(jié)點之間需要傳輸并合并大量的中間數(shù)據(jù)，這使得節(jié)點之間的通訊代價增大，需耗費很多的系統(tǒng)資源，加大了算法的時間運行成本.另外，對于相同規(guī)模的數(shù)據(jù)集，隨著節(jié)點的增加，數(shù)據(jù)量大的樣本集運行效率率明顯優(yōu)于數(shù)據(jù)量小的樣本集，尤其在第4個節(jié)點時，運行1600萬條數(shù)據(jù)時明顯比運行800萬條的數(shù)據(jù)運行效率高，這是因為隨著數(shù)據(jù)量的增加，處理數(shù)據(jù)的時間遠(yuǎn)遠(yuǎn)會大于各個節(jié)點的通信開銷，這使得Hadoop平臺的DataNode節(jié)點更容易發(fā)揮它的并行計算能力.由此可知，本文算法在節(jié)點增加時，可以提高系統(tǒng)對相同規(guī)模數(shù)據(jù)的處理能力，具有良好的擴(kuò)展性.

4 結(jié) 論

1) 將Hadoop云計算平臺與基于“最小最大”原則改進(jìn)的Canopy算法和基于三角不等式原理改進(jìn)的K-means算法相結(jié)合，設(shè)計并實現(xiàn)了一種基于雙MapReduce編程模型改進(jìn)的Canopy-Kmeans算法.

2) 與傳統(tǒng)的K-means算法相比，改進(jìn)的算法精確率平均提高了15.3%，且加速比和擴(kuò)展性隨著數(shù)據(jù)規(guī)模的不斷增大也相應(yīng)的提高了1.5～3倍，明顯改善了聚類效果，適合運行于大規(guī)模的數(shù)據(jù)處理平臺上，且數(shù)據(jù)量越大，節(jié)點數(shù)越多，算法所取得的效果就越好.

3) 本文算法對于非等軸狀分布、具有噪聲或孤立點的數(shù)據(jù)較為敏感，不適合非凸面形狀、條形狀聚類的數(shù)據(jù)集，或者簇大小差別很大的數(shù)據(jù)集，且在高維數(shù)據(jù)空間上Canopy中心點的生成較為耗時，在不影響算法聚類精度的基礎(chǔ)上，需進(jìn)一步提高K-means算法的效率.

[1] 趙慶.基于Hadoop平臺下的Canopy-Kmeans高效算法[J].電子科技,2014,27(2):29.

ZHAO Qing.The Canopy-Kmeans Efficient Algorithm Based on Hadoop Platform[J].Electronic Science and Technology,2014,27(2):29.(in Chinese)

[2] 張順龍,庫濤,周浩.針對多聚類中心大數(shù)據(jù)集的加速K-means聚類算法[J].計算機(jī)應(yīng)用研究,2016,33(2):413.

ZHANG Shunlong,KU Tao,ZHOU Hao.An Accelerated K-means Clustering Algorithm for Large Data Sets in Multi Cluster Centers[J].Computer Application Research，2016,33(2):413.(in Chinese)

[3] 常晉義,何春霞.基于三角不等式原理的K-means加速算法[J].計算機(jī)工程與設(shè)計,2007,28(21):5094.

CHANG Jinyi,HE Chunxia.K-means Acceleration Algorithm Based on the Principle of Triangle Inequality[J].Computer Engineering and Design,2007,28(21):5094.(in Chinese)

[4] 雷小鋒,謝昆青,夏征義.一種基于K-means局部最優(yōu)性的高效聚類算法[J].軟件學(xué)報,2008,19(7):1683.

LEI Xiaofeng,XIE Kunqing,XIA Zhengyi.An Efficient Clustering Algorithm Based onK-means Local Optimality[J].Journal of Software,2008,19(7):1683.(in Chinese)

[5] 武霞,董增壽,孟曉燕.基于大數(shù)據(jù)平臺Hadoop的聚類算法K值優(yōu)化研究[J].太原科技大學(xué)學(xué)報,2015,36(2):1673.

WU Xia,DONG Zengshou,MENG Xiaoyan.Research on K Value Optimization of Clustering Algorithm Based on Large Data Hadoop Platform[J].Journal of Taiyuan University of Science and Technology,2015,36(2):1673.(in Chinese)

[6] QIAN Y J.Research on and Implementation of the Technologies of Mining of Massive Datasets[D].Chengdu:University of Electronic Science and Technology of China.2009.

[7] 賈瑞玉,管玉勇,李亞龍.基于MapReduce模型的并行遺傳K-means聚類算法[J].計算機(jī)工程與設(shè)計,2014,2(2):31.

JIA Ruiyu,GUAN Yuyong,LI Yalong.Parallel Genetic K-means Clustering Algorithm Based on MapReduce Model[J].Computer Engineering and Design,2014,2(2):31.(in Chinese)

[8] 江小平,李成華,向文,等.K-means聚類算法的MapReduce并行化實現(xiàn)[J].華中科技大學(xué)報,2011,39(1):120.

JIANG Xiaoping,LI Chenghua,XIANG Wen,et al.MapReduce Parallel Implementation ofK-means Clustering Algorithm[J].Journal of Huazhong University of Science and Technology,2011,39 (1):120.(in Chinese)

[9] 虞倩倩,戴月明,李晶晶.基于MapReduce的ACO-Kmeans并行聚類算法[J].計算機(jī)工程與用,2013,49(16):117.

YU Qianqian,DAI Yueming,LI Jingjing.ACO-Kmeans Parallel Clustering Algorithm Based on MapReduce[J].Computer Engineering and Applications,2013,49(16):117.(in Chinese)

[10] QIU R T.Research on MapReduce Application Based on Hadoop[D].Jiaozuo:Henan Polytechnic University,2009.

[11] 溫程.并行聚類算法在MapReduce上的實現(xiàn)[D].杭州:浙江大學(xué),2011.

WEN Cheng.Parallel Clustering Algorithm on the MapReduce to Achieve [D].Hangzhou:Zhejiang University,2011.(in Chinese)

[12] 趙衛(wèi)中,馬慧芳,傅燕翔,等.基于云計算平臺Hadoop的并行K-means聚類算法設(shè)計研究[J].計算機(jī)科學(xué),2011，38(10):166.

ZHAO Weizhong,MA Huifang,FU Yanxiang,et al.Research on ParallelK-means Algorithm Design Based on Hadoop Platform[J].Computer Science,2011，38(10):166.(in Chinese)

[13] 周麗娟,王慧,王文伯.面向海量數(shù)據(jù)的并行K-means算法[J].華中科技大學(xué)學(xué)報,2012(S1) :150.

ZHOU Lijuan,WANG Hui,WANG Wenbo.ParallelK-means Algorithm for Massive Data[J].Journal of Huazhong University of Science and Technology,2012(S1):150.(in Chinese)

[14] CUI X L,ZHU Pingfei,YANG Xin,et al.Optimized Big DataK-means Clustering Using MapReduce[J].The Journal of Supercomputing,2014,70(3):1249.

[15] 唐振坤.基于Spark的機(jī)器學(xué)習(xí)平臺設(shè)計與實現(xiàn)[D].廈門:廈門大學(xué),2014.

TANG Zhenkun.Design and Implementation of Machine Learning Platform Based on Spark[D].Xiamen:Xiamen University,2014.(in Chinese)

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

MAO Dianhui.Improved Canopy-Kmeans Algorithm Based on MapReduce[J].Computer Engineering and Applications,2012,48(27):22.(in Chinese)

[17] 劉遠(yuǎn)超,王曉龍,劉秉權(quán).一種改進(jìn)得K-means文檔聚類初始值選擇算法[J].高技術(shù)通訊,2006,16(1):11.

LIU Yuanchao,WANG Xiaolong,LIU Bingquan.An Improved Initial Value Selection Algorithm forK-means Document Clustering[J].High Tech Communication,2006,16(1):11.(in Chinese)

[18] DEAN J,GHEMAWAT S.MapReduce：Simplified Data Processing on Large Clusters[C]//Proceedings of the 6th International Conference on Operation Systems Design & Implementation (OSDI),Berkeley,CA,USA,2004:137.

[19] ELKAN C.Using the Triangle Inequality to AccelerateK-means[C]//Proceedings of the 20th International Conference on Machine Learning,Washington DC,2003.

[20] ANDREW W M.The Anchors Hierarchy:Using the Triangle Inequality to Survive High Dimensional Data[C]//Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence,Stanford University,San Francisco,2000.

[21] 何春霞,常晉義.三角不等式原理對聚類算法的改進(jìn)[J].常熟理工學(xué)院學(xué)報(自然科學(xué)版),2007,21(2):100.

HE Chunxia,CHANG Jinyi.The Improvement of Clustering Algorithm Based on the Theory of Three Inequalities[J].Journal of Changshu Institute of Technology(Nature Science Edition),2007,21(2):100.(in Chinese)

(責(zé)任編輯、校對 肖 晨)

Improved Canopy-Kmeans Algorithm based on Double-MapReduce

LIUBaolong,SUJin

(School of Computer Science and Engineering,Xi’an Technological University,Xi’an 710021,China)

The Canopy-Kmeans algorithm has the disadvantage of great randomness in the selection of center points, and the redundant computation in the iterative process significantly reduces the operation efficiency of the algorithm. So the paper proposes an improved Canopy-Kmeans algorithm based on the Double-MapReduce on the Hadoop platform,which is based on the "minimum maximum principle" and the principle of triangle inequality.The experimental results show that the precision of the designed parallel algorithm is raised by 15.3% on average,and the speedup and scalability are increased by 1.5 to 3 times with the increase of the data size and the number of node. The problem existing in the selection of Canopy center point is successfully solved and the redundant distance calculation in iterative is avoided.

Canopy-Kmeans;redundant computation;hadoop platform;double-MapReduce

10.16185/j.jxatu.edu.cn.2016.09.009

2016-05-09

陜西省科技統(tǒng)籌創(chuàng)新工程計劃項目(2015KTCXSF-10-11);西安市未央?yún)^(qū)科技計劃項目(201609).

劉寶龍(1976-)，男，西安工業(yè)大學(xué)副教授，主要研究方向為信息安全工程.E-mail：b.liu@xatu.edu.cn.

TP301.6

A

1673-9965(2016)09-0730-08