周愛武，潘 勇，崔丹丹，肖 云

(安徽大學 計算機科學與技術學院，安徽 合肥 230039)

K-means算法是基于劃分的經典聚類算法，該算法簡單、快速，得到了廣泛應用，但是該算法對孤立點是敏感的，其次該算法要求用戶必須事先給出簇數(shù)k值，該算法聚類結果受初始聚類中心隨機性選擇影響比較大，聚類中心選擇不當，容易導致聚類準確度下降，甚至無法得到聚類結果。針對以上缺點，國內外許多專家和學者提出很多對K-means算法的改進，比如參考文獻[1]~參考文獻[3]是基于密度的對K-means算法進行改進來找到密度比較高的代表點作為初始聚類中心，參考文獻[4]是把遺傳算法應用到K-means算法中來確定k個初始聚類中心，這種結合能夠進行一種全局優(yōu)化，可提高算法的準確率，將智能算法與K-means算法的結合也是近年來研究的熱點。K-means算法以及其改進的算法已經應用到了各個領域，取得了很好的效果，比如參考文獻[3]是改進的K-means算法在客戶劃分中的應用，參考文獻[5]是在圖像標注和檢索的應用，參考文獻[6]是在存在異常孤立點大數(shù)據(jù)集中進行聚類發(fā)現(xiàn)簇的應用。由此可見，K-means算法的效率高、時間復雜度低，應用前景寬廣。

本文針對初始聚類中心隨機選擇這個缺陷，提出將凝聚層次聚類算法AGNES應用到改進的算法中，得到k個密度比較高的初始聚類中心，并將其應用到K-means中去進行聚類。實驗表明，改進的算法運行效率高，并能獲得比較高的準確率。

1 算法的基本思想

1.1 K-means算法

算法接收輸入量k，然后將n個數(shù)據(jù)對象劃分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“聚類中心對象”來進行計算的。

K-means算法步驟描述如下：

輸入：n個數(shù)據(jù)對象，簇數(shù)k

輸出：k個簇的集合。

(1)從n個數(shù)據(jù)對象中任意選擇k個數(shù)據(jù)對象作為初始聚類中心。

(2)根據(jù)簇中數(shù)據(jù)對象的平均值，將每個數(shù)據(jù)對象依次劃分到最近距離聚類中心標志的簇中。

(5)如果E值變化明顯，將返回步驟(2)。

1.2 AGNES算法

[7]中提到的AGNES算法是凝聚的層次聚類方法。AGNES算法最初將每個對象作為一個簇，然后這些簇根據(jù)某些準則被一步步地合并。

AGNES算法描述如下：

輸入：包含n個數(shù)據(jù)對象的數(shù)據(jù)庫，終止條件簇的數(shù)目 c；

輸出：c個簇，達到終止條件規(guī)定簇數(shù)目。

(1)將每個數(shù)據(jù)對象當成一個初始簇；

(2)REPEAT；

(3)根據(jù)兩個簇中最近的數(shù)據(jù)點找到最近的兩個簇；

(4)合并兩個簇，生成新的簇的集合；

(5)UNTIL達到定義的簇的數(shù)目；

2 改進K-means算法

K-means算法初始聚類中心是隨機選取的，選取不當?shù)脑?，將會無法得到正確的聚類結果。而AGNES算法將最近的數(shù)據(jù)對象聚集在一起形成簇，根據(jù)AGNES算法的這種思想，提出一種新的算法來確定k個初始聚類中心。

2.1 相關概念

定義1歐式距離

定義2點的密度

數(shù)據(jù)xi和距離α，以xi為圓心，α為半徑的區(qū)域內對象的個數(shù) (包括圓心自身)記為該對象的密度，記為Density(xi)=(p 的 個 數(shù)|Distance(xi，p)≤α)， 其 中 Dis tan ce(.)為歐式距離，α取所有數(shù)據(jù)對象間距離和的平均值。

定義3平均密度

2.2 初始聚類中心的確定算法

Initial Clustering Center算法如下：

輸入：n個數(shù)據(jù)對象的數(shù)據(jù)集 DataSet，聚類簇數(shù)k，參 數(shù) θ，ClusterSet、HighSet、CenterSet 3 個 集 合 開 始 均 為空。

輸出：k個初始聚類中心數(shù)據(jù)集CenterSet。

(1)將每個對象當成一個初始簇；

(2)REPEAT；

(3)根據(jù)兩個簇中最近的的數(shù)據(jù)點找到最近的兩個簇；

(4)合并兩個簇，生成新的簇的集合；

(6)計算數(shù)據(jù)對象的平均密度Ave；

(7)對步驟(5)中生成的c個簇將其加入到ClusterSet集合中，分別計算每個簇中數(shù)據(jù)對象的個數(shù)，將個數(shù)大于Ave的簇加入到HighSet集合中；

(8)令 i=1；

(9)如果HighSet集合不為空，執(zhí)行步驟 (10)~步驟(13)；否則執(zhí)行步驟(15)~步驟(18)；

(10)REPEAT；

(11)取出HighSet集合中數(shù)據(jù)對象個數(shù)最多的簇cx；

(12)計算該簇cx中數(shù)據(jù)對象的平均值做為第i個初始聚類中心，將其加入到CenterSet集合中去，并將簇cx從 HighSet和 ClusterSet中刪除，i=i+1；

(13)UNTIL得到k個初始聚類中心；

(14)如果步驟(10)~步驟(13)生成的初始聚類中心個數(shù)小于k，并且HighSet集合為空，即執(zhí)行步驟(15)~步驟(18)；

(15)REPEAT；

(16)取出ClusterSet集合中數(shù)據(jù)個數(shù)最多的簇cx；

(17)計算簇cx中數(shù)據(jù)對象的平均值做為第i個初始聚類中心，將其加入到 CenterSet集合中去，并將簇cx從ClusterSet中刪除，i=i+1；

(18)UNTIL得到k個初始聚類中心；

(19)算法結束。

2.3 改進的K-means算法

改進K-means算法如下：

(1)運行 Initial Clustering Center算法，得到 k個初始聚類中心集合CenterSet；

(2)輸入 k值、k個初始聚類中心集合 CenterSet和數(shù)據(jù)對象集合DataSet；

(3)運行K-means算法，輸出K個聚類，算法結束。

3 改進后的實驗及分析

表1 傳統(tǒng)K-means算法和改進K-means算法的比較

從表1 Iris數(shù)據(jù)集可以看出傳統(tǒng)K-means算法的迭代次數(shù)有時比改進K-means算法要小，但是其準確率卻顯得很低。這說明K-means算法受初始聚類中心的影響比較大，一旦選擇不當，準確率將會很低，而優(yōu)化的初始聚類中心是比較穩(wěn)定的，符合數(shù)據(jù)對象的實際分布，同時可以盡快收斂最優(yōu)解并且準確率高。從隨機數(shù)據(jù)集整體上來看，改進的K-means算法的迭代次數(shù)減少，收斂速度比較快，準確率很高。所以改進的K-means算法收斂速度比較快，得到的初始聚類中心符合數(shù)據(jù)對象的實際分布，提高了聚類準確率，達到了更好的聚類效果，同時該算法在煙草配送點分配問題等領域都得到了很好的應用。

本文結合層次聚類算法AGNES算法，提出一種確定初始聚類中心的算法，使得到的初始聚類中心比較穩(wěn)定，符合數(shù)據(jù)的實際分布，避免選到孤立點，大大提高了算法的準確率和效率。同時改進的算法一個優(yōu)點是能進行異常點的發(fā)現(xiàn)，能夠對網絡異常進行檢測。但是改進K-means算法的時間復雜度不如傳統(tǒng)K-means算法，所以今后的研究方向主要是針對大數(shù)據(jù)集在時間復雜度的提高上作進一步的研究，并將改進的算法應用到其他實際領域中。

參考文獻

[1]賴玉霞，劉建平.K-means算法的初始聚類中心的優(yōu)化[J].計算機工程與應用，2008，44(10)：147-149.

[2]劉艷麗，劉希云.一種基于密度的 K-均值算法[J].計算機工程與應用，2007，43(32)：153-154.

[3]向堅持，劉相濱，資武成.基于密度的 K-Means算法及在客戶細分中的應用研究 [J].計算機工程與應用，2008，44(35)：246-248.

[4]孫秀娟，劉希玉.基于初始中心優(yōu)化的遺傳K-means聚類新算法[J].計算機工程與應用，2008，44(23)：166-168.

[5]潘崇，朱紅斌.改進K-means算法在圖像標注和檢索中的應用[J].計算機工程與應用，2010，46(4)：183-185.

[6]ESTER M，RIEGEL H P.A density based algorithm for discovering clusters in large spatial databases with noise[C].Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining(KDD-96)， Ortland，Oregon，1996.

[7]毛國君，段立娟，王實，等.數(shù)據(jù)挖掘原理與算法[M].北京：清華大學出版社，2000年.