融合相對密度與近鄰關系的密度峰值聚類算法

代永楊，張清華，支學超

(重慶郵電大學 計算智能重慶市重點實驗室，重慶 400065)

0 引 言

作為一種無監(jiān)督學習方法,聚類旨在發(fā)現(xiàn)數(shù)據(jù)之間潛在的數(shù)據(jù)結構[1]。目前國內外學者已經(jīng)提出了許多不同類型的經(jīng)典聚類算法?；趯哟蔚木垲愃惴ㄓ蠧URE[2]和BIRCH[3]等; 基于劃分的聚類算法有K-means[4]等; 基于網(wǎng)格的聚類算法有WaveCluster[5],STING[6]和CLIQUE[7]等; 基于密度的聚類算法有DBSCAN[8]和OPTICS[9]等。這些經(jīng)典的聚類算法已經(jīng)被廣泛應用到數(shù)據(jù)挖掘[10-11]、圖像分割[12-14]、數(shù)據(jù)壓縮[15]等領域。

密度峰值聚類算法(density peaks cluster,DPC)是由A.Rodriguez等[16]于2014年發(fā)表在Science上的一種基于密度的聚類算法。樣本的密度和相對距離是DPC中的2個重要概念。給定數(shù)據(jù)集中任意一個樣本p，p的密度即在給定截斷距離dc的條件下，以p為圓心，dc為半徑的鄰域中所包含的樣本數(shù)量。p的相對距離即從密度比p大樣本中找到距離p最近的樣本q，p和q之間的距離為p的相對距離。在本文中，記q為p的父節(jié)點。DPC根據(jù)2個假設進行聚類:①類簇中心被周圍密度更低的樣本包圍;②類簇中心與其父節(jié)點間的距離較遠。基于以上2個假設，DPC首先計算樣本的密度和相對距離，構建決策圖; 然后，從決策圖中選擇具有較大密度和相對距離的樣本作為聚類中心; 最后，將非中心點按照密度由高到低的順序分配到各自父節(jié)點所在的類簇。

由于DPC算法思想簡單且能夠聚類任意形狀的類簇，這使得DPC已經(jīng)被廣泛應用，然而，該算法仍然存在以下不足。

①DPC的非中心點的分配策略容易引起密度跳躍，從而導致連續(xù)錯誤，影響聚類結果[17]。

②DPC密度估計不能消除類簇間的密度差距，在選擇聚類中心時傾向于選擇密度更高的類簇中的樣本作為聚類中心，進而影響算法聚類性能。

針對問題①，Xie等[17]提出FKNN-DPC算法，該算法基于k近鄰思想設計2步分配策略用于分配非中心點。為了避免分配策略受到邊界點的影響，F(xiàn)KNN-DPC基于樣本與第k個近鄰的距離檢測邊界點，邊界點的閾值為所有樣本與其第k個近鄰的距離均值。然而，在面對類簇間有密度差距的數(shù)據(jù)集時，F(xiàn)KNN-DPC的邊界點檢測方法會將低密度類簇中大部分樣本檢測為邊界點，導致聚類結果不理想。

針對問題②以及FKNN-DPC所存在的問題，本文基于FKNN-DPC中的非中心點分配框架，定義相對密度并結合近鄰關系提出RN-DPC算法。RN-DPC算法的主要創(chuàng)新點在于以下幾點。

1)在估計樣本密度時，根據(jù)反向k近鄰關系定義相對密度以消除類簇間的密度差距，解決DPC傾向于選擇高密度類簇中的樣本作為聚類中心的問題。

2)在檢測邊界點時，根據(jù)反向k近鄰數(shù)作為檢測邊界點的指標，解決FKNN-DPC的邊界點檢測方法會導致密度較小的類簇中大部分樣本被檢測為邊界點的問題。

3)在分配非中心點時，引入共享最近鄰相似度設計2步分配策略對非中心點進行分配，提高非中心點分配的準確率。

1 相關工作

本節(jié)將簡要介紹DPC的主要思想、DPC的相關改進工作以及近鄰關系的基本定義和概念。

1.1 DPC聚類算法

DPC需要計算樣本密度和相對距離以選擇聚類中心。在本文中，記數(shù)據(jù)集為X={x1,x2,…,xn},基于數(shù)據(jù)集X，DPC的密度和相對距離定義如下。

定義1[16]給定數(shù)據(jù)集X，截斷距離dc，對于?xi∈X，xi的密度定義為

(1)

(1)式中:d(xi,xj)表示xi和xj之間的距離，當x<0時，χ(x)=1；反之，χ(x)=0。

定義2[16]給定數(shù)據(jù)集X，ρi和ρj分別表示xi和xj的密度，對于?xi∈X，xi的相對距離定義為

(2)

通過樣本的密度和相對距離2個特征可以構建決策圖，從決策圖中選擇有較大密度和較大相對距離的樣本作為聚類中心。對于非中心點，DPC將它們分配到各自的父節(jié)點所在的類簇得到最終的聚類結果。

1.2 改進的DPC算法

近年來，有許多學者針對DPC的不同問題對其進行改進。這些改進的DPC算法可以分為2類：①針對DPC的聚類性能進行改進[17-21]；②針對DPC的聚類效率進行改進[22-25]。

為了提高DPC的聚類性能，一些學者從不同角度對DPC算法進行改進。為了加強DPC算法對于流形簇的聚類能力并減少算法對于參數(shù)的依賴,Cheng等[18]提出了DLORE-DP算法，該算法基于局部代表點的思想，通過共享最近鄰關系連接代表點，對每一個代表點進行聚類，最后將非代表點分配到各自的代表點所在的類簇。為了更好地度量樣本的密度,Du等[19]基于k近鄰思想并結合主成分分析法提出DPC-KNN-PCA算法，該算法使用k近鄰的概念并且充分考慮數(shù)據(jù)集的全局分布重新定義局部密度，并結合PCA算法對數(shù)據(jù)集進行聚類以達到更好的聚類效果。為了避免DPC算法發(fā)生密度跳躍而引起連續(xù)錯誤，Xie等[17]基于k近鄰的思想設計2步分配策略用于分配非中心點，首先，該算法對邊界點進行剔除，然后，在第一步分配策略中對非邊界點進行分配，最后，基于k近鄰分類的思想對所有沒有標簽的樣本進行分配。為了消除類簇間密度差距對DPC中心點選擇的影響，Hou等[20]定義直接下屬和間接下屬的概念，以樣本的直接下屬數(shù)量作為樣本的相對密度，根據(jù)相對密度和相對距離選擇聚類中心。由于DPC使用樣本間的歐氏距離作為樣本的相似度度量，這一度量方法無法反映樣本的真實分布。因此，Du等[21]引入測地距離的概念，使用k近鄰圖中樣本間的最短路徑作為樣本的相似度度量以及相對距離度量。

為了提高DPC的聚類效率，一些學者通過不同策略來減少距離計算次數(shù)對DPC進行改進。Chen等[22]基于k近鄰思想提出一種快速DPC算法,該算法將非密度峰值的父節(jié)點搜索范圍鎖定在其k近鄰中，在搜索密度峰值的父節(jié)點時，使用三角不等式進行樣本過濾，從而減少大量不必要的計算。Xu等[23]將數(shù)據(jù)點映射到網(wǎng)格中，將位于同一網(wǎng)格中的樣本視為一個新的樣本，進而提出DPCG算法，該算法對于低維數(shù)據(jù)有比較明顯的速度提升，但是無法應用于高維數(shù)據(jù)。Gong等[24]基于分布式計算策略提出EDDPC算法，該算法減少了大量的距離計算次數(shù)和數(shù)據(jù)洗牌、數(shù)據(jù)復制和數(shù)據(jù)過濾的成本。Bai等[25]使用k-means算法來提高DPC的效率，該算法在計算相對距離之前使用k-means算法對數(shù)據(jù)集進行一次劃分，這樣在計算樣本相對距離時可以將搜索范圍縮小到單個類簇或者樣本相鄰的類簇，不必搜索整個數(shù)據(jù)集，這樣可以減少距離的計算次數(shù)。

1.3 近鄰關系

樣本近鄰關系的選擇是許多數(shù)據(jù)挖掘算法的基礎，選擇合理的近鄰關系可以提高算法的性能[26]。常用的近鄰關系有k近鄰[27]，反向k近鄰[28]，相互k近鄰[29]以及共享最近鄰[30]。本文用到的k近鄰、反向k近鄰和共享最近鄰3種關系的定義如下。

(3)

定義4[28]給定數(shù)據(jù)集X,knn(xj)表示xj的k近鄰集合,對于?xi∈X,xi的反向k近鄰集合定義為

rnn(xi)={?xj∈X|xi∈knn(xj)}

(4)

定義5[30]給定數(shù)據(jù)集X，knn(xi)和knn(xj)分別表示xi和xj的k近鄰集合，對于?xi,xj∈X，xi和xj的共享最近鄰集合定義為

snn(xi,xj)=knn(xi)∩knn(xj)

(5)

定義6[30]給定數(shù)據(jù)集X，xi和xj的共享最近鄰集合snn(xi,xj)以及近鄰數(shù)k,對于?xi,xj∈X,xi和xj的共享近鄰相似度定義為

sim(xi,xj)=|snn(xi,xj)|/k

(6)

2 RN-DPC聚類算法

針對DPC算法和FKNN-DPC算法所存在的問題，即①DPC的密度估計不能消除不同類簇間的密度差距，導致該算法的中心點選擇方案傾向于選擇高密度類簇中的樣本作為聚類中心;②sFKNN-DPC的邊界點檢測方法對類簇密度變化十分敏感，容易將低密度類簇中大量樣本檢測為邊界點。本節(jié)將定義相對密度和邊界點并進一步提出本文的RN-DPC算法。

RN-DPC算法的聚類過程可以分為中心點選擇和非中心點分配2個部分。在中心點選擇過程中，RN-DPC算法定義相對密度解決DPC在面對有密度差距的類簇時無法正確選擇聚類中心的問題。在非中心點分配過程中，RN-DPC算法引入反向k近鄰關系進行邊界點檢測，并且根據(jù)樣本的共享最近鄰相似度分配非中心點。選擇聚類中心的過程可以分為3個步驟:①根據(jù)反向k近鄰關系計算樣本的相對密度;②基于樣本的相對密度計算相對距離;③根據(jù)相對密度和相對距離構造決策圖以選擇聚類中心。非中心點分配過程也可以分為3個步驟:①根據(jù)樣本反向k近鄰數(shù)檢測邊界點;②分配非邊界點中樣本間共享最近鄰相似度較大的樣本;③根據(jù)已經(jīng)被分配樣本的類簇信息，采用k近鄰分類的思想對剩余樣本進行分配。

2.1 中心點選擇策略

針對DPC的中心點選擇策略的問題，RN-DPC算法基于相對密度提出一種新的中心點選擇策略。為了更直觀地說明DPC的中心點選擇策略存在的問題，接下來以Jain數(shù)據(jù)集[20]為例來展示說明,如圖1。圖1a中，橫坐標x和縱坐標y分別表示二維數(shù)據(jù)集中樣本點2個屬性的坐標值。從圖1b中可以看出，在DPC的密度定義下，2個類簇的樣本密度差距十分明顯。由于DPC的中心點選擇策略是從決策圖中選擇同時有較大密度和較大相對距離的樣本作為聚類中心，所以,2個類簇的密度差距會導致紫色類簇中有3個樣本，即位于圖1c中紅色圈內的樣本，在中心點選擇的優(yōu)先級上都大于黃色類簇中的樣本A。樣本A的密度太小導致其沒有被選作聚類中心，這會使得DPC無法得到正確的聚類結果。最終的聚類結果如圖1d，紅色五角星表示聚類中心。

圖1 DPC密度估計的問題

RN-DPC算法的密度定義旨在消除不同類簇間的密度差距，文獻[30]指出在類簇的核心區(qū)域的樣本相比類簇邊界區(qū)域的樣本有更多的反向k近鄰，并且樣本的反向k近鄰數(shù)目對類簇密度變化不敏感?；谏鲜鼋Y論，RN-DPC根據(jù)樣本的反向k近鄰關系對樣本的密度給出了新的定義，如下所示。

定義7給定數(shù)據(jù)集X,rnn(xi)表示xi的反向k近鄰集合,對于?xi∈X,xi的相對密度定義為

(7)

(7)式中:|·|表示集合的勢；d(xi,xj)表示xi和xj的距離。

根據(jù)定義7對Jain中樣本的密度計算結果如圖2a。對比圖1b和圖2a可以看出，使用定義7所計算得到的2個類簇的樣本密度更均衡，沒有明顯的密度差距。這說明了RN-DPC算法中的相對密度定義可以消除不同類簇中樣本的密度差距。其原因在于反向k近鄰關系對類簇密度變化不敏感，只與樣本近鄰的分布有關。根據(jù)樣本的相對密度和相對距離可以構建新的決策圖，如圖2b。由圖2b可知，本文提出的RN-DPC算法可以選擇到2個正確的聚類中心，即位于圖2b中紅色圈內的樣本，最終的聚類結果如圖2c。

圖2 Jain上相對密度度量結果

在計算得到樣本的相對密度之后，RN-DPC算法根據(jù)樣本間的相對密度關系計算樣本的相對距離，然后基于相對密度和相對距離2個特征構造決策圖，并進一步從決策圖中選擇聚類中心。RN-DPC的中心點選擇策略的具體步驟給出如算法1。

算法1中心點選擇策略

輸入:數(shù)據(jù)集X，中心點數(shù)目m，近鄰數(shù)k。

輸出:聚類中心，k近鄰矩陣knn，反向k近鄰矩陣rnn，共享近鄰矩陣snn。

步驟1計算每對樣本的距離矩陣distn×n。

步驟2根據(jù)距離矩陣獲取樣本的k近鄰矩陣knn、反向k近鄰矩陣rnn和共享近鄰矩陣snn。

步驟4根據(jù)定義2計算樣本相對距離δi。

2.2 非中心點分配策略

針對FKNN-DPC的非中心點分配策略中邊界點檢測方法存在的問題以及為了提高非中心點分配的準確率，RN-DPC引入反向k近鄰數(shù)作為檢測邊界點的指標，并結合共享最近鄰相似度和k近鄰思想提出一種新的非中心點分配策略。

以Jain數(shù)據(jù)集為例說明FKNN-DPC的邊界點檢測方法存在的問題。FKNN-DPC在Jain上的邊界點檢測結果如圖3，其中，灰色“+”代表邊界點。從圖3中可以看出，幾乎所有屬于黃色類簇的樣本都被檢測為邊界點，而只有極少部分屬于紫色類簇的樣本被檢測為邊界點。因為紫色類簇中樣本與其第k個近鄰的距離比黃色類簇中樣本與其第k個近鄰的距離更小且紫色類簇樣本數(shù)量較多，這會導致FKNN-DPC的邊界點閾值偏小。而黃色類簇密度較小，其中大量樣本與其第k個近鄰的距離都大于邊界點的閾值，所以，黃色類簇中大量樣本都被檢測為邊界點。顯然，這是不合理的。

圖3 FKNN-DPC的邊界點檢測結果

為了解決FKNN-DPC的邊界點檢測方法不能用于有密度差距的類簇中的問題，RN-DPC利用反向k近鄰關系對類簇密度變化不敏感的特點，基于樣本的反向k近鄰數(shù)與k近鄰數(shù)的比值作為檢測邊界點的指標，提出一種新的邊界點檢測方法如下。

定義8給定數(shù)據(jù)集X,knn(xi)和rnn(xi)分別表示xi的k近鄰和反向k近鄰集合，對于?xi∈X，若|rnn(xi)|/|knn(xi)|<1，則xi為邊界點，反之，xi不是邊界點。邊界點集合為B，非邊界點集合為B′。

同樣，接下來仍用Jain數(shù)據(jù)集來說明RN-DPC算法的邊界點檢測方法的有效性。RN-DPC的邊界點檢測方法在Jain數(shù)據(jù)集上的檢測結果如圖4。從圖4中可以看出，RN-DPC算法中的邊界點檢測方法可以保留2個類簇的核心部分，不會使得黃色類簇中大部分樣本被檢測為邊界點。這說明了RN-DPC的邊界點定義的有效性和合理性。

圖4 RN-DPC的邊界點檢測結果

RN-DPC在進行了邊界點檢測后得到集合B和B′，接下來需要分2步對非中心點進行分配以保證分配的準確率。為了更好地敘述RN-DPC對非中心點的2步分配策略，給出RN-DPC的核心樣本定義如下。

定義9給定數(shù)據(jù)集X，所有樣本與其k近鄰的共享最近鄰相似度均值為γ，xi為任意一個有標簽的樣本，其k近鄰集合為knn(xi)，非邊界點集合為B′。對?xj∈knn(xi)，若xj∈B′且xi和xj的共享最近鄰相似度滿足sim(xi,xj)≥γ，則稱xj為核心樣本，否則，xj為非核心樣本。核心樣本集合記為C，非核心樣本集合記為C′。

RN-DPC算法的2步分配策略首先分配滿足定義9的非中心點，然后分配不滿足定義9的非中心點。2步分配策略的主要思想如下。

分配策略1:初始化待訪問集合為所選擇的中心點，每次迭代訪問一個已經(jīng)被分配但沒有訪問過的樣本p，并將p的k近鄰中滿足定義9的近鄰q分配到p所在的類簇，同時將q加入待訪問的集合中，一直持續(xù)該過程直到待訪問集合為空。得到C和C′。

分配策略2:初始化矩陣A，其中任意元素A(i,j)表示樣本i的近鄰中類簇標簽為j的近鄰數(shù)量。每次迭代找到A的最大值，將最大值對應的行所代表的樣本i分配到最大值對應的列所代表的類簇j。進行一次迭代后對矩陣A進行更新，直到A的最大值為0或所有樣本分配完畢則停止。

分配策略1和分配策略2的具體步驟分別如算法2和算法3。本文所提出的RN-DPC算法的流程如圖5。

圖5 RN-DPC算法流程圖

算法2分配策略1

輸入:近鄰數(shù)k，中心點centers，k近鄰矩陣knn，反向k近鄰矩陣rnn，共享最近鄰相似度矩陣sim。

輸出:剩余未分配樣本R。

步驟1初始化數(shù)組queue為所選擇的中心點centers。

步驟2記queue中的第一個元素為thispoint并將其從queue中刪除。

步驟3遍歷每thispoint的每一個近鄰p，如果p沒有被分配并且是一個核心點，添加neighbor到queue的末尾并且分配neighbor到thispoint所在的類簇，否則，跳過點p訪問下一個近鄰。

步驟4若queue為空，則結束，否則，回到步驟2。

算法3分配策略2

輸入:待分配樣本集合R，近鄰數(shù)k，中心點centers，k近鄰矩陣knn，反向k近鄰矩陣rnn。

輸出: 聚類結果S。

步驟1初始化矩陣A，矩陣A中的元素A(i,j)記為樣本i的k近鄰中屬于類簇j的近鄰的數(shù)目。

步驟2找到矩陣A的最大值，記為maxvalue。

步驟3如果maxvalue大于0，則找到A(i,j)=maxvalue的樣本點i和類簇j，并且分配樣本點i到對應的類簇j。

步驟4更新矩陣A，將R中已經(jīng)分配的樣本點所在的行置為0，更新R中未分配的樣本點的近鄰的類簇信息。

步驟5若R為空，則結束，反之，回到步驟2。

2.3 時間復雜度分析

在本節(jié)將對RN-DPC的時間復雜度進行分析，設近鄰數(shù)為k，類簇數(shù)為m，核心樣本集合為C，非核心樣本集合為C′。RN-DPC的時間復雜度主要由算法1、算法2和算法3組成。

算法1這一部分的時間復雜度主要來源于算法1的步驟1，2和4，這3個步驟的時間復雜度均為O(n2)，因此，整個算法1的時間復雜度為O(n2)。

算法2分配策略1中需要遍歷所有核心樣本及其k近鄰，時間復雜度為O(k×|C|)。

算法3分配策略2中待分配的樣本數(shù)為|C′|，最壞的情況下算法3迭代次數(shù)為|C′|，每次迭代的主要時間復雜度來源于搜索矩陣A的最大值，時間復雜度為O(m×|C′|)。因此，算法3的平均時間復雜度小于O(m×|C′|2)。因為非核心樣本數(shù)量遠遠小于樣本總數(shù)，所以分配策略2的時間復雜度小于O(n2)。

綜上所述，RN-DPC的時間復雜度為O(n2)。

3 對比實驗與分析

RN-DPC算法將在人工數(shù)據(jù)集和真實數(shù)據(jù)集上與DPC算法、RDDPC算法、KNN-DPC算法、DBSCAN算法和K-means算法進行對比實驗以驗證其有效性。本文采用ARI[33]，NMI[34]來評估聚類算法的聚類結果。ARI和NMI的取值均為[0,1]，且值越大，表示聚類的效果越好。

實驗所用到的數(shù)據(jù)集由表1給出。序號1-8為常用的人工數(shù)據(jù)集，它們被用于測試聚類算法在面對不同分布的類簇時的聚類能力。序號9-16為真實數(shù)據(jù)集，它們經(jīng)常被用于測試聚類算法性能。人工數(shù)據(jù)集中包含了符合高斯分布的數(shù)據(jù)集，流型流形數(shù)據(jù)集，類簇高度重疊的數(shù)據(jù)集以及不同類簇之間有密度差距的數(shù)據(jù)集。

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

3.1 數(shù)據(jù)預處理與算法參數(shù)設置

為了避免數(shù)據(jù)集中不同屬性量綱不同影響實驗結果，本文采用最大最小歸一化原則對實驗數(shù)據(jù)進行處理。針對含有缺失值的屬性，采用對應屬性的均值代替缺失值。

為了保證對比實驗的有效性，本文對每種算法都進行參數(shù)調優(yōu)。FKNN-DPC、RDDPC和RN-DPC都需要設置近鄰數(shù)k,取值為[5,50],調整步長為1。DPC中截斷距離dc的取值為(0,1],調整步長為0.01。DBSCAN中需要設置半徑eps和密度閾值minpoint，2個參數(shù)分別的取值為(0,1]和[1,40]，調整步長為0.01和1。因為K-means算法的初始聚類中心點是隨機選取的，初始聚類中心點選擇不同會導致最終的聚類結果不同，所以對于K-means算法，本文在每個數(shù)據(jù)集上運行30次，取各聚類評價指標的均值作為最終的聚類結果。

3.2 人工數(shù)據(jù)集上實驗對比分析

人工數(shù)據(jù)集的樣本分布如圖6。不同聚類算法在人工數(shù)據(jù)集上可視化聚類結果如圖7—圖14。其中，每一幅圖的橫縱坐標分別表示人工數(shù)據(jù)集中樣本點的2個屬性的屬性值。圖中不同的類簇用不同的顏色區(qū)分，聚類中心采用紅色五角星進行標識，錯誤分配的樣本點用紅色“X”標識。DBSCAN算法檢測到的噪聲用灰色“+”標識。沒有被對應算法所識別出的類簇用灰色圓點標識。6個聚類算法在人工數(shù)據(jù)集上的具體聚類性能評價指標如表2。

從表2中可以看出，RN-DPC算法在人工數(shù)據(jù)集上的聚類性能評價指標總體優(yōu)于其余5個算法。本文所提出的RN-DPC算法在Jain，F(xiàn)lame和Spiral 3個流形數(shù)據(jù)集上都取得了正確的聚類結果。從圖6c中可以看出，Jain中的2個流形類簇間存在明顯的密度差距，位于圖上方的黃色類簇密度明顯小于圖下方的紫色類簇。DPC和FKNN-DPC都沒有在Jain上取得正確的聚類結果，因為這2個算法的密度度量不能消除不同類簇中樣本的密度差距，導致聚類中心選擇出錯，2個算法的聚類中心選擇結果如圖9b和圖9c，它們都沒有識別出位于Jain上方的類簇。從DBSCAN的聚類結果中可以看出，DBSCAN能夠正確識別出位于圖6c下方的類簇。由于DBSCAN的參數(shù)對于類簇密度變化敏感，該算法將圖6c上方的類簇識別為了2個不同的類簇。FKNN-DPC沒有在Flame數(shù)據(jù)集上取得正確的聚類結果，因為該算法在分配Flame的邊界點時沒有考慮到數(shù)據(jù)點間的密度關系，導致其錯誤地分配了4個樣本，如圖13c。其余的DPC算法以及DPC的改進算法在Flame上都能夠獲得正確的聚類結果。從圖13e中可以看出，DBSCAN錯誤地分配了Flame中的2個邊界點，導致其沒有獲得正確的聚類結果。通過圖11展示的不同算法在Spiral上的聚類結果可以看出，除了K-means以外其余5個算法都能獲得正確的聚類結果。K-means在3個流形數(shù)據(jù)集上的表現(xiàn)不太理想，因為該算法按照距離最近的原則劃分類簇，這種劃分策略無法處理不符合高斯分布的類簇。Compound數(shù)據(jù)集中有6個類簇，如圖6d，其中位于圖6d右邊的紫色類簇非常稀疏。通過圖10展示的不同算法在Compound上的聚類結果中可以看出，6個算法均沒有識別出位于圖6d右邊的紫色類簇。從圖10e中可以看出，DBSCAN將屬于紫色類簇中的樣本全部錯誤地檢測為了噪聲。本文算法和RDDPC算法能夠識別出Compound中的6個類簇。通過對比圖10a和圖10d展示的本文算法和RDDPC算法在Compound上的聚類結果可以看出，本文算法可以正確地分配更多的非聚類中心點。因此，本文算法在Compound上的聚類結果優(yōu)于RDDPC算法。DPC和FKNN-DPC均正確地識別出Compound中的6個類簇，其原因是Compound中右邊的紫色類簇不但稀疏，而且還包圍了另外1個類簇，這使得2個類簇很難被聚類算法區(qū)分出來。

圖6 8個人工數(shù)據(jù)集

圖9 Jain數(shù)據(jù)集上的聚類結果

圖10 Compound數(shù)據(jù)集上的聚類結果

圖11 Spiral數(shù)據(jù)集上的聚類結果

圖13 Flame數(shù)據(jù)集上的聚類結果

接下來討論Aggregation，Mouse，D31和A1這4個符合高斯分布的數(shù)據(jù)集。對于Aggregation數(shù)據(jù)集，從表2中的2個聚類性能指標來看，本文算法的聚類結果略低于DPC，F(xiàn)KNN-DPC和RDDPC，然而，本文算法的聚類結果明顯優(yōu)于K-means和DBSCAN。從圖8展示的不同算法在Aggregation上的聚類結果來看，F(xiàn)KNN-DPC只錯誤地分配了1個樣本，因此獲得了最好的聚類結果。D31和A1是2個類簇間存在重疊樣本的數(shù)據(jù)集，其中每個類簇的大小基本一致。對于這類數(shù)據(jù)集，DPC及其改進算法都能選擇到正確的聚類中心。由于RN-DPC的邊界點檢測策略比FKNN-DPC能夠更準確地識別出類簇邊界，因此，在分配非中心點時能夠更好地避免類簇間重疊樣本對聚類結果的影響。對比圖12a和圖12c，本文算法在D31上可以正確地分配更多的非中心點。對比圖14a、圖14c，本文算法仍然可以正確地分配更多的非中心點。因此，本文算法在A1和D31上的聚類結果都優(yōu)于FKNN-DPC。K-means算法在D31上取得了最好的聚類結果，這充分地體現(xiàn)了該算法聚類高斯分布類簇的能力。Mouse數(shù)據(jù)集中的類簇仍然服從高斯分布，但是它包含的3個類簇中有一個類簇較大，其余2個較小。從表2所示中的不同算法在Mouse上的聚類結果可以看出，RN-DPC在Mouse數(shù)據(jù)集上的聚類結果僅次于FKNN-DPC。從圖7f可以看出，K-means算法根據(jù)樣本與聚類中心的歐式距離對樣本進行劃分，這導致遠離Mouse中最下方類簇中心的一些樣本被錯誤地分配到2個規(guī)模較小的類簇中。這也說明了K-means算法只能處理高斯分布的數(shù)據(jù)集并且數(shù)據(jù)集中的類簇規(guī)模不能相差太大。從圖7e可以看出，DBSCAN算法將Mouse數(shù)據(jù)集中最下方的類簇的大量邊界點錯誤地檢測為了噪聲，沒有取得較好的聚類結果。DPC和RDDPC在Mouse上發(fā)生聚類錯誤的主要原因是在分配邊界點時發(fā)生了密度跳躍，密度跳躍進一步引起連續(xù)錯誤效應。從圖7b和圖7d可以看出，DPC和RDDPC錯誤地分配了較多的邊界樣本，所以最終的聚類結果不理想。

圖8 Aggregation數(shù)據(jù)集上的聚類結果

圖12 D31數(shù)據(jù)集上的聚類結果

圖14 A1數(shù)據(jù)集上的聚類結果

圖7 Mouse數(shù)據(jù)集上的聚類結果

3.3 真實數(shù)據(jù)集上實驗對比分析

真實數(shù)據(jù)集上聚類結果如表3。從表3中可以看出，RN-DPC算法在8個真實數(shù)據(jù)集上的聚類性能評價指標均值優(yōu)于其余5個算法，取得了較好的聚類結果。RN-DPC算法除了在Dermatoloy數(shù)據(jù)集上的NMI值低于K-means以外，在剩余數(shù)據(jù)集上都能取得較好的聚類結果。本文所提出的RN-DPC算法在8個真實數(shù)據(jù)集上的NMI均值相比較于FKNN-DPC和DPC分別提升了4.09%和10.2%，ARI均值相比較于FKNN-DPC和DPC分別提升了6.84%和15.4%。

表3 真實數(shù)據(jù)集上的實驗結果

FKNN-DPC算法取得了僅次于RN-DPC算法的聚類結果。K-means算法的聚類結果排名第3，優(yōu)于DPC，RDDPC和DBSCAN。對比K-means在人工數(shù)據(jù)集和真實數(shù)據(jù)集上的聚類結果，可以看出，K-means在真實數(shù)據(jù)集上的聚類結果遠遠優(yōu)于其在人工數(shù)據(jù)集上的聚類結果。其原因是人工數(shù)據(jù)集中大部分數(shù)據(jù)集的類簇規(guī)模大小不一致且類簇形狀十分不規(guī)則，所以，K-means算法無法很好地處理這些數(shù)據(jù)集。但是，在真實數(shù)據(jù)集中，大部分數(shù)據(jù)集中的類簇符合高斯分布。因此，K-means算法可以在真實數(shù)據(jù)集上取得不錯的聚類效果。RN-DPC算法是基于密度選擇聚類中心和k近鄰思想分配非聚類中心，不僅可以處理不規(guī)則的類簇，而且也可能聚類高斯分布的類簇。所以能夠在人工數(shù)據(jù)集和真實數(shù)據(jù)集上都取得較好的聚類結果。

本文所提出的RN-DPC算法能夠取得較好的聚類效果的原因有以下幾點。

1)本文算法在度量樣本密度時使用一種新的相對密度度量方法，該方法能夠消除不同類簇間的密度差距，更客觀地度量樣本的密度。

2)本文引入反向k近鄰關系進行邊界點檢測，該方法可以減小類簇間密度差異對邊界點檢測的影響。

3)本文算法在設計第一步基于k近鄰的分配策略時引入共享最近鄰相似度，充分考慮了樣本的共同鄰居信息，使得樣本間的相似度度量更合理。

4 總 結

本文為了解決DPC的密度度量無法消除不同類簇間的密度差距以及FKNN-DPC算法的邊界點檢測方法無法應用到有密度差距的數(shù)據(jù)集中的問題，定義相對密度并結合近鄰關系提出RN-DPC算法。首先，該算法利用樣本的反向k近鄰數(shù)計算相對密度，根據(jù)相對密度計算樣本的相對距離以選擇聚類中心; 其次，根據(jù)樣本的反向k近鄰數(shù)進行邊界點檢測; 然后，針對非邊界點，根據(jù)樣本間的共享最近鄰相似度定義核心樣本，分配非邊界點中滿足核心樣本定義的樣本; 最后，采用k近鄰分類的思想設計分配策略用于分配非邊界點中不滿足核心樣本定義的樣本，得到聚類結果。經(jīng)過實驗驗證，本文所提出的RN-DPC算法不僅可以聚類有密度差距的類簇，而且在滿足高斯分布的類簇上也有較好的聚類效果。希望本文的研究工作能夠為如何處理復雜場景下的聚類任務提供思路。未來工作將進一步研究如何構建更有效的聚類模型。