王美琪 李 建

(西南石油大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 四川 成都 610500)

0 引 言

初始聚類中心對(duì)K-means聚類結(jié)果影響極大。經(jīng)典的K-means聚類算法采用隨機(jī)選取初始聚類中心的方式，有以下不足：① 易導(dǎo)致聚類結(jié)果的不穩(wěn)定；② 有取得離群點(diǎn)作為初始聚類中心的可能；③ 某些初始聚類中心可能離群體太遠(yuǎn)，有的初始聚類中心可能相互之間隔得太近。為克服這些缺點(diǎn)，文獻(xiàn)[1-3]分別采用構(gòu)造最小生成樹、最短路徑加權(quán)屬性圖、最大最小距離MMD(Max-Min Distance)算法計(jì)算K-means的初始聚類中心，獲得了一定的效果。但實(shí)驗(yàn)發(fā)現(xiàn)，在聚類簇?cái)?shù)較大時(shí)，因k值的限定，MMD算法獲得的初始聚類中心有同類多點(diǎn)而導(dǎo)致初始類的缺失，雖然K-means算法通過迭代移動(dòng)聚類中心部分最后接近實(shí)際中心，但仍有部分將陷入局部最優(yōu)。且MMD初始聚類中心往往在簇的邊界，這無形中影響了算法收斂速度。近鄰傳播算法(Affinity Propagation，AP)可根據(jù)相似參考度進(jìn)行全局尋優(yōu)，獲得多個(gè)具有代表性的聚類中心[4-5]，但由于選到同類多點(diǎn)而導(dǎo)致聚類數(shù)目一般大于實(shí)際簇?cái)?shù)，直接用AP聚類中心作為K-means初始聚類中心聚類的結(jié)果不符合實(shí)際。

本文提出一種近鄰傳播算法和最大最小距離算法聯(lián)合計(jì)算K-means初始聚類中心的算法(APMMD)。該算法首先通過近鄰傳播算法從整個(gè)樣本集中全局尋優(yōu)，獲得Kap(Kap>k)個(gè)具有代表性的候選中心點(diǎn)，再利用最大最小距離算法從Kap個(gè)候選中心點(diǎn)中選擇k個(gè)初始聚類中心。將該算法獲得的初始聚類中心應(yīng)用于K-means聚類，在多個(gè)UCI數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，通過已知分類對(duì)比，用Purity、AC、NMI、JC、RI和FMI有效性評(píng)價(jià)指標(biāo)及迭代次數(shù)驗(yàn)證。結(jié)果表明，APMMD算法獲得初始聚類中心應(yīng)用于K-means聚類，聚類結(jié)果與已知分類十分吻合，有效性評(píng)價(jià)指標(biāo)極高，迭代次數(shù)明顯降低，同時(shí)不受聚類簇?cái)?shù)的限制。

1 經(jīng)典的K-means聚類算法

K-means聚類算法是一種經(jīng)典算法，算法簡(jiǎn)單、快速，對(duì)處理大數(shù)據(jù)集，該算法保持可伸縮性和高效性。該算法的主要流程：

設(shè)X={x1,x2,…,xn}為已知數(shù)據(jù)集，X中的x1,x2,…,xn為n個(gè)數(shù)據(jù)對(duì)象，每個(gè)數(shù)據(jù)對(duì)象都是N維數(shù)據(jù)，即xi=[vi,1,vi,2,…,vi,N]，算法要找到含有k個(gè)聚類中心的集合:

C={c1,c2,…,ck}=

{[v1,1,v1,2,…,v1,N],[v2,1,v2,2,…,v2,N],…,[vk,1,vk,2,…,vk,N]}

目標(biāo)函數(shù)表示為：

(1)

式中：d(ci,xj)表示聚類中心與數(shù)據(jù)對(duì)象的歐氏距離，其計(jì)算式為：

(2)

算法把數(shù)據(jù)集劃分成使目標(biāo)函數(shù)為最小值的K個(gè)類。具體步驟為：首先利用隨機(jī)選取從數(shù)據(jù)集中抽取K個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心；然后計(jì)算剩余數(shù)據(jù)對(duì)象與各個(gè)聚類中心的歐氏距離，按照距離最小原則來劃分類別;完成一輪聚類后，再計(jì)算每一類的平均值，用K個(gè)平均值作為新的K個(gè)聚類中心，再計(jì)算剩余的數(shù)據(jù)對(duì)象與這K個(gè)聚類中心的歐氏距離，再按照距離最小原則劃分類別，循環(huán)反復(fù)，直到滿足某個(gè)終止條件停止迭代。

算法存在以下問題：

(1) 初始聚類中心隨機(jī)選取，聚類結(jié)果不穩(wěn)定。

(2) 易選到噪聲數(shù)據(jù)和孤立點(diǎn)而陷入局部極值。

(3) 當(dāng)選到不合理的初始聚類中心時(shí)，算法通過迭代移動(dòng)聚類中心部分最后接近實(shí)際中心，部分將陷入局部最優(yōu)。

2 相關(guān)算法

2.1 近鄰傳播算法

近鄰傳播算法(AP)由Frey等[6]于2007年提出。AP算法將所有樣本都看成潛在的聚類中心，在迭代過程中不斷通過節(jié)點(diǎn)之間的“信息傳遞”搜尋具有代表性的聚類中心。AP算法不設(shè)置聚類中心的個(gè)數(shù)，但需要事先設(shè)置相似度的參考度，參考度的大小決定聚類中心的個(gè)數(shù)；參考度一般設(shè)為相似度矩陣中所有值的最小值或者中位數(shù)，參考度越大則說明各數(shù)據(jù)點(diǎn)成為聚類中心的能力越強(qiáng)，最終聚類中心的個(gè)數(shù)則越多。

“信息傳遞”：將n個(gè)數(shù)據(jù)點(diǎn)之間的相似度組成相似度矩陣s(n,n)，并以對(duì)角線上的值s(i,i)作為第i個(gè)數(shù)據(jù)點(diǎn)能否成為聚類中心的評(píng)判標(biāo)準(zhǔn)。r(i,k)表示從i點(diǎn)發(fā)送到k候選聚類中心的消息，a(i,k)表示k從候選聚類中心發(fā)送到i的數(shù)值消息。r(i,k)反映點(diǎn)k是否適合作為i點(diǎn)的聚類中心，a(i,k)則反映i點(diǎn)是否選擇k作為其聚類中心，稱為吸引度和歸屬度。r(i,k)與a(i,k)越強(qiáng)，則k點(diǎn)作為聚類中心的可能性越大，并且i點(diǎn)隸屬于以k點(diǎn)為聚類中心的聚類的可能性也越大。通過迭代而不斷地更新每一個(gè)點(diǎn)的吸引度和歸屬度值，直到產(chǎn)生多個(gè)高質(zhì)量的聚類中心，同時(shí)將其余的數(shù)據(jù)點(diǎn)分配到相應(yīng)的聚類中。

算法可根據(jù)參考度獲得數(shù)據(jù)集中具有代表性的多個(gè)聚類中心，對(duì)數(shù)據(jù)的初始樣本不敏感，聚類中心不會(huì)選到離群點(diǎn)，代表性點(diǎn)不會(huì)在類的邊界，但會(huì)有同類多點(diǎn)而導(dǎo)致聚類數(shù)目往往大于實(shí)際簇?cái)?shù)現(xiàn)象。

2.2 最大最小距離算法

最大最小距離算法(MMD)是模式識(shí)別中一種基于試探的聚類算法，它以距離(歐氏)為基礎(chǔ)，取盡可能遠(yuǎn)的樣本作為聚類中心[7]。首先選擇距離最遠(yuǎn)的兩個(gè)樣本作為第一、第二個(gè)聚類中心，再選擇未被作為聚類中心的樣本與已選中心點(diǎn)之間距離最小中最大點(diǎn)作為下一個(gè)聚類中心。依此方法直到產(chǎn)生所需的k個(gè)聚類中心。

MMD算法可根據(jù)數(shù)據(jù)集簇?cái)?shù)，快速求取指定的k個(gè)聚類中心，獲得距離較遠(yuǎn)的樣本作為初始聚類中心，但可能選到離群點(diǎn)。聚類簇?cái)?shù)較大時(shí)，因k值的限定，求取的聚類中心會(huì)有同類多點(diǎn)而導(dǎo)致初始類的缺失，選擇的中心點(diǎn)一般在類的邊界，K-means算法雖然通過迭代移動(dòng)聚類中心最后接近實(shí)際中心，但是無形中影響了算法收斂速度，甚至影響聚類結(jié)果。

3 APMMD算法

3.1 基本思路

首先通過AP算法從整個(gè)樣本集中獲得Kap(Kap>k)個(gè)具有代表性的候選中心點(diǎn)，再利用最大最小距離算法從Kap個(gè)候選中心點(diǎn)中選擇k個(gè)初始聚類中心。AP對(duì)數(shù)據(jù)的初始樣本不敏感，不會(huì)選到離群點(diǎn)，也不缺失類別，代表性候選點(diǎn)不在該類的邊界，主要問題是因同類多點(diǎn)而導(dǎo)致聚類數(shù)目大于實(shí)際簇?cái)?shù)問題。MMD算法可根據(jù)數(shù)據(jù)集簇?cái)?shù)，快速求取指定的k個(gè)聚類中心，獲得距離較遠(yuǎn)的樣本作為初始聚類中心。AP候選點(diǎn)中類內(nèi)的點(diǎn)距離要小于類間點(diǎn)距離，通過MMD可去掉AP同類多出的點(diǎn)，從而獲得代表性的k個(gè)最優(yōu)聚類中心點(diǎn)。

3.2 算法解析

APMMD算法求取K-means初始聚類中心的過程如圖1所示，假設(shè)整個(gè)樣本對(duì)象點(diǎn)如圖1(a)所示(x1,x2，…，x16，共計(jì)16個(gè)樣本對(duì)象點(diǎn)，x5為異常點(diǎn))，要將樣本集劃分為3個(gè)簇(k=3)。

首先根據(jù)AP算法原理，給定參考度從整個(gè)樣本點(diǎn)獲取具有代表性的聚類中心，設(shè)獲得5個(gè)吸引度和歸屬度(r(i,k),a(i,k))較強(qiáng)的AP候選中心如圖1(b)所示，v1=x9，v4=x6，v5=x10，v3=x7，v2=x8，x6和x10、x7和x8在同一簇均具代表性(同類多點(diǎn))。

再根據(jù)MMD算法獲得初始聚類中心。如圖1(c)所示，設(shè)v1和v4距離為d1；v1和v3距離為d2；v1和v2距離為d3，v1和v5距離為d4;v4和v2距離為d6；v4和v3距離為d5；v4和v5距離為d7。

圖1 APMMD求取K-means初始聚類中心過程

(1) 選擇距離最遠(yuǎn)的兩個(gè)樣本作為第一、第二個(gè)聚類中心，因距離d1為最大，則v1、v4為第一、第二個(gè)聚類中心，如圖1(d)所示，c1=v1，c4=v4。

(2) 分別比較v2、v3、v5與v1、v4兩點(diǎn)的距離，找出距離最?。簐2與v1、v4兩點(diǎn)的距離最小，選d6；v3與v1、v4兩點(diǎn)的距離最小，選d5；v5與v1、v4兩點(diǎn)的距離最小，選d7。

(3) 找出v2、v3和v5與v1、v4兩點(diǎn)的距離最小中最大的點(diǎn)：d6>d5>d7，即v2作為第三個(gè)聚類中心，如圖1(d)所示,c2=v2。

3.3 算法步驟

設(shè)X={x1,x2,…,xn}?RP為n個(gè)需聚類的樣本。

步驟1定義聚類數(shù)目k，選擇AP相似參考類型，給定θ∈[0,1]。

步驟2計(jì)算數(shù)據(jù)點(diǎn)的相似度矩陣，計(jì)算式為：

s(i,k)=-d2(xi,xk)=-‖xi-xk‖2

(3)

步驟3計(jì)算樣本點(diǎn)間的吸引度，如下：

r(i,k)=s(i,k)-max{a(i,k′)+s(i,k′)}k≠k′

(4)

步驟4計(jì)算樣本點(diǎn)間的歸屬度，計(jì)算式為：

(5)

步驟5更新吸引度、歸屬度。

ri+1(i,k)=λ×ri(i,k)+(1-λ)×ri+1(i,k)λ∈[0,1)

(6)

ai+1(i,k)=λ×ai(i,k)+(1-λ)×ai+1(i,k)λ∈[0,1)

(7)

步驟6迭代次數(shù)超過既定的次數(shù)或聚類中心變化較小時(shí)結(jié)束迭代計(jì)算，獲得聚類中心Vkap={v1,v2,…,vkap}。否則返回步驟4繼續(xù)迭代計(jì)算。

步驟7從vkap個(gè)對(duì)象樣本中找出距離最大的兩個(gè)點(diǎn)作為第一、第二個(gè)聚類中心，c1=v1，c2=v2。

步驟8計(jì)算vkap個(gè)對(duì)象樣本到c1和c2的聚類Di1和Di2，計(jì)算c1到c2的距離D12。

步驟9Di=max{min(Di1,Di2)},i=1,2,…,n，若Di>θ×D12，則作為第三個(gè)聚類中心，c3=vi。

步驟10依此類推，如有k個(gè)聚類中心，返回步驟9，計(jì)算所有vkap個(gè)對(duì)象樣本到k個(gè)聚類中心距離Dik，直到最大最小距離Di不大于θ×D12，結(jié)束計(jì)算，獲得K-means初始聚類中心。

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

實(shí)驗(yàn)在6個(gè)UCI測(cè)試公共數(shù)據(jù)集上進(jìn)行，數(shù)據(jù)集分類情況已知。Iris數(shù)據(jù)集150個(gè)樣本點(diǎn)為3類、4k2_far數(shù)據(jù)集400個(gè)樣本點(diǎn)為4類，Wine數(shù)據(jù)集178個(gè)樣本點(diǎn)為3類，ASD_12_2數(shù)據(jù)集535個(gè)樣本點(diǎn)為12類，ASD_14_2數(shù)據(jù)集685個(gè)樣本點(diǎn)為14類，Leuk72_3k數(shù)據(jù)集72個(gè)樣本點(diǎn)為3類。

通過降維圖[8-9]顯示，可更直觀、更真實(shí)地展示各種算法獲得聚類中心的變化過程。圖中用閉合曲線圈出不同的簇，“+”代表聚類中心，并加注文本及簇邊框。

利用外部Purity、AC、NMI、JC、RI、FMI有效性指標(biāo)[10-11]及迭代次數(shù)對(duì)6個(gè)UCI測(cè)試公共數(shù)據(jù)集不同獲取初始中心算法的聚類進(jìn)行評(píng)價(jià)。

首先以兩個(gè)數(shù)據(jù)集Iris數(shù)據(jù)集，ASD_14_2數(shù)據(jù)集為例，分別對(duì)MMD、AP、APMMD三種算法獲得聚類中心的過程及聚類中心優(yōu)缺點(diǎn)進(jìn)行描述，并將各方法獲得的中心進(jìn)行K-means聚類，與已知數(shù)據(jù)集的分類情況用降維圖進(jìn)行對(duì)比。圖2(a)為已知 Iris分類情況；圖2(b)為ASD_14_2已知分類情況。

圖2 UCI測(cè)試公共數(shù)據(jù)集已知分類情況

4.1 MMD、AP、APMMD算法獲得初始聚類中心點(diǎn)對(duì)比

1) MMD算法對(duì)Iris數(shù)據(jù)集獲得的初始聚類中心如圖3(a)所示：① 簇1、3初始中心點(diǎn)在簇的邊界;② 簇1、2、3均獲得一個(gè)中心，不存在同簇多個(gè)中心而導(dǎo)致簇中心的缺失(對(duì)比已知圖2(a))。MMD算法對(duì)ASD_14_2數(shù)據(jù)集獲得初始聚類中心如圖3(d)所示：① 初始中心點(diǎn)基本在各簇的邊界；② 因簇6、9獲得兩個(gè)中心點(diǎn)，同簇多中心而導(dǎo)致簇7、11缺失中心點(diǎn)(對(duì)比已知圖2(b))。

2) AP算法對(duì)Iris數(shù)據(jù)集獲得6個(gè)聚類中心如圖3(b)所示：① 大于已知簇?cái)?shù)(k=3)；② 簇1、2、3均獲得2個(gè)聚類中心；③ AP算法中心點(diǎn)具代表性，不在簇的邊界；④ 每個(gè)簇均獲得初始中心，不存在簇中心的缺失(對(duì)比已知圖2(a))。AP算法對(duì)ASD_14_2數(shù)據(jù)集獲得21個(gè)聚類中心如圖3(e)所示：①大于已知簇?cái)?shù)(k=14)；② 其中簇2、3、4、5、6、9、10同簇為2個(gè)聚類中心。簇1、7、8、11、12、13、14為1個(gè)聚類中心，每個(gè)簇均獲得初始中心，不存在簇中心的缺失(對(duì)比已知圖2(b))。

3) APMMD算法：該算法分兩步獲得K-means初始聚類中心。

(1) 首先用AP算法從原始數(shù)據(jù)集X={x1,x2,…,xn}獲得多個(gè)聚類中心作為下一步MMD的候選中心。AP算法對(duì)Iris數(shù)據(jù)集獲得6個(gè)聚類中心見圖3(b)。AP算法對(duì)ASD_14_2數(shù)據(jù)集獲得21個(gè)聚類中心見圖3(e)。

(2) 再用MMD算法從AP獲得的候選聚類中心獲得 個(gè)初始聚類中心。然后MMD算法對(duì)AP算法從Iris數(shù)據(jù)集獲得的6個(gè)AP候選中心中去掉了同類多出的點(diǎn)，獲得3個(gè)初始聚類中心圖3(c)(APMMD算法聚類中心)，對(duì)比已知圖2(a)。最后MMD算法對(duì)AP算法從ASD_14_2數(shù)據(jù)集獲得的21個(gè)AP候選中心中去掉了同類多出的點(diǎn)，獲得14個(gè)初始聚類中心圖3(f) (APMMD算法聚類中心)，對(duì)比已知圖2(b)。

可以看出，MMD對(duì)簇?cái)?shù)較小的數(shù)據(jù)集基本適應(yīng)，對(duì)簇?cái)?shù)較大的數(shù)據(jù)集存在同類多點(diǎn)而導(dǎo)致一些簇的缺失。AP中心簇?cái)?shù)大于實(shí)際簇?cái)?shù)。APMMD算法能較好的為每簇找到一個(gè)合理的聚類中心。

(a) MMD獲得Iris的中心 (b) MMD獲得ASD_14_2的中心

(c) AP獲得Iris的中心 (d) AP獲得ASD_14_2的中心

(e) APMMD獲得Iris的中心 (f) APMMD獲得ASD_14_2中心圖3 MMD、AP、APMMD算法獲得中心點(diǎn)對(duì)比

4.2 MMD、AP、APMMD算法對(duì)K-means改進(jìn)聚類結(jié)果圖對(duì)比

(1) MMD對(duì)K-means改進(jìn)的聚類結(jié)果。MMD算法對(duì)Iris數(shù)據(jù)集獲得的聚類中心，通過K-means聚類迭代，聚類中心最后接近實(shí)際中心，聚類結(jié)果圖4(a)與圖2(a)已知分類基本一致。對(duì)ASD_14_2數(shù)據(jù)集獲得的聚類中心，通過K-means聚類迭代，部分中心最后接近實(shí)際中心，部分將陷入局部最優(yōu)、且同類多點(diǎn)情況，見圖3(d)簇6、9分成了兩類。聚類結(jié)果圖4(d)與圖2(b)已知分類相差較大。主要是ASD_14_2聚簇?cái)?shù)較大，因MMD算法受K值的限定，求取的聚類中心有同類多點(diǎn)而導(dǎo)致初始類的缺失原因，初始類缺失的圖3(d)簇7、11劃分給了其他的簇。

(2) AP對(duì)K-means改進(jìn)的聚類結(jié)果。AP算法對(duì)Iris數(shù)據(jù)集獲得6個(gè)聚類中心，大于已知簇?cái)?shù)(k=3)，聚類分類結(jié)果如圖4(c)所示，其與已知圖2(a)不符。

AP算法對(duì)ASD_14_2數(shù)據(jù)集獲得21個(gè)聚類中心，大于已知簇?cái)?shù)(k=21)，聚類分類結(jié)果如圖4(d)所示，其與已知的圖2(b)不符。

(3) APMMD對(duì)K-means改進(jìn)的聚類結(jié)果。APMMD算法對(duì)Iris數(shù)據(jù)集通過K-means聚類迭代，聚類中心最后接近實(shí)際中心，聚類結(jié)果如圖4(e)所示，其與圖2(a)已知分類基本一致。

APMMD算法對(duì)ASD_14_2數(shù)據(jù)集通過K-means迭代，聚類中心全部接近實(shí)際中心，聚類結(jié)果如圖4(f)所示，其與圖2(b)已知分類完全一致。

可以看出，MMD、APMMD算法獲得的初始聚類中心對(duì)簇?cái)?shù)較小的Iris數(shù)據(jù)集基本適應(yīng)，只是因MMD中心在簇邊界，聚類收斂速度要低于APMMD中心。MMD對(duì)簇?cái)?shù)較大的ASD_14_2數(shù)據(jù)集存在同類多點(diǎn)而導(dǎo)致一些簇的缺失，聚類結(jié)果與已知分類相差較大，說明MMD對(duì)簇?cái)?shù)較大的數(shù)據(jù)集不適應(yīng)。AP算法中心簇?cái)?shù)大于實(shí)際簇?cái)?shù)，自然不能直接應(yīng)用。APMMD算法能較好地為Iris數(shù)據(jù)集、ASD_14_2數(shù)據(jù)集的每個(gè)簇找到一個(gè)合理的聚類中心，聚類結(jié)果自然較好。

(a) MMD改進(jìn)Iris聚類 (b) MMD改進(jìn)ASD_14_2聚類

(c) AP改進(jìn)Iris聚類 (d) AP改進(jìn)ASD_14_2聚類

(e) APMMD改進(jìn)Iris聚類 (f) APMMD改進(jìn)ASD_14_2聚類圖4 MMD、AP、APMMD改進(jìn)K-means聚類結(jié)果對(duì)比

4.3 有效性指標(biāo)對(duì)比

聚類的性能指標(biāo)可評(píng)價(jià)聚類性能的質(zhì)量，在聚類方法相同的情況下，可評(píng)價(jià)K-means初始聚類中心的質(zhì)量。

聚類的性能指標(biāo)分為兩類：① 外部指標(biāo)，由聚類結(jié)果和某個(gè)參考模型進(jìn)行比較而獲得；② 內(nèi)部指標(biāo)，由本身的聚類結(jié)果而得到，不利用任何參考模型。

最后本文方法將與隨機(jī)、金字塔、MMD、MMD & SSE和M-AP幾種已有改進(jìn)聚類算法進(jìn)行比較，采用多個(gè)外部指標(biāo)Purity、AC、NMI、JC、RI和FMI對(duì)6個(gè)UCI測(cè)試公共數(shù)據(jù)集對(duì)幾種算法聚類結(jié)果進(jìn)行評(píng)價(jià)，數(shù)據(jù)集分類已知。從表1可以看出，隨機(jī)中心聚類各有效性指標(biāo)遠(yuǎn)低于改進(jìn)算法和APMMD算法的有效性指標(biāo)。

表1 數(shù)據(jù)集聚類有效性指標(biāo)對(duì)比

續(xù)表1

對(duì)于Iris、4k2_far、Wine和Leuk72_3k簇?cái)?shù)不大的4個(gè)數(shù)據(jù)集，MMD算法和APMMD算法初始聚類中心的聚類指標(biāo)基本一致。但對(duì)于數(shù)據(jù)集簇?cái)?shù)較大的ASD_12_2、ASD_14_2數(shù)據(jù)集，MMD算法有效性指標(biāo)全低于APMMD算法。對(duì)于4k2_far、ASD_12_2兩數(shù)據(jù)集，APMMD算法的6個(gè)有效性指標(biāo)全為1，正確識(shí)別率為100%、對(duì)于ASD_14_2數(shù)據(jù)集，則接近完全吻合。充分說明了改進(jìn)的APMMD算法求取的初始中心優(yōu)于隨機(jī)和其他算法。

4.4 迭代次數(shù)對(duì)比

在聚類方法相同的情況下，聚類收斂速度也可評(píng)價(jià)初始聚類中心的質(zhì)量。用幾種算法分別求得6個(gè)數(shù)據(jù)集的初始中心，并依次用于K-means聚類，其收斂迭代次數(shù)對(duì)比如圖5所示，可以看出隨機(jī)、金字塔、MMD、MMD&SSE、M-AP算法獲得的初始聚類中心聚類迭代次數(shù)都遠(yuǎn)大于APMMD算法。因算法初始中心在簇的邊界，收斂迭代次數(shù)要大于APMMD。

圖5 不同初始中心的K-means聚類收斂迭代次數(shù)對(duì)比

5 結(jié) 語(yǔ)

本文通過對(duì)經(jīng)典的K-means算法、MMD算法及AP算法的研究，并進(jìn)行實(shí)驗(yàn)對(duì)比、聚類結(jié)果質(zhì)量評(píng)價(jià)，證明了初始聚類中心的選擇對(duì)K-means算法的聚類結(jié)果有極大的影響，不同的初始聚類中心會(huì)有不同的聚類結(jié)果，不合理的初始聚類中心可能導(dǎo)致聚類結(jié)果的局部最優(yōu)，且降低聚類算法的收斂速度，影響聚類效果。MMD算法獲得的初始聚類中心對(duì)簇?cái)?shù)較小的數(shù)據(jù)集基本適應(yīng)，對(duì)簇?cái)?shù)較大的數(shù)據(jù)集存在同類多點(diǎn)而導(dǎo)致一些簇的缺失，聚類精度不高。AP算法獲得的聚類中心簇?cái)?shù)大于實(shí)際簇?cái)?shù)，不能直接應(yīng)用。APMMD算法能較好地為數(shù)據(jù)集的每個(gè)簇找到一個(gè)合理的聚類中心，較其他幾種算法改進(jìn)K-means聚類精度更高、迭代次數(shù)更少、收斂速度更快。