基于PAM和簇閾值的改進(jìn)K-Means聚類算法

卜旭松，劉立波，石　磊

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

基于PAM和簇閾值的改進(jìn)K-Means聚類算法

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

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

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

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

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)志碼：碼：A

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

收稿日期：2015-03-03

作者簡(jiǎn)介：卜旭松(1988-)，男，山東煙臺(tái)人，寧夏大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院碩士研究生。

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-)，女，寧夏銀川人，寧夏大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院教授，博士后。

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

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

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

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

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

1.1　相關(guān)定義

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

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

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

1.2　PAM算法

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

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

步驟：

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

(2)repeat；

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

(4) 隨機(jī)地選擇一個(gè)非代表對(duì)象Orandom；

(5) 計(jì)算用Orandom代表對(duì)象的總代價(jià)S；

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

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

1.3　簇閾值設(shè)置

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

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

2　改進(jìn)的K-Means算法

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

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

輸出：k個(gè)簇的集合；孤立點(diǎn)集I。

步驟：

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

(3)repeat；

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

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

改進(jìn)的K-Means算法流程如圖1所示。

圖1　改進(jìn)K-Means算法流程圖

3　實(shí)驗(yàn)仿真及分析

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

表1　實(shí)驗(yàn)數(shù)據(jù)集屬性

3.1　聚類中心選取驗(yàn)證

iris數(shù)據(jù)集實(shí)際聚類數(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}。本文改進(jìn)的算法獲取的聚類中心與iris數(shù)據(jù)實(shí)際聚類中心的誤差平方和為0.049 1，說(shuō)明提出的算法獲取的聚類中心與iris數(shù)據(jù)集真實(shí)聚類中心非常接近，能有效代表數(shù)據(jù)的實(shí)際分布。因此，利用本文的算法獲取的聚類中心作為K-Means算法初始聚類中心是可行且較優(yōu)的。

3.2　準(zhǔn)確率和效率比較

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

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

4　結(jié)束語(yǔ)

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

[參考文獻(xiàn)]

[1]趙衛(wèi)中,馬慧芳,李志清,等.一種結(jié)合主動(dòng)學(xué)習(xí)的半監(jiān)督文檔聚類算法[J].軟件學(xué)報(bào)，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]侯曉晶,王會(huì)青.基于最近鄰距離差的改進(jìn)孤立點(diǎn)檢測(cè)算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(4):1265-1269

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

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

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

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

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

[14]畢方明,王為奎,陳龍.基于空間密度的群以噪聲發(fā)現(xiàn)聚類算法研究[J].南京大學(xué)學(xué)報(bào)：自然科學(xué)版，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

(責(zé)任編輯：張凱兵)