基于密度峰值優(yōu)化的Canopy-Kmeans并行算法*

李 琪，張 欣，張平康，張 航

0 引 言

聚類分析作為統(tǒng)計(jì)學(xué)的一個(gè)分支，已經(jīng)被廣泛研究和使用了多年。它是數(shù)據(jù)挖掘中非常重要的一部分，是從數(shù)據(jù)中發(fā)現(xiàn)有用信息的一種有效手段。聚類基于“相似同類，相異不同”的思想，將數(shù)據(jù)對(duì)象分組為若干類或簇，使得在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別很大[1]。通過(guò)聚類，人們可以了解數(shù)據(jù)的分布情況，也可能會(huì)發(fā)現(xiàn)數(shù)據(jù)內(nèi)事先未知的群組。

K-means算法是聚類分析中的經(jīng)典算法，自20世紀(jì)60年代提出，已成為目前應(yīng)用最廣泛的聚類方法之一。K-means算法具有理論思想可靠、算法數(shù)學(xué)思想簡(jiǎn)單且易于實(shí)現(xiàn)、收斂速度快等優(yōu)點(diǎn)，但算法本身存在缺陷，需要預(yù)先確定聚類數(shù)目K的值，且隨機(jī)選取的K個(gè)初始中心點(diǎn)可能會(huì)使聚類結(jié)果產(chǎn)生局部最優(yōu)解，算法效果受噪聲點(diǎn)影響大。針對(duì)K-means算法存在的缺點(diǎn)，學(xué)者們從不同角度提出了改進(jìn)方法。文獻(xiàn)[2]提出一種優(yōu)化初始中心點(diǎn)的算法，采用密度敏感的相似性度量來(lái)計(jì)算對(duì)象密度。文獻(xiàn)[3]提出運(yùn)用Canopy[4]算法和K-means算法結(jié)合，解決初始中心點(diǎn)選擇問(wèn)題，但Canopy算法初始參數(shù)的確定也需依靠人工選取，因此效果并不穩(wěn)定。文獻(xiàn)[5]提出了用最大距離法選取初始簇中心的K。文獻(xiàn)[6]提出一種基于最大最小化準(zhǔn)則的Canopy-Kmeans算法。

在學(xué)者們對(duì)傳統(tǒng)K-means算法進(jìn)行改進(jìn)的同時(shí)，互聯(lián)網(wǎng)不斷發(fā)展，數(shù)據(jù)規(guī)模呈現(xiàn)爆炸式增長(zhǎng)，傳統(tǒng)的串行聚類算法已經(jīng)無(wú)法滿足當(dāng)前處理海量數(shù)據(jù)的需求。而基于Spark與Hadoop等的開(kāi)源分布式云計(jì)算平臺(tái)的出現(xiàn)，為解決這一問(wèn)題提供了很好的方案。Spark是一款基于內(nèi)存的分布式計(jì)算框架，計(jì)算中通過(guò)將上一個(gè)任務(wù)的處理結(jié)果緩存在內(nèi)存中，大大節(jié)省了反復(fù)讀寫HDFS花費(fèi)的時(shí)間。

為了進(jìn)一步提高K-means聚類的準(zhǔn)確率和聚類速度，基于以上算法的優(yōu)缺點(diǎn)，結(jié)合Spark計(jì)算框架，本文提出一種基于密度峰值的Canopy-Kmeans并行算法。利用密度峰值[7]的思想和最大最小準(zhǔn)則，結(jié)合Canopy-Kmeans算法，降低了選取初始聚類中心時(shí)離群點(diǎn)對(duì)算法的干擾和陷入局部最優(yōu)的概率，提高了聚類的準(zhǔn)確性，并利用Spark框架將算法并行化，減少了聚類所花費(fèi)的時(shí)間。

1 相關(guān)概念

1.1 Canopy-Kmeans算法

Canopy-Kmeans算法是一種改進(jìn)的K-means算法，其算法思想分為兩個(gè)階段。第一階段利用Canopy算法對(duì)數(shù)據(jù)集合進(jìn)行預(yù)處理，快速將距離較近的數(shù)據(jù)分到一個(gè)子集中，這個(gè)子集稱作Canopy。通過(guò)計(jì)算將得到多個(gè)Canopy，數(shù)據(jù)集中的所有對(duì)象均會(huì)落在Canopy的覆蓋內(nèi)，且Canopy之間可以重疊。第二階段利用得到的Canopy中心點(diǎn)作為K-means算法的初始聚類中心點(diǎn)和K值，在Canopy內(nèi)使用K-means算法直至算法收斂。如果兩個(gè)數(shù)據(jù)對(duì)象不屬于同一個(gè)Canopy，那么它們就不屬于同一個(gè)簇。所以，在迭代過(guò)程中，對(duì)象只需計(jì)算與其在同一個(gè)Canopy下的K-means中心點(diǎn)的距離。

定義1（Canopy集合）：給定數(shù)據(jù)集合S={si|i=1,2,…,n}，對(duì)于?xi∈S，若滿cj||≤T1,cj∈ S,i≠ j}，則稱Pc是以 cj為中心點(diǎn)、以T1為半徑的Canopy集合。

定義2（Canopy中心點(diǎn)）：給定數(shù)據(jù)集合S={si|i=1,2,…,n}，對(duì)于Sxi∈?，若Qm||≤ T2,T2＜T1,Qm∈ S,i≠m}， 則 稱 Qm為 非Canopy候選中心點(diǎn)集合。其中，T1、T2為距離閾值，是預(yù)設(shè)的參數(shù)值，可以通過(guò)交叉檢驗(yàn)得出。

1.2 局部密度

針對(duì)K-means對(duì)孤立點(diǎn)敏感的問(wèn)題，提出一種假設(shè)。對(duì)于一個(gè)數(shù)據(jù)集，若類簇中的一個(gè)點(diǎn)由一些相對(duì)其局部密度較低的點(diǎn)圍繞，那么這個(gè)點(diǎn)為此類簇的密度峰值點(diǎn)[7]。定義為：設(shè)待聚類的數(shù)據(jù)集 S={x1,x2,…,xn}，相應(yīng)的指標(biāo)集為 Is={1,2,…,n}，dij=dist(xi,xj)為數(shù)據(jù)點(diǎn)xi和xj之間的距離，當(dāng)數(shù)據(jù)點(diǎn)為離散值時(shí)，局部密度ρi為：

式中：j與i不相等且都屬于Is，函數(shù)χ(x)為：

其中dc＞0表示截?cái)嗑嚯x，根據(jù)所有點(diǎn)與點(diǎn)之間的歐氏距離小于dc值占總樣本數(shù)的k來(lái)確定[8]，一般在2%～5%；dij為歐式距離。

1.3 最大最小化準(zhǔn)則

在集合S中隨機(jī)選取一個(gè)點(diǎn)作為種子點(diǎn)A，然后計(jì)算A點(diǎn)與集合S中所有剩余點(diǎn)的距離；距離最大的點(diǎn)選為種子點(diǎn)B，計(jì)算A點(diǎn)和B點(diǎn)與集合S中所有剩余點(diǎn)的距離，得出距離兩個(gè)種子點(diǎn)最近的距離da與db；選取da、db中最大值的點(diǎn)作為下一個(gè)種子點(diǎn)C，可表示為：

按照式（3）一直迭代至無(wú)法滿足條件，即可選取出全部的種子點(diǎn)。

2 基于密度峰值的算法改進(jìn)

隨機(jī)選取的Canopy-Kmeans算法，通過(guò)初期Canopy算法對(duì)數(shù)據(jù)集的快速預(yù)聚類，解決了K-means算法的K個(gè)中心點(diǎn)選取問(wèn)題，同時(shí)優(yōu)化了算法復(fù)雜度。但是，由于距離閾值T1、T2的選取需要通過(guò)多次運(yùn)行算法求出最優(yōu)距離，耗費(fèi)了大量時(shí)間。文獻(xiàn)[9]對(duì)此問(wèn)題進(jìn)行了優(yōu)化，避免了人為選取距離閾值T1、T2及Canopy初始中心點(diǎn)的隨機(jī)選取，但并未解決選取的初始中心點(diǎn)可能為噪聲點(diǎn)，從而影響算法的聚類效果。本文引入密度峰值的概念，在選取Canopy中心點(diǎn)前先計(jì)算數(shù)據(jù)集中密度相對(duì)較大的點(diǎn)，剔除低密度區(qū)域的噪聲點(diǎn)，得到一個(gè)高密度點(diǎn)集合W，同時(shí)利用“最大最小化原則”使Canopy初始中心點(diǎn)的距離盡可能大，使算法不易陷入局部最優(yōu)。

“最大最小化準(zhǔn)則”選取的Canopy中心點(diǎn)呈現(xiàn)以下規(guī)律：當(dāng)Canopy中心點(diǎn)個(gè)數(shù)迫近或等于集合的聚類真實(shí)值時(shí)會(huì)產(chǎn)生較大波動(dòng)，而少于或超過(guò)聚類真實(shí)值時(shí)相對(duì)平穩(wěn)[10]。同時(shí)，參考Hearst M A文本自動(dòng)分段算法中的邊界思想，定義[11]為：

當(dāng)值Depth(i)最大時(shí)，Canopy取得最優(yōu)初始中心點(diǎn)個(gè)數(shù)，并令Canopy的T1=min dist(i)。因?yàn)橐呀?jīng)計(jì)算出Canopy中心點(diǎn)，所以不再需要計(jì)算T2。綜上所述，算法的實(shí)現(xiàn)流程圖如圖1所示。

圖1 基于密度峰值優(yōu)化的Canopy-Kmeans流程

具體實(shí)現(xiàn)步驟如下：

（1）對(duì)于數(shù)據(jù)集S={x1,x2,…,xn}，通過(guò)上文中局部密度的定義，在集合S中算出每個(gè)對(duì)象的局部密度，將局部密度低的點(diǎn)剔除后，把剩余的點(diǎn)放入集合W中，并標(biāo)注每個(gè)點(diǎn)的局部密度。

（2）將集合W中局部密度最高的密度峰值點(diǎn)記作初始點(diǎn)A，在集合W中選取距離A最遠(yuǎn)的對(duì)象記作第二個(gè)初始點(diǎn)B；利用最大最小準(zhǔn)則在集合W中計(jì)算第三個(gè)點(diǎn)C，C的取值滿足DistC=Max(min(da,db))，并求出剩余M個(gè)點(diǎn)，M滿足 DistM=Max(min(da,db,…,dm))，且M＜（聚類個(gè)數(shù)K＜[12]）。

（3）計(jì)算Depth(i)，將M個(gè)點(diǎn)中的前i個(gè)對(duì)象賦值給集合U，得到Canopy中心點(diǎn)集合U=(u1,u2,…,ui),同時(shí)令T1=min dist(i)；

（4）輸入Canopy的中心點(diǎn)數(shù)據(jù)集U=(u1,u2,…,ui)，將集合S中的所有點(diǎn)與Canopy中心點(diǎn)進(jìn)行距離比較；小于T1的，標(biāo)注該對(duì)象屬于對(duì)應(yīng)的Canopy，最后生成i個(gè)可相互重疊的Canopy；

（5）在Canopy中應(yīng)用K-means算法進(jìn)行迭代，其中初始中心點(diǎn)為i個(gè)Canopy中心點(diǎn)；迭代過(guò)程中，對(duì)象只需計(jì)算與其在同一個(gè)Canopy下的K-means中心點(diǎn)的距離，直至算法收斂。

3 基于Spark的改進(jìn)算法并行化

Spark[13]是一個(gè)開(kāi)源的基于內(nèi)存的集群運(yùn)算框架，在2009年由美國(guó)加州大學(xué)伯克利分校AMP實(shí)驗(yàn)室開(kāi)發(fā)。由于Hadoop的MapReduce在運(yùn)算過(guò)程中會(huì)將中間結(jié)果寫入硬盤，而頻繁的讀寫硬盤會(huì)大大增加運(yùn)算時(shí)間。Spark使用內(nèi)存運(yùn)算技術(shù)，將中間結(jié)果寫入內(nèi)存，所以基于Spark的算法運(yùn)算速度相比于Hadoop MapReduce大大提升?；谝陨蟽?yōu)點(diǎn)，本文采用Spark框架進(jìn)行算法的并行化計(jì)算，流程如圖2所示。

圖2 算法并行流程

并行化過(guò)程中會(huì)使用Map進(jìn)行局部密度點(diǎn)集合的求取、Canopy中心點(diǎn)的求取和K-means聚類。然后，使用Redcue或reduceByKey實(shí)現(xiàn)全局聚類，再對(duì)配置好的Spark參數(shù)后初始化環(huán)境，讀取存放在HDFS上的數(shù)據(jù)集生成彈性數(shù)據(jù)集RDD并將數(shù)據(jù)向量化。對(duì)RDD使用map操作，求取兩兩對(duì)象間的距離，得出局部密度集合和密度峰值點(diǎn)。使用最大最小化準(zhǔn)則，在局部密度集合中點(diǎn)求取M個(gè)初始值點(diǎn)。匯總各節(jié)點(diǎn)中的初值點(diǎn)到主節(jié)點(diǎn)，計(jì)算深度值Depth(i)得到T1，并將Canopy中心點(diǎn)集合賦值為K-means的Cluster中心點(diǎn)。對(duì)RDD執(zhí)行map操作，在子節(jié)點(diǎn)中將距離小于T1的點(diǎn)劃入同一Canopy。在各節(jié)點(diǎn)上運(yùn)行K-means迭代，只需計(jì)算與中心點(diǎn)屬于同一Canopy的點(diǎn)距離。綜上所述，算法主要可分為以下三部分。

算法1：利用密度峰值計(jì)算局部密度集合

input：節(jié)點(diǎn)數(shù)據(jù)集L=(l1,l2,…,ln)

output：節(jié)點(diǎn)局部密度集合 W=(w1,w2,…,wm)，密度峰值點(diǎn)A

令集合W為空//設(shè)置初始局部密度集合

計(jì)算集合L中兩兩對(duì)象的距離dij；

利用dij求取dc，其中k取2%；

求出每個(gè)點(diǎn)的局部密度ρi；

if ρi＞ 1

將對(duì)應(yīng)的點(diǎn)加入到集合W中；

end if

將ρ值最大的點(diǎn)定義為密度峰值點(diǎn)A。

算法2：Canopy本地中心點(diǎn)生成

Input：局部密度集合W，密度峰值點(diǎn)A，當(dāng)前節(jié)點(diǎn)數(shù)據(jù)集規(guī)模N

output：Canopy中心點(diǎn)集合P=( p1,p2,…,pn)

將A點(diǎn)賦值給p1；

if 集合P中對(duì)象數(shù)為1

計(jì)算數(shù)據(jù)集W中距離p1最遠(yuǎn)的點(diǎn)B；

else

計(jì)算數(shù)據(jù)集W中數(shù)據(jù)點(diǎn)與集合P中所有數(shù)據(jù)點(diǎn)的距離，選最小值中最大者，結(jié)果放于集合P；

end if

end while

算法3：Canopy全局中心點(diǎn)生成

input：子節(jié)點(diǎn)的Canopy中心點(diǎn)集合P=( p1,p2,…,pn)

output：中心點(diǎn)集合U與T1

求取子節(jié)點(diǎn)匯總后集合的數(shù)據(jù)總量N

求取數(shù)據(jù)集中數(shù)據(jù)之間最小距離的最大者，將其保存到集合P'

end while

將P'中對(duì)象數(shù)賦值給k；

while j＜k

計(jì)算集合P'中的最大值并輸出T1，并令集合U的值為集合P'的前i個(gè)對(duì)象

end while

算法4：K-Means迭代

input：中心點(diǎn)集合U=(u1,u2,…,ui)

output：K-means中心點(diǎn)集合U '

令U '=U；

判斷U '是否改變

若U '改變，則將數(shù)據(jù)對(duì)象分配給同Canopy與它距離最小的K-means中心點(diǎn)；

將屬于同一中心點(diǎn)的對(duì)象匯總，計(jì)算新的初始中心點(diǎn)；

輸出新的聚類中心點(diǎn)。

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

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

本文實(shí)驗(yàn)是在Hadoop2.7.2的YARN基礎(chǔ)上部署的Spark框架，Spark版本為2.02。實(shí)驗(yàn)由5臺(tái)PC機(jī)組成，機(jī)器內(nèi)存4 GB，CPU為Intel Core i5處理器，主頻2.5 GHz，硬盤大小160 GB，操作系統(tǒng)版本為CentOS7。

實(shí)驗(yàn)一共選用五個(gè)數(shù)據(jù)集，其中4個(gè)來(lái)自UCI機(jī)器學(xué)習(xí)庫(kù)，分別為Iris、Wine、Waveform和Pima Indians Diabetes，各數(shù)據(jù)集屬性如表1所示；另一個(gè)來(lái)自搜狗實(shí)驗(yàn)室的開(kāi)源分類數(shù)據(jù)庫(kù)，在其中選取文化、財(cái)經(jīng)和體育三個(gè)類別的文檔，各選10 000篇。

表1 UCI數(shù)據(jù)集屬性

4.2 結(jié)果分析

首先用傳統(tǒng)K-means算法、文獻(xiàn)[6]中的Canopy-Kmeans算法（下簡(jiǎn)稱CK-means算法）以及本文利用密度峰值思想改進(jìn)后的算法（下簡(jiǎn)稱M-CKmeans算法），對(duì)前4個(gè)UCI數(shù)據(jù)集進(jìn)行多次計(jì)算后求平均準(zhǔn)確率，以對(duì)比算法的準(zhǔn)確率，結(jié)果如圖3所示。然后，再用以上幾個(gè)算法對(duì)搜狗數(shù)據(jù)集的數(shù)據(jù)進(jìn)行運(yùn)算，結(jié)果如圖4所示。

圖3 UCI數(shù)據(jù)集聚類準(zhǔn)確率

圖4 文本聚類

從圖3、圖4可以看出，本文提出的M-CKmeans算法相比于CK-means算法和傳統(tǒng)K-means算法，在準(zhǔn)確率上均有一定提高，驗(yàn)證了基于密度峰值思想改進(jìn)的Canopy-Kmeans算法的有效性。

加速比是常用來(lái)衡量程序執(zhí)行并行化的重要指標(biāo)[14]，本文用其來(lái)衡量算法在Spark平臺(tái)下的性能。針對(duì)同一算法，用單機(jī)運(yùn)行時(shí)間除以并行運(yùn)行時(shí)間，就可以得到并行算法的加速比。本文將搜狗的開(kāi)源數(shù)據(jù)集用CK-means與M-CKmeans算法多次運(yùn)行后取平均時(shí)間，計(jì)算兩種算法的加速比，結(jié)果如圖5所示；再利用Iris數(shù)據(jù)集構(gòu)造成60維度，不同大小的數(shù)據(jù)集（500 MB，1 GB，2 GB）對(duì)改進(jìn)后的算法進(jìn)行加速比對(duì)比，結(jié)果如圖6所示。

圖5 相同數(shù)據(jù)集不同算法加速比

圖6 不同數(shù)據(jù)大小M-CKmeans加速比

從圖5可以看出，本文的M-CKmeans算法在同一數(shù)據(jù)集下，相同節(jié)點(diǎn)的執(zhí)行效率高于CK-means算法。這主要是因?yàn)樗惴▋?yōu)化了CK-means算法的初始中心點(diǎn)的選取，減少了后續(xù)算法需要迭代的次數(shù)。在保持相同的數(shù)據(jù)規(guī)模下，隨著數(shù)據(jù)節(jié)點(diǎn)數(shù)目的增加，雖然每個(gè)節(jié)點(diǎn)所需處理的數(shù)據(jù)量減小，但因?yàn)楣?jié)點(diǎn)的增加還會(huì)導(dǎo)致節(jié)點(diǎn)間的通信開(kāi)銷增大，所以加速比的增長(zhǎng)速度放緩。從圖6可以看出，隨著數(shù)據(jù)集的增加，并行后的M-CKmeans算法具有良好的加速比。綜上結(jié)果證明，本文算法在Spark環(huán)境下具有較好的加速比，且并行化性能更高。

5 結(jié) 語(yǔ)

文中主要利用密度峰值的思想，先求出各點(diǎn)的局部密度，然后結(jié)合最大最小準(zhǔn)則，優(yōu)化Canopy初始中心點(diǎn)的選擇，同時(shí)利用Spark框架改進(jìn)算法并行化。實(shí)驗(yàn)結(jié)果表明：改進(jìn)后算法在抗噪性、準(zhǔn)確度上有明顯提高，且基于Spark的改進(jìn)算法能夠很好地應(yīng)付大量數(shù)據(jù)，具有可觀的加速比。

[1] Jain A K,Murty.Data Clustering:A Review[J].Acm Computing Surveys,1999,31(03):264-323.

[2] 汪中,劉貴全,陳恩紅.一種優(yōu)化初始中心點(diǎn)的K-means算法[J].模式識(shí)別與人工智能,2009,22(02):299-304.WANG Zhong,LIU Gui-quan,CHEN En-hong.A K-means Algorithm Based on Optimized Initial Center Points[J].Pattern Recognition and Artificial Intelligence,2009,22(02):299-304.

[3] 邱榮太.基于Canopy的K-means多核算法[J].微計(jì)算機(jī)信息,2012(09):486-487.QIU Rong-tai.Canopy for K-Means on Multi-core[J].Microcomputer Information,2012(09):486-487.

[4] Rong C.Using Mahout for Clustering Wikipedia's Latest Articles:A Comparison between K-means and Fuzzy C-means in the Cloud[C].IEEE Third International Conference on Cloud Computing Technology and Science,IEEE Computer Society,2011:565-569.

[5] 翟東海,魚(yú)江,高飛等.最大距離法選取初始簇中心的K-means文本聚類算法的研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(03):713-715.ZHAI Dong-hai,YU Jiang,GAO Fei,et al.K-means Text Clustering Algorithm Based on Initial Cluster Centers Selection According to Maximum Distance[J].Application Research of Computers,2014,31(03):713-715.

[6] 毛典輝.基于MapReduce的Canopy-Kmeans改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(27):22-26.MAO Dian-hui.Improved Canopy-Kmeans Algorithm Based on MapReduce[J].Computer Engineering &Applications,2012,48(27):22-26.

[7] Rodriguez A,Laio A.Machine learning Clustering by Fast Search and Find of Density Peaks[J].Science,2014,344(6191):1492.

[8] 張嘉琪,張紅云.拐點(diǎn)估計(jì)的改進(jìn)譜聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng),2017,38(05):1049-1053.ZHANG Jia-qi,ZHANG Hong-yun.Improved Spectral Clustering Based on Inflexion Point Estimate[J].Journal of Chinese Computer Systems,2017,38(05):1049-1053.

[9] 程堃.基于云平臺(tái)的聚類算法并行化研究[D].南京:南京郵電大學(xué),2015.KUN Cheng.Parallelized Clustering Algorithm Based on the Cloud Platform[D].Nanjing:Nanjing University of Posts and Telecommunications,2015.

[10] 劉遠(yuǎn)超,王曉龍,劉秉權(quán).一種改進(jìn)的k-means文檔聚類初值選擇算法[J].高技術(shù)通訊,2006,16(01):11-15.LIU Yuan-chao,WANG Xiao-long,LIU Bing-quan.An Adapted Algorithm of Choosing Initial Values for k-means Document Clustering[J].Chinese High Technology Letters,2006,16(01):11-15.

[11] Hearst M A.TextTiling:Segmenting Text into Multiparagraph Subtopic Passages[M].MIT Press,1997.

[12] 岑詠華,王曉蓉,吉雍慧.一種基于改進(jìn)K-means的文檔聚類算法的實(shí)現(xiàn)研究[J].現(xiàn)代圖書情報(bào)技術(shù),2008,24(12):73-79.CEN Yong-Hua,WANG Xiao-rong,JI Yong-hui.Algorithm and Experiment Research of Textual Document Clustering Based on Improved K-means[J].New Technology of Library and Information Service,2008,24(12):73-79.

[13] 丁文超,冷冰,許杰等.大數(shù)據(jù)環(huán)境下的安全審計(jì)系統(tǒng)框架[J].通信技術(shù),2016,49(07):909-914.DING Wen-chao,LENG Bing,XU Jie,et al.Security Audit System Framework in Big Data Environment[J].Communications Technology,2016,49(07):909-914.

[14] 陳愛(ài)平.基于Hadoop的聚類算法并行化分析及應(yīng)用研究[D].成都:電子科技大學(xué),2012.CHEN Ai-ping.Parallelized Clustering Algorithm Analysis and Application Based on Hadoop Platform[D].Chengdu:University Of Electronic Science and Technology of China,2012.