廖禮

摘 要 聚類分析在科研和商業(yè)中都有著非常重要的應(yīng)用。其算法可以被劃分為五類：劃分方法、層次方法、基于密度方法、基于網(wǎng)格方法和基于模型方法。K-means算法是聚類分析中一種常用的劃分方法。但是隨著數(shù)據(jù)量的增加，K-means算法的局限性日益突出。于是針對(duì)K-means算法的各種改進(jìn)算法應(yīng)運(yùn)而生。本文主要介紹了兩種典型的改進(jìn)K-means算法。

關(guān)鍵詞 聚類分析 K-means算法 改進(jìn)的K-means算法

中圖分類號(hào)：TP484.9 文獻(xiàn)標(biāo)識(shí)碼：A

0引言

聚類分析是指將物理或抽象對(duì)象的集合分組成為由類似的對(duì)象組成的多個(gè)類的分析過程。它是一種重要的數(shù)據(jù)挖掘技術(shù)，是分析數(shù)據(jù)并從中發(fā)現(xiàn)有用信息的一種有效手段，被廣泛應(yīng)用在商業(yè)、生物、地理、保險(xiǎn)業(yè)、因特網(wǎng)等方面。作為統(tǒng)計(jì)學(xué)的一個(gè)分支和一種無監(jiān)督的學(xué)習(xí)方法， 聚類從數(shù)學(xué)分析的角度提供了一種準(zhǔn)確、細(xì)致的分析工具。

1 K-means算法

K-means算法首先隨機(jī)地在N個(gè)對(duì)象中選取k個(gè)數(shù)，作為初始聚類中心（即把N個(gè)對(duì)象分為k個(gè)簇），采用距離作為相似性的評(píng)價(jià)指標(biāo)，認(rèn)為兩個(gè)對(duì)象的距離越近，其相似度就越大。相似度通過一個(gè)簇中對(duì)象的平均值來計(jì)算。然后按最小距離原則將N個(gè)對(duì)象劃分到不同的簇中。最后不斷迭代計(jì)算聚類中心和調(diào)整各對(duì)象的類別，最終使每個(gè)對(duì)象到其判屬的聚類中心的距離的平方和最小。步驟如下：

（1）在N個(gè)對(duì)象中隨機(jī)地選取k個(gè)數(shù)作為初始聚類中心，即c1…ck；

（2）將N個(gè)對(duì)象按最小距離原則找到離它最近的聚類中心ci，并將其劃分到ci所標(biāo)明的簇中；

（3）計(jì)算每個(gè)簇中對(duì)象的均值，并且該均值作為該簇新的聚類中心；

（4）重復(fù)（2）—（3）步，直到?jīng)]有對(duì)象或很少的對(duì)象被分配到不同的簇中。

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

2.1 K-means++算法

K-means++算法相較于K-means算法的不同之處是在對(duì)初始聚類中心的選取上，不同于K-means的隨機(jī)選取，K-means++只有第一個(gè)初始聚類中心是隨機(jī)選取的，其余k-1個(gè)則是根據(jù)一定的概率來有目地選擇初始聚類中心。比傳統(tǒng)的K-means算法在速度和精確性上都有了顯著地提高。步驟如下：

（1）在N個(gè)對(duì)象中隨機(jī)地選取1個(gè)數(shù)作為初始聚類中心，即c1；

（2）以概率P繼續(xù)在N個(gè)對(duì)象中隨機(jī)地選取新的數(shù)作為下一個(gè)初始聚類中心，即ci；

其中，P為選取新的聚類中心的概率：p=D（x）2/D（x）2式中，D（x） 表示一個(gè)對(duì)象到已經(jīng)選擇好的初始聚類中心的最小距離；

（3）重復(fù)步驟（2）直到選擇到k個(gè)初始聚類中心；

（4）同K-means算法步驟（2）—（4）；

2.2基于均衡化評(píng)價(jià)函數(shù)的K-means改進(jìn)算法

由上式，可以看出不需要事先給定k值而自動(dòng)生成聚類的數(shù)目，為實(shí)際應(yīng)用提供了很大的便利。根據(jù)大量的實(shí)驗(yàn)結(jié)果表明，k的值不會(huì)超過。算法從l到取整，循環(huán)執(zhí)行K-means算法，以均衡化的評(píng)價(jià)函數(shù)作為準(zhǔn)則函數(shù)，搜索評(píng)價(jià)函數(shù)值最小的并記下相應(yīng)的k值，即最優(yōu)聚類的結(jié)果。改進(jìn)的算法自動(dòng)生成聚類數(shù)目，其中在將樣本對(duì)象聚類到最近的簇時(shí)，屬于最近鄰搜索問題，采用擴(kuò)展的部分失真搜索算法。利用最近鄰搜索算法減少算法的層次數(shù)，大大降低算法的時(shí)間復(fù)雜度。步驟如下：

（1）輸入N個(gè)對(duì)象作為樣本空間；

（2）For i=1 to do；

（3）任意選擇個(gè)對(duì)象作為初始聚類中心；

（4）計(jì)算簇中的均值，使用EPDS算法將每個(gè)樣本賦給最近的簇；

（5）更新簇的均值；

（6）計(jì)算J（c，k）直到其收斂為之，否則返回到（4）；

（7）搜索均衡化函數(shù)J（c，k）的最小值，記錄下相應(yīng)的k值；

（8）結(jié)束。

3總結(jié)

K-means算法作為聚類分析經(jīng)典的方法之一，對(duì)大型數(shù)據(jù)集的處理效率較高，尤其是對(duì)樣本分布呈現(xiàn)類團(tuán)聚狀時(shí)，可以達(dá)到很好的聚類效果。但是作為一個(gè)NP問題，它對(duì)初始聚類中心的選擇以及k值大小的確定有很大的依賴性，在一定程度上限制了K-means算法的實(shí)際應(yīng)用。本文主要總結(jié)了兩種改進(jìn)后的K-means算法，通過與傳統(tǒng)的K-means比較，改進(jìn)后的算法更加穩(wěn)定，速度更快，時(shí)間花費(fèi)小，應(yīng)用更廣。當(dāng)然改進(jìn)后的算法也不是完美無暇的，依然存在著一些不足之處，因此希望此文能對(duì)今后改進(jìn)K-means算法提供一些理論指導(dǎo)。

參 考 文 獻(xiàn)

[1] Mahamed G.H. Omran， Andries P. Engelbrecht and Ayed Salman .An overview of clustering methods[J].Intelligent Data Analysis， 2007（11）：583-605.

[2] 張建輝.k-means聚類算法研究及應(yīng)用[D].武漢：武漢理工大學(xué)，2007.

[3] 張玉芳，毛嘉莉，熊忠陽.一種改進(jìn)的K2means算法[J].計(jì)算機(jī)應(yīng)用， 2003，23（08）.

[4] 施培蓓，錢雪忠，汪中.基于均衡化函數(shù)的快速K-means算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44 （03）：189-191.endprint