鄭帥　趙曉東

摘要：聚類算法在自然科學(xué)和和社會(huì)科學(xué)中都有很普遍的應(yīng)用，而K-means算法是聚類算法中經(jīng)典的劃分方法之一。但如果數(shù)據(jù)集內(nèi)相鄰的簇之間離散度相差較大，或者是屬性分布區(qū)間相差較大，則算法的聚類效果十分有限。本文基于離散度的思想，采用新的加權(quán)距離函數(shù)代替了傳統(tǒng)算法的歐氏距離，在一定程度上優(yōu)化了k-means算法的聚類結(jié)果。

關(guān)鍵詞：聚類；k-means算法；離散度

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）34-0167-03

1 概述

在當(dāng)今時(shí)代，數(shù)據(jù)可以說是最寶貴的財(cái)富，數(shù)據(jù)挖掘算法成了發(fā)掘數(shù)據(jù)財(cái)富的最有效手段，而聚類分析可以算是數(shù)據(jù)挖掘算法的重要組成部分。聚類分析是指根據(jù)物理或者抽象對(duì)象的集合相似度來分組的分析過程，目標(biāo)是盡量將類似的對(duì)象歸為一類。聚類源于各種領(lǐng)域，包括計(jì)算機(jī)科學(xué)，數(shù)學(xué)，統(tǒng)計(jì)學(xué)，經(jīng)濟(jì)學(xué)和生物學(xué)等。用于衡量不同數(shù)據(jù)元素之間的相似性，并根據(jù)相似性將數(shù)據(jù)元素歸類到不同的簇中。而根據(jù)對(duì)象間相似性度量和聚類評(píng)價(jià)準(zhǔn)則的不同，聚類方法可以分成五類：層次方法，劃分方法，基于密度的方法，基于網(wǎng)格的方法和基于模型的方法[1]。

K-means算法是很典型的基于距離的聚類算法，同是也是一種基于劃分的算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)。該算法簡(jiǎn)單且易于使用，運(yùn)行速度快，與其他聚類算法相比應(yīng)用更加廣泛[2]。但同時(shí)k-means的缺陷也十分明顯。首先，算法只能求得局部最優(yōu)解，無法得到全局最優(yōu)；其次，算法是硬聚類，初始中心點(diǎn)的選擇對(duì)最終結(jié)果的影響相當(dāng)大；再次，對(duì)于異常點(diǎn)非常敏感；最后，對(duì)于簇間離散度相差較大的數(shù)據(jù)集的邊界點(diǎn)分類效果不好。

針對(duì)k-means的缺陷，出現(xiàn)了許許多多不同的改進(jìn)，主要針對(duì)類別個(gè)數(shù)K的選擇，初始中心點(diǎn)，異常點(diǎn)剔除，相似性度量和聚類評(píng)價(jià)準(zhǔn)則這四個(gè)方面。對(duì)于最佳聚類數(shù)的確定，國外學(xué)者Hamerly等提出了對(duì)于簇?cái)?shù)量的估算方法[3]，可以根據(jù)簇的分布估算出K的大小，國內(nèi)學(xué)者周世兵[4]等從樣本幾何結(jié)構(gòu)的角度設(shè)計(jì)了一種新的聚類有效性指標(biāo)，并在此基礎(chǔ)上提出了一種新的確定最佳聚類數(shù)的方法；關(guān)于初始中心點(diǎn)的選擇，朱顥東[5]等提出的使用改進(jìn)的模擬退火算法來優(yōu)化初始中心點(diǎn)，將退火算法和k-means結(jié)合在一起，較好的改進(jìn)了算法對(duì)初始中心點(diǎn)敏感這一缺點(diǎn)；對(duì)于樣本異常點(diǎn)對(duì)于分類的影響，張玉芳[6]等提出了基于取樣的劃分思想，直接在樣本層面排除了一部分的異常點(diǎn)，張琳[7]等采用密度的思想，通過設(shè)定EPS領(lǐng)域以及EPS領(lǐng)域內(nèi)至少包含的對(duì)象數(shù)minpts來排除孤立點(diǎn)，并將不重復(fù)的核心點(diǎn)作為初始聚類中心；最后關(guān)于k-means相似性度量和聚類評(píng)價(jià)準(zhǔn)則，這一直是改進(jìn)的主要方向，特別是對(duì)于原算法使用的歐氏距離，Mao & Jain[8]提出了Mahalanobis距離來代替，但是本身缺點(diǎn)也很明顯。后來，先后出現(xiàn)了Itakura-Saito，Bregman等距離，相對(duì)于歐式距離有許多突出優(yōu)點(diǎn)，如克服局部最優(yōu)，線性時(shí)間復(fù)雜度等[9]。

2 K-means算法的基本思想和過程

2.1 K-means基本思想

k-means算法是硬聚類算法，它將數(shù)據(jù)元素到中心點(diǎn)的某種距離作為聚類規(guī)則并迭代求極小值，是基于原型的目標(biāo)函數(shù)聚類方法的代表。最原始的k-means算法用元素點(diǎn)到中心點(diǎn)的歐式距離作為相似度測(cè)度，本質(zhì)是一種貪心的思想，只選擇當(dāng)前所能看到的最優(yōu)解，所以只能得到局部最優(yōu)解。算法以K為簇的數(shù)量，一旦確定在算法執(zhí)行過程中就不會(huì)改變，把n個(gè)對(duì)象分為K簇，k-means的核心思想就是先從n個(gè)待聚類對(duì)象中選出K個(gè)點(diǎn)作為第一次聚類的初始中心點(diǎn)，而剩余的對(duì)象則根據(jù)相似度測(cè)度即到中心點(diǎn)的歐式距離分配到離得最近的簇，分配結(jié)束后計(jì)算新形成的簇的中心點(diǎn)。這是個(gè)迭代的過程直到中心點(diǎn)不再有較大的變化，達(dá)到聚類的效果。顯然，k-means的幾個(gè)主要的缺點(diǎn)，初始K值難以確定、初始中心點(diǎn)選擇影響較大也是因此而來。

2.2 K-means算法的基本過程

第一步：在X中任意選擇k個(gè)對(duì)象作為初始的簇中心；

第二步：REPEAT；

第三步：計(jì)算每個(gè)對(duì)象到每個(gè)簇中心點(diǎn)的距離，將每個(gè)對(duì)象分配給離得最近的簇（即最相似的簇）；

第四步：根據(jù)新的聚類計(jì)算每個(gè)簇新的中心點(diǎn)；

第五步：直到每個(gè)簇的中心不再變化，或者變化小于某個(gè)閾值。

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

3.1 改進(jìn)的出發(fā)點(diǎn)

對(duì)于數(shù)據(jù)集來說如何才算是好的劃分，除了要使同一簇中的對(duì)象相似，不同簇之間的對(duì)象不相似外，還應(yīng)該看聚類結(jié)果是否能揭示數(shù)據(jù)的內(nèi)在聯(lián)系，得到合理的可解釋的數(shù)據(jù)分類[10]。但是一個(gè)數(shù)據(jù)集內(nèi)的簇不可能都是分布均勻的，他們之間的離散度可能相差很大。這種情況下，傳統(tǒng)k-means算法很難有很高的聚類正確率，特別是對(duì)于離散度比較大的簇，由于其準(zhǔn)則函數(shù)是將各個(gè)簇的誤差平方值直接相加而得到的，很容易將大離散度的簇的元素點(diǎn)，特別是兩個(gè)簇的邊界點(diǎn)，分配給離散度小的元素集中的簇，從而影響了聚類的質(zhì)量。所以改進(jìn)的出發(fā)點(diǎn)就在聚類評(píng)價(jià)準(zhǔn)則。我們都知道，標(biāo)準(zhǔn)差可以用來描述組內(nèi)個(gè)體間的離散程度，假設(shè)有一組數(shù)值則其標(biāo)準(zhǔn)差公式為：

3.2 對(duì)象分配以及算法的改進(jìn)

改進(jìn)后的距離公式如下所示：

最近的元素點(diǎn)。該分配函數(shù)目的是使得簇的離散度和簇內(nèi)元素的粘合度也成為影響分類的因素，[1σ2]這個(gè)懲罰系數(shù)在一定程度上增加了元素點(diǎn)分配給離散度大的簇的概率，當(dāng)元素點(diǎn)到達(dá)兩個(gè)簇中心的距離相近時(shí)更傾向于分配給離散度大的點(diǎn)；相比于傳統(tǒng)的k-means距離函數(shù)，改進(jìn)之后的函數(shù)加入了待分配點(diǎn)到離其最近的點(diǎn)的距離，使得簇內(nèi)元素之間的距離和簇之間的距離也成為分類時(shí)需要考量的因素。試想離散度比較大的簇，或者說屬性分布區(qū)間比較大的簇，如果分配函數(shù)只計(jì)算到中心點(diǎn)的距離，對(duì)于這個(gè)簇的邊界點(diǎn)，誤分的概率幾乎是百分之百。而且分配錯(cuò)誤的結(jié)果會(huì)引起中心點(diǎn)相應(yīng)的偏離，造成更大的誤差。改進(jìn)后的k-means算法對(duì)于離散度均勻的數(shù)據(jù)集，聚類效果和傳統(tǒng)k-means算法相近；但是對(duì)于存在兩個(gè)距離過近的簇的數(shù)據(jù)集，改進(jìn)算法的效果會(huì)比傳統(tǒng)k-means算法差。

聚類對(duì)象分配函數(shù)改進(jìn)之后，元素點(diǎn)不再直接分配到距離最近中心點(diǎn)所在那個(gè)簇中，而是綜合考慮上述幾點(diǎn)因素，根據(jù)加權(quán)距離來確定最后的歸屬，而算法的聚類準(zhǔn)則函數(shù)和重新選取中心點(diǎn)的函數(shù)還是和傳統(tǒng)k-means算法一樣。改進(jìn)后的k-means算法的具體過程如下：

輸入：含有N個(gè)對(duì)象的數(shù)據(jù)集以及簇的個(gè)數(shù)k；

輸出：在k個(gè)中心點(diǎn)穩(wěn)定之后的k個(gè)簇；

第一步：在數(shù)據(jù)集中隨機(jī)選取k個(gè)對(duì)象作為初始的簇中心；

第二步：REPEAT；

第三步：使用改進(jìn)之后的距離函數(shù)計(jì)算每個(gè)對(duì)象到每個(gè)簇中心點(diǎn)的距離，使dist（）最小，將每個(gè)對(duì)象分配給離得最近的簇（即最相似的簇）；

第四步：根據(jù)新的聚類計(jì)算每個(gè)簇新的中心點(diǎn)并計(jì)算此簇的標(biāo)準(zhǔn)差；

第五步：直到元素點(diǎn)的類別不在變化。

從上面的算法步驟可以看出，改進(jìn)后的算法和傳統(tǒng)k-means步驟上沒有什么區(qū)別，只有dist函數(shù)不一樣。自然，改進(jìn)后的算法時(shí)間復(fù)雜度比之傳統(tǒng)k-means算法要高一些。

4 試驗(yàn)和結(jié)果分析

模擬試驗(yàn)使用的數(shù)據(jù)由MATLAB生成，包含一個(gè)數(shù)據(jù)集，數(shù)據(jù)集如圖1所示：

數(shù)據(jù)集包含兩個(gè)相鄰的圓形簇。所有的數(shù)據(jù)點(diǎn)都是用的MATLAB隨機(jī)方法生成，具體的數(shù)據(jù)見表1。

兩個(gè)數(shù)據(jù)集的特點(diǎn)都是相鄰的簇的離散度相差比較大，其中一個(gè)簇的數(shù)據(jù)元素的屬性分布比較廣，而且簇之間的距離比較近。分別對(duì)兩個(gè)數(shù)據(jù)集上運(yùn)行傳統(tǒng)的k-means算法和改進(jìn)的k-means算法。數(shù)據(jù)集二的試驗(yàn)結(jié)果如下所示，圖3是傳統(tǒng)k-means算法的聚類結(jié)果，圖4是改進(jìn)算法的聚類結(jié)果。

從以上結(jié)果中可以看出，離散度大的簇的邊界點(diǎn)有很大一部分被分配給小而密的簇。簇1中共有23個(gè)數(shù)據(jù)點(diǎn)被誤分給了簇2，誤分率為11.5%，直接使用歐式距離分類的缺陷非常明顯，同一個(gè)簇的元素間的聯(lián)系完全沒有被考慮在內(nèi)。

改進(jìn)版算法的聚類結(jié)果如下圖所示，簇1中有7個(gè)點(diǎn)被錯(cuò)誤的分類，誤分率為3.5%，具體對(duì)比見表2。

對(duì)比可以看出，在模擬數(shù)據(jù)集下改進(jìn)后的算法的正確率相對(duì)于傳統(tǒng)k-means有一定的提高。

5 結(jié)論

通過改進(jìn)迭代過程中的分配函數(shù)，將到各個(gè)簇中心的歐式距離調(diào)整為到簇中心的距離加上到簇內(nèi)離其最近元素點(diǎn)的距離之和，并將[1σ2]作為懲罰因子。在簇離散度不均勻且相鄰簇大小相差較大的數(shù)據(jù)集上，元素點(diǎn)將更有可能分配給簇內(nèi)元素屬性分布比較廣離散度較大的簇，改進(jìn)后的k-means算法在一定程度上減少了不合理的分類；對(duì)于簇離散度和屬性分布差不多或者是簇之間距離較大的數(shù)據(jù)集，改進(jìn)后的算法聚類效果和傳統(tǒng)k-means一樣，但是速度慢一些；對(duì)于簇之間距離過小的數(shù)據(jù)集，改進(jìn)算法比之傳統(tǒng)k-means算法略差。

參考文獻(xiàn)：

[1] Berkhin P. A survey of clustering data mining techniques， in Grouping multidimensional data，2006：25-71.

[2] Hamerly G， Elkan C， Learning the k in A> means. Advances in neural information processing systems， 2004（16）：281.

[3] Hand D J， Mannila H， Smyth P.Principles of data mining. MIT press，2001.

[4] Jain A K， Mao J， Mohiuddin K. Artificial neural networks： A tutorial. Computer，1996（3）：31-44.

[5] Soman K， Diwakar S， Ajay V. Data Mining： Theory and Practice [WITH CD]. 2006： PHI Learning Pvt. Ltd.

[6] 王千. K-means 聚類算法研究綜述[J]. 電子設(shè)計(jì)工程，2012，20（7）：21-24.

[7] 張琳.一種基于密度的 K-means 算法研究[J].計(jì)算機(jī)應(yīng)用研究，2011，28（11）：4071-4073.

[8] 張玉芳，毛嘉莉， 熊忠陽. 一種改進(jìn)的 K—means算法[J]. 計(jì)算機(jī)應(yīng)用， 2003，23（8）：31-33.

[9] 周世兵，徐振源， 唐旭清. K-means 算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)應(yīng)用，2010，30（8）：1995-1998.

[10] 朱顥東， 鐘勇， 趙向輝. 一種優(yōu)化初始中心點(diǎn)的K-Means文本聚類算法[J]. 鄭州大學(xué)學(xué)報(bào)： 理學(xué)版，2009（2）.