張 銳，王義武，朱嘯龍，殷 俊，韓 晨，楊余旺

(南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210000)

0 引 言

K-means是一種經(jīng)典的基于劃分的聚類分析方法，具有簡(jiǎn)單、高效的特點(diǎn)，在眾多領(lǐng)域得到了廣泛應(yīng)用。通過計(jì)算每個(gè)數(shù)據(jù)對(duì)象與k個(gè)聚類中心的距離，將數(shù)據(jù)對(duì)象劃分到距離它最近的一個(gè)類，然后更新每個(gè)類的中心，這個(gè)過程反復(fù)迭代直到收斂，輸出聚類結(jié)果。傳統(tǒng)的K-means算法中，k個(gè)初始聚類中心是在數(shù)據(jù)對(duì)象集中隨機(jī)選取的，因此迭代過程從不同的初始聚類中心出發(fā)，得到的聚類結(jié)果也不同，并且聚類的迭代過程容易產(chǎn)生局部最優(yōu)解[1]。同時(shí)，這種聚類結(jié)果波動(dòng)在工程應(yīng)用中也會(huì)帶來許多技術(shù)問題[2]。

為了選擇優(yōu)化的初始聚類中心，已有研究主要從密度優(yōu)化和距離估計(jì)兩方面對(duì)K-means算法加以改進(jìn)。文獻(xiàn)[3]是一種典型的密度優(yōu)化聚類中心選擇算法，通過密度函數(shù)法求得樣本數(shù)據(jù)空間的多個(gè)聚類中心，結(jié)合類的合并運(yùn)算，避免局部最優(yōu)問題。類似的，文獻(xiàn)[4]提出按照數(shù)據(jù)集的數(shù)學(xué)分布動(dòng)態(tài)地尋找k個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心。而進(jìn)一步的理論和實(shí)驗(yàn)表明，在密度優(yōu)化方法的基礎(chǔ)上，采用距離估計(jì)(如最大最小距離法)可提升算法的收斂速度、準(zhǔn)確率[5-6]。

文中引入了不加權(quán)算術(shù)平均組對(duì)法(UPGMA)[7]和最大最小距離算法，通過這兩種算法的優(yōu)化和篩選，選取優(yōu)化的數(shù)據(jù)中心，為K-means算法提供準(zhǔn)確反映數(shù)據(jù)分布的聚類中心，解決聚類中心高度依賴的問題。

1 優(yōu)化候選中心K-means算法

在理想的聚類算法中,各聚類中心應(yīng)該分散地取自密集區(qū)域,根據(jù)這一思想,提出優(yōu)化候選中心(OICC)K-means算法。該算法可以將改進(jìn)的UPGMA算法和最大最小距離算法相融合，充分發(fā)揮各自的優(yōu)點(diǎn)，得到經(jīng)過優(yōu)化的可以反映密集區(qū)數(shù)據(jù)分布的初始候選中心。如圖1所示，這些點(diǎn)可以作為密集區(qū)域的代表，再把這些聚類中心應(yīng)用到K-means算法中,在整體上提高聚類效果。

圖1 數(shù)據(jù)與候選中心分布

1.1 基本思想

定義1：數(shù)據(jù)點(diǎn)Xi與Xj之間的距離定義為：

(1)

其中，Xi、Xj表示數(shù)據(jù)集中m維的數(shù)據(jù)對(duì)象。

定義2：聚類C中心點(diǎn)的坐標(biāo)為C=(C1,C2,…,Cj),第j維的數(shù)據(jù)定義為：

(2)

其中，n為子類包含的數(shù)據(jù)個(gè)數(shù)；Xi為子類內(nèi)的數(shù)據(jù)。

最大最小距離[8]算法其基本思想是使作為聚類中心的候選點(diǎn)盡可能相隔較遠(yuǎn),得到經(jīng)過優(yōu)化的候選中心，更好地刻畫數(shù)據(jù)集的整體分布。避免了在選取初始候選點(diǎn)時(shí)選點(diǎn)存在過近的情況，盡可能地在所有數(shù)據(jù)聚集區(qū)都能選到候選點(diǎn),有效避免了初始中心的過于集中,很大程度上提高了聚類算法的效果[9-10]。但在這個(gè)過程中可能把噪聲數(shù)據(jù)、邊緣數(shù)據(jù)也加入到初始聚類中心內(nèi)。同時(shí)，該算法需要兩次掃描數(shù)據(jù)庫,第一次是找到每個(gè)類到已有聚類中心的最短距離,第二次是掃描數(shù)據(jù)庫得到最大的最小距離即Max(Min(Dt))。算法完成時(shí),時(shí)間復(fù)雜度為O(nk)(k為聚類中心的個(gè)數(shù),n為數(shù)據(jù)對(duì)象的個(gè)數(shù))?？梢?當(dāng)數(shù)據(jù)規(guī)模很大時(shí),計(jì)算量過大。K-means算法是建立在數(shù)據(jù)間距離之上的，即它的類劃分標(biāo)準(zhǔn)為數(shù)據(jù)間的相互距離，數(shù)據(jù)距離近說明數(shù)據(jù)間相似度大，就可把它們劃分到同一個(gè)類中[11-12]。

定義3：聚類和數(shù)據(jù)集中剩余數(shù)據(jù)的最大最小距離定義為：

Dmax=Max(d)

(3)

其中，d為每個(gè)聚類與數(shù)據(jù)集中剩余各數(shù)據(jù)距離的最小值組成的集合。

定義4：d為每個(gè)聚類與數(shù)據(jù)集中剩余各數(shù)據(jù)距離的最小值，即

(4)

其中，Xi為聚類中心；Xj為數(shù)據(jù)集中剩余的數(shù)據(jù)；m數(shù)據(jù)的維度。

定義5：判斷是否將初始候選中心選為優(yōu)化后的候選中心。

Max(Min(Dt))>θ‖v1-v2‖

(5)

其中，v1、v2為最先成為優(yōu)化后的候選中心的點(diǎn)；θ為參數(shù)，常取0.5。

定義6：K-means算法進(jìn)行聚類的準(zhǔn)則函數(shù)為誤差平方和準(zhǔn)則函數(shù)。

(6)

其中，Mi為類Ci中所有數(shù)據(jù)的均值；p為類Ci中的每個(gè)數(shù)據(jù)；Jc為樣本和聚類中心的函數(shù)。在已知樣本集時(shí),Jc的值取決于Mi。Jc描述了n個(gè)樣本數(shù)據(jù)得出k個(gè)分類產(chǎn)生的總的誤差平方和?？梢钥闯?Jc越大,表明誤差越大,效果越差。所以應(yīng)力求Jc最小,從而得出最好的聚類效果。

初始隨機(jī)給定k個(gè)簇中心,將數(shù)據(jù)劃分到距自己最近的簇中，然后重新計(jì)算每個(gè)簇的中心，一直迭代，直到前后兩次得出的簇的中心不再變化或者滿足一定要求為止。每次迭代后,需要檢驗(yàn)數(shù)據(jù)分類是否正確,如果錯(cuò)誤,就要繼續(xù)劃分聚類,重新計(jì)算簇中心,進(jìn)行下一次迭代。但K-means算法結(jié)束時(shí)找到的解常常為局部最優(yōu)而非全局最優(yōu)，如圖2所示。

圖中，p1、p2、p3的初值不同,目標(biāo)函數(shù)分別順著誤差平方和準(zhǔn)則函數(shù)逐漸減小的方向搜索,直到找到各自對(duì)應(yīng)的最小值A(chǔ)、B、C。其中,A、B為局部極小值,C為全局最小值,但算法結(jié)束時(shí)經(jīng)常只能收斂局部極小值[13-14]。

圖2 局部極小值和全局極小值

1.2 改進(jìn)UPGMA算法

在UPGMA改進(jìn)算法中，將每個(gè)數(shù)據(jù)都看作一個(gè)類，獲得每個(gè)類之間的距離,將相互間距離最小的數(shù)據(jù)加入到同一個(gè)類中形成一個(gè)新類,重復(fù)此步驟,當(dāng)滿足算法停止的條件或者不再產(chǎn)生新類時(shí),算法結(jié)束。改進(jìn)的UPGMA運(yùn)算過程如下所述：

算法1：改進(jìn)UPGMA算法。

Input:需要進(jìn)行聚類的數(shù)據(jù);聚類內(nèi)數(shù)據(jù)數(shù)目占數(shù)據(jù)總數(shù)的百分比m%;序列Q的前p%；

Output:初始候選中心。

Step1:把所有數(shù)據(jù)都看成一個(gè)獨(dú)立的類。

Step2:計(jì)算出任意兩個(gè)類的距離，合并相距最近的兩個(gè)類，同時(shí)判斷剩下數(shù)據(jù)的總數(shù)是否大于等于總數(shù)的m%,若否，則轉(zhuǎn)Step4。

Step3:迭代次數(shù)i=0

Step4:do

Step5:t=t+1;

Step6:forj=i+1,…,maxcluster do

當(dāng)子類i和子類j內(nèi)部的數(shù)據(jù)個(gè)數(shù)少于等于總數(shù)的m%時(shí),計(jì)算兩個(gè)類之間的距離,并加入到距離矩陣中。

Step7:endfor

Step8:在距離矩陣中找到距離最小的對(duì)應(yīng)的兩個(gè)類，將它們合并為新類,同時(shí)加入到序列Q的結(jié)尾,轉(zhuǎn)至Step2。

Step9:whilet>maxcluster

Step10:將序列Q前p%個(gè)子類作為候選子類,通過計(jì)算得出它們的中心點(diǎn)，作為初始候選中心。

其中，m為篩選條件，只有當(dāng)類中數(shù)據(jù)的數(shù)目大于數(shù)據(jù)總數(shù)的m%，才將此類加入到序列Q中；取序列Q的前q%計(jì)算它們的中心，作為初始候選中心；maxcluster為聚類的總數(shù)，測(cè)量?jī)蓚€(gè)數(shù)據(jù)之間的距離采用歐氏距離。

在這個(gè)迭代過程中可以發(fā)現(xiàn),位于數(shù)據(jù)密集區(qū)的數(shù)據(jù)最先聚集在一起。這一過程選擇出來的初始候選中心是經(jīng)過優(yōu)化的，能夠很好地反映數(shù)據(jù)的分布情況，提高了精確性。

2 算法流程

將最大最小距離算法的輸出作為K-means算法的輸入，使得聚類中心點(diǎn)能夠充分反映數(shù)據(jù)分布情況，很大程度上彌補(bǔ)了K-means算法在初始聚類中心選擇上的不足之處。優(yōu)化候選中心(OICC)K-means算法的框架大致分為三個(gè)階段：第一階段是產(chǎn)生候選中心及其優(yōu)化,獲得最佳的候選中心；第二階段是算法執(zhí)行,主要是K-means算法在已有初始聚類中心上進(jìn)行聚類操作；第三階段主要是實(shí)驗(yàn)和評(píng)估結(jié)果,驗(yàn)證OICCK-means的實(shí)際效果。

算法流程如圖3所示。

圖3 OICC K-means算法框架

OICCK-means算法有效解決了如何選擇候選中心的問題，既保證了聚類中心來自于數(shù)據(jù)密集區(qū)域,減小噪聲數(shù)據(jù)和邊緣數(shù)據(jù)的影響,同時(shí)也確保了被選中的聚類中心之間有足夠遠(yuǎn)的距離,真實(shí)地反映了整體數(shù)據(jù)的分布,使得算法更加穩(wěn)定和有效。

具體操作過程如下所述：

算法2：OICCK-means算法。

Input:需要進(jìn)行聚類的數(shù)據(jù);聚類內(nèi)數(shù)據(jù)數(shù)目占數(shù)據(jù)總數(shù)的百分比m%;序列Q的前P%，θ；

Output:經(jīng)過聚類的數(shù)據(jù)。

Step1:UPGMA算法:得到初始聚類候選中心;

Step2:最大最小距離算法:得到優(yōu)化的初始聚類中心；

Step3:K-means算法迭代;

Step4:結(jié)果評(píng)定。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)描述

對(duì)傳統(tǒng)的K-means算法和提出的OICCK-means算法在UCI的三個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行聚類效果對(duì)比。使用F-measure來衡量算法效果,包括準(zhǔn)確率(precision)和召回率(recall)。

準(zhǔn)確率定義為：

P(i,j)=precision(i,j)=Nij/Ni

(7)

召回率定義為：

R(i,j)=recall(i,j)=Nij/Nj

(8)

其中，Nij為聚類j中分類i的數(shù)目;Ni為分類i中所有的對(duì)象數(shù);Nj為聚類j中所有的對(duì)象數(shù)。

F-measure表示為:

F(i)=2P/(P+R)

(9)

在輸出的結(jié)果中，對(duì)分類i來說，F(xiàn)-measure高的聚類即對(duì)應(yīng)分類i。在實(shí)驗(yàn)中，文中運(yùn)用UCI中的數(shù)據(jù)集作為測(cè)試集,由于庫中的數(shù)據(jù)有明確的類別,可以直觀準(zhǔn)確地測(cè)試算法的聚類效果。選擇其中的Iris、Tae和Hayes-roth三個(gè)庫(見表1),比較了傳統(tǒng)K-means算法和OICCK-means算法在準(zhǔn)確率、召回率和F-measure上的實(shí)際數(shù)據(jù)。

表1 測(cè)試數(shù)據(jù)集

3.2 實(shí)驗(yàn)結(jié)果

Iris、Tae、Hayes-roth在OICCK-means算法中(m,q,θ)分別取(0.08,0.8,0.5)、(0.09,0.8,0.5)、(0.06,0.8,0.5)，傳統(tǒng)K-means算法中k的取值均取3。通過對(duì)這些結(jié)果的對(duì)比來說明OICCK-means算法在聚類效果方面的有效性。評(píng)價(jià)標(biāo)準(zhǔn)的值越大，說明聚類效果越好。對(duì)比實(shí)驗(yàn)結(jié)果如表2所示。

表2 算法對(duì)比

通過圖4可以更加直觀地看出兩個(gè)算法在效果上的差別。

由圖4可見，OICC算法相比于傳統(tǒng)K-means，在Iris數(shù)據(jù)集上，準(zhǔn)確率提高了58.0%，召回率提高了12.7%，F(xiàn)-measure提高了31.0%；在Tae數(shù)據(jù)集上，準(zhǔn)確率提高了72.5%，召回率提高了44.9%，F(xiàn)-measure提高了77.7%；在Hayes-roth數(shù)據(jù)集上，準(zhǔn)確率提高了36.4%，召回率提高了17.8%，F(xiàn)-measure提高了13.3%。原因在于OICCK-means算法運(yùn)用改進(jìn)UPGMA算法和最大最小距離算法得到經(jīng)過優(yōu)化的聚類候選中心,這些聚類中心可以真實(shí)有效地代表實(shí)際數(shù)據(jù)的分布[15]，大大增強(qiáng)了算法的聚類效果,同時(shí)算法的計(jì)算量明顯減少。該算法不僅可以自動(dòng)確定初始候選中心k的值，也避免了噪聲數(shù)據(jù)和邊緣數(shù)據(jù)對(duì)實(shí)驗(yàn)的影響，比傳統(tǒng)K-means算法在聚類方面具有更高的準(zhǔn)確性和實(shí)用性。

圖4 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

4 結(jié)束語

為了彌補(bǔ)傳統(tǒng)K-means算法聚類效果嚴(yán)重依賴于初始聚類中心這一不足，提出了OICCK-means算法。實(shí)驗(yàn)結(jié)果表明，該算法在聚類效果方面要好于傳統(tǒng)K-means算法，準(zhǔn)確率、召回率、F-measure三項(xiàng)指標(biāo)都有明顯提高，并且對(duì)不同的數(shù)據(jù)集都有比較好的效果。OICC算法是根據(jù)真實(shí)數(shù)據(jù)分布情況，通過對(duì)比數(shù)據(jù)間的距離得出較理想的候選中心，這些數(shù)據(jù)中心在一定程度上成為了數(shù)據(jù)密集區(qū)的代表，降低了噪聲數(shù)據(jù)、邊緣數(shù)據(jù)和不恰當(dāng)?shù)某跏季垲愔行膶?duì)實(shí)驗(yàn)的影響,使得K-means算法有一個(gè)較理想的聚類中心，具有較高的可行性。

[1] 謝娟英,高紅超.基于統(tǒng)計(jì)相關(guān)性與K-means的區(qū)分基因子集選擇算法[J].軟件學(xué)報(bào),2014,25(9):2050-2075.

[2] JAIN A K.Data clustering:50years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[3] SHI N,LIU X,GUAN Y.Research on k-means clustering algorithm:an improved k-means clustering algorithm[C]//Third international symposium on intelligent information technology and security informatics.[s.l.]:IEEE,2010:63-67.

[4] 仝雪姣，孟凡榮，王志曉．對(duì)k-means初始聚類中心的優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011,32(8)：2721-2723.

[5] 張文明,吳 江,袁小蛟.基于密度和最近鄰的k-means文本聚類算法[J].計(jì)算機(jī)應(yīng)用,2010,30(7):1933-1935.

[6] 熊忠陽,陳若田,張玉芳.一種有效的k-means聚類中心初始化方法[J].計(jì)算機(jī)應(yīng)用研究,2011,28(11)：4188-4190.

[7] MILLIGAN G W.Cluster analysis for researchers[J].Journal of Marketing Research,1985,22(2):224-225.

[8] 賴玉霞，劉建平.K-means算法的初始聚類中心的優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(10):147-149.

[9] 王賽芳，戴 芳，王萬斌，等．基于初始聚類中心優(yōu)化的K-均值算法[J]．計(jì)算機(jī)工程與科學(xué)，2010，32(10):105-107.

[10] SAMBASIVAM S,THEODOSOPOULOS N.Advanced data clustering methods of mining Web documents[J].Issues in Informing Science and Information Technology,2006,8(3):563-579.

[11] 傅德勝，周 辰．基于密度的改進(jìn)K均值算法及實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2011，31(2):432-434.

[12] DEHARIYA V K,SHRIVASTAVA S K,JAIN R C.Clustering of image data set using k-means and fuzzy k-means algorithms[C]//International conference on computational intelligence and communication networks.[s.l.]:IEEE Computer Society,2010:386-391.

[13] ERISOGLU M,CALIS N,SAKALLIOGLU S.A new algorithm for initial cluster centers in k-means algorithm[J].Pattern Recognition Letters,2011,32(14):1701-1705.

[14] 張宜浩，金 澎，孫 銳.基于改進(jìn)k-means算法的中文詞義歸納[J].計(jì)算機(jī)應(yīng)用，2012,32(5):1332-1334.

[15] 唐賢倫,仇國慶,莊 陵.一種面向非規(guī)則非致密空間分布數(shù)據(jù)的聚類方法[J].計(jì)算機(jī)科學(xué),2009,36(3):167-169.