鄭帥　趙曉東

摘要：聚類算法在自然科學(xué)和和社會科學(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算法；離散度

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

1 概述

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

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

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

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

2.1 K-means基本思想

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

2.2 K-means算法的基本過程

第一步：在X中任意選擇k個對象作為初始的簇中心；

第二步：REPEAT；

第三步：計算每個對象到每個簇中心點的距離，將每個對象分配給離得最近的簇（即最相似的簇）；

第四步：根據(jù)新的聚類計算每個簇新的中心點；

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

3 改進的K-means算法

3.1 改進的出發(fā)點

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

3.2 對象分配以及算法的改進

改進后的距離公式如下所示：

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

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

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

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

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

第二步：REPEAT；

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

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

第五步：直到元素點的類別不在變化。

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

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

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

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

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

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

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

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

5 結(jié)論

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

參考文獻：

[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è)計工程，2012，20（7）：21-24.

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

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

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

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