基于距離和權(quán)重改進的K-means算法

王子龍，李 進，宋亞飛

1.空軍工程大學(xué) 研究生院，西安 710051

2.空軍工程大學(xué) 防空反導(dǎo)學(xué)院，西安 710051

1 引言

從海量數(shù)據(jù)中通過一定方法搜尋到隱藏于其中的信息的技術(shù)稱為數(shù)據(jù)挖掘（Data Mining）技術(shù)[1]，在大數(shù)據(jù)、云計算高速發(fā)展的今天數(shù)據(jù)挖掘技術(shù)得到了廣泛的應(yīng)用。聚類是數(shù)據(jù)挖掘的一種方法，通過一定過程將數(shù)據(jù)集分為多個簇，簇內(nèi)數(shù)據(jù)之間的相似度高，簇間數(shù)據(jù)之間的相似度低[2]。根據(jù)聚類手段的差異，聚類算法可分為劃分聚類、層次聚類、基于密度的聚類、基于網(wǎng)格的聚類和基于模型的聚類[3]。

由MacQueen J[4]提出的K-means 算法是最廣泛使用的聚類算法[5]，它是一種劃分式聚類算法。經(jīng)典K-means聚類算法具有一定的局限性，由于算法的初始聚類中心是隨機設(shè)置的，聚類結(jié)果不穩(wěn)定而且易陷入局部最優(yōu)，結(jié)果易受噪聲點影響；在聚類之前需要用戶預(yù)先設(shè)定K值，算法的自適應(yīng)性較差[6]。

近年來大量國內(nèi)外學(xué)者在經(jīng)典K-means算法的基礎(chǔ)上對其進行了改進。Huang等人[7]提出了一種名為WKM（WeightedK-Means）的算法，給各個特征取不同的權(quán)重，用特征加權(quán)進行中心點的選擇，綜合考慮了不同維度數(shù)據(jù)對聚類結(jié)果的影響，但并未說明特征權(quán)重和特征值的尺度之間的關(guān)系。左進等人[8]提出依據(jù)數(shù)據(jù)的緊密性來排除數(shù)據(jù)集中離散點的影響，均勻選擇初始聚類中心，但這種方法仍需手動確定K值。朱二周[9]等人提出了一種ZK-means 算法，初始聚類中心選的是數(shù)據(jù)集中密度較高的點，但后面未考慮噪點的影響。張素潔等人[10]根據(jù)樣本集中的最遠(yuǎn)距離和樣本密度來對中心點進行選取，然后綜合SSE 值最終得出最優(yōu)的K值，該算法獲得了較高的聚類準(zhǔn)確率，但時間復(fù)雜度較高。Zhang等人[11]提出了DCK-means算法，加入了Canopy的思想，同時在尋找初始點的過程中又結(jié)合了樣本密度，在處理低密度區(qū)域時效果良好，但可能在聚類的過程中將離群點歸為一個類，影響了聚類效果。錢雪忠等人[12]在密度峰值算法的基礎(chǔ)上引入了K近鄰思想來確定數(shù)據(jù)點的局部密度，然后提出了一種新的自適應(yīng)聚合策略，有效提高了聚類準(zhǔn)確度和質(zhì)量，但是在此過程中引入了較高的時間復(fù)雜度，不適合在大型數(shù)據(jù)集上使用。王義武等人[13]運用空間投影的思想，將特征空間劃分為聚類空間和噪聲空間，并舍棄噪聲空間，而聚類空間密度更高維度更小，使得算法時間消耗減小，但是當(dāng)數(shù)據(jù)集特征維度高且稀疏時，算法可能找不到最優(yōu)子空間。郭永坤[14]等人引入了高密度優(yōu)先聚類的思想，提高了密度差異較大數(shù)據(jù)集的聚類效果，并且增強了算法的穩(wěn)定性，但該方法未考慮孤立點存在的情況，而且在密度差異較小的數(shù)據(jù)集上的聚類效果一般。

針對上述部分改進K-means算法存在對噪點敏感、準(zhǔn)確率不高以及時間消耗大的問題，本文以密度峰值算法思想為基礎(chǔ)，并根據(jù)前人的研究經(jīng)驗，提出一種基于距離和權(quán)重改進的K-means算法，權(quán)重的計算綜合了樣本密度（Sample Density）、簇內(nèi)平均距離（Mean Distance within the Cluster）和簇間距離（Distance between the Clusters），并且樣本距離的計算采用的是加權(quán)的歐氏距離，加大了數(shù)據(jù)屬性之間的區(qū)分程度，減少了異常點的影響，然后通過計算得到的樣本密度、樣本權(quán)值和距離來選擇初始聚類中心，得到K-means聚類算法的初始輸入?yún)?shù)，這個過程排除了孤立點的影響，有效解決了經(jīng)典K-means 算法的抗噪性差以及易陷入局部最優(yōu)的缺點，并且提高了算法的穩(wěn)定性。在UCI數(shù)據(jù)集上測試實驗結(jié)果表明，本文的改進K-means算法聚類準(zhǔn)確度和效率更高。

2 改進K-means算法

2.1 經(jīng)典K-means算法

經(jīng)典K-means聚類算法的基本思想是：輸入聚類數(shù)目k之后，首先從數(shù)據(jù)集中隨機選取k個樣本點作為初始聚類中心，然后計算各個樣本點分別到k個初始聚類中心的距離，將樣本按照距離最小原則歸類，形成k個簇，再計算各個簇的平均值得到新的聚類中心，不斷重復(fù)上述過程，直到聚類中心不再發(fā)生變化或者迭代次數(shù)達到設(shè)定的值之后，算法結(jié)束。

K-means 算法在計算樣本之間距離時采用的一般是歐氏距離[15]，算法復(fù)雜度較小，適用于大型數(shù)據(jù)集，計算公式如下：

其中，xi={xi1,xi2,…,xim}和xj={xj1,xj2,…,xjm}為任意兩個維度等于m的樣本點，xip表示樣本i對應(yīng)第p個維度的具體取值。

2.2 基于距離和權(quán)重改進的K-means算法

2.2.1 相關(guān)概念

給定數(shù)據(jù)集D={x1,x2,…,xn}，其中的每個樣本點可表示為xi={xi1,xi2,…,xim}，1 ≤i≤n，樣本元素的維度為m。

定義1計算距離時樣本點不同維度數(shù)據(jù)的權(quán)值[16]：

為了加大數(shù)據(jù)屬性之間的區(qū)分程度，本文參考文獻[16]中的權(quán)值計算公式來計算得到不同維度數(shù)據(jù)的權(quán)值。式（2）為維度權(quán)值計算公式。其中，xid是第i個樣本數(shù)據(jù)中的第個分量值的大??；表示樣本數(shù)據(jù)集中各個數(shù)據(jù)點的第d個分量的平均值，引入的權(quán)值在一定程度上能反應(yīng)樣本集整體的數(shù)據(jù)分布特征。

定義2維度加權(quán)后的歐氏距離如公式（3）所示：

式中,dw(xi,xj)是樣本xi和樣本xj在m維向量空間下維度加權(quán)后計算出來的的歐氏距離，后面簡寫為dwij，xid和xjd分別是在向量空間第d維下的樣本點xi和樣本點xj的數(shù)據(jù)值。

觀察式（3），可以看出在引入屬性權(quán)值之后，新的歐氏距離計算公式使得正常的數(shù)據(jù)與聚類中心的距離變小，而使得異常點與聚類中心的距離變大，從而減少異常點的影響，并且會使得原本不易區(qū)分的數(shù)據(jù)變得更為突出，起到了類似于放大差異的效果，有利于后面的聚類計算[16]。本文后面提到的樣本之間的距離指的都是維度加權(quán)過的歐氏距離。

定義3數(shù)據(jù)集D的平均樣本距離公式[11]為：

定義4數(shù)據(jù)集中樣本點i的密度[17]為：

定義的樣本密度直觀解釋如圖1所示。

圖1 樣本點密度定義圖解

定義5由定義4可知，ρ(i)的實際含義即為以樣本點xi為圓心，以MeanDis(D)為半徑的圓內(nèi)包含的樣本點的數(shù)目，將這些點歸為一個類簇，它們之間的平均距離定義為：

定義6定義類簇之間的距離si，表示樣本xi與另一個具有更高點密度的樣本xj之間的距離。如果樣本xi的密度不是最大，將si定義為min(dwij)，如果密度最大的樣本點是xi，則將si定義為max(dwij)；數(shù)學(xué)表達式如下：

si的計算原則如圖2所示。

圖2 樣本的簇間距離選擇原則

定義7定義樣本點xi的權(quán)重為：

由式（8）可以看出，ρi越大，即樣本i周圍點越密，則權(quán)重wi越大；si越大，即簇間距離大，則權(quán)重wi越大；ai越大，即簇內(nèi)平均距離越大，一定程度上反映了簇內(nèi)點樣本分布比較松散，則權(quán)重wi越小。

定義8定義參數(shù)τi為：

其中，dw(xi,ci-1)是D中待選擇樣本點xi到上一個已選擇的初始聚類中心ci-1的距離。由τi定義式可以看出，下一個待選擇樣本點到上一個中心點越遠(yuǎn)、權(quán)重越大，則參數(shù)τi越大，聚類中心就更可能在其附近產(chǎn)生，很好地反映了數(shù)據(jù)集D的全局分布特征，后面根據(jù)τi一步步選出來的初始聚類中心也減少了算法的迭代次數(shù)。

2.2.2 算法思想描述

算法思想為：首先由上面定義1 至定義7 計算出樣本密度、樣本權(quán)重，選擇密度最大的點作為第一個聚類中心，這樣可以有效避免孤立點、噪點的影響，然后計算當(dāng)前聚類中心與數(shù)據(jù)集中所有點的距離，與它距離在MeanDist(D)之內(nèi)的點不參加后面聚類中心的選擇，然后將這個距離乘以相對應(yīng)點的權(quán)重，即得到計算定義8中參數(shù)τi的值，選出其中的最大值，對應(yīng)的點作為第二個初始聚類中心，然后刪去距其MeanDist(D)之內(nèi)的樣本。重復(fù)上述過程直至數(shù)據(jù)集為空集，即得到k個初始聚類中心。

第一個聚類中心選的是密度最大的點，而后面聚類中心的選擇依靠τi的值，由τi的定義式（8）、（9）可以看出，后面依次選出來的聚類中心都是密度較大，簇間距離大，簇內(nèi)平均距離小的點，這就排除了像經(jīng)典K-means 算法隨機選擇初始聚類中心那樣選到噪點和孤立點的可能性，也符合密度峰值聚類算法[18（]Density Peaks Clustering algorithm，DPC）的假設(shè)：一個數(shù)據(jù)集的聚類中心由低局部密度的數(shù)據(jù)點包圍，而這些低局部密度的點距其他高局部密度的點的距離較大。

初始點尋找過程如圖3和圖4所示。

圖3 第二個聚類中心的尋找

圖4 第三個聚類中心的尋找

2.2.3 算法流程

傳統(tǒng)的K-means聚類算法需要手動輸入聚類數(shù)目，并且初始聚類中心也是隨機選取的，缺乏自適應(yīng)性以及聚類結(jié)果的穩(wěn)定性。本文通過以下步驟，可以自動確定初始聚類中心和聚類數(shù)目，具體步驟如下：

步驟1對于給定的數(shù)據(jù)集D，由公式（5）計算得到數(shù)據(jù)集內(nèi)所有樣本的密度，由公式（8）計算得到數(shù)據(jù)集D內(nèi)所有樣本元素的權(quán)重w。第一個初始聚類中心選擇D中密度最大的對象c1，將之添加到聚類中心點的集合C中，此時C={c1}，然后將D中所有距離點c1小于MeanDist(D)的點刪除。

步驟2選擇具有最大τi=wi?dw(xi,c1)值的點xi作為第2 個初始聚類中心，記為c2，將c2添加到集合C中，此時C={c1,c2}，與第一步類似的，將D中所有距離c2小于MeanDist(D)的點刪除。

步驟 3選擇具有最大τi=wi′?dw(xi′,c2)值的點xt′作為第3 個初始聚類中心，記為c3，將c3添加到集合C中，此時C={c1,c2,c3} ，將D中所有距離c3小于MeanDist(D)的點刪除，類似地不停重復(fù)上述過程，直到數(shù)據(jù)集D變?yōu)榭占?。此時C={c1,c2,…,ck}，由此得到k個初始聚類中心，即集合C中的樣本點。

步驟4以上面步驟得到的初始聚類中心和聚類數(shù)為輸入，對給定數(shù)據(jù)集D進行K-means 聚類運算，直到聚類中心不再變化。

步驟5輸出最終聚類結(jié)果。

算法基于距離和權(quán)重改進的K-means算法

輸入：Data setsD

輸出：Clustering results

1.initialize the ArrayList；

2.computeMeanDist(D)；// 計算平均樣本距離

3.FOR（each samplei∈D）{

4.computeρ(i)；//計算樣本密度

5.}

6.FOR（each samplei∈D） {

7.computeai；

8.computesi；

9.computewi；//計算樣本權(quán)重

10.}

11.select Centerc1←sample Maxρ(i)；

12.remove ClusterC1fromD；//找到第一個初始聚類中心并從D中刪除該簇內(nèi)所有點

13.WHILE（data setsD!=null）{

14.Centerci←sample（Maxτi）i；

15.remove ClusterCifromD；//從D中找到令式子wi?dw(xi,ci-1)最大化的點i作為下一個初始聚類中心，并刪除該簇內(nèi)所有點，不斷重復(fù)直到數(shù)據(jù)集D為空

16.}

17.END WHILE；

18.PRINTF（K，Initial CenterC）；//輸出得到K個初始聚類中心

19.K-means inpu（tD,K，Initial CenterC）；//將得到的初始中心點集合作為K-means算法的輸入

20.WHILE（new center!=original center）{

21.FOR（each samplei∈D）{

22.FOR（each centercj∈C）{

23.computedw(xi,xk)；

24.}

25.IF（dw(xi,xk)=Mindw(xi,xj)）{

26.Centerck←samplei；//更新聚類中心點

27.}

28.}END FOR；

29.compute NEW Centerci=

30.Mean（sample（i&&（i∈Clusterci）））；

31.}END WHILE；

32.PRINTF（ClusterCi）；

改進后的K-means算法流程圖如圖5所示。

圖5 基于距離和權(quán)重改進的K-means算法流程圖

2.3 算法時間復(fù)雜度

理論上傳統(tǒng)K-means算法的時間復(fù)雜度是O(nkT1)[19]，其中n為輸入樣本的個數(shù)，k是聚類數(shù)目，T1是算法聚類過程的迭代次數(shù)；WK-means算法引入了特征加權(quán)，時間復(fù)雜度是O(nm2l+nkT2)，其中m是樣本維數(shù)，l是尋找初始點的迭代次數(shù)，T2是進行K-means聚類迭代的次數(shù)；ZK-means算法利用密度來確定初始聚類中心，而聚類過程和K-means 相同，其時間復(fù)雜度是O(n2kT3)；DCK-means 算法的時間復(fù)雜度為O(n2+nS+nkT4)，其中O(n2)是在計算密度的過程中引入的，S是尋找初始點的迭代次數(shù)，大小大約等于k；本文的改進K-means算法的時間復(fù)雜度是O(n2+nl+nkT5) ，O(nl) 是按步驟2 到步驟3 過程依次尋找初始聚類中心時引入的，l是初始中心點尋找過程中的迭代次數(shù)，數(shù)量級與k相當(dāng)，T5是在輸入初始聚類中心的前提下K-means 算法的迭代次數(shù)。在將本文提出的方法得到的初始聚類中心作為初始輸入?yún)?shù)后，迭代次數(shù)T5將大大小于傳統(tǒng)K-means 算法的迭代次數(shù)T1。這一點從后面實驗部分的不同算法時間消耗對比可以看出。用本文的改進算法處理小中型數(shù)據(jù)時，在時耗上具有明顯優(yōu)勢，當(dāng)樣本數(shù)量增大到一定程度時，本文的改進算法時間復(fù)雜度接近O(n2)。近幾年提出的結(jié)合了密度的改進K-means算法的時間復(fù)雜度都在O(n2)和O(n3)之間[20]，由以上時間復(fù)雜度的理論分析可以看出，用本文的改進算法處理數(shù)據(jù)在時耗上更有優(yōu)勢，后面實驗部分證實了這一點。

3 仿真實驗

3.1 實驗數(shù)據(jù)

本文仿真實驗中采用的是UCI數(shù)據(jù)集，從其網(wǎng)站可以獲得，UCI是加州大學(xué)提出的一個專門用來測試聚類效果的標(biāo)準(zhǔn)測試數(shù)據(jù)集[21]。本次實驗，選用UCI的三個子數(shù)據(jù)集 Iris、Waveform 和 Glass，其中 Iris 數(shù)據(jù)集最簡單，Waveform 和Glass 數(shù)據(jù)集結(jié)構(gòu)相對更復(fù)雜，目的是為了更全面分析算法的有效性，數(shù)據(jù)集具體情況如表1所示，部分原始數(shù)據(jù)如圖6所示。

表1 實驗所用數(shù)據(jù)集的樣本分布情況

圖6 UCI數(shù)據(jù)集的部分?jǐn)?shù)據(jù)示例

3.2 實驗數(shù)據(jù)集的預(yù)處理

本次實驗環(huán)境為：Intel?Core i7-8750H、16 GB內(nèi)存、GTX1060顯卡、Windows 10操作系統(tǒng)、Matlab R2016a。

原始數(shù)據(jù)在輸入到算法之前必須經(jīng)過數(shù)據(jù)預(yù)處理，一是因為原始數(shù)據(jù)不經(jīng)過預(yù)處理一般情況下無法輸入到算法中；二是即便可以順利輸入，若是給算法輸入一個完全原始的數(shù)據(jù)集來測試，那么無論這個算法的理論準(zhǔn)確率有多么高，實驗結(jié)果也一般不會很理想；三是避免出現(xiàn)不同維度數(shù)據(jù)“大數(shù)吃小數(shù)”現(xiàn)象[22]，造成結(jié)果失真，因此，數(shù)據(jù)集的預(yù)處理工作是必不可少的。

3.2.1 數(shù)據(jù)集類別編號

Iris 數(shù)據(jù)集分為Iris-setosa（山鳶尾）、Iris-versicolor（變色鳶尾）、Iris-virginia（維吉尼亞鳶尾），原始數(shù)據(jù)集中它們的類別標(biāo)號是英文單詞，位于最后一列，為了便于實驗，分別將三類數(shù)據(jù)編號為1、2、3。

Waveform數(shù)據(jù)集本身自有類別編號0、1、2，在這里為了統(tǒng)一改為1、2、3。

Glass 數(shù)據(jù)集原本類別編號為1、2、3、5、6、7（類別4的樣本數(shù)目是0 個），在這里為了便于實驗直接刪除類別4，將編號重新設(shè)置為1、2、3、4、5、6，并刪除作為數(shù)據(jù)序號標(biāo)識的第一列數(shù)據(jù)。

3.2.2 數(shù)據(jù)標(biāo)準(zhǔn)化

式中，AVGp是所有的n個樣本第p個屬性的平均值，Sp是所有的n個樣本第p個屬性的平均絕對偏差，記xip′為標(biāo)準(zhǔn)化后樣本xi的第p維度的值[23]。

3.2.3 數(shù)據(jù)歸一化

數(shù)據(jù)經(jīng)過標(biāo)準(zhǔn)化后，再將這些數(shù)值放到[0，1]區(qū)間[24]稱為數(shù)據(jù)歸一化，計算公式如下：

其中，xip″即為數(shù)據(jù)標(biāo)準(zhǔn)歸一化后樣本xi的第p維度的值，xpmin′為n個樣本標(biāo)準(zhǔn)化后的第p維度數(shù)值最小的值，xpmax′為n個樣本標(biāo)準(zhǔn)化后的第p維度數(shù)值最大的值。

3.3 聚類效果評價指標(biāo)

大部分相關(guān)文獻都將準(zhǔn)確率[25]或者誤分率作為聚類結(jié)果好壞的評價指標(biāo)，所以本文也將準(zhǔn)確率作為評價聚類算法優(yōu)劣的指標(biāo)，準(zhǔn)確率的計算公式如下：

其中，是聚類結(jié)果中第i類樣本的數(shù)目，Ci是第i類樣本的真實數(shù)目。

除此之外，本文還加入了相對度量中的三種有效性評價指標(biāo)對聚類效果好壞進行度量，分別為：

（1）分割系數(shù)PC[26]

PC的取值范圍為[1/k,1]，值越接近于1，說明劃分結(jié)果越清晰，聚類效果越好；反之，PC值接近1/k時，說明劃分結(jié)果模糊。

（2）劃分熵系數(shù)PE[27]

PE取值范圍為[0,logak]，值越接近0，說明聚類效果越好；反之當(dāng)PE值接近logak時，說明算法無法正確進行聚類。

（3）Xie-Beni指標(biāo)[28]

本文選取的這三種聚類有效性評價指標(biāo)很有代表性，現(xiàn)有的其他指標(biāo)大部分都是這三種指標(biāo)的變形。

3.4 實驗結(jié)果與分析

本次實驗，在UCI 的三個子數(shù)據(jù)集Iris、Waveform和 Glass 上對經(jīng)典K-means 算法、WK-means 算法、ZK-means算法、DCK-means算法和本文算法進行測試和對比，每種算法分別運行50 次，結(jié)果取平均值。圖7 為五種算法在實驗數(shù)據(jù)集上的平均聚類準(zhǔn)確率。

表2至表4是五種不同的算法在UCI數(shù)據(jù)集上的測試結(jié)果。

表2 算法在Iris數(shù)據(jù)集上的聚類結(jié)果指標(biāo)

表3 算法在Waveform數(shù)據(jù)集上的聚類結(jié)果指標(biāo)

表4 算法在Glass數(shù)據(jù)集上的聚類結(jié)果指標(biāo)

3.4.1 聚類效果分析

從圖7的準(zhǔn)確率指標(biāo)折線圖可以直觀看出，幾種不同算法在Iris數(shù)據(jù)集上表現(xiàn)最好，在Glass數(shù)據(jù)集上表現(xiàn)最差，而兩者數(shù)據(jù)集大小基本相同，可能原因是Glass數(shù)據(jù)集的類別數(shù)目和屬性數(shù)目明顯高于Iris 數(shù)據(jù)集的，Glass 不同類別的樣本差異較小，數(shù)據(jù)分布分隔不是很明顯。從表2 至表4 聚類結(jié)果四種指標(biāo)的對比可以看出，本文提出的算法各項指標(biāo)都是最優(yōu)的，在三個UCI數(shù)據(jù)集上平均準(zhǔn)確率比經(jīng)典K-means算法高24.87%，比WK-means 算法高12.90%，比ZK-means 算法高7%，比DCK-means 算法高1.43%，總體上性能上接近但高于DCK-means算法，因為兩種算法在尋找初始點的過程中都考慮了距離和密度，相比于其他算法更加具有全局性，而本文算法為了加大數(shù)據(jù)屬性間的區(qū)分程度還引入了維度加權(quán)的歐氏距離，以及在初始聚類中心的尋找過程中引入?yún)?shù)τi，使得樣本點之間的距離度量更準(zhǔn)確，找到的初始點更能代表各類的大致分布，最終使得聚類結(jié)果更加優(yōu)異。

3.4.2 改進算法的收斂性分析

當(dāng)輸入數(shù)據(jù)集一定時，改進K-means聚類算法的收斂速度和迭代次數(shù)主要取決于初始聚類中心的選取。

圖8是本文算法和另外幾種算法的聚類時耗對比，本文改進算法在3 個UCI 數(shù)據(jù)集上的時間消耗較其他四種算法有優(yōu)勢，與2.3 節(jié)中時間復(fù)雜度的理論分析基本一致。

圖8 算法的平均時耗對比

表5顯示的是算法的迭代次數(shù)，可以看出改進初始聚類中心的選擇方法后，迭代次數(shù)均有所減少，其中本文改進算法的迭代次數(shù)要小于經(jīng)典K-means算法、WK-means 算法、ZK-means 算法和 DCK-means 算法。根據(jù)文獻[6]提出的初始聚類中心選擇原理，聚類計算中用距離來度量數(shù)據(jù)對象之間的相似性，距離越小則相似性越高，對于密度不均勻的數(shù)據(jù)集，密度越高的部分越容易聚在一起，若能夠找到k個分別代表相似程度高的那部分?jǐn)?shù)據(jù)集合的聚類中心，那么將更加有利于算法收斂。本文的改進K-means 算法優(yōu)化了初始聚類中心的選取過程，在密度峰值原理的基礎(chǔ)上結(jié)合了數(shù)據(jù)集局部與宏觀特征，并且采用加權(quán)距離減少了異常因素的影響，較其他改進算法考慮得更全面，選出來的初始點更符合上述初始聚類中心選擇原理，從而減少了迭代次數(shù)，最終有利于減少運行時間。

表5 算法平均迭代次數(shù)

綜上所述，本文提出的改進K-means算法的初始聚類中心選擇方法較WK-means 算法、ZK-means 和DCK-means 的有優(yōu)勢，聚類結(jié)果的聚類精度更高且速度較快。從原理上看其優(yōu)勢在于：（1）采用維度加權(quán)的歐氏距離，減少了離群點的影響，增大了數(shù)據(jù)之間的區(qū)分度。（2）第一個聚類中心選的是密度最高的點，后面的聚類中心選擇根據(jù)的是到上一個聚類中心的距離以及剩余點的權(quán)重，這個過程選出的點符合密度峰值原則，而噪點由于權(quán)重過小無法被選為聚類中心，避免了陷入局部最優(yōu)。（3）由2.3 節(jié)時間復(fù)雜度的分析可知，理論時間復(fù)雜度相較其他改進算法較低。實驗過程中還發(fā)現(xiàn)，測試傳統(tǒng)K-means 算法時，對同一組輸入數(shù)據(jù)，前后運行兩次程序，輸出的結(jié)果是不同的，而本文的改進算法在相同前提下多次實驗輸出結(jié)果穩(wěn)定，這是因為傳統(tǒng)K-means算法初始聚類中心是隨機選取的，無法考慮整體情況，萬一初始聚類中心選到離散點就會陷入局部最優(yōu)解。而本文改進算法的每一步都是經(jīng)過計算可以確定的，不存在隨機性，初始聚類中心點的選擇考慮了數(shù)據(jù)集整體的分布，結(jié)合了樣本密度、權(quán)重和距離，因此排除了孤立點的影響，最終結(jié)果能夠收斂到全局最優(yōu)，避免了陷入局部最優(yōu)解。

4 結(jié)束語

本文所提出的改進K-means算法，在聚類過程中結(jié)合了單個樣本密度、樣本的局部分布以及宏觀分布，距離計算上還采用了維度加權(quán)的歐氏距離，解決了傳統(tǒng)K-means算法的初始聚類中心選擇問題，以及異常數(shù)據(jù)影響聚類效果的問題，并且時間性能也優(yōu)于其他改進算法，最后的仿真實驗結(jié)果表明本文改進后算法的各項性能指標(biāo)更優(yōu)，在聚類精度提高的情況下耗時也有所減少。聚類算法在數(shù)據(jù)爆炸時代應(yīng)用廣闊，根據(jù)前面理論分析，本文算法在處理中小型數(shù)據(jù)時由于明顯減少了聚類過程中的迭代次數(shù)，比其他算法在速度上有優(yōu)勢，但在處理大型數(shù)據(jù)時由于尋找初始聚類中心引入了更高階的時間復(fù)雜度，耗時將大于經(jīng)典K-means 算法，這也是下一步需要解決的問題。