基于PAM和簇閾值的改進K-Means聚類算法

卜旭松，劉立波，石　磊

(1.寧夏大學 數(shù)學與計算機學院，寧夏 銀川 750021;2. 湖北工程學院 現(xiàn)代教育技術(shù)中心，湖北 孝感 432000)

基于PAM和簇閾值的改進K-Means聚類算法

卜旭松1，劉立波1，石磊2

(1.寧夏大學 數(shù)學與計算機學院，寧夏 銀川 750021;2. 湖北工程學院 現(xiàn)代教育技術(shù)中心，湖北 孝感 432000)

摘要:為了彌補K-Means算法對孤立點數(shù)據(jù)敏感的缺陷，提高K-Means算法對包含孤立點數(shù)據(jù)集的聚類效果，在深入研究K-Means算法的基礎上，提出了基于PAM和簇閾值的改進K-Means聚類算法。該算法首先對待聚類數(shù)據(jù)進行抽樣，然后利用PAM算法獲取樣本數(shù)據(jù)的聚類中心，以樣本數(shù)據(jù)的聚類中心作為K-Means算法的初始聚類中心。在聚類迭代過程中動態(tài)計算各簇閾值，利用簇閾值準確地過濾孤立點數(shù)據(jù)。實驗結(jié)果表明，本文提出的算法不僅聚類時間短，而且具有較高的聚類準確率。

關(guān)鍵詞：采樣；K-Means聚類；聚類閾值；孤立點

中圖分類號：TP18

文獻標志碼：碼：A

文章編號：號：2095-4824(2015)03-0036-04

收稿日期：2015-03-03

作者簡介：卜旭松(1988-)，男，山東煙臺人，寧夏大學數(shù)學與計算機學院碩士研究生。

Abstract：In order to overcome the weakness of K-Means algorithm which is sensitive to outliers, and to improve the quality of K-Means clustering algorithm, the paper makes an in-depth study on the traditional K-Means algorithm and proposes an improved clustering algorithm based on the PAM algorithm and the cluster threshold. The proposed method first samples the clustering data and then employs the PAM algorithm to obtain the clustering center of the sample data as the initial center of K-Means algorithm. By calculating the threshold for each cluster dynamically in the iterative process of clustering, the outliers can be excluded from the dataset. Experimental results indicate that the proposed algorithm have been shown lower computational cost and higher clustering accuracy.

劉立波(1974-)，女，寧夏銀川人，寧夏大學數(shù)學與計算機學院教授，博士后。

石磊(1986-)，男，內(nèi)蒙古興安盟人，湖北工程學院現(xiàn)代教育中心實驗師，碩士。

聚類是一種無監(jiān)督的分類方法[1]。作為一種有效的數(shù)據(jù)挖掘技術(shù)，聚類分析可以發(fā)現(xiàn)數(shù)據(jù)的分布，觀察每個簇的特征，便于將進一步分析集中在某個特定的集合上。目前，聚類分析已經(jīng)廣泛地應用于商務智能、圖像模式識別、Web搜索[2]、市場營銷、生物學[3]和安全等領(lǐng)域。

K-Means算法是一種基于劃分的聚類方法，算法以簇內(nèi)點的均值作為簇的聚類中心[4-7]。孤立點是顯著偏離數(shù)據(jù)集中其他數(shù)據(jù)的點，不屬于任何簇[8]。孤立點的存在，嚴重影響了簇均值，致使簇的聚類中心顯著偏離數(shù)據(jù)的實際中心，影響了其他對象到簇的分配，導致算法準確率降低。基于密度[9-10]、區(qū)域劃分[11]等初始聚類中心的優(yōu)化算法盡管能為算法提供優(yōu)質(zhì)的初始聚類中心，但無法處理后繼迭代過程中孤立點對簇中心重新計算引起的誤差，最終影響聚類的準確性。文獻[12]采用鄰域密度方法對數(shù)據(jù)進行預處理，把指定鄰域內(nèi)包含其他對象數(shù)量少于Minpts的對象作為孤立點過濾掉。由于處理后的數(shù)據(jù)集不含孤立點數(shù)據(jù)，因此算法聚類準確率較高，但單獨處理孤立點會增加算法的時間開銷，嚴重影響算法整體執(zhí)行效率。

本文從初始聚類中心選取和聚類規(guī)則兩方面對傳統(tǒng)K-Means算法進行改進。利用PAM算法獲取樣本數(shù)據(jù)的聚類中心作為K-Means算法初始聚類中心，利用閾值系數(shù)與簇邊距乘積作為簇閾值。在聚類過程中同步過濾孤立點數(shù)據(jù)，避免單獨處理孤立點數(shù)據(jù)增加額外的時間開銷，使算法具有較高準確率的同時保持較高的執(zhí)行效率。

1　相關(guān)理論及定義

1.1　相關(guān)定義

離簇Ci距離最近的簇Cj的質(zhì)心。

定義3對于一個簇u，如果樣本數(shù)據(jù)集s大小滿足：

本文假設各簇數(shù)據(jù)量為uavg=N/K，N為數(shù)據(jù)集數(shù)據(jù)總量，則樣本數(shù)據(jù)量Savg為：

1.2　PAM算法

PAM算法是一種基于代表對象的技術(shù)，算法不采用簇均值作為聚類中心，而是選擇簇中實際對象作為聚類中心，因而不易受孤立點影響，對小規(guī)模數(shù)據(jù)集合非常有效，但缺點是算法時間復雜度高，當數(shù)據(jù)量較大時算法執(zhí)行效率不高。研究表明，在樣本數(shù)據(jù)合適、取樣均勻的情況下，抽樣數(shù)據(jù)可以較為真實地反映總體數(shù)據(jù)集的分布狀況[14]。本文利用PAM算法對樣本數(shù)據(jù)進行聚類，獲取樣本數(shù)據(jù)的聚類中心作為K-Means算法的初始聚類中心，以樣本數(shù)據(jù)的簇邊距作為K-Means算法初次迭代的簇閾值計算參數(shù)。PAM算法描述如下：

輸入：結(jié)果簇的個數(shù)k；D：包含n個對象的數(shù)據(jù)集合。

步驟：

(1) 從D中隨機選取k個對象作為初始的代表對象或種子；

(2)repeat；

(3) 將每個剩余的對象分配到最近的代表對象所代表的簇；

(4) 隨機地選擇一個非代表對象Orandom；

(5) 計算用Orandom代表對象的總代價S；

(6)ifS<0，then用Orandom替換Oj，形成k個新的代表對象集合；

(7) until聚類中心和簇邊距不再發(fā)生變化。

1.3　簇閾值設置

傳統(tǒng)的K-Means算法無法處理孤立點，對包含孤立點的數(shù)據(jù)集聚類準確率低。本文對K-Means算法的聚類準則進行改進，通過設置閾值方式過濾孤立點，算法以閾值系數(shù)ε和各簇的簇邊距乘積作為各簇簇閾值。與全局閾值相比，局部簇閾值更能準確地反映各簇的區(qū)域范圍，具有過濾孤立點數(shù)據(jù)的能力。由于K-Means算法初次迭代過程中無簇邊距信息，利用PAM算法獲取樣本數(shù)據(jù)的簇邊距與閾值系數(shù)ε乘積作為簇閾值，在后繼迭代過程中使用上次迭代分配到該簇的對象重新計算簇邊距并更新簇閾值，使簇閾值更加準確。使用簇閾值過濾孤立點的步驟如下:

(3) 若不滿足步驟(2)，則將點X劃分到孤立點集中。

2　改進的K-Means算法

算法基本思想如下：依據(jù)定義3進行抽樣，利用PAM算法獲取樣本數(shù)據(jù)的k個聚類中心。對于數(shù)據(jù)集中每個對象，計算其到各個簇中心的歐式距離dx，若該對象與某簇最相似且dx不大于該簇的簇閾值，則將該對象劃分到該簇，否則將該數(shù)據(jù)對象劃分到孤立點數(shù)據(jù)集。重新計算簇均值和簇閾值，重新分配所有對象，直到分配穩(wěn)定。改進的K-Means聚類算法描述如下：

輸入：ε閾值系數(shù)；聚類簇個數(shù)k；包含N個對象的數(shù)據(jù)集D。

輸出：k個簇的集合；孤立點集I。

步驟：

(1) 依據(jù)定義3所述，從數(shù)據(jù)集D中抽取樣本數(shù)據(jù)集S；

(3)repeat；

(4) 清空孤立點數(shù)據(jù)集I中的數(shù)據(jù)；

(7) until簇中心不再發(fā)生變化。

改進的K-Means算法流程如圖1所示。

圖1　改進K-Means算法流程圖

3　實驗仿真及分析

實驗環(huán)境為 Intel(R) Core(TM)i3-3110M CPU @ 2.40GHz，內(nèi)存 4 GB，Windows 7系統(tǒng)，實驗工具為Matlab 7。實驗數(shù)據(jù)為UCI數(shù)據(jù)庫中iris和waveform數(shù)據(jù)集，各數(shù)據(jù)集屬性見表1。為驗證算法處理孤立點的效果，在兩個數(shù)據(jù)集中添加孤立點數(shù)據(jù)，使孤立點數(shù)據(jù)比例達到整個數(shù)據(jù)集的5%。

表1　實驗數(shù)據(jù)集屬性

3.1　聚類中心選取驗證

iris數(shù)據(jù)集實際聚類數(shù)據(jù)中心分別為setosa{5.00,3.41,1.46,0.24}、versicolor{5.93,2.77,4.26,1.32}、virginica{6.58,2.97,5.55,2.02}。依照定義3，利用PAM算法獲取的樣本數(shù)據(jù)的聚類中心別為setosa{5.0,3.4,1.5,0.2}、versicolor{5.9,3.0,4.2,1.5}、virginica{6.5,3.0,5.5,1.8}。本文改進的算法獲取的聚類中心與iris數(shù)據(jù)實際聚類中心的誤差平方和為0.049 1，說明提出的算法獲取的聚類中心與iris數(shù)據(jù)集真實聚類中心非常接近，能有效代表數(shù)據(jù)的實際分布。因此，利用本文的算法獲取的聚類中心作為K-Means算法初始聚類中心是可行且較優(yōu)的。

3.2　準確率和效率比較

表2是本文提出的算法、傳統(tǒng)K-Means算法、文獻[11]和文獻[12]在iris和waveform數(shù)據(jù)集上聚類準確率比較結(jié)果，其中本文提出的算法的參數(shù)設置如下：簇閾值系數(shù) =1.5，聚類數(shù)k=3。由于本文提出的算法和文獻[12]的方法不僅對初始聚類中心進行優(yōu)化，而且對孤立點數(shù)據(jù)進行了處理，聚類準確率明顯高于傳統(tǒng)K-Means算法和僅對初始聚類中心進行優(yōu)化的文獻[11]的結(jié)果。但從圖2可以看出，文獻[12]需要對孤立點數(shù)據(jù)進行預處理，因此隨著實驗數(shù)據(jù)量的不斷增加，算法執(zhí)行所需要的時間增長趨勢明顯，呈冪指數(shù)增長。相比而言，本文提出的算法在聚類過程中同步處理孤立點數(shù)據(jù)，算法執(zhí)行時間增長速度平穩(wěn)，呈線性增長趨勢。綜上可知，本文算法在保持高準確率的同時能顯著提高算法的執(zhí)行效率。

圖2　算法執(zhí)行時間比較

4　結(jié)束語

數(shù)據(jù)集中存在的孤立點數(shù)據(jù)嚴重影響了K-Means算法聚類準確率。為了消除孤立點對聚類質(zhì)量的影響，提高K-Means算法聚類效果，本文提出了一種基于PAM和簇閾值的改進K-Means算法。該算法利用PAM獲取樣本數(shù)據(jù)聚類中心作為K-Means算法的初始聚類中心，利用簇閾值方式過濾孤立點數(shù)據(jù)，消除了孤立點對聚類準確率的影響，具有較高的聚類準確率和執(zhí)行效率。

[參考文獻]

[1]趙衛(wèi)中,馬慧芳,李志清,等.一種結(jié)合主動學習的半監(jiān)督文檔聚類算法[J].軟件學報，2012,23(6):1486-1499.

[2]Lingras P,West C.Interval set clustering of web users with rough K-Means[J].Journals of Intelligent Information Systems,2004,23(1):5-16.

[3]Redmond S J,Heneghan C.A method for initialising the K-Means clustering algorithm using kd-trees[J].Pattern Recognition Letters,2007,28(8):965-973.

[4]Li M J,Ng M K, Cheung Y M.Agglomerative fuzzy K-Means clustering algorithm with selection of number of clusters[J].IEEE Transactions on Knowledge and Data Engineering,2008,20(11):1519-1534．

[5]Zhang Y,Zhou H,Qin S.Decentralized fault diagnosis of large-scale processes using multiblock kernel principal component analysis[J].Acta Automatic Sinica,2010,36(4):593-597.

[6]Likas A,Vlassis M,Verbeek J.The global K-Means clustering algorithm[J].Pattern Recognition,2003,36 (2):451-461.

[7]Seinley D,Brusco M J.Initializing K-Means batch clustering:a critical evaluation of several techniques[J].Journal of Classification,2007,24(1):99-121.

[8]侯曉晶,王會青.基于最近鄰距離差的改進孤立點檢測算法[J].計算機工程與設計,2013,34(4):1265-1269

[9]鄭丹,王潛平.K-Means初始聚類中心的選擇算法[J].計算機應用,2012,32 (8):2186-2188,2192.

[10]周董,劉鵬.VDBSCAN:變密度聚類算法[J].計算機工程與應用,2009,45(11):137-153.

[11]蘇錦旗,薛惠鋒,詹海亮.基于劃分的K-均值初始聚類中心優(yōu)化算法[J].微電子學與計算機,2009,26(1):8-11.

[12]王賽芳,戴芳.基于初始聚類中心優(yōu)化的K-均值算法[J].計算機工程與科學,2010,44(23):166-168.

[13]雷小鋒,謝昆青,林帆,等.一種基于K-Means局部最優(yōu)性的高效聚類算法[J].軟件學報,2008,19(7):1683-1692.

[14]畢方明,王為奎,陳龍.基于空間密度的群以噪聲發(fā)現(xiàn)聚類算法研究[J].南京大學學報：自然科學版，2012,48(4):491-498.

An Improved K-Means Algorithm Based on PAM Algorithm and Cluster Threshold

Bu Xusong1,Liu Libo1, Shi Lei2

(1.SchoolofMathematicsandComputer,NingxiaUniversity，Yinchuan,Ningxia750021,China;

2.TechniqueCenterofModernEducation,HubeiEngineeringUniversity,Xiaogan,Hubei432000,China)

Key Words：sampling;K-Means cluster; cluster threshold; outlier

(責任編輯：張凱兵)