分布式MVC-Kmeans算法設計與實現

(長江大學電子信息學院,湖北 荊州 434023)

K-means算法[1]和Canopy算法[2]都屬聚類成員，是一種無監督的模式分類法[3]。K-means算法實現簡單，收斂速度快，但其聚類質量受初始聚類中心選取和類簇數影響較大。文獻[4]以聚類對象分布密度為基礎來確定初始聚類中心的選取；文獻[5]采用最大距離不斷劃分最大距離簇，得到相距較遠的初始聚類中心；文獻[6]以數據點的距離構成最小生成樹，對樹剪枝將數據劃分為k個初始聚類簇，獲得初始聚類中心；文獻[7]引入Canopy算法進行“粗”聚類，獲得了K-means算法的類簇數k和聚類中心。

以上這些方法都只是在串行化條件下對K-means進行了改進，隨著數據量增長，傳統K-means以及改進的K-means算法已很難滿足需求，因此，學者們提出了基于云平臺的分布式K-means方法。文獻[8]采用最小加權距離確定數據點被劃歸的類簇，增加收斂性判定，最終聚類準確率、收斂時間都有明顯提升，并利用Hadoop平臺[9]的MapReduce編程框架[10]，將算法擴展至大規模數據集，擴展性和加速比的結果表明該算法適于海量數據處理。文獻[11]根據樣本密度剔除孤立點，利用最大最小化距離思想選擇k個初始中心，使初始聚類中心點得到優化，利用MapReduce模型進行了并行化處理，提高了聚類結果準確率和穩定性,同時很好地將算法擴展至大規模數據處理。文獻[12]引入Canopy算法優化K-means初始中心的選取，并利用MapReduce框架進行并行化，算法能獲得較好的執行效率和優良的擴展性，適合海量數據的聚類分析。

針對文獻[7]和文獻[12]引入的Canopy算法未考慮任選的初始中心可能是離散點或是孤立點的問題，筆者以樣本密度表征類內聚集度[13]程度，利用樣本方差和最小方差改進Canopy算法的初始中心選取，并參照文獻[6，7]設定了Canopy中的閾值，提出了一種利用最小方差獲取Canopy最優全局中心作為K-means聚類中心初值的算法(簡稱MVC-Kmeans，K-means based on the Minimum Variance Canopy)。

1 相關知識

在實際應用中，K-means算法通過設置k個初始聚類中心，對待測數據集根據距離準則反復迭代更新聚類中心并進行聚類劃分直至收斂；Canopy算法根據隨機選取的初始Canopy中心和給定的閾值T1和T2(T1>T2)[14]，按照距離準則對待測數據集進行閾值劃分，最終生成互相重疊的Canopy類。通常k值、初始聚類中心以及T1和T2大多根據經驗或者隨機選取，帶有很強盲目性，對最終聚類質量有較大影響。因此對上述初值確定是筆者研究重點。

設待聚類數據集為D={xi|xi∈Rm,i=1,2,3,…,n}，其中數據集每個樣本擁有m個屬性，數據xi可表示為xi=(xi1,xi2,…,xim)。

定義1樣本xi和xj的歐氏距離：

(1)

定義2樣本xi到所有樣本距離的平均值：

(2)

定義3樣本xi的方差：

(3)

定義4待聚類數據集的平均距離：

(4)

定義5誤差平方和：

(5)

2 分布式MVC-Kmeans算法思想

圖1 MVC-Kmeans執行流程圖

依據樣本方差原理，數據集中樣本方差的大小，直接決定樣本在數據集中的離散趨勢。方差越小，則樣本點周圍數據越稠密，收斂越快；反之，則越稀疏，收斂越慢。因此，對Canopy算法隨機從待聚類樣本中任選一點作為Canopy中心的方式進行優化，利用式(1)～(3)計算樣本數據集中每個樣本的方差，以樣本方差最小點作為Canopy中心進行Canopy劃分來獲取優質的初始聚類中心作為K-means算法的輸入，同時參照文獻[5，6]設置Canopy中的閾值。其執行流程圖如圖1所示。

3 MVC-Kmeans算法步驟

算法步驟描述如下：

步1Canopy階段獲得局部Canopy中心。

a)令t=0,根據式(1)～(3)獲取每一個數-據集D的樣本方差集合C，同時依據噪聲點和孤立點存在hi>hAV,為消除這些點的影響以及基于T1與T2之間存在的關系，設定T2=hAV，T1=2T2。

則將xj加入到Ct集合并C=C-Ct；

則將xj加入到Ct集合且該點可能會成為下一個Canopy中心；

else

xj可能會成為下一個Canopy中心；

d)若C為空，則獲得W={wt|wt∈Rm,t=1,2,3,…,n}結束；否則，轉到步1b)。

步2獲得Canopy算法的最終輸出。

a)令t=0,將W以式(1)～(3)獲得的每個樣本方差放入集合K，設定T2=hAV，T1=2T2。

則將xj加入到Ct集合并K=K-Ct；

則將xj加入到Ct集合且該點可能會成為下一個Canopy中心；

else

xj可能會成為下一個Canopy中心；

d)若K為空，則獲得G={gt|gt∈Rm,t=1,2,3,…,n}結束；否則，轉到步2b)。

e)將重疊區域的樣本歸入到與所屬Ct的gt距離最近的Ct中，并計算各個Ct的樣本與對應gt和的均值，作為全局的Canopy中心，并更新集合G。

步3K-means階段構造初始劃分。

a)以G為K-means的初始聚類中心，利用式(1)計算D中各樣本到各初始中心的距離，根據相似性原則將樣本劃歸到最相似的類簇中。

b)計算每個類簇的平均值作為新的聚類中心。

c)根據式(5)計算當前聚類結果的誤差平方和E。

步4重新構造類簇及更新聚類中心。

a)以新的初始聚類中心作為聚類中心，利用式(1)計算D中各樣本到各初始中心的距離，根據相似性原則將樣本劃歸到最相似的類簇中。

b)計算每個類簇的平均值作為新的聚類中心。

c)根據式(5)計算當前聚類結果的誤差平方和E′。

d)如果E′-E<ε,則聚類收斂，算法結束；否則，令E=E′,轉到步3。

4 分布式MVC-Kmeans算法的并行設計

MVC-Kmeans算法的執行流程如圖1所示，由兩部分組成。在Hadoop平臺的MapReduce下進行了該算法的并行化設計，其包含2個任務，依次執行，前一個任務的輸出將是下一個任務的輸入。

任務1：結合最小方差和Canopy算法思想在MapReduce編程框架下的實現。

在Map階段，利用分布在集群不同站點的數據子集，通過Canopy算法快速產生若干個以最小方差劃分的局部Canopy中心和重疊的Canopy；在Reduce階段，對Map階段輸出的Canopy中心重新計算后，以方差最小的樣本為新的初始Canopy中心，再次運用Canopy算法獲得全局Canopy中心和重疊的Canopy，將重疊區域的樣本歸入到與所屬Canopy的Canopy中心距離最近的Canopy中，并計算各個Canopy的樣本與對應Canopy中心和的均值，獲得K-means算法的初始聚類中心。整個階段的算法設計流程如圖2、圖3所示。

圖2 最小方差Canopy-Map階段 圖3 最小方差Canopy-Reduce階段

任務2：該部分是傳統K-means算法在MapReduce編程框架的實現。

在Map階段，將來自于任務一的輸出作為全局的初始聚類中心，通過對逐行讀取的數據按照就近原則進行劃分歸類；由于Map階段輸出的大量結果會寫入磁盤，當Reduce階段啟動時需要通過網絡來獲取這些結果，嚴重消耗磁盤IO和網絡IO，為了優化MapReduce中間產生的結果，設計了Combine階段，對于來自于Map階段的輸出，以Key相同的各個Value進行合并；在Reduce階段，讀取每個Combine階段處理后的數據樣本個數N及各樣本維度的坐標值，并將各維度的值對應相加求均值，獲得新聚類中心來更新原聚類中心，然后進入下一次迭代直至算法收斂。其K-means算法并行化設計如圖4所示。

圖4 K-means算法并行化設計

5 試驗與分析

Hadoop平臺由1臺主節點和3臺從節點構成，對來源于公開UCI機器學習庫[15]中的數據集進行試驗分析。為了驗證MVC-Kmeans算法的準確性和收斂性,與傳統的K-means算法進行了比較；同時，

表1 試驗測試數據集

為了驗證MVC-Kmeans算法處理大規模數據的優勢，進行了加速比和擴展率的分析。

5.1 試驗數據

表1列出了所選樣本的屬性、樣本數量以及類別數。這些標準數據集用來準確率量算法的聚類質量。

同時，為了符合MapReduce編程框架的數據格式要求，所有的數據以對形式表示，具體格式如表2所示。

表2 試驗各階段數據格式

5.2 試驗結果及分析

1)MVC-Kmeans算法與傳統K-means算法聚類質量的比較 利用表1數據集對優化的算法在單機上進行了檢驗。為了保證檢驗的結果可靠，每個樣本集在各算法下分別進行10次，結果取10次試驗的平均值，其試驗結果如表3所示。

表3 樣本數據集試驗結果

從表3中可以看出，MVC-Kmeans算法在所選數據集上聚類精度均有提高，提高了4.11～25.91個百分點；誤差平方和與迭代次數均有降低，其降低幅度分別為4.70%～34.00%和16.67%～42.86%，可見MVC-Kmeans算法能獲得較好的聚類質量和更快的收斂速度

圖5 Iris數據集加速比測試結果 圖6 Iris數據集擴展率測試結果

6 結語

筆者基于最小方差和Canopy算法優化了K-means算法初始聚類中心選取，提出了MVC-Kmeans聚類算法。在Hadoop云計算平臺上，對MVC-Kmeans算法進行了MapReduce并行化設計。在開源數據集上相比傳統聚類算法的試驗結果表明，無論是在準確率、迭代次數還是誤差平方和，MVC-Kmeans算法明顯優于傳統K-means算法,能獲得更加穩定的聚類結果以及更快的收斂速度,并適于大規模數據的聚類分析。但對于Canopy算法中閾值T1與T2的選擇不具備確定性，這將是下一步要開展的工作。