摘要：聚類算法在自然科學和和社會科學中都有很普遍的應用，而K-means算法是聚類算法中經典的劃分方法之一。但如果數據集內相鄰的簇之間離散度相差較大，或者是屬性分布區間相差較大，則算法的聚類效果十分有限。本文基于離散度的思想，采用新的加權距離函數代替了傳統算法的歐氏距離，在一定程度上優化了k-means算法的聚類結果。

關鍵詞：聚類；k-means算法；離散度

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

1 概述

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

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

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

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

2.1 K-means基本思想

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

2.2 K-means算法的基本過程

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

第二步：REPEAT；

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

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

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

3 改進的K-means算法

3.1 改進的出發點

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

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

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

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

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

輸入：含有N個對象的數據集以及簇的個數k；

輸出：在k個中心點穩定之后的k個簇；

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

第二步：REPEAT；

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

第四步：根據新的聚類計算每個簇新的中心點并計算此簇的標準差；

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

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

4 試驗和結果分析

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

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

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

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

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

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

5 結論

通過改進迭代過程中的分配函數，將到各個簇中心的歐式距離調整為到簇中心的距離加上到簇內離其最近元素點的距離之和，并將[1σ2]作為懲罰因子。在簇離散度不均勻且相鄰簇大小相差較大的數據集上，元素點將更有可能分配給簇內元素屬性分布比較廣離散度較大的簇，改進后的k-means算法在一定程度上減少了不合理的分類；對于簇離散度和屬性分布差不多或者是簇之間距離較大的數據集，改進后的算法聚類效果和傳統k-means一樣，但是速度慢一些；對于簇之間距離過小的數據集，改進算法比之傳統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]. 電子設計工程，2012，20(7)：21-24.

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

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

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

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

總結

以上是生活随笔為你收集整理的kmeans改进 matlab,基于距离函数的改进k―means 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。