孫玉強，李媛媛，陸 勇

(常州大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 常州 213164)

基于MapReduce的K-means聚類算法的優(yōu)化

孫玉強，李媛媛，陸 勇

(常州大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 常州 213164)

針對傳統(tǒng)的聚類算法K-means對初始中心點的選擇非常依賴，容易產(chǎn)生局部最優(yōu)而非全局最優(yōu)的聚類結(jié)果，同時難以滿足人們對海量數(shù)據(jù)進行處理的需求等缺陷，提出了一種基于MapReduce的改進K-means聚類算法。該算法結(jié)合系統(tǒng)抽樣方法得到具有代表性的樣本集來代替海量數(shù)據(jù)集；采用密度法和最大最小距離法得到優(yōu)化的初始聚類中心點；再利用Canopy算法得到粗略的聚類以降低運算的規(guī)模；最后用順序組合MapReduce編程模型的思想實現(xiàn)了算法的并行化擴展，使之能夠充分利用集群的計算和存儲能力，從而適應(yīng)海量數(shù)據(jù)的應(yīng)用場景；文中對該改進算法和傳統(tǒng)聚類算法進行了比較，比較結(jié)果證明其性能優(yōu)于后者；這表明該改進算法降低了對初始聚類中心的依賴，提高了聚類的準(zhǔn)確性，減少了聚類的迭代次數(shù)，降低了聚類的時間，而且在處理海量數(shù)據(jù)時表現(xiàn)出較大的性能優(yōu)勢。

K均值算法；抽樣；Canopy算法；最大最小距離法

0 引言

隨著數(shù)據(jù)規(guī)模的爆炸性增長，傳統(tǒng)的數(shù)據(jù)挖掘工作在處理大規(guī)模數(shù)據(jù)時會出現(xiàn)用時過長、存儲量不足等缺點。云計算的提出將這些問題迎刃而解，它是一種基于互聯(lián)網(wǎng)的計算，是分布式計算、并行處理和網(wǎng)格計算的進一步發(fā)展。由Google提出的MapReduce編程框架[1]是云計算中代表性的技術(shù)，主要用于海量數(shù)據(jù)的并行計算。已有多種數(shù)據(jù)挖掘算法在MapReduce計算模型的基礎(chǔ)上被實現(xiàn)了，而聚類是在數(shù)據(jù)挖掘中運用比較廣泛的一種算法。

K-means算法是一種典型的基于劃分的聚類算法[2]，該算法簡單高效，運用于科學(xué)研究的各個領(lǐng)域。但是它對初始聚類中心的選擇非常敏感，不能有效地對大規(guī)模數(shù)據(jù)進行聚類處理。針對 K-means算法的特點以及不足，很多學(xué)者提出了相應(yīng)的改進K-means算法。鄧海等人[3]提出了基于最近高密度點間的垂直中心點優(yōu)化初始聚類中心的K-means聚類算法；王玲等人[4]提出一種密度敏感的相似度度量的方法;馬帥等人[5]提出了一種基于參考點和密度的快速聚類算法。這些研究通過不同的方法解決了算法對初始中心敏感的問題，但卻增加了算法的復(fù)雜度。其他的例如毛典輝等人[6]提出了改進的Canopy和K-means相結(jié)合的算法；虞倩倩[7]等人提出了聚類的蟻群優(yōu)化算法；馬漢達(dá)等人[8]提出了基于粒子群算法(PSO)的K-means算法；賈瑞玉等人[9]提出了并行遺傳K-means聚類算法，都是結(jié)合一些成熟的算法來改進K-means聚類算法，雖然在少量數(shù)據(jù)環(huán)境下能夠顯著提升K-means算法的性能，但卻因為額外的組件增加了算法的復(fù)雜性， 無法適應(yīng)海量數(shù)據(jù)的處理需求。因此，本文提出了一種基于MapReduce的高效 K-means并行算法， 其結(jié)合了抽樣方法進行預(yù)處理以減少數(shù)據(jù)量；通過密度思想對初始中心點優(yōu)化提高聚類準(zhǔn)確性；結(jié)合其他算法降低計算規(guī)模；再通過MapReduce分布式并行模型提高運行效率。實現(xiàn)的過程主要有4個子任務(wù)：1)抽取樣本；2)計算樣本初始聚類中心點；3)Canopy劃分；4)K-means迭代。通過實驗結(jié)果得出，此改進算法在處理海量數(shù)據(jù)時可以體現(xiàn)出更大的優(yōu)勢。

1 背景

1.1 MapReduce簡介

MapReduce是一種分布式并行編程模型，數(shù)據(jù)被存儲在分布式文件系統(tǒng)(distributed file system, DFS)中，以鍵-值對的形式來表示數(shù)據(jù)。MapReduce的具體步驟是：先將數(shù)據(jù)切割成Split，對Split又分成一批鍵值對傳給Map函數(shù)；Map函數(shù)對每個鍵值對進行處理后形成新的鍵值對< K2,V2>，并把K2值相同的進行匯總，輸出中間結(jié)果< K2,list>；Reduce函數(shù)對Map函數(shù)輸出的中間結(jié)果做相應(yīng)的處理后得到鍵值對。MapReduce的操作流程如圖1所示[10]。

圖1 Mapreduce的操作流程圖

1.2 密度思想

在一個大規(guī)模的數(shù)據(jù)對象空間中，低密度區(qū)域的數(shù)據(jù)對象點一般劃分著高密度區(qū)域的數(shù)據(jù)對象點，通常所說的噪聲點或孤立點就是這些低密度區(qū)域的點。如果在進行聚類分析時，這些噪聲點或孤立點被選為初始聚類中心，就會造成聚類不理想的結(jié)果。因此，初始聚類中心的選取應(yīng)該集中到高密度區(qū)域以排除孤立點的干擾。為了有效地排除數(shù)據(jù)樣本中存在的噪聲點對象和孤立點對象，可以通過引入高密度點的概念來處理。

定義1 高密度點：取數(shù)據(jù)集中的數(shù)據(jù)對象xi為中心點，計算此中心點在鄰域半徑δ內(nèi)包含的樣本個數(shù)，若樣本個數(shù)不少于常數(shù)Minds，則該中心點就被稱為高密度點。其中δ的取值需結(jié)合輸入的數(shù)據(jù)對象集，將其取為n個數(shù)據(jù)樣本間距離均方根的一半，公式如下：

(1)

其中：‖xi-xj‖為公式(2)的歐式距離D(i,j)。

1.3 最大最小原則

為了避免初值選取時出現(xiàn)的聚類中心過于鄰近的情況，最大最小原則可以用來選取盡可能遠(yuǎn)的數(shù)據(jù)對象作為初始聚類中心?！白畲笞钚≡瓌t”[11]的算法描述如下：

1)從n個數(shù)據(jù)集{X1,X2,…Xn}中隨機選取一個樣本作為第一個初始聚類中心點C1；

2)在剩余的數(shù)據(jù)對象集中找到距離C1最遠(yuǎn)的點，作為第二個初始聚類中心點C2；

3)分別計算剩余的數(shù)據(jù)對象集到已有的i個聚類中心點之間的距離，取最小距離的最大者：D(i+1)=max{min{D(j,1),D(j,2),…,D(j,i)}}，j=1,2,…,n，則第i+1個初始聚類中心點為Ci+1=Xj；

4)用來表示D(i+1)變化幅度的深度指標(biāo)Depth(k)可以通過邊界識別的思想進行引入，其定義為：Depth(k)=|D(k)-D(k-1)|+ |D(k+1)-D(k)|，當(dāng)深度值 Depth(k)取得最大值時，需求解的最優(yōu)初始聚類中心點就為前k個記錄值，同時下一輪Canopy的區(qū)域半徑可設(shè)為T1=D(k)，避免了Canopy算法初始值設(shè)置的盲目性和隨機性。

1.4 Canopy算法

Canopy算法[12]的思想是使用一種代價低的相似性度量方法，快速粗略地將數(shù)據(jù)劃分成若干個重疊子集，每個子集可以看成是一個簇。Canopy算法基本流程[13]如下：

1)設(shè)置閾值T1，T2，其中T1>T2；

2)從數(shù)據(jù)集中取得一個數(shù)據(jù)對象，構(gòu)建初始Canopy，并從該數(shù)據(jù)集中刪除該數(shù)據(jù)對象；

3)從剩余的數(shù)據(jù)集中取出一個數(shù)據(jù)對象，

計算其與所的有Canopy中心之間的距離，如果該數(shù)據(jù)對象與某個Canopy中心的距離在T1內(nèi)，則將該對象加入到這個Canopy中，如果該對象與Canopy中的某個Canopy中心的距離小于T2，則當(dāng)該數(shù)據(jù)對象與所有Canopy中心的距離計算完成后，將其從數(shù)據(jù)集中刪除，如果該數(shù)據(jù)對象沒有加入到任何Canopy，則構(gòu)建一個新的Canopy；

4)重復(fù)步驟3)，直到數(shù)據(jù)集為空。

2 K-means算法介紹和分析

2.1 K-means算法思想

K-means算法流程[14]：1)首先從n個數(shù)據(jù)對象中隨機選取k個初始聚類中心點；2)對于剩下的其它數(shù)據(jù)對象，分別求它們與這k個聚類中心的歐式距離(相似度)，將它們分配給與其歐式距離最小(相似度最大)的聚類；3)計算新的聚類中心(聚類中所有對象的均值)；4)不斷重復(fù)步驟2)和3)這一過程直到準(zhǔn)則函數(shù)開始收斂為止。

1)歐式距離公式如下：

(2)

其中：i=(xi1, xi2,...,xip)；j=(xj1,xj2,...,xjp)；它們分別表示一個p-維數(shù)據(jù)對象。

2)均方差準(zhǔn)則函數(shù)

(3)

其中：E為數(shù)據(jù)集中所有數(shù)據(jù)的均方差之和；p為數(shù)據(jù)對象空間中的一個點；mi為聚類Ci的均值(p和mi都是多維的)。

2.2 K-means算法的不足及其改進

1)傳統(tǒng)K-means算法不能有效處理大規(guī)模數(shù)據(jù)的聚類操作。而基于MapReduce的分布式并行計算模型，將一個大型數(shù)據(jù)切分成多個小數(shù)據(jù)模塊的形式，分配給多臺計算機集群進行分布式計算，與傳統(tǒng)的單機運行平臺相比，加快了總體的運行速率，減少了執(zhí)行時間。

2)傳統(tǒng)的K-means算法通過完全隨機的策略對初始聚類中心點進行選取，不能確保聚類結(jié)果的準(zhǔn)確性，更不能有效處理海量數(shù)據(jù)?？梢酝ㄟ^抽樣方法對初始數(shù)據(jù)進行預(yù)處理操作，得出有效樣本集合。再結(jié)合密度思想和最大最小原則求得樣本集的初始聚類中心。在高密度區(qū)域選擇初始中心點可以排除噪聲點和孤立點的干擾，而最大最小原則可以避免在高密度區(qū)域選取的中心點過于鄰近。

3)傳統(tǒng)的K-means算法在比較數(shù)據(jù)對象與聚類中心的距離時，計算了全局對象與中心點之間一一對應(yīng)的距離，雖然在一定程度上確保了聚類的效果，但是總體上降低了算法的效率，而且不能適應(yīng)大規(guī)模數(shù)據(jù)的聚類處理。對此，引入了Canopy(華蓋)的思想，每次只比較落在同一Canopy內(nèi)的對象與相應(yīng)中心點之間的距離，通過減少比較次數(shù)大大降低整個聚類的運行時間[13]。實驗結(jié)果表明，該策略在處理大規(guī)模數(shù)據(jù)時，與傳統(tǒng)方法相比，其收斂速度更快。

3 改進K-means算法的并行化

改進的K-means算法思想：首先采取系統(tǒng)抽樣，得到一個具有較少數(shù)目并能代表全局?jǐn)?shù)據(jù)對象的樣本集合；再運用密度法和最大最小距離法相結(jié)合的方法求得樣本集合的最佳初始聚類中心；最后利用Canopy算法對全局?jǐn)?shù)據(jù)對象進行粗略劃分，以改進 K-means 算法。一方面，該算法可以通過獲得優(yōu)化的初始聚類中心來提高聚類結(jié)果的精確度；另一方面，該算法能夠智能的降低數(shù)據(jù)比較的次數(shù)。最后，將改進后的算法運用于MapReduce的并行計算模型中，其基本流程如圖2所示。

3.1 抽取樣本

系統(tǒng)抽樣主要將在HDFS上存儲的split文件塊進行規(guī)則設(shè)計與文件讀取，設(shè)每個部分抽樣概率為px，則我們首先在Map階段對每個文件塊的數(shù)據(jù)量大小以及文件行數(shù)進行預(yù)估，順序讀取文件的前x%行，并指定為相同的key值傳到同一個Reducer上，在Reduce階段對每個塊的樣本數(shù)據(jù)合并，得到最終的抽樣結(jié)果。

指定參數(shù)0<ε<1來控制樣本大小，設(shè)n為數(shù)據(jù)集大小，則通過概率px=1/(nε2)對整個數(shù)據(jù)集進行系統(tǒng)抽樣，可以得到均勻的樣本。算法1描述了利用MapReduce模型進行系統(tǒng)抽樣(RS)的過程。

算法1：系統(tǒng)抽樣算法。

輸入：初始數(shù)據(jù)集G；

輸出：樣本集S。

Map 函數(shù)：

1)每個Map讀取數(shù)據(jù)G和抽樣概率px，利用px進行抽樣；

2)將所有數(shù)據(jù)作為value，為它們指定相同的key，形成中間鍵值對；

Reduce 函數(shù)：

1)將中間鍵值對shuffle到同一Reducer上；

2)輸出樣本數(shù)據(jù)集S；

3.2 計算樣本初始聚類中心點

3.2.1 計算高密度數(shù)據(jù)集

算法2：高密度點生成的并行化。

輸入：樣本集S。

輸出：高密度點集HD。

Map函數(shù)：

1)每個Map讀取樣本集S，計算每個樣本點xi與其余樣本點之間的距離D(i,j)；

Reduce函數(shù)：

(1)根據(jù)公式(3)計算鄰域半徑δ，并統(tǒng)計到每個樣本點xi距離小于δ的樣本個數(shù)；

2)讀取密度閾值Minds，若個數(shù)大于Minds，則把該點定義為高密度點，得到高密度點集合HD。

3.2.2 計算優(yōu)化初始中心點

算法3：樣本中心點生成算法。

Map 函數(shù)：

輸入：高密度點集HD；

輸出：中心點的初始集合Q。

(1)設(shè)置初始中心點的集合，Q=null；

(2)設(shè)置迭代次數(shù)，Whilek

(3)if集合Q為空，求數(shù)據(jù)集V(當(dāng)前節(jié)點數(shù)據(jù)集V)中密度最大點，并保存該點至集合Q；else求數(shù)據(jù)集V中數(shù)據(jù)點與集合Q中數(shù)據(jù)點的距離最小值中最大者，并保存該點至集合Q；

Reduce函數(shù)：

輸入：各節(jié)點中心點的初始集合Q={Q1,Q2,…,Qn}；

輸出：樣本中心點的最終集合U以及半徑T1；

(1)求取集合Q的數(shù)據(jù)總量，N=Count(Q)；

(2)設(shè)置迭代次數(shù)，While k< sqrt(N)；

(3)求數(shù)據(jù)集中數(shù)據(jù)點之間距離最小值中最大者，并保存該點至集合Q′；

(4)求取集合Q′的數(shù)據(jù)量m=Count(Q′)；

(5)whilej

3.3 Canopy劃分

算法4：Canopy劃分算法。

Map函數(shù)：

輸入：初始數(shù)據(jù)集G；

輸出：標(biāo)注對應(yīng)Canopy的數(shù)據(jù)集C。

(1)讀取樣本中心點的最終集合U以及半徑T1，計算初始數(shù)據(jù)集與樣本中心點之間的距離D；

(2)當(dāng)D<=T1，則標(biāo)注該數(shù)據(jù)點屬于對應(yīng)的Canopy，并將結(jié)果輸出。

3.4 K-means迭代

該階段的主要任務(wù)是進行精確的聚類計算，其算法流程為：

算法5：K-Means算法。

輸入：標(biāo)注對應(yīng)Canopy的數(shù)據(jù)集C；

輸出：K中心點集合U′。

Map函數(shù)：

1) 讀取樣本中心點的最終集合U，將樣本中心點的最終集合U作為初始K中心點集合，U′=U；

2)通過Map函數(shù)比較已標(biāo)注的輸入數(shù)據(jù)點與對應(yīng)中心點的距離，輸出當(dāng)前數(shù)據(jù)點及對應(yīng)最近距離的中心點編號；

Reduce函數(shù)：

1)通過Reduce函數(shù)將同一中心點下的數(shù)據(jù)點歸并，計算均值并將結(jié)果輸出作為新的中心點；

2)判斷準(zhǔn)則函數(shù)是否收斂，若收斂則終止程序，否則進行下一輪MapReduce的迭代。

4 實驗結(jié)果

本實驗在Hadoop分布式集群平臺上對多組測試數(shù)據(jù)進行了仿真測試[15]，傳統(tǒng)的K-means算法K：任意選取k個聚類中心點后再用K-means算法進行聚類；改進的Canopy-Kmeans算法CK：首先結(jié)合最大最小原則計算出初始k個Canopy中心點，利用各個Canopy中心點對數(shù)據(jù)集進行粗略地Canopy聚類，再結(jié)合K-means算法對每個Canopy類進行精確地聚類；高效的DM Canopy-Kmeans(Canopy-Kmeans Clustering Algorithm based on Density Method and Max-min Distance Algorithm)算法DMCK：1)結(jié)合密度法和最大最小距離法計算已有的抽樣數(shù)據(jù)對象的k個初聚類中心C；2)利用樣本聚類中心C作為全局?jǐn)?shù)據(jù)對象的初始聚類中心，結(jié)合Canopy算法進行Canopy劃分；3)再利用 K-means算法計算出最終的聚類結(jié)果。數(shù)據(jù)集的記錄數(shù)為n，聚類個數(shù)為k，具體算法為M，迭代次數(shù)為t，算法執(zhí)行時間為T。

實驗一：驗證改進的K-means算法的可行性。

實驗說明：采用50條測試數(shù)據(jù)進行測試，運行結(jié)果見表1。

表1 不同聚類算法和不同聚類個數(shù)的聚類結(jié)果

從表1可以得出以下結(jié)論，改進的Canopy-Kmeans算法運行的聚類結(jié)果與高效的DM Canopy-Kmeans算法的聚類結(jié)果相比，其迭代次數(shù)和運行時間取得了相似的結(jié)果，而且保持了穩(wěn)定性；且改進的Canopy-Kmeans算法與傳統(tǒng)的隨機選擇聚類中心的K-means算法相比，表現(xiàn)出了更好的性能優(yōu)勢。但在處理海量數(shù)據(jù)時，若用改進Canopy-Kmeans算法，聚類迭代次數(shù)會增加，甚至?xí)斐蓛?nèi)存不足。所以提出了這種折中的用樣本數(shù)據(jù)初始聚類中心代替全局?jǐn)?shù)據(jù)初始聚類中心的聚類算法。

實驗二：驗證改進的K-means算法的有效性。

實驗說明：用隨機產(chǎn)生的記錄數(shù)來驗證方法的有效性，記錄數(shù)n(單位：萬)分別是1、10、100，環(huán)境：單機偽分布條件下，聚類方法同上，聚類個數(shù)為100時結(jié)果見表2。

表2 單機下的聚類結(jié)果

通過表2得出以下結(jié)論：改進的Canopy-Kmeans聚類算法在用最大最小原則計算初始聚類中心點時，隨著處理的數(shù)據(jù)規(guī)模的擴大，迭代時間也會隨之增長，會導(dǎo)致算法效率變低。當(dāng)處理的數(shù)據(jù)量不斷增加時，這種改進的聚類算法將不再適用于初始中心點的計算。而提出的高效DM Canopy-Kmeans算法在面對海量數(shù)據(jù)量時，大大減少了執(zhí)行的時間，提高了算法的運行效率和聚類的精度。

實驗三：驗證改進算法可以并行執(zhí)行。

實驗說明：4臺均是裝有Centos5操作系統(tǒng)的虛擬機，其中一臺是master，剩余三臺是slave，內(nèi)存512 M，硬盤100G，2.5Ghz雙核CPU。數(shù)據(jù)：使用實驗2中數(shù)據(jù)，在集群平臺下聚類為100時的運行結(jié)果見表3。

表3 集群下運行結(jié)果

表3與表2對比得出以下結(jié)論，在同樣的條件下，并行化與串行相比，其操作時間明顯是降低的，且提高了算法的運行效率，進一步體現(xiàn)了海量數(shù)據(jù)在集群環(huán)境下處理的優(yōu)勢。

5 結(jié)束語

在處理海量數(shù)據(jù)時，為減少 k-means 算法對初值的依賴性，

我們詳細(xì)探討了初始聚類中心的優(yōu)化選擇問題，并提出全新的 DM Canopy-Kmeans 算法。為提高算法的運行效率，在MapReduce的平臺下對改進聚類算法進行實現(xiàn)。并通過實驗對其進行對比分析，驗證了基于并行模型下的改進算法更優(yōu)于傳統(tǒng)的算法，提高了算法的執(zhí)行效率。下一步的主要工作是進一步改進抽樣數(shù)據(jù)的樣本質(zhì)量，可以用來更精確地代表全局?jǐn)?shù)據(jù)對象。

[1] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113．

[2] Han J, Kamber M. Data Mining: Concepts and Techniques [M]. Fan Ming, Meng Xiaofeng, translation.2 edition. Beijing: Mechanical Industry Press, 2007.

[3] 鄧 海，覃 華，孫 欣．一種優(yōu)化初始中心的K-means 聚類算法[J]．計算機技術(shù)與發(fā)展，2013, 23(11)：42-45.

[4] 王 玲，薄列峰，焦李成．密度敏感的普聚類[J]．電子學(xué)報，2007, 35(8) : 1577-1581.

[5] 馬 帥，王騰蛟，唐世渭，等．一種基于參考點和密度的快速聚類算法[J]．軟件學(xué)報，2003，14(6)：1089-1095.

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

[7] 虞倩倩，戴月明，李晶晶．基于MapReduce的ACO-K-means并行聚類算法[J]．計算機工程與應(yīng)用，2013，49(16)：117-120.

[8] 馬漢達(dá)，郝曉宇，馬仁慶．基于Hadoop的并行PSO-kmeans算法實現(xiàn)Web日志挖掘[J]．計算機科學(xué)，2015,42(6A)：470-473.

[9] 賈瑞玉，管玉勇，李亞龍．基于MapReduce模型的K-means并行遺傳聚類算法[J]．計算機工程與設(shè)計，2014,35(2)：657-660.

[10] Isard M, Budiu M, Yu Y, et al. Dryad: Distributed data-parallel programs from sequential building blocks[A]. Proc. of the 2ndEuropean Conf. on Computer Systems (EuroSys)[C]. 2007：59-72．

[11] 劉遠(yuǎn)超，王曉龍，劉秉權(quán)．一種改進的 K-means 文檔聚類初值選擇算法[J].高技術(shù)通訊，2006(1)：11-15．

[12] 孫吉貴，劉 杰，趙連宇．聚類算法研究[J]．軟件學(xué)報，2008, 19(1)：48-61．

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

[14] Han Jiawei. Kamber. Data mining: Concepts and techniques [M]. Beijing: Mechanical Industry Press. 2008: 288-375 (in Chinese).

[15] Apache．Hadoop[EB/OL].[2012-10-10]．http: //hadoop.apache.org.

Optimization of K-means Clustering Algorithm Based on MapReduce

Sun Yuqiang, Li Yuanyuan, Lu Yong

(School of Information Science&Engineering, ChangZhou University, Changzhou 213164，China)

To deal with the problems that traditional K-means clustering algorithm is very dependent on the selection of the initial points, being prone to clustering result of local optimum rather than global optimum, and it is difficult to meet the need of dealing with massive amounts of data, an improved K-means clustering algorithm based on MapReduce is proposed. The algorithm combines systematic sampling method to get a representative sample set which is used to replace the massive data set; and uses density method and Max-Min distance method to get the optimal initial clustering centers; and adopts Canopy algorithm to get a rough clustering which can reduce the computational scale; and finally employs the idea of sequential composition of MapReduce programming model to realize the parallel extension of the algorithm, which can make full use of the computing and storage capacity of the cluster, in order to adapt to the application of massive data. The improved algorithm is compared with the traditional clustering algorithms in this paper, and the comparative results show that the performance of improved algorithm is better than the latter. The experiments show that the improved method reduces the dependence on the initial cluster centers and also reduces the number of iterations of clustering and the clustering time.Furthermore it shows greater performance advantage in dealing with massive data.

K-means clustering algorithm；sampling； Canopy algorithm；Max-Min distance method

2016-01-19；

2016-02-29。

國家自然科學(xué)基金項目(11271057,51176016)；江蘇省自然科學(xué)基金項目(BK2009535)。

李媛媛(1991-)，女，江蘇鹽城人，碩士研究生，主要從并行計算、數(shù)據(jù)挖掘等方向的研究。

孫玉強(1956-)，男，河南人，教授，碩士研究生導(dǎo)師，主要從事并行計算、軟件工程等方向的研究。

1671-4598(2016)07-0272-04

10.16526/j.cnki.11-4762/tp.2016.07.073

TP311 文獻(xiàn)標(biāo)識碼：A