優化分配策略的密度峰值聚類算法*

丁志成，葛洪偉+

1.江南大學 江蘇省模式識別與計算智能工程實驗室，江蘇 無錫 214122

2.江南大學 物聯網工程學院，江蘇 無錫 214122

1 引言

聚類作為一種無監督的學習方法，是數據挖掘的重要分支，它通過將對象的屬性按照某種特定的標準進行相似性劃分從而將數據集分割為若干不同的簇類，最大化相同簇類內的數據屬性相似度，并最小化不同簇類間的數據屬性相似度[1]。在信息全球化的背景下，對于挖掘潛在、有價值數據的要求與日俱增，因此聚類在航天航空、市場分析、信息安全、人工智能、Web搜索等領域[2-3]得到了深入的研究與推廣。

由于聚類分析有著極強的實用性與延展性，經過學者們的多年研究和努力，眾多優越的相關算法被相繼提出，其中較為經典的算法有：基于劃分的Kmeans[4]、K-medoids[5]算法；基于網格的STING（statistical information grid）[6]、CLIQUE（clustering in quest）和WaveCluster[7]算法；基于層次的CURE（clustering using representatives）[8]、Chameleon[9]等聚類算法；基于密度的DBSCAN（density-based spatial clustering of applications with noise）[10]、OPTICS（ordering points to identify the clustering structure）[11]算法。

Rodriguez、Laio 于2014 年在權威期刊Science中發表了一篇關于新型的基于密度的聚類算法論文：快速搜索與發現密度峰值聚類（clustering by fast search and find of density peaks，DPC）[12]算法。DPC 算法的關鍵點在于：利用決策圖手動選擇密度峰值作為所需要的聚類中心點，隨即將剩余點分配給與之距離最近的聚類中心點所屬類簇，最后對分配結果進行噪聲識別從而完成聚類。與大部分經典的基于密度的算法相比，該算法簡潔高效，無需迭代，只需一個截斷距離參數dc，能夠發現數據集中所有任意形狀的簇類并且可以有效消除離群點。盡管如此，DPC算法依然容易在分配復雜結構數據集數據點時出現錯誤，導致聚類效果不理想。

針對DPC 算法存在的缺陷，Xu 等人提出了基于γ線性擬合的DenPEHC（density peak based efficient hierarchical clustering）密度峰值聚類算法[13]，利用γ排序圖的變化趨勢產生了自適應的聚類中心并改進了聚類分配機制，但在高維數據處理上容易出現錯誤聚類。Xu 等人提出了分別基于網格劃分和圓劃分的密度峰值聚類算法GDPC（density peaks clustering algorithm with gird-division strategy）和CDPC（density peaks clustering algorithm with circle-division strategy）算法[14]，兩者都優化了密度峰值的聚類分配。GDPC算法耗時更少而CPDC 算法在大型數據集上具有更高的準確率，但在處理復雜結構數據集時會出現分配錯誤的情況。金輝等人提出了自然最近鄰優化的

TNDP（optimized density peak clustering algorithm by natural nearest neighbor）算法[15]，利用自然鄰居概念計算數據點的局部密度，再使用類簇間相似度合并簇類，算法雖然有較優的聚類效果，但無法很好地識別數據集噪聲。

因此，本文針對以上算法的缺陷，提出一種優化分配策略的密度峰值聚類算法（density peaks clustering with optimized allocation strategy，ODPC）。新算法利用相似度指標MS分配對象數據集的數據點，然后通過dc近鄰法重新界定邊界區域中的噪聲點。實驗證明，在數據集對象存在高維數據、復雜數據結構、噪聲數據的情況下，新算法可以得到更優的聚類結果。

2 DPC 算法及其缺陷

DPC 算法將符合以下特征的數據點對象定義為密度峰值點即聚類中心：被擁有相對較低局部密度的鄰居點所環繞并且此類數據點和其余擁有相對較高密度的數據點間有較大的距離。算法僅需要截斷距離dc這一個輸入參數，通過人工選取聚類中心點，一步完成所有數據點的聚類與分配。

對于任意數據點Xi，DPC 只需要計算其局部密度ρi以及距離具有更大密度的點的最短距離δi這兩個變量。

局部密度ρi為以dc為半徑的范圍內其余數據點的數量：

式（2）中，di為所有點間的歐式距離的升序排列；N為數據總量；M=N(N-1)/2；round函數表示對M×P/100 四舍五入取整；P為可調參數，DPC 原文中選取P值為2。

δi為距離具有更大密度的點的最短距離：

式（3）中，對于數據集最高密度的數據點K，默認它為數據集的聚類中心點并令其δk為所有距離中的最大值，即δk=max(dij)。

在得到數據點的ρi和δi值后，DPC 算法首先生成相應的決策圖并將同時具有較大ρ和δ值的點視作聚類中心，然后將非聚類中心點依次分配給最接近的聚類中心點所在簇，最后對聚類結果進行噪聲識別，完成聚類。DPC 算法為識別出聚類結果中的噪聲點，引入邊界區域密度ρb的概念：在某簇內卻與屬于其余簇的點距離小于截斷距離dc的數據點中局部密度最大值。而在簇中局部密度ρi大于邊界區域密度ρb的數據點被認為此簇的核心點，反之則視為該簇的噪聲點。

盡管DPC可以快速高效地完成聚類，但是算法仍存在一些缺陷：只有當數據點的ρ和δ值同時大的情況下，該數據點才有可能被選為聚類中心點；對于復雜結構的數據集來說，僅僅通過將數據點分配給距離最近的聚類中心點所屬簇類容易出現錯誤的聚類結果；在噪聲識別階段，直接通過邊界區域密度對核心點及噪聲點進行一次性的劃分也并不是較優的方法。

綜上所述，DPC 算法在面對以下三種情況時仍然會出現較大的誤差：

（1）由于DPC 算法分別單獨考察ρ和δ的大小，僅當數據點在兩值上均大于所選點時才會被確定為聚類中心點，而事實上仍存在部分ρ大δ小或者是ρ小δ大的數據點也為實際聚類中心。如圖1 所示，DPC 算法僅識別到兩個團狀簇的聚類中心而沒有發現環形簇的聚類中心。因此會導致數據集聚類中心點的少選、漏選。

Fig.1 DPC gets less clusters by decision graph圖1 DPC 算法通過決策圖少選聚類中心

（2）當DPC 算法處理如流形數據集等具有復雜數據結構的對象時，會因為只考慮局部密度而無視整體結構一致性以及數據點間的連通性而導致在分配數據點所屬類簇時產生相應的錯誤。如圖2 所示，很明顯，區域C和區域D的數據點應該歸屬于聚類中心點a所屬類簇A類。而在DPC 算法中，由于C區域與D區域中的點距離B類聚類中心點b的距離比a更近因此都被分配到B類中，因此出現了如圖2（b）的錯誤聚類。

（3）DPC 算法依據邊界區域密度ρb的定義對數據集劃分，從而實現聚類結果的噪聲識別。算法會在噪聲點較為密集、局部密度ρ較大的情況下將其錯誤地歸類為核心點或是在核心點較為稀疏、ρ值較小時將核心點錯誤地識別為噪聲點。如圖3 所示，大量的核心點因此被錯誤地識別為噪聲點。

3 優化分配策略的密度峰值聚類算法

3.1 優化的分配策略

定義1令γi作為判斷點i是否為密度峰值點，即聚類中心點的參數指標：

Fig.2 Wrong clustering results caused by allocation strategy of DPC圖2 DPC 分配策略導致的錯誤的聚類結果

Fig.3 Bad denoising result caused by DPC圖3 DPC 導致的不佳的去噪結果

對于擁有相對較大ρ或δ值的聚類中心來說，γ值同樣也會取得較大值，因此γ值具有判斷數據點能否為聚類中心的作用。記對象數據集為U(x)，樣本數據點總量為N，對所有數據點進行關于γ的降序排列γdes。在決策圖上，將數據點的參數積γi大于被選點γ值的點視作聚類中心。

定義2令MS為衡量數據點間相似度的參數指標，稱為相似度指標，其公式為：

本文借鑒牛頓萬有引力定律[16]對數據點進行基于相似度的局部連通性分配。萬有引力公式為F=，公式中M和m表示兩個差異個體的各自質量，G為萬有引力常量，r為個體間的距離，反映的是存在于力場中的任意兩個不同個體間都存在著互相吸引的力，這個力與它們的質量成正比而和它們間距離的平方成反比，其本質是物體將力通過空間向四周傳遞，距離越長則傳遞的力越小。

參照自然界中物體間的吸引力作用，將之引申到數據結構空間中，可以發現數據空間中也有類似“場”的存在，其表現為：數據集中距離越近，密度越大，局部密度越相似的兩點，其相互作用力越大，同樣其相似度也越高。因此本文利用萬有引力公式的變式來描述數據點間的相似度，式（5）中的G為相似度參數，ρi、ρj分別為數據集中任意兩點的局部密度，而dist(i,j)則表示任意兩點間的歐式距離。

在數據空間中，數據點默認體積一致，將其視作單位1，則質量M、m分別轉化為局部密度ρi、ρj。由路網模型及其應用[17]可知，數據點所處區域的局部密度密切影響著點間相似度，并且在兩點的局部密度越接近時，其相似度也越高，因此使用相似度參數G用以表示空間數據集的局部連通性。公式G=中，|ρi-ρj|用以表示不同數據點的局部密度差異，與其對應的相似度成反比，因此對公式的指數取反；引入ρmax-ρmin并使用e為底的指數函數以限制G的取值范圍，因此式（6）最終為取值在[1/e,1]區間的相似度參數，其參數值與點間相似度成正比。相似度指標也最終根據萬有引力公式變式為式（5）。

Fig.4 Clustering results caused by different allocation strategies of algorithms圖4 不同的算法分配策略導致的聚類結果

DPC 算法中，利用數據局部密度ρi和該點到具有更大局部密度的點的最短距離δi兩值確定聚類中心點后，直接依照距離簇中心的距離，將數據點歸類為最接近的聚類中心點所屬簇。而ODPC 算法使用優化的分配策略如下：首先通過式（4）計算所有點的γi值，將參數積γi大于選中點γ值的點作為聚類中心點；然后按照降序排列γdes的順序，依次將γ值漸小的點分配給在已被分配簇類的數據點中，與其相似度最大的點所在的類簇，完成聚類。

以數據集Compound 為例，如圖4（a）所示的DPC算法在數據集Compound 上的聚類結果，點1 和點2分別為兩簇的聚類中心點，DPC 算法通過最近聚類中心點分配的方法將點3 與點2 錯誤地歸于同一類。而在新算法ODPC 中，如圖4（b）所示，點4 在已被分配類簇的數據點集合中與點1 的相似度指標MS值最大，因此兩點被分為同一類。同理，點5 與點4，點6 與點5，點7 與點6，點8 與點7，點9 與點8，點10與點9，直到點3 與點10 都通過相似度指標MS歸為同一類，因而點1 與點3 屬于一類。依此類推，整個環狀流形區域均被劃分為一類，而中間的團狀簇則被劃分為另一類，因此ODPC 算法得到如圖4（b）所示的正確聚類效果圖。

3.2 優化識別噪聲點

DPC 算法中，使用邊界區域密度的概念對所有數據點進行統一識別，大于邊界區域密度的點定義為核心點，反之則視作噪聲點。這一策略容易導致分布較為稀疏的核心點或是分布較為稠密的噪聲點被錯誤識別，如圖5（a）所示，大量的核心點被錯誤識別從而降低了算法的魯棒性。

分布較為稀疏的核心點與分布較為稠密的噪聲點多出現于簇類的邊緣區域，而這塊區域與DPC 定義的邊界區域極為相似。因此為了更好地識別數據集的噪聲點與核心點，新算法對邊界區域的數據點進行二次識別，有助于從健壯性角度提升ODPC 算法的聚類質量。由于初次識別后所有數據點都已經被劃分為相應的核心點或是噪聲點，本文參照K近鄰算法[18]，使用新的dc近鄰法優化噪聲識別。

Fig.5 Effect of different noise recognition methods圖5 不同噪聲識別方法的效果

定義3（dc近鄰法）對以邊界區域數據點i為核心，dc為半徑的區域進行考察，若范圍內噪聲點更多則識別該點為噪聲點，反之則識別為核心點。

根據DPC 中局部密度ρi的定義，本文通過dc近鄰法引入邊界區域噪聲密度ρi′的概念，對邊界區域的數據點重新識別噪聲。

定義4定義邊界區域i點的區域噪聲密度ρi′為，以i點為核心，dc為半徑的區域內噪聲點比核心點多的數量，其計算公式為：

其中，對象數據集為U(x)，噪聲點集合為Ni，核心點集合為Co，j∈U(x)。對邊界區域的數據點按照γ值降序排列的順序進行重新分配，若ρi′≥0，i點的dc近鄰中噪聲點較多，將其劃分到噪聲點集合Ni中；若ρi′＜0，則其dc近鄰中有更多核心點，因此將i點劃分到核心點集合Co中。將識別過程中未改變所屬集合的點的集合作為新的邊界區域，遞歸該識別過程直到邊界區域不再發生變化，至此完成對邊界區域所有數據點的噪聲識別。以圖5（b）中數據集Flame 的聚類效果為例，經過ODPC 的dc近鄰法對邊界區域噪聲點的重新識別，流形簇和團狀簇中均有更多分布較為稀疏的核心點被正確識別。不同于DPC 算法將噪聲識別與算法聚類效果割裂開，ODPC 算法則是將數據對象中的噪聲去除后再進行聚類效果分析，消除了數據集噪聲點對聚類效果的負面影響，因此新算法在Flame 數據集上的兩個聚類評價指標均為1，得到了完全正確的聚類結果。實驗證明優化的噪聲識別有著更好的準確性和抗干擾性。

3.3 算法步驟分析

輸入：實驗數據集U(x)={x1,x2,…,xn}，數據點的鄰居點數目占數據總數的比例P。

輸出：聚類結果C={C1,C2,…,Ch}，h為總簇類數量。

步驟1選取P值為2，根據式（2）計算出截斷距離dc。

步驟2根據式（1）、式（3）分別計算數據集中所有點的局部密度ρi以及最短距離δi。

步驟3生成有關ρi和δi的決策圖，根據式（4）得到的γ值在決策圖上選取聚類中心。

步驟4根據式（5）、式（6）引入相似度指標MS，對關于γ的降序排列γdes中的非聚類中心點，進行依次分配：將未劃分簇類的數據點分配到已歸類并且相似度指標MS最高的點所在簇。

步驟5根據式（7）計算數據集邊界區域點的邊界區域噪聲密度ρi′，若ρi′≥0，將i點識別為噪聲點；若ρi′＜0，則識別該點為核心點。

步驟6將識別過程中未改變所屬集合的點作為新的邊界區域，重復步驟5。

步驟7邊界區域不再發生變化，完成噪聲識別。

3.4 時間復雜度分析

假設聚類實驗的數據集共有n個數據，由第2 章DPC 算法及其缺陷的描述可知，DPC 算法的時間復雜度主要由計算歐式距離(O(n2))、對歐式距離降序排列(O(lbn2))、計 算ρ和δ(O(n2)) 和去噪處理(O(n)) 組成。因此，DPC 的時間復雜度為O(n2)。而DenPEHC算法相較于DPC 算法，不同點在于：對γ降序排列(O(nlbn))和改進的分配機制(O(n2))，因此DenPEHC的時間復雜度為O(n2)。GDPC 算法的時間復雜度主要由網格化數據點(O(n))、快速排序移除稀疏網格(O(nlbn))、利用決策圖聚類數據點(O(h2))、分配其余數據點至K個聚類中心(O(k(n-h)))組成，其中h為經過篩選的數據點(h＜n)，因此GDPC 算法的時間復雜度為O(n)+O(nlbn)+O(h2)+O(k(n-h))。而根據3.1節、3.2 節的描述，ODPC 相較于DPC 算法，不一樣的步驟在于優化的分配策略(O(n2))和改進的噪聲識別方法(O(n)+O(m2))，其中m為邊界區域數據點數量，數值遠小于n。因此，ODPC 的算法時間復雜度與DPC 算法一致，也為O(n2)。

4 仿真實驗與性能分析

為驗證ODPC 算法的效果與性能，本文分別在人工數據集以及真實數據集上進行實驗分析。

4.1 人工數據集的實驗結果與分析

仿真實驗中使用到四個人工數據集，相關信息見表1。分別運行DPC 算法、ODPC 算法、同樣優化分配機制的DenPEHC[13]和GDPC[14]算法，對表1 中數據集進行實驗，實驗結果如圖6～圖9 所示。

對于線狀簇的數據集Spiral，如圖6 所示，四種算法均能得到正確的聚類結果。對于Aggregation 數據集，由圖7 可知，DenPEHC 算法利用γ線性擬合中出現的第一個異常增幅點，將數據集錯誤地分為八類；GDPC 將數據集錯分為十類；DPC 與ODPC 算法則可以得到正確的聚類結果。而對于復雜數據集結構的Compound 數據集，如圖8 所示，DenPEHC 與DPC 算法雖然得到了正確的六個聚類中心點，卻在環形簇的分割上出現了錯誤，將其分成了兩類；GDPC 算法則錯誤地將其分為七個類簇；而ODPC 算法由于使用了基于相似度指標MS的優化分配策略，使得算法能夠在流形簇等復雜的數據集結構中通過局部連通使得聚類能夠反映數據集的全局一致性，從而得到正確的簇類，并且提高了聚類準確度。在Flame 數據集上，DPC 算法則將流形簇兩端的區域錯誤地分配給了團狀簇，如圖9（a）所示；而DenPEHC 算法通過基于γ線性擬合，ODPC 算法通過對數據點進行相似度連通分配，GDPC 算法通過對數據點的網格單元映射分別可以取得如圖9（b）～圖9（d）所示的正確聚類效果。綜上所述，在人工數據集上，ODPC 算法較之DPC、DenPEHC 和GDPC 算法，可以提高密度峰值聚類算法的準確度，得到更優的聚類結果。

Table 1 Four synthetic data sets表1 四個人工數據集信息

Fig.6 Clustering results of Spiral by four algorithms圖6 四種算法在數據集Spiral上的聚類結果

Fig.7 Clustering results of Aggregation by four algorithms圖7 四種算法在數據集Aggregation 上的聚類結果

Fig.8 Clustering results of Compound by four algorithms圖8 四種算法在數據集Compound 上的聚類結果

Fig.9 Clustering results of Flame by four algorithms圖9 四種算法在數據集Flame上的聚類結果

4.2 真實數據集的實驗結果與分析

為進一步驗證ODPC 算法的性能與效果，本文采用F-measure[19]與ARI[20]兩類聚類評價指標并利用表2中的五個真實數據集對DPC算法、基于γ線性擬合的密度峰值算法DenPEHC、基于網格劃分優化的密度峰值算法GDPC 和本文的ODPC 算法進行對比實驗。

Table 2 Five real data sets表2 五個真實數據集信息

兩類評價指標F-measure 的取值在0 到1 之間，而ARI 的取值范圍為-1 到1，在取值范圍內評價指標值越接近1 則表明聚類效果越佳。實驗結果如表3、表4 所示。

Table 3 F-measure index value of four algorithms on real data sets表3 四種算法在真實數據集上的F-measure值

Table 4 ARI index value of four algorithms on real data sets表4 四種算法在真實數據集上的ARI值

由表3、表4 的聚類實驗結果可知，在兩類聚類指標值上，ODPC 算法在所有五個真實數據集上均能取得四種算法中的最大值。DPC、DenPEHC、GDPC 算法盡管在部分數據集上的聚類結果較好，但在面對具有復雜結構的數據集時，數據點更容易被錯誤分配，聚類效果不如ODPC 算法。因此整體來看，ODPC 算法是其中最優的算法。

綜上，ODPC 算法對DPC 算法進行了成功的優化改進，在人工以及真實數據集上的仿真實驗可以有效說明算法能夠獲得更好的聚類分配效果。

5 結束語

為了解決DPC 算法在面對復雜結構數據集時容易出現分配錯誤的問題，本文提出了一種優化分配策略的ODPC 算法。新算法參考萬有引力公式，利用基于相似度指標的MS值對數據集數據點進行更加科學合理的連通性分配；使用dc近鄰法對邊界區域的數據點進行優化的噪聲識別。通過實驗證明，新算法在保留原DPC 算法簡單高效的同時，能夠獲得更好的聚類分配和更優的噪聲識別效果。

由于ODPC 算法沒有實現對聚類中心的自動選擇，在實際運用時會造成額外的時間成本。但是算法引入γ擴大了聚類中心的范圍以避免漏選潛在的密度峰值點，通過算法的多次運行來確保聚類中心選取的正確性和有效性。盡管如此，在實際應用時辨別數據對象是否被正確劃分依然會受到人為判斷和經驗值的影響。因此，如何使ODPC 算法在保證準確率的同時自動選取聚類中心，將會是下一步的研究方向。