基于聚合距離參數的改進K-means算法

王巧玲 喬非 蔣友好

摘 要：針對傳統K均值聚類（K-means）算法隨機選擇初始中心及K值導致的聚類結果不確定且精度不高問題，提出了一種基于聚合距離的改進K-means算法。首先，基于聚合距離參數篩選出優質的初始聚類中心，并將其作用于K-means算法。然后，引入戴維森堡丁指數（Davies-Bouldin Index， DBI）作為算法的準則函數，循環更新聚類直到準則函數收斂，最后完成聚類。改進算法提供了優質的初始聚類中心及K值，避免了聚類結果的隨機性。二維數值型仿真數據的聚類結果表明，改進算法在數據樣本數達到10000時仍能保持較好的聚類效果。針對Iris和Seg 這兩個UCI標準數據集的調整蘭德系數，改進算法比傳統算法性能分別提高了83.7%和 71.0%，最終驗證了改進算法比傳統算法聚類結果的準確性更高。

關鍵詞：聚合距離參數;聚類中心;聚類評判指標;戴維森堡丁指數（DBI）;數據聚類

中圖分類號：TP301.6

文獻標志碼：A

Improved K-means algorithm with aggregation distance coefficient

WANG Qiaoling， QIAO Fei*， JIANG Youhao

School of Electronics and Information Engineering， Tongji University， Shanghai 201804， China

Abstract：

Initial centers and K value are determined randomly in the traditional K-means algorithm， which makes clustering results uncertain and with low precision. Therefore， an improved K-means algorithm based on aggregation distance was proposed. Firstly， high-quality cluster centers were filtered out based on the aggregation distance coefficient as the initial centers of the K-means algorithm. Secondly， Davies-Bouldin Index （DBI） was introduced as the criterion function of the algorithm， and the clustering was cyclically updated until the criterion function converged. Finally， the clustering was completed. The proposed algorithm provides good initial clustering centers and K value， avoiding the randomness of clustering results. The clustering results of two-dimensional numerical simulation data show that the improved algorithm can still maintain a good clustering effect when the number of? data samples reaches 10000. For the adjusted Rand coefficients of the two UCI standard datasets named Iris and Seg， the improved algorithm respectively improves the performance of clustering by 83.7% and 71.0% compared to the traditional algorithm. It can be seen that the improved algorithm can increase the accuracy of the clustering result compared with the traditional algorithm.

Key words：

aggregation distance coefficient; cluster center; clustering evaluation index; Davies-Bouldin Index （DBI）; data clustering

0 引言

隨著云計算、物聯網等技術的出現，企業日趨信息化，應用系統中的數據量呈指數級增長。數據挖掘技術能夠幫助用戶從大量數據中分析出其所蘊涵的有價值的信息。聚類算法就是一種典型的數據挖掘方法，它是一種無監督的機器學習算法，適合于將不含訓練集的大數據以相似度為依據進行聚類[1-3]。

K均值聚類（K-means）是一種常見的聚類算法，它在處理大規模數據集時可保持較好的可伸縮性和高效性[4-6]。然而，傳統的K-means算法也存在一些缺陷：1）初始聚類中心的選擇是隨機的，這使得聚類結果不穩定，準確性較低。2）聚類個數K值的選擇是隨機的，若K值過大，則類與類之間的相似度太小;若K值過小，則類與類之間的相似度過大，這兩種情況都會導致聚類結果不準確。

很多學者針對K-means算法的缺點提出了相應的改進。郁啟麟[7]采用關系矩陣和度中心性選擇K個初始聚類中心，以此來改進K-means算法。文獻[8]中提出了一種基于優化抽樣聚類的方法，一定程度上解決了K-means算法聚類精度不足和收斂速度慢的問題。文獻[9]中提出了用隨機取樣策略來避免決策選取陷入局部最小。為了解決K-means算法初始聚類中心和K值隨機性的問題，文獻[10]應用了Canopy-Kmeans算法，先由Canopy算法對數據集進行粗聚類，得到一定數量的類，每個類的中心作為K-means算法的初始聚類中心，類的個數決定K值的大小。然而Canopy算法的兩個閾值是隨機選擇的，這導致了獲得的初始中心和K值存在隨機性，從而影響聚類效果。

針對K-means算法初始聚類中心和K值選擇問題，本文提出了一種基于聚合距離參數的改進K-means算法。對給定數據集中的每一個數據點進行聚合度及其所屬類的距離分析，篩選出符合條件的數據點作為初始聚類中心，符合條件的數據點的個數即為K值。改進的算法能夠確定最優的初始聚類中心及聚類個數，從而避免了聚類結果的不確定性。最后，采用可視化數據及UCI標準數據集，驗證了改進算法聚類結果的準確性。

1 聚合距離參數

初始聚類中心及K值選擇不準確，會導致K-means算法聚類結果準確性不高，因此，本文提出了聚合距離參數，以篩選出一定量的優質的初始聚類中心。聚合距離參數中涉及到的一些相關定義和概念如下：

歐氏距離 設每一個數據點包含m個屬性，即xi={xi1，xi2，…，xim}，則xi、xj之間的距離可以表示為：

d（xi，xj）=∑ms=1（xis-xjs）2（1）

數據集平均距離 即為一個數據集合中所有數據點之間的平均歐氏距離。

Avgd（D）=2n（n-1）∑n-1i=1∑nj=i+1d（xi，xj）（2）

鄰域半徑 R=Avgd（D）nreleR，其中n表示數據點的個數，releR為鄰域半徑調節系數，范圍在0～1，根據經驗，releR取0.13時，聚類效果最佳[11-13]。

聚合度 點xi的聚合度Deg（xi）表示為與其距離小于半徑的點的個數，即：

Deg（xi）=∑nj=1f（dij-R）; f（x）=1， x≤0

0，x>0（3）

集合平均距離 與點xi的距離小于鄰域半徑的所有點組成一個集合，那么點xi所在集合的平均距離可以定義為：

Cavgd（xi）=2Deg（xi）（Deg（xi）-1）∑Deg（xi）-1i=1∑Deg（xi）j=i+1d（xi，xj）（4）

集合平均距離可以衡量一個數據點所在集合的緊密度， 值越小，表示Cavgd（xi）所在集合越緊密。

聚合度距離 聚合度距離表示點xi與其他具有較高聚合度點xj之間的距離。若所有點中xi的聚合度最大，則其聚合度距離為xi與其余任何點的最大距離。若xi的聚合度不是所有點中最大的，則其聚合度距離為xi與其余任何點的最小距離。即：

G（xi）=min（d（xi，xj））， 存在xj滿足Deg（xj）>Deg（xi）

max（d（xi，xj）），不存在xj滿足Deg（xj）>Deg（xi）（5）

聚合距離參數 聚合距離參數由聚合度、集合平均距離及聚合度距離3個參數決定。即：

ω（xi）=Deg（xi）·G（xi）Cavgd（xi）（6）

聚合度Deg（xi）越大，表明點xi周圍的數據點越密集。聚合度距離G（xi）越大，則兩個簇之間的相異程度越高。集合平均距離Cavgd（xi）越小，則其倒數越大，表明由xi組成的集合中的元素越緊密。由此可見，聚合距離參數值越大的點，越適合作為聚類中心。

2 改進K-means算法

2.1 改進初始聚類中心

由聚合距離參數篩選最優初始聚類中心步驟如下：

1）根據式（2）～（6），計算出數據集中所有數據點相關參數，從而得到每一個數據點的聚合距離參數。

2）篩選出聚合距離值最大的點，作為第一個初始聚類中心，并依次計算其他點到該點的歐氏距離：若距離小于鄰域半徑R，將該點從數據集中移除;若距離大于R，則不作處理。

3）從剩余點中篩選出聚合距離值最大的點，作為第二個初始聚類中心，并依次計算其他點到該點的歐氏距離，若距離小于鄰域半徑R，將該點從數據集中移除。

4）重復步驟3）和步驟4），直到數據集為空。

5）輸出一系列符合條件的優質初始聚類中心。

2.2 改進準則函數

傳統K-means的準則函數一般為平方誤差和函數，該函數計算了每個聚類樣本與其聚類中心的平方距離之和，但僅片面地衡量了一個類之內數據是否緊湊，沒有考慮到類與類之間的相異性，因此，本文采用戴維森堡丁指數（Davies-Bouldin Index， DBI）指標函數作為K-means算法的準則函數[14-15]。

類間距離 類間距離 Dis（i， j）表示為第i個類與第j個類之間的距離，即第i個聚類中心vi與第j個聚類中心vj的歐氏距離。

Dis（i， j）=‖vi-vj‖（7）

類內標準誤差 類內標準誤差Si表示為第i個聚類Ci中每一個數據點x與該類的中心點vi之間的歐氏距離標準誤差和，即：

Si=1Ni∑x∈Ci‖x-vi‖（8）

其中Ni表示第i個聚類Ci包含的數據對象個數。

DBI指標

DBI=1K∑K-1i=1∑Kj=i+1maxSi+SjDis（i， j）（9）

其中K表示為數據集的所有聚類個數。

DBI指標由類之間的距離和類內的距離決定。好的聚類結果應該滿足同一個類中數據之間的相似程度大，而類與類之間的相似程度小。DBI指標不僅考慮了類內的相似性，還考慮了類與類之間的相異性：如果一個類的類內距離較小，則DBI的分子較小，表明類中數據點的相似程度大;如果類與類之間的距離較大，則DBI的分母較大，表明類之間的相異性較大。因此，DBI指標數值越小，表明聚類效果越好。

2.3 改進算法總流程

改進算法根據聚合距離參數選取一定數量的最優中心，作為K-means的初始聚類中心，用DBI指標作為準則函數，若準則函數收斂，則說明聚類效果達到最優，聚類完成，輸出聚類結果。整體的算法流程如下所示。

算法1 基于聚合距離參數的改進K-means算法。

輸入：數據集;

輸出：聚類結果。

有序號的程序——————————Shift+Alt+Y

程序前

M=數據點個數

R=鄰域半徑

1）

for i in range（M）

2）

計算兩兩數據點之間的歐氏距離

3）

計算每個數據點xi的聚合距離參數ω（xi）

4）

選出ω（xi）數值最大的數據點，作為第一個初始聚聚類中心，并將其從數據集中移除

5）

計算剩余各點xj到該聚類中心xi的距離di， j

6）

if di， j < R

7）

則將點xj從數據集中移除

8）

else if di， j≥R

9）

不作處理

10）

end

11）

重復步驟4）～10），直到數據集為空。

12）

輸出一定個數的最優中心作為K-means算法的初始聚類中心

13）

輸入中心個數N

14）

執行改進K-means算法，將數據集分為N個聚類

15）

if 準則函數DBI=1K∑K-1i=1∑Kj=i+1maxSi+SjDis（i， j）不收斂

16）

繼續循環執行改進K-means算法

17）

else if 準則函數收斂

18）

改進K-means算法執行完畢

19）

end

20）

輸出聚類結果

程序后

3 實驗結果與分析

3.1 可視化數據集

為了更好地說明改進算法的優異性，本節使用Python中的make_blobs模塊生成二維數值型仿真數據。首先，為了便于可視化處理，生成兩組均包含200個樣本點的數據。圖1（a）和圖1（b）的結果表明，改進算法找到了優質的初始聚類中心，成功將數據分成了2類和3類，聚類結果準確，從而改進算法的有效性得以驗證。然后，為了檢驗算法面對較大樣本時的效果，再生成一組達到10000樣本數的數據。圖1（c）的結果表明，改進算法仍能很好地完成聚類。

3.2 標準數據集

3.2.1 評估指標

標準數據集指明了每一個數據點真實所屬的類，即true_label，而實際的聚類結果也會有一個相對應的標簽，即pred_label，用于表示每個數據點實際被分到的類。對于標準數據集，本文采用以下指標進行評估：調整蘭德系數、互信息、Fowlkes-Mallows 指標、同質性和完整性，這些指標都用于衡量true_label和pred_label的相似程度。

3.2.2 實驗結果

本文采用了UCI網站上的標準數據集，數據集名稱及其屬性如表1所示。

為了更深入地進行對比，本文采用了傳統K-means算法，Canopy算法及改進K-means算法對標準數據集進行聚類。聚類結果的評估指標如圖2所示。

圖2（a）顯示調整蘭德系數指標結果，調整蘭德系數表示兩個數據分布之間的相似度，其范圍從-1到1。值越大，表明聚類結果與實際情況越一致;若值為負，表明兩個數據分布相互獨立，匹配程度很低。改進K-means算法相比于傳統K-means，調整蘭德系數指標均可有效提高。其中Iris和Seg 這兩個數據集，改進算法比傳統算法的調整蘭德系數指標分別提高了83.7%和71.0%。

圖2（b）和圖2（c）分別顯示互信息及Fowlkes-Mallows指標結果。這兩個指標用于表示兩個變量true_label和pred_label是否有關系，以及關系的接近程度?；バ畔⒑虵owlkes-Mallows指標的范圍都為0～1，如果值較大，則表示true_label和pred_label之間的關系更接近。實驗結果表明，改進算法在各個數據集上，互信息及Fowlkes-Mallows指標的數值都明顯比傳統K-means算法有提高。即改進K-means的實際聚類結果與標準結果更接近，聚類效果更好。

圖3表示同質性和完整性的實驗結果。同質性表示每個群集只包含單個類的成員，完整性表示給定類的所有成員都分配給同一個群集，這兩個指標通常一起使用，范圍為0到1之間，值越大表明聚類效果越好。

通過比較圖2和圖3的整體結果可知：1）改進K-means算法的評估指標數值均高于其他兩個算法，即改進算法的實際聚類結果與標準結果更一致，這說明了其性能是優于傳統算法的。2）對于不同的數據集來說，同一個算法聚類結果的評估指標數值也不一樣，這說明聚類效果會因不同的數據集而波動。3）Canopy的聚類結果大多比傳統K-means算法差，有時比傳統K-means更好，這是因為Canopy的聚類結果很大程度上取決于兩個閾值，且閾值在實驗中是隨機選擇的。如果閾值更準確，最終的聚類結果將更好，指標將更好。而改進的K-means算法避免了隨機性，并且始終具有更好的聚類結果。

4 結語

K-means算法是聚類算法中的重要方法。本文針對傳統K-means算法的不足，提出了基于聚合距離參數的改進K-means算法。首先，通過使用聚合距離參數獲取一定的最優聚類中心;然后，將最優聚類中心應用于改進的K-means，并且改進的K-means算法將根據新的準則函數DBI收斂，當準則函數達到最小值時，聚類結束，輸出聚類結果。

改進的K-means算法有效地解決了初始聚類中心和K值選擇不確定的問題，實驗結果表明，改進的K-means算法比傳統K-means算法，在聚類效果上有很大的提升。

未來工作中將會采用改進的K-means算法來對工業大數據進行聚類。由于工業大數據大都具有時效性，因此，將考慮對大數據進行降維，從而減少聚類算法的計算時間。同時，會在Hadoop平臺上并行化實現大數據的聚類，提高時間效能。最后基于改進算法得出的聚類結果，提出針對工業大數據的異常值檢測方法，從而將改進算法應用于工業大數據領域，有效檢測工業設備運行的健康程度。

參考文獻

[1]王治和，黃夢瑩，杜輝，等. 基于密度峰值與密度聚類的集成算法[J].計算機應用，2019，39（2）：398-402. （WANG Z H， HUANG M Y， DU H， et al. Integrated algorithm based on density peaks and density-based clustering J]. Journal of Computer Applications， 2019， 39（2）： 398-402.）

[2]McLOUGHLIN F， DUFFY A， CONLON M. A clustering approach to domestic electricity load profile characterisation using smart metering data [J]. Applied Energy， 2015， 141： 190-199.

[3]ALI A-W， WU J， JENKINS N. K-means based load estimation of domestic smart meter measurements [J]. Applied Energy， 2016， 194： 333-342.

[4]楊輝華，王克，李靈巧，等.基于自適應布谷鳥搜索算法的K-means聚類算法及其應用[J].計算機應用，2016，36（8）：2066-2070.（YANG H H， WANG K， LI L Q， et al. K-means clustering algorithm based on adaptive cuckoo search and its application [J]. Journal of Computer Applications， 2016， 36（8）： 2066-2070.）

[5]黃韜，劉勝輝，譚艷娜.基于K-means聚類算法的研究[J].計算機技術與發展，2011，21（7）：54-57.（HUANG T， LIU S H， TAN Y N. Research of clustering algorithm based on K-means [J]. Computer Technology and Development， 2011， 21（7）：54-57.）

[6]王駿，王士同，鄧趙紅. 特征加權距離與軟子空間學習相結合的文本聚類新方法[J].計算機學報， 2012， 35（8）： 1655-1665. （WANG J， WANG S T， DENG Z H. A novel text clustering algorithm based on feature weighting distance and soft subspace learning [J]. Chinese Journal of Computers， 2012， 35（8）： 1655-1665. ）

[7]郁啟麟. K-means算法初始聚類中心選擇的優化[J]. 計算機系統應用， 2017， 26（5）： 170-174. （YU Q L. Optimization of initial clustering centers selection method for K-means algorithm [J]. Computer Systems & Applications， 2017， 26（5）： 170-174.）

[8]周潤物，李智勇，陳少淼，等.面向大數據處理的并行優化抽樣聚類K-means算法[J].計算機應用，2016，36（2）：311-315.（ZHOU R W， LI Z Y， CHEN S M， et al. Parallel optimization sampling clustering K-means algorithm for big data processing [J]. Journal of Computer Applications， 2016， 36（2）： 311-315.）

[9]王麗娟，郝志峰，蔡瑞初，等. 基于隨機取樣的選擇性K-means聚類融合算法[J]. 計算機應用， 2013， 33（7）： 1969-1972. （WANG L J， HAO Z F， CAI R C， et al. Selective K-means clustering ensemble based on random sampling [J]. Journal of Computer Applications， 2013， 33（7）： 1969-1972.）

[10]毛典輝.基于MapReduce的Canopy-Kmeans改進算法[J]. 計算機工程與應用， 2012， 48（27）： 22-26. （MAO D H. Improved Canopy-Kmeans algorithm based on MapReduce [J]. Computer Engineering and Applications， 2012， 48（27）： 22-26.）

[11]趙昱，陳琴，蘇一丹，等. 基于鄰域相似度的近鄰傳播聚類算法[J]. 計算機工程與設計， 2018， 39（7）： 1883-1888. （ZHAO Y， CHEN Q， SU Y D， et al. Affinity propagation clustering algorithm based on neighborhood similarity [J]. Computer Engineering and Design， 2018， 39（7）： 1883-1888.）

[12]劉鵬，王明陽，王焱.基于自適應動態球半徑的K鄰域搜索算法[J]. 機械設計與制造工程， 2016， 45（6）： 83-86.（LIU P， WANG M Y， WANG Y. K domain search algorithm based on adaptive dynamic sphere radius [J]. Machine Design and Manufacturing Engineering， 2016， 45（6）： 83-86.）

[13]NGUYEN D， LE T， NGUYEN S. An algorithmic method of calculating neighborhood radius for clustering in-home activities within smart home environment [C]// Proceedings of the 7th International Conference on Intelligent Systems， Modelling and Simulation. Piscataway， NJ： IEEE， 2016： 42-47.

[14]COELHO G P， BARBANTE C C， BOCCATO L， et al. Automatic feature selection for BCI： an analysis using the Davies-Bouldin index and extreme learning machines [C]// Proceedings of the 2012 International Joint Conference on Neural Networks. Piscataway， NJ： IEEE， 2012： 1-8.

[15]THOMAS J C R， PEAS M S， MORA M. New version of Davies-Bouldin index for clustering validation based on cylindrical distance [C]// Proceedings of the 32nd International Conference of the Chilean Computer Science Society. Piscataway， NJ： IEEE， 2013： 49-53.

This work is partially supported by the Major Program of National Natural Science Foundation of China （71690230， 71690234）.

WANG Qiaoling， born in 1994， M. S. candidate. Her research interests include clustering algorithm， big data analysis.

QIAO Fei， born in 1967， Ph. D.， professor. Her research interests include big data analysis， complex manufacturing planning and scheduling， intelligent production systems.

JIANG Youhao， born in 1976， Ph. D. candidate. His research interests include big data analysis， intelligent production systems.