黃學雨，程世超

（江西理工大學，江西 贛州 341000）

0 引 言

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

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

1 密度峰值聚類算法介紹

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

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

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

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

根據(jù)式（1）可知，截斷距離dc選取值的不同對DPC聚類算法影響很大，并且原始的DPC算法對于小型數(shù)據(jù)集的聚類效果并不好。因此，有文獻提出當數(shù)據(jù)規(guī)模較小時，使用高斯核定義樣本數(shù)據(jù)點的局部密度，公式如下[16]：

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

2 改進的密度峰值聚類KDPC算法

2.1 改進的KDPC算法基本思想

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

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

2.2 自適應(yīng)合并策略優(yōu)化KDPC

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

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

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

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

式中：Pkm表示聚類簇k和m的所有的邊界點。

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

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

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

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

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

3.1 K-means基本思想

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

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

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

3.2 KDPC-K算法思想

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

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

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

3.2.1 KDPC部分算法

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

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

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

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

（3）根據(jù)式（6）和式（7）標記和去除噪聲點；

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

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

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

3.2.2 K-means部分算法

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

輸出：聚類中心點集ci。

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

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

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

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

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

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

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

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

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

4.1 聚類性能評價指標

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

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

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

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

式中：TP+TN表示本屬于同一個類簇的樣本點被分到一起的對數(shù)和本不屬于同一類簇的樣本點被分到不同類簇的對數(shù)之和；FP+FN表示分類錯誤的樣本點的對數(shù)。

4.2 KDPC-K算法的可視化聚類效果及分析

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

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

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

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

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

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

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

4.3 KDPC-K算法的性能指標分析

為了檢驗KDPC-K算法的聚類性能，實驗通過在UCI數(shù)據(jù)集上對比KDPC-K、文獻 [12]、文獻[13]和文獻[14]這4種算法的性能指標和運行時間，UCI數(shù)據(jù)集的具體信息如表2所示。

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

在實驗中，每種算法都在各數(shù)據(jù)集上運行40次，以3種性能評價指標的均值和平均運行時間作為4種算法的聚類性能，4種算法在UCI數(shù)據(jù)集上的性能指標如表3所示。

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

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

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

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

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

實驗過程中每種算法都在數(shù)據(jù)集上運行40次，取4種算法的評價指標均值作為聚類性能值，4種算法的聚類結(jié)果指標如表5所示。

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

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

5 結(jié) 語

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