KNN優(yōu)化的密度峰值聚類(lèi)算法*

黃學(xué)雨，程世超

（江西理工大學(xué)，江西 贛州 341000）

0 引 言

聚類(lèi)算法是一種常用的在數(shù)據(jù)集中尋找簇結(jié)構(gòu)的方法，其目的是使得數(shù)據(jù)集中同一個(gè)簇內(nèi)的數(shù)據(jù)具有最大相似性，不同簇之間具有最大差異性。在不同的科學(xué)領(lǐng)域具有廣泛的應(yīng)用，尤其在無(wú)人監(jiān)督的學(xué)習(xí)場(chǎng)景中有著重要的應(yīng)用[1-4]。根據(jù)聚類(lèi)算法中樣本空間中數(shù)據(jù)點(diǎn)之間目標(biāo)函數(shù)定義方法不同以及各聚類(lèi)簇內(nèi)和簇間的數(shù)據(jù)對(duì)象間的關(guān)系，聚類(lèi)算法一般分為基于劃分的方法、基于層次的方法、基于網(wǎng)格的方法、基于密度的方法和基于模型的方法，其中基于劃分的方法被廣泛研究與應(yīng)用[5]。

基于劃分方法假設(shè)數(shù)據(jù)集可以用有限的聚類(lèi)原型來(lái)表示，這些原型具有各自的目標(biāo)函數(shù)，因此定義一個(gè)點(diǎn)和一個(gè)聚類(lèi)原型之間的差異（或距離）是劃分方法的關(guān)鍵。K-means算法是最流行的一種劃分方法[6]。由于K-means算法的初始聚類(lèi)中心設(shè)置對(duì)聚類(lèi)效果影響較大，因此有效提高初始聚類(lèi)中心的設(shè)置一直是K-means算法的研究熱點(diǎn)。Pelleg和Moore[7]提出了X-means算法，通過(guò)在K-means的每次迭代中對(duì)聚類(lèi)中心進(jìn)行局部決策，并對(duì)其進(jìn)行自我分裂，從而得到更好的聚類(lèi)結(jié)果；Bezdek等[8]結(jié)合數(shù)學(xué)中的隸屬度函數(shù)表示數(shù)據(jù)點(diǎn)屬于類(lèi)簇的概率值，提出了FCM算法，但該算法對(duì)初始聚類(lèi)中心c和柔性參數(shù)m這兩個(gè)參數(shù)較敏感；Khan等[9]提出以數(shù)據(jù)點(diǎn)間的距離均值、標(biāo)準(zhǔn)差等統(tǒng)計(jì)信息作為數(shù)據(jù)點(diǎn)的密度信息，即類(lèi)中心自動(dòng)初始化算法（Cluster Center Initialization Algorithm，CCIA）算法；Redmond等[10]通過(guò)構(gòu)建k-d樹(shù)計(jì)算出數(shù)據(jù)集中數(shù)據(jù)對(duì)象的密度分布情況，并利用數(shù)據(jù)點(diǎn)的密度信息獲取數(shù)據(jù)集的初始聚類(lèi)中心，提高聚類(lèi)精準(zhǔn)性；文獻(xiàn)[11]利用螢火蟲(chóng)優(yōu)化算法的特點(diǎn)優(yōu)化初始聚類(lèi)中心的選擇；文獻(xiàn)[12]引入改進(jìn)的森林優(yōu)化算法提高原始K-means算法的收斂速度和收斂精度；文獻(xiàn)[13]提出基于距離和權(quán)重來(lái)計(jì)算樣本點(diǎn)的密度，并以密度最大的數(shù)據(jù)點(diǎn)作為初始聚類(lèi)中心點(diǎn)；文獻(xiàn)[14]引入二次冪思想預(yù)處理數(shù)據(jù)集，然后計(jì)算樣本點(diǎn)的密度來(lái)初始化聚類(lèi)中心點(diǎn)。盡管目前有大量各種改進(jìn)的K-means聚類(lèi)算法，在一定程度上提高了算法的聚類(lèi)效果和收斂速度，但參數(shù)設(shè)置過(guò)多并且參數(shù)的選擇對(duì)算法的聚類(lèi)效果影響太大。本文提出一種基于K-最近鄰（K-Nearest Neighbor，KNN）優(yōu)化的密度峰值的K-means算法，使用KNN的思想優(yōu)化局部密度，并以樣本數(shù)據(jù)點(diǎn)平均距離代替原始密度峰值算法的截?cái)嗑嚯x，再利用平均局部密度檢測(cè)和去除離群點(diǎn)，最后結(jié)合提出的自適應(yīng)合并策略合并相似類(lèi)簇，從而獲取初始聚類(lèi)中心，提高K-means算法的聚類(lèi)性。

1 密度峰值聚類(lèi)算法介紹

密度峰值聚類(lèi)（Density Peaks Clustering，DPC）算法的典型代表是快速搜索和查找樣本密度峰值的聚類(lèi)算法。DPC[15]算法的基本思想：聚類(lèi)簇中心點(diǎn)的局部密度大于屬于該聚類(lèi)簇所有樣本點(diǎn)的局部密度，并且與其他聚類(lèi)簇中心點(diǎn)距離較遠(yuǎn)。根據(jù)DPC算法這兩個(gè)特點(diǎn)建立決策圖，樣本數(shù)據(jù)點(diǎn)的局部密度 ρi為：

δi表示數(shù)據(jù)樣本點(diǎn)i與比它局部密度更高的點(diǎn)之間的歐式距離，表示為：

如果i=j，則δi定義為：

DPC算法通過(guò)ρi和δi構(gòu)建決策圖來(lái)選取聚類(lèi)中心，再根據(jù)聚類(lèi)中心把剩余樣本數(shù)據(jù)點(diǎn)歸類(lèi)于離其最近的聚類(lèi)簇。

根據(jù)式（1）可知，截?cái)嗑嚯xdc選取值的不同對(duì)DPC聚類(lèi)算法影響很大，并且原始的DPC算法對(duì)于小型數(shù)據(jù)集的聚類(lèi)效果并不好。因此，有文獻(xiàn)提出當(dāng)數(shù)據(jù)規(guī)模較小時(shí)，使用高斯核定義樣本數(shù)據(jù)點(diǎn)的局部密度，公式如下[16]：

在實(shí)際應(yīng)用中是沒(méi)有客觀方式來(lái)度量一個(gè)數(shù)據(jù)集的大小，并且在小數(shù)據(jù)集上使用式（4）來(lái)定義樣本數(shù)據(jù)點(diǎn)的局部密度，截?cái)嗑嚯xdc的大小對(duì)于聚類(lèi)效果影響還是很大，一旦一個(gè)數(shù)據(jù)樣本點(diǎn)聚類(lèi)錯(cuò)誤將會(huì)產(chǎn)生連鎖反應(yīng)，將導(dǎo)致整個(gè)數(shù)據(jù)樣本點(diǎn)聚類(lèi)不佳的情況[17]。為了解決以上原始DPC聚類(lèi)算法的問(wèn)題，本文提出基于KNN優(yōu)化密度峰值算法，使用KNN的思想和一種新的密度定義函數(shù)代替截?cái)嗑嚯xdc來(lái)確定數(shù)據(jù)樣本點(diǎn)的局部密度，并提出一種自適應(yīng)合并策略來(lái)合并相鄰聚類(lèi)簇。

2 改進(jìn)的密度峰值聚類(lèi)KDPC算法

2.1 改進(jìn)的KDPC算法基本思想

由于DPC聚類(lèi)算法易受截?cái)嗑嚯xdc的影響和對(duì)不同大小數(shù)據(jù)集的要使用不同的局部密度函數(shù)，本文通過(guò)使用高斯核函數(shù)，提出基于KNN優(yōu)化的DPC算法。該算法使用KNN獲取K個(gè)數(shù)據(jù)點(diǎn)的最近鄰信息，再利用樣本數(shù)據(jù)點(diǎn)的最近鄰信息定義一種新的局部密度函數(shù)。該密度函數(shù)可以適應(yīng)不同大小數(shù)據(jù)集并且不需要人工設(shè)定截?cái)嗑嚯xdc，并將dc定義為一個(gè)普適性的公式[18]。改進(jìn)的DPC算法減少了人為干預(yù)，并將在各種數(shù)據(jù)集得到更好的聚類(lèi)效果，其改進(jìn)的樣本數(shù)據(jù)點(diǎn)的局部密度度量公式如下：

為了提高聚類(lèi)效果的精確性，減少異常點(diǎn)對(duì)聚類(lèi)效果的影響，在使用改進(jìn)的DPC算法對(duì)樣本數(shù)據(jù)集獲取初始聚類(lèi)中心點(diǎn)之前，需要檢測(cè)和去除樣本數(shù)據(jù)集中的離群點(diǎn)[19]。本文提出以下定義：如果樣本數(shù)據(jù)點(diǎn)的局部密度小于樣本數(shù)據(jù)集的平均局部密度，則標(biāo)記該樣本數(shù)據(jù)點(diǎn)為離群點(diǎn)，即樣本噪聲點(diǎn)。樣本噪聲點(diǎn)的識(shí)別函數(shù)如下：

2.2 自適應(yīng)合并策略?xún)?yōu)化KDPC

為了提高KDPC算法對(duì)樣本數(shù)據(jù)集的聚類(lèi)性能，本文提出一種對(duì)于聚類(lèi)簇的自適應(yīng)合并策略，該策略主要是通過(guò)以下定義把聚類(lèi)簇進(jìn)行合并，從而獲得更好的聚類(lèi)中心。

定義1簇心均值。一個(gè)聚類(lèi)簇中所有數(shù)據(jù)點(diǎn)到簇心距離的平均值，表示為：

式中：ηk表示第k個(gè)聚類(lèi)簇中所有數(shù)據(jù)點(diǎn)到簇心的平均距離；|Ck|表示第k個(gè)聚類(lèi)簇中數(shù)據(jù)點(diǎn)的個(gè)數(shù)；Ck-c表示第k個(gè)聚類(lèi)簇的中心點(diǎn)。

定義2簇內(nèi)邊界點(diǎn)。若兩個(gè)聚類(lèi)簇之間，存在一對(duì)數(shù)據(jù)點(diǎn)的距離小于兩個(gè)聚類(lèi)簇中任意一個(gè)聚類(lèi)簇的簇心均值，則把這兩個(gè)數(shù)據(jù)點(diǎn)成對(duì)保存到一個(gè)集合中。

式中：Pkm表示聚類(lèi)簇k和m的所有的邊界點(diǎn)。

定義3邊界點(diǎn)的密度。根據(jù)定義1和2可重新定義聚類(lèi)簇k邊界點(diǎn)的局部密度ρkP。

根據(jù)以上兩個(gè)條件可知，兩個(gè)聚類(lèi)簇之間只要滿(mǎn)足它的簇內(nèi)邊界點(diǎn)不為空，且存在邊界點(diǎn)的密度大于兩個(gè)聚類(lèi)簇的局部密度。那么，這兩個(gè)聚類(lèi)簇是密度直接可達(dá)的。

定義5密度可達(dá)。如果存在類(lèi)簇k和類(lèi)簇m直接密度可達(dá)，類(lèi)簇m和類(lèi)簇l也直接密度可達(dá)。那么，類(lèi)簇k和類(lèi)簇l是密度可達(dá)的。

改進(jìn)的DPC算法在去除噪聲點(diǎn)基礎(chǔ)上，可以獲取較好的初始聚類(lèi)簇，但可能會(huì)存在一些很相似的聚類(lèi)簇。通過(guò)以上定義，可以很好地識(shí)別出密度可達(dá)的聚類(lèi)簇，并將它們進(jìn)行合并，合并之后的聚類(lèi)簇不會(huì)太大改變初始的聚類(lèi)中心，將大大提高算法對(duì)聚類(lèi)中心獲取的準(zhǔn)確性。

3 基于KDPC優(yōu)化的K-means聚類(lèi)算法

3.1 K-means基本思想

K-means算法是一種常見(jiàn)的聚類(lèi)算法，在對(duì)小數(shù)據(jù)集聚類(lèi)時(shí)有著良好的聚類(lèi)效果。K-means算法的核心是將n個(gè)樣本的數(shù)據(jù)集合劃分為K個(gè)類(lèi)簇，使得每個(gè)簇內(nèi)的樣本相似度高，簇間的樣本相似度低，設(shè)X={x1,…,xn}是d維歐氏空間中的一個(gè)數(shù)據(jù)集Rd，設(shè)A={a1,…,ac}是c個(gè)聚類(lèi)簇的中心。用dist(x,ai)表示x∈ai與該聚類(lèi)簇中心ai之差，其計(jì)算公式如下：

K-means算法使用誤差平方和（Sum of Squares due to Error，SSE）作為度量聚類(lèi)質(zhì)量的目標(biāo)函數(shù)，其內(nèi)涵是各聚類(lèi)簇內(nèi)樣本數(shù)據(jù)點(diǎn)之間的緊密程度，SSE越小，簇內(nèi)樣本數(shù)據(jù)點(diǎn)相似性越高，反之越小。SSE的計(jì)算公式如下：

式中：x表示樣本數(shù)據(jù)點(diǎn)；p為數(shù)據(jù)對(duì)象的特征屬性；dist(x,ai)表示在聚類(lèi)簇中的樣本數(shù)據(jù)點(diǎn)與聚類(lèi)中心ai的歐式距離；ni表示屬于第i聚類(lèi)簇的樣本數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

3.2 KDPC-K算法思想

KDPC-K算法思想主要分為以下兩個(gè)部分。

（1）改進(jìn)的密度峰值算法部分：運(yùn)用改進(jìn)的KDPC算法思想計(jì)算出所有樣本點(diǎn)的局部密度ρi和δi，根據(jù)ρi和δi的值構(gòu)建決策圖，假設(shè)樣本數(shù)據(jù)集劃分為K類(lèi)，則選擇前K個(gè)ρi和δi的值較大的樣本數(shù)據(jù)點(diǎn)作為聚類(lèi)中心點(diǎn)。

（2）K-means算法部分：使用第一部分得到的聚類(lèi)中心點(diǎn)作為K-means算法的初始聚類(lèi)中心點(diǎn)，開(kāi)始循環(huán)迭代，直至滿(mǎn)足迭代次數(shù)t或更新前后的目標(biāo)函數(shù)值的誤差很小則停止迭代，從而獲得更好的聚類(lèi)效果。

3.2.1 KDPC部分算法

輸入：樣本數(shù)據(jù)集X，類(lèi)別數(shù)K。

輸出：初始聚類(lèi)中心集ci(0)。

（1）對(duì)樣本數(shù)據(jù)集進(jìn)行歸一化處理；

（2）計(jì)算所有樣本數(shù)據(jù)點(diǎn)的歐式距離，并根據(jù)式（5）計(jì)算樣本點(diǎn)的局部密度ρi；

（3）根據(jù)式（6）和式（7）標(biāo)記和去除噪聲點(diǎn)；

（4）根據(jù)式（8）、式（9）分別計(jì)算所有聚類(lèi)簇的ηk、Pkm和ρkP，并根據(jù)定義4和5合并相似的類(lèi)簇；

（5）根據(jù)式（2）計(jì)算類(lèi)簇的δi；

（6）根據(jù)ρi和δi的值構(gòu)建決策圖，并選取前c個(gè)樣本點(diǎn)作為初始的聚類(lèi)中心點(diǎn)集ci(0)。

3.2.2 K-means部分算法

輸入：樣本數(shù)據(jù)集X，初始聚類(lèi)中心點(diǎn)集ci(0)。

輸出：聚類(lèi)中心點(diǎn)集ci。

步驟1：初始化迭代次數(shù)t，令t=0；

步驟2：根據(jù)初始聚類(lèi)中心點(diǎn)集ci(0)，由式（10）和式（11）計(jì)算目標(biāo)函數(shù)SSE(t)的值；

步驟4：再由式（10）和式（11）計(jì)算目標(biāo)函數(shù)SSE(t+1)的值判斷SSE(t+1)-SSE(t)＞ε是否成立，若成立則轉(zhuǎn)到步驟3，否則迭代中止；

步驟5：算法對(duì)數(shù)據(jù)集完成上述步驟之后，經(jīng)過(guò)多次迭代得到最終的聚類(lèi)中心點(diǎn)集ci。

3.3 KDPC-K算法復(fù)雜度分析

KDPC-K算法的主要由KDPC算法和K-means算法組成，在KDPC算法對(duì)樣本數(shù)據(jù)集處理過(guò)程中，假設(shè)要處理的樣本數(shù)據(jù)集的大小為n，要存儲(chǔ)每個(gè)樣本數(shù)據(jù)點(diǎn)的k近鄰信息則需要o(nk)空間；還需要存儲(chǔ)每個(gè)樣本點(diǎn)的δ和ρ值則需要o(2n)空間；最后，KDPC算法需要存儲(chǔ)每個(gè)類(lèi)簇的邊界點(diǎn)對(duì)，最不理想的情況需要o(n2)空間。獲得初始聚類(lèi)中心點(diǎn)集之后，K-means聚類(lèi)算法使用快速排序存儲(chǔ)數(shù)據(jù)點(diǎn)的歐式距離需要o(n1gn)，因此，KDPC-K算法總的空間復(fù)雜度為o(n2)。KDPC-K算法的時(shí)間復(fù)雜度由以下幾點(diǎn)決定：

（1）計(jì)算數(shù)據(jù)點(diǎn)之間的距離的時(shí)間復(fù)雜度o(n2)，但可以用快速排序把時(shí)間復(fù)雜度降至o(n1gn)；

（2）每個(gè)類(lèi)簇的邊界點(diǎn)的數(shù)量理論上可以達(dá)到n，計(jì)算邊界點(diǎn)密度的時(shí)間復(fù)雜度為o(n2)。因此，KDPC-K算法總的時(shí)間復(fù)雜度為o(n2)。

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

4.1 聚類(lèi)性能評(píng)價(jià)指標(biāo)

為驗(yàn)證算法在樣本數(shù)據(jù)集上聚類(lèi)結(jié)果的性能，本文采用Precision和Recall加權(quán)調(diào)和平均F、RI指數(shù)、相似系數(shù)系數(shù)J、精準(zhǔn)率P和召回率R來(lái)評(píng)價(jià)算法的聚類(lèi)效果。這5種評(píng)價(jià)指標(biāo)都是其值越大表示算法的聚類(lèi)效果越好，取值范圍都在[0,1]之間，這5種評(píng)價(jià)指標(biāo)的計(jì)算公式為：

式中：β是一個(gè)參數(shù)，P、R、J的計(jì)算公式如下：

式中：|F|表示算法的聚類(lèi)結(jié)果中分類(lèi)的數(shù)量；|T|表示樣本數(shù)據(jù)集原始的分類(lèi)數(shù)量；|T∩F|表示算法的聚類(lèi)結(jié)果中正確分類(lèi)的數(shù)量；|T∪F|表示聚類(lèi)結(jié)果的樣本分布和原始數(shù)據(jù)集樣本分布的數(shù)量。

RI指數(shù)計(jì)算公式為：

式中：TP+TN表示本屬于同一個(gè)類(lèi)簇的樣本點(diǎn)被分到一起的對(duì)數(shù)和本不屬于同一類(lèi)簇的樣本點(diǎn)被分到不同類(lèi)簇的對(duì)數(shù)之和；FP+FN表示分類(lèi)錯(cuò)誤的樣本點(diǎn)的對(duì)數(shù)。

4.2 KDPC-K算法的可視化聚類(lèi)效果及分析

為了檢驗(yàn)KDPC-K算法的聚類(lèi)效果，實(shí)驗(yàn)通過(guò)在4種數(shù)據(jù)集上對(duì)比KDPC-K、文獻(xiàn)[12]、文獻(xiàn)[13]和文獻(xiàn)[14]這4種算法的聚類(lèi)效果，在聚類(lèi)效果圖中，不同的顏色代表不同的類(lèi)簇，實(shí)驗(yàn)過(guò)程中文獻(xiàn)[13]和文獻(xiàn)[14]算法的參數(shù)設(shè)置為最佳，實(shí)驗(yàn)數(shù)據(jù)集的分布如圖1所示。

其中，樣本數(shù)據(jù)集Data1共有567個(gè)數(shù)據(jù)點(diǎn)，分成兩個(gè)類(lèi)簇；樣本數(shù)據(jù)集Data2共有3 603個(gè)數(shù)據(jù)點(diǎn)，分成3個(gè)類(lèi)簇；樣本數(shù)據(jù)集Data3共有785個(gè)數(shù)據(jù)點(diǎn)，分為7個(gè)類(lèi)簇；樣本數(shù)據(jù)集Data4共有3 100個(gè)數(shù)據(jù)點(diǎn)，分為31個(gè)類(lèi)簇，數(shù)據(jù)集的具體信息如表1所示。

表1 4種數(shù)據(jù)集信息

4種算法在樣本數(shù)據(jù)集Data1上實(shí)驗(yàn)的聚類(lèi)效果如圖2所示，可以得出KDPC-K、文獻(xiàn)[12]和文獻(xiàn)[14]算法都能夠準(zhǔn)確識(shí)別樣本數(shù)據(jù)點(diǎn)并得到準(zhǔn)確的聚類(lèi)結(jié)果。然而，文獻(xiàn)[13]算法沒(méi)有得到準(zhǔn)確的聚類(lèi)個(gè)數(shù)，將一個(gè)類(lèi)簇錯(cuò)誤地分為兩個(gè)類(lèi)簇。

4種算法在樣本數(shù)據(jù)集Data2上實(shí)驗(yàn)的聚類(lèi)結(jié)果如圖3所示，可以得出KDPC-K、文獻(xiàn)[14]和文獻(xiàn)[13]算法都能夠獲得正確的聚類(lèi)結(jié)果，而文獻(xiàn)[12]算法沒(méi)有將樣本數(shù)據(jù)點(diǎn)歸類(lèi)正確。雖然文獻(xiàn)[13]和文獻(xiàn)[14]的算法獲得了準(zhǔn)確的聚類(lèi)結(jié)果，但需要更多的參數(shù)設(shè)置。

4種算法在樣本數(shù)據(jù)集Data3上實(shí)驗(yàn)的聚類(lèi)結(jié)果如圖4所示。從圖4中可以得出文獻(xiàn)[12]和文獻(xiàn)[13]算法聚類(lèi)效果最差，把一個(gè)類(lèi)簇分為兩個(gè)并且一些其他的類(lèi)簇?cái)?shù)據(jù)點(diǎn)歸類(lèi)錯(cuò)誤，KDPC-K和文獻(xiàn)[14]算法取得正確的聚類(lèi)結(jié)果。雖然文獻(xiàn)[14]和KDPC-K算法都取得了正確的聚類(lèi)數(shù)，但文獻(xiàn)[14]算法對(duì)參數(shù)的依賴(lài)性更大，并且KDPC-K算法在此數(shù)據(jù)集上的聚類(lèi)效果表現(xiàn)更佳。

4種算法在樣本數(shù)據(jù)集Data4上實(shí)驗(yàn)的聚類(lèi)結(jié)果如圖5所示。從圖5中可以得出，4種算法在樣本數(shù)據(jù)集上都取得了正確的聚類(lèi)簇?cái)?shù)。但文獻(xiàn)[13]、文獻(xiàn)[14]算法需要人工選擇較多參數(shù)，一旦參數(shù)選擇不好，對(duì)算法的聚類(lèi)效果影響較大，并且KDPC-K算法的聚類(lèi)效果比文獻(xiàn)[12]算法更好。因此，KDPC-K算法聚類(lèi)性能更佳。

4.3 KDPC-K算法的性能指標(biāo)分析

為了檢驗(yàn)KDPC-K算法的聚類(lèi)性能，實(shí)驗(yàn)通過(guò)在UCI數(shù)據(jù)集上對(duì)比KDPC-K、文獻(xiàn) [12]、文獻(xiàn)[13]和文獻(xiàn)[14]這4種算法的性能指標(biāo)和運(yùn)行時(shí)間，UCI數(shù)據(jù)集的具體信息如表2所示。

表2 UCI數(shù)據(jù)集信息

在實(shí)驗(yàn)中，每種算法都在各數(shù)據(jù)集上運(yùn)行40次，以3種性能評(píng)價(jià)指標(biāo)的均值和平均運(yùn)行時(shí)間作為4種算法的聚類(lèi)性能，4種算法在UCI數(shù)據(jù)集上的性能指標(biāo)如表3所示。

表3 4種算法在UCI數(shù)據(jù)上的性能指標(biāo)及運(yùn)行時(shí)間

從表3中可以得出，在Iris數(shù)據(jù)集上，KDPC-K算法比其他3種算法的性能指標(biāo)更佳，在F指標(biāo)上KDPC-K算法比文獻(xiàn)[12]、文獻(xiàn)[13]和文獻(xiàn)[14]分別高出0.038 7、0.037 5和0.051 9，在J指標(biāo)上KDPC-K算法比文獻(xiàn)[12]、文獻(xiàn)[13]和文獻(xiàn)[14]分別高出0.104 0、0.060 3和0.055 9，在RI指標(biāo)上，KDPC-K算法比文獻(xiàn)[12]、文獻(xiàn)[13]和文獻(xiàn)[14]分別高出0.043 3、0.037 9和0.034 6，并且KDPC-K算法的平均運(yùn)行時(shí)間最少，文獻(xiàn)[13]和文獻(xiàn)[12]次之，文獻(xiàn)[14]最長(zhǎng)；在Segment數(shù)據(jù)集上，4種算法的性能指標(biāo)比在Iris數(shù)據(jù)集更低并且平均運(yùn)行時(shí)間更長(zhǎng)，這是由于Segment數(shù)據(jù)集更大，特征維數(shù)和類(lèi)別數(shù)更多并且數(shù)據(jù)及分布形態(tài)更復(fù)雜，KDPC-K算法的性能指標(biāo)依舊比其他3種算法更佳，KDPC-K算法的3種性能指標(biāo)比另外3種算法高出0.1～0.2，KDPC-K算法的平均運(yùn)行時(shí)間最少，文獻(xiàn)[14]的算法平均運(yùn)行時(shí)間最長(zhǎng)；4種算法都在Wine數(shù)據(jù)集上表現(xiàn)得比在其他數(shù)據(jù)集更好，Wine數(shù)據(jù)集數(shù)量小、特征維數(shù)和類(lèi)別數(shù)少，數(shù)據(jù)集分別形態(tài)不復(fù)雜，KDPC-K算法的性能指標(biāo)仍然比其他3種算法高出0.1～0.3，文獻(xiàn)[13]和KDPC-K算法的平均運(yùn)行時(shí)間相差不大，文獻(xiàn)[12]和文獻(xiàn)[14]算法的平均運(yùn)行時(shí)間較長(zhǎng)；由于Pageblocks數(shù)據(jù)集的樣本數(shù)量是最多的，所以4種算法的平均運(yùn)行時(shí)間也是最長(zhǎng)的，在4種算法中KDPC-K算法的平均運(yùn)行時(shí)間最短，文獻(xiàn)[14]算法的平均運(yùn)行時(shí)間最長(zhǎng)。因?yàn)槲墨I(xiàn)[12]只是利用改進(jìn)的森林算法提高K-means算法的尋優(yōu)能力來(lái)避免算法陷入局部最優(yōu)，對(duì)原始K-means算法對(duì)初始聚類(lèi)中心的敏感并沒(méi)有改進(jìn)。文獻(xiàn)[13]和文獻(xiàn)[14]雖然對(duì)K-means算法的初始聚類(lèi)中心進(jìn)行了改進(jìn)，但該算法其中的參數(shù)對(duì)聚類(lèi)性能影響較大，并且對(duì)數(shù)據(jù)集的傾斜問(wèn)題比較敏感，總之KDPC-K算法的聚類(lèi)性能指標(biāo)和平均運(yùn)行時(shí)間都比其他3種算法表現(xiàn)更佳。

4.4 KDPC-K算法的抗噪性和魯棒性分析

為驗(yàn)證KDPC-K算法的抗噪性和魯棒性，使用KDPC-K、文獻(xiàn)[12]、文獻(xiàn)[13]、文獻(xiàn)[14]算法在同一人工合成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，人工合成數(shù)據(jù)集的具體信息如表4所示。

表4 含有噪聲的合成數(shù)據(jù)集信息

實(shí)驗(yàn)過(guò)程中每種算法都在數(shù)據(jù)集上運(yùn)行40次，取4種算法的評(píng)價(jià)指標(biāo)均值作為聚類(lèi)性能值，4種算法的聚類(lèi)結(jié)果指標(biāo)如表5所示。

表5 4種算法在含噪聲的數(shù)據(jù)集上的性能指標(biāo)

表5顯示了KDPC-K、文獻(xiàn)[12]、文獻(xiàn)[13]和文獻(xiàn)[14]這4種聚類(lèi)算法在含噪聲的合成數(shù)據(jù)集上的聚類(lèi)性能。在Flame數(shù)據(jù)集上，文獻(xiàn)[12]和文獻(xiàn)[14]算法的3種聚類(lèi)性能指標(biāo)相差不大，文獻(xiàn)[13]算法的性能指標(biāo)比以上兩種算法好，KDPC-K算法的聚類(lèi)性能指標(biāo)最佳；在Zigzag數(shù)據(jù)集上，文獻(xiàn)[12]算法聚類(lèi)性能指標(biāo)最差，文獻(xiàn)[13]和文獻(xiàn)[14]算法在RI指標(biāo)表現(xiàn)相差無(wú)幾，但在其他兩種性能指標(biāo)上文獻(xiàn)[14]算法表現(xiàn)得更好一些，KDPC-K算法在各項(xiàng)性能指標(biāo)上都比其他3種算法更好；在Jain數(shù)據(jù)集上，文獻(xiàn)[12]、文獻(xiàn)[13]和文獻(xiàn)[14]這3種算法表現(xiàn)一般，與KDPC-K算法在各種性能指標(biāo)上相差較多；在D6數(shù)據(jù)上，文獻(xiàn)[13]算法除了在Jaccard指標(biāo)上與文獻(xiàn)[12]和文獻(xiàn)[14]表現(xiàn)不佳，在其他兩種性能指標(biāo)上3種算法表現(xiàn)差不多，KDPC-K算法的3種性能指標(biāo)都較大；在Atom數(shù)據(jù)集上，文獻(xiàn)[12]和文獻(xiàn)[13]算法的性能指標(biāo)都比其他兩種算法低，KDPC-K算法比文獻(xiàn)[14]算法表現(xiàn)更佳。因?yàn)槲墨I(xiàn)[12]只是利用改進(jìn)的森林算法提高K-means算法的尋優(yōu)能力來(lái)避免算法陷入局部最優(yōu)，對(duì)原始K-means算法對(duì)初始聚類(lèi)中心的敏感并沒(méi)有改進(jìn)。文獻(xiàn)[13]雖然對(duì)K-means算法的初始聚類(lèi)中心進(jìn)行了改進(jìn)，但該算法其中的一個(gè)參數(shù)對(duì)聚類(lèi)性能影響較大，并且對(duì)數(shù)據(jù)集的傾斜和噪聲問(wèn)題比較敏感，文獻(xiàn)[14]算法也沒(méi)有解決數(shù)據(jù)集中噪聲的問(wèn)題。總之，在5種含有噪聲點(diǎn)的合成數(shù)據(jù)集上，KDPC-K算法的3種性能指標(biāo)都比其他3種算法表現(xiàn)更佳。

5 結(jié) 語(yǔ)

本文針對(duì)K-means算法對(duì)初始聚類(lèi)中心敏感和易受噪聲點(diǎn)的影響，提出一種基于KNN優(yōu)化的DPC的K-means算法（KDPC-K）。該算法利用KNN思想和改進(jìn)的密度函數(shù)優(yōu)化樣本數(shù)據(jù)點(diǎn)的局部密度，并以平均密度作為閾值去除離群點(diǎn)，再結(jié)合自適應(yīng)策略合并相似的類(lèi)簇來(lái)提高聚類(lèi)中心點(diǎn)的精確性，最后，通過(guò)取得的類(lèi)簇中心點(diǎn)集作為K-means算法的初始聚類(lèi)中心。為了驗(yàn)證KDPC-K算法的聚類(lèi)效果，本文先通過(guò)在UCI數(shù)據(jù)集上以圖示的方式驗(yàn)證分析KDPC-K聚類(lèi)的有效性，然后在含有噪聲的合成數(shù)據(jù)集和UCI數(shù)據(jù)集上比較KDPC-K和文獻(xiàn)[12-14]這4種算法的聚類(lèi)性能。實(shí)驗(yàn)證明：KDPC-K算法能夠有效提高傳統(tǒng)K-means算法的聚類(lèi)性能，并且比其他改進(jìn)的算法聚類(lèi)效果更佳。