馬克勤，楊延嬌，秦紅武，耿 琳，王丕棟

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

1 引言

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

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

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

2 基本概念

2.1 K-means算法

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

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

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

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

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

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

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

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

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

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

3 KWDM 算法

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

3.1 權(quán)值的計算

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

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

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

3.2 所有樣本點的平均距離

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

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

所有樣本點的平均歐式距離如式（7）所示：

3.3 K 值的確定

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

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

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

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

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

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

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

3.4 KWDM算法流程

輸入：樣本集X。

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果和分析

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

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

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

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

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

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

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

為了驗證算法的有效性，K-means算法、文獻(xiàn)[10]、文獻(xiàn)[11]、文獻(xiàn)[13]算法及KWDM 算法分別在三組數(shù)據(jù)集上進(jì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 個百分點、6.0 個百分點、8.6 個百分點和 3.0 個百分點。也可以看出文獻(xiàn)[10]、文獻(xiàn)[11]和文獻(xiàn)[13]算法優(yōu)于K-means 算法，這是因為文獻(xiàn)[10]和文獻(xiàn)[13]算法不再是隨機(jī)選取初始聚類中心，而是通過空間樣本密度來選取初始聚類中心，但是文獻(xiàn)[10]算法忽略了離群點對聚類中心的影響，文獻(xiàn)[13]算法沒有考慮到不同的特征在簇中可能占有不同的比重，文獻(xiàn)[11]雖然通過確定K值提高了算法的準(zhǔn)確率，但是初始中心點的選取還是隨機(jī)進(jìn)行，因此相較于通過密度法來確定聚類中心和對屬性進(jìn)行加權(quán)的KWDM 算法來說，其聚類準(zhǔn)確率較低。表3 顯示的是算法的迭代次數(shù)，可以看出KWDM 算法的迭代次數(shù)均少于K-means、文獻(xiàn)[10]、文獻(xiàn)[11]算法。這是因為對選取初始中心的優(yōu)化，減少了算法的迭代次數(shù)，加速了算法的收斂。

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

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

圖3、圖4、圖5 分別統(tǒng)計了五種算法在三組數(shù)據(jù)集上算法的準(zhǔn)確率和迭代次數(shù)關(guān)系。這充分說明K-means算法和文獻(xiàn)[11]算法隨機(jī)選取初始聚類中心而導(dǎo)致算法穩(wěn)定性較差，而文獻(xiàn)[10]、文獻(xiàn)[13]算法和KWDM 算法則可以保持較好的穩(wěn)定性，且KWDM 算法無論從準(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 算法的時間復(fù)雜度為O(nkT)，其中n為聚類樣本個數(shù)，k為聚類簇數(shù)，T為聚類過程迭代次數(shù)。KWDM 與傳統(tǒng)K-means 算法相比，聚類過程主要分為兩步，其中選擇初始聚類中心的時間復(fù)雜度為O(2n2),確定K值的時間復(fù)雜度為O(nt3/2),因此KWDM 算法整體時間復(fù)雜度變?yōu)镺(2n2)+O(nt3/2),其中t為KWDM 算法的迭代次數(shù)。雖然KWDM 算法增加了選擇初始聚類中心點這一環(huán)節(jié)，會造成大量的時間消耗，但是一旦選擇到較優(yōu)的初始聚類中心點，可以減少迭代次數(shù)，縮小時間消耗。由圖3、圖4、圖5五種算法在Iris、Wine、Seeds 三種數(shù)據(jù)集上的迭代次數(shù)與準(zhǔn)確率的關(guān)系圖可知，KWDM 算法在迭代次數(shù)較小的情況下也能達(dá)到較高的準(zhǔn)確率，因此t＜T時，KWDM 算法可以減少迭代時間。算法的運行時間如表4所示。

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

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

5 結(jié)束語

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