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

王子龍，李 進(jìn)，宋亞飛

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

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

1 引言

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

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

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

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

2 改進(jìn)K-means算法

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

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

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

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

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

2.2.1 相關(guān)概念

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

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

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

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

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

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

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

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

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

圖1 樣本點(diǎn)密度定義圖解

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

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

si的計(jì)算原則如圖2所示。

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

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

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

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

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

2.2.2 算法思想描述

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

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

初始點(diǎn)尋找過(guò)程如圖3和圖4所示。

圖3 第二個(gè)聚類(lèi)中心的尋找

圖4 第三個(gè)聚類(lèi)中心的尋找

2.2.3 算法流程

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

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

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

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

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

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

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

輸入：Data setsD

輸出：Clustering results

1.initialize the ArrayList；

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

3.FOR（each samplei∈D）{

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

5.}

6.FOR（each samplei∈D） {

7.computeai；

8.computesi；

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

10.}

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

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

13.WHILE（data setsD!=null）{

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

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

16.}

17.END WHILE；

18.PRINTF（K，Initial CenterC）；//輸出得到K個(gè)初始聚類(lèi)中心

19.K-means inpu（tD,K，Initial CenterC）；//將得到的初始中心點(diǎn)集合作為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；//更新聚類(lèi)中心點(diǎn)

27.}

28.}END FOR；

29.compute NEW Centerci=

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

31.}END WHILE；

32.PRINTF（ClusterCi）；

改進(jìn)后的K-means算法流程圖如圖5所示。

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

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

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

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

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

3.2.1 數(shù)據(jù)集類(lèi)別編號(hào)

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

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

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

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

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

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

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

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

3.3 聚類(lèi)效果評(píng)價(jià)指標(biāo)

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

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

除此之外，本文還加入了相對(duì)度量中的三種有效性評(píng)價(jià)指標(biāo)對(duì)聚類(lèi)效果好壞進(jìn)行度量，分別為：

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

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

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

PE取值范圍為[0,logak]，值越接近0，說(shuō)明聚類(lèi)效果越好；反之當(dāng)PE值接近logak時(shí)，說(shuō)明算法無(wú)法正確進(jìn)行聚類(lèi)。

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

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

3.4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

3.4.1 聚類(lèi)效果分析

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

3.4.2 改進(jìn)算法的收斂性分析

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

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

圖8 算法的平均時(shí)耗對(duì)比

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

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

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

4 結(jié)束語(yǔ)

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