密度峰值聚類算法研究現狀與分析*

葛麗娜，陳園園，周永權,3**

(1.廣西民族大學人工智能學院，廣西南寧 530006；2.廣西民族大學，網絡通信工程重點實驗室，廣西南寧 530006；3.廣西混雜計算與集成電路設計分析重點實驗室，廣西南寧 530006)

隨著現代信息技術的發展，生活中充斥著海量的數據信息，如醫療數據信息、個人消費記錄、個人理財記錄等，而數據信息的增多，也促使數據挖掘技術不斷提高。聚類算法是數據挖掘的關鍵技術之一。聚類算法是根據數據之間的相似性將數據集樣本劃分為不同的類簇，每個類簇之間的數據相似性較高，不同的類簇中數據相似性較低。

傳統的聚類算法分為基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法、基于網格的聚類算法以及基于模型的聚類算法[1]。基于密度的聚類算法，如基于密度的噪聲應用空間聚類(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)算法，其對噪聲不敏感，能夠發現任意形狀的簇，但是該算法對參數ε和Minpts設置敏感，且對于密度不均勻的數據集，該算法不適用[2]。基于密度的聚類算法是以數據集在空間分布上的稠密度為依據進行聚類，無需預先設定類簇數，適合對未知內容的數據集進行聚類。

本文所研究的密度峰值聚類(Clustering by Fast Search and Find of Density Peaks,DPC)算法是2014年意大利學者Rodriguez等[3]提出的。DPC算法由于參數唯一、可以發現任意形狀的數據、聚類過程簡潔高效等優點，受到各界的廣泛關注。目前，DPC算法已經在醫學圖像處理[4]、分子動力學[5]、文檔處理[6，7]、社區檢測[8-10]等許多領域中展現出較好的性能。如在生物醫學應用方面，為了確定在300 K基準溫度下T-REMD模擬過程中采樣的主要構象，Kührová等[11]引入了DPC算法，與εRMSD結合，提出了新的算法；Chen等[12]引入DPC算法來識別疾病癥狀，再利用Apriori算法分別對疾病診斷規則和疾病治療規則進行關聯分析。本文對DPC算法原理進行介紹、分析，并對自適應DPC算法的國內外研究現狀進行比較總結，最后給出今后的研究方向。

1 DPC算法原理

DPC算法[3]基于以下假設：每一類簇的聚類中心被與其相鄰的密度較低的樣本點所包圍,這些相鄰的樣本點距離其他局部密度相對較大的點較遠。

設有數據集D={q1,q2,…,qn}，對于每一點qi，由公式(1)計算其局部密度ρi，對于小規模數據集，采用公式(2)計算：

ρi=∑jχ(dij-dc),其中，χ(x)=

(1)

(2)

式中，dc是截斷距離，dij是點qi到點qj之間的歐氏距離。

再由公式(3)計算樣本點qi的距離δi，δi是樣本點qi到其他密度較高樣本點之間的最短距離，若qi是密度最高的樣本點，則δi為qi到其他樣本的最大距離。

(3)

計算出qi的局部密度和距離后，選取聚類中心。在DPC算法中，選取聚類中心的方法有兩種，一種是決策圖法，另一種是公式法。決策圖法是根據樣本點的局部密度和距離生成一個決策圖，然后選取最佳的聚類中心點。例如，圖1中的數據點按密度遞減的順序排列，圖2是根據圖1中的樣本點計算局部密度和距離后得出的決策圖[3]。由此可以得出DPC算法決策圖選取聚類中心的一般規律：①位于決策圖右上方的樣本點適合選取為聚類中心，這些點擁有較高的局部密度且距離其他更高密度的點較遠；②位于決策圖ρ坐標軸附近的樣本點具有較近的距離，認為是普通樣本點，因為其附近存在更適合選取為聚類中心的樣本點；③位于決策圖δ坐標軸附近且距離ρ坐標軸相對較遠的樣本點識別為離群點，這些點擁有較低的密度且距離更高密度點較遠。

圖1 數據分布圖Fig.1 Distribution map of data

圖2 決策圖Fig.2 Graph of decision

DPC算法中選取聚類中心的另一種方法是公式法，根據公式(4)計算γ的值，并將其值進行降序排序，選取前k個樣本作為聚類中心(k為預先指定的簇數)。將局部密度值與距離相乘是為了尋找局部密度較高且距離較遠的樣本點。但是，該公式未考慮樣本點鄰域結構的影響。

γi=ρi×δi。

(4)

選出聚類中心后，將剩余樣本點分配到距離其最近且擁有較高密度的樣本點所在的類簇。

DPC算法的具體流程如算法1所示：

算法1 密度峰值聚類算法流程 輸入:數據集D=q1,q2,…,qn{},簇數k 輸出:聚類劃分結果 1.根據數據集樣本點總數確定截斷距離dc 2.根據公式(1)或(2)計算樣本局部密度ρ 3.根據公式(3)計算樣本距離δ 4.由計算出的局部密度和距離生成決策圖,根據決策圖或公式(4)選取聚類中心 5.將剩余樣本點分配到距離其最近的局部密度較高點所在的類簇中 6.返回聚類劃分結果圖

2 自適應DPC算法的優化

在DPC算法中，截斷距離dc并不是算法自動設定的，而是按照文獻[3]中提出的經驗策略設定dc的值使得鄰域樣本點數為總樣本點數的1%-2%。而在實際應用中，按照文獻[3]中所提的方法設定截斷距離的值，并不是所有的聚類問題都適用。圖3所示是DPC算法在不同的dc取值下對同一數據集進行聚類的結果。由圖3可以看出，雖然對類簇數沒有影響，但是普通樣本點和異常點的劃分隨著dc的取值變化而發生變化。

圖3 不同dc取值下的聚類結果Fig.3 Clustering results when takes different values

在聚類中心選取階段，雖然根據決策圖選取聚類中心能夠得到較好的聚類結果，但是若數據集較為復雜，人工難以選取合適的聚類中心，而聚類中心一旦選擇錯誤，會導致非聚類中心點分配錯誤。圖4為DPC算法對數據集Aggregation進行聚類時生成的決策圖。由圖4可以看出，符合聚類中心要求的點不容易確定，手動選取易造成聚類中心個數選取錯誤。由于DPC算法聚類無需迭代，若聚類中心選取錯誤，會引起剩余樣本點分配出現錯誤，最終導致聚類效果不佳。

圖4 對Aggregation數據集聚類的決策圖Fig.4 Decision graph of aggregation data set

目前，針對DPC算法過程不能實現自適應的問題，主要的改進方法有3種：①針對參數dc的改進，使得dc值能夠自適應選取；②對計算局部密度ρ和距離δ的公式進行改進，避免參數dc的使用；③在選取聚類中心時，采用不同的方式使得聚類中心自適應選取，不需要人為參與。

2.1 參數dc的改進

第1種改進方式主要是針對參數dc的選取。由于原來的dc值是人為設定的，淦文燕等[13]提出了Improved Clustering Algorithm that Searches and Finds Density Peaks (ICADEP)算法。該算法引入密度估計熵，提出新的參數優化方法，使得參數dc能夠自適應選取最優值且聚類結果與核函數的類型無關，達到了更精確的聚類效果。但是該方法仍然需要人為參與選取聚類中心，為了解決這一問題，有學者引入K近鄰思想[14-16]，即在聚類過程中計算樣本點的近鄰密度，提出新的計算dc的公式，實現dc的自動計算取值。Liu等[15]提出一種新的基于K近鄰的計算dc的算法。該算法不僅使得dc的值自適應選擇且聚類中心的選取準確、不遺漏，并能夠更好地區分核心區域和邊界區域。該算法的截斷距離計算公式如下：

(5)

(6)

為了避免在改進算法的過程中出現需要選取參數的問題，王洋等[17]研究發現計算點勢能的方法與DPC算法中計算ρ的方法相似，認為截斷距離的最優值等價于電勢能計算中的影響因子σ的最優值。而基尼指數G會隨σ的改變而改變，因此，將基尼指數G最小時對應的σ作為截斷距離的最優值；在聚類中心的選取上，根據γ的排序圖中兩點間的斜率差的變化來選取聚類中心。最終，該文算法實現了DPC算法的截斷距離和聚類中心的自適應選取。

有研究將智能優化算法與DPC算法結合，如朱紅等[18]將果蠅優化算法與DPC算法相結合，提出了Density Peaks Clustering Based on Fruit Fly Optimization Algorithm (FOA-DPC)算法。該算法將截斷距離dc以及類簇數k作為決策變量，采用果蠅優化算法進行尋優，找到最優值后，采用公式(4)計算γi的值，選取前k個點作為聚類中心，對圖像進行分割。

2.2 局部密度和距離的改進

第2種改進方法的主體是局部密度和距離的計算公式。DPC算法的局部密度和距離的測量是基于截斷距離的值，很難得到最優的參數。謝娟英等[19]提出的K-Nearest Neighbors Optimized Clustering Algorithm by Fast search and Finding the Density Peaks (KNN-DPC)算法采用指數核函數，根據樣本的K近鄰信息重新定義局部密度的計算公式，使得局部密度的計算與參數dc的取值無關，更準確地發現聚類中心。但是，其聚類中心的選擇仍是人機交互模式。

Liu等[20]提出了Shared-Nearest-Neighbors-based Clustering by Fast Search and Find of Density Peaks (SNN-DPC)算法。該算法提出了共享最近鄰SNN和共享最近鄰相似度Sim，將Sim引入局部密度的計算中，使得局部密度和距離的計算與截斷距離無關，并且提出了新的剩余樣本點分配方案，避免DPC算法一步分配策略易導致的“多米諾骨牌效應”的影響。從實驗結果來看，SNN-DPC算法的聚類準確性得到了提高。

雖然KNN-DPC算法和SNN-DPC算法避免了參數dc對聚類結果的影響，但是對于稀疏密度相差較大的數據集，其聚類中心較難選取。因此，薛小娜等[21]提出了Improved Density Peaks Clustering Algorithm (IDPCA)。該算法在計算局部密度時引入帶有相似性系數的高斯核函數，既避免了截斷距離對聚類結果的影響，又使得算法適用于任意數據集。

賈露等[22]提出的Physics Improved Density Peak Clustering Algorithm (W-DPC)引入了物理學中的萬有引力定律，用于重新定義局部密度的計算。樣本間距離越小，吸引力越大，局部密度越大，從而易于找到高密度點和選擇聚類中心，同時還引入第一宇宙速度用于處理剩余樣本點。

以上4種改進算法雖然都避免了截斷距離對聚類結果的影響，但是都引入了新的參數，如KNN-DPC算法、SNN-DPC算法以及IDPCA算法中都需要預先給定樣本近鄰K的值，而W-DPC算法需要給出掃描半徑r的值。除此之外，這4種算法的聚類中心選取方面均是采用決策圖法，需要人為參與。

2.3 聚類中心選取方式的改進

第3種改進方式的主體是聚類中心的選取。王星等[23]提出了Fast Searching Clustering Centers Algorithm based on Linear Regression Analysis (LR-CFDP)算法，該算法利用線性回歸模型和殘差分析，實現了聚類中心自動選取，解決了算法聚類中心需要人機交互選擇的問題，避免了主觀影響。

同樣是將數學理論用于DPC算法的改進，崔世琦等[24]將高斯核函數的數學性質用于DPC算法的局部密度度量優化，并在聚類中心選取時利用γ值的中位數和絕對中位差求取殘差Ri，選取前r個作為潛在聚類中心，計算α顯著水平下的檢驗臨界值λi，將原來的潛在聚類中心中λi>Ri的點作為最終的聚類中心，實現了聚類中心的自適應選取，但是對于高維數據集，該算法的性能不理想。因此，江平平等[25]提出了Improved Density Peak Clustering Algorithm based on Grid (G-DPC)算法。該算法采用網格劃分法將樣本空間劃分為均等且不相交的網格單元，聚類中心的選取依據公式(7)和(8)：

ρCi-μ(ρi)≥0，

(7)

(δCi-E(δi))/2≥σ(δi)，

(8)

若網格代表點滿足這兩個公式，即為所尋聚類中心點,其中ρCi為聚類中心的網格代表點的局部密度值，μ(ρi)是所有網格代表點的局部密度均值，δCi則表示同一類簇中其他代表點與聚類中心的代表點間的最短距離，E(δi)表示所有δi的期望。該算法實現了聚類中心自適應選取。

3 自適應DPC算法指標分析

3.1 聚類準確率(ACC)

準確率[26]是計算算法正確劃分的樣本數占總樣本數的比例，如式(9)所示。準確率的取值區間為[0,1],其值越大，表示算法的聚類結果越接近于正確的劃分。

(9)

表1為DPC算法及6種改進算法作用在UCI數據集上的聚類準確率。可以看出，KM-DPC和IDPCA算法在Seeds數據集中取得最優的聚類結果，在Segmentation數據集中表現最佳的是KM-DPC算法；在Iris數據集中，KNN-DPC和SNN-FKNN-DPC兩種算法聚類結果最好；其余的3個數據集ACC值最大的均為SNN-FKNN-DPC算法。總體來說，從ACC值來看，6種改進算法均優于DPC算法，而SNN-FKNN-DPC算法則是幾個數據集中聚類最優的算法。基于聚類中心自適應改進的AD-PC-WKNN和AKDP算法與原算法相比聚類性能有了一定程度的改進，但是與基于局部密度計算方式改進的其他算法相比，性能優勢不夠明顯。

表1 7種算法在UCI數據集上的聚類準確率Table 1 Clustering accuracy of 7 algorithms on the UCI data set

3.2 Adjusted Mutual Information (AMI)

AMI[31]是基于信息論的聚類度量指標，通過互信息(Mutual information)度量兩個事件集合的相關性，如式(10)所示：

AMI(U,V)=

(10)

式中，U=(U1,U2,…,UL)是數據集D的標準劃分，V=(V1,V2,…,VL)是優化算法的聚類結果,MuI(U,V)表示事件U與事件V之間的互信息，如式(11)所示，互信息是一種對稱度量，用于量化兩個分布之間共享的統計信息。E{MuI(U,V)}是U和V之間的期望互信息，如式(12)所示。H(U)和H(V)分別是U和V的熵。

MuI(U,V)=

(11)

E{MuI(U,V)}=

(12)

AMI的取值范圍是[-1，1]，其值越接近1，表示算法的聚類結果越優，越接近于真實結果。

由表2可以看出，5種改進算法的AMI值大部分都優于原始的DPC算法。Wine數據集中AMI值最優的是SNN-FKNN-DPC算法，Seeds數據集最優的是W-DPC算法，Libras movement和Waveform數據集中表現最佳的是SNN-DPC算法，Waveform(noise)數據集中KM-DPC算法取得最優的AMI值。關于Iris數據集，KNN-DPC、SNN-FKNN-DPC以及SNN-DPC這3種算法的AMI值均為0.912，原因是該數據集中的簇重疊嚴重，而這3種算法均是引入近鄰思想，受該數據集的特殊鄰域環境影響，這3種算法在Iris數據集的AMI值相等。

表2 6種聚類算法在各數據集上的AMI值Table 2 AMI values of six clustering algorithms on each data set

3.3 Adjusted Rand Index (ARI)

蘭德指數(Rand Index,RI)只考慮表3所示的a和d兩種聚類結果的情況，忽略了b和c兩種聚類結果，評價方式較為片面并且沒有區分度，其計算公式如式(13)。其中，U=(U1,U2,…,UL)是數據集D的標準劃分，V=(V1,V2,…,VL)是優化算法的聚類結果：

(13)

ARI[32]是基于RI的改進，度量標準劃分U和聚類結果V之間的相似程度，如式(14)，也可用式(15)來表示。ARI的取值范圍為[-1,1]，數值越高表示聚類劃分效果越好。

ARI(U,V)=

(14)

ARI(U,V)=

(15)

式中，nij=|Ui∩Vj|為在U中屬于Ui且在V中屬于Vj的樣本總數，ni·表示在U中屬于類簇Ui的樣本個數，n·j表示在V中屬于類簇Vj的樣本個數。

表4是6種改進算法和DPC算法在UCI數據集的ARI值。相比于DPC算法，各改進算法在UCI數據集的ARI值均有所改善，其中，在Iris數據集中，SNN-DPC算法表現最佳；SNN-FKNN-DPC算法在Wine和Libras movement兩個數據集的聚類結果相比于其他算法較優；KM-DPC算法在Seeds和Segmentation數據集的ARI值最大；在WDBC數據集中，聚類效果最優的是SNN-DPC算法。

表4 6種算法在UCI數據集的ARI值Table 4 ARI values of 6 algorithms on UCI data set

3.4 F-Measure

F-Measure[33]指標綜合了查準率(Precision)和查全率 (Recall)兩種評價指標，其優勢在于對聚類結果的整體區分能力。一般的聚類結果分布情況總結如表3所示。F-Measure的取值范圍為[0,1]，數值越高表示聚類效果越好。

查準率評估聚類結果的精確程度，計算方式如公式(16)所示。查全率評估實驗結果的完備程度，計算方式如公式(17)所示。F-Measure的計算方式如式(18)所示。

(16)

(17)

(18)

由表5可以看出，ADPC-KNN算法在Seeds和Libras Movement兩個數據集中的F-Measure值較其他算法大，即該算法在這兩個數據集中的表現最佳；而在Iris、Wine、Ecoli以及WDBC 4個數據集中聚類結果最優的是SNN-DPC算法。

表5 5種算法在UCI數據集的F-Measure值Table 5 F-Measure values of 5 algorithms on UCI data set

3.5 算法平均運行時間

由表6可以看出，3種改進算法的平均運行時間均大于DPC算法，而由前面的ACC、AMI、ARI以及F-Measure 4個指標可以看出，這些算法的聚類結果都比DPC算法有所改善，但是其運行時間都比DPC算法慢。

表6 4種算法在UCI數據集上的平均運行時間(ms)Table 6 Average running time of 4 algorithms on UCI data set (ms)

由表1、表2、表4、表5及表6的數據可以看出，3種方向上的改進算法相比于原來的算法，聚類性能在一定程度上都得到了提升，但是從整體上來看，針對dc值選取的改進算法以及針對聚類中心選取的改進算法，在數據集上的聚類效果不如基于局部密度計算公式的改進算法。5個表格中的數據集均為規模較小的數據集，說明已改進的算法在處理規模較小、數據分布較為均勻的數據集時聚類效果比較理想。

4 展望

本文主要分析了目前針對DPC算法參數dc及其聚類中心的選取不能自適應的缺陷，研究者對其進行改進的研究工作，并對改進算法的聚類結果指標進行分析。未來可從以下3個方面進行深入研究：

①將智能優化算法與DPC聚類算法有機結合，研究自適應DPC自動聚類算法：目前已有的對于DPC算法的自適應改進方式，主要是針對參數的自適應或者在選取聚類中心時無需人為參與，兩者同時達到自適應效果的改進仍然較少，基于此，對DPC算法的自適應研究還可以更加完善；

②DPC算法參數選取的數學理論依據分析：目前參數的選取主要依賴經驗策略，缺乏數學理論的支撐；

③高維空間DPC聚類算法理論與方法研究：雖然PDC算法能夠識別任意形狀簇，但是對于高維數據集，該算法的處理性能不夠理想，而現有的針對高維數據的改進方式主要是基于PCA的改進算法，因此，DPC在高維空間的研究有待進一步探索。