王美琪 李 建

(西南石油大學計算機科學學院 四川 成都 610500)

0 引 言

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

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

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

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

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

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

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

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

(1)

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

(2)

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

算法存在以下問題：

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

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

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

2 相關算法

2.1 近鄰傳播算法

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

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

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

2.2 最大最小距離算法

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

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

3 APMMD算法

3.1 基本思路

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

3.2 算法解析

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

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

再根據(jù)MMD算法獲得初始聚類中心。如圖1(c)所示，設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) 選擇距離最遠的兩個樣本作為第一、第二個聚類中心，因距離d1為最大，則v1、v4為第一、第二個聚類中心，如圖1(d)所示，c1=v1，c4=v4。

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

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

3.3 算法步驟

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

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

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

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

(3)

步驟3計算樣本點間的吸引度，如下：

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

(4)

步驟4計算樣本點間的歸屬度，計算式為：

(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ù)或聚類中心變化較小時結束迭代計算，獲得聚類中心Vkap={v1,v2,…,vkap}。否則返回步驟4繼續(xù)迭代計算。

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

步驟8計算vkap個對象樣本到c1和c2的聚類Di1和Di2，計算c1到c2的距離D12。

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

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

4 實驗與結果分析

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

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

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

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

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

4.1 MMD、AP、APMMD算法獲得初始聚類中心點對比

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

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

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

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

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

可以看出，MMD對簇數(shù)較小的數(shù)據(jù)集基本適應，對簇數(shù)較大的數(shù)據(jù)集存在同類多點而導致一些簇的缺失。AP中心簇數(shù)大于實際簇數(shù)。APMMD算法能較好的為每簇找到一個合理的聚類中心。

(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算法獲得中心點對比

4.2 MMD、AP、APMMD算法對K-means改進聚類結果圖對比

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

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

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

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

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

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

(a) MMD改進Iris聚類 (b) MMD改進ASD_14_2聚類

(c) AP改進Iris聚類 (d) AP改進ASD_14_2聚類

(e) APMMD改進Iris聚類 (f) APMMD改進ASD_14_2聚類圖4 MMD、AP、APMMD改進K-means聚類結果對比

4.3 有效性指標對比

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

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

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

表1 數(shù)據(jù)集聚類有效性指標對比

續(xù)表1

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

4.4 迭代次數(shù)對比

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

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

5 結 語

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