K—means算法研究綜述

吳進(jìn)寶

摘 要

K-means算法是硬聚類算法，是典型的基于原型的目標(biāo)函數(shù)聚類方法的代表，它是數(shù)據(jù)點(diǎn)到原型的某種距離作為優(yōu)化的目標(biāo)函數(shù)，利用函數(shù)求極值的方法得到迭代運(yùn)算的調(diào)整規(guī)則。本文主要闡述了K-means的基本算法流程，總結(jié)評述了改進(jìn)的k-means算法的研究現(xiàn)狀，以及和經(jīng)典算法的比較。最后總結(jié)了k-means算法存在的一些問題，并指出了改進(jìn)的方向。

【關(guān)鍵詞】K-Means聚類算法 初始聚類中心

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

本人主要是在研究K-Means基本算法的基礎(chǔ)上，總結(jié)闡述了改進(jìn)的K-Means算法。基于向量語義相似度的K-means算法，針對傳統(tǒng)的K-Means算法的不足，提出通過向量語義相似度的計(jì)算自動確定初始聚類中心，在聚類過程中，達(dá)到語義相似度閾值的網(wǎng)頁才使用K-Means算法進(jìn)行聚類；基于初始聚類中心優(yōu)化的K-means算法，通過數(shù)據(jù)之間距離，計(jì)算密度參數(shù)，保留高密度區(qū)域，刪除低密度區(qū)域，找出數(shù)據(jù)的真實(shí)分布。

1 K-Means算法簡介

K-means算法，它是一種基于距離遠(yuǎn)近的聚類算法，同時也是一種無監(jiān)督學(xué)習(xí)算法，對以后的算法改進(jìn)具有很大的影響。該算法的優(yōu)點(diǎn)是簡單易行，容易理解，時間復(fù)雜性接近線性，對大規(guī)模數(shù)據(jù)挖掘具有高效性和可伸縮性，在科研以及實(shí)際應(yīng)用中有著很重要的作用。

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

步驟：

輸入：數(shù)據(jù)集中的n個數(shù)據(jù)對象，聚類個數(shù)為k；

輸出：滿足誤差平方和準(zhǔn)則函數(shù)最小的K個聚類；

算法流程：

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

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

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

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

2 K-Means算法改進(jìn)

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

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

2.2 基于初始聚類中心優(yōu)化的K-means算法

傳統(tǒng)的算法對初始聚類中心特別敏感，聚類結(jié)果隨不同的初始輸入而波動，基于初始聚類中心優(yōu)化的K-means算法通過計(jì)算對象相互之間的距離，產(chǎn)生密度參數(shù)，很好的排除了低密度區(qū)域的臟數(shù)據(jù)，從而也優(yōu)化了傳統(tǒng)K-Means算法對臟數(shù)據(jù)的敏感性。

3 K-means算法的其他改進(jìn)

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

4 與經(jīng)典K-means算法的比較

基于向量語義相似度的K-means算法首先計(jì)算網(wǎng)易語義之間的相似度，只有達(dá)到一定閾值時，才進(jìn)行聚類，新算法克服了傳統(tǒng)K-Means算法無法處理語義信息的問題，提高了聚類的質(zhì)量。基于初始聚類中心優(yōu)化的K-means算法通過對象相互之間的距離，產(chǎn)生密度參數(shù)，很好的排出了低密度區(qū)域的臟數(shù)據(jù)，從而也優(yōu)化了傳統(tǒng)K-Means算法對臟數(shù)據(jù)的敏感性。

5 結(jié)束語

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

參考文獻(xiàn)

[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]孫士保，秦克云.改進(jìn)的k-Means聚類算法研究[J].計(jì)算機(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.

作者單位

北京航空航天大學(xué)軟件學(xué)院 北京市 100083endprint