基于改進(jìn)Canopy-K-means算法的并行化研究

王 林，賈鈞琛

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，西安 710048)

0 引言

隨著互聯(lián)網(wǎng)普及率的不斷提高，網(wǎng)絡(luò)數(shù)據(jù)呈幾何級(jí)增長(zhǎng)，面對(duì)海量以及快速增長(zhǎng)的網(wǎng)絡(luò)數(shù)據(jù)，通過(guò)聚類(lèi)分析可以快速準(zhǔn)確地從中挖掘出價(jià)值信息。但是，傳統(tǒng)的聚類(lèi)算法無(wú)論是在聚類(lèi)精度，還是在執(zhí)行時(shí)間上都已經(jīng)不能很好地滿(mǎn)足當(dāng)前需求，利用分布式計(jì)算框架對(duì)其進(jìn)行并行化改進(jìn)，不僅可以縮短聚類(lèi)時(shí)間，還可以增強(qiáng)算法的擴(kuò)展性，更好地滿(mǎn)足當(dāng)下數(shù)據(jù)挖掘的需要。

K-means算法作為一種具有代表性的聚類(lèi)算法，具備較快的收斂速度、可靠的理論以及容易實(shí)現(xiàn)等諸多優(yōu)勢(shì)，因而被人們廣泛應(yīng)用于各行各業(yè)，但是算法也存在聚類(lèi)中心點(diǎn)的選取具有隨機(jī)性，需要提前確定聚類(lèi)個(gè)數(shù)等不足[1]。對(duì)此，許多學(xué)者對(duì)K-means算法進(jìn)行了改進(jìn)并取得了一定的成果。

鄧海等人[2]結(jié)合密度法和“最大最小原則”優(yōu)化K-means初始聚類(lèi)中心點(diǎn)的選擇，算法準(zhǔn)確率得到提高，但是改進(jìn)后算法的時(shí)間復(fù)雜度較高，運(yùn)行時(shí)間較長(zhǎng)。趙慶等人[3]通過(guò)Canopy算法對(duì)數(shù)據(jù)集進(jìn)行“粗”聚類(lèi)，避免了傳統(tǒng)K-means中心點(diǎn)選取存在的盲目性，極大提升了其準(zhǔn)確性，然而在采用Canopy算法初始閾值需要人為指定，所以聚類(lèi)結(jié)果不穩(wěn)定。劉紀(jì)偉等人[4]結(jié)合密度思想優(yōu)化了K-means初始中心點(diǎn)的選取，同時(shí)引入聚類(lèi)有效性判別函數(shù)確定值，提高了算法的準(zhǔn)確度，但是也增加了算法的運(yùn)行時(shí)間，執(zhí)行效率較低。李曉瑜等人[5]結(jié)合MapReduce分布式框架并行化實(shí)現(xiàn)改進(jìn)的Canopy-K-means算法，并行化實(shí)現(xiàn)的算法具有良好的準(zhǔn)確率和擴(kuò)展性，但是Canopy算法初始閾值人為指定的問(wèn)題仍然存在。

上述工作均是針對(duì)K-means算法初始中心點(diǎn)隨機(jī)選取的不足進(jìn)行改進(jìn)，一定程度上提高了算法的聚類(lèi)準(zhǔn)確度，然而仍舊存在不足。本文首先針對(duì)Canopy-K-means算法中Canopy中心點(diǎn)隨機(jī)選取的不足，引入“最大最小原則”進(jìn)行優(yōu)化，此外，定義深度指標(biāo)計(jì)算公式，確定Canopy中心點(diǎn)的最優(yōu)個(gè)數(shù)及區(qū)域半徑；接著借助三角不等式定理對(duì)K-means算法進(jìn)行優(yōu)化，減少冗余的距離計(jì)算，加快收斂速度；最后結(jié)合MapReduce分布式框架將改進(jìn)后的算法并行化實(shí)現(xiàn)。在構(gòu)建的微博文本數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明改進(jìn)算法的準(zhǔn)確率和擴(kuò)展性都得到提升。

1 MapReduce并行框架

MapReduce[6]是一種用于處理大規(guī)模數(shù)據(jù)的分布式編程模型，可以將大型任務(wù)進(jìn)行拆分處理，從而加快數(shù)據(jù)的處理效率。

MapReduce主要包括Map和Reduce兩個(gè)函數(shù)，在數(shù)據(jù)處理過(guò)程中，數(shù)據(jù)均以鍵/值對(duì)形式保存。其中，Map函數(shù)根據(jù)用戶(hù)輸入的鍵/值對(duì)生成中間結(jié)果，而Reduce函數(shù)對(duì)中間結(jié)果進(jìn)行歸并處理，得到的最終結(jié)果同樣以鍵/值對(duì)形式輸出。除了Map和Reduce兩個(gè)核心函數(shù)外，還提供了Combine函數(shù)，它在Map后調(diào)用，相當(dāng)于本地的Reduce，主要是為了減少?gòu)腗ap到Reduce的數(shù)據(jù)量。

2 Canpoy-K-means聚類(lèi)算法研究與改進(jìn)

2.1 Canpoy-K-means算法研究

K-means算法由于算法簡(jiǎn)單、易于實(shí)現(xiàn)等優(yōu)點(diǎn)而被廣泛使用。其基本思想是：從數(shù)據(jù)集中隨機(jī)選取K個(gè)數(shù)據(jù)對(duì)象作為初始聚類(lèi)中心點(diǎn)；將剩余數(shù)據(jù)對(duì)象和簇中心進(jìn)行間距計(jì)算，并且把它劃至間距最短的簇中，持續(xù)該過(guò)程，直到數(shù)據(jù)集為空集；然后根據(jù)簇中的數(shù)據(jù)對(duì)象計(jì)算新的聚類(lèi)中心點(diǎn)，繼續(xù)上述過(guò)程，直到簇的中心點(diǎn)不再發(fā)生變化或者符合停止條件，迭代才會(huì)停止，完成聚類(lèi)劃分。

Canpoy-K-means算法是一種借助Canpoy算法改進(jìn)的K-means算法。在Canpoy-K-means算法中，通過(guò)Canpoy算法對(duì)數(shù)據(jù)集進(jìn)行“粗”聚類(lèi)，得到個(gè)Canpoy子集，隨后再以個(gè)Canopy子集的中心點(diǎn)作為K-means算法的初始中心點(diǎn)進(jìn)行“細(xì)”聚類(lèi)，生成聚類(lèi)結(jié)果。Canpoy-K-means算法執(zhí)行步驟如下：

1)將待聚類(lèi)數(shù)據(jù)集構(gòu)成List集合，然后指定兩個(gè)距離閾值T1和T2(T1>T2)；

2)隨機(jī)選取List合中的一個(gè)數(shù)據(jù)對(duì)象P，構(gòu)成一個(gè)新的Canpoy，并將對(duì)象P從集合List中移除；

3)對(duì)于List中剩余的數(shù)據(jù)對(duì)象，計(jì)算與對(duì)象P之間的距離。如果間距小于T1，就把它分配到對(duì)象P所在的Canpoy中；如果與對(duì)象P的間距小于T2，則將它從List中刪除；

4)重復(fù)步驟2)和3)，直到List為空；

5)將形成的Canpoy子集數(shù)目作為K值，Canpoy子集的中心點(diǎn)作為初始的聚類(lèi)中心點(diǎn)進(jìn)行K-means聚類(lèi)，得到較為準(zhǔn)確的聚類(lèi)結(jié)果。

Canpoy-K-means算法雖然解決了K-means算法人為指定值和初始中心點(diǎn)隨機(jī)選取的不足，然而其也存在不足：Canopy的初始聚類(lèi)中心點(diǎn)隨機(jī)選取和初始閾值人為指定，具有盲目性，初始閾值對(duì)聚類(lèi)所得的最終結(jié)果具有顯著影響，一定程度上降低了聚類(lèi)結(jié)果的穩(wěn)定性；另外，由于其具備較高的時(shí)間復(fù)雜度，串行執(zhí)行過(guò)程時(shí)所需時(shí)間較長(zhǎng)，算法串行執(zhí)行效率較低。

2.2 Canpoy算法改進(jìn)

為了改善Canopy算法初始閾值人為指定以及初始中心點(diǎn)隨機(jī)選取的不足，本文引入“最大最小原則”對(duì)其進(jìn)行優(yōu)化，提高算法的準(zhǔn)確率以及聚類(lèi)結(jié)果的穩(wěn)定性。

基于“最大最小原則”的中心點(diǎn)選取方法基本思想如下：在將數(shù)據(jù)集劃分為若干個(gè)Canopy的過(guò)程中，任意兩個(gè)Canopy中心點(diǎn)之間的距離應(yīng)盡可能遠(yuǎn)，即假設(shè)目前已生成個(gè)Canopy中心點(diǎn)，則處于第n+1位的Canopy中心點(diǎn)應(yīng)為其它數(shù)據(jù)點(diǎn)和前n個(gè)中心點(diǎn)間最短間距的最大者[7]，其公式如下：

(1)

式中，dn表示第n個(gè)中心點(diǎn)與候選數(shù)據(jù)點(diǎn)的最小距離；DistList表示前n個(gè)中心點(diǎn)與候選數(shù)據(jù)點(diǎn)最小距離的集合；DistMin(n+1)則表示集合DistList中最小距離的最大者，即Canopy集合n+1的第個(gè)中心點(diǎn)。

基于“最大最小原則”的Canopy中心點(diǎn)選擇方法，在實(shí)際應(yīng)用中符合下述情況：如果中心點(diǎn)數(shù)量和最佳中心點(diǎn)的數(shù)量較為接近，此時(shí)DistMin(n+1)具備最大的變化幅度。所以，為了確定最優(yōu)的Canopy中心點(diǎn)個(gè)數(shù)及區(qū)域半徑Depth(i)，根據(jù)參考文獻(xiàn)[8]提出的邊界思想，采用深度指標(biāo)T1，描述Canopy中心點(diǎn)的變化幅度，如公式(2)所示：

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

|DistMin(i+1)-DistMin(i)|

(2)

當(dāng)i接近真實(shí)聚類(lèi)簇?cái)?shù)時(shí)，Depth(i)取得最大值，此時(shí)設(shè)置T1=DistMin(i)使得聚類(lèi)結(jié)果最優(yōu)。

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

傳統(tǒng)K-means算法需要迭代計(jì)算數(shù)據(jù)對(duì)象與中心點(diǎn)的間距，完成數(shù)據(jù)對(duì)象的劃分，然而在該過(guò)程中存在許多不必要的距離計(jì)算，為了減少K-means算法的計(jì)算量，加快算法的收斂速度，本文引入三角不等式定理對(duì)其進(jìn)行優(yōu)化改進(jìn)[9]。

定理1：任意一個(gè)三角形，兩邊之和大于第三邊，兩邊之差小于第三邊。由于歐式距離也滿(mǎn)足三角不等式的特性，因此將其擴(kuò)展到多維的歐幾里得空間可知：對(duì)于歐式空間的任意向量x、b、c，滿(mǎn)足：d(x,b)+d(b,c)≥d(x,c)和d(x,b)-d(b,c)≤d(x,c) 成立。

對(duì)于任意一個(gè)向量x和兩個(gè)聚類(lèi)中心b、c，根據(jù)三角不等式定理可得：d(x,b)+d(b,c)≥d(x,c)，但是為了避免計(jì)算距離d(x,b)，需要得到d(x,b)≤d(x,c)這個(gè)不等式關(guān)系，給出引理及其證明過(guò)程如下：

引理1：假設(shè)xp是數(shù)據(jù)集中的任意一個(gè)向量，ci是向量xp當(dāng)前的簇中心，d(xp,ci)已知且cj是除ci外的任意一個(gè)簇中心，如果2d(xp,ci)≤d(ci,cj)，則有d(xp,ci)≤d(xp,cj)。

證明：假設(shè)有2d(xp,ci)≤d(ci,cj)，兩邊同時(shí)減去，得d(xp,ci)≤d(ci,cj)-d(xp,ci)，由定理1可得d(ci,cj)-d(xp,ci)≤d(xp,cj)：因此可以得到結(jié)論d(xp,ci)≤d(xp,cj)，即向量xp屬于簇中心ci。

根據(jù)引理的推導(dǎo)過(guò)程可知，基于三角不等式的改進(jìn)方法可以有效減少K-means冗余的距離計(jì)算，應(yīng)用如下：已知是數(shù)據(jù)集中任意一個(gè)向量，ci是向量的當(dāng)前簇中心，d(xp,ci)已知且cj是另外的任一簇中心，根據(jù)引理1可知，如果2d(xp,cj)≤d(ci,cj)，則可以確定數(shù)據(jù)向量xp屬于簇中心ci，此時(shí)就不再需要計(jì)算d(xp,cj)。

2.4 改進(jìn)算法的MapReduce并行化實(shí)現(xiàn)

本文主要從兩方面對(duì)Canopy-K-means算法進(jìn)行改進(jìn)，首先引入“最大最小原則”優(yōu)化Canopy中心點(diǎn)的選取；接著利用三角不等式對(duì)K-means算法進(jìn)行優(yōu)化，減少冗余的距離計(jì)算，加快算法的收斂速度。改進(jìn)后的算法主要分為兩個(gè)階段，其流程如圖1所示。

圖1 改進(jìn)Canopy-K-means算法流程圖

階段一：基于“最大最小原則”改進(jìn)的Canopy算法在MapReduce框架上的并行化實(shí)現(xiàn)，用來(lái)選取初始聚類(lèi)中心點(diǎn)及K值。該階段由Map函數(shù)和Reduce函數(shù)兩部分完成。算法的偽代碼如下：

Map函數(shù)

輸入：節(jié)點(diǎn)數(shù)據(jù)集合List

輸出：節(jié)點(diǎn)Canopy中心點(diǎn)集合Ci

1)Ci=null

2)While (List!=null)

3)If (Ci=null)

4)在List中隨機(jī)選取一個(gè)數(shù)據(jù)點(diǎn)作為Canopy中心點(diǎn)，保存至Ci中，并將該數(shù)據(jù)點(diǎn)從中刪除

5)Else if (Ci!=null)

6)遍歷計(jì)算中的數(shù)據(jù)點(diǎn)到集合Ci各個(gè)中心點(diǎn)的距離，取距離的最小值dn保存到集合中

7)求出集合D中的最大值Max(D)

8)把Max(D)對(duì)應(yīng)的數(shù)據(jù)點(diǎn)作為Canopy集合的下一個(gè)中心點(diǎn)，存入集合Ci中

9)End If

10)End While

11)output(Ci)

Reduce函數(shù)：

輸入：各個(gè)節(jié)點(diǎn)在Map階段產(chǎn)生的局部中心點(diǎn)集合C{C1,C2,C3,…,Cn}

輸出：Canopy中心點(diǎn)集合U；

1)計(jì)算集合C中的數(shù)據(jù)總量K=Count(C)且令j=0

2)while(j

3)計(jì)算全局Canopy中心點(diǎn)集合C中Depth(i)的最大值

4)令T1=Max(Depth(i))，j++

5)把集合C中的前i個(gè)中心點(diǎn)賦值給集合U

6)End While

7)K=Count(U)

8)OutPut(U)

階段二：將階段一得到的Canopy中心點(diǎn)作為初始中心點(diǎn)完成K-means聚類(lèi)。此外，在此階段引入三角不等式定理，減少迭代過(guò)程中不必要的距離計(jì)算。該階段由Map函數(shù)、Combine函數(shù)和Reduce函數(shù)三部分組成。算法的偽代碼如下：

Map函數(shù)

輸入：K值和Canopy中心點(diǎn)集合U，數(shù)據(jù)集X={x1,x2,x3,…,xn}

輸出：聚類(lèi)中心點(diǎn)集合W

1)While (W!=U)

2)計(jì)算集合U任意兩中心點(diǎn)間的距離d(c,c′)

3)保存最短距離S(c)=min(d(c,c′))

4)計(jì)算數(shù)據(jù)集X中的數(shù)據(jù)點(diǎn)到集合U中第i個(gè)中心點(diǎn)的距離dist[i]

5)If (2dist[i]≤S(c))，則標(biāo)記該數(shù)據(jù)點(diǎn)屬于第i個(gè)Canopy中心點(diǎn)的簇，然后從X中刪除該數(shù)據(jù)點(diǎn)；對(duì)于不符合條件的數(shù)據(jù)點(diǎn)，保存其到該中心點(diǎn)的距離

6)If (X!=null)

7)計(jì)算不符合條件的數(shù)據(jù)點(diǎn)與中心點(diǎn)的距離，將其劃分給距離最小的簇中心并進(jìn)行標(biāo)記

8)計(jì)算被標(biāo)記點(diǎn)的新簇中新W′

9)If (W=W′)

10)Break

11)Else 返回2)重新計(jì)算

12)End While

Combine函數(shù)：

輸入：X中數(shù)據(jù)點(diǎn)所屬簇下標(biāo)key，key值所屬的鍵值對(duì)列表

輸出：X中數(shù)據(jù)點(diǎn)所屬簇下標(biāo)key，各個(gè)簇內(nèi)被標(biāo)記數(shù)據(jù)點(diǎn)的各維累加值以及值key所屬的鍵值對(duì)列表；

在本地解析各維坐標(biāo)值，求出各維的累加值，并保存到對(duì)應(yīng)列表中。

Reduce函數(shù)：

輸入：X中數(shù)據(jù)點(diǎn)所對(duì)應(yīng)下標(biāo)key，key值所屬的鍵值對(duì)列表

輸出：X中數(shù)據(jù)點(diǎn)所屬簇的下標(biāo)key，最終的簇心W

1)初始化Num=0，記錄所屬簇內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)

2)While (X.hasNext())

3)解析X.next()中的各維下標(biāo)值，計(jì)算樣本個(gè)數(shù)num

4)計(jì)算各維下標(biāo)值的累加和并進(jìn)行存儲(chǔ)

5)Num+num

6)End While

7)用各維下標(biāo)的累加和除以Num，計(jì)算新的簇中心W

Reduce函數(shù)結(jié)束后，對(duì)比新生成的簇心和之前的簇心是否相同，若簇中心相同，則算法結(jié)束，否則繼續(xù)執(zhí)行上述過(guò)程，直到簇中心不再變化。

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

3.1 實(shí)驗(yàn)環(huán)境及測(cè)試數(shù)據(jù)集

本文的Hadoop集群環(huán)境搭建在一臺(tái)I7CPU，16 G內(nèi)存，2 TB硬盤(pán)服務(wù)器之上。集群包括1個(gè)Master節(jié)點(diǎn)和5個(gè)Slave節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)均為2 GB內(nèi)存，200 G硬盤(pán)，操作系統(tǒng)為CentOs 6.5，jdk為jdk1.8.0_181，Hadoop版本為2.7.3，程序開(kāi)發(fā)工具為Eclipse，算法全部由Java語(yǔ)言完成。

實(shí)驗(yàn)的數(shù)據(jù)集是經(jīng)過(guò)中文分詞、去停去重和文本特征提取等預(yù)處理后的微博數(shù)據(jù)。本文共構(gòu)造了100 M、500 M、1 G和2 G這4個(gè)數(shù)據(jù)量依次遞增的微博數(shù)據(jù)集，用于改進(jìn)Canopy-K-means算法的測(cè)試。

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

3.2.1 算法準(zhǔn)確率分析

本文以準(zhǔn)確率(precision)、召回率(recall)和F值作為評(píng)判指標(biāo)[10]。對(duì)比傳統(tǒng)K-means算法(算法1)，Canopy-K-means算法(算法2)以及本文改進(jìn)算法(算法3)在文本聚類(lèi)上的優(yōu)劣，分別在100 M、500 M、1 G和2 G數(shù)據(jù)集各聚類(lèi)10次，取各項(xiàng)指標(biāo)的平均值進(jìn)行比較，結(jié)果如表1所示。

表1 文本聚類(lèi)測(cè)試結(jié)果

由表1中的測(cè)試結(jié)果可知，與常規(guī)K-means算法相比，Canopy-K-means算法的準(zhǔn)確率提升了約10%，而本文改進(jìn)算法與Canopy-K-means算法相比，準(zhǔn)確率提升了約7%。這是由于改進(jìn)后的Canopy-K-means算法，優(yōu)化了Canopy的中心點(diǎn)的選取，根據(jù)深度指標(biāo)計(jì)算公式，確定了Canopy中心點(diǎn)的最優(yōu)個(gè)數(shù)與最佳區(qū)域半徑，從而使得聚類(lèi)結(jié)果更加穩(wěn)定，算法的準(zhǔn)確率得到提高。

3.2.2 算法擴(kuò)展性分析

加速比是常用來(lái)衡量程序并行化執(zhí)行效率的重要指標(biāo)。它的定義如下：Sp=Ts/Tp。此處，為在單機(jī)條件之下算法運(yùn)行的具體時(shí)長(zhǎng)，而Tp則是在并行條件之下算法運(yùn)行的具體時(shí)長(zhǎng)。加速比Sp越大，表示算法的效率越高。考慮到單機(jī)環(huán)境處理大規(guī)模數(shù)據(jù)時(shí)系統(tǒng)容易崩潰，因此本文以1個(gè)數(shù)據(jù)節(jié)點(diǎn)下算法的執(zhí)行時(shí)長(zhǎng)作為。

為了對(duì)比改進(jìn)后算法和未改進(jìn)算法在擴(kuò)展性上的差異。使用K-means算法、Canopy-K-means算法以及改進(jìn)的Canopy-K-means算法分別對(duì)1 G的數(shù)據(jù)集進(jìn)行5次聚類(lèi)運(yùn)算，取其平均運(yùn)算時(shí)長(zhǎng)，計(jì)算其加速比，測(cè)試結(jié)果如圖2所示。

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

根據(jù)圖2可知，在相同規(guī)模節(jié)點(diǎn)數(shù)目下，本文改進(jìn)算法的執(zhí)行效率明顯優(yōu)于其它兩種算法，這是由于“最大最小原則”的中心點(diǎn)選取方法優(yōu)化了Canopy中心點(diǎn)的選取，減少了算法的迭代次數(shù)，并且基于三角不等式定理改進(jìn)的K-means算法，有效減少了迭代過(guò)程中存在的冗余距離計(jì)算，算法的執(zhí)行速度得到提高。

為了驗(yàn)證改進(jìn)后算法在不同數(shù)據(jù)集上的并行執(zhí)行效率，分別使用100 M、500 M、1 G和2 G這4個(gè)數(shù)據(jù)集，在節(jié)點(diǎn)個(gè)數(shù)為1、3、5的Hadoop集群上聚類(lèi)5次，取其平均運(yùn)算時(shí)長(zhǎng)，計(jì)算加速比。結(jié)果如圖3所示。

圖3 改進(jìn)算法在不同數(shù)據(jù)集下的加速比

根據(jù)圖3可知，由于100 M的數(shù)據(jù)集相對(duì)較小，在集群的節(jié)點(diǎn)為2時(shí)，算法的加速比有所提升，此時(shí)，數(shù)據(jù)處理時(shí)長(zhǎng)超過(guò)節(jié)點(diǎn)間的通信時(shí)長(zhǎng)；當(dāng)集群節(jié)點(diǎn)為3時(shí)，算法的加速比趨于平穩(wěn)，說(shuō)明此時(shí)集群資源的利用率最高；然后隨著節(jié)點(diǎn)數(shù)目的不斷增加，加速比略有下降，說(shuō)明此時(shí)處理數(shù)據(jù)的時(shí)間要小于節(jié)點(diǎn)間的通信時(shí)間，集群資源得到浪費(fèi)。對(duì)于500 M、1 G、2 G這些數(shù)據(jù)規(guī)模較大數(shù)據(jù)集來(lái)說(shuō)，隨著節(jié)點(diǎn)數(shù)目的增加，算法的加速比呈現(xiàn)上升狀態(tài)，并且由數(shù)據(jù)規(guī)模為500 M的加速比變化曲線(xiàn)可以看出，隨著節(jié)點(diǎn)數(shù)目的不斷增加，加速比增長(zhǎng)的幅度在逐漸變小。由此可以看出改進(jìn)后的Canopy-K-means算法在并行化執(zhí)行時(shí)能夠有效提升聚類(lèi)效率，并且數(shù)據(jù)量越大時(shí)算法的效率越高。

4 結(jié)束語(yǔ)

本文通過(guò)引入“最大最小原則”來(lái)優(yōu)化Canopy中心點(diǎn)的選取，進(jìn)而定義深度指標(biāo)計(jì)算公式，計(jì)算得到最佳的Canopy個(gè)數(shù)及區(qū)域半徑，避免了傳統(tǒng)Canopy算法初始閾值人為指定的問(wèn)題；接著借助三角不等式定理對(duì)K-means算法進(jìn)行優(yōu)化，減少冗余的距離計(jì)算，加快收斂速度；最后結(jié)合MapReduce分布式框架將改進(jìn)后的算法并行化實(shí)現(xiàn)，在構(gòu)建的微博文本數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明改進(jìn)算法的準(zhǔn)確率和擴(kuò)展性都得到提升。但是，由于Canopy中心點(diǎn)的計(jì)算花費(fèi)時(shí)間較長(zhǎng)，如何在保證聚類(lèi)準(zhǔn)確度的同時(shí)，提高Canopy中心點(diǎn)的生成效率還有待研究。