K—means算法研究綜述

吳進寶

摘 要

K-means算法是硬聚類算法，是典型的基于原型的目標函數聚類方法的代表，它是數據點到原型的某種距離作為優化的目標函數，利用函數求極值的方法得到迭代運算的調整規則。本文主要闡述了K-means的基本算法流程，總結評述了改進的k-means算法的研究現狀，以及和經典算法的比較。最后總結了k-means算法存在的一些問題，并指出了改進的方向。

【關鍵詞】K-Means聚類算法 初始聚類中心

K-means聚類算法是由J.B.MacQueen在1967年提出的，之后迅速應用在不同的學科和領域。雖然K-means聚類算法被提出有50多年了，但目前還是被應用最廣泛的算法之一。其容易實施、簡單、高效的 特征，以及解決無數成功案例，仍然使其依舊是被研究的熱點。

本人主要是在研究K-Means基本算法的基礎上，總結闡述了改進的K-Means算法?；谙蛄空Z義相似度的K-means算法，針對傳統的K-Means算法的不足，提出通過向量語義相似度的計算自動確定初始聚類中心，在聚類過程中，達到語義相似度閾值的網頁才使用K-Means算法進行聚類；基于初始聚類中心優化的K-means算法，通過數據之間距離，計算密度參數，保留高密度區域，刪除低密度區域，找出數據的真實分布。

1 K-Means算法簡介

K-means算法，它是一種基于距離遠近的聚類算法，同時也是一種無監督學習算法，對以后的算法改進具有很大的影響。該算法的優點是簡單易行，容易理解，時間復雜性接近線性，對大規模數據挖掘具有高效性和可伸縮性，在科研以及實際應用中有著很重要的作用。

按照K-means的基本思想，可以將K-means聚類算法描述如下：

步驟：

輸入：數據集中的n個數據對象，聚類個數為k；

輸出：滿足誤差平方和準則函數最小的K個聚類；

算法流程：

（1）從n個數據對象中隨機選取k個對象作為初始聚類中心；

（2）計算數據集中各個數據對象與聚類中心的距離，并根據最小距離對數據對象進行類群劃分；

（3）在形成的子類群中，重新計算每個聚類中所包含的數據對象的平均值作為新的聚類中心；

（4）循環流程（2）到（3）直到前后兩次迭代得到的每個類群的中心點不再高于某個閾值為止。

2 K-Means算法改進

2.1 基于向量語義相似度的K-means算法

針對傳統的K-Means算法對網頁處理的不足，以及其在文本聚類中存在的局限性，提出了基于網頁向量語義相似度的改進K-Means算法。新算法通過向量語義相似度的計算確定初始聚類中心，在聚類過程中，達到語義相似度閾值的網頁才使用K-Means算法進行聚類。新算法很好地克服了傳統K-Means算法隨機選取聚類中心以及無法處理語義信息的問題，提高了聚類的質量。

2.2 基于初始聚類中心優化的K-means算法

傳統的算法對初始聚類中心特別敏感，聚類結果隨不同的初始輸入而波動，基于初始聚類中心優化的K-means算法通過計算對象相互之間的距離，產生密度參數，很好的排除了低密度區域的臟數據，從而也優化了傳統K-Means算法對臟數據的敏感性。

3 K-means算法的其他改進

在K-means聚類算法中，每個數據點都被唯一的劃分到一個類別中，這被稱為硬聚類算法，它不易處理聚類不是致密而是殼型的情形。這對這一情況，Dunn等人于1973年提出了模糊K-means聚類算法。Kashima等人于2008年使用L1距離，最終聚類中心是每一類的中位向量。對于一維數據集X={x1，x2，x3，…，xi，…，xn}而言，中位數M比均值對異常數據有較強的抗干擾性，聚類結果受數據中異常值的影響較小。Mao & Jain[4]于1996年提出使用Mahalanobis距離，但計算代價太大。在應用中，Linde等于1980年提出使用Itakura-Saito距離。Banerjee等人2004年提出，如果使用Bregman差異作為距離度量，有許多突出優點，如克服局部最優、類別之間的線性分離、線性時間復雜度等。

4 與經典K-means算法的比較

基于向量語義相似度的K-means算法首先計算網易語義之間的相似度，只有達到一定閾值時，才進行聚類，新算法克服了傳統K-Means算法無法處理語義信息的問題，提高了聚類的質量?；诔跏季垲愔行膬灮腒-means算法通過對象相互之間的距離，產生密度參數，很好的排出了低密度區域的臟數據，從而也優化了傳統K-Means算法對臟數據的敏感性。

5 結束語

對于K-means算法，筆者比較感興趣的是未來K-means算法對于稀疏數據的處理能力。大家都知道，隨著大型互聯網公司的發展，以及商品數量的增多，數據對象稀疏問題對聚類過程影響很大，現在已有的處理數據稀疏的技術，比如平均、平滑等，筆者不是很滿意。我們可以假設數據對象的屬性就好比一個人在不同成長階段的性格，沒必要刻意塑造，而在于它自己豐富。

參考文獻

[1] Meng Jianliang， Shang Hai kun，Bian Ling. The application on intrusion detection based on K-means cluster algorithm [C].International Forum on InformationTechnology and Applications，2009：150-152.

[2]孫士保，秦克云.改進的k-Means聚類算法研究[J].計算機工程，2007（07）：200-202.

[3]Dunn JC.A fuzzy relative of the isodata process and itsuse in detecting compact well-separated clusters [J].Journal of Cybernetics，1973（3）：32-57.

[4]Mao J，Jain A K.A self-organizing network for hyper-ellipsoidal clustering.IEEE Transactions on neural net-works，1996（7）：16-29.

作者單位

北京航空航天大學軟件學院 北京市 100083endprint