基于雙重密度和簇間近鄰度的密度峰值聚類算法

李沛武，張永芳，黃逸翠，劉紫亮，居 翔

(南昌工程學院 信息工程學院，江西 南昌 330099)

數(shù)掘挖掘因具有數(shù)據(jù)過濾的高效性和獲取信息的便捷性而備受關注，聚類算法是其經(jīng)典的技術[1]。聚類算法無需先驗知識，根據(jù)樣本點間的相似性將數(shù)據(jù)集劃分成對應的簇[2]。聚類算法大致包括5種：基于劃分的聚類、基于層次的聚類、基于密度的聚類、基于網(wǎng)格的聚類和基于模型的聚類，每一種算法都有其對應的優(yōu)點和缺點[3]。

Rodriguez[4]等在2014年提出密度峰值聚類算法(Density Peaks Clustering，DPC)，該算法不同于傳統(tǒng)的密度聚類，具有參數(shù)少、能發(fā)現(xiàn)非球狀簇、對噪聲點不敏感的特點。但對密度分布不均衡數(shù)據(jù)集聚類時，DPC算法未考慮樣本點空間分布，會導致聚類效果不佳，在分配過程中易產(chǎn)生連帶錯誤。為解決以上缺陷，很多研究者對DPC算法進行改進。針對局部密度計算方式存在的不足，文獻[5]引入最近鄰和共享近鄰的概念，定義兩步分配準則，提出基于共享近鄰的密度峰值聚類算法(Shared-nearest-neighbor-based clustering by fast search and find of density peaks，SNN-DPC)，提高了算法對于不同數(shù)據(jù)集聚類的準確性。文獻[6]引入逆K近鄰的思想改進局部密度公式，緩解了DPC算法對密度不均數(shù)據(jù)集聚類效果不佳的問題。文獻[7]融合共享K近鄰和共享逆K近鄰改進樣本點間的相似性，改善了DPC算法不能很好處理簇間密度分布不均的情況。文獻[8]將自然和共享近鄰算法結合重新定義局部密度的計算規(guī)則，使算法在性能等方面有明顯的提升。文獻[9]將密度比例思想引入密度峰值聚類中，通過計算兩個鄰域內(nèi)密度平均值之比來重新定義樣本的相對密度，提高了對于密度較小類簇中心的識別度。文獻[10]引入改進凝聚度的思想，使用節(jié)點凝聚度替代樣本點相對密度的計算，通過在真實數(shù)據(jù)集和人工數(shù)據(jù)集上的實驗證明，改進算法能找到更高精度的聚類中心。針對樣本分配存在的不足，文獻[11]借鑒萬有引力公式，重新定義樣本點與簇間的相似性，將未分配樣本點劃分給相似性高的簇，提高了在復雜數(shù)據(jù)集中樣本點分配的正確率。文獻[12]提出了兩步分配策略，對于核心點按照密度遞減的順序分配給最近的簇中心點，對于離群點根據(jù)鄰近樣本點所屬簇信息進行劃分。改進算法不僅能很好處理含有噪聲點的數(shù)據(jù)集，而且能適應大規(guī)模數(shù)據(jù)集。文獻[13]提出新的樣本分配策略，首先將簇中心的K個近鄰點分配給對應的類簇，其次將未分配點劃分給相互近鄰度最高樣本點所在的類簇，解決了數(shù)據(jù)集密度不均聚類效果不佳的問題。雖然上述改進算法都提高了算法的準確度，但部分算法未重視樣本空間結構的影響。文獻[14]提出樣本點進行類簇分配時，不僅要考慮與密度較大點之間的距離，還要考慮K近鄰對樣本點的影響，改進算法減少了對密度較大樣本點正確分配的依賴性。文獻[15]提出結合K近鄰思想的統(tǒng)計學習分配策略，根據(jù)樣本點K近鄰中屬于各類簇的樣本個數(shù)決定所屬類簇，改進算法提高了樣本分配的準確。文獻[16]提出微簇融合策略，根據(jù)簇間密度差和簇間距離進行微簇合并，改善了剩余樣本點分配的容錯性，提高樣本分配的效率。文獻[17]利用第一宇宙速度建立兩步樣本點分配策略，通過每一個未分配樣本點與簇類中心點之間的第一宇宙速度比較，把未分配點劃分為必然屬于和可能屬于該類簇，針對可能屬于該簇的樣本點進行再一次對比，此分配方法使剩余樣本點的分配更加準確。文獻[18]將K近鄰算法與圖標簽傳播結合改進密度峰值聚類算法，利用K近鄰圖傳播動態(tài)地對剩余未分配樣本點進行類簇劃分，提高了聚類的準確性。

針對DPC算法存在的問題，本文提出了一種基于雙重密度和簇間近鄰度的密度峰值聚類算法(Density peak clustering based on dual density and inter cluster proximity，DI-DPC)。首先，DI-DPC算法根據(jù)樣本密度受局部特征和全局特征的影響，在融合K近鄰和截斷距離的基礎上提出雙重密度計算準則，提高了聚類結果的準確率；其次，根據(jù)樣本點的相對密度和相對距離選出候選中心點，并將未分配樣本點分配給距離最近、密度更大的樣本點所在的簇，生成候選微簇；最后，根據(jù)簇與簇之間的近鄰度進行簇間合并，緩解樣本點連鎖式錯誤分配的問題。通過實驗證明，改進的算法有效地改善了對密度分布不均衡數(shù)據(jù)集聚類效果不佳和對未分配點劃分類簇易出現(xiàn)連帶錯誤的情況。

1 DPC算法

DPC算法假設簇中心周圍近鄰點的密度相對較小，且簇中心與其它密度更大點距離相對較遠。因此DPC算法定義了局部密度ρi和相對距離δi兩個變量。

假設數(shù)據(jù)集DN×M=[x1，x2，…，xN]T，其中N為樣本個數(shù)，M為樣本維數(shù)。DPC算法在計算局部密度ρi時，有兩種計算方法，如式(1)～(3)所示：

(1)

(2)

(3)

式中dc為截斷距離，dij為樣本點i與樣本點j間的歐氏距離。式(1)稱為截距核，適用于數(shù)據(jù)量較大的數(shù)據(jù)集；式(3)稱為高斯核，適用于數(shù)據(jù)量較小的數(shù)據(jù)集。

相對距離δi指樣本點到最近局部密度更大點的距離。對于密度最大點，其相對距離δi表示樣本點間距離的最大值；反之，相對距離δi表示樣本點i與密度比其大的樣本點間的最短距離，如式(4)所示：

(4)

計算出以上兩個參數(shù)之后，構造以ρ為橫坐標，δ為縱坐標的決策圖，選擇局部密度ρ和相對距離δ相對較大的樣本點作簇中心，最后將未分配樣本點劃分給比其密度大且最近的樣本點所在的簇。

2 DI-DPC算法

2.1 融合截斷距離和K近鄰的雙重密度

針對DPC密度計算存在的問題，本文提出融合截斷距離和K近鄰雙重密度計算方法，過程如下：

由于DPC算法聚類結果對dc取值比較敏感，本文根據(jù)文獻[17]定義的公式計算dc，如式(5)所示，以減少計算過程中參數(shù)的使用量。

(5)

定義1基于K近鄰的局部密度。根據(jù)樣本點與K個近鄰點的距離定義基于K近鄰的局部密度，如式(6)所示：

(6)

定義2基于截斷距離的局部密度。在考慮樣本點間結構的前提下，本文重新定義樣本點i與其截斷距離范圍內(nèi)樣本點間的距離，如式(7)所示：

(7)

式中y_dc(i)為已劃分類簇的集合；n_dc(i)為未劃分類簇的集合。計算基于截斷距離的局部密度步驟分三步進行：(1)將樣本點i截斷距離范圍內(nèi)的近鄰點根據(jù)距離降序排列，同時將樣本點i存入到y(tǒng)_dc(i)，將其它近鄰點依照排序存入n_dc(i)；(2)依次計算y_dc(i)中樣本點與n_dc(i)中樣本點的最小距離，并將計算出最小距離的樣本點由n_dc(i)移入中y_dc(i)并對計算出的距離求和；(3)直到n_dc(i)為空時，停止遍歷。

定義3雙重密度。融合K近鄰和截斷距離的雙重密度計算公式，如式(8)～(9)所示：

ρave_i=(ρKnn_i+ρdc_i)/2，

(8)

(9)

2.2 基于簇間近鄰度的多簇合并準則

針對DPC算法分配策略存在的問題，本文提出基于簇間近鄰度的多簇合并準則。進行多簇合并前需要生成候選簇，其過程為從依據(jù)式(4)～(9)計算出樣本點相對距離和相對密度構造的決策圖中獲取p個候選簇中心點(C≤p≤5C，C表示實際類簇個數(shù))，然后將未分配樣本點依照密度降序劃分給距離最近、密度更大的樣本點所在的簇，顯然生成的候選簇數(shù)量大于或等于實際的類簇數(shù)量。為獲得更好的聚類結果，需要將相鄰的或距離相近的簇進行合并，因此本文提出新的多簇合并算法規(guī)則定義如下：

定義4簇間近鄰度。統(tǒng)計每個簇邊緣點dc范圍內(nèi)其它簇的點個數(shù)，如式(10)所示：

(10)

(11)

式中截斷距離dc根據(jù)式(5)定義；M(dij-dc)=1表示i點與j點不在同一個簇中且兩者間距離小于截斷距離，否則M(dij-dc)=0。mij表示樣本點i所在簇與樣本點j所在簇之間的近鄰度，簇間近鄰度越大，表明簇間相似性越大。

基于簇間近鄰度的多簇合并過程主要計算候選簇間的近鄰度mij，將計算出的mij放入構建的簇間近鄰度矩陣，從矩陣中選擇最大近鄰度對應的兩個候選簇進行合并，直到候選簇數(shù)等于實際簇數(shù)為止。

2.3 算法步驟及分析

綜上所述，改進算法采用雙重密度法則計算樣本相對密度，依據(jù)DPC算法中類簇中心的選擇機制選出候選類簇中心，將剩余樣本點分配給鄰近候選類簇，最后依據(jù)改進的類簇合并法則進行剩余樣本點分配，從而形成最終的類簇。DI-DPC算法的具體流程如下：

step1 讀取數(shù)據(jù)，對數(shù)據(jù)進行最大最小歸一化處理；

step2 按照式(6)～(9)計算局部密度；

step3 根據(jù)式(4)計算相對距離；

step4 構建決策圖，選出候選簇中心點；

step5 將未分配點劃分給最近的密度較大點對應的簇；

step6 根據(jù)式(10)～(11)計算候選簇間的相似性，構建簇間近鄰度矩陣；

step7 遍歷簇間近鄰度矩陣獲得最大值，合并對應的候選簇；

step8 直到候選簇的個數(shù)等于真實簇個數(shù)時，輸出聚類結果。

2.4 算法時間復雜度分析

為更好地分析DI-DPC算法的時間復雜度，本文先對DPC算法的時間復雜度進行分析。樣本數(shù)為n的數(shù)據(jù)集進行密度峰值聚類的時間復雜度主要包括以下三個方面：(1)計算樣本點相對密度時，需要兩重循環(huán)遍歷所有樣本構建樣本間的距離矩陣，因此其時間復雜度量級為O(n2)。(2)計算樣本點相對距離時，需要對所有樣本與其它樣本的距離和密度進行比較，因此需要兩重循環(huán)所有樣本，其相應的時間復雜度量級為O(n2)。(3)在進行剩余樣本點的分配時，根據(jù)剩余樣本點與已選出的C(C表示實際類簇個數(shù))個聚類中心點間距離進行比較，因此該階段的時間復雜度為O(n×C)。綜上所述，DPC算法的時間復雜度量級為O(n2)。

DI-DPC算法相較于DPC算法改進部分的時間復雜度主要包括：(1)改進的相對密度計算的時間復雜度包含以下兩個步驟：基于K近鄰的密度計算的時間復雜度為O(n×K)，其中K的取值遠小于n的取值；基于截斷距離的局部密度也需要雙重遍歷所有樣本構建距離矩陣，其時間復雜度量級為O(n2)。因此該階段整體的時間復雜度量級為O(n2)。(2)進行候選簇合并時，遍尋簇間近鄰度表的時間復雜度為O(p×n)，其中C≤p≤5C。綜上所述，DI-DPC算法的時間復雜度與DPC算法的時間復雜度量級一致為O(n2)。

3 實驗結果與分析

本文使用9種經(jīng)典人工數(shù)據(jù)集以及9種UCI真實數(shù)據(jù)集證明DI-DPC算法的有效性，并將DI-DPC算法與DPC[4]、SNN-DPC[5]、FCM[20]、K-means[21]、DBSCAN[22]進行性能對比，采用準確率(ACC)[23]、調(diào)整蘭德系數(shù)(AMI)[24]、調(diào)整互信息(ARI)[24]作評價標準。采用Spyder進行實驗，所有程序均采用Python實現(xiàn)。

在實驗之前，對所有的數(shù)據(jù)集進行最大最小歸一化處理如式(12)所示，使數(shù)據(jù)的不同特征歸一到一個范圍下，降低算法運算時間開銷。

(12)

式中max(xj)、min(xj)分別代表j列中的最大值和最小值。

3.1 算法參數(shù)設置

為更好客觀地測試各算法的聚類性能，本文對每種算法進行了參數(shù)調(diào)優(yōu)。DI-DPC算法、SNN-DPC算法需要設置樣本近鄰數(shù)K，一般從1～20中選出最優(yōu)參數(shù)作為樣本近鄰數(shù)K。K-means算法需要給出類簇數(shù)K，但K-means選取類簇中心點存在隨機性，所以需要進行50次實驗取最好結果。FCM算法需要事先指定類簇的個數(shù)K。DPC需要確定截斷距離dc，取值參照文獻[4]規(guī)定，使落入圓中點個數(shù)占數(shù)據(jù)集總數(shù)的1%～2%。DBSCAN需要確定鄰域半徑ε和最小樣本點數(shù)Minpts，鄰域半徑ε取值從0.01～1.20，步長為0.01；最小樣本點數(shù)Minpts取值從1～50，步長為1。

3.2 人工數(shù)據(jù)集結果分析

采用人工數(shù)據(jù)集實驗的主要目的是比較每種算法在不同數(shù)據(jù)集上的聚類效能。表1列出了9種人工數(shù)據(jù)集的具體屬性信息以及DI-DPC算法在9種人工數(shù)據(jù)集上的聚類結果。

表1 人工數(shù)據(jù)集及其聚類結果

表1是6種算法在人工數(shù)據(jù)集上的對比結果，加粗加黑的部分表示結果中相對較好的。具體情況是：在Jain數(shù)據(jù)上，DI-DPC算法的性能最好，評價標準的取值都可達到最大值1.000，而SNN-DPC、K-means及FCM的性能相對較差；在Aggregation和Flame數(shù)據(jù)集，DPC和DI-DPC算法相較于K-means和FCM聚類結果是較優(yōu)；在Spiral數(shù)據(jù)集上，K-means、FCM聚類效果較差，其余4種皆可取得最優(yōu)值；在R15數(shù)據(jù)集上，4種經(jīng)典算法及SNN-DPC算法的準確率僅有0.992，而DI-DPC算法的準確率為0.996，準確率提高了0.4%；在Pathbased、D31、S2、Five_clusters數(shù)據(jù)集上，DI-DPC算法為6種算法中的最優(yōu)算法，ACC、AMI和ARI都有較大的提高。為更好證明DI-DPC算法的優(yōu)越性，本研究選取3種聚類算法在3組人工數(shù)據(jù)集上的聚類效果圖進行詳細說明，其中效果圖中不同形狀的樣本點代表不同的類簇。

Jain數(shù)據(jù)集中兩個簇的密度相差較大，上半部分密度較為稀疏，下半部分密度較大。簇間密度不均導致聚類中心點選取易在一個簇中。通過圖1可以看出，3種算法中只有DI-DPC算法分類是正確的；DPC、SNN-DPC都錯誤地將一個簇劃分成兩個。相比之下，在處理Jain數(shù)據(jù)集時，DI-DPC算法更好。

圖1 3種算法對Jain數(shù)據(jù)集的處理結果

Five_clusters數(shù)據(jù)集中樣本點總體密度較大且數(shù)據(jù)集相對較為密集。從圖2可知，3種算法對于Five_clusters數(shù)據(jù)集處理的結果中，SNN-DPC算法和DI-DPC算法對于該數(shù)據(jù)集的分類是相對較好的，但DI-DPC算法對兩簇間的樣本點的聚類效果更好，DI-DPC算法的聚類效果更優(yōu)。DPC算法存在將一個簇劃分為2個簇的情況，聚類結果相對較差。

圖2 3種算法對Five_clusters數(shù)據(jù)集的處理結果

Aggregation數(shù)據(jù)集是由7個相對集中的類簇組成，其中部分類簇之間相互連接。由圖3可以看出，DPC、SNN-DPC算法錯誤地將一個完整的類簇劃分為兩個類簇；DI-DPC算法較好地保留了類簇的完整性。整體上來看，在Aggregation數(shù)據(jù)集上，DI-DPC算法的性能較好。

圖3 3種算法在Aggregation數(shù)據(jù)集上的處理結果

綜合上述內(nèi)容，可以看出DI-DPC算法在處理人工合成數(shù)據(jù)集的時候，可以獲得良好的聚類結果。

3.3 UCI數(shù)據(jù)集結果分析

為了進一步驗證算法的效果與性能，本文選擇了9種規(guī)模和維度有較大區(qū)別的UCI數(shù)據(jù)集。表2中總結了9種UCI數(shù)據(jù)集的相關屬性，以及DI-DPC算法與K-means、DPC、DBSCAN、SNN-DPC算法在ACC、AMI、ARI上的對比。

通過表2可看出，DI-DPC算法相對于其它4種算法有不同程度的提高。在Wine數(shù)據(jù)集上，DI-DPC算法的AMI和ARI取值次于SNN-DPC算法，但ACC值高于4種對比算法；在Movement_libras數(shù)據(jù)集上，本文算法的ACC值低于SNN-DPC算法，但其它兩個評價函數(shù)的取值高于其它算法；在其它數(shù)據(jù)集上，DI-DPC算法的聚類效果好于其它4種對比算法。通過上述分析可以得到，DI-DPC算法聚類效果更好。

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

4 結束語

針對DPC算法存在的問題，本文提出了基于雙重密度和簇間近鄰度的密度峰值聚類算法。DI-DPC算法提出了基于K近鄰和基于截斷距離的雙重密度計算公式，提高了對密度不均衡數(shù)據(jù)集聚類時的準確性，同時增強了不同空間結構樣本的相互作用；提出了新的簇合并法則，改善了DPC算法分配策略的不足之處。通過在人工合成數(shù)據(jù)集以及UCI真實數(shù)據(jù)集聚類結果證明，DI-DPC算法相較于經(jīng)典聚類算法、SNN-DPC算法都取得良好的分配結果。但DI-DPC算法在選取聚類中心時，會受到人為選擇和經(jīng)驗值的影響，造成額外的時間成本，因此自動獲取聚類中心將會是下一步實驗的方向。