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

(1. 云南民族大學 云南省高校信息與通信安全災備重點實驗室，云南 昆明 650500; 2. 云南民族大學 電氣信息工程學院，云南 昆明 650500)

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

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

1 K-means算法

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

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

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

Step 3 計算簇中點集的質心點，質心點定義為所有數(shù)據(jù)點的均值點，再次確定k個簇的聚類中心，并根據(jù)誤差平方和公式計算相應的評價函數(shù)值.

Step 4 當2次的評價函數(shù)值之差小于ε(ε是一個人為定義的數(shù)值)，或者到達設定的最大迭代次數(shù)，可以認為算法收斂，此時算法停止.否則轉步驟2.

2 全局K-means聚類算法

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

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

Step 2 終止條件：k=k+1；若k>K，初始中心點的選擇結束.

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

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

(1)

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

4 改進的DGK-means算法

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

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

密度數(shù)：點在其鄰域范圍R內點的個數(shù).

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

(2)

改進流程圖：

5 實驗仿真

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

(3)

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

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

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

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

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

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

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

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

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

表5 3種算法對Mice protein expression Data Set的運行時間 s

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

6 結語

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