一種K－均值聚類的改進算法及其應用

江京亞，郭慶勝，陳 旺，周賀杰，陳 勇

（1．武漢大學 資源與環境科學學院，湖北 武漢430079；2．湖北省鄂東地質大隊，湖北 孝感432000）

聚類分析是人類理性認識自然，科學分析世界的主要手段之一。自1994年，李德仁院士在國際上首次提出空間數據挖掘與知識發現（Knowledge Discovering and Data Mining）這一概念以來，聚類分析在信息領域得到空前發展，至今已成為空間數據挖掘與知識發現的主要技術手段之一［1］。近十年來，聚類分析已經成為數據挖掘中的一個熱點，得到廣大學者的關注。綜合國內外多年的研究成果［1－5］，聚類分析常用的算法基本可分為基于劃分的算法、基于層次的算法、基于密度的算法、基于圖論的算法、基于模型的算法、基于格網的算法及其混合算法等七類方法［1］。

K－均值聚類是一種基于劃分的經典聚類算法，由于其簡單、高效，已被廣泛應用于諸如圖像處理、模式識別、人工智能和市場銷售等領域。然而K－均值聚類其本身卻存在很多缺陷，如對初始聚類中心的依賴性和對少量噪聲點的敏感性。本文正是為了較好克服這兩方面的缺陷，基于k－dist圖（又稱第k鄰近距離圖）提出了一種改進K－均值聚類算法。通過數據集的第k鄰近距離圖，獲得噪聲范圍去除噪聲點，同樣地在第k鄰近距離圖中取得點聚集區域范圍，從中選取距離相距最遠且盡量靠近真實簇中心的k′（為了區別第k鄰近距離圖中的參數k，聚類類別數用k′表示）個數據點作為初始簇中心。實驗證明改進算法能很好地去除噪聲點影響，減少迭代次數，得到穩定的聚類結果。

1 K-均值聚類算法

K－均值聚類算法是應用最為廣泛的一種空間聚類方法［4］，其基本思想是：在數據集范圍內，隨機選取k′個對象作為初始簇中心，然后將數據集中每個對象分配到離它最近的初始簇中心分為一類。處理完后，整個數據集暫時被劃分為k′個簇，更新簇中心（一般是取此簇中所有對象的平均值），重復上述步驟直到達到一定迭代次數或滿足一定的平方誤差準則為止。

K－均值算法由于是在數據集范圍內隨機選取初始簇中心，難以正確反映數據集的性質，聚類結果波動較大，穩定性差。與此同時，在更新簇中心時，采取簇內所有對象的平均值，少量遠離數據聚集區的噪聲點的加入會使計算結果產生誤差，偏離真正的聚類中心，較大地影響聚類結果，甚至可能產生不準確的結果。

近些年，針對K－均值聚類算法對初始中心的依賴性和對噪聲點的敏感性，許多學者提出了改進算法。文獻［2］在K－均值算法引入混合粒子群優化算法思想，將k′個聚類中心整體作為一個粒子，尋找最優解得到聚類結果。該方法能改善K－均值聚類對于初始聚類中心依賴的缺陷，加快收斂速度，具有很好的全局尋優能力。文獻［3］基于高密度區域數據被低密度區域數據所分割的思想，從高密度區域選取k′個相距最遠的點作為初始聚類中心，能很好體現數據的分布情況，消除算法對初始聚類中心的依賴。文獻［4］用迪杰斯特拉最短距離作為數據對象之間的距離，初始中心選擇距離和平均值最小的數據對象，進行K－均值聚類。該方法能消除噪聲點的影響，取得較好的聚類結果。這些改進算法雖在一定程度上克服某一方面的缺陷，如對初始中心點依賴性，但無法兼顧噪聲點影響，或者消除噪聲點，初始聚類中心選取卻無法顧及，而且實現起來都比較復雜。

2 第k鄰近距離圖

在待聚類分析的數據集中，計算每個數據對象離它最近的第k個數據對象的距離（文章后面就稱第k鄰近距離），然后將此距離序列降序排列，繪制成一個折線圖，即為第k鄰近距離圖，圖1為人工數據集Point1及其第4鄰近距離圖。橫坐標代表第k鄰近距離排序后的點序列號（和實際讀入的數據序列順序不同），縱軸代表橫軸序列點所對應的第k鄰近距離。

第k鄰近距離圖最早是由Martin Ester［5］等為確定一種密度聚類－DBSCAN方法的鄰域半徑參數而做的圖，曲線走向變化較大的那個數據對象所對應的第k鄰近距離即為鄰域半徑（如圖1（b）中箭頭所指的縱坐標值）。第k鄰近距離圖能很好地反映一個數據集的分布情況。曲線從左邊以陡峭的趨勢快速下降到一個臨界值－臨界第k鄰近距離，然后以較小的第k鄰近距離趨于平緩，即為數據聚集的地帶。由于噪聲點數量少，分布離散，因此從左邊開始下降速度較快，呈陡峭形勢，而在數據聚集區域，數據對象的第k鄰近距離都相對較小，較為集中，曲線呈平緩趨勢。數據對象的第k鄰近距離越小，其為簇中心的可能性越大，反之，其為噪聲點的可能性越大。

文獻［5］研究發現，第k鄰近距離圖中當k＞4時，如k＝8，繪制出來的曲線整體趨勢與k＝4繪出的曲線變化很小，因此本文取k＝4。

圖1 Point1數據集及其第4鄰近距離圖

3 改進后的K-均值算法

3．1 算法思想及流程

做出數據集的第4鄰近距離圖，由于數據對象的第4鄰近距離越小，其為簇中心的可能性越大，反之，則其為噪聲點的可能性越大，因此需要找出噪聲臨界點（曲線趨勢顯著變化的那個數據點）所對應的第4鄰近距離（稱臨界第4鄰近距離），然后從數據集中清除那些第4鄰近距離大于臨界第4鄰近距離所對應的數據點，得到整理后的數據集。接著在第4鄰近距離圖中平緩帶（數據點密集段）所對應的數據點集中選取相距最遠的k′個數據點作為初始簇中心，然后按照最近距離將各個數據分配到離它最近的簇中心，更新簇中心，直到達到一定迭代次數或滿足一定的誤差平方準則為止。

改進算法主要是基于第4鄰近距離圖，獲得噪聲范圍去除噪聲點，然后選取盡量靠近數據聚集區的k′個初始簇中心，因此迭代次數少，聚類穩定，同時消除噪聲點的影響，所得結果較好。

3．2 去除噪聲點

噪聲點往往是遠離數據聚集區的孤立點，數量不多，因此處在4－鄰近圖中陡峭的一段中。做出第4鄰近距離圖后，找到臨界第4鄰近距離，將此距離作為數據點的第4鄰近距離的閾值，去除那些第4鄰近距離大于該臨界第4鄰近距離所對應的數據點，即得到去噪后的數據集。

輸入：含n個對象的待聚類數據集P

輸出：去噪后數據集P1，第4鄰近距離圖

具體步驟如下：

1）讀取數據集P，計算P中每個數據對象pi（i＝1，2，3，…，n）的第4鄰近距離，并存儲在temp Dist（pi）中。

2）將temp Dist（pi）降序排序，并制作出第4鄰近距離圖。

3）順序計算圖中相鄰3點之間的轉角ɑ，找到最大轉角ɑ所對應的數據點，將該數據點設為臨時臨界點，然后依據第4鄰近距離圖人工判斷其合理性，若不符合數據分布特征，則重新指定。確定該臨界點的第4鄰近距離為臨界第4鄰近距離dist－Threshol d（如圖1（b）中箭頭所指臨界點所對應的第4鄰近距離）。

4）將每個數據點的第4鄰近距離與dist－Threshol d比較，若大于或等于dist－Threshol d，則該點是噪聲點，從P中刪除該點，否則保留此點。

5）處理完所有數據后得到去噪后數據集P1，同時將第4鄰近距離圖保留下來。

如圖2所示，對于數據集Point1，選用傳統K－均值聚類算法處理得到的多個聚類結果中較好的一個，如圖2（a）中所示，其最終生成的3類簇中包含大量噪聲點，簇的中心（圖2（a）中十字架所在位置）也偏離了真正的簇中心，而采用本文方法得到的結果，則去除了噪聲點只保留了數據點聚集的3個簇，簇的中心也在數據集正中間，聚類效果較好。但是必須注意到很多數據的分布并不是很理想化，即數據聚集區和噪聲點可以明顯區分開，很多數據簇的界線是模糊的，如圖3所示，此時將最大轉角a對應的數據點設置為臨時臨界點，依據第4鄰近距離圖，發現其并不合理，應順序后移重新設置臨界點，而其第4鄰近距離作為臨界第4鄰近距離。

圖2 傳統K-均值聚類與改進K-均值聚類結果比較

圖3 point2數據集及其第4鄰近距離圖

3．3 k′個初始簇中心的確定

經過去噪后的數據集P1沒有噪聲點的干擾，可以開始進行K－均值聚類。在第4鄰近距離圖中找到數據點密集分布的那個平緩帶，提取第4鄰近距離的范圍C（事實上在去噪的同時提取第4鄰近距離的最大值和最小值），找到第4鄰近距離在此范圍內的數據集P2，取最小的第4鄰近距離所對應的那個點作為第1個初始簇中心k′1，然后在數據集P2選取離k′1最遠的數據點作為第2個初始中心k′2，同理第3個初始簇中心k′3選取離k′1，k′2最遠的點，以此類推直到k′個初始簇中心都找到為止。

輸入：去噪后數據集P1，聚類個數k′

輸出：k′個初始簇中心集合

具體步驟如下：

1）利用去噪時制作的第4鄰近距離圖，找出數據點密集分布的平緩帶C，其中第4鄰近距離dist－Threshol d可作為C的上界，下界則為最小4－鄰近距離。

2）從數據集P1中選擇第4鄰近距離在C段的數據點，完成選擇后得到數據集P2。

3）將最小第4鄰近距離所對應的數據點作為第1個初始簇中心k′1，在P2中找到距離k′1最遠的數據點作為第2個初始簇中心k′2，同理，第3個初始簇中心k′3選取離k′1，k′2最遠的數據點，即得到的k′3與k′1，k′2之間的最小距離最大。以此類推，直到找到k′個初始簇中心。

4）輸出k′個初始簇中心集合。

圖4即為數據集Point1的初始簇中心選擇，十字架所在位置即為初始簇中心，圖4（b）是改進后的K－均值聚類方法選取的初始簇中心，初始簇中心已經很靠近數據點聚集區了，迭代次數少，聚類穩定，而圖4（a）則是傳統K－均值算法中選取的初始簇中心，它們已經偏離了真正的數據聚集區，增加了迭代次數，產生的結果也有誤差。

圖4 改進前后K-均值聚類初始簇中心

4 實驗結果及其應用

數據來源于網絡爬蟲軟件在2013年6月采集到的47個類型130 683個興趣點集，本文從中選用了屬于河北省張家口市，類型為“小區”的251個子點集，每個數據點包含9個屬性，共有3個聚類。運用本文改進的K－均值聚類算法后得出的實驗結果見圖5。

圖5 改進算法后所得結果

從圖5可以看出，改進算法去除了少量的噪聲點（圖5（a）中三角板所在位置），獲得了3個主要小區點密集分布區域（圖5（b）中3個斑塊，也是點集的凸包），效果較好。由于傳統的K－均值聚類處理該數據集的不穩定性，進行了10次實驗，取其迭代次數平均值（見表1），為3．6次，而采用本文算法只需迭代2次，實驗結果也比較滿意。在運行時間上，傳統K－均值平均運行1 367．9 ms，而本文算法只需738．6 ms，效率提高了46%。這是由于改進算法選取的初始簇中心是盡量靠近點集密集區的數據點，離真正的簇中心很接近，聚類迭代次數少，只需2次就能完成聚類，實驗結果穩定，效率高。

表1 改進前后K-均值聚類算法迭代次數和執行時間

聚類分析是信息挖掘的有效工具之一。通過K-均值聚類分析居民居住小區的聚集區域，往往可以得到很多信息。例如，選址一直是關系經營者盈利與否的關鍵問題［6］，商場建在那里才能保證人流量足夠大，當然也可以結合小區周圍的商場、超市等數據點一起分析，怎樣才能確定既不和其它商場或超市沖突又能保證足夠客流量的最佳位置。利用本文改進的K－均值聚類算法對小區數據點去噪，聚類得到3個小區點數據集，進而生成3個數據集的凸包，得到小區密集區域，即居民常住區域，可以直觀地觀察到居民的生活范圍。為居民提供服務的行業，如餐廳，服裝店，商場、KTV等等可以選擇在其周圍建立，保證其利潤最大化。同時，本文提出的算法也可以用來確定傳染病重癥區，合理安排救治人員；劃分旅游景點聚集區，規劃最佳旅游路線等等，實用性較好。

5 結束語

針對K－均值聚類對初始簇中心選取的依賴性和對噪聲點的敏感性，基于第k鄰近距離圖，提出了一種改進的聚類算法。該算法去除第k鄰近距離較大的噪聲點后，選取處于第k鄰近距離圖中平緩帶－數據點密集區中的k′個相距最遠的數據點作為初始簇中心。實驗證明了改進后算法迭代次數少，聚類穩定，所得結果理想。與此同時，結合實際應用，驗證了本文算法的實用性，希望能為選址、規劃等一些特定問題決策提供參考。

［1］鄧敏，劉啟亮，李光強，等．空間聚類分析及應用［M］．北京：科學出版社，2011．

［2］但漢輝，張玉芳，張世勇．一種改進的 K－均值聚類算法［J］．重慶工商大學學報：自然科學版，2009，26（2）：144－147．

［3］傅德勝，周辰．基于密度的改進K均值算法及實現［J］．計算機應用，2011，31（2）：432－434．

［4］仇新玲．K－均值聚類算法改進及應用［D］．北京：北京郵電大學，2012．

［5］ESTER M，KRIEGEL H－P，SANDER J，et al．A densitybased algorit h m for discovering clusters in large spatial databases with noise［C］／／KDD－96：Proceedings of 2nd Inter national Conference on Knowledge Discovery and Data Mining．Menlo Par k：AAAI Press，1996：226－231．

［6］付金輝，趙軍喜，高源．基于灰色預測法的超市選址模型研究［J］．測繪工程，2013，22（5）：46－50．

［7］WANG M，WANG A P，LI A B．Mining spatial－temporal clusters fro m geo－database［J］．Lect Notes Artif Intell，2006，4093：263－270．

［8］殷君偉．K－均值聚類算法改進及其在服裝生產的應用研究［D］．蘇州：蘇州大學，2013．

［9］鄭丹，王潛平．K－Means初始聚類中心的選擇算法［J］．計算機應用，2012，32（8）：2186－2188．

［10］劉艷麗，劉希云．一種基于密度的 K－均值算法［J］．計算機工程與應用，2007，43（32）：153－155．