結(jié)合最大最小距離和加權(quán)密度的K-means聚類算法

馬克勤，楊延?jì)?，秦紅武，耿 琳，王丕棟

西北師范大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，蘭州 730070

1 引言

聚類是數(shù)據(jù)挖掘[1]領(lǐng)域的一項(xiàng)重要技術(shù)，一直受到研究者的高度重視，被廣泛應(yīng)用到很多領(lǐng)域，包括市場(chǎng)研究[2]、數(shù)據(jù)分析[3]、模式識(shí)別[4]、圖像處理[5]和文本分析[6]等。傳統(tǒng)K-means算法即K均值算法是MacQueen[7]提出的一種經(jīng)典的基于劃分的聚類算法。該算法憑借著原理簡(jiǎn)單易懂、收斂速度快、執(zhí)行效率高等優(yōu)點(diǎn)而被人們廣泛使用。但該算法的聚類結(jié)果不僅易受聚類數(shù)K的影響，而且對(duì)初始聚類中心的選擇依賴性比較大，不同的初始聚類中心下聚類結(jié)果通常不一樣，因此算法的穩(wěn)定性較差；另外聚類中心的選擇往往會(huì)使聚類結(jié)果收斂于局部最優(yōu)。

目前對(duì)K-means算法的研究主要集中在以下方向：一是研究如何通過(guò)獲得更好的初始聚類中心來(lái)改進(jìn)算法的性能。左進(jìn)等[8]在數(shù)據(jù)點(diǎn)緊密性的基礎(chǔ)上排除離群點(diǎn)，均勻地選擇初始聚類中心，但依然需要根據(jù)經(jīng)驗(yàn)確定K值；湯深偉等[9]將混沌搜索引入到粒子群算法中，將改進(jìn)的粒子群算法應(yīng)用到K-means算法中，以此來(lái)尋找較好的聚類中心；隋心怡等[10]將樣本分布空間分割為大小相同的子空間，通過(guò)統(tǒng)計(jì)子空間中的樣本密度來(lái)優(yōu)化初始聚類中心，實(shí)驗(yàn)表明該方法可以有效提高算法穩(wěn)定性并減少迭代次數(shù)，最終獲得較好的聚類效果。二是研究如何獲得最佳的聚類數(shù)，即確定最優(yōu)的K值。王建仁等[11]針對(duì)傳統(tǒng)手肘法中“肘點(diǎn)”不明確問(wèn)題，結(jié)合指數(shù)函數(shù)性質(zhì)、權(quán)重調(diào)節(jié)、偏執(zhí)項(xiàng)和手肘法基本思想進(jìn)行改進(jìn)優(yōu)化，實(shí)驗(yàn)表明改進(jìn)算法能有效確定K值，且性能良好；Sun 等[12]提出了基于密度和下一個(gè)擬合情況下的K值優(yōu)化算法，可以高效準(zhǔn)確地獲得簇的數(shù)量K，通過(guò)用戶合理的閾值設(shè)置，大大降低錯(cuò)誤并提高簇?cái)?shù)K的準(zhǔn)確性。三是對(duì)中心點(diǎn)和聚類數(shù)同時(shí)進(jìn)行改進(jìn)。張素潔等[13]根據(jù)密度和最遠(yuǎn)距離對(duì)中心點(diǎn)進(jìn)行選取并結(jié)合SSE（Sum of Squares for Error）確定最優(yōu)的K值，最終獲得較高的聚類準(zhǔn)確率；賈瑞玉等[14]使用密度法選取中心點(diǎn)集，再將聚類離差距離與聚類距離的比值作為一種新的聚類有效性指標(biāo)IBWP，并依據(jù)此指標(biāo)獲得最佳聚類數(shù)，從而得到良好的聚類效果，但算法因受聚類數(shù)和搜索范圍的影響付出了時(shí)間代價(jià)。

綜合上述對(duì)傳統(tǒng)K-means算法的改進(jìn)，本文提出了一種基于加權(quán)密度和最大最小距離的K-means 算法（K-means algorithm based on Weighted Density and Max-min distance，KWDM），通過(guò)加權(quán)密度法來(lái)確定中心點(diǎn)集，排除離群點(diǎn)對(duì)聚類結(jié)果的影響，再利用最大最小距離準(zhǔn)則來(lái)選擇中心點(diǎn)，有效地避免了聚類結(jié)果陷入局部最優(yōu)，提高了劃分初始數(shù)據(jù)集的效率，最后利用準(zhǔn)則函數(shù)即簇內(nèi)距離和簇間距離的比值來(lái)確定K值，使聚類的準(zhǔn)確率和穩(wěn)定性都得到提升。

2 基本概念

2.1 K-means算法

K-means 算法的基本原理是將n個(gè)樣本集劃分到K個(gè)簇中，要求劃分到同一簇中的樣本盡可能地相似，而劃分到不同簇中的樣本盡可能地相異。

算法基本思想：先隨機(jī)選取k個(gè)樣本作為初始聚類中心，計(jì)算剩余的每個(gè)樣本到初始聚類中心的歐氏距離，將每個(gè)樣本劃分到離它最近的聚類簇中；然后對(duì)調(diào)整后的類簇進(jìn)行簇類中心的更新，反復(fù)迭代直到聚類準(zhǔn)則函數(shù)收斂或者達(dá)到迭代次數(shù)。

評(píng)價(jià)聚類結(jié)果通常用誤差平方函數(shù)作為聚類準(zhǔn)則函數(shù)，如式（1）所示：

其中，Cj表示第j個(gè)類別中的樣本集合，vj是Cj內(nèi)所有樣本點(diǎn)pi的聚類中心點(diǎn)，k表示聚類個(gè)數(shù)。dist(pi,vj)表示簇Cj的對(duì)象pi與質(zhì)心vj在m維空間的歐氏距離，m、l為空間維數(shù)，如式（2）所示：

聚類中心的更新如式（3）所示：

其中，n是Cj中數(shù)據(jù)對(duì)象的個(gè)數(shù)。

2.2 最大最小距離準(zhǔn)則

最大最小距離準(zhǔn)則[15]是以歐式距離為基礎(chǔ)，取盡可能遠(yuǎn)的樣本點(diǎn)作為聚類中心，避免了K-means算法選取初始值時(shí)可能出現(xiàn)的聚類中心過(guò)于鄰近的情況，而且提高了劃分初始數(shù)據(jù)集的效率。算法的基本思想：在樣本中首先任選一個(gè)樣本點(diǎn)作為聚類中心點(diǎn)v1，再選距離v1最遠(yuǎn)的樣本點(diǎn)作為聚類中心v2，選擇剩余的中心點(diǎn)l(l＞2)時(shí)，分別將剩余的每個(gè)樣本點(diǎn)到之前中心點(diǎn)的歐氏距離值小的放入集合中，將集合中最大值對(duì)應(yīng)的樣本點(diǎn)作為下一個(gè)中心點(diǎn)，重復(fù)該過(guò)程依次計(jì)算剩余所需要的中心點(diǎn)，如式（4）所示：

其中，disti1、disti2分別是樣本i到v1和v2的歐式距離。

最大最小距離準(zhǔn)則找距離遠(yuǎn)的樣本點(diǎn)作為聚類中心，但是僅從距離判斷很有可能會(huì)將離群點(diǎn)作為初始中心點(diǎn)，從而降低聚類的準(zhǔn)確率。

3 KWDM 算法

KWDM 算法基本思想：利用加權(quán)密度法排除離群點(diǎn)，選出聚類中心點(diǎn)集；通過(guò)最大最小距離準(zhǔn)則在聚類中心點(diǎn)集中選取聚類中心；最后利用簇內(nèi)樣本距離與簇間樣本距離的比值來(lái)確定K值。KWDM 算法克服了K-means算法對(duì)聚類中心選擇的隨機(jī)性，防止聚類結(jié)果陷入局部最優(yōu)，同時(shí)在歐式距離的基礎(chǔ)上加入權(quán)值，進(jìn)一步加強(qiáng)了數(shù)據(jù)中不同屬性的區(qū)分程度，減少了離群點(diǎn)的影響，優(yōu)化了初始聚類中心的選擇，提高了聚類結(jié)果的準(zhǔn)確率。對(duì)于K值，文獻(xiàn)[16]以距離代價(jià)最小原則將K值的范圍限定在，實(shí)驗(yàn)證明該范圍可以提高聚類效率，并從理論上論證了其合理性，因此可以作為本文K值確定的參考。

3.1 權(quán)值的計(jì)算

算法中權(quán)值的計(jì)算引用了文獻(xiàn)[17]的權(quán)值計(jì)算公式，相關(guān)定義如下：

設(shè)有n個(gè)樣本數(shù)據(jù)X={x1,x2,…,xn}為聚類數(shù)據(jù)集，其中xi=(xi1,xi2,…,xim)T為m維向量，根據(jù)每個(gè)樣本數(shù)據(jù)中每個(gè)分量的影響不同，定義權(quán)值W=(w1,w2,…,wm)T∈Rn×m，其中wi=(wi1,wi2,…,wim)T為m維向量，權(quán)值計(jì)算如式（5）所示：

其中，xid表示第i個(gè)樣本數(shù)據(jù)中的第d個(gè)分量；表示樣本數(shù)據(jù)中各個(gè)數(shù)據(jù)對(duì)象的第d個(gè)分量中和的平均值；w反映了樣本數(shù)據(jù)整體分布特征。

3.2 所有樣本點(diǎn)的平均距離

加權(quán)的歐式距離如式（6）所示：

其中，distw(xi,xj)表示樣本xi和xj在m維空間下的加權(quán)歐氏距離，xil和xjl分別表示在空間l維下的樣本xi和xj，m、l為空間維數(shù)。

所有樣本點(diǎn)的平均歐式距離如式（7）所示：

3.3 K 值的確定

聚類中K值的確定對(duì)聚類結(jié)果有很大的影響，不同的K值對(duì)應(yīng)不同的聚類結(jié)果。聚類結(jié)果要求簇內(nèi)樣本距離越小即簇內(nèi)相似度越高，簇間樣本距離越大即簇間相似度越低，則聚類效果越好，也就是說(shuō)聚類效果跟簇內(nèi)樣本距離和簇間樣本距離都有關(guān)系。因此本文利用簇內(nèi)樣本距離與簇間樣本距離的比值來(lái)確定K值，相關(guān)定義如下：

定義1 存在n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集S，假設(shè)n個(gè)數(shù)據(jù)對(duì)象被劃分到K個(gè)類簇中，定義第j類對(duì)象i的簇間樣本距離b(j,i)為該樣本到其他每個(gè)簇中樣本平均值的最小值，如式（8）所示：

其中，nc表示類c的元素個(gè)數(shù)，表示第c類的第p個(gè)樣本，表示第j類的第i個(gè)樣本，表示加權(quán)的不同簇間的樣本p到樣本i之間的歐式距離。

定義2 存在n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集S，假設(shè)n的數(shù)據(jù)對(duì)象被劃分到K個(gè)類簇中，定義第j類的對(duì)象i的簇內(nèi)樣本距離v(j,i)為該樣本到簇內(nèi)其他樣本的平均值，如式（9）所示：

其中，nj表示類j的元素個(gè)數(shù)，表示第j類的第p個(gè)樣本，表示第j類的第i個(gè)樣本，表示加權(quán)的簇內(nèi)的樣本i到簇內(nèi)其他樣本間的歐式距離。

定義3 第j類的數(shù)據(jù)對(duì)象i的聚類有效性指標(biāo)為簇內(nèi)樣本距離與簇間樣本聚類的比值，如式（10）所示：

由公式可得，簇內(nèi)樣本距離v(j,i)越小，簇間樣本距離b(j,i)越大，則H(j,i)的值越小，聚類效果越好。通過(guò)比較聚類樣本集n個(gè)樣本對(duì)象的H值的平均值的大小來(lái)確定最佳聚類數(shù)，則式（11）中指標(biāo)最小時(shí)所對(duì)應(yīng)的聚類數(shù)為最佳聚類數(shù)，即最佳的K值。

3.4 KWDM算法流程

輸入：樣本集X。

輸出：聚類結(jié)果。

步驟1 輸入樣本點(diǎn)集X，根據(jù)式（6）、（7）計(jì)算出所有樣本點(diǎn)的平均距離avgdistw。

步驟2 以任意樣本點(diǎn)x為中心，R=avgdistw為半徑畫圓，將圓內(nèi)的所有樣本點(diǎn)數(shù)目T（包括邊緣的樣本點(diǎn)）作為樣本點(diǎn)x的密度。

步驟3 計(jì)算出所有樣本點(diǎn)的密度后，按從大到小的順序?qū)⑶皞€(gè)樣本數(shù)據(jù)存入到數(shù)據(jù)集合U中，選取樣本點(diǎn)密度最大的點(diǎn)x1作為第一個(gè)聚類中心放入中心點(diǎn)集合C中。

步驟4 在數(shù)據(jù)集合U中找出距離x1最遠(yuǎn)的點(diǎn)作為第2個(gè)中心點(diǎn)x2加入到中心點(diǎn)集合C中。

步驟5 根據(jù)最大最小距離準(zhǔn)則，在剩余的所有樣本中依次計(jì)算出-2個(gè)中心點(diǎn)，依次加入中心點(diǎn)集合C中。

步驟 6 因?yàn)? ≤K≤，則從集合C中選擇前k個(gè)數(shù)據(jù)樣本作為初始聚類中心點(diǎn)。

步驟7 將數(shù)據(jù)集X中的其他樣本點(diǎn)根據(jù)歐式距離劃分到最近的簇中，然后根據(jù)式（11）計(jì)算本次聚類avgH(k)的值。

步驟8 比較所有不同K的avgH(k)的值，avgH(k)的值最小時(shí)，K的取值為最佳聚類數(shù)。

步驟9 輸出最佳聚類數(shù)和對(duì)應(yīng)的初始聚類中心點(diǎn)并進(jìn)行聚類，算法結(jié)束。

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

為了檢驗(yàn)KWDM 算法的性能，采用隨機(jī)生成的數(shù)值型人工數(shù)據(jù)集和UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)配置：操作系統(tǒng)為Win8系統(tǒng)，64位，使用python2.7.0來(lái)實(shí)現(xiàn)提出的算法，運(yùn)行環(huán)境為Intel?CoreTMi5-7200U CPU，2.50 GHz，8.00 GB。

實(shí)驗(yàn)1 隨機(jī)生成1 000條數(shù)值型數(shù)據(jù)作為數(shù)據(jù)集散布在解空間，其中每條數(shù)據(jù)有兩個(gè)屬性，通過(guò)對(duì)比K-means算法和KWDM 的聚類效果圖，驗(yàn)證本文算法聚類中心選取的有效性，經(jīng)過(guò)最大最小距離準(zhǔn)則得到聚類類別數(shù)為K=6，聚類結(jié)果如圖1、圖2所示。

通過(guò)兩種算法聚類結(jié)果對(duì)比，由圖1、圖2可以看出K-means算法的部分聚類中心分布較為集中，有的簇選取了離群點(diǎn)作為中心點(diǎn)；KWDM 算法通過(guò)密度法排除了離群點(diǎn)作為中心點(diǎn)的可能，優(yōu)化了聚類中心的選取，并通過(guò)最大最小距離準(zhǔn)則改善了K-means算法易陷入局部最優(yōu)的問(wèn)題，相較于K-means算法，聚類中心分布更均勻，聚類效果更佳。

圖1 K-means算法聚類結(jié)果

圖2 KWDM 算法聚類結(jié)果

實(shí)驗(yàn)2 選取專用于測(cè)試聚類算法性能的UCI 數(shù)據(jù)庫(kù)中的Iris、Wine 和Seeds 三組數(shù)據(jù)集進(jìn)行仿真。其中Iris 數(shù)據(jù)集樣本個(gè)數(shù)為150，數(shù)據(jù)屬性為4，類數(shù)為3；Wine 數(shù)據(jù)集樣本個(gè)數(shù)為178，數(shù)據(jù)屬性個(gè)數(shù)為13，類數(shù)為3；Seeds 數(shù)據(jù)集樣本個(gè)數(shù)為210，數(shù)據(jù)屬性個(gè)數(shù)為7，類數(shù)為3。三個(gè)數(shù)據(jù)集的統(tǒng)計(jì)信息如表1所示。

表1 UCI數(shù)據(jù)集信息

為了驗(yàn)證算法的有效性，K-means算法、文獻(xiàn)[10]、文獻(xiàn)[11]、文獻(xiàn)[13]算法及KWDM 算法分別在三組數(shù)據(jù)集上進(jìn)行獨(dú)立實(shí)驗(yàn)，從聚類的準(zhǔn)確率、迭代次數(shù)及穩(wěn)定性上進(jìn)行分析。

表2 顯示的是算法的準(zhǔn)確率。從表2 可以看出，KWDM 算法得到的平均聚類準(zhǔn)確率相較于K-means算法和文獻(xiàn)[10]、文獻(xiàn)[11]、文獻(xiàn)[13]算法分別提高了13.3 個(gè)百分點(diǎn)、6.0 個(gè)百分點(diǎn)、8.6 個(gè)百分點(diǎn)和 3.0 個(gè)百分點(diǎn)。也可以看出文獻(xiàn)[10]、文獻(xiàn)[11]和文獻(xiàn)[13]算法優(yōu)于K-means 算法，這是因?yàn)槲墨I(xiàn)[10]和文獻(xiàn)[13]算法不再是隨機(jī)選取初始聚類中心，而是通過(guò)空間樣本密度來(lái)選取初始聚類中心，但是文獻(xiàn)[10]算法忽略了離群點(diǎn)對(duì)聚類中心的影響，文獻(xiàn)[13]算法沒(méi)有考慮到不同的特征在簇中可能占有不同的比重，文獻(xiàn)[11]雖然通過(guò)確定K值提高了算法的準(zhǔn)確率，但是初始中心點(diǎn)的選取還是隨機(jī)進(jìn)行，因此相較于通過(guò)密度法來(lái)確定聚類中心和對(duì)屬性進(jìn)行加權(quán)的KWDM 算法來(lái)說(shuō)，其聚類準(zhǔn)確率較低。表3 顯示的是算法的迭代次數(shù)，可以看出KWDM 算法的迭代次數(shù)均少于K-means、文獻(xiàn)[10]、文獻(xiàn)[11]算法。這是因?yàn)閷?duì)選取初始中心的優(yōu)化，減少了算法的迭代次數(shù)，加速了算法的收斂。

表2 算法準(zhǔn)確率 %

表3 算法迭代次數(shù)

圖3、圖4、圖5 分別統(tǒng)計(jì)了五種算法在三組數(shù)據(jù)集上算法的準(zhǔn)確率和迭代次數(shù)關(guān)系。這充分說(shuō)明K-means算法和文獻(xiàn)[11]算法隨機(jī)選取初始聚類中心而導(dǎo)致算法穩(wěn)定性較差，而文獻(xiàn)[10]、文獻(xiàn)[13]算法和KWDM 算法則可以保持較好的穩(wěn)定性，且KWDM 算法無(wú)論從準(zhǔn)確率和迭代次數(shù)上都優(yōu)于文獻(xiàn)[10]算法。

圖3 Iris迭代次數(shù)與準(zhǔn)確率關(guān)系圖

圖4 Wine迭代次數(shù)與準(zhǔn)確率關(guān)系圖

圖5 Seeds迭代次數(shù)與準(zhǔn)確率關(guān)系圖

算法復(fù)雜度分析，K-means 算法的時(shí)間復(fù)雜度為O(nkT)，其中n為聚類樣本個(gè)數(shù)，k為聚類簇?cái)?shù)，T為聚類過(guò)程迭代次數(shù)。KWDM 與傳統(tǒng)K-means 算法相比，聚類過(guò)程主要分為兩步，其中選擇初始聚類中心的時(shí)間復(fù)雜度為O(2n2),確定K值的時(shí)間復(fù)雜度為O(nt3/2),因此KWDM 算法整體時(shí)間復(fù)雜度變?yōu)镺(2n2)+O(nt3/2),其中t為KWDM 算法的迭代次數(shù)。雖然KWDM 算法增加了選擇初始聚類中心點(diǎn)這一環(huán)節(jié)，會(huì)造成大量的時(shí)間消耗，但是一旦選擇到較優(yōu)的初始聚類中心點(diǎn)，可以減少迭代次數(shù)，縮小時(shí)間消耗。由圖3、圖4、圖5五種算法在Iris、Wine、Seeds 三種數(shù)據(jù)集上的迭代次數(shù)與準(zhǔn)確率的關(guān)系圖可知，KWDM 算法在迭代次數(shù)較小的情況下也能達(dá)到較高的準(zhǔn)確率，因此t＜T時(shí)，KWDM 算法可以減少迭代時(shí)間。算法的運(yùn)行時(shí)間如表4所示。

表4 時(shí)間復(fù)雜度 ms

從表4 可以看出，KWDM 算法的時(shí)間復(fù)雜度優(yōu)于文獻(xiàn)[10]、文獻(xiàn)[11]和文獻(xiàn)[13]的時(shí)間復(fù)雜度。KWDM算法通過(guò)密度法來(lái)確定聚類中心并對(duì)屬性進(jìn)行加權(quán)，提高了算法的準(zhǔn)確率，但是該算法與K-means算法相比，其運(yùn)行時(shí)間較長(zhǎng)。

5 結(jié)束語(yǔ)

本文主要針對(duì)K-means 算法隨機(jī)選取初始聚類中心和根據(jù)經(jīng)驗(yàn)確定聚類數(shù)而造成的算法不穩(wěn)定性等問(wèn)題，提出了一種基于密度和最大最小距離的KWDM 算法，不僅對(duì)聚類中心的選擇進(jìn)行了優(yōu)化，對(duì)K值也進(jìn)行了有效的確定，在歐氏距離的基礎(chǔ)上加入了權(quán)值，利用密度法來(lái)選取初始聚類中心集，減少了離群點(diǎn)對(duì)聚類結(jié)果的影響，再結(jié)合最大最小距離準(zhǔn)則，有效地避免了在聚類中心的選取上陷入局部最優(yōu)的問(wèn)題。在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，KWDM 算法不僅在聚類的準(zhǔn)確率上有所提高，而且減少了算法的迭代次數(shù)，提高了算法的穩(wěn)定性。但由于KWDM 算法需要統(tǒng)計(jì)所有樣本空間的分布，從而算法的時(shí)間復(fù)雜度有所提高，因此在處理高維大數(shù)據(jù)時(shí)，KWDM 算法還需要進(jìn)一步的改進(jìn)，這也是今后需要研究的方向。