基于密度期望和有效性指標(biāo)的K-均值算法

何云斌，肖宇鵬，萬靜，李松

哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

基于密度期望和有效性指標(biāo)的K-均值算法

何云斌，肖宇鵬，萬靜，李松

哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

1 引言

所謂聚類，就是根據(jù)事物的某些屬性，將其劃分為若干類，使得類內(nèi)相似性盡量大，類間相似性盡量小。聚類是一種無監(jiān)督分類方法，其對(duì)數(shù)據(jù)及分析人員的專業(yè)相關(guān)知識(shí)要求較少，因而其相關(guān)技術(shù)在統(tǒng)計(jì)、模式識(shí)別、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等諸多領(lǐng)域中都有極其廣泛的應(yīng)用前景[1]。通過適當(dāng)?shù)木垲悾梢园l(fā)現(xiàn)同類事物共同性質(zhì)的特征型知識(shí)，以及不同類事物之間的差異型知識(shí)。為了對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類，目前已經(jīng)提出許多有效的聚類算法，例如基于層次的CURE[2]算法，基于劃分的K-Means[3]算法，基于密度的DBSCAN[4]算法，基于網(wǎng)格的STING[5]算法，基于模型的COBWEB[6]算法等。

在諸多聚類算法中，K-均值聚類算法是使用最為廣泛的算法之一。該算法對(duì)大型數(shù)據(jù)集的處理效率較高，特別是當(dāng)簇群密集，簇間距離較大時(shí)，能得到較好的聚類效果。傳統(tǒng)K-均值算法的初始聚類中心點(diǎn)是從數(shù)據(jù)集中隨機(jī)產(chǎn)生的，因此在聚類過程中容易陷入局部最優(yōu)解，并且聚類結(jié)果不穩(wěn)定。針對(duì)上述缺點(diǎn)，文獻(xiàn)[7]中Likas等人提出了全局K-均值算法，通過不斷迭代的方式最終確定最佳初始聚類中心；文獻(xiàn)[8]提出了基于可變閥值的初始聚類中點(diǎn)選取方法，選擇較為分散的樣本作為初始聚類中心，以增加找到全局最優(yōu)解的可能性；文獻(xiàn)[9]對(duì)最大最小距離算法進(jìn)行了改進(jìn)，選取到所有已初始化聚類中心距離最大的高密度點(diǎn)作為當(dāng)前聚類中心；文獻(xiàn)[10]引入特征選擇和特征賦權(quán)思想，提出了基于密度的初始中心點(diǎn)選取算法和改進(jìn)的特征賦權(quán)K-均值算法；文獻(xiàn)[11]將免疫原理的選擇操作機(jī)制引入遺傳算法中，利用遺傳算法全局尋優(yōu)能力和K-均值算法的高效性，較好地解決了聚類中心優(yōu)化的問題；文獻(xiàn)[12]提出了一種改進(jìn)人工蜂群算法與K-均值相結(jié)合的混合聚類方法，將蜂群算法全局尋優(yōu)能力與局部尋優(yōu)能力的優(yōu)點(diǎn)與K-均值算法收斂速度快的優(yōu)點(diǎn)相結(jié)合，克服了傳統(tǒng)K-均值聚類算法穩(wěn)定性差的缺點(diǎn)。此外，對(duì)于實(shí)際問題中聚類數(shù)目的適當(dāng)選取也是獲取高精度聚類結(jié)果的關(guān)鍵因素之一。但多數(shù)情況下，聚類數(shù)k無法預(yù)先確定。對(duì)于有效聚類數(shù)k值的選取，李永森，楊善林等[13]提出了距離代價(jià)函數(shù)，綜合了類間距離與類內(nèi)距離，并證明了當(dāng)距離代價(jià)函數(shù)最小時(shí)，可得到最佳聚類數(shù)k；汪中等[14]學(xué)者在距離代價(jià)函數(shù)的基礎(chǔ)上，提出了新的評(píng)價(jià)函數(shù)，即均衡化函數(shù)，以均衡化函數(shù)為準(zhǔn)則自動(dòng)生成有效聚類數(shù)目；文獻(xiàn)[15]則利用二分思想遞歸分裂簇內(nèi)相似度大于給定閥值的簇，合并簇間相似度小于給定閥值的簇，從而最終確定有效的聚類數(shù)；此外，諸如Silhouette[16]、Calinski-Harabasz[17]、In-Group Proportion[18]、Davies-Bouldin[19]、Dunn[19]等學(xué)界公認(rèn)較為優(yōu)秀的聚類有效性指標(biāo)函數(shù)也常用于評(píng)價(jià)聚類結(jié)果，并根據(jù)評(píng)價(jià)的結(jié)果來確定最優(yōu)的k值。

本文首先提出了基于密度期望的初始聚類中心點(diǎn)選取方法。該方法消除了傳統(tǒng)K-均值算法對(duì)初始聚類中心點(diǎn)選取的盲目性，并且有效地減少了聚類的迭代次數(shù)，同時(shí)還獲得了更穩(wěn)定的聚類結(jié)果。在上述基礎(chǔ)上，本文還給出了一種基于密度期望和聚類有效性指標(biāo)函數(shù)的K-均值優(yōu)化算法。該算法對(duì)于不同的k值，首先使用基于密度期望的方法選取k個(gè)初始聚類中心點(diǎn)，其次對(duì)樣本集進(jìn)行聚類，最后通過聚類有效性指標(biāo)分析每次聚類的結(jié)果，從而確定最佳有效聚類數(shù)。

2 傳統(tǒng)K-均值聚類算法

式中，nj表示聚類子集Cj中樣本的數(shù)量。

傳統(tǒng)K-均值聚類算法基本思想：首先隨機(jī)地從樣本空間中選取k個(gè)初始聚類中心；通過式（1）計(jì)算對(duì)象間的距離，根據(jù)距離最小的原則，將每個(gè)對(duì)象分配給距離最近的初始代表點(diǎn)所在的聚類簇Cj；完成數(shù)據(jù)樣本劃分后，對(duì)每一個(gè)聚類簇計(jì)算簇中所有對(duì)象的平均值cj，并將其作為新的簇中心點(diǎn)；通過不斷迭代對(duì)樣本數(shù)據(jù)進(jìn)行劃分，直至劃分的結(jié)果不再發(fā)生變化，即誤差平方和準(zhǔn)則函數(shù)E的值達(dá)到最優(yōu)。誤差平方和準(zhǔn)則函數(shù)定義為：

式中，xi為空間的點(diǎn)，即數(shù)據(jù)對(duì)象，ci是簇Ci的平均值。E越大說明對(duì)象與聚類中心的距離越大，簇內(nèi)的相似度越低；E越小說明簇內(nèi)的相似度越高。

算法描述如下：

從算法的第一步可以看出，在聚類數(shù)目k值事先確定的情況下，初始中心點(diǎn)的選取是隨機(jī)的。這就可能造成在同一類別中的樣本被強(qiáng)行當(dāng)做兩個(gè)類的初始聚類中心，如圖1中的紅色樣本數(shù)據(jù)，其中有兩個(gè)黑色樣本點(diǎn)被強(qiáng)行選做兩個(gè)類的初始聚類中心。因此在圖2中，最終使得聚類結(jié)果只能收斂于局部最優(yōu)。故而，K-均值算法的聚類效果在很大程度上依賴于初始聚類中心的選擇。

圖1 初始中心點(diǎn)隨機(jī)選取情況

圖2 聚類結(jié)果的局部最優(yōu)

3 基于密度期望的初始中心點(diǎn)選取

對(duì)于傳統(tǒng)的K-均值聚類算法，隨機(jī)選取初始的聚類中心往往不能較好地反映數(shù)據(jù)的分布情況，因而得到的聚類結(jié)果往往也是局部最優(yōu)的。通常希望所選取的初始聚類中心較為分散，但在一般的基于貪心算法的初始中心點(diǎn)搜索過程中，由于僅考慮距離因素，往往找到許多孤立點(diǎn)作為初始聚類中心點(diǎn)，不利于算法的聚類[15]。因此在選擇聚類初始中心點(diǎn)時(shí)，如果同時(shí)考慮距離和密度兩個(gè)因素，則可有效改善初始聚類中心點(diǎn)的選取效果。這里所提及的密度是指樣本的密度，具有統(tǒng)計(jì)的性質(zhì)，即對(duì)于待聚類樣本中的某一對(duì)象，在其給定的鄰域有效半徑r中包含的樣本數(shù)目，即為該樣本點(diǎn)的密度。此外，期望所選取的最大樣本密度應(yīng)小于或等于聚類簇中樣本的數(shù)量。因?yàn)檫@樣的一組樣本點(diǎn)在鄰域有效半徑r作用下，能較好地反映該聚類簇的分布情況。特別是對(duì)于每一個(gè)聚類簇中樣本數(shù)量大致相當(dāng)?shù)那闆r下，如圖3中所示，所選取的一組樣本點(diǎn)，在半徑r的鄰域內(nèi)包含了其所屬聚類簇中樣本的70%左右。因此可以看出該組樣本點(diǎn)能有效地代表其所屬聚類簇中的所有樣本。因而在聚類數(shù)k已知的情況下，可以通過計(jì)算樣本總數(shù)n和k值，進(jìn)而得到每一個(gè)聚類簇中大致期望的樣本平均個(gè)數(shù)，同時(shí)對(duì)其附加最大及最小期望系數(shù)，即為樣本點(diǎn)密度范圍的上、下限。隨后從最大與最小密度期望之間選取相距最遠(yuǎn)的k個(gè)對(duì)象作為初始聚類中心。這樣不僅能有效避免所選取的樣本點(diǎn)過分密集，同時(shí)還屏蔽了異常數(shù)據(jù)對(duì)算法結(jié)果的影響。

圖3 鄰域半徑r下的樣本密度

3.1 基本定義

已知樣本數(shù)據(jù)集X={x1,x2,…,xn}為m維空間的n個(gè)對(duì)象。

定義1（樣本密度）對(duì)于空間中任意樣本xi和鄰域有效半徑r，以樣本xi為中心，半徑為r的區(qū)域中樣本點(diǎn)個(gè)數(shù)稱為樣本xi基于距離r的密度，計(jì)為Density(xi)，即

Density(xi)={p∈X|Dist(xi,p)≤r}（4）式中，r為鄰域有效半徑，Dist(xi,p)為數(shù)據(jù)集中任意兩點(diǎn)的歐氏距離，其定義如2章中的式（1）。

定義2（鄰域半徑）鄰域有效半徑r定義為：

式中，θ為半徑調(diào)節(jié)參數(shù)；n為樣本個(gè)數(shù)；xi，xj為樣本對(duì)象。

聚類對(duì)象的有效鄰域半徑r以n個(gè)樣本的均方根距離為基礎(chǔ)，這是由于樣本的均方根距離能較好地反映樣本的離散程度，通過調(diào)節(jié)參數(shù)θ來調(diào)節(jié)半徑r的大小，使得半徑r保持在一個(gè)合理的范圍內(nèi)。

定義3（密度期望）密度期望范圍定義為：

3.2 基于密度期望的初始中心點(diǎn)選取方法

設(shè)樣本數(shù)據(jù)集X={x1,x2,…,xn}為m維空間的n個(gè)對(duì)象，現(xiàn)將對(duì)其聚成k類；集合D包含樣本密度在密度期望區(qū)間范圍內(nèi)的樣本點(diǎn)；集合U保存所選取的初始聚類中心。

算法的基本思想是：計(jì)算樣本總數(shù)n和k值，得到每個(gè)類簇中大致期望的樣本平均個(gè)數(shù)，并對(duì)其附加最大及最小期望系數(shù)，從而得到密度期望區(qū)間的上下限；其次計(jì)算數(shù)據(jù)集中所有樣本的密度，將介于密度期望區(qū)間范圍內(nèi)的樣本添加到集合D中；接著從集合D中選取密度最大的樣本點(diǎn)d1作為第一個(gè)初始聚類中心點(diǎn)，并添加到集合U中，此時(shí)D=D-{d1}，U=U∪{d1}；然后不斷從集合D中選取距集合U中所有樣本平均距離最遠(yuǎn)的樣本di，作為第i個(gè)初始聚類中心點(diǎn)添加到集合U中，有D=D-{di}，U=U∪{di}，直至集合U中的樣本數(shù)等于k為止。最后，以集合U中的k個(gè)樣本作為初始聚類中心，按照K-均值算法進(jìn)行聚類分析。

算法描述：

算法中，選取處于密度期望范圍內(nèi)相距最遠(yuǎn)的k個(gè)對(duì)象作為初始聚類中心點(diǎn)，這些中心點(diǎn)能較好地反映數(shù)據(jù)的分布，使聚類結(jié)果具有較好的穩(wěn)定性。但是有效鄰域半徑調(diào)節(jié)參數(shù)θ是未知的，是根據(jù)實(shí)驗(yàn)數(shù)據(jù)選取的，其數(shù)值的大小會(huì)對(duì)有效鄰域半徑r產(chǎn)生影響。這是因?yàn)閞過大或者過小都會(huì)使聚類結(jié)果較差，故而要求有效鄰域半徑r的取值應(yīng)能良好地反映樣本在空間的分布情況。通常有效鄰域半徑調(diào)節(jié)參數(shù)θ是基于經(jīng)驗(yàn)選取的，θ滿足0＜θ＜1。

傳統(tǒng)K-均值算法的時(shí)間復(fù)雜度為O(nkt)，其中n是所有樣本數(shù)目，k是聚類數(shù)目，t是迭代的次數(shù)[20]。在基于密度期望的改進(jìn)K-均值算法中，計(jì)算樣本密度時(shí)需要事先計(jì)算所有樣本之間距離，其時(shí)間復(fù)雜度為O(n2)，因此該算法的時(shí)間復(fù)雜度為O(n2+nkt)，即O(n2)。

4 基于密度期望和聚類有效性指標(biāo)函數(shù)的k值優(yōu)化

對(duì)于有效聚類數(shù)k值的選取，目前通常的做法是要預(yù)先確定其最佳搜索范圍[kmin,kmax]的上、下限，而后在從中選取合適的數(shù)值作為最佳有效聚類數(shù)。其中對(duì)于最佳搜索范圍下限kmin有，當(dāng)kmin=1時(shí)，表明樣本是均勻分布的，無明顯特征差異。因此通常聚類數(shù)k最小為2，即kmin=2[21]。而對(duì)kmax的確定尚無明確的理論指導(dǎo)，其中Frey等人在文獻(xiàn)[22]中提出了近鄰傳播聚類算法（Affinity Propagation clustering），簡(jiǎn)稱AP算法，將該算法產(chǎn)生的聚類數(shù)作為聚類數(shù)搜索范圍的上限kmax。此外，更多采用的是通過經(jīng)驗(yàn)規(guī)則來確定聚類數(shù)搜索范圍的上限kmax，即kmax≤n。于劍等在文獻(xiàn)[23]中給出了確定kmax新方法，該方法證明了規(guī)則kmax≤n具有一定的理論依據(jù)，并在文獻(xiàn)中驗(yàn)證了新方法的有效性。楊善林等[13]提出了運(yùn)用距離代價(jià)函數(shù)確定最優(yōu)的k值，同時(shí)還給出了k值最優(yōu)解kopt及其上界kmax的條件，并證明了規(guī)則的合理性。

4.1 聚類有效性指標(biāo)函數(shù)

當(dāng)確定有效聚類數(shù)目k的搜索范圍后，選擇合適的聚類有效性指標(biāo)是尤為關(guān)鍵的。聚類有效性指標(biāo)主要有兩類，即外部有效性指標(biāo)和內(nèi)部有效性指標(biāo)。當(dāng)原始數(shù)據(jù)劃分是已知的情況下，外部有效性指標(biāo)反映了聚類劃分結(jié)果與原始數(shù)據(jù)劃分之間的吻合度；內(nèi)部有效性指標(biāo)則是在原始數(shù)據(jù)劃分未知的情況下評(píng)價(jià)聚類結(jié)果好壞的一個(gè)度量。因而對(duì)于有效聚類數(shù)目k的確定，可借助內(nèi)部有效性指標(biāo)來實(shí)現(xiàn)。通過對(duì)不同k值下聚類有效性指標(biāo)的計(jì)算，將最優(yōu)聚類結(jié)果所對(duì)應(yīng)的聚類數(shù)目作為最佳聚類數(shù)，從而最終確定有效的k值。目前在常用的聚類有效性指標(biāo)函數(shù)中Silhouette[17]指標(biāo)以其較優(yōu)良的性能及較低的計(jì)算復(fù)雜度，得到了廣泛的應(yīng)用。Silhouette指標(biāo)是一種復(fù)合型指標(biāo)，Silhouette指標(biāo)定義如下：

假設(shè)樣本xi屬于簇Ci，a(xi)表示樣本xi到Ci中其余樣本的平均距離；b(xi)表示樣本xi到其他每個(gè)類中樣本的平均距離的最小值。即有：

每個(gè)樣本的Silhouette指標(biāo)值介于[-1,1]的區(qū)間內(nèi)，當(dāng)Sil(xi)接近于1時(shí)，表明樣本xi歸到簇Ci是適合的；當(dāng)Sil(xi)近似于0時(shí)，表明樣本xi可能屬于距離簇Ci最近的類簇中；當(dāng)Sil(xi)近似于-1時(shí)，表明樣本xi被錯(cuò)到類簇Ci中。因此，Silhouette指標(biāo)既能反應(yīng)出目標(biāo)樣本跟其所屬簇內(nèi)樣本的相似程度，也能反應(yīng)出目標(biāo)樣本跟其他簇中樣本的不相似程度。同樣的對(duì)于樣本任何的一次劃分，如果求出該劃分結(jié)果中所有樣本的Silhouette平均值，就能夠了解到該劃分的優(yōu)劣。全部樣本的Silhouette平均值定義如下：

式中，n表示樣本數(shù)量。Silhouette平均值越大表示聚類結(jié)果質(zhì)量越好，其最大值所對(duì)應(yīng)的類數(shù)就是期望的最佳聚類數(shù)。結(jié)合調(diào)研資料和相關(guān)實(shí)驗(yàn)分析，認(rèn)為Silhouette指標(biāo)作為K-均值算法聚類結(jié)果評(píng)價(jià)指標(biāo)是合適的。

4.2 基于密度期望和有效性指標(biāo)函數(shù)的K-均值優(yōu)化算法

基于密度期望和有效性指標(biāo)函數(shù)的k值優(yōu)化算法的基本思想是：首先確定最佳聚類數(shù)k的搜索范圍[kmin,kmax]，根據(jù)不同的k值，首先通過基于密度期望原則選取k個(gè)初始聚類中心點(diǎn)；其次使用傳統(tǒng)的K-均值聚類算法聚類；計(jì)算每次聚類的有效性指標(biāo)——Silhouette指標(biāo)值；最后分析聚類結(jié)果，根據(jù)最大Silhouette平均值確定最優(yōu)聚類數(shù)。容易分析得出基于密度期望和有效性指標(biāo)函數(shù)的k值優(yōu)化算法的復(fù)雜度為O(n2)。該算法的描述如下：

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

本文實(shí)驗(yàn)分為兩部分，第一部分將傳統(tǒng)K-均值算法與基于密度期望的改進(jìn)K-均值算法進(jìn)行比較，所采用的測(cè)試數(shù)據(jù)集是UCI中的Iris、Glass、Wine、Balance-scale 4組數(shù)據(jù)。第二部分是在基于密度期望的改進(jìn)K-均值算法的基礎(chǔ)上，采用聚類有效性Silhouette指標(biāo)確定最佳聚類數(shù)的實(shí)驗(yàn)，所采用的人工數(shù)據(jù)集DataSet1，DataSet2。數(shù)據(jù)集描述如表1所示。

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

5.1 基于密度期望改進(jìn)K-均值算法實(shí)驗(yàn)與分析

實(shí)驗(yàn)分別從類間距、類內(nèi)距、正確率和迭代次數(shù)四個(gè)方面對(duì)比了改進(jìn)的K-均值算法和傳統(tǒng)的K-均值算法，并給出分析結(jié)果。將基于密度期望的改進(jìn)K-均值算法中數(shù)據(jù)對(duì)象的密度期望系數(shù)鎖定在0.7至0.9之間，即γmin=0.7，γmax=0.9；設(shè)定Iris數(shù)據(jù)集半徑調(diào)節(jié)系數(shù)θ=0.4，Wine數(shù)據(jù)集半徑調(diào)節(jié)系數(shù)θ=0.7，其余兩個(gè)數(shù)據(jù)集的半徑調(diào)節(jié)系數(shù)θ= 1；進(jìn)行聚類分析并記錄聚類結(jié)果。此外，運(yùn)用傳統(tǒng)K-均值算法對(duì)上述數(shù)據(jù)集進(jìn)行10次獨(dú)立聚類實(shí)驗(yàn)，記錄每次實(shí)驗(yàn)結(jié)果，并求其結(jié)果的平均值與基于密度期望的改進(jìn)K-均值算法所獲得的結(jié)果進(jìn)行比較。實(shí)驗(yàn)結(jié)果對(duì)比分析如表2所示。

表2 新舊算法聚類性能實(shí)驗(yàn)對(duì)比

由本實(shí)驗(yàn)所得的結(jié)果可以看出，基于密度期望的改進(jìn)K-均值算法的各項(xiàng)聚類評(píng)價(jià)指標(biāo)均優(yōu)于傳統(tǒng)K-均值聚類算法。其中基于密度期望的改進(jìn)K-均值算法的實(shí)驗(yàn)結(jié)果中類間距相對(duì)更大，類內(nèi)距相對(duì)更小，實(shí)驗(yàn)結(jié)果的正確率要高于傳統(tǒng)K-均值算法，而迭代次數(shù)也有所減少。這是因?yàn)榛诿芏绕谕母倪M(jìn)K-均值算法所選取的初始聚類中心點(diǎn)更加穩(wěn)定，其選取結(jié)果基本符合數(shù)據(jù)的實(shí)際分布情況，從而幫助算法更加高效、快速地向最優(yōu)逼近，最終提高了其聚類性能。

5.2 最佳聚類數(shù)確定的實(shí)驗(yàn)與分析

在基于密度期望的改進(jìn)K-均值算法的基礎(chǔ)上，采用聚類有效性Silhouette指標(biāo)確定最佳聚類數(shù)，并將實(shí)驗(yàn)結(jié)果與隨機(jī)確定初始聚類中心點(diǎn)的計(jì)算結(jié)果對(duì)比，考察兩種不同方法對(duì)Silhouette指標(biāo)的影響。實(shí)驗(yàn)采用人工生成的數(shù)據(jù)集DataSet1、DataSet2。此外，本實(shí)驗(yàn)還給出了兩種初始中心點(diǎn)選取方法下聚類結(jié)果的直觀對(duì)比。

根據(jù)樣本數(shù)據(jù)總量確定DataSet1的聚類數(shù)搜索范圍為[2，48]；DataSet2的聚類數(shù)搜索范圍為[2，62]。將基于密度期望的改進(jìn)K-均值算法分別應(yīng)用于數(shù)據(jù)集DataSet1、DataSet2中，其類數(shù)與Silhouette指標(biāo)的關(guān)系如圖4、圖5所示。將隨機(jī)確定初始聚類中心點(diǎn)的方法分別應(yīng)用于數(shù)據(jù)集DataSet1，DataSet2中，其類數(shù)與Silhouette指標(biāo)的關(guān)系圖如圖6、圖7所示。表3給出了上述兩種初始聚類中心選取方法下的最佳聚類數(shù)實(shí)驗(yàn)結(jié)果。結(jié)合表3分析可得：圖4中數(shù)據(jù)集DataSet1最佳聚類數(shù)為3，其對(duì)應(yīng)的Silhouette指標(biāo)為0.792 8；在圖5中，數(shù)據(jù)集DataSet2最佳聚類數(shù)為4，其對(duì)應(yīng)的Silhouette指標(biāo)取到最大的0.755 7?？梢缘贸龈倪M(jìn)后的算法，依據(jù)Silhouette指標(biāo)可以得到準(zhǔn)確的聚類數(shù)目。然而圖6中數(shù)據(jù)集DataSet1在隨機(jī)初始中心點(diǎn)選取方法下，其最佳聚類數(shù)為4，其對(duì)應(yīng)的Silhouette指標(biāo)為0.780 1；圖7中，數(shù)據(jù)集DataSet2的最佳聚類數(shù)為5，其對(duì)應(yīng)的Silhouette指標(biāo)取為0.677 9。均未得到正確的聚類數(shù)目。

圖4 基于密度期望的改進(jìn)K-均值算法下DataSet1聚類數(shù)-Silhouette指標(biāo)關(guān)系圖

圖6 基于傳統(tǒng)K-均值算法下DataSet1聚類數(shù)-Silhouette指標(biāo)關(guān)系圖

圖5 基于密度期望的改進(jìn)K-均值算法下DataSet2聚類數(shù)-Silhouette指標(biāo)關(guān)系圖

圖7 基于傳統(tǒng)K-均值算法下DataSet2聚類數(shù)-Silhouette指標(biāo)關(guān)系圖

表3 基于不同初始中心點(diǎn)選取方法得到的最佳聚類數(shù)

此外，采用基于密度期望的初始中心點(diǎn)選取方法，所得到的兩個(gè)人工數(shù)據(jù)集的聚類效果分別如圖8，圖9所示。結(jié)果表明采用基于密度期望的改進(jìn)K-均值算法能得到最佳聚類效果。表4給出了兩種方法下的聚類準(zhǔn)確率和迭代次數(shù)?？梢钥闯鲈趯?duì)于類內(nèi)緊湊，類間遠(yuǎn)離的聚類結(jié)構(gòu)時(shí)，基于密度期望的K-均值改進(jìn)算法得到的聚類結(jié)果是唯一確定且正確合理的。而采用隨機(jī)方法確定初始聚類中心點(diǎn)得到的聚類效果往往欠佳。

圖8 數(shù)據(jù)集DataSet1的聚類效果圖

圖9 數(shù)據(jù)集DataSet2的聚類效果圖

表4 基于不同初始中心點(diǎn)選取方法得到的聚類準(zhǔn)確率和迭代次數(shù)

實(shí)驗(yàn)結(jié)果表明：基于密度期望的初始中心點(diǎn)的選取方法結(jié)合聚類有效性指標(biāo)Silhouette指標(biāo)能夠得到正確的最佳聚類數(shù)。而基于隨機(jī)初始中心點(diǎn)選取方法則很難得到正確的最佳聚類數(shù)。

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

傳統(tǒng)K-均值聚類算法在聚類數(shù)目k已知的情況下，通過隨機(jī)選取k個(gè)樣本作為初始聚類中心，聚類結(jié)果受初始聚類中心影響較大，容易陷入局部最優(yōu)。提出將樣本對(duì)象的密度鎖定在一個(gè)合理的期望范圍內(nèi)，從中選取k個(gè)相距最遠(yuǎn)的對(duì)象作為初始中心點(diǎn)。能有效地降低初始中心點(diǎn)的敏感性。實(shí)驗(yàn)表明，基于密度期望的初始中心點(diǎn)的選取方法能獲得較為穩(wěn)定且高質(zhì)量的聚類效果。此外，結(jié)合本文提出的基于密度期望的初始中心點(diǎn)選取方法，通過聚類有效性Silhouette指標(biāo)分析聚類結(jié)果，從而確定最佳聚類數(shù)，可有效改善K值無法預(yù)先確定的缺點(diǎn)。實(shí)驗(yàn)分析結(jié)果驗(yàn)證了所提出方案的可行性。該方案及實(shí)驗(yàn)結(jié)果對(duì)K-均值聚類算法的進(jìn)一步研究，具有一定的理論和實(shí)踐參考價(jià)值。

[1]張志兵.空間數(shù)據(jù)挖掘及其相關(guān)問題研究[M].武漢：華中科技大學(xué)出版社，2011：20-21.

[2]Guha S，Rastogir，Shmk.Cure：an efficient clustering algorithm for large databases[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.New York：ACM Press，1998：73-84.

[3]Mac Q J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability.USA：University of California Press，1967：281-297.

[4]Ester M，Hans P K，Sander J，et a1.A density based algorithm for discovering clusters in large spatial databases with noise[C]// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining（KDD-96），Portland，1996：226-231.

[5]Wang W，Yang J，Muntz R.Sting：a statistical information grid approach to spatial data mining[C]//Proceedings of the 23rd IEEE International Conference on Very Large Data Bases，Athens，1997：186-195.

[6]Kohonen T.Self organized formation of topologically correct feature maps[J].Biological Cybernetics，1982，43（1）：59-69.

[7]Likas A，Ulassis M，Uerbeek J.The global k-means clustering algorithm[J].Pattern Recognition，2003，36（2）：451-461.

[8]劉一鳴，張化祥.可變閾值的K-means初始中心選擇方法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（32）：56-58.

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

[10]任江濤，施瀟瀟，孫靖昊，等.一種改進(jìn)的基于特征賦權(quán)的K均值聚類算法[J].計(jì)算機(jī)科學(xué)，2006，33（7）：186-187.

[11]徐家寧，張立文，徐素莉，等.改進(jìn)遺傳算法的K-均值聚類算法研究[J].微計(jì)算機(jī)應(yīng)用，2010，31（4）：11-15.

[12]畢曉君，宮汝江.一種結(jié)合人工蜂群和K的值的混合聚類算法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（6）：2040-2046.

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

[14]汪中，劉貴全，陳恩紅.一種優(yōu)化初始中心點(diǎn)的K-means算法[J].模式識(shí)別與人工智能，2009，22（2）：299-304.

[15]張中平，王愛杰，柴旭光.簡(jiǎn)單有效的確定聚類數(shù)目算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（15）：166-168.

[16]Thalamuthu A，Mukhopadhyay I，Zheng X，et al.Evaluation and comparison of gene clustering methods in microarray analysis[J].Bioinformatics，2006，22（19）：2405-2412.

[17]Dudoit S，F(xiàn)ridlyand J.A prediction-based resampling method for estimating the number of clusters in a dataset[J].Genome Biology，2002，3（7）：1-21.

[18]Kapp A V，Tibshirani R.Are clusters found in one dataset present in another dataset?[J].Biostatistics，2007，8（1）：9-31.

[19]Halkidi M，Batistakis Y，Vazirgiannis M.On clustering validation techniques[J].Journal of Intelligent Information Systems，2001，17（2）：107-145.

[20]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報(bào)，2008，19（1）：48-61.

[21]周世兵，徐振源，唐旭清.新的K-均值算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（16）：27-31.

[22]Frcy B J，Dueck D.Clustering by passing message between data points[J].Science，2007，315（5814）：972-976.

[23]于劍，程乾生.模糊聚類方法中的最佳聚類數(shù)的搜索范圍[J].中國(guó)科學(xué)：E輯，2002，32（2）：274-280.

HE Yunbin,XIAO Yupeng,WAN Jing,LI Song

School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China

The traditionalK-means clustering algorithm must be given in advance the number of clustersk,but in the actual cases,kis difficult to establish;in addition,traditionalK-means clustering algorithm is sensitive to initialization and easily falls into local optimum.In view of this,this paper presents an improvedK-means algorithm based on expectation of density and Silhouette validity index.The algorithm chooses the furthest mutual distanceksample objects as the initial centers,which belong to the expectation of density region.The experimental result shows that the improvedK-means algorithm has not only the weak dependence on initial data,but also fast convergence and high clustering quality.Meanwhile,the new algorithm can automatically analyze the clustering quality in differentkvalues and determine the optimal number of clusters by selecting the Silhouette validity index.The experiment and analysis demonstrate the feasibility and effectiveness of the proposed algorithm.

K-means clustering;initial clustering centers;expectation of density;optimization ofk

傳統(tǒng)K-均值聚類算法雖然收斂速度快，但存在聚類數(shù)k無法預(yù)先確定，并且算法對(duì)初始中心點(diǎn)敏感的缺點(diǎn)。針對(duì)上述缺點(diǎn)，提出了基于密度期望和聚類有效性Silhouette指標(biāo)的K-均值優(yōu)化算法。給出了基于密度期望的初始中心點(diǎn)選取方案，將處于密度期望區(qū)間內(nèi)相距最遠(yuǎn)的k個(gè)樣本作為初始聚類中心。該方案可有效降低K-均值算法對(duì)初始中心點(diǎn)的依賴，從而獲得較高的聚類質(zhì)量。在此基礎(chǔ)上，可進(jìn)一步通過選擇合適的聚類有效性指標(biāo)Silhouette指標(biāo)分析不同k值下的每次聚類結(jié)果，確定最佳聚類數(shù)，則可有效改善k值無法預(yù)先確定的缺點(diǎn)。實(shí)驗(yàn)及分析結(jié)果驗(yàn)證了所提出方案的可行性和有效性。

K-均值聚類；初始聚類中心點(diǎn)；期望密度；k值優(yōu)化

A

TP18

10.3778/j.issn.1002-8331.1307-0079

HE Yunbin,XIAO Yupeng,WAN Jing,et al.Improved K-means algorithm based on expectation of density and clustering validity index.Computer Engineering and Applications,2013,49（24）：105-111.

黑龍江省自然科學(xué)基金（No.F201134）；黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目（No.12531120）。

何云斌（1972—），男，博士，教授，研究生導(dǎo)師，主要研究方向：數(shù)據(jù)庫(kù)理論與應(yīng)用、時(shí)空數(shù)據(jù)庫(kù)、嵌入式系統(tǒng)；肖宇鵬（1986－），男，碩士研究生，主要研究方向：空間數(shù)據(jù)挖掘；萬靜（1972—），女，博士，教授，碩導(dǎo)，主要研究方向：數(shù)據(jù)庫(kù)理論及應(yīng)用；李松（1977—），男，博士，副教授，主要研究方向：空間數(shù)據(jù)庫(kù)理論及應(yīng)用。E-mail：hybha@163.com

2013-07-08

2013-08-27

1002-8331（2013）24-0105-07

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.002.html