基于UPGMA的優化初始中心K-means算法研究

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

(南京理工大學 計算機科學與工程學院，江蘇 南京 210000)

0 引 言

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

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

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

1 優化候選中心K-means算法

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

圖1 數據與候選中心分布

1.1 基本思想

定義1：數據點Xi與Xj之間的距離定義為：

(1)

其中，Xi、Xj表示數據集中m維的數據對象。

定義2：聚類C中心點的坐標為C=(C1,C2,…,Cj),第j維的數據定義為：

(2)

其中，n為子類包含的數據個數；Xi為子類內的數據。

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

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

Dmax=Max(d)

(3)

其中，d為每個聚類與數據集中剩余各數據距離的最小值組成的集合。

定義4：d為每個聚類與數據集中剩余各數據距離的最小值，即

(4)

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

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

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

(5)

其中，v1、v2為最先成為優化后的候選中心的點；θ為參數，常取0.5。

定義6：K-means算法進行聚類的準則函數為誤差平方和準則函數。

(6)

其中，Mi為類Ci中所有數據的均值；p為類Ci中的每個數據；Jc為樣本和聚類中心的函數。在已知樣本集時,Jc的值取決于Mi。Jc描述了n個樣本數據得出k個分類產生的總的誤差平方和。可以看出,Jc越大,表明誤差越大,效果越差。所以應力求Jc最小,從而得出最好的聚類效果。

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

圖中，p1、p2、p3的初值不同,目標函數分別順著誤差平方和準則函數逐漸減小的方向搜索,直到找到各自對應的最小值A、B、C。其中,A、B為局部極小值,C為全局最小值,但算法結束時經常只能收斂局部極小值[13-14]。

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

1.2 改進UPGMA算法

在UPGMA改進算法中，將每個數據都看作一個類，獲得每個類之間的距離,將相互間距離最小的數據加入到同一個類中形成一個新類,重復此步驟,當滿足算法停止的條件或者不再產生新類時,算法結束。改進的UPGMA運算過程如下所述：

算法1：改進UPGMA算法。

Input:需要進行聚類的數據;聚類內數據數目占數據總數的百分比m%;序列Q的前p%；

Output:初始候選中心。

Step1:把所有數據都看成一個獨立的類。

Step2:計算出任意兩個類的距離，合并相距最近的兩個類，同時判斷剩下數據的總數是否大于等于總數的m%,若否，則轉Step4。

Step3:迭代次數i=0

Step4:do

Step5:t=t+1;

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

當子類i和子類j內部的數據個數少于等于總數的m%時,計算兩個類之間的距離,并加入到距離矩陣中。

Step7:endfor

Step8:在距離矩陣中找到距離最小的對應的兩個類，將它們合并為新類,同時加入到序列Q的結尾,轉至Step2。

Step9:whilet>maxcluster

Step10:將序列Q前p%個子類作為候選子類,通過計算得出它們的中心點，作為初始候選中心。

其中，m為篩選條件，只有當類中數據的數目大于數據總數的m%，才將此類加入到序列Q中；取序列Q的前q%計算它們的中心，作為初始候選中心；maxcluster為聚類的總數，測量兩個數據之間的距離采用歐氏距離。

在這個迭代過程中可以發現,位于數據密集區的數據最先聚集在一起。這一過程選擇出來的初始候選中心是經過優化的，能夠很好地反映數據的分布情況，提高了精確性。

2 算法流程

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

算法流程如圖3所示。

圖3 OICC K-means算法框架

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

具體操作過程如下所述：

算法2：OICCK-means算法。

Input:需要進行聚類的數據;聚類內數據數目占數據總數的百分比m%;序列Q的前P%，θ；

Output:經過聚類的數據。

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

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

Step3:K-means算法迭代;

Step4:結果評定。

3 實驗結果與分析

3.1 實驗描述

對傳統的K-means算法和提出的OICCK-means算法在UCI的三個標準數據集上進行聚類效果對比。使用F-measure來衡量算法效果,包括準確率(precision)和召回率(recall)。

準確率定義為：

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

(7)

召回率定義為：

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

(8)

其中，Nij為聚類j中分類i的數目;Ni為分類i中所有的對象數;Nj為聚類j中所有的對象數。

F-measure表示為:

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

(9)

在輸出的結果中，對分類i來說，F-measure高的聚類即對應分類i。在實驗中，文中運用UCI中的數據集作為測試集,由于庫中的數據有明確的類別,可以直觀準確地測試算法的聚類效果。選擇其中的Iris、Tae和Hayes-roth三個庫(見表1),比較了傳統K-means算法和OICCK-means算法在準確率、召回率和F-measure上的實際數據。

表1 測試數據集

3.2 實驗結果

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)，傳統K-means算法中k的取值均取3。通過對這些結果的對比來說明OICCK-means算法在聚類效果方面的有效性。評價標準的值越大，說明聚類效果越好。對比實驗結果如表2所示。

表2 算法對比

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

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

圖4 數據集實驗結果

4 結束語

為了彌補傳統K-means算法聚類效果嚴重依賴于初始聚類中心這一不足，提出了OICCK-means算法。實驗結果表明，該算法在聚類效果方面要好于傳統K-means算法，準確率、召回率、F-measure三項指標都有明顯提高，并且對不同的數據集都有比較好的效果。OICC算法是根據真實數據分布情況，通過對比數據間的距離得出較理想的候選中心，這些數據中心在一定程度上成為了數據密集區的代表，降低了噪聲數據、邊緣數據和不恰當的初始聚類中心對實驗的影響,使得K-means算法有一個較理想的聚類中心，具有較高的可行性。

[1] 謝娟英,高紅超.基于統計相關性與K-means的區分基因子集選擇算法[J].軟件學報,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] 仝雪姣，孟凡榮，王志曉．對k-means初始聚類中心的優化[J].計算機工程與設計，2011,32(8)：2721-2723.

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

[6] 熊忠陽,陳若田,張玉芳.一種有效的k-means聚類中心初始化方法[J].計算機應用研究,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算法的初始聚類中心的優化[J].計算機工程與應用,2008,44(10):147-149.

[9] 王賽芳，戴 芳，王萬斌，等．基于初始聚類中心優化的K-均值算法[J]．計算機工程與科學，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] 傅德勝，周 辰．基于密度的改進K均值算法及實現[J].計算機應用，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] 張宜浩，金 澎，孫 銳.基于改進k-means算法的中文詞義歸納[J].計算機應用，2012,32(5):1332-1334.

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