基于改進Canopy-K-means算法的并行化研究

王 林，賈鈞琛

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

0 引言

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

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

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

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

1 MapReduce并行框架

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

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

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

2.1 Canpoy-K-means算法研究

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

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

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

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

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

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

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

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

2.2 Canpoy算法改進

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

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

(1)

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

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

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

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

(2)

當i接近真實聚類簇數時，Depth(i)取得最大值，此時設置T1=DistMin(i)使得聚類結果最優。

2.3 K-means算法改進

傳統K-means算法需要迭代計算數據對象與中心點的間距，完成數據對象的劃分，然而在該過程中存在許多不必要的距離計算，為了減少K-means算法的計算量，加快算法的收斂速度，本文引入三角不等式定理對其進行優化改進[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，根據三角不等式定理可得：d(x,b)+d(b,c)≥d(x,c)，但是為了避免計算距離d(x,b)，需要得到d(x,b)≤d(x,c)這個不等式關系，給出引理及其證明過程如下：

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

證明：假設有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)：因此可以得到結論d(xp,ci)≤d(xp,cj)，即向量xp屬于簇中心ci。

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

2.4 改進算法的MapReduce并行化實現

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

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

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

Map函數

輸入：節點數據集合List

輸出：節點Canopy中心點集合Ci

1)Ci=null

2)While (List!=null)

3)If (Ci=null)

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

5)Else if (Ci!=null)

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

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

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

9)End If

10)End While

11)output(Ci)

Reduce函數：

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

輸出：Canopy中心點集合U；

1)計算集合C中的數據總量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函數、Combine函數和Reduce函數三部分組成。算法的偽代碼如下：

Map函數

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

輸出：聚類中心點集合W

1)While (W!=U)

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

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

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

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

6)If (X!=null)

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

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

9)If (W=W′)

10)Break

11)Else 返回2)重新計算

12)End While

Combine函數：

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

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

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

Reduce函數：

輸入：X中數據點所對應下標key，key值所屬的鍵值對列表

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

1)初始化Num=0，記錄所屬簇內數據點的個數

2)While (X.hasNext())

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

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

5)Num+num

6)End While

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

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

3 實驗與分析

3.1 實驗環境及測試數據集

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

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

3.2 實驗結果與分析

3.2.1 算法準確率分析

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

表1 文本聚類測試結果

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

3.2.2 算法擴展性分析

加速比是常用來衡量程序并行化執行效率的重要指標。它的定義如下：Sp=Ts/Tp。此處，為在單機條件之下算法運行的具體時長，而Tp則是在并行條件之下算法運行的具體時長。加速比Sp越大，表示算法的效率越高。考慮到單機環境處理大規模數據時系統容易崩潰，因此本文以1個數據節點下算法的執行時長作為。

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

圖2 相同數據集不同算法加速比

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

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

圖3 改進算法在不同數據集下的加速比

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

4 結束語

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