基于距離和權(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ù)樣本集中的最遠距離和樣本密度來對中心點進行選取，然后綜合SSE 值最終得出最優(yōu)的K值，該算法獲得了較高的聚類準確率，但時間復(fù)雜度較高。Zhang等人[11]提出了DCK-means算法，加入了Canopy的思想，同時在尋找初始點的過程中又結(jié)合了樣本密度，在處理低密度區(qū)域時效果良好，但可能在聚類的過程中將離群點歸為一個類，影響了聚類效果。錢雪忠等人[12]在密度峰值算法的基礎(chǔ)上引入了K近鄰思想來確定數(shù)據(jù)點的局部密度，然后提出了一種新的自適應(yīng)聚合策略，有效提高了聚類準確度和質(zhì)量，但是在此過程中引入了較高的時間復(fù)雜度，不適合在大型數(shù)據(jù)集上使用。王義武等人[13]運用空間投影的思想，將特征空間劃分為聚類空間和噪聲空間，并舍棄噪聲空間，而聚類空間密度更高維度更小，使得算法時間消耗減小，但是當數(shù)據(jù)集特征維度高且稀疏時，算法可能找不到最優(yōu)子空間。郭永坤[14]等人引入了高密度優(yōu)先聚類的思想，提高了密度差異較大數(shù)據(jù)集的聚類效果，并且增強了算法的穩(wěn)定性，但該方法未考慮孤立點存在的情況，而且在密度差異較小的數(shù)據(jù)集上的聚類效果一般。

針對上述部分改進K-means算法存在對噪點敏感、準確率不高以及時間消耗大的問題，本文以密度峰值算法思想為基礎(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算法聚類準確度和效率更高。

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

2.2.2 算法思想描述

算法思想為：首先由上面定義1 至定義7 計算出樣本密度、樣本權(quán)重，選擇密度最大的點作為第一個聚類中心，這樣可以有效避免孤立點、噪點的影響，然后計算當前聚類中心與數(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相當，T5是在輸入初始聚類中心的前提下K-means 算法的迭代次數(shù)。在將本文提出的方法得到的初始聚類中心作為初始輸入?yún)?shù)后，迭代次數(shù)T5將大大小于傳統(tǒng)K-means 算法的迭代次數(shù)T1。這一點從后面實驗部分的不同算法時間消耗對比可以看出。用本文的改進算法處理小中型數(shù)據(jù)時，在時耗上具有明顯優(yōu)勢，當樣本數(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é)提出的一個專門用來測試聚類效果的標準測試數(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ù)集的部分數(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ù)集來測試，那么無論這個算法的理論準確率有多么高，實驗結(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ù)集中它們的類別標號是英文單詞，位于最后一列，為了便于實驗，分別將三類數(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ù)序號標識的第一列數(shù)據(jù)。

3.2.2 數(shù)據(jù)標準化

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

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

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

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

3.3 聚類效果評價指標

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

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

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

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

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

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

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

（3）Xie-Beni指標[28]

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

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

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

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

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

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

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

3.4.1 聚類效果分析

從圖7的準確率指標折線圖可以直觀看出，幾種不同算法在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é)果四種指標的對比可以看出，本文提出的算法各項指標都是最優(yōu)的，在三個UCI數(shù)據(jù)集上平均準確率比經(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，使得樣本點之間的距離度量更準確，找到的初始點更能代表各類的大致分布，最終使得聚類結(jié)果更加優(yōu)異。

3.4.2 改進算法的收斂性分析

當輸入數(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個分別代表相似程度高的那部分數(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é)果表明本文改進后算法的各項性能指標更優(yōu)，在聚類精度提高的情況下耗時也有所減少。聚類算法在數(shù)據(jù)爆炸時代應(yīng)用廣闊，根據(jù)前面理論分析，本文算法在處理中小型數(shù)據(jù)時由于明顯減少了聚類過程中的迭代次數(shù)，比其他算法在速度上有優(yōu)勢，但在處理大型數(shù)據(jù)時由于尋找初始聚類中心引入了更高階的時間復(fù)雜度，耗時將大于經(jīng)典K-means 算法，這也是下一步需要解決的問題。