基于密度的全局K-means算法的改進(jìn)

徐 娟，范 菁，陳楚天，曲金帥1，

(1. 云南民族大學(xué) 云南省高校信息與通信安全災(zāi)備重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650500; 2. 云南民族大學(xué) 電氣信息工程學(xué)院，云南 昆明 650500)

傳統(tǒng)的K-means算法，方法簡(jiǎn)單有效，收斂迅速，便于處理較大型數(shù)據(jù)，已經(jīng)被廣泛運(yùn)用到各個(gè)領(lǐng)域[1].但是傳統(tǒng)的K-means算法對(duì)初始中心點(diǎn)[2]的選擇依賴性強(qiáng)，為了解決該問(wèn)題，人們提出了很多增量式算法[3].

2003年Likas[4]等提出了一種全局K-means聚類算法，同時(shí)在文獻(xiàn)中還提出了一種改進(jìn)的快速全局K-means算法.全局K-means聚類算法是一種增量式算法，該算法需要通過(guò)全局搜索來(lái)確定下一個(gè)簇的初始聚類中心點(diǎn)，每次都需要迭代運(yùn)行N次(N是數(shù)據(jù)集中數(shù)據(jù)的個(gè)數(shù))K-means算法計(jì)算簇內(nèi)平方誤差函數(shù)E，使得簇內(nèi)平方誤差函數(shù)最小的點(diǎn)，則設(shè)定為下一簇的最佳初始中心點(diǎn).該算法的缺點(diǎn)是每一次都需要迭代N次，計(jì)算量大，在處理大數(shù)據(jù)集時(shí)消耗的時(shí)間更多，因此文獻(xiàn)[4]提出了改進(jìn)的快速全局K-means聚類算法，該算法提出了一種新的簇內(nèi)中心判斷指標(biāo)參數(shù)bi替換全局K-means算法的簇內(nèi)平方誤差函數(shù)E，減少了算法的計(jì)算量.

1 K-means算法

傳統(tǒng)K-means算法的規(guī)則：從原始數(shù)據(jù)中隨機(jī)選取K個(gè)初始聚類簇中心點(diǎn)，然后按照數(shù)據(jù)的最短距離點(diǎn)的原則(歐式距離)，將原始數(shù)據(jù)集中的點(diǎn)分配給最近的簇中心.分配完所有的數(shù)據(jù)點(diǎn)后，在每個(gè)已生成的簇中，計(jì)算簇中點(diǎn)集的質(zhì)心點(diǎn)，以所有數(shù)據(jù)的平均值點(diǎn)作為新的聚類簇中心點(diǎn).重復(fù)迭代計(jì)算，直到簇中心點(diǎn)位置收斂，收斂的判斷方式一般采用簇內(nèi)誤差平方和函數(shù).此時(shí)可判斷為最佳聚類中心點(diǎn)，進(jìn)行最后的聚類，聚類結(jié)束[5].具體流程如下：

Step 1 初始化：從待聚類的數(shù)據(jù)集中隨機(jī)選擇k個(gè)聚類中心點(diǎn)，c1c2...ck.

Step 2 計(jì)算除聚類中心點(diǎn)外其他的數(shù)據(jù)到這k個(gè)簇中心點(diǎn)的距離，并將該數(shù)據(jù)分配到距離最近的簇中.

Step 3 計(jì)算簇中點(diǎn)集的質(zhì)心點(diǎn)，質(zhì)心點(diǎn)定義為所有數(shù)據(jù)點(diǎn)的均值點(diǎn)，再次確定k個(gè)簇的聚類中心，并根據(jù)誤差平方和公式計(jì)算相應(yīng)的評(píng)價(jià)函數(shù)值.

Step 4 當(dāng)2次的評(píng)價(jià)函數(shù)值之差小于ε(ε是一個(gè)人為定義的數(shù)值)，或者到達(dá)設(shè)定的最大迭代次數(shù)，可以認(rèn)為算法收斂，此時(shí)算法停止.否則轉(zhuǎn)步驟2.

2 全局K-means聚類算法

全局K-means聚類算法[5]用一種遞增式的方法來(lái)選擇一個(gè)新的簇的最佳初始聚類中心.具體過(guò)程如下：

將一組數(shù)據(jù)集X={x1,x2,...,xn}，xi∈RD(i=1,2,...,N)，分為k個(gè)簇，聚類中心分別為(c1,c2...,ck)，形成的聚類簇為(M1,M2,...Mk).

Step 2 終止條件：k=k+1；若k>K，初始中心點(diǎn)的選擇結(jié)束.

3 快速全局K-means聚類算法

快速全局K-means聚類算法，在不影響聚類效果的前提下，大大的減少了全局K-means聚類算法的算法耗時(shí).它的改進(jìn)之處在于，定義了一個(gè)新的參數(shù)bi代替了簇內(nèi)平方誤差和函數(shù)E，通過(guò)減少算法的計(jì)算量來(lái)提高聚類速度.

(1)

其中，bi表示的是相比較數(shù)據(jù)集中的其他點(diǎn)，xi作為簇內(nèi)中心點(diǎn)時(shí)，得到的簇內(nèi)平方和的差值.該差值越大，表示對(duì)應(yīng)的E值越小.該算法流程與全局K-means聚類算法基本一致，只需將選擇下一簇內(nèi)初始中心點(diǎn)的條件換為bi值，選取使bi值最大的點(diǎn)作為下個(gè)簇的初始中心點(diǎn).

4 改進(jìn)的DGK-means算法

針對(duì)全局K-means聚類算法和快速全局K-means聚類算法在選擇下一簇的聚類中心點(diǎn)時(shí)，需要對(duì)數(shù)據(jù)集中所有的數(shù)據(jù)點(diǎn)逐一計(jì)算E值并進(jìn)行對(duì)比，這一過(guò)程中存在很多不可能作為備選點(diǎn)的數(shù)據(jù)點(diǎn)，比如數(shù)據(jù)集的邊緣孤立點(diǎn)，數(shù)據(jù)中的噪聲點(diǎn)等.對(duì)于這些噪聲點(diǎn)的計(jì)算屬于無(wú)用功，反而增加了算法的計(jì)算量.基于此問(wèn)題，提出了一種基于高密度數(shù)[6-7]的全局K-means聚類算法.

該算法旨在將N個(gè)數(shù)據(jù)點(diǎn)依靠其各個(gè)點(diǎn)的密度數(shù)分類，將高密度數(shù)的數(shù)據(jù)點(diǎn)提取出來(lái)，同時(shí)剔除低密度點(diǎn).剔除的低密度點(diǎn)即是該數(shù)據(jù)集中相對(duì)的離散點(diǎn).將高密度數(shù)的數(shù)據(jù)聚集形成新的數(shù)據(jù)集合Data1.該部分也提出了一個(gè)依據(jù)密度級(jí)來(lái)確定聚類個(gè)數(shù)的想法，依靠密度等級(jí)的劃分將該數(shù)據(jù)集劃分成相應(yīng)個(gè)數(shù)的聚類簇.

密度數(shù)：點(diǎn)在其鄰域范圍R內(nèi)點(diǎn)的個(gè)數(shù).

Density(xi)={P∈X|dist(xi,p)≤R}.

(2)

改進(jìn)流程圖：

5 實(shí)驗(yàn)仿真

本實(shí)驗(yàn)仿真選用了UCI數(shù)據(jù)庫(kù)中的4個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對(duì)比，證明了本文所提出的DGK-means聚類算法，比全局K-means算法和快速全局K-means算法，聚類耗時(shí)更短[8-9].并且選擇了分類適確性指標(biāo)(davis-bouldin idex，DB)，簡(jiǎn)稱為DB值，來(lái)衡量聚類效果.DB值用來(lái)衡量簇內(nèi)和簇間的關(guān)系.DB值越小，意味著簇內(nèi)數(shù)據(jù)之間的距離越小，相互聯(lián)系度高，還表示簇間的距離越大，聚類結(jié)果越好.

(3)

本實(shí)驗(yàn)采取了4組從UCI數(shù)據(jù)庫(kù)中下載的數(shù)據(jù)集，見(jiàn)表1.對(duì)每一組數(shù)據(jù)用3種聚類算法分別運(yùn)行20次，并求得均值時(shí)間作比較.同時(shí)計(jì)算每一個(gè)算法的DB值，來(lái)衡量算法的穩(wěn)定性，判斷聚類效果的優(yōu)劣.

表1 數(shù)據(jù)集

圖2為IRis數(shù)據(jù)的高密度數(shù)點(diǎn)集，圖3為本文所提的DGK-means算法對(duì)IRIS數(shù)據(jù)集的聚類結(jié)果圖，圖4為GK-means，F(xiàn)GK-means，和DGK-means算法針對(duì)Iris數(shù)據(jù)集，運(yùn)行所需時(shí)間的對(duì)比圖.取20次運(yùn)行時(shí)間的均值做對(duì)比如表2所示，本文所提的DGK-means算法用時(shí)分別近似于全局K-means算法和快速全局K-means算法的51.64%和71.68%.同時(shí)本文所提的改進(jìn)算法的DB值與其他2種算法相比，差距較小，可以保證聚類效果的一致性.

表2 3種算法對(duì)Iris數(shù)據(jù)集的運(yùn)行時(shí)間s

圖5為Imports-85數(shù)據(jù)集的高密度數(shù)點(diǎn)集，圖6為本文所提的DGK-means算法對(duì)Imports-85數(shù)據(jù)集的聚類結(jié)果圖，圖7為GK-means，F(xiàn)GK-means，和DGK-means算法針對(duì)Imports-85數(shù)據(jù)集，運(yùn)行所需時(shí)間的對(duì)比圖.取20次運(yùn)行時(shí)間的均值做對(duì)比如表3所示，本文所提的DGK-means算法用時(shí)分別近似于全局K-means算法和快速全局K-means算法的34.7%和56.34%.

圖8為WDBC數(shù)據(jù)的高密度數(shù)點(diǎn)集，圖9為本文所提的DGK-means算法對(duì)WDBC數(shù)據(jù)集的聚類結(jié)果圖，圖10為GK-means，F(xiàn)GK-means，和DGK-means算法針對(duì)WDBC數(shù)據(jù)集，運(yùn)行所需時(shí)間的對(duì)比圖.取20次運(yùn)行時(shí)間的均值做對(duì)比如表4所示，本文所提的DGK-means算法用時(shí)分別近似于全局K-means算法和快速全局K-means算法的15.08%和30.94%.

表3 3種算法對(duì)Imports-85數(shù)據(jù)集的運(yùn)行時(shí)間s

表4 3種算法對(duì)WDBC數(shù)據(jù)集的運(yùn)行時(shí)間 s

圖11為Mice protein expression Data Set數(shù)據(jù)的高密度數(shù)點(diǎn)集，圖12為本文所提的DGK-means算法對(duì)Mice protein expression Data Set的聚類結(jié)果圖，圖13為GK-means，F(xiàn)GK-means，和DGK-means算法針對(duì)Mice protein expression Data Set數(shù)據(jù)集，運(yùn)行所需時(shí)間的對(duì)比圖.取20次運(yùn)行時(shí)間的均值做對(duì)比如表5所示，本文所提的DGK-means算法用時(shí)分別近似于全局K-means算法和快速全局K-means算法的13.98%和29.4%.

表5 3種算法對(duì)Mice protein expression Data Set的運(yùn)行時(shí)間 s

綜上分析，在不影響最終聚類效果的前提下，本文所提出的DGK-means算法，對(duì)比全局K-means算法和快速全局K-means算法，有效地減少了算法的運(yùn)行時(shí)間.

6 結(jié)語(yǔ)

本文在學(xué)習(xí)全局K-means聚類算法的過(guò)程中，提出了一種縮小備選數(shù)據(jù)點(diǎn)的改進(jìn)算法DGK-means聚類算法.該方法通過(guò)定義高密度數(shù)的概念，縮小了作為備選的下一簇的初始中心點(diǎn)點(diǎn)集，減少了算法的迭代計(jì)算次數(shù).通過(guò)UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)的4組數(shù)據(jù)測(cè)試, 驗(yàn)證了本文提出的DGK-means算法在保持聚類效果穩(wěn)定的情況下，聚類用時(shí)少于全局K-均值聚類算法和快速全局K-均值聚類算法，提高了算法的聚類效率.