韓存鴿，劉長(zhǎng)勇

(1.武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建 武夷山 354300；2.認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室，福建 武夷山 354300)

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

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

1 K-Means算法理論

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

(1)

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

K-Means算法的流程如下：

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

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

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

2)repeat；

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

4)更新簇均值，即計(jì)算每個(gè)簇中對(duì)象的平均值；

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

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

K-Means算法缺點(diǎn)[7]：

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

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

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

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

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

2.1 最大最小距離算法思想

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

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

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

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

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

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

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

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

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

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

表1 樣本到C1的距離

4)根據(jù)計(jì)算結(jié)果，本例只有C1、C2、C3這3個(gè)聚類中心，分別為按照最近原則把所有樣本劃分給距離最近的聚類中心。{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)常被人們使用的檢驗(yàn)聚類有效性的指標(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)相似與簇間相異兩方面來評(píng)判聚類結(jié)果。如果X={X1,X2,…,Xn}為聚類數(shù)據(jù)集，k= (X,R) 為聚類空間, 如果數(shù)據(jù)集中的n個(gè)樣本分為c類，則最小類間距離、類內(nèi)距離，BWP指標(biāo)判別函數(shù)公式如下[9]。

最小類間距離：

(2)

類內(nèi)距離：

(3)

BWP指標(biāo)：

(4)

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

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

(5)

(6)

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

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

UPK-Means算法流程：

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

output：聚類結(jié)果

Step 1：從X中找出距離最遠(yuǎn)的兩個(gè)樣本點(diǎn)，分別記作C1、C2；

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

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

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

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

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

3 實(shí)驗(yàn)仿真及結(jié)果分析

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

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

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

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

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

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

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

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

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

4 總結(jié)

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