一種改進的K-means聚類算法與孤立點檢測研究

摘要:傳統(tǒng)的K-means算法對于孤立點數(shù)據(jù)是非常敏感的，少量的該類數(shù)據(jù)就能對聚類結(jié)果產(chǎn)生很大影響。該文提出了一種改進的K-means算法來消弱這種敏感性。算法基于孤立點檢測LOF算法中計算K距離的思想，將大于K距離的數(shù)據(jù)點作為偽聚類中心參與聚類劃分，通過對聚類結(jié)果的評價來判斷該數(shù)據(jù)點是否為孤立點。若為孤立點則去掉該點，進而來提高聚類質(zhì)量。

關鍵詞:K-means;K距離;孤立點;偽聚類中心

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2010)21-6085-02

A Modified K-means Clustering Algorithm and Research on Outlier Detection

YING Min-jie， DONG Chun-zhao

(Southwest Jiaotong University， Chengdu 610031， China)

Abstract: lassical K-means algorithm is very sensitive to outlier data， small amounts of such data can have a great impact on the clustering results. In this paper， a modified K-means algorithm is put forward to weaken this sensitivity. This algorithm bases on the idea of LOF outlier detection algorithm， which regards the data that are greater than K-distance as a pseudo-center. Through the evaluation of clustering results to determine whether the data is an outlier data point. If so， the outlier data point is removed in order to improve the quality of clustering.

Key words: k-means; k-distance; outlier data point; pseudo-center

聚類是把一組個體按照相似性歸成若干類別，使得屬于同一類別個體之間的距離盡可能小，而不同類別個體間的距離盡可能的大。聚類作為數(shù)據(jù)挖掘中的一種重要技術，在模式識別、數(shù)據(jù)分析以及市場研究等很多領域都發(fā)揮著重要作用。目前主要的聚類算法[1-2]有基于劃分方法的K-means算法和K-中心算法，基于密度的DBSCAN和OPTICS方法，基于網(wǎng)格的CLIQUE和 STING方法等。本文重點研究了K-means算法，并針對該算法的孤立點敏感性提出了一種改進算法。改進后的K-means算法能很好的削弱孤立點的影響，大大提高了聚類質(zhì)量。

1 K-means算法研究

1.1 K-means算法[1，6]

K-means是基于劃分方法的一種核心算法，劃分的思路是以k為參數(shù)，把n個對象分為k個簇，并使簇內(nèi)具有較高的相似度，簇間具有較低相似度，相似度根據(jù)一個簇中對象的平均值來計算。

K-means算法的處理流程如下:

(1) 隨機選擇k個對象，每個對象都代表一個初始簇中心;

(2) 對剩余的對象，計算其與各個簇中心的距離，并將它賦給距離最近的簇;

(3) 重新計算每個簇的平均值，并將該平均值作為新的簇中心;

(4) 不斷重復第(2)、(3)步，直到準則函數(shù)收斂或聚類中心不再發(fā)生變化，準則函數(shù)通常采用平方誤差準則。

1.2 K-means算法的優(yōu)缺點

當結(jié)果簇是密集的，而且簇之間的區(qū)分明顯時，它的效果較好。對于大數(shù)據(jù)集處理，效率較高。但K-means算法不適合發(fā)現(xiàn)非凸面形狀的簇，并且它對孤立點數(shù)據(jù)敏感，少量的孤立點數(shù)據(jù)對聚類效果產(chǎn)生很大影響。

2 LOF局部孤立因子算法[3]之K距離[4]

本論文中，為區(qū)分K-means的初始簇中心個數(shù)k，將LOF算法的K距離稱為K'距離。

K'距離，又稱局部最大距離，定義為:當對象p至少有k'個鄰居時，對象p與這k'個鄰居的最大距離。任何與對象p的距離大于p的k'距離的對象不是 p的鄰居。即若對象o為p的鄰居，則滿足以下條件[5]:

1) 至少存在k'個對象o'，使d(p， o')≤d(p，o);

2) 至多存在k'-1個對象o'，使d(p， o')

如果p的k'距離值很大，就意味著p周圍的區(qū)域稀疏，相反，如果 k'距離值很小就表明p周圍的區(qū)域稠密。

3 改進的K-means算法

針對傳統(tǒng)K-means算法對孤立點數(shù)據(jù)的敏感性，如何消除孤立點是提高聚類質(zhì)量的一個突破點，通常孤立點檢測算法與聚類算法是分離的，兩者必須先后進行，影響了效率及聚類結(jié)果。

筆者針對這一缺點，綜合了K-means算法和LOF算法中K距離的思想，提出了一種綜合聚類和孤立點檢測的改進的K-means方法。該算法能有效消弱孤立點對聚類結(jié)果的影響。

3.1 改進的K-means算法原理

改進的K-means算法是在傳統(tǒng)K-means算法的基礎上，將所有數(shù)據(jù)點分配給距離它最近的簇中心后，計算每個聚類中心的K'距離，如果某數(shù)據(jù)點與離它最近的簇中心的距離大于該簇K'距離，則將該數(shù)據(jù)點看做偽簇中心，與其他簇中心一起進行下一輪的分配。如果該偽中心在經(jīng)一次聚類后，周圍無鄰居或只有幾個鄰居，則可將該偽中心看做孤立點去掉。如果該偽中心周圍有較多鄰居時，說明該偽中心不是孤立點，此時應增大K'，繼續(xù)下一輪聚類，直到準則函數(shù)收斂。

算法描述如下:

輸入:數(shù)據(jù)集，初始簇中心個數(shù)k，最近鄰居數(shù)K';

輸出:聚類結(jié)果及孤立點

(1) 隨機選擇k個對象，作為初始簇中心，并設此時偽簇中心個數(shù)為0;

(2) 對剩余的對象，計算其與各個簇中心(包括偽簇中心)的距離，并將它分配給距離最近的簇;

(3) 計算每個簇中心的K'距離;

(4) 將該簇中的對象與中心的距離與K'距離相比，如果大于，則將該對象作為偽簇中心;否則，認為該對象是屬于這個簇的，即是該簇中心的鄰居。

(5) 如果該簇中心的K'距離非常大，則認為該簇中心周圍區(qū)域稀疏，該簇中心為孤立點，可去掉，不參與下次分配;

(6) 重新計算每個簇的平均值，并將該平均值作為新的簇中心;

(7) 不斷重復第(2)、(3)、(4)、(5)、(6)步，直到準則函數(shù)收斂或聚類中心不再發(fā)生變化。

3.2 實驗結(jié)果

為檢驗改進算法的有效性，筆者采用java語言編程實現(xiàn)了該算法，并對多組數(shù)據(jù)進行測試。圖1是其中一組典型數(shù)據(jù)的實驗結(jié)果，其中紅色代表簇中心，以該中心為圓點，該簇的K'距離為半徑做圓，本例中K'為10。o點是偽簇中心，K1，K2，K3分別是兩個簇中心和偽簇中心o的K'距離，有圖可見，偽簇中心o周圍區(qū)域比較稀疏，它的K'距離較大，可以判斷o點是孤立點。

圖2、圖3分別是K-means算法與改進的k-means算法的聚類結(jié)果圖。由圖2可以看出K-means算法對孤立點非常敏感，聚類效果不夠精確。圖3是改進的K-means算法聚類結(jié)果，該算法忽略了孤立點，使聚類效果較好。

3.3 算法評價

傳統(tǒng)的K-means算法極易受孤立點的影響，造成聚類結(jié)果不盡人意。本文提出的改進的K-means算法能極大的消弱孤立點的干擾，提高聚類質(zhì)量。但也存在不足之處，K'距離計算依賴最近鄰居數(shù)K'，不同K'值會造成聚類結(jié)果有所浮動。

4 結(jié)束語

本文結(jié)合K-means算法與LOF孤立點檢測算法中K距離思想，提出了一種改進的K-means算法，該算法將孤立點檢測與聚類結(jié)合在一起，有效的減弱了傳統(tǒng)K-means算法的孤立點敏感性，提高了聚類效果。

參考文獻:

[1] 安淑芝.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘[M].北京:清華大學出版社，2005.

[2] 韓家煒，M.Kamber.數(shù)據(jù)挖掘:概念與技術[M].北京:機械工業(yè)出版社，200l.

[3] Breuning M.M，Kriegel H.-P，Ng R.T，and Sander J.\"LOF:Identifying density-based local outliers\".In proceeding of ACM SIGMOD International Conference on Management of Data ，Dalles，Texas，USA，2000.

[4] 賈晨科，邱保志.基于K一距離的孤立點和聚類算法研究[D].鄭州大學碩士學位論文，2006.

[5] 劉大任，孫煥良，牛志成，朱葉麗.一種新的基于密度 的聚類與孤立點檢測算法[J].建筑大學學報，2006.

[6] Aristidis Likas，Nikos Vlassis，Jakob J.Verbeek.The global k-means clustering algorithm，，Pattern Recognition，2003，451-461.

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文