基于密度峰值剪枝后的最短路徑聚類算法

胡恩祥，汪春雨，潘美芹

1.上海外國語大學(xué)國際工商管理學(xué)院，上海201600

2.華東師范大學(xué)計算機科學(xué)與技術(shù)學(xué)院，上海200062

最早在1996年由Ester等[1]提出的DBSCAN 算法使人們意識到密度這一概念的引入，不僅能夠直觀地解釋類別是如何分配的，而且對較大體量的數(shù)據(jù)和噪聲點的數(shù)量也有較好的包容性.聚類的速度和準確性得到了明顯的提升和改進.此后，圍繞DBSCAN 算法的領(lǐng)域半徑Eps 值和MinPts 最小點數(shù)量展開了討論，如荊繼武等[2]提出的SA-DBSCAN 仍取MinPts=4，但采用了Inverse Gaussian 擬合曲線模擬第4 近鄰距離下點概率分布圖，用更準確的統(tǒng)計模型計算出實際拐點對應(yīng)的Eps 值.曹晶等[3]提出了PDBSAN 并認為DBSCAN 采用全局參數(shù)，而對不同類型和密度的類別需要分開確定局部參數(shù).通過數(shù)據(jù)特性進行分區(qū)，確定局部參數(shù)，局部聚類后再進行局部類合并.基于分區(qū)的思想，曹晶等[4]又提出了FDBSCAN，通過選擇每一個核心點區(qū)域的代表對象，減少區(qū)域內(nèi)的點被重復(fù)遍歷的次數(shù)和可能.后來，Rodriguez等[5]在密度屬性的基礎(chǔ)上又定義了一個新的距離屬性δ，由此提出了CDP 算法，具有較大的密度值和δ值的點作為聚類中心，然后依次對剩余點進行分類.與DBSCAN 算法相比，該算法的核心是通過引入屬性δ值使聚類中心表現(xiàn)出更“離群”和突出的特性，同時δ值計算過程也暗示了剩余點的分配規(guī)則.這樣的CDP 算法通過巧妙的雙重屬性設(shè)置，解決了DBSCAN 算法中通過單一全局密度值判斷所有潛在核心點的尷尬情景.2019年，Pizzagalli等[6]在剩余點的分配規(guī)則上提出了新的想法，認為剩余點的分配規(guī)則應(yīng)該是基于全局最優(yōu)而不是局部最優(yōu)原則，在對一些特殊的鏈狀數(shù)據(jù)集聚類時CDP 聚類精度出現(xiàn)較大偏差.因此，提出了基于密度峰值的可訓(xùn)練最短路徑算法[6]，通過最短路徑法從全局出發(fā)找到剩余點到真正聚類中心的最佳路徑.但該算法在每次最短路徑計算過程中都需要遍歷全局中所有的路徑節(jié)點，其中包括對某些不會影響最終計算結(jié)果的路徑反復(fù)迭代，降低了算法運行效率.本文基于Pizzagalli等[6]提出的算法，在最短路徑算法的執(zhí)行上基于對路徑圖的預(yù)先評估，通過截斷閾值的設(shè)定對一些不會影響最終計算結(jié)果的遠距離路徑進行剪枝，使這些路徑不會出現(xiàn)在每一次迭代計算中，從而減少最短路徑算法的迭代和運算次數(shù)，提升了算法運算效率，進而改進了算法.

1 國內(nèi)外研究現(xiàn)狀

CDP 算法中密度峰值點之間的距離應(yīng)大于任意一點與比它密度大的點的距離，否則不同密度的類別將無法區(qū)分.針對CDP 算法中局部密度的定義問題和剩余點分配問題，國內(nèi)外學(xué)者展開了研究和討論.Wang等[7]認為基于截斷距離dc的局部密度的定義難以確定參數(shù)最優(yōu)解，而提出了基于非線性多元核估計方程來估計局部密度，并通過最大化平均輪廓系數(shù)自動選擇聚類中心[7].謝娟英等[8]利用K近鄰信息定義樣本點的局部密度以此反映樣本的真實分布信息，提出了基于K近鄰的剩余點樣本分配策略.Wang等[9]將每一個數(shù)據(jù)對象作為物理對象來擴散其對給定任務(wù)的數(shù)據(jù)貢獻，由此產(chǎn)生數(shù)據(jù)字段，進而利用數(shù)據(jù)字段中的熵的不確定性自動提取出最優(yōu)的截斷距離dc，避免了經(jīng)驗估計對于閾值判斷的偏誤.在面對類簇間樣本密度差異較大的情況下，CDP 算法容易忽視密度較小的類簇并將其當(dāng)作噪聲點來處理，高詩瑩等[10]將密度比例引入到CDP 算法中，通過計算密度峰值比來提高密度較小類簇的相對重要性和辨識度.當(dāng)一個類簇中出現(xiàn)多個密度峰值時，CDP 算法無法準確判定聚類中心[10].Zhang等[11]受到層次聚類（hierarchical clustering）算法啟發(fā)，針對這類具有多個密度峰值的簇聚類問題，首先利用CDP 算法生成原始簇，然后根據(jù)集群間的相對互連性和近似性合并子簇.蔣禮青等[12]則受到DBSACN 算法中近鄰距離曲線的啟發(fā)，利用近鄰距離曲線中Υ值的第一次跳躍點來判斷聚類中心并確定其對應(yīng)的截斷距離dc，利用截斷距離dc來指導(dǎo)類的合并及優(yōu)化.Tang等[13]針對基于聚類的無監(jiān)督波段選擇（unsupervised band selection,UBS）方法，認為當(dāng)需要多個聚類中心時，CDP 算法的局部密度ρ和距離δ沒有適當(dāng)?shù)目s放方式，提出了先將局部密度ρ和距離δ歸一化，重新定義Υ函數(shù)，并引入了一個指數(shù)化的啟發(fā)規(guī)則調(diào)整截斷距離dc來提高局部密度ρ的分辨力.此外，CDP 算法剩余點的分配規(guī)則強調(diào)局部最優(yōu)準測，即剩余點只關(guān)心周圍比自己密度更大的點，而不考慮與其他點，尤其是與聚類中心的關(guān)聯(lián)性.Tenenbaum等[14]認為傳統(tǒng)的歐氏距離無法檢測出數(shù)據(jù)點間內(nèi)在的二維屬性，提出了利用測地路徑進行非線性降維的等距特征映射算法（isometric feature mapping,ISOMAP）.對于非線性流體集上的任意兩個點，基于低維流形體利用最短路徑法計算測地距離（geodesic distance,GD），即計算在三維空間中曲面上A和B兩點間的最短距離以此生成一個全局最優(yōu)的關(guān)聯(lián)規(guī)則.Xu等[15]提出了一種流形密度峰值聚類（manifold density peaks clustering,MDP）算法，該算法基于測地距離計算距離矩陣，根據(jù)聚類數(shù)目自動識別出聚類中心并通過ISOMAP 算法實現(xiàn)對高維數(shù)據(jù)集的降維處理.Du等[16]認為在諸如折疊、扭曲、彎曲的流形體數(shù)據(jù)集上CDP 算法不能夠有效地聚類，進而提出了基于測地距離來確定密度峰值的算法.通過重新計算各點之間的測地距離，縮短了處在同一類簇中點與點間的距離，放大了處在不同類簇中的點與點間的距離，密度峰值點的距離δ值將會顯著增加，從而在決策圖上能夠更準確找到密度峰值.本文所介紹的TP-CDP 算法以及在此基礎(chǔ)上提出的PTP-CDP 算法，都是利用截斷距離dc定義局部密度確定聚類中心，在剩余點的分配規(guī)則上則是通過評估各點之間路徑的屬性從全局角度尋找最優(yōu)解.

2 基于密度峰值剪枝后的最短路徑聚類算法

2.1 CDP 算法

CDP 算法[5]假設(shè)聚類中心周圍都是密度比其低的點，且與其他密度較高的聚類中心之間距離更遠，以此形成不同的類別.算法定義密度ρi為點i在給定截斷距離dc內(nèi)點的數(shù)目，該算法只對不同點密度的相對重要性敏感.對大數(shù)據(jù)集來說，其穩(wěn)健性與截斷距離dc的選擇相關(guān)，即

在定義密度屬性后，CDP 算法又定義距離δi為所有密度比i點大的點與i點距離的最小值，即

通常定義密度最大的點與其他點距離的最大值為δi.在CDP 中通過較大的密度ρi和距離δi值確定聚類中心和離群點的情況.具體選擇聚類中心的數(shù)目則通過定義Υi計算出每個點的對應(yīng)值，按照降序排序在圖像中選擇突變點對應(yīng)于聚類中心的數(shù)量，其中

在剩余點的分配問題上，通過CDP 算法，在確定聚類中心后剩余的點按密度降序依次被分配到離該點最近、密度更高的點所屬的類中.剩余點的分配規(guī)則與δi定義存在聯(lián)系，在計算每個點的距離δi時通過尋找距離自己最近且密度比自己大的點，以此形成了某種類的“關(guān)聯(lián)”，即這兩個點相互綁定，歸屬于同一類中.從聚類中心開始向外進行類擴充，遵循密度降序，通過距離δi的穿針引線，每一個點都在局部達成了最優(yōu)的分配結(jié)果.

2.2 基于密度峰值的可訓(xùn)練最短路徑算法

基于密度峰值的可訓(xùn)練最短路徑算法（TP-CDP）[6]針對CDP 算法中剩余點的分配規(guī)則提出了質(zhì)疑，認為剩余點的分配應(yīng)該基于全局最優(yōu)而不是局部最優(yōu).在CDP 算法剩余點的分配過程中，剩余點被分配到最近且密度比自己大的點所屬的類中.其中，如果有密度較大的點分類錯誤，則會導(dǎo)致其附近密度比它小的點也隨之分類錯誤.該算法基于兩種鏈狀數(shù)據(jù)和環(huán)狀數(shù)據(jù)集，證實了CDP 算法中剩余點可能的分配錯誤.在該類數(shù)據(jù)集中，造成CDP 算法聚類錯誤的原因主要是某些其他類別離自己應(yīng)真正所屬的鏈狀、環(huán)狀類間距離太近，導(dǎo)致聚類錯誤.圖1列舉了CDP 在具有上述數(shù)據(jù)分布特征的集上錯誤的聚類結(jié)果.

圖1 CDP 在3 種數(shù)據(jù)集上聚類結(jié)果Figure 1 CDP clustered in three different datasets

圖1中，3 種不同的數(shù)據(jù)集基于CDP 算法聚類出現(xiàn)明顯錯誤的原因相同，這里我們選擇分析圖1(c)的聚類結(jié)果來清楚地解釋CDP 算法聚類發(fā)生錯誤的原因.

如圖2所示，在剩余點的分配過程中出現(xiàn)了某個密度稍大的剩余點3，然而比點3 密度更大點只有作為聚類中心的點1 和2，點3 到達聚類中心點2 的歐氏距離小于到達聚類中心點1 的歐氏距離.此時根據(jù)CDP 剩余點的分配規(guī)則，點3 選擇歸屬于比自己密度更大且距離更近的點所屬的類中，也就是聚類中心點2 所屬的類.由此出現(xiàn)了局部聚類錯誤，而這又會導(dǎo)致點3 周圍密度比自己小，且距離自己較近的其他剩余點也同點3 一樣聚類錯誤.

圖2 CDP 剩余點分配錯誤示意圖Figure 2 Remaining points incorrectly allocated by CDP

針對剩余點的分配問題，TP-CDP 算法提出一種全局最優(yōu)規(guī)則，認為剩余點的分配應(yīng)該基于最短路徑法，從不同的聚類中心出發(fā)選擇到達該點最短距離的路徑，由此確定剩余點所歸屬的聚類中心.算法先假定空間中存在一個虛擬節(jié)點s連接到每一個聚類中心的距離設(shè)置為0，目標是找到以s點為源的所有點的單源最短路徑，對應(yīng)以s點為根的最小生成樹.定義加權(quán)后的路徑成本函數(shù)，即

當(dāng)P≥1 時，路徑成本函數(shù)ξp(Γ)懲罰高成本即距離較大的邊.隨著p值的增大，擁有較大距離的路徑在路徑成本函數(shù)的計算中將占據(jù)更大的權(quán)重，當(dāng)p值趨向正無窮時，路徑成本函數(shù)的計算結(jié)果將近似于單條路徑中的距離最大值.TP-CDP 算法認為有必要懲罰距離較大的路徑，通過賦予這些路徑更大的權(quán)重使較大路徑無法再“走通”.理由是，寧可選擇更多的小路徑拼接起來，絕對距離可能較長的線路，而不愿選擇在絕對距離可能較小，但包含了較大距離的路徑線路，避免因為鏈狀類數(shù)據(jù)圍繞的干擾而產(chǎn)生的局部聚類錯誤.由于單源最短路徑算法每一次運算都要遍歷所有的點計算加權(quán)后的最短距離，因此算法平均時間復(fù)雜度為O(n2).

2.3 基于密度峰值剪枝后的最短路徑聚類算法

本文基于密度峰值的可訓(xùn)練最短路徑算法，提出一種基于密度峰值剪枝后的最短路徑聚類算法（PTP-CDP），認為在路徑計算迭代之前設(shè)置一個截斷閾值，而這個截斷閾值就是CDP 算法中初始不斷測試的領(lǐng)域半徑值，即截斷距離dc.因為在加權(quán)路徑成本計算過程中，某些較大成本的邊永遠不需要出現(xiàn)在某次計算或某條路徑中.通過最初對每一條邊的計算，先剪切掉路徑圖中大于截斷閾值dc的邊，使成本較大的邊永遠不會出現(xiàn)在后續(xù)的迭代計算中，然后得到的單源最短路徑也不會包含較大路徑，符合我們的要求和預(yù)想.由此我們得到PTP-CDP 算法的平均時間復(fù)雜度為O(n2)，與TP-CDP 一致.但在面對大數(shù)據(jù)集時，PTPCDP 在求單源最短路徑的環(huán)節(jié)中對圖的剪枝后，通過priority_queue 實現(xiàn)的Dijkstra 最短路，堆中元素O(|V|)個，在每次更新時往堆里插入當(dāng)前最短距離和頂點的值O(|E|)次，所以PTP-CDP 的最短路部分平均時間復(fù)雜度為O(|E|ln|V|)，而TP-CDP 的最短路部分沒有剪枝，相當(dāng)于是通過鄰接矩陣實現(xiàn)，認為每兩個頂點之間均有邊連接，所以TP-CDP 的平均時間復(fù)雜度為O(|V|2).因此，本文算法在樣本點越多、類間距離越大的情況下，比TP-CDP 算法的性能更具優(yōu)勢.通過反復(fù)實驗測試和對比，也證實了截斷距離dc的設(shè)置能夠減少算法的運行和迭代次數(shù)，提升算法的運行效率并改進原有算法.

3 對比實驗

本文在測試對比CDP、TP-CDP、PTP-CDP 算法之前，首先對原有CDP 算法中的一些細節(jié)進行了改進.在樣本密度ρi的定義下，當(dāng)數(shù)據(jù)點連續(xù)時原CDP 算法中的局部密度定義并不能很好地反映數(shù)據(jù)點密度的連續(xù)性，因此我們采用指數(shù)核[17]來計算局部密度，計算公式如下：

式(6)不僅表示了局部點密度的連續(xù)化，而且對計算規(guī)模較小的數(shù)據(jù)集來說，在給定截斷距離dc內(nèi)的局部點密度，可以使不同點局部密度特征更加緊湊，表現(xiàn)更好.在判斷聚類中心的數(shù)目時，采用Kneed 拐點檢測曲線[18]自動判別Υi ?i決策曲線圖上的拐點，實現(xiàn)了聚類中心數(shù)目的自動化確定.整個PTP-CDP 算法的偽代碼如下：

事實上，本文所提出的PTP-CDP 算法與TP-CDP 算法本質(zhì)上并無差別，只是在單源最短路徑中采用截斷距離時，省去了一些不會影響最終計算結(jié)果的遠距離路徑.Pizzagalli等[6]根據(jù)Wiwie等[19]研究的生物聚類指標性能比較選擇F1-score 和Jaccard Index 評估指標，證實了TP-CDP 算法聚類精度相比于CDP 算法是有效提升的.本文選擇外部聚類指標Jaccard Index 和Rand Index[20]來證明在聚類精度上PTP-CDP 與TP-CDP 基本保持一致，在算法效率提升的問題上是本文的重點.圖3為基于PTP-CDP 算法對前文提及的幾個鏈狀、環(huán)狀數(shù)據(jù)集再聚類的結(jié)果圖.

圖3 PTP-CDP 在3 種數(shù)據(jù)集上聚類結(jié)果Figure 3 PTP-CDP clustered in three different datasets

無論是TP-CDP 或是本文提出的PTP-CDP 算法，其聚類中心的確定方法都與CDP 算法一致，只是在剩余點的分配規(guī)則中TP-CDP 基于全局最優(yōu)準則確定點所歸屬的類，PTPCDP 則是在計算每個點的全局最短路徑時利用Eps 作為截斷閾值，減少不必要的路徑計算和迭代次數(shù).因此，我們首先對含有類標簽的數(shù)據(jù)集進行外部指標的聚類精度測試，證明本文PTP-CDP 并沒有從本質(zhì)上影響TP-CDP 聚類的精度.接下來對14個數(shù)據(jù)集進行測試，這些數(shù)據(jù)集中包含有鏈狀、環(huán)狀類數(shù)據(jù)的特征，大部分由ClustEval 數(shù)據(jù)平臺、UCI 機械學(xué)習(xí)數(shù)據(jù)庫提供，有些則是人工合成數(shù)據(jù)集.本文數(shù)據(jù)集的測試量級大部分在3 萬～5 萬區(qū)間內(nèi)，實驗測試環(huán)境基于Intel(R) Core(TM) i7-5500UCPU @2.4 GHz.

圖4表示外部聚類精度指標Jaccard Index和Rand Index 在不同數(shù)據(jù)集上的基于3 種算法的精度差異.

圖4 外部聚類精度指標在不同數(shù)據(jù)集上的表現(xiàn)Figure 4 External clustering accuracy index performed on the different datasets

外部聚類精度指標Jaccard Index 和Rand Index 在[0,1]區(qū)間內(nèi)，指標數(shù)值越接近1，聚類越精確.圖4表示PTP-CDP 和TP-CDP 在大部分數(shù)據(jù)集上精度保持一致，PTP-CDP 在少數(shù)數(shù)據(jù)集上精度的損失并不顯著，在可接受的誤差范圍內(nèi).在99_synthetic_dendrites、three_cluster 等人工合成的無噪聲點的數(shù)據(jù)集中，TP-CDP 和PTP-CDP 都近乎實現(xiàn)了完全正確聚類，聚類精度指標接近1 且彼此沒有差異.而對liver、pima 等高維數(shù)據(jù)集，TP-CDP 和PTPCDP 雖然聚類精度有所下降，但都在0.5 以上.PTP-CDP 相比TP-CDP 在大部分數(shù)據(jù)集上精度保持不變，在極少數(shù)據(jù)集上有些精度損失，但精度損失在1%左右.考慮到路徑剪枝對路徑計算迭代的顯著減少，少量精度損失完全在誤差允許的可接受范圍內(nèi).表1顯示了各數(shù)據(jù)集的規(guī)模、測試次數(shù)、參數(shù)Eps、p值及3 種算法的測試時間均值的信息.

通過本文PTP-CDP 算法測試結(jié)果不難看出，在各個類型數(shù)據(jù)集上相比TP-CDP 在執(zhí)行時間（單位s）均有不同程度的提升.其中，p值表示路徑成本函數(shù)ξp(Γ)對較大路徑的懲罰程度，p值越大則擁有較大距離值的路徑在路徑成本函數(shù)的計算中權(quán)重也越大.在本文的數(shù)據(jù)測試中，取p=2 已經(jīng)滿足了算法的需求.圖5顯示了在不同數(shù)據(jù)集上PTP-CDP 相較于TP-CDP 算法時間的提升比例，我們在相同的計算機運行狀態(tài)下測試每一個數(shù)據(jù)集的CDP、TP-CDP 和PTP-CDP 運算時間，重復(fù)10 次取時間均值，經(jīng)計算PTP-CDP 算法速度的時間均值提升了2.147 8%.

通過對不同類型數(shù)據(jù)集的測試可以看出，在與TP-CDP 算法聚類精度保持一致的前提下，PTP-CDP 在具有顯著的鏈狀類、環(huán)狀類數(shù)據(jù)特征的數(shù)據(jù)集中速度提升較大，而在普通的類別數(shù)據(jù)中表現(xiàn)一般，這也與我們算法的思想一致.在具有更大數(shù)據(jù)量的鏈狀數(shù)據(jù)集中，當(dāng)Eps 值越小時，從剩余點出發(fā)時可以截斷更多顯著不需要的路徑，減少路徑成本函數(shù)的計算和迭代步驟，算法的速度也會得到顯著提升.同時，在人臉面部識別等高維數(shù)據(jù)集中，傳統(tǒng)的聚類算法針對高緯度數(shù)據(jù)的低性能，PTP-CDP 在此方面也有不錯的表現(xiàn).

表1 數(shù)據(jù)集信息及測試時間均值Table 1 Information of datasets and the average of the testing time s

4 結(jié) 語

本文從基于密度的DBSCAN 算法入手，著重分析了CDP 算法的聚類機理，并介紹了為解決CDP 算法在鏈狀、環(huán)狀類上聚類不準確問題而提出的TP-CDP 算法.通過分析TP-CDP 算法在剩余點分配問題上所采用的最短路徑算法，提出了將超參數(shù)Eps 值作為截斷閾值dc，減少了不需要的路徑成本計算和最短路徑法的迭代次數(shù)，并通過實際測試數(shù)據(jù)集證實了我們的假設(shè).在保持聚類精度不變的前提下，減少了TP-CDP 算法的計算時間，改進了算法.實際上，在全局完全圖中求解最短路徑時，在聚類中應(yīng)遵循類內(nèi)距離盡可能小、類間距離盡可能大的準則.截斷閾值dc就是讓最短路求解過程盡可能在類內(nèi)中展開，而剪去屬于類間距離的較大路徑，這是因為這部分路徑成本經(jīng)過加權(quán)后對求解最優(yōu)的最短路徑并無幫助.

本文借鑒了TP-CDP 算法，該算法基于最短路徑法對剩余點進行全局分配，針對這種全局分配規(guī)則提出改進算法PTP-CDP.未來TP-CDP 算法改進的可能，會側(cè)重于剩余點的分配過程中采用怎樣的全局最優(yōu)的分配準則可以得出唯一最優(yōu)解，以此確定剩余點的類歸屬問題.此外，本文在截斷距離dc的設(shè)置上采用超參數(shù)Eps 值，是否有其他更好的截斷閾值，在滿足聚類精度的前提下，還能進一步減少不必要的計算過程和迭代次數(shù)，這方面值得我們?nèi)ヌ骄?另外，在剩余點的分配問題上，除了基于最短路徑算法的分配規(guī)則，是否還有其他高效可行的方法既能夠勾畫出樣本的整體空間分布規(guī)律，又能夠有效地找到全局計算中的最優(yōu)解，值得我們在未來不斷去探尋和發(fā)現(xiàn).