葛麗娜，陳園園，周永權(quán),3**

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

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

傳統(tǒng)的聚類算法分為基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法、基于網(wǎng)格的聚類算法以及基于模型的聚類算法[1]?；诿芏鹊木垲愃惴?，如基于密度的噪聲應(yīng)用空間聚類(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)算法，其對噪聲不敏感，能夠發(fā)現(xiàn)任意形狀的簇，但是該算法對參數(shù)ε和Minpts設(shè)置敏感，且對于密度不均勻的數(shù)據(jù)集，該算法不適用[2]?；诿芏鹊木垲愃惴ㄊ且詳?shù)據(jù)集在空間分布上的稠密度為依據(jù)進行聚類，無需預(yù)先設(shè)定類簇數(shù)，適合對未知內(nèi)容的數(shù)據(jù)集進行聚類。

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

1 DPC算法原理

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

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

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

(1)

(2)

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

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

(3)

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

圖1 數(shù)據(jù)分布圖Fig.1 Distribution map of data

圖2 決策圖Fig.2 Graph of decision

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

γi=ρi×δi。

(4)

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

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

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

2 自適應(yīng)DPC算法的優(yōu)化

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

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

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

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

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

2.1 參數(shù)dc的改進

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

(5)

(6)

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

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

2.2 局部密度和距離的改進

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

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

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

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

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

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

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

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

ρCi-μ(ρi)≥0，

(7)

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

(8)

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

3 自適應(yīng)DPC算法指標分析

3.1 聚類準確率(ACC)

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

(9)

表1為DPC算法及6種改進算法作用在UCI數(shù)據(jù)集上的聚類準確率?？梢钥闯?，KM-DPC和IDPCA算法在Seeds數(shù)據(jù)集中取得最優(yōu)的聚類結(jié)果，在Segmentation數(shù)據(jù)集中表現(xiàn)最佳的是KM-DPC算法；在Iris數(shù)據(jù)集中，KNN-DPC和SNN-FKNN-DPC兩種算法聚類結(jié)果最好；其余的3個數(shù)據(jù)集ACC值最大的均為SNN-FKNN-DPC算法?？傮w來說，從ACC值來看，6種改進算法均優(yōu)于DPC算法，而SNN-FKNN-DPC算法則是幾個數(shù)據(jù)集中聚類最優(yōu)的算法?；诰垲愔行淖赃m應(yīng)改進的AD-PC-WKNN和AKDP算法與原算法相比聚類性能有了一定程度的改進，但是與基于局部密度計算方式改進的其他算法相比，性能優(yōu)勢不夠明顯。

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

3.2 Adjusted Mutual Information (AMI)

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

AMI(U,V)=

(10)

式中，U=(U1,U2,…,UL)是數(shù)據(jù)集D的標準劃分，V=(V1,V2,…,VL)是優(yōu)化算法的聚類結(jié)果,MuI(U,V)表示事件U與事件V之間的互信息，如式(11)所示，互信息是一種對稱度量，用于量化兩個分布之間共享的統(tǒng)計信息。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，表示算法的聚類結(jié)果越優(yōu)，越接近于真實結(jié)果。

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

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

3.3 Adjusted Rand Index (ARI)

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

(13)

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

ARI(U,V)=

(14)

ARI(U,V)=

(15)

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

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

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

3.4 F-Measure

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

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

(16)

(17)

(18)

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

表5 5種算法在UCI數(shù)據(jù)集的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個指標可以看出，這些算法的聚類結(jié)果都比DPC算法有所改善，但是其運行時間都比DPC算法慢。

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

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

4 展望

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

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

②DPC算法參數(shù)選取的數(shù)學(xué)理論依據(jù)分析：目前參數(shù)的選取主要依賴經(jīng)驗策略，缺乏數(shù)學(xué)理論的支撐；

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