一種改進的K-均值聚類算法?

隋心怡 王瑞剛 張鴻翔

（1.西安郵電大學計算機學院 西安 710061）（2.西安交通大學電子與信息工程學院 西安 710049）

1 引言

聚類問題是指依據樣本的某些屬性或按照某種標準，將樣本分為多個類，并使相同類中的樣本相似度盡可能大，不同類中的樣本相似度盡可能小［1］。為解決聚類問題，研究人員提出了多種聚類算法，主要有：基于劃分的算法、基于層次的算法、基于密度的算法、基于網絡的算法、基于模型的算法以及其他形式的算法［2～5］。

基于劃分的聚類算法是最早提出，也是最常用的經典聚類算法［6］。該類算法通過選擇k個初始聚類中心（代表k個類），然后根據其他樣本與中心點的距離，將每個樣本劃分到與它距離最近的類中，從而實現樣本聚類［7］。

K-均值聚類算法就是一種基于劃分的聚類算法［8］，由于其原理簡單易于實現，在多個領域中都有廣泛的應用。但是傳統的K-均值聚類算法易受初始點影響，當初始點選擇不當時，甚至無法得到正確聚類結果［9～10］，算法穩定性較差。鑒于K-均值聚類算法存在的缺陷，如何選取聚類初始點一直是其算法改進的重要方向［11］。

本文根據樣本的空間分布動態選取初始聚類中心，提出了一種改進的K-均值聚類算法。實驗結果表明，改進后的算法提高了穩定性，并取得了較高的分類準確率。

2 K-均值聚類算法

K-均值聚類算法首先需要輸入聚類個數k，然后隨機選擇k個樣本作為聚類中心；通過計算剩余樣本與聚類中心的距離，將樣本歸入與其距離最近的類；當所有樣本計算結束后，根據當前聚類結果更新聚類中心；通過循環迭代直到目標函數［12］滿足一定要求或達到最大迭代次數時聚類結束。

目標函數用于度量聚類結果的好壞，其定義如下

K-均值聚類算法常采用歐氏距離［13］表示樣本與聚類中心的遠近，此時目標函數也稱為平方誤差準則函數：

當一次迭代結束后，需要更新聚類中心，更新公式為

式中nj為第 j類中的樣本個數，cj*為新的聚類中心。

算法流程：

1）從樣本中隨機選取k個對象作為初始聚類中心；

2）計算樣本與k個聚類中心的距離，將樣本歸入距離最近的類中；

3）根據式（3）計算新的聚類中心；

客觀原因主要包括：由于溫度變化而引起變形、地基地質構造存在較大差別、地下水位上升或降低導致高速公路地基被侵蝕、土壤物理性質存在較大差異，以上各項客觀因素都會對造成軟土地基發生沉降，從而會對高速公路最終質量造成較為嚴重的影響，影響高速公路施工，以及工程竣工后的應用。

4）重復步驟2）、3），直至滿足結束條件；

5）計算結束，得到聚類結果。

3 改進的K-均值聚類算法

初始聚類中心的選擇直接影響到K-均值聚類算法的性能，這導致傳統的K-均值聚類算法性能較不穩定［14］。一方面，若隨機選取的初始聚類中心距離較近，會導致算法迭代次數較多甚至聚類出現偏差，因為距離較近的兩個樣本更有可能屬于同一類而不是不同類，所以選取相互之間距離較遠的k個樣本作為初始點更具有代表性；另一方面，若一味地尋找相距較遠的初始點，有可能會取到孤立點，也不利于聚類。通過觀察數據樣本的空間分布發現，實際的聚類中心所在的區域往往密度較高，即這一區域內的樣本數量要大于其他區域。針對上述先驗知識，本文改進了初始聚類中心的選取方法，根據樣本所在空間的分布密度，并結合樣本間最大距離選取初始聚類中心。

設待聚類的m個n維數據樣本為X，所處空間范圍為RN，可表示為

定義子空間r（r∈RN）的樣本密度為該子空間內的樣本數量，記作ρr。如果一個子空間的樣本密度不小于ρmin，則該子空間為高密度子空間，ρmin為高密度子空間閾值。

兩個 n維數據 x1(α1，α2，…，αn)、x2(β1，β2，…，βn)間的距離定義為

改進后的K-均值聚類算法流程如下：

1）設定聚類個數k、高密度子空間閾值ρmin；

2）選定正整數l，將輸入樣本所處的n維空間等分為ln（ln＞2k）個子空間，計算各子空間ri的樣本密度 ρri，并將密度不小于ρmin的子空間放入高密度子空間集合Dρ，統計高密度子空間數量；

3）若高密度子空間數量小于聚類個數k，返回1），調整閾值 ρmin；

4）選取密度最高的子空間，計算該空間內樣本點的平均距離，設為第一個初始聚類中心c1；

5）計算c1與其他高密度子空間中心的距離，選取與其距離最遠的高密度子空間，計算該空間內樣本點的平均距離，得到第二個初始聚類中心c2；

6）計算c1、c2與其他高密度子空間中心的距離和，按照最大距離準則選取高密度子空間，并計算得到聚類中心c3；

7）繼續按照6）的方法尋找聚類中心，直到找到第k個聚類中心ck；

8）將k個初始聚類中心帶入傳統的K-均值聚類算法進行聚類，得到聚類結果。

4 實驗結果及分析

本文使用UCI機器學習數據庫［15］對傳統k均值算法和改進算法進行對比實驗。選取Iris、Wine和Glass三組數據作為測試數據集。為了使結果更加直觀，首先將三個測試數據集不同屬性值做歸一化處理，并其降維至二維空間。

采用傳統k均值算法進行30次實驗，取平均值作為實驗最終結果；由于改進算法計算出的初始聚類中心是固定的，所以只進行一次試驗，并將其結果作為最終結果。實驗結果如表1所示。

由表1可以看出，采用本文提出的改進算法得到的聚類精度要好于傳統的k均值算法。

表1 算法精度比較

為對比兩算法的運算效率，實驗還統計了算法的迭代次數和運行時間，結果如表2所示。由于本文提出的改進算法根據樣本點的空間分布選取初始聚類中心，算法迭代次數要明顯少于傳統k均值算法；但因為改進算法要統計所有樣本點的空間分布，會犧牲一定的時間，所以改進算法的運行時間要大于傳統的k均值算法。

表2 算法迭代次數與運行時間比較

此外，通過觀察采用傳統k均值算法進行的30次實驗，發現各實驗間結果相差較大，這也表明由于傳統k均值算法的初始聚類中心是隨機選擇的，結果隨機性較強，算法穩定性較差。而本文提出的改進算法在參數設置確定的情況下，實驗結果也是固定的，穩定性好于傳統k均值算法。

5 結語

本文在傳統K-均值聚類算法的基礎上，將樣本點分布密度與初始點選取相結合，提出了一種改進的K-均值聚類算法，實驗結果表明，本算法的聚類精度和穩定性都要好于傳統的K-均值聚類算法。

由于本文提出的算法需要分割樣本所處的n維空間，當樣本屬性值較多時，會導致分割得到的子空間數量較多，不利于之后的處理。所以本算法適用于對屬性值較少的數據集進行聚類；當屬性值較多時，需要先進行預處理，舍棄部分相關屬性或將屬性值投影到低維空間，然后再使用本算法進行聚類。此外，算法中的參數會影響數據集的聚類效果，如何針對不同數據集設置合理的參數也是今后的研究方向之一。

［1］李桂林，陳曉云.關于聚類分析中相似度的討論［J］.計算機工程與應用，2004，40（31）：64-65.LI Guilin，CHEN Xiaoyun.The Discussion on the Similar?ity of Cluster Analysis［J］.Computer Engineering and Ap?plications，2004，40（31）：64-65.

［2］席景科，譚海樵.空間聚類分析及評價方法［J］.計算機工程與設計，2009，30（7）：1712-1715.XI Jingke，TAN Haiqiao.Spatial clustering analysis and its evaluation［J］.Computer Engineering and Design，2009，30（7）：1712-1715.

［3］賈璦瑋.基于劃分的聚類算法研究綜述［J］.電子設計工程，2014（23）：38-41.JIA Aiwei.Survey on partitional clustering algorithms［J］.Electronic Design Engineering，2014（23）：38-41.

［4］李新良.基于層次聚類算法的改進研究［J］.軟件導刊，2007（19）：141-142.LI Xinliang.Improved Research of Hierarchical Cluster Algorithm［J］.Software Guide，2007（19）：141-142.

［5］羅軍鋒，鎖志海.一種基于密度的k-means聚類算法［J］.微電子學與計算機，2014（10）：28-31.LUO Junfeng，SUO Zhihai.A Density Based k-means Clustering Algorithm［J］.Microelectronics&Computer，2014（10）：28-31.

［6］尹成祥，張宏軍，張睿，等.一種改進的K-Means算法［J］.計算機技術與發展，2014（10）：30-33.YI Chengxiang，ZHANG Hongjun，ZHANG Rui，et al.An Improved K-means Algorithm［J］.Computer Applications，2014（10）：30-33.

［7］段桂芹.基于均值與最大距離乘積的初始聚類中心優化K-means算法［J］.計算機與數字工程，2015（3）：379-382.DUAN Guiqin.Automatic Generation Cloud Optimization Based on Genetic Algorithm［J］.Computer&Digital Engi?neering，2015（3）：379-382.

［8］王千，王成，馮振元，等.K-means聚類算法研究綜述［J］.電子設計工程，2012，20（7）：21-24.WANG Qian，WANG Cheng，FENG Zhenyuan，et al.Re?view of K-means clustering algorithm［J］.Electronic De?sign Engineering，2012，20（7）：21-24.

［9］胡偉.改進的層次K均值聚類算法［J］.計算機工程與應用，2013，49（2）：157-159.HU Wei.Improved hierarchical K-means clustering algo?rithm.Computer Engineering and Applications［J］.2013，49（2：157-159.

［10］鄭丹，王潛平.K-means初始聚類中心的選擇算法［J］.計算機應用，2012，32（8）：2186-2188.ZHENG Dan，WANG Qianpin.Selection algorithm for K-means initial clustering center［J］.Journal of Comput?er Applications，2012，32（8）：2186-2188.

［11］王曉燕.常用的聚類算法及改進算法的研究［J］.辦公自動化：學術版，2013，3（9）：49-52.WANG Xiaoyan.Commonly Used Clustering Algorithm and Improved Algorithm Research［J］.Office Automa?tion，2013，3（9）：49-52.

［12］Meng Jianliang，Shang Hai kun，Bian Ling.The applica?tion on intrusion detection based on K-means cluster al?gorithm［C］.International Forum on Information Technol?ogy and Applications，2009：150-152.

［13］Liu X M，Lei D.An improved K-Means clustering algo?rithm［J］.Journal of Networks，2014，9（1）：1-3.

［14］Wu J.K-means Based Consensus Clustering［J］.Knowl?edge&Data Engineering IEEE Transactions on，2015，27（1）：155-169.

［15］University B I.Uci machine learning.ftp.ics.uci.edu/pub/machine-learning-databases［J］.2010.