一種改進(jìn)的K-means算法

尹寶勇， 吳斌， 劉建生

（江西理工大學(xué)理學(xué)院，江西 贛州341000）

0 引 言

伴隨著數(shù)字化時(shí)代的高速發(fā)展，數(shù)據(jù)挖掘技術(shù)已成為當(dāng)前研究的熱點(diǎn)之一.而聚類分析作為現(xiàn)今數(shù)據(jù)挖掘中最為流行的一種技術(shù)，已被廣泛的應(yīng)用于圖像分割[1]、模式識(shí)別[2]、病毒入侵檢測等領(lǐng)域中[3].根據(jù)不同領(lǐng)域的應(yīng)用，人們研究出了不同的聚類算法，其中主要分為基于網(wǎng)格、基于密度、基于層次以及基于劃分的聚類算法.其中以基于劃分的聚類算法更為被人們所常用.而K-means作為基于劃分的算法中最經(jīng)典的一個(gè)聚類算法，被廣泛的應(yīng)用于各領(lǐng)域中[4-6].并且K-means算法因其高效的執(zhí)行效率[7]，備受研究人員的青睞.然而該算法也存在如下的缺點(diǎn)[8]：①傳統(tǒng)K-means算法需事先預(yù)知聚類中心的數(shù)目；②傳統(tǒng)K-means算法采用歐式距離作為樣本劃分的準(zhǔn)則，僅能體現(xiàn)對象間的相似性，樣本對象間相關(guān)性不能得到很好體現(xiàn).為克服傳統(tǒng)K-means算法聚類中心數(shù)目難以確定的問題，大量改進(jìn)的K-means算法已被提出.Jing等[9]重新定義內(nèi)類距離與內(nèi)間距離的關(guān)系來提高自動(dòng)劃分聚類中心數(shù)目的準(zhǔn)確度.文獻(xiàn)[10]及文獻(xiàn)[11]中主要采用了BWP指標(biāo)對聚類效果進(jìn)行評價(jià).謝娟英等[12]提出了一種新的統(tǒng)計(jì)計(jì)量指標(biāo)Fr，通過采用該指標(biāo)對類別數(shù)目的優(yōu)劣進(jìn)行評價(jià).

除了以上幾種改進(jìn)算法以外，K-means算法也常與其他智能算法相結(jié)合使用[13-14].文中在分析已有改進(jìn)算法的基礎(chǔ)上，提出一種改進(jìn)的K-means算法用于實(shí)現(xiàn)聚類中心數(shù)目的確定以及增強(qiáng)樣本對象間的相關(guān)性.

1 K-means算法回顧

K-means算法是一種采用交替最小化方法求解非凸優(yōu)化問題的算法.它是將一個(gè)給定的數(shù)據(jù)集劃分為用戶指定的k個(gè)聚簇，有著較高的執(zhí)行效率.在歷史上，有著許多不同領(lǐng)域的研究人員都對基本的K-means算法進(jìn)行了研究，其中比較知名的有 Forgey（1965），McQueen（1967）等[15].Jain 與Dubes詳細(xì)的描述了K-means算法的發(fā)展歷史和多種變體.其算法步驟如下[16].

算法輸入：數(shù)據(jù)集X，聚類數(shù)k

算法輸出：聚類代表集合C

Step1：從整個(gè)數(shù)據(jù)集X中，隨機(jī)任意選取k個(gè)樣本對象作為初始簇中心；

Step2：計(jì)算數(shù)據(jù)集中每個(gè)樣本對象xm到簇中心ci的距離；

Step3：找到每個(gè)樣本對象xm到簇中心ci的最小距離，并將該樣本對象xm歸為與ci相同的簇中；

Step4：計(jì)算同一簇中對象的均值，更新簇中心；

Step5：重復(fù) Step2～Step4，直到簇中心不再發(fā)生改變.

K-means算法具有簡單、易于實(shí)現(xiàn)等優(yōu)點(diǎn)，但同時(shí)K-means算法確定聚類數(shù)目是困難的.圖1顯示相同數(shù)據(jù)集在不同聚類中心數(shù)下的實(shí)驗(yàn)結(jié)果，從圖1中可看到準(zhǔn)確的聚類數(shù)對于聚類準(zhǔn)確率的影響是非常大的.

2 CS-kmeans算法

在分析已有改進(jìn)K-means算法的基礎(chǔ)上，本文針對傳統(tǒng)K-means算法中不能自動(dòng)確定聚類數(shù)目、對象間相關(guān)性難以體現(xiàn)的缺點(diǎn)，提出了一種改進(jìn)的CS-kmeans算法.CS-kmeans算法的改進(jìn)有：①樣本間距離的計(jì)算過程中引入了樣本相關(guān)性，為歐式距離添加相關(guān)性縮放因子；②將最大類內(nèi)距離與最小類間距離作為樣本劃分或合并的標(biāo)準(zhǔn).具有相關(guān)性縮放因子的距離定義如下：

圖1 同聚類中心數(shù)k時(shí)的聚類結(jié)果

其中，d（xi，xj）表示 xi和 xj的歐式距離，cor（xi，xj）表示 xi與 xj的皮爾遜相關(guān)系數(shù)，Max_cor，Min_cor分別表示樣本對象間皮爾遜相關(guān)系數(shù)的最大與最小值，g（xi，xj）表示歸一化后的相關(guān)系數(shù)，0.001 為了防止 g（xi，xj）為 1 時(shí)樣本間距離為 0.

最小類間距離：

最大類內(nèi)距離：

其中，xi是以cj為聚類中心的對象.

平均類間距離：

其中，k為聚類數(shù)，ci和cj代表簇中心.

因?yàn)樽钚☆愰g距離小于等于平均類間距離，最小類間距離越大，類與類之間的差異性越明顯，則聚類效果越好，所以選用當(dāng)前劃分的平均類間距離來近似理想劃分的最小類間距離，即.最大類內(nèi)距離越小，類中對象相似性越強(qiáng)，聚類效果越好，因此理想劃分下的最大類內(nèi)距離不妨為 0，即=0.

另一方面，在聚類過程中，隨著類別數(shù)的增多，類與類之間將變得越來越密集，假設(shè)此時(shí)對于相鄰的兩類之間邊界樣本間距趨近于0時(shí).此時(shí)存在a3+a4≥a5，其中 a3、a4為內(nèi)類距離，a5為類間距離.而聚類過程中，最大的內(nèi)類距離應(yīng)盡可能小，既相鄰兩類間內(nèi)類距離之差應(yīng)盡可能小，不妨建立a3=a4=0.5×a5，可得 Inter=2×Intra，既 a1=2×a2.關(guān)系示意圖如圖2所示.

圖2 類內(nèi)與類間距離示意

將 a1=2×a2代入公式（5），可得：

算法輸入：包含n對對象的數(shù)據(jù)集X，X={xm|m=1，2，…，n}，初始聚類中心數(shù)目 k0，點(diǎn)密度領(lǐng)域半徑λ；

算法輸出：聚類代表集合 C，C={ci|1，2，…，k}；

Step1：初始化k=k0，按文獻(xiàn)[9]初始化方法選取k0個(gè)密度高的樣本為初始簇中心ci；

Step2：按傳統(tǒng)K-means算法流程聚類，計(jì)算平均類間距離d；

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

為驗(yàn)證文中算法的有效性及合理性.文中選用6組UCI數(shù)據(jù)集與4組人工模擬數(shù)據(jù)集在相同環(huán)境將文中算法、傳統(tǒng)K-menas算法、文獻(xiàn)[9]算法（Rt-kmeans）、文獻(xiàn)[10]算法（BWP）及文獻(xiàn)[11]算法（MST_Fr）在聚類準(zhǔn)確率、標(biāo)準(zhǔn)差、收斂時(shí)間、k值搜索上界、聚類中心數(shù)目5方面進(jìn)行對比.數(shù)據(jù)集如表1所示.

文中驗(yàn)證過程分為兩步.第一步是通過選取不同初始聚類中心數(shù)目k時(shí)，對算法確定類別數(shù)目的魯棒性及準(zhǔn)確性進(jìn)行分析，如表2所示.第二是對文中所選的五個(gè)評價(jià)指標(biāo)進(jìn)行實(shí)驗(yàn)對比，實(shí)驗(yàn)中的聚類準(zhǔn)確率，收斂時(shí)間是通過10次單獨(dú)實(shí)驗(yàn)取平均值進(jìn)行記錄，實(shí)驗(yàn)結(jié)果如表3、表4所示.

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

表2 不同k值時(shí)各數(shù)據(jù)集CS-kmeans算法下的聚類中心數(shù)

表3 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表4 人工模擬數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

由表2可知，當(dāng)選取不同的初始聚類中心數(shù)目k時(shí)，除了Yeast與Jain數(shù)據(jù)集，CS-kmeans算法對文中其它8組數(shù)據(jù)集均能獲得穩(wěn)定的聚類中心數(shù)目.雖然Yeast與Jain數(shù)據(jù)集所得結(jié)果不穩(wěn)定，但不同結(jié)果之間的差值也較小.并且對于文中所選用的大部分?jǐn)?shù)據(jù)集，最終所確定的聚類中心數(shù)目與標(biāo)準(zhǔn)聚類中心數(shù)目也比較一致.

從表3與表4可以看出，對文中所選用的10組數(shù)據(jù)集傳統(tǒng)K-means算法雖然收斂速度快，但僅少數(shù)數(shù)據(jù)集能獲得較好的聚類效果，大部分?jǐn)?shù)據(jù)集所得聚類結(jié)果均不穩(wěn)定，并且傳統(tǒng)K-means算法需要提前輸入準(zhǔn)確的聚類中心數(shù)目.文獻(xiàn) [10]算法、Rt-kmeans算法、MST_Fr算法雖然自動(dòng)對聚類中心數(shù)目進(jìn)行劃分，但文獻(xiàn)[10]算法需要較大范圍的對不同的k值進(jìn)行搜索，同時(shí)從各數(shù)據(jù)集最終所得聚類數(shù)可看出，該評價(jià)指標(biāo)僅對類別數(shù)目為3的數(shù)據(jù)集才能獲得較好的聚類效果，并收斂速度也較慢.MST_Fr算法雖然能對不同類別數(shù)的數(shù)據(jù)集進(jìn)行劃分，但是最終所得結(jié)果與標(biāo)準(zhǔn)聚類中心數(shù)目差別較大，聚類準(zhǔn)確度較低，并且該算法在計(jì)算各樣本點(diǎn)密度及更新簇中心過程中耗時(shí)較長.Rtkmeans算法雖然收斂速度也較快，但該算法對于確定聚類中心數(shù)目的準(zhǔn)確度以及聚類結(jié)果的準(zhǔn)確率仍存在明顯不足，并且從Yeast數(shù)據(jù)集的聚類結(jié)果看出，當(dāng)數(shù)據(jù)集類別數(shù)較多時(shí)，文獻(xiàn)[9]與[10]中的算法所得的最終聚類中心數(shù)的結(jié)果是較差的，雖文中算法也沒有得到標(biāo)準(zhǔn)聚類數(shù)，但分析Yeast數(shù)據(jù)集發(fā)現(xiàn)，Yeast數(shù)據(jù)集樣本分布是不均勻的，由表1得Yeast數(shù)據(jù)集后四類樣本數(shù)僅為總樣本數(shù)的7%，所以CS-kmeans算法所得結(jié)果比較可靠.

相比其它4個(gè)算法，CS-kmeans算法無論從聚類結(jié)果準(zhǔn)確率、確定聚類中心數(shù)目及收斂速度等方面都能獲得較為優(yōu)越的聚類結(jié)果.通過上述實(shí)驗(yàn)結(jié)果表明，文中算法能夠有效的提升聚類的效果.

4 結(jié) 論

文中通過使得最小類間距離及最大類內(nèi)距離與理想最小類間距離與理想最大類內(nèi)距離盡可能接近來確定聚類數(shù)目，使用類間距離與類內(nèi)距離之間的關(guān)系實(shí)現(xiàn)對樣本對象的自動(dòng)劃分與合并.并且與傳統(tǒng)的K-means算法以及其他幾種改進(jìn)的K-means算法相比較，文中提出的算法在聚類準(zhǔn)確率、穩(wěn)定性、收斂時(shí)間等方面都能得到更好效果.