一種改進的K-Means算法

韓存鴿，劉長勇

(1.武夷學(xué)院數(shù)學(xué)與計算機學(xué)院，福建 武夷山 354300；2.認知計算與智能信息處理福建省高校重點實驗室，福建 武夷山 354300)

數(shù)據(jù)挖掘是一個年輕而充滿生機的領(lǐng)域，常用的數(shù)據(jù)挖掘技術(shù)有決策樹、聚類挖掘、神經(jīng)網(wǎng)絡(luò)、規(guī)則歸納、遺傳算法、統(tǒng)計學(xué)習(xí)、聯(lián)機分析處理等，其中聚類挖掘在數(shù)據(jù)挖掘研究領(lǐng)域中扮演著非常重要的角色，是一種無監(jiān)督的機器學(xué)習(xí)算法。K-Means 算法是J.B.MacQueen在1967年提出的一種聚類挖掘算法，同時也是一種經(jīng)典的基于劃分的聚類分析方法，該算法將一個給定的樣本數(shù)據(jù)集劃分為由若干相似實例組成的簇的過程，聚類結(jié)果使得同一個簇內(nèi)的相似度高，而不同簇之間的相似度最小化[1]。

雖然K-Means算法已經(jīng)得到廣泛的應(yīng)用，但該算法本身也有一些不足，從而吸引了許多研究人員對其進行改進，相繼衍生出了許多改進的K-Means 算法。文獻[2]提出一種用多層受限玻爾茲曼機(RBM)對數(shù)據(jù)進行特征學(xué)習(xí)，采用深度信念網(wǎng)絡(luò)(DBN)對相關(guān)參數(shù)和初始聚類中心進行交叉迭代優(yōu)化算法。文獻[3]提出一種關(guān)系矩陣和度中心性相結(jié)合的分析方法的來確定K-Means算法中的k個中心點。文獻[4]提出一種基于K-Means分層迭代的檢測算法，通過多次屬性消減的K-Means聚類迭代操作來檢測到不同異常類型的攻擊。文獻[5]提出了一種改進的自適應(yīng)雙層變量加權(quán)K-Means算法，該算法根據(jù)數(shù)據(jù)集的特點自動聚成合適的K個簇。本文提出一種基于最大最小距離和BWP指標(biāo)相結(jié)合的K-Means算法，為了驗證改進算法的性能，本次實驗對UCI數(shù)據(jù)庫中的4個數(shù)據(jù)集進行仿真測試，根據(jù)實驗結(jié)果，改進后的算法在準(zhǔn)確率、聚類效果兩方面有一定的優(yōu)勢。

1 K-Means算法理論

K-Means算法對數(shù)據(jù)進行聚類的過程為：首先將數(shù)據(jù)集隨機的分為k類，分成的這k個類中包含若干對象，計算每個類簇的中心。接著對剩余的每個對象，根據(jù)簇均值的距離按照就近原則分派給最近的簇；最后繼續(xù)計算每個簇的新均值。直到準(zhǔn)則函數(shù)收斂，否則該過程將會一直重復(fù)執(zhí)行，通常，采用平方誤差準(zhǔn)則，其定義如下[6]：

(1)

其中，p表示數(shù)據(jù)對象；mi是簇ci的平均值。

K-Means算法的流程如下：

輸入：聚類數(shù)目k和數(shù)據(jù)集D={d1,d2,…,dn}

輸出：k個類簇，滿足平方誤差準(zhǔn)則函數(shù)收斂

1)從數(shù)據(jù)集D中任意選擇k個數(shù)據(jù)對象作為初始簇中心；

2)repeat；

3)根據(jù)簇中對象的均值，將每個對象賦給最相似的簇；

4)更新簇均值，即計算每個簇中對象的平均值；

5)計算聚類準(zhǔn)則函數(shù)；

6)直到準(zhǔn)則函數(shù)值不再進行變化，算法結(jié)束。

K-Means算法缺點[7]：

1)需要預(yù)先指定聚類數(shù)目k值，而現(xiàn)實生活中，用戶在對數(shù)據(jù)集進行聚類的時候剛開始并不知道應(yīng)該分幾類合適，也就是說這個聚類數(shù)目k值不好估計。

2)質(zhì)心不確定，需要對質(zhì)心多次循環(huán)才能達到收斂，從而使K-Means算法陷入局部最小解，無法做到全局最優(yōu)解。

3) 初始簇中心不同使得的聚類結(jié)果可能不同。

2 改進算法的理論依據(jù)及改進后的算法

針對K-Means算法需要預(yù)先指定類簇的值、質(zhì)心選擇不確定、初始簇中心的選擇敏感等不足，本文提出一種基于最大最小距離結(jié)合BWP指標(biāo)的UPK-Means聚類算法。

2.1 最大最小距離算法思想

最大最小距離算法核心為：取盡可能遠的對象作為聚類中心,是一種以歐氏距離為基礎(chǔ)的聚類算法。該算法最直觀的優(yōu)勢是可以避免K-Means算法的聚類種子過于臨近問題，它不但能夠智能地確定初始聚類種子的個數(shù)，而且還能提高劃分初始數(shù)據(jù)集的效率。

最大最小距離算法的主要流程[8]如下：

1)從數(shù)據(jù)集X={X1,X2,X3,…,Xn}中任取一個樣本作為第1個聚類中心，如取C1=X1;

2)計算其他所有樣本到C1的距離Di1，若Dk1=max{Di1}，則取C2=xk;Di1=‖xi-C1‖=

3)分別計算D中剩余的樣本到C2的距離Di2，假設(shè)Di=max{min(Di1,Di2)}，i=1,2,3,…,n,若Di>θ·D12(C1到C2距離)，則取xi為第3個聚類中心，記作C3=xi;

4)如果C3存在則計算Dj=max{min(Di1，Di2，Di3)}，j=1,2,3,…,n,若Dj>θ·D12(C1到C2距離) 則取xj為第4個聚類中心，記作C4=xj以此類推，直到最大最小距離不大于D12時，尋找聚類中心的計算結(jié)束；

5)對所有樣本按照就近原則劃分給距離最近的聚類中心，然后根據(jù)某聚類準(zhǔn)則考查聚類結(jié)果，若不滿意，則重新選擇C1與θ，重新進行相關(guān)距離計算，直到滿意算法結(jié)束。

2.2 最大最小距離算法應(yīng)用舉例

假設(shè)有7個模式樣本點{X1,X2,X3,X4,X5,X6,X7}，對樣本進行聚類分析，7個二維樣本為：X1=(0,0)，X2=(1,3)，X3=(2,2)，X4=(6,7)，X5=(0,1)，X6=(5,6)，X7=(8,1)

1)任取一個樣本點作為第一個聚類中心,這里取C1=X1=(0,0)，分別計算所有樣本到C1的距離,為了更直觀地顯示計算過程，計算結(jié)果如表1所示。

表1 樣本到C1的距離

4)根據(jù)計算結(jié)果，本例只有C1、C2、C3這3個聚類中心，分別為按照最近原則把所有樣本劃分給距離最近的聚類中心。{X1,X2,X3,X5}∈C1，{X4,X6}∈C2，{X7}∈C3，該聚類結(jié)果與傳統(tǒng)的K-Means算法的聚類結(jié)果完全一致，傳統(tǒng)K-Means算法的聚類過程這里不做贅述。

2.3 BWP 指標(biāo)函數(shù)

目前經(jīng)常被人們使用的檢驗聚類有效性的指標(biāo)有XB指標(biāo) (Xie-Beni) 、KL指標(biāo) (Krzanowski-Lai) 、Sil指標(biāo) (Silhouette) 、DB指標(biāo) (Davies-Bouldin)、IGP指標(biāo) (In-Group Proportion)、BWP指標(biāo) (Between-Within Proportion) 等。其中BWP 是一種有效的聚類指標(biāo)，該指標(biāo)依據(jù)簇內(nèi)相似與簇間相異兩方面來評判聚類結(jié)果。如果X={X1,X2,…,Xn}為聚類數(shù)據(jù)集，k= (X,R) 為聚類空間, 如果數(shù)據(jù)集中的n個樣本分為c類，則最小類間距離、類內(nèi)距離，BWP指標(biāo)判別函數(shù)公式如下[9]。

最小類間距離：

(2)

類內(nèi)距離：

(3)

BWP指標(biāo)：

(4)

其中BWP指標(biāo)值越高，聚類性能越好,BWP指標(biāo)確定k值。

對于單個樣本來說，若BWP指標(biāo)值越高，則意味著聚類性能就越好。那么對所有樣本來說，要取BWP的平均值來觀察聚類性能，BWP平均值越高，數(shù)據(jù)集的聚類性能就會越好[10]。其中avgBWP(k)為所有樣本的BWP平均值，kopt為聚類數(shù)，計算公式如下：

(5)

(6)

2.4 基于最大最小距離和BWP指標(biāo)優(yōu)化的K-Means算法改進

本文提出一種基于最大最小距離和BWP指標(biāo)相結(jié)合的K-Means算法，以下命名為UPK-Means，改進后算法的基本思想如下:假如數(shù)據(jù)集X={X1,X2,X3,…,Xn}可分為K類，K數(shù)目未知。首先在X中找出距離最遠的兩個樣本點C1、C2，結(jié)合給定的θ值，根據(jù)最大最小距離原則確定余下的K-2個聚類中心，然后把樣本點分配給距離最近的聚類中心，當(dāng)數(shù)據(jù)集中的每個樣本點都有確定的一個類別時，聚類結(jié)束。參數(shù)值θ不同，聚類效果也會有所不同，最后利用avgBWP(k)評價聚類性能，avgBWP(k)值越高，聚類性能越好。

UPK-Means算法流程：

input：數(shù)據(jù)集X={X1,X2,X3,…,Xn}

output：聚類結(jié)果

Step 1：從X中找出距離最遠的兩個樣本點，分別記作C1、C2；

Step 2：計算數(shù)據(jù)集X中每個樣本點到C1、C2的距離Di1、Di2，Di=max{min(Di1，Di2)} ，i=1, 2,…,n。若D1>θ·D12(C1到C2距離) , 則取xi為第三個聚類中心，記作C3=xi；

Step 3：如果C3存在，繼續(xù)計算Dj=max{min (Di1，Di2，Di3)}，j=1,2,3,…,n,若Dj>θ·D12(C1到C2距離) 則取xj為第4個聚類中心，記作C4=xj，以此類推，直到最大最小距離不大于D12時，尋找聚類中心的計算結(jié)束；如果C3不存在，執(zhí)行Step 4；

Step 4:按照最近原則把所有樣本劃分給距離最近的聚類中心，從而得到C1,C2,…,Ci個聚類；

Step 5:根據(jù)聚類結(jié)果，計算每個樣本點的BWP值, 然后將BWP值按照從大到小的順序排列, 選擇前96 %的指標(biāo)值求平均值avgBWP(k)；

在參數(shù)θ值的選擇上，本文采用等寬分箱思想，將區(qū)間[0,1]分成n個區(qū)間[0, 1/n]，[1/n, 2/n],[2/n, 3/n],…,[n-1/n,1] ,在每個區(qū)間找一個點作為θ值，利用此處得到的n個θ值，然后聚類數(shù)據(jù)集，使BWP值較小的θ值的區(qū)間去掉，將余下的區(qū)間繼續(xù)分成若干區(qū)間，直到區(qū)間的長度小于規(guī)定的值時，迭代過程結(jié)束。

3 實驗仿真及結(jié)果分析

表2 測試數(shù)據(jù)集基本信息

為了驗證本文提出算法的性能，本實驗選擇UCI數(shù)據(jù)庫中Wine、Iris、Glass、Zoo 4個數(shù)據(jù)集作為測試數(shù)據(jù)，實驗數(shù)據(jù)的基本信息見表2，采用Java 語言在WEKA平臺中進行仿真實驗。

仿真實驗時，首先利用最大最小距離找出最遠的兩個樣本點作為聚類中心，繼而計算數(shù)據(jù)集中每個樣本點到C1、C2的距離，若D1>θ·D12(C1到C2距離)，則取Xi為第三個聚類中心，記作C3=Xi，依次類推，直到最大最小距離不大于D12時，尋找聚類中心的算法結(jié)束，最后按照最近原則對樣本進行劃分，每個樣本都保證分給距離最近的聚類中心，根據(jù)得到的聚類結(jié)果，計算每個樣本點的BWP值, 然后將BWP值按照從大到小的順序排列, 對前96%的指標(biāo)值求平均值avgBWP(k)。

圖1 Wine 數(shù)據(jù)的正確率Fig.1 Correct rate of Wine data

由圖1可以看出，對于Wine數(shù)據(jù)集，使用傳統(tǒng)的K-Means聚類結(jié)果的正確率相對較低，而采用本文提出的UPK-Means算法后，聚類的正確率得到明顯提升。而基于最大最小距離的K-Means算法的正確率處于K-Means算法和UPK-Means算法之間。

為了驗證UPK-Means算法的效率，對于其他3組數(shù)據(jù)集，同樣都分別使用K-Means算法、基于最大最小距離的K-Means算法，以及本文提出的UPK-Means進行仿真實驗，每個數(shù)據(jù)集都測試5次，聚類結(jié)果的具體信息如表3所示。表中信息為5次測試的平均值。

從表3結(jié)果可以看出, 對于Wine、Irish、Glass、以及Zoo數(shù)據(jù)集傳統(tǒng)K-Means算法收斂時間短, 但標(biāo)準(zhǔn)差較大，聚類效果不好, 聚類結(jié)果的正確率也較低, 而且傳統(tǒng)K-Means算法需要預(yù)先指定聚類數(shù)目的值。

表3 測試數(shù)據(jù)集的聚類結(jié)果

相比K-Means算法、基于最大最小距離的K-Means算法，本文提出的UPK-Means算法從聚類效果的正確率，標(biāo)準(zhǔn)差兩方面獲得了較好的聚類結(jié)果。

4 總結(jié)

傳統(tǒng)K-Means算法具有算法簡單、容易理解、收斂速度快等優(yōu)點，但使用該算法聚類分析時需要指定聚類數(shù)目，而且質(zhì)心的選擇具有不確定性。本文提出一種基于最大最小距離和BWP指標(biāo)優(yōu)化的K-Means算法，通過對UCI數(shù)據(jù)庫中的Wine、Iris、Glass、Zoo 4個數(shù)據(jù)集進行仿真實驗，本文提出的UPK-Means算法在算法的準(zhǔn)確率、聚類效果兩方面均優(yōu)于傳統(tǒng)的K-Means算法以及基于最大最小距離的K-Means算法。