王森 邢帥杰 劉琛

摘要：密度峰值聚類（DPC）是一種新提出的基于密度和距離的聚類算法，由于其原理簡(jiǎn)單，無需迭代和能處理形狀數(shù)據(jù)集等優(yōu)點(diǎn)，正在數(shù)據(jù)挖掘領(lǐng)域得到廣泛應(yīng)用。但DPC算法也有著一定的缺陷，如：對(duì)截?cái)嗑嚯x參數(shù)敏感，初始聚類中心的選擇非自動(dòng)化，后續(xù)標(biāo)簽分配存在鏈?zhǔn)絾栴}，時(shí)間復(fù)雜度較高等。文章對(duì)DPC算法的研究現(xiàn)狀進(jìn)行了總結(jié)與整理，首先介紹了DPC的算法原理和流程;其次，針對(duì)DPC算法的不足對(duì)DPC算法的優(yōu)化進(jìn)行概括和分析，指出了優(yōu)化算法的核心技術(shù)以及優(yōu)缺點(diǎn);最后，對(duì)DPC算法未來可能面對(duì)的挑戰(zhàn)和發(fā)展趨勢(shì)進(jìn)行展望。

關(guān)鍵詞：聚類算法;密度峰值;截?cái)嗑嚯x;初始聚類中心;微簇合并;時(shí)間復(fù)雜度

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

本文引用格式：王森，邢帥杰，劉琛. 密度峰值聚類算法研究綜述[J]. 華東交通大學(xué)學(xué)報(bào)，2023，40（1）：106-116.

Survey of Density Peak Clustering Algorithm

Wang Sen， Xing Shuaijie， Liu Chen

（School of Science， East China Jiaotong University， Nanchang 330013， China）

Abstract：Density peak clustering（DPC） is a novel clustering algorithm based on density and distance. It is widely used in the field of data mining because of its simple principle， no iteration and the ability to process shape datasets. However， DPC algorithm also has some defects，including the sensitive cutoff distance parameter， non-automatic selection of initial clustering center， the chain problem in subsequent allocation and? high time complexity. This paper summarizes the research status of DPC algorithm. Firstly， it introduces the principle and process of DPC algorithm. Secondly， in view of the deficiencies of DPC algorithm， the optimization of DPC algorithm is summarized and analyzed， and the core technology， advantages and disadvantages of the optimization algorithm are pointed out. Finally， the possible challenges and development trend of DPC algorithm in the future are concluded.

Key words： clustering algorithm; density peak; cutoff distance; initial cluster center; micro-cluster merge; time complexity

Citation format：WANG S，XING S J，LIU C. Survey of density peak clustering algorithm[J]. Journal of East China Jiaotong University，2023，40（1）：106-116.

隨著互聯(lián)網(wǎng)和信息技術(shù)的快速發(fā)展，數(shù)據(jù)量每天都在以驚人的速度增加，人類社會(huì)已步入大數(shù)據(jù)時(shí)代，如何從海量數(shù)據(jù)中挖掘潛在的有價(jià)值的信息是一個(gè)迫切的問題。聚類分析是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域一種處理大數(shù)據(jù)的重要方法，無需先驗(yàn)知識(shí)[1]。其主要目的是根據(jù)數(shù)據(jù)集的某些特征將數(shù)據(jù)集劃分為幾個(gè)不同的潛在的簇，并且使簇內(nèi)數(shù)據(jù)對(duì)象的相似性盡可能高，簇間的相似性盡可能低[2]。各種聚類算法已經(jīng)成功應(yīng)用于許多領(lǐng)域，如：圖像處理[3-4]、短文本聚類[5]、損傷診斷[6]、模式識(shí)別[7]、生物信息學(xué)[8]、信息檢索[9]等。

目前得到廣泛使用的聚類算法非常多，并且研究人員仍在尋找新的聚類算法以應(yīng)對(duì)各種不同的聚類任務(wù)。在過去的幾十年里，涌現(xiàn)出了許多不同類型的聚類算法，主要包括基于劃分的K-Means[10]和K-Medoid[11]算法，基于密度的DBSCAN[12]和OPTICS[13]算法，基于層次的CURE[14]和BIRCH[15]算法，基于網(wǎng)格的方法[16]，基于圖論的方法[17]，基于模型的方法[18]以及基于深度學(xué)習(xí)的方法[19]等。

2014年，Rodriguez和Laio[20]在SCIENCE提出了一個(gè)基于密度和相對(duì)距離的新算法（clustering by fast search and find of density peaks，DPC）。其主要基于兩個(gè)假設(shè)：① 聚類簇的中心的密度要比其周圍數(shù)據(jù)對(duì)象的密度高;② 聚類中心到比它密度更高的數(shù)據(jù)對(duì)象的距離較遠(yuǎn)。由于DPC算法可解釋性強(qiáng)，無需迭代，算法簡(jiǎn)單且能處理不同類型的數(shù)據(jù)集而備受矚目。但DPC算法也有著一定的局限性，比如截?cái)嗑嚯x參數(shù)的選取需要提前確定，初始聚類中心的確定受人為主觀影響，后續(xù)標(biāo)簽分配的鏈?zhǔn)絾栴}，算法的復(fù)雜度較高等。為了提高DPC的性能以及克服上述缺點(diǎn)，各個(gè)領(lǐng)域的學(xué)者已經(jīng)做了很多工作并提出了一系列的優(yōu)化算法。

本文首先簡(jiǎn)述傳統(tǒng)DPC算法的原理以及算法流程，然后針對(duì)DPC算法的不足，按照4個(gè)優(yōu)化方向分類討論了不同優(yōu)化算法的關(guān)鍵技術(shù)與優(yōu)缺點(diǎn)，最后對(duì)DPC算法的未來發(fā)展所可能面臨的挑戰(zhàn)及優(yōu)化方向進(jìn)行了展望。

1 傳統(tǒng)密度峰值聚類算法

1.1 密度峰值聚類算法原理

DPC算法是一種基于距離和密度的無監(jiān)督的聚類算法，且無需提前輸入簇的真實(shí)個(gè)數(shù)。DPC算法首先尋找密度峰值點(diǎn)作為初始聚類中心，之后按照距離將剩余非中心點(diǎn)分配至最近的聚類中心所在的簇。尋找簇中心（密度峰值點(diǎn)）作為算法最重要的一步，主要思想基于兩個(gè)假設(shè)：① 簇的中心局部密度較高且被密度比它低的數(shù)據(jù)所包圍;② 簇中心到比其密度更大的數(shù)據(jù)對(duì)象的距離相對(duì)較大。針對(duì)以上假設(shè)，DPC的作者提出了兩個(gè)重要參數(shù)描述每一個(gè)數(shù)據(jù)對(duì)象：局部密度ρ和與密度更高點(diǎn)的相對(duì)距離δ。

對(duì)于數(shù)據(jù)集X={x1，x2，…xn}，采用歐式距離計(jì)算兩點(diǎn)之間的相似性

dist（xi，xj）= （1）

式中：m為數(shù)據(jù)的維度;xil是數(shù)據(jù)對(duì)象xi在第l個(gè)維度下的取值。

DPC算法使用截?cái)嗑嚯xdc或者高斯核計(jì)算數(shù)據(jù)對(duì)象的局部密度ρi，對(duì)于數(shù)據(jù)集X每一個(gè)數(shù)據(jù)對(duì)象xi，其局部密度ρi的計(jì)算為

ρi=φ（dist（xi，xj）-dc） （2）

式中：φ（x）為判斷函數(shù)，當(dāng)x≥0時(shí)，φ（x）=1;當(dāng)x<0時(shí)，φ（x）=0。

ρi=exp-

（3）

式中：dist（xi，xj）表示數(shù)據(jù)對(duì)象xi和xj之間的歐氏距離，dc>0。式（2）計(jì)算的局部密度即為以數(shù)據(jù)對(duì)象xi為中心，以截?cái)嗑嚯xdc為半徑的鄰域內(nèi)包含的點(diǎn)的個(gè)數(shù)，或者可以認(rèn)為是與數(shù)據(jù)對(duì)象xi的距離小于dc的數(shù)據(jù)對(duì)象的個(gè)數(shù)。式（3）計(jì)算的則是所有數(shù)據(jù)對(duì)象到該點(diǎn)的高斯距離之和。

相對(duì)距離δi定義為

δi=（dist（xi，xj））? ? ?（4）

對(duì)于具有最大局部密度的數(shù)據(jù)對(duì)象，其相對(duì)距離δi為

δi=（δj）? （5）

DPC算法認(rèn)為，當(dāng)局部密度ρ和相對(duì)距離δ的值都比較大時(shí)，此時(shí)對(duì)應(yīng)的數(shù)據(jù)對(duì)象即為初始聚類中心（密度峰值點(diǎn)）。通過繪制出關(guān)于ρ和δ的二維決策圖，初始聚類中心點(diǎn)與非聚類中心點(diǎn)明顯分開，故通過人為選擇位于右上角區(qū)域（較大的ρ和δ）的點(diǎn)作為初始聚類中心點(diǎn)，且挑選出的點(diǎn)的個(gè)數(shù)即為最終聚類簇的個(gè)數(shù)。圖1（a）為數(shù)據(jù)實(shí)際分布情況，圖1（b）為投影至二維空間得到的決策圖。密度峰值點(diǎn)即為決策圖右上角的突出的點(diǎn)1和點(diǎn)10，參考圖1（a），這兩點(diǎn)位于每一個(gè)簇的中心位置，表明選擇的初始聚類中心是合適的。點(diǎn)7雖然也有較高的密度，但其相對(duì)距離δ的值很小，這說明在點(diǎn)7的周圍存在密度比其更大的點(diǎn)（點(diǎn)1），點(diǎn)7不能作為初始聚類中心。另外點(diǎn)28具有較高的值但密度較小，這表明點(diǎn)28是遠(yuǎn)離聚類簇的噪聲點(diǎn)。

另外也可以通過決策值γi=ρi δi選擇聚類中心，選擇具有較大決策值的點(diǎn)作為初始聚類中心。最后再將所有的非聚類中心點(diǎn)分配至距離最近的聚類中心點(diǎn)所在的簇中，完成聚類過程。

1.2 傳統(tǒng)DPC算法流程

密度峰值聚類算法的主要步驟如下：

1） 輸入數(shù)據(jù)集X={x1，x2，…，xn};

2） 根據(jù)式（1）計(jì)算n個(gè)數(shù)據(jù)對(duì)象之間的歐式距離矩陣Dn×n;

3） 根據(jù)式（2）或（3）計(jì)算數(shù)據(jù)對(duì)象局部密度參數(shù)ρi;

4） 根據(jù)式（4）或（5）計(jì)算數(shù)據(jù)對(duì)象xi到具有更高密度的數(shù)據(jù)點(diǎn)的最近距離δi;

5） 根據(jù)密度參數(shù)ρi和相對(duì)距離參數(shù)δi繪制決策圖;

6） 根據(jù)決策圖或決策值γ挑選合適的初始聚類中心;

7） 將剩下的非聚類中心點(diǎn)分配至具有更高的密度ρi中距離最近的點(diǎn)所在的簇;

8） 輸出最終聚類結(jié)果φ={C1，C2，…，Cm}。

2 密度峰值聚類算法的優(yōu)化

2.1 實(shí)現(xiàn)DPC算法的自動(dòng)化

提前確定合適的截?cái)嗑嚯x參數(shù)與密度峰值點(diǎn)的選取阻礙了算法的自動(dòng)化。DPC算法的核心即尋找密度峰值點(diǎn)，而決定密度參數(shù)大小的因素主要取決于dc。DPC算法對(duì)輸入dc的值異常敏感，過大或者過小的dc值可能產(chǎn)生完全不同的聚類結(jié)果，聚類精度波動(dòng)大，但提前確定合適的dc的值是非常困難的。另外，密度峰值點(diǎn)的選取是人為通過決策圖選取的，當(dāng)決策圖復(fù)雜時(shí)難以選取合適的峰值點(diǎn)，且操作人員得到的峰值點(diǎn)受主觀影響較大，同一個(gè)數(shù)據(jù)集可能會(huì)產(chǎn)生不同的選擇結(jié)果。

Liu等[21]在ADPC-KNN中引入K-最近鄰的思想自動(dòng)計(jì)算截?cái)嗑嚯xdc以及基于K-最近鄰的密度ρi計(jì)算方式

ρi=exp（）? ? （6）

dc=μK+? ? ?（7）

μK=δiK? ? ? （8）

式中：dij為兩點(diǎn)間的歐氏距離;δiK為數(shù)據(jù)點(diǎn)i與第K個(gè)最近鄰之間的距離;N為整個(gè)數(shù)據(jù)集的容量;μk為不同數(shù)據(jù)點(diǎn)的δik的均值。ADPC-KNN能自適應(yīng)地找到合適的dc值和初始聚類中心。雖然算法減少了對(duì)dc的依賴性，但同時(shí)引入了需要提前確定的K-最近鄰參數(shù)。另外，算法仍然需要通過人工確定初始聚類中心的個(gè)數(shù)。

王芙銀等[22]提出一種結(jié)合鯨魚優(yōu)化算法的WOA-DPC算法，建立ACC目標(biāo)函數(shù)，利用鯨魚優(yōu)化算法迭代尋找使指標(biāo)最大時(shí)所對(duì)應(yīng)的dc值即最優(yōu)的截?cái)嗑嚯x參數(shù)。另外，根據(jù)加權(quán)的決策值斜率的變化情況確定初始聚類中心。該算法實(shí)現(xiàn)了自動(dòng)化，降低了對(duì)截?cái)鄥?shù)的依賴性。但WOA-DPC算法的時(shí)間復(fù)雜度高于傳統(tǒng)DPC算法，在針對(duì)大型數(shù)據(jù)集時(shí)耗時(shí)較長(zhǎng)。

Wang等[23]引入物理學(xué)中的數(shù)據(jù)場(chǎng)的勢(shì)能熵，自動(dòng)確定計(jì)算密度參數(shù)時(shí)的截?cái)鄥?shù)dc，避免了人為確定的隨機(jī)性。場(chǎng)函數(shù)中數(shù)據(jù)對(duì)象的潛在勢(shì)能φi即數(shù)據(jù)分布的局部密度，越密集的對(duì)象φi的值越大，能很好地反應(yīng)數(shù)據(jù)分布的情況。熵用來描述數(shù)據(jù)集的不穩(wěn)定性，最小的熵取值對(duì)應(yīng)于σ的最優(yōu)取值。最后根據(jù)高斯分布的3σ準(zhǔn)則，得到最優(yōu)dc的值為σ。實(shí)驗(yàn)結(jié)果表明，針對(duì)小型數(shù)據(jù)集，該算法的聚類效果優(yōu)于傳統(tǒng)算法且能自動(dòng)確定截?cái)鄥?shù)dc的取值，但面對(duì)大型數(shù)據(jù)集時(shí)的有效性還有待研究。

王洋等[24]引入基尼指數(shù)描述數(shù)據(jù)的不純度，自適應(yīng)地確定截?cái)嗑嚯x參數(shù)dc同時(shí)自動(dòng)獲取初始聚類峰值點(diǎn)。當(dāng)基尼指數(shù)的值最小時(shí)所對(duì)應(yīng)的σ的取值即為截?cái)嗑嚯x參數(shù)dc。按γ對(duì)數(shù)據(jù)點(diǎn)降序排列，并繪制二維圖像，橫坐標(biāo)為數(shù)據(jù)點(diǎn)的排列序號(hào)，縱坐標(biāo)為γ值。然后通過尋找決策值的臨界值p自動(dòng)選擇初始聚類中心，如果p滿足

p=max{i | ki-ki+1≥β，i=1，2，3，…，n-2}? （9）

β=a（j）/（n-2）? ? （10）

a（j）=kj-kj+1? ? ?（11）

式中：ki為γ排序圖上相鄰兩點(diǎn)之間的斜率;a（j）為γ序列圖中相鄰兩點(diǎn)之間斜率差的和，β為數(shù)據(jù)集中a（j）的平均值。

Flores等[25]提出一種通過檢測(cè)決策值γ在連續(xù)數(shù)據(jù)點(diǎn)之間的差距gap進(jìn)而自動(dòng)確定聚類中心的方法。首先將所有數(shù)據(jù)對(duì)象{x1，x2，…，xn}按照γ值降序排列為P={p1，p2，…，pn}。并定義點(diǎn)距離di=

γi+γi+1，平均點(diǎn)距離為d=，則最后一次出現(xiàn)的di≥d所對(duì)應(yīng)的點(diǎn)i即為閾值點(diǎn)，比點(diǎn)xi的γ值大的數(shù)據(jù)點(diǎn)將被自動(dòng)視為初始中心。

Ding等[26]提出新的判斷初始聚類中心的參數(shù)，提出了DPC-GEV和DPC-CI自動(dòng)選擇初始聚類中心。首先采用“最小最大化”將局部密度ρ和相對(duì)距離δ標(biāo)準(zhǔn)化，DPC-GEV認(rèn)為新的判斷參數(shù)θ=min（ρ*，δ*）大致遵循廣義極值分布，利用式（12）確定分位數(shù)p，θ>p的點(diǎn)被視為初始中心。

p=

-

（1-yp-ξ），

≠0

-

log yp，

≠0 （12）

yp=-log p? ? ? （13）

式中：，，的值均通過最大似然估計(jì)確定。DPC-CI借助切比雪夫不等式，如果點(diǎn)i滿足式（14）則被視為初始聚類中心。

θi>（μ+ε×σ），?ε>0 （14）

式中：μ和σ分別為判斷指標(biāo)θ的均值和標(biāo)準(zhǔn)差。實(shí)驗(yàn)結(jié)果表明，DPC-GEV與DPC-CI可以選擇出合理的初始中心，保證了DPC的連續(xù)性。但由于新的判斷指標(biāo)θ需參考局部密度參數(shù)，對(duì)于截?cái)鄥?shù)dc的依賴仍然存在。

關(guān)于上述DPC自動(dòng)化的優(yōu)化策略的對(duì)比分析如表 1 所示。

2.2 優(yōu)化密度參數(shù)ρ和相對(duì)距離δ

盡管DPC算法能處理大部分形狀數(shù)據(jù)集，但局部密度的定義過于簡(jiǎn)單，當(dāng)面對(duì)形狀結(jié)構(gòu)復(fù)雜的數(shù)據(jù)集時(shí)聚類精度下降。例如一個(gè)簇內(nèi)存在多個(gè)密度峰會(huì)導(dǎo)致簇被分割，數(shù)據(jù)分布的稠密性差異較大時(shí)DPC會(huì)忽視稀疏簇，流形數(shù)據(jù)集中位于不同簇但距離較近的數(shù)據(jù)對(duì)象被誤分配標(biāo)簽等。需要對(duì)DPC算法中的密度ρ和相對(duì)距離δ進(jìn)行優(yōu)化以適應(yīng)不同類型的數(shù)據(jù)集。

Guo等[27]提出的NDPC認(rèn)為無論是在密集或者稀疏的簇中，相比于其他點(diǎn)，聚類中心被包含在更多的K-最近鄰中。將數(shù)據(jù)對(duì)象的局部密度定義為其鄰居包含該點(diǎn)的數(shù)據(jù)對(duì)象的個(gè)數(shù)，從而公平對(duì)待密度分布差異較大的區(qū)域?；诖硕x，初始聚類中心的挑選不會(huì)造成稀疏簇的遺漏。另外，若一個(gè)簇中存在多個(gè)密度峰值，提出NDPC結(jié)合凝聚層次聚類算法的NDPC-AC將被分割的小簇迭代合并，直到最終簇的個(gè)數(shù)等于真實(shí)簇的個(gè)數(shù)，但NDPC-AC算法的凝聚策略需要提前知道真實(shí)簇的個(gè)數(shù)。劉娟等[28]提出一種借助自然反向最近鄰的密度峰值聚類算法，利用反向最近鄰計(jì)算密度參數(shù)，利用密度自適應(yīng)距離計(jì)算初始中心的距離，之后挑選更為合適的初始聚類中心（密度峰值點(diǎn)）。Du等[29]提出的DPC-KNN-PCA中將K-最近鄰的思想引入密度峰值聚類算法并改進(jìn)局部密度的定義，同時(shí)結(jié)合主成分分析（PCA）降維處理高維數(shù)據(jù)。

Hou等[30]認(rèn)為造成DPC算法性能不佳的原因是算法假設(shè)與實(shí)現(xiàn)過程的不一致性。假設(shè)基于數(shù)據(jù)對(duì)象間的相對(duì)密度關(guān)系，而算法實(shí)施過程中密度參數(shù)的計(jì)算卻是絕對(duì)密度關(guān)系，故作者提出了一個(gè)新的基于相對(duì)密度關(guān)系的初始聚類中心識(shí)別準(zhǔn)則。首先，作者提出從屬點(diǎn)和直接上級(jí)點(diǎn)的定義，并認(rèn)為數(shù)據(jù)點(diǎn)與其上級(jí)點(diǎn)存在于同一個(gè)簇中。如圖2所示，箭頭由從屬點(diǎn)指向直接上級(jí)點(diǎn)。

如果x2是x1最近的高密度點(diǎn)，即δ1=d（x1，x2），那么x1是x2的直接從屬點(diǎn)，x2是x1的直接上級(jí)點(diǎn)。為防止兩個(gè)獨(dú)立簇的合并，滿足δ>T的點(diǎn)被視為聚類中心，聚類中心點(diǎn)不會(huì)作為任意點(diǎn)的從屬點(diǎn)。其次，數(shù)據(jù)對(duì)象x1的局部密度ρi′通過只考慮直接從屬點(diǎn)的個(gè)數(shù)ηi確定

ρi′=ζ（si，xj）? ? （15）

ζ（u，v）=1， v為u的直接從屬點(diǎn)且v∈

S

0， 其他 （16）

式中：S代表數(shù)據(jù)點(diǎn)xi的ηi最近鄰的集合。該算法在數(shù)據(jù)密度分布不均勻時(shí)的聚類效果優(yōu)于其余聚類算法，但閾值T和初始聚類中心仍需要人為提前指定，且算法結(jié)果受K-最近鄰參數(shù)K的影響較大。

Xu等[31]提出的RDPC-DSS在DPC算法中用密度自適應(yīng)距離代替歐式距離處理流形數(shù)據(jù)集。在流形數(shù)據(jù)集中，如果兩點(diǎn)可以通過一條穿過高密度區(qū)域的路徑連接，那么稱他們具有較高的相似度。數(shù)據(jù)集X={x1，x2，…，xn}中的數(shù)據(jù)對(duì)象可以被視為圖G=（V，E）的結(jié)點(diǎn)，P={p1，p2，…，pl}為p1至pl的路徑，pij為連接v1至v2的所有路徑。密度自適應(yīng)距離Sij的計(jì)算為

Sij= （17）

式中：ρ′為放縮因子。之后將密度自適應(yīng)距離引入DPC算法，更新局部密度和相對(duì)距離的定義。RDPC-DSS在流形數(shù)據(jù)集上的聚類效果優(yōu)異，但計(jì)算密度自適應(yīng)距離的時(shí)間復(fù)雜度遠(yuǎn)高于DPC算法，使得處理大型數(shù)據(jù)集需要消耗大量的時(shí)間。

Lotfi等[32]提出的DPC-DBFN根據(jù)一種新的模糊核進(jìn)行局部密度的計(jì)算，減少離群點(diǎn)的影響。根據(jù)決策圖篩選出簇主干，簇主干能大致保持?jǐn)?shù)據(jù)集的形狀且距另一簇的主干距離較遠(yuǎn)，然后完成對(duì)剩余非主干點(diǎn)標(biāo)簽的傳播。

第1步，基于模糊鄰域的密度參數(shù)ρi定義為

ρi=max1-

dxi，xj，0? ? （18）

式中：KNN（xi）為數(shù)據(jù)點(diǎn)xi的K-最近鄰。

第2步根據(jù)決策圖確定聚類中心點(diǎn)，簇主干點(diǎn)，邊界點(diǎn)以及噪聲點(diǎn)。score函數(shù)值最大的c個(gè)數(shù)據(jù)作為初始聚類中心

score（i）=

2×? ? （19）

對(duì)于其余數(shù)據(jù)，如果ρi>ρ，則xi為主干中的密集點(diǎn);如果ρi<ρ且δi<λσδ2，則xi為簇的邊界點(diǎn);如果ρi<ρ且δi<λσδ2，則xi為噪聲點(diǎn)。其中，λ為控制參數(shù)，σδ2為相對(duì)距離的方差。

第3步分配標(biāo)簽主要包括主干點(diǎn)的分配以及邊界點(diǎn)的分配。標(biāo)簽分配過程始于將簇中心的標(biāo)簽分配到附近的主干點(diǎn)，首先將每個(gè)簇的標(biāo)簽傳給初始中心的K個(gè)最近的主干鄰居，之后再將標(biāo)簽傳遞給鄰居的鄰居，重復(fù)此過程，直到所有主干密集點(diǎn)都被分配簇標(biāo)簽。DPC-DBFN成功地克服了初始DPC算法以及大部分優(yōu)化算法帶來的問題，該算法能有效地識(shí)別聚類中心，并且能對(duì)形狀復(fù)雜的數(shù)據(jù)進(jìn)行聚類，并且對(duì)于噪聲點(diǎn)具有魯棒性。但該算法中仍存在兩個(gè)參數(shù)需要確定，控制參數(shù)和最近鄰參數(shù)K，且其對(duì)于聚類性能有著較大的影響。

基于共享最近鄰的快速搜索密度峰值聚類算法SNN-DPC[33]提出了共享最近鄰的概念，充分考慮數(shù)據(jù)集的結(jié)構(gòu)和形狀提出了新的兩個(gè)數(shù)據(jù)對(duì)象的相似性度量。并采用補(bǔ)償值的方式來處理簇間密度差異較大的數(shù)據(jù)集，為改善DPC算法后續(xù)非中心點(diǎn)分配過程的鏈?zhǔn)絾栴}，提出了兩步分配的策略。共享最近鄰SNN定義為K-最近鄰的交集SNN，基于SNN的相似性sim（xi，xj）定義為

sim（xi，xj）=，

若xi，xj∈SNN（xi，xj）

0，? ? ? ? ? ? ? ? 其他 （20）

式中：局部密度ρ定義為具有最大SNN相似性的K個(gè)數(shù)據(jù)對(duì)象的相似性之和。當(dāng)數(shù)據(jù)分布的稀疏程度差異較大時(shí)，為避免忽視稀疏簇，提出基于補(bǔ)償值的相對(duì)距離δ的定義。SNN-DPC在面對(duì)復(fù)雜形狀數(shù)據(jù)集時(shí)取得了優(yōu)異的聚類結(jié)果，且對(duì)噪聲點(diǎn)具有魯棒性。但缺點(diǎn)在于需要提前確定K-最近鄰的參數(shù)K，以及初始聚類中心仍需要通過人工選取，打斷了算法的連續(xù)性。

本小節(jié)基于DPC優(yōu)化密度參數(shù)和相對(duì)距離的不同策略，分析了優(yōu)化算法的核心技術(shù)以及優(yōu)缺點(diǎn)，優(yōu)化算法的對(duì)比分析如表 2 所示。

2.3 微簇合并避免鏈?zhǔn)絾栴}

DPC算法在面對(duì)流形數(shù)據(jù)集時(shí)，受算法假設(shè)的影響，即使挑選了合適的初始聚類中心，但在后續(xù)非中心點(diǎn)標(biāo)簽的分配過程中可能會(huì)產(chǎn)生鏈?zhǔn)絾栴}：一個(gè)誤分配點(diǎn)可能會(huì)導(dǎo)致大范圍數(shù)據(jù)標(biāo)簽的錯(cuò)誤傳播。凝聚層次聚類算法將數(shù)據(jù)對(duì)象看作單獨(dú)簇，每次合并相似度最高的兩個(gè)簇，直至合并到真實(shí)簇的個(gè)數(shù)。研究人員提出了一些類似于層次聚類的算法，先將數(shù)據(jù)集劃分成多個(gè)微簇，對(duì)數(shù)據(jù)對(duì)象進(jìn)行局部范圍內(nèi)的標(biāo)簽的分配，避免鏈?zhǔn)絾栴}。微簇的個(gè)數(shù)往往大于真實(shí)簇的個(gè)數(shù)，之后根據(jù)提出的簇間相似性不斷地將微簇進(jìn)行合并以形成最終的聚類結(jié)果。

Zhang等[34]受自然界衰減現(xiàn)象的啟發(fā)，提出基于密度衰減圖的DGDPC算法，通過密度衰減圖形成初始簇，之后根據(jù)同一衰減現(xiàn)象下的數(shù)據(jù)對(duì)象屬于同一個(gè)簇完成聚類過程。Li等[35]定義一種局部密度差異處理高維且數(shù)據(jù)分布不均勻的數(shù)據(jù)集，考慮了數(shù)據(jù)對(duì)象與其鄰居的密度差異，公平對(duì)待稠密程度不同簇的確定核心點(diǎn)。之后在K最近鄰圖上尋找潛在的交叉簇的邊，并刪除連接了噪聲的邊以及距離過遠(yuǎn)的邊，最后根據(jù)得到的新的K-最近鄰圖完成聚類。Bie等[36]提出了Fuzzy-CFSFDP算法借助模糊規(guī)則對(duì)不同的密度峰挑選不同的聚類中心，并且將具有相近的內(nèi)部模式的密度峰進(jìn)行合并，最后通過一種啟發(fā)式的方式挑選合適的初始中心。

Cheng等[37]將自然最近鄰的概念引入密度峰值聚類算法，提出了一種無需參數(shù)的基于局部核心密集成員的DLORE-DPC算法，其本質(zhì)是先尋找微簇核心再進(jìn)行微簇間的合并。通過挑選局部核心代表整個(gè)數(shù)據(jù)集，形成不同的微簇核心，之后在局部核心點(diǎn)之上通過圖距離完成DPC，最后根據(jù)代表點(diǎn)完成對(duì)剩余點(diǎn)的標(biāo)簽的分配。數(shù)據(jù)點(diǎn)xi局部密度den（xi）為

den（xi）=? ? ?（21）

式中：k為xi的自然最近鄰數(shù)。如果數(shù)據(jù)對(duì)象p是q的局部鄰域里具有最大den的點(diǎn)，則p稱作數(shù)據(jù)對(duì)象q的代表點(diǎn)，記作REP（q）=p。在此基礎(chǔ)上，如果REP（p）=p，數(shù)據(jù)對(duì)象p被認(rèn)為是一個(gè)局部核心點(diǎn)。將局部核心點(diǎn)的集合視為一個(gè)較小數(shù)據(jù)集，對(duì)其執(zhí)行DPC算法，兩個(gè)局部核心點(diǎn)p，q之間基于圖的距離DG（p，q）定義為

DG（p，q）=DS（pk，pk+1）? ?（22）

DS（p，q）=

，

若SNN（p，q）≠0

maxd，? ? ? ? ? ? ? ? 其他（23）

式中：pk，pk+1為最短路徑上相鄰的局部核心點(diǎn);m為連接核心點(diǎn)的節(jié)點(diǎn)數(shù);dlsore（p，q）為局部核心點(diǎn)之間的共享最近鄰。實(shí)驗(yàn)結(jié)果表明，DLORE-DPC算法無需人為輸入?yún)?shù)能發(fā)現(xiàn)不同形狀的聚類簇，由于該算法只計(jì)算局部核心之間的圖距離且只對(duì)核心點(diǎn)執(zhí)行DPC算法，算法的時(shí)間復(fù)雜度得到大大降低，但自然最近鄰搜索算法受噪聲點(diǎn)的影響較大且核心點(diǎn)集上的初始聚類中心的選取仍未自動(dòng)化。

Ni等[38]提出了一種尋找突出峰值點(diǎn)的優(yōu)化算法PPC，其通過將數(shù)據(jù)集劃分為多個(gè)潛在的簇，然后將密度峰值不突出的簇合并，從而獲得準(zhǔn)確的聚類結(jié)果。首先根據(jù)統(tǒng)計(jì)學(xué)中標(biāo)準(zhǔn)差和均值可以衡量數(shù)據(jù)的中心化趨勢(shì)，將滿足δi>δ+S的數(shù)據(jù)點(diǎn)視為潛在的簇中心，δ和S分別代表相對(duì)距離參數(shù)的均值和標(biāo)準(zhǔn)差，此時(shí)得到的簇的個(gè)數(shù)多于真正簇的個(gè)數(shù)。然后使用兩個(gè)密度峰之間的密度差確定峰值是否突出。如果此峰的密度差異大于閾值th，則足夠突出，就是一個(gè)聚集中心;否則，它與密度較高的鄰近峰在同一簇中。

Chen等[39]認(rèn)為對(duì)于具有變密度分布（VDD）數(shù)據(jù)集，繼續(xù)使用統(tǒng)一的密度函數(shù)會(huì)導(dǎo)致稀疏簇的丟失，故提出了針對(duì)數(shù)據(jù)密度分布不均勻的優(yōu)化算法DADC。首先定義了一種基于K-最近鄰（KNN）的區(qū)域自適應(yīng)密度，以自適應(yīng)地檢測(cè)不同密度區(qū)域的密度峰值。區(qū)域自適應(yīng)密度ρi定義為

ρi=i×

i=max

i×

（dij），其他? ? （24）

i=denk（i）+j∈K（（j）（denk（j）×ωi）? ? （25）

denk（i）=? ? （26）

其中：ωi=1/dij為數(shù)據(jù)與其K-最近鄰的權(quán)重值;denk（i），denk（j）為中間變量。最后根據(jù)簇間融合度是否大于閾值決定微簇的合并。

基于微簇合并避免鏈?zhǔn)絾栴}的優(yōu)化DPC算法的對(duì)比分析如表3所示。

2.4 提升算法速度

DPC算法的時(shí)間復(fù)雜度較高，DPC算法的時(shí)間復(fù)雜度主要由三方面組成：第一，計(jì)算數(shù)據(jù)點(diǎn)之間的歐氏距離矩陣需要消耗O（N2）;第二，對(duì)于每個(gè)數(shù)據(jù)對(duì)象的局部密度和相對(duì)距離的計(jì)算都需要遍歷數(shù)據(jù)集中的每一個(gè)點(diǎn)，時(shí)間復(fù)雜度為O（N2）;第三，對(duì)于非聚類中心點(diǎn)的分配過程的時(shí)間復(fù)雜度為O（N2）。因此，DPC算法整體的時(shí)間復(fù)雜度為O（N2），算法的時(shí)間消耗較大，處理大型數(shù)據(jù)集時(shí)的效率不高。

Chen等[40]提出的FastDPeak算法基于降低原始DPC算法中計(jì)算局部密度和對(duì)距離的時(shí)間復(fù)雜度。首先采用Cover-tree尋找每個(gè)數(shù)據(jù)對(duì)象的K-最近鄰，并利用KNN密度代替原始密度。其次對(duì)于相對(duì)距離的計(jì)算，將數(shù)據(jù)對(duì)象分為局部密度峰值和一般點(diǎn)（非局部密度峰值）。局部密度峰值點(diǎn)是數(shù)據(jù)對(duì)象在其K-最近鄰具有最大的局部密度，否則為一般點(diǎn)。一般數(shù)據(jù)點(diǎn)的相對(duì)距離的計(jì)算只需要遍歷其K-最近鄰，而對(duì)于局部峰值點(diǎn)，通過逐漸擴(kuò)大K值的方式計(jì)算其相對(duì)距離，大大降低了算法計(jì)算密度的時(shí)間消耗，時(shí)間復(fù)雜度約為。Wu等[41]提出了DGB聚類算法，DGB運(yùn)用了網(wǎng)格化的思想減少數(shù)據(jù)空間中不必要的歐式距離的計(jì)算。首先將數(shù)據(jù)空間進(jìn)行網(wǎng)格化得到一些小單元格Cell，將原本每個(gè)數(shù)據(jù)點(diǎn)之間的歐氏距離替換為計(jì)算少量的非空單元格Cell之間的距離，這大大地提升了算法的計(jì)算速度。Sami等[42]提出一種優(yōu)化的快速密度峰值聚類算法FastDP，在對(duì)聚類質(zhì)量沒有明顯影響的情況下實(shí)現(xiàn)了算法的加速。其使用一種快速且通用性強(qiáng)的K-最近鄰圖計(jì)算局部密度和相對(duì)距離參數(shù)，傳統(tǒng)DPC算法二次時(shí)間復(fù)雜度的問題得到消除，并允許對(duì)大規(guī)模的數(shù)據(jù)集進(jìn)行聚類。

表4對(duì)比分析了基于提升速度的優(yōu)化DPC算法。

3 結(jié)束語

本文主要將DPC的優(yōu)化算法基于4大類進(jìn)行了詳細(xì)闡述和分析：實(shí)現(xiàn)DPC的自動(dòng)化，優(yōu)化密度參數(shù)和相對(duì)距離，微簇合并避免鏈?zhǔn)絾栴}與提升算法速度，并指出優(yōu)化算法的核心技術(shù)及優(yōu)缺點(diǎn)。

參考文獻(xiàn)：

[1] XU R，WUNSCH D. Survey of clustering algorithms[J]. IEEE

Transactions on Neural Networks，2005，16（3）：645-678.

[2] JAIN A K，Murty M N，F(xiàn)LYNN P J. Data clustering：a review[J]. ACM Computing Surveys（CSUR），1999，31（3）：264-323.

[3] HOU J，LIU W，XU E，et al. Towards parameter-independent data clustering and image segmentation[J]. Pattern Recognition，2016，60：25-36.

[4] SULAIMAN S N，ISA N A M. Adaptive fuzzy-K-means clustering algorithm for image segmentation[J]. IEEE Transactions on Consumer Electronics，2010，56（4）：2661-2668.

[5] YIN J，WANG J. A dirichlet multinomial mixture modelbased approach for short text clustering[C]//Association for Computing Machinery：Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining，2014.

[6] 韓慶華，馬乾，劉名，等. 溫度變化下基于固有頻率聚類分析的空間網(wǎng)格結(jié)構(gòu)損傷診斷[J]. 華東交通大學(xué)學(xué)報(bào)，2021，

38（4）：8-17.

HAN Q H，MA Q，LIU M，et al. Damage diagnosis of space grid structure based on natural frequency clustering analysis under varying temperature effects[J]. Journal of East China Jiaotong University，2021，38（4）：8-17.

[7] HAMZA A B. Graph regularized sparse coding for 3D shape clustering[J]. Knowledge-Based Systems，2016，92：92-103.

[8] TRUONG H Q，NGO L T，PEDRYCZ W. Granular fuzzy possibilistic C-means clustering approach to DNA microarray problem[J]. Knowledge Based Systems，2017，133：53-65.

[9] BORDOGNA G，PASI G. A quality driven hierarchical data divisive soft clustering for information retrieval[J]. Knowledge-

based systems，2012，26：9-19.

[10] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Berkelay：Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. 1967，1（14）：281-297.

[11] KAUFMAN L，ROUSSEEUEW P J. Finding groups in data：an introduction to cluster analysis[M]. London：John

Wiley & Sons，2009.

[12] ESTER M，KRIEGEL H P，SANDER J，et al. A density-based algorithm for discovering clusters in large spatial databases with noise[J]. Data Base System and Logic，1996，

96（34）：226-231.

[13] ANKERST M，BREUNIG M M，KRIEGEL H P，et al. OPTICS：Ordering points to identify the clustering structure[J]. ACM Sigmod Record，1999，28（2）：49-60.

[14] GUHA S，RASTOGI R，SHIM K. CURE：An efficient clustering algorithm for large databases[J]. ACM Sigmod Record，1998，27（2）：73-84.

[15] ZHANG T，RAMAKRISHNAN R，LIVNY M. BIRCH：an efficient data clustering method for very large databases[J]. ACM Sigmod Record，1996，25（2）：103-114.

[16] WANG W，YANG J，MUNTZ R. STING：A statistical information grid approach to spatial data mining[J]. Programming，1997，97：186-195.

[17] VON L U. A tutorial on spectral clustering[J]. Statistics

and Computing，2007，17（4）：395-416.

[18] DEMPSTER A P，LAIRD N M，RUBIN D B. Maximum likelihood from incomplete data via the EM algorithm[J].

Journal of the Royal Statistical Society：Series B（Methodological），1977，39（1）：1-22.

[19] 章永來，周耀鑒. 聚類算法綜述[J]. 計(jì)算機(jī)應(yīng)用，2019，

39（7）：1869-1882.

ZHANG Y L，ZHOU Y J. Review of clustering algorithms[J]. Journal of Computer Applications，2019，39（7）：1869-1882.

[20] RODRIGUEZ A，LAIO A. Clustering by fast search and find of density peaks[J]. Science，2014，344（6191）：1492-1496.

[21] LIU Y H，MENG E M，YANG F. Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy[J]. Knowledge-Based Systems，2017，133：208-220.

[22] 王芙銀，張德生，張曉. 結(jié)合鯨魚優(yōu)化算法的自適應(yīng)密度峰值聚類算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2021，57（3）：94-102.

WANG F Y，ZHANG D S，ZHANG X. Adaptive density peaks clustering algorithm combining with whale optimization algorithm[J]. Computer Engineering and Applications，2021，57（3）：94-102.

[23] WANG S，WANG D，LI C，et al. Clustering by fast search and find of density peaks with data field[J]. Chinese Journal

of Electronics，2016，25（3）：397-402.

[24] 王洋，張桂珠. 自動(dòng)確定聚類中心的密度峰值算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2018，54（8）：137-142.

WANG Y，ZHANG G Z. Automatically determine density of cluster center of peak algorithm[J]. Computer Engineering and Applications，2018，54（8）：137-142.

[25] FLORES K G，GARZA S E. Density peaks clustering with gap-based automatic center detection[J]. Knowledge Based

Systems，2020，206：106350.

[26] DING J，HE X，YUAN J，et al. Automatic clustering based on density peak detection using generalized extreme value distribution[J]. Soft Computing，2018，22（9）：2777-2796.

[27] GUO Z，HUANG T，CAI Z，et al. A new local density for density peak clustering[C]//Springer Cham：Pacific-Asia Conference on Knowledge Discovery and Data Mining，2018.

[28] 劉娟，萬靜. 自然反向最近鄰優(yōu)化的密度峰值聚類算法[J]. 計(jì)算機(jī)科學(xué)與探索，2021，15（10）：1888-1899.

LIU J，WAN J. Optimized density peak clustering algorithm by natural reverse nearest neighbor[J]. Journal of Frontiers of Computer Science and Technology，2021，15（10）：1888-1899.

[29] DU M，Ding S，JIA H. Study on density peaks clustering based on K-nearest neighbors and principal component analysis[J]. Knowledge-Based Systems，2016，99：135-145.

[30] HOU J，ZHANG A，QI N. Density peak clustering based on relative density relationship[J]. Pattern Recognition，2020，

108：107554.

[31] XU X，DING S，WANG L，et al. A robust density peaks clustering algorithm with density-sensitive similarity[J].

Knowledge-Based Systems，2020，200：106028.

[32] LOTFI A，MORADI P，BEIGY H. Density peaks clustering based on density backbone and fuzzy neighborhood[J].

Pattern Recognition，2020，107：107449.

[33] LIU R，WANG H，YU X. Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J]. Information Sciences，2018，450：200-226.

[34] ZHANG Z，ZHU Q，ZHU F，et al. Density decay graph-based density peak clustering[J]. Knowledge Based Systems，2021，224：107075.

[35] LI R，YANG X，QIN X，et al. Local gap density for clustering high-dimensional data with varying densities[J].

Knowledge Based Systems，2019，184：104905.

[36] BIE R，MEHMOOD R，RUAN S，et al. Adaptive fuzzy

clustering by fast search and find of density peaks[J]. Personal and Ubiquitous Computing，2016，20（5）：785-793.

[37] CHENG D，ZHANG S，HUANG J. Dense members of local cores based density peaks clustering algorithm[J]. Knowledge Based Systems，2020，193：105454.

[38] NI L，LUO W，ZHU W，et al. Clustering by finding prominent peaks in density space[J]. Engineering Applications of Artificial Intelligence，2019，85：727-739.

[39] CHEN J，PHILIP S Y. A domain adaptive density clustering algorithm for data with varying density distribution[J]. IEEE Transactions on Knowledge and Data Engineering，2019，33（6）：2310-2321.

[40] CHEN Y，HU X，F(xiàn)AN W，et al. Fast density peak clustering for large scale data based on KNN[J]. Knowledge Based Systems，2020，187：104824.

[41] WU B，WILAMOWSKI B M. A fast density and grid based clustering method for data with arbitrary shapes and noise[J]. IEEE Transactions on Industrial Informatics，2016，13（4）：1620-1628.

[42] SIERANOJA S，F(xiàn)RANTI P. Fast and general density peaks clustering[J]. Pattern Recognition Letters，2019，128：551-

558.