李正兵，羅斌，翟素蘭，涂錚錚

1.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，合肥 230039

2.安徽省工業(yè)圖像處理與分析重點實驗室，合肥 230039

3.安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，合肥 230039

4.安徽大學(xué)計算智能與信號處理教育部重點實驗室，合肥 230039

基于關(guān)聯(lián)圖劃分的Kmeans算法

李正兵1，2，羅斌1，2，翟素蘭1，3，4，涂錚錚1，4

1.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，合肥 230039

2.安徽省工業(yè)圖像處理與分析重點實驗室，合肥 230039

3.安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，合肥 230039

4.安徽大學(xué)計算智能與信號處理教育部重點實驗室，合肥 230039

1 引言

傳統(tǒng)的Kmeans是基于中心的聚類算法[1]，因其簡潔、運算速度快，并能有效地處理大數(shù)據(jù)集而得到廣泛應(yīng)用。Kmeans有很多固有的缺陷[2-3]：對初始聚類中心的選擇過于敏感且容易陷入局部極值；聚類參數(shù)k很難確定。實際的應(yīng)用中，用戶往往不充分了解數(shù)據(jù)的分布特性，很難確定聚類參數(shù)k，增加了用戶的負擔(dān)。這兩個缺點極大地制約了Kmeans的應(yīng)用。

針對傳統(tǒng)Kmeans的缺陷，學(xué)者們做過一系列的研究。文獻[4-5]采用基于密度的最大最小距離法替代了傳統(tǒng)Kmeans隨機初始化聚類中心的方法，在收斂速度、準確率方面都有了較大的提高；文獻[6]運用距離代價函數(shù)作為聚類有效性檢驗函數(shù)，即當(dāng)距離代價函數(shù)達到最小值時，空間聚類結(jié)果為最優(yōu)，并在理論上做了嚴格證明；文獻[7]用直方圖方法將數(shù)據(jù)樣本空間進行最優(yōu)劃分，依據(jù)樣本自身分布特點確定k值；文獻[8]提出了一種新的基于數(shù)據(jù)樣本分布特性選取初始聚類中心的Kmeans算法。

本文通過分析原始數(shù)據(jù)集的分布特性，提出了基于關(guān)聯(lián)圖的Kmeans算法（以下簡稱：KCG），能夠在用戶指定的密集程度η下，自動確定聚類的數(shù)目，減輕了用戶的負擔(dān)，同時選取每個類別中關(guān)聯(lián)度最高的對象作為初始聚類中心。這種做法的優(yōu)點是能夠從全局的角度將初始聚類中心均衡地分布在整個數(shù)據(jù)空間中，避免了因?qū)Τ跏季垲愔行牡倪x擇而陷入局部極值。該方法可以得到較為合理的初始聚類中心和聚類數(shù)目，將它們作為參數(shù)調(diào)用Kmeans算法。通過有效性分析和實驗表明，KCG具有以下優(yōu)點：

（1）聚類的準確率能夠達到多次運行傳統(tǒng)的Kmeans算法的最高準確率。

（2）算法在用戶指定的密集程度η下自適應(yīng)地確定數(shù)據(jù)集的聚類數(shù)目。

（3）多種數(shù)據(jù)集，多次運行KCG算法，聚類結(jié)果穩(wěn)定性很好。

2 Kmeans算法思想

Kmeans算法是基于劃分的聚類方法，是十大經(jīng)典數(shù)據(jù)挖掘算法之一。Kmeans算法的基本思想是[1]：通過用戶事先指定聚類數(shù)目k，隨機選擇k個對象作為初始聚類中心，對最靠近它們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至標準測度函數(shù)開始收斂為止。

所獲得的聚類應(yīng)滿足[1]：同一類中的數(shù)據(jù)對象相似度較高；不同類中的數(shù)據(jù)對象相似度較小。

假設(shè)要把數(shù)據(jù)集D分為k個類別，傳統(tǒng)Kmeans算法描述如下：

步驟1隨機選擇k個類的初始聚類中心；

步驟2對任意一個對象，計算到k個中心的距離，并將該對象歸到相似性最大的中心所在的類；

步驟3利用均值法更新k個類的中心值；

步驟4對于所有的k個聚類中心，如果利用步驟2、步驟3的迭代法更新后，標準測度函數(shù)收斂或達到最大迭代次數(shù)，則迭代結(jié)束，否則繼續(xù)迭代。

3 圖劃分問題的數(shù)學(xué)描述

圖劃分的優(yōu)化理論可以描述為：

對于一個圖G=(V,E,ω)，其中頂點集為V=(ν1,ν2,…，νn)，邊集為E?V×V，用w:E→R表示邊上的權(quán)值，現(xiàn)將圖G劃分成k個子圖G1，G2，…，Gk，且G1∩G2∩…∩Gk=Φ，滿足以下目標函數(shù)：上式是求子圖間權(quán)重之和的最小值，實質(zhì)上等價于求子圖內(nèi)權(quán)重之后的最大值，即公式（2）與公式（3）等價：

4 KCG算法的設(shè)計

本文充分研究數(shù)據(jù)分布特性的度量方法和關(guān)聯(lián)圖的劃分方法，提出了KCG。該算法首先構(gòu)建對象集的關(guān)聯(lián)圖SG=(V，E，ω)，根據(jù)下文中公式（4）～（6）計算各對象的關(guān)聯(lián)度，再遍歷關(guān)聯(lián)圖SG，得到圖SG的一個合理劃分，選取每個子劃分中關(guān)聯(lián)度最高的對象作為該類的初始聚類中心，將子圖的數(shù)目作為聚類數(shù)目k。根據(jù)所得的初始聚類中心集和聚類數(shù)目k調(diào)用Kmeans算法，得到最終的聚類結(jié)果。

4.1 關(guān)聯(lián)圖的構(gòu)造

首先將每個數(shù)據(jù)對象di看做關(guān)聯(lián)圖SG的一個頂點νi，任意的兩個頂點νi、νj有一條邊eij，邊上的權(quán)重按照公式（4）進行定義。所得的是一個完全圖，為了降低計算的復(fù)雜度，對完全圖作如下處理：對于每個頂點νi，將與其相連的所有邊權(quán)重的均值作為閾值，即公式（5），刪除權(quán)重小于閾值的所有邊，保留權(quán)重大于或等于閾值的邊，即公式（6）得到較為稀疏的關(guān)聯(lián)圖SG=(V，E)。

定義1設(shè)di為n維數(shù)據(jù)di=(di1，di2，…，din)，將邊eij的權(quán)重weight(eij)定義為：

4.2 關(guān)聯(lián)度的定義和計算

對于4.1節(jié)中得到的關(guān)聯(lián)圖SG=(V，E)，依次定義各頂點對應(yīng)的對象di的度df(di)，關(guān)聯(lián)權(quán)重之和sw(di)，關(guān)聯(lián)度attachment(di)為公式（7）～（9），這三個指標能夠很好地反應(yīng)對象集的分布特性：關(guān)聯(lián)度越大，表示數(shù)據(jù)的平均密集程度越高。

定義4第i個對象di的度df(di)為：

定義5第i個對象di的關(guān)聯(lián)權(quán)重之和sw(di)為：

4.3 KCG具體描述

輸入：數(shù)據(jù)對象集D

輸出：合理的聚類結(jié)果

步驟1申請一個空隊列Q（用于關(guān)聯(lián)圖的遍歷），一個空棧S（存儲候選聚類中心），初始化聚類數(shù)目clusternum=1。

步驟2按照4.1節(jié)所述構(gòu)建關(guān)聯(lián)圖SG=(V，E，w)，根據(jù)公式（7）～（9）計算各對象關(guān)聯(lián)度attachment(di)，根據(jù)關(guān)聯(lián)度降序排列對象集D，初始時所有對象均未被標記。

步驟3若D中存在數(shù)據(jù)對象未被標記，則將具有最高關(guān)聯(lián)度的對象d加入隊列Q，作上訪問標記，同時作為類別clusternum的初始聚類中心加入S中，否則程序執(zhí)行完畢（即：將當(dāng)前未被標記的具有最高關(guān)聯(lián)度的數(shù)據(jù)對象選做類別clusternum的候選聚類中心）。

步驟5利用上述四步得到的初始聚類中心集S和聚類數(shù)目clusternum，調(diào)用Kmeans算法，便得到合理的聚類結(jié)果。

4.4 KCG的幾點說明

4.4.1 參數(shù)η的選取

η通常取1，得到的聚類數(shù)目非常接近數(shù)據(jù)集的自然數(shù)目。很多實際的應(yīng)用中為了得到不同粒度上的聚類，可以對η進行放縮，如15%、25%等等。

4.4.2 初始聚類中心的選擇

KCG中選擇新的初始聚類中心至關(guān)重要。較高的關(guān)聯(lián)度具有較高的權(quán)重之和，因此反映了該對象與相鄰對象的密集程度。所以選擇一個沒有被訪問的具有最高關(guān)聯(lián)度的對象作為一個新類的候選聚類中心非常合理。

4.4.3 類的擴充

初始化時每個類僅有一個初始聚類中心。考慮關(guān)聯(lián)圖中所有相鄰的對象，一個相鄰的對象被加入此類當(dāng)且僅當(dāng)它和初始聚類中心是最相似的。新加入的對象再執(zhí)行初始聚類中心相似的操作擴充該類。

4.4.4 有效性分析

良好的初始聚類中心的選擇算法保證了子圖內(nèi)權(quán)重之和達到最大值，即子圖內(nèi)相似度最大的原則，所得的聚類結(jié)果趨于全局最優(yōu)解。

本文對初始對象集沒有作任何假設(shè)，第5章中的實驗表明在真實的和人工數(shù)據(jù)集上KCG都能夠得到非常好的聚類結(jié)果，同時說明算法的有效性。

5 實驗設(shè)計及結(jié)果分析

聚類結(jié)果的好壞可以用聚類精度、迭代次數(shù)、運行時間和聚類精度的方差四個指標來衡量。本章將傳統(tǒng)Kmeans 和KCG在上述四個指標下作了對比實驗。

5.1 聚類性能測試

UCI數(shù)據(jù)庫是國際通用的測試數(shù)據(jù)挖掘算法的標準數(shù)據(jù)庫，每個數(shù)據(jù)含有一個確定的屬性分類，因此方便計算每次聚類的精確度。采用的測試數(shù)據(jù)是UCI數(shù)據(jù)庫的Iris、Wine、Glass三組數(shù)據(jù)。

由于傳統(tǒng)Kmeans算法對初始聚類中心依賴性較強，因此需要多次運行了解其平均性能。在表1至表3中，Kmeans 與KCG分別取50次運行的結(jié)果。圖1中，Kmeans與KCG在三種數(shù)據(jù)集上分別運行50、100、150、200、250、300、350 和400次，取聚類精度的方差。為了增加實驗的可比性，本文設(shè)定傳統(tǒng)Kmeans的聚類參數(shù)k與KCG算法中的一致。

表1 Kmeans算法與KCG聚類精度比較

表2 Kmeans算法與本文算法迭代次數(shù)比較

表3 Kmeans算法與KCG平均時間比較

聚類精度的計算公式：r=1-er/N，其中N為樣本總數(shù)，er為錯分樣本個數(shù)。

圖1 三種數(shù)據(jù)集上聚類準確率的方差

由表1可知，在數(shù)據(jù)集Iris、Wine、Glass上KCG聚類精度超出了傳統(tǒng)Kmeans的平均精度的3.54%、2.78%、2.94%，達到了多次運行傳統(tǒng)Kmeans算法的最高精度，由此可見KCG在聚類精度上有了較大的提高。由表2可知，與傳統(tǒng)Kmeans算法的平均迭代次數(shù)相比，KCG分別減少了2.4、3.2、4.6次，優(yōu)化之后的迭代次數(shù)有了較大減少，收斂速度有了較大提高。因此KCG有較高的聚類精度。

由表3可知，KCG的執(zhí)行時間有了一定的延長。這里主要時間消耗為構(gòu)建關(guān)聯(lián)圖，時間復(fù)雜度為O(N2)，略大于傳統(tǒng)聚類算法的時間復(fù)雜度O(Nkt)，其中N為數(shù)據(jù)對象的個數(shù)，k是聚類數(shù)目，t是迭代次數(shù)。而傳統(tǒng)的Kmeans算法需要多次運行找到較好的結(jié)果，從這個角度來說時間消耗換得性能的提高是很有意義的。

圖2 四種人工數(shù)據(jù)集上的聚類效果圖

由圖1可知，在不同的數(shù)據(jù)集上，KCG準確率的方差均較原Kmeans算法小很多，說明KCG算法有較高的穩(wěn)定性。

5.2 聚類參數(shù)k的自動估計

為了驗證KCG算法能夠在指定的η下自適應(yīng)確定聚類的數(shù)目，本文選取了UCI數(shù)據(jù)集上的八種數(shù)據(jù)集分別在η為1、0.8、1.2的實驗結(jié)果，如表4所示。

表4 KCG算法對聚類參數(shù)k的估計

為了能夠更直觀地考察KCG的性能，選取了四組人工數(shù)據(jù)集，分別代表四種不同的流行結(jié)構(gòu)，所獲得聚類結(jié)果如圖2所示。

從表4、圖2中可以看出，KCG能夠自動確定聚類的數(shù)目，并且非常符合聚類數(shù)據(jù)的實際類別。在聚類準確率上圖2（a）有所偏離，這說明本文的算法在環(huán)繞的流行數(shù)據(jù)集上的處理效果還不是很好。自適應(yīng)地確定聚類數(shù)目能夠給用戶帶來極大的方便。

6 結(jié)束語

Kmeans算法是一種應(yīng)用非常廣泛的聚類算法，但它對初始聚類中心的依賴性較強，容易陷入局部最優(yōu)解。本文提出的KCG能夠從全局角度均衡地選取初始聚類中心，確定聚類數(shù)目，增加找到全局最優(yōu)解的可能。

有效性分析和實驗表明，KCG較大地提高了聚類性能。但該算法仍然沒有解決Kmeans算法處理非球形數(shù)據(jù)、流行數(shù)據(jù)集的聚類效果，如何拓展Kmeans算法的適用范圍是下一步要做的工作。

[1]Jain A K.Data clustering：50 years beyond Kmeans[C]//Daelemans W，Goethals B，Morik K.Lecture Notes in Computer Science 5211：ECML/PKDD（1），2008：3-4.

[2]Pollard D.Strong consistency of Kmeans clustering[J].Ailnals of Statistics，1981，9：135-140.

[3]Huang Z.Extensions to the Kmeans algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discover，1998，2.

[4]張文明，吳江，袁小蛟.基于密度和最近鄰的K-means文本聚類算法[J].計算機應(yīng)用，2010，30（7）：1933-1934．

[5]Gan Wenyan，Li Deyi.Hierarchical clustering based on kernel density estimation[J].Journal of System Simulation，2004，16 （2）：302-309.

[6]楊善林，李永森，胡笑旋，等.K-means算法中的k值優(yōu)化問題研究[J].系統(tǒng)工程理論與實踐，2006（2）：97-101.

[7]張健沛，楊悅，楊靜，等.基于最優(yōu)劃分的K-Means初始聚類中心選取算法[J].系統(tǒng)仿真學(xué)報，2009，21（9）：2586-2590.

[8]曹志宇，張忠林，李元韜.快速查找初始聚類中心的Kmeans算法[J].蘭州交通大學(xué)學(xué)報，2009，28（6）：15-18.

[9]Mimaroglu S，Erdil E.Combining multiple clusterings using similarity graph[J].Pattern Recognition，2011，44.

LI Zhengbing1，2,LUO Bin1，2,ZHAI Sulan1，3，4,ΤU Zhengzheng1，4

1.School of Computer Science&Τechnology,Anhui University,Hefei 230039,China
2.Anhui Provincial Key Lab for Industrial Image Processing and Analysis,Hefei 230039,China
3.School of Mathematical Sciences,Anhui University,Hefei 230039,China
4.Key Lab of Intelligent Computing and Signal Processing of Ministry of Education,Anhui University,Hefei 230039,China

Kmeans is the most typical clustering algorithm,which is widely used because it is concise,fast.As the traditional Kmeans is sensitive to initial clustering centers and the value of clustering parameter k is difficult to establish,this paper proposes an algorithm based on the partition of correlational graph.Τhe algorithm can select initial clustering centers globally according to the distribution characteristics of the given data;the algorithm can determine the number of cluster automatically according to intensive degree of the given data.Effective experiments show that the algorithm has great accuracy and stability.

Kmeans;relation graph;initial clustering center;similarity matrix

Kmeans是最典型的聚類算法，因其簡潔、快速而被廣泛使用。針對傳統(tǒng)Kmeans算法對初始聚類中心敏感和聚類參數(shù)k難以確定的問題，提出了一種基于關(guān)聯(lián)圖劃分的Kmeans算法。該算法能夠有效地根據(jù)數(shù)據(jù)的分布特性選取初始聚類中心，能夠在指定的數(shù)據(jù)密集程度下自適應(yīng)確定聚類數(shù)目。有效性實驗表明上述改進的Kmeans算法具有較高的準確率和穩(wěn)定性。

K均值；關(guān)聯(lián)圖；初始聚類中心；相似度矩陣

A

ΤP391

10.3778/j.issn.1002-8331.1202-0314

LI Zhengbing,LUO Bin,ZHAI Sulan,et al.Kmeans algorithm based on partition of correlational graph.Computer Engineering and Applications,2013,49（21）：141-144.

國家自然科學(xué)基金（No.61073116）；安徽省教育廳自然科學(xué)研究基金資助重大項目（No.KJ2011ZD10）；博碩士隊伍建設(shè)計劃（No.02203105）；安徽省高校優(yōu)秀青年人才基金項目（No.2009SQRZ19ZD）。

李正兵（1988—），男，碩士研究生，主要研究方向：圖像處理和模式識別；羅斌，教授，博導(dǎo)，主要研究方向：圖像處理與模式識別；翟素蘭，副教授，碩導(dǎo)。E-mail：lizhengbing870427@163.com

2012-02-20

2012-04-09

1002-8331（2013）21-0141-04

CNKI出版日期：2012-06-15http://www.cnki.net/kcms/detail/11.2127.ΤP.20120615.1726.025.html