王 林，賈鈞琛

(西安理工大學 自動化與信息工程學院，西安 710048)

0 引言

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

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

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

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

1 MapReduce并行框架

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

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

2 Canpoy-K-means聚類算法研究與改進

2.1 Canpoy-K-means算法研究

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

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

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

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

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

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

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

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

2.2 Canpoy算法改進

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

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

(1)

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

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

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

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

(2)

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

2.3 K-means算法改進

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

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

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

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

證明：假設(shè)有2d(xp,ci)≤d(ci,cj)，兩邊同時減去，得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ù)引理的推導過程可知，基于三角不等式的改進方法可以有效減少K-means冗余的距離計算，應(yīng)用如下：已知是數(shù)據(jù)集中任意一個向量，ci是向量的當前簇中心，d(xp,ci)已知且cj是另外的任一簇中心，根據(jù)引理1可知，如果2d(xp,cj)≤d(ci,cj)，則可以確定數(shù)據(jù)向量xp屬于簇中心ci，此時就不再需要計算d(xp,cj)。

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

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

圖1 改進Canopy-K-means算法流程圖

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

Map函數(shù)

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

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

1)Ci=null

2)While (List!=null)

3)If (Ci=null)

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

5)Else if (Ci!=null)

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

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

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

9)End If

10)End While

11)output(Ci)

Reduce函數(shù)：

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

輸出：Canopy中心點集合U；

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

2)while(j

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

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

5)把集合C中的前i個中心點賦值給集合U

6)End While

7)K=Count(U)

8)OutPut(U)

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

Map函數(shù)

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

輸出：聚類中心點集合W

1)While (W!=U)

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

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

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

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

6)If (X!=null)

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

8)計算被標記點的新簇中新W′

9)If (W=W′)

10)Break

11)Else 返回2)重新計算

12)End While

Combine函數(shù)：

輸入：X中數(shù)據(jù)點所屬簇下標key，key值所屬的鍵值對列表

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

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

Reduce函數(shù)：

輸入：X中數(shù)據(jù)點所對應(yīng)下標key，key值所屬的鍵值對列表

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

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

2)While (X.hasNext())

3)解析X.next()中的各維下標值，計算樣本個數(shù)num

4)計算各維下標值的累加和并進行存儲

5)Num+num

6)End While

7)用各維下標的累加和除以Num，計算新的簇中心W

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

3 實驗與分析

3.1 實驗環(huán)境及測試數(shù)據(jù)集

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

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

3.2 實驗結(jié)果與分析

3.2.1 算法準確率分析

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

表1 文本聚類測試結(jié)果

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

3.2.2 算法擴展性分析

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

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

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

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

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

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

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

4 結(jié)束語

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