密度峰值聚類算法綜述

陳葉旺 申蓮蓮 鐘才明 王 田 陳 誼 杜吉祥

1(華僑大學計算機科學與技術學院 福建廈門 361021)2(食品安全大數據技術北京市重點實驗室(北京工商大學) 北京 100048)3(江蘇省計算機信息處理技術重點實驗室(蘇州大學) 江蘇蘇州 215006)4(福建省大數據智能與安全重點實驗室(華僑大學) 福建廈門 361021)5(寧波大學信息學院 浙江寧波 315211)

近年來，全球存儲的信息以每年近24%的速度增長[1]，數據量的爆炸式增長加快了大數據時代的到來，這給各行各業帶來了新的機遇和挑戰.如何對大數據高效地進行自動分析和挖掘成為各行業面臨的重大課題.

聚類算法是處理大數據的關鍵技術之一，它根據數據的相似特征對數據集進行自動劃分，按一定規則根據對象屬性把對象劃分成不同的類別，同一個類別下的對象具有一定的相似性，而不同類別對象之間則差異性較大.聚類算法是機器學習中一種重要的無監督學習技術[2]，已廣泛應用于諸多領域，如計算機科學[3-5]、生物信息學[6-9]、圖像處理[10-13]、社會網絡[14-15]、天文學[16]以及許多其他領域[17].

目前，現有的聚類算法數以千計，且還在大量涌現.不同的聚類算法能很好地解決某些特定問題，但總體上仍然存在許多亟待解決的問題，比如聚類效果受數據分布影響大[18-19]、復雜度高、聚類數量需人工干預、聚類效果難以評價[20]等.

2014年在《Science》上發表了密度峰值聚類(density peak, DPeak)算法[21].該算法可識別出任意形狀數據，能直觀地找到簇(類別)數量，也能非常容易地發現異常點.此外，DPeak參數唯一、使用簡單、具有非常好的魯棒性，因而受到了廣泛的關注.

本文針對DPeak算法進行介紹、分析，并總結了近年來的發展與應用動態，主要貢獻有以下4個方面：1)介紹了DPeak算法，對其在聚類算法體系中的位置進行了討論.特別地，對DPeak與mean shift[22]作了詳細比較，并認為DPeak可能是一種特殊的mean shift算法或變種.2)討論了DPeak算法的不足，并對相關改進算法的優缺點進行了分類討論.3)梳理了DPeak及其改進算法在不同應用領域中所發揮的作用.4)討論了DPeak與相關改進算法所存在的問題及挑戰，并對其未來工作進行展望.

1 DPeak聚類算法的原理

DPeak是一種粒度計算模型[23]，不僅在學術界產生了熱烈的反響，同時也吸引了大量科研人員對該算法進行研究.DPeak算法基于2個假設：1)聚類中心被局部密度較低的近鄰數據點包圍；2)任意聚類中心與比它密度更高的數據點之間的距離都較遠.

對于任意數據點i，DPeak需要計算2個量：i的局部密度ρi和它與具有更高密度的最近點的距離δi.數據點i的局部密度ρi定義為

(1)

其中,n為數據點個數；dij是數據點i和j的距離；χ是指示函數，當x<0時，χ(x)=1，否則χ(x)=0；dc是截斷距離.可以看出，ρi等于分布在i的dc鄰域范圍內的數據點個數，即密度.δi則是通過計算點i與其他密度更高的點之間的最小距離來測量:

(2)

除了式(1)的計算離散點的密度方式外，還有一種利用高斯核來計算連續點密度的方式，如下：

(3)

基于這2個量，DPeak通過“決策圖”將數據點區分為3種不同的類型，即密度峰值點、正常點與離群點.如圖1所示，數據點按密度遞減的順序排列.容易看出點1和10是非常突出，分布在圖的右上角，具有非常高的δ值和ρ值，表明這2點在較大鄰域范圍內不存在比它們密度更高的數據點.因而這2個點正是所謂的密度峰值點，適合被選為簇(類別)中心.點7，8雖然具很高的ρ值，δ值卻很小，分布在右下角，表明在它們近鄰處存在密度更高的點，因而不是峰值點，不適合作為簇中心.點26，27，28具有較高的δ，ρ值卻非常低，分布在偏左上角，表明它們是離群點.

Fig. 1 Two-dimensional mapping圖1 二維映射[21]

用戶可以在決策圖中手動選擇簇中心，也可以選取前k個γ值最大的數據點作為簇中心,其中γ=ρ×δ.DPeak再將剩余的點分配到與其最近的密度較高的鄰近區域的簇中.

2 DPeak與其他算法的比較

2.1 DPeak在聚類算法簇中的類別歸屬

聚類算法憑借其廣泛的適用范圍吸引了大量的研究人員，目前已存在大量的相關工作.為方便研究，人們對這些聚類算法進行了分類.基于現有聚類的分類方式[24-30]，大致將聚類算法分為7類：劃分聚類(division based)、層次聚類(hierarchical clustering)、網格聚類(grid based)、基于密度聚類(density-based)、模型聚類(model-based)、代表點聚類(exemplar)和圖模型聚類(graph model)，每種類型的聚類方式都有其優缺點.這些分類的方法并非是排他的，即一種聚類算法可以分別屬于好幾種不同類別.例如：均值漂移聚類(mean shift)[31]是基于密度梯度進行分析的，其中每個數據點迭代地向其局部密度中心漂移,所以可劃分為基于密度聚類的算法.但其簇內數據點之間實際上是存在一定的層次關系，因而也可歸到層次聚類.k均值聚類算法(k-means)雖然一般認為是劃分聚類和代表點(質心)聚類，但它又是mean shift的一種特例[22].最大熵聚類[32]是一種基于統計物理的聚類方法，也是一種基于特殊內核的mean shift算法[22]，所以也可劃分到多種類別上.

對于DPeak而言，它是一種混合型聚類算法，可歸為層次聚類、代表點聚類和密度聚類:

1) 層次聚類

與劃分聚類相比，層次聚類[33]通過以自上而下或自下而上的方式遞歸地對數據進行分類來構建簇，可以更好地反映真實世界的數據集.層次聚類生成了一個嵌套簇的層次序列，可以用樹狀圖來表示，輸出的結果為層次結構，比平面結構含有更多的信息[34].然而，層次聚類缺乏魯棒性，數據集小的擾動就會產生層次樹狀圖結構較大的變化，而且算法的復雜度高[35].

Xu等人[36]提出了前導樹的概念，除了根節點外，每個節點都是由其父節點引導加入同一個簇中的，即每個點的上一層節點是與其距離最近且密度更高的點，而整個數據集中密度最高的點是根節點.按前導樹規則，DPeak算法生成的聚類結構實際上是一棵樹狀的層次結構，如圖2所示.圖2(a)是數據分布圖；圖2(b)是根據圖2(a)畫出來的樹；圖2(c)是假設簇數為3時，所生成的森林.點5是密度最大的點因此也是樹的根節點.3，10，14，15，18為1個簇，其中3為密度峰值點；5，6，7，9，12，13，16，19，20為1個簇，其中5為密度峰值點；其余點為1個簇，其中8為密度峰值點.

Fig. 2 Hierarchical structure of DPeak algorithm圖2 DPeak算法的層次結構

2) 代表點聚類

代表點聚類分為3類[38]：①把每個樣本都視為潛在的簇中心，迭代更新其吸引度值和歸屬度值直到產生更好的代表點.如APCluster[39]中通過不斷迭代使得每個類別產生的聚類中心為其代表點(exemplar).②隨機選擇代表點通過迭代調整來達到平方誤差最小，如k-means.③采用密度估計來發現密度峰值點，用以當作代表點.

DPeak滿足上述類型③，即選取一組密度高的遠點來代表不同簇，如圖2(c)中的3，5，8分別是3個簇的代表點.因而，DPeak可歸為基于代表點聚類.

3) 密度聚類

密度聚類假設屬于每個簇的點是從一個特定的概率分布[40]中提取出來的，該類算法可以發現任意形狀的簇.基于密度聚類以DBSCAN[41]為代表，不需要先驗知識來指定數據中的簇數，并且可以發現特征空間中具有任意形狀的簇.但是它對用戶定義的參數值非常敏感，即使參數設置稍有不同，通常也會在數據集中產生非常不同的聚類結果[24].

DPeak與DBSCAN(density-based spatial clustering of applications with noise)相比，兩者的密度定義一致，DPeak中的截斷距離參數dc與DBSCAN中的eps起相同作用.兩者都將數據空間中密度較大的連續區域視為同一簇，因此DPeak算法是一種密度聚類算法.故密度聚類可以發現任意形狀的簇這一優點也在DPeak算法中得以體現.

2.2 DPeak與5個主要聚類算法比較

目前，比較常用的聚類算法主要是k-means[18-19]、DBSCAN[41-42]、mean shift[31]、譜聚類(spectral clustering)[43]和近鄰傳播聚類(affinity propagation cluster， APCluster)[39,44].相比于這些算法，DPeak算法的思想簡單、參數要求少、能識別出任意形狀的簇，缺點是復雜度較高.表1對上述這些算法進行了詳細比較.可看出DPeak與mean shift算法最為接近.因此本文對兩者進行詳細比較，具體有6個方面：

1) 兩者聚類過程都是自然過程.簇的形成是順著數據密度變大的方向延展的，有明確的漂移軌跡.

2) 兩者不同在于mean shift漂移的中間點可能是虛擬點，而在DPeak中，低密度點向上漂移到與其最近的高密度點，要求中間點必須是定義在數據集中的真實點.這個過程是一次搜索完成的，即不需迭代.

3) Fukunaga等人[45]提出mean shift算法，并認為該方法可能是梯度上升法.Cheng[22]指出mean shift是變步長的影子梯度上升法，當數據分布是理想狀態下的高斯分布時mean shift是最速上升法.Fashing等人[46]進一步指明當核函數是分段常數(piecewise const)時，mean shift是牛頓法，而對于任意核函數，mean shift的均值漂移過程實際上是在使用影子函數對密度估計進行二次有界最大化.

直觀而言，DPeak也應屬于梯度上升法.按DPeak的定義可以理解為：每個點i向比其密度更高的最近鄰(目標點)漂移，是跳躍式非連續的最小步長梯度上升法.目標點在i的最小步長鄰域范圍內密度最高，該最小步長不受參數dc約束，是全局最優.而mean shift則是在局部范圍內尋找密度上升方向，其漂移過程是連續的、局部收斂和局部最優的.

Table 1 Comparisons on Several Typical Clustering Algorithms表1 幾種典型聚類算法的比較

Note: √ means “Yes” or “Has”; × means “No”.

4) 雖然mean shift是無參算法，但當其核函數是平整函數(flat kernel)時需要輸入參數，其作用與DPeak的參數dc等價.

Fig. 3 Two examples of local peak of DPeak圖3 DPeak的局部峰值中心2個實例

5) mean shift無需指定聚類個數k，因為mean shift直接將均值漂移的收斂點視為一個簇的中心，也是局部密度中心點.DPeak算法雖然要指定k(或指定具體的聚類峰值點)，但其與mean shift一樣，在數據漂移的過程中存在一些數據點是局部中心點，這些點在dc鄰域范圍內是密度最高的，即局部峰值中心點.它們的密度更高且近鄰在dc鄰域范圍之外.在沒有指定k的情況下，可將這些點作為聚類中心，這與mean shift的尋找聚類中心方式是一致的.

以圖3為例，圖3(a)中局部峰值中心點有2和6，嚴格來說點2應該向點6繼續漂移，如虛線箭頭方向所示.若以局部峰值中心點為聚類中心，則該圖可聚成2類：1，2，3一類；0，4，5，6，7，8，9為另一類.同理，圖3(b)中局部峰值中心點有2，6，7，該圖可聚成3類，分別是：1，2，3為第1類；0，4，6，8為第2類；5，7，9為第3類.

6) 在DPeak計算過程中，數據集S本身固定不變，是一個非模糊過程(non-blurring process)[21].在起始階段，DPeak把所有數據點都看成是臨時中心，并為每一個點迭代尋找最終中心.只不過在迭代程中有許多路徑是重疊或重復的，可以省略，使DPeak看起來顯得不用迭代，其復雜度相比mean shift較低.以圖2(b)為例，對于數據點17而言，對其做完整迭代的路徑是：17→8→12→20→5；對于數據點8而言，其路徑則為：8→12→20→5，2條路徑是交叉重疊的.因而，若數據點17的漂移路徑計算完成后，點8的迭代過程可以省略，數據點12，20類似.

3 DPeak算法的優化

DPeak算法具有諸多優點，如不需要迭代、參數少、算法簡單等，但仍存在一些亟待解決的問題.

1) 復雜度O(n2)較高.不適用于大規模數據的聚類分析.

2) 過程不是自適應的.不能自動調整內在參數.例如，不能自適應選擇密度峰值與dc.

3) 精度易受影響.DPeak在計算局部密度時，如果沒有考慮到數據的局部結構會導致許多簇的丟失、“假峰”[47-48]和“無峰值”[49]現象從而影響聚類的精度.

4) 高維數據適用性差.因為在高維數據中的許多維度相互無關，這會造成一些簇的丟失[50].

針對這些問題，近年來有許多算法從各方面對DPeak算法進行改進，下文選擇具有代表性的算法進行匯總、分類和分析.

3.1 提升速度

DPeak在計算過程中產生了距離矩陣，因此增加了其空間復雜度.Wu等人[51]提出了DGB(density-and grid-based)聚類方法，先使用網格技術對數據空間按維度進行劃分，每個單元格稱之為一個Cell，再通過計算少量的非空Cell節點之間的距離來代替計算每個點之間的歐氏距離從而達到提升DPeak速度的目的.類似地，Xu等人[52]提出DPCG(density peaks clustering algorithm based on grid)算法，在計算局部密度時采用分團(clique)方法[53]中的網格思想來代替DPeak的原始方法，可將DPeak第1步計算數據點密度的復雜度大幅降低，也可將DPeak第2步尋找各點的密度更高近鄰的復雜度降為O(m2)，其中m為非空Cell數.PDPC(fast density peaks clustering algorithm based on pre-screening)[54]也采用網格(grid)技術來在前期過濾一部分計算，快速找到密度稠密區域.

然而，DGB和DPCG算法實驗均只是在低維小規模數據集上有較好表現.在較高維數據集上，這2種方法效果并不佳，不能有效地對大規模數據進行聚類.究其原因在于：隨著數據空間維度增大，Cell數成幾何級數增長.非空Cell數越多，利用網格消除的歐氏距離計算量就越少.當非空Cell數接近于數據點總個數n時，網格技術失效[55].

我們隨機生成若干個數據集，維度d分別取2，3，4，5，10，數據點每個維度上的取值范圍為(0，1].對這些數據集進行網格劃分，Cell寬度設為0.1.表2列出不同數據集上的Cell個數.從表2中可以看出隨d的增長，非空Cell個數指數級增長.

Table 2 Cell Growth Trend with Dimension表2 Cell隨維度增長變化趨勢表

另外，Li等人[56]引入CUDA技術，通過GPU實現DPeak算法的簡單并行化，相比于在CPU上運行，該算法計算距離矩陣速度提升了4.39倍(其中線程數為1 000，有N個Blocks，Block size為32×32).當硬件條件更好時，速度還可以進一步提升.該算法復雜度降為O(αn2t)，其中t為線程數，α為GPU數據調度偶合系數.可以看出通過并行化處理，以硬件加速來改進DPeak是可行之道.

在DPeak的計算過程中，每個點的ρ與δ值需要計算距離2n2次，計算量無疑是非常大的．Bai等人[26]提出了一種計算更少距離的加速算法CFSFDP+A，并且可以得到與原算法相同的聚類結果．該文作者發現簇往往存在于局部空間中，因此采用k-means來劃分空間區域，使用近似算法和三角不等式精確地縮小了搜索空間.CFSFDP+A的時間復雜度為O(nkmt+nn1+nn2)，其中km為劃分的子集數，t為迭代次數，n1為計算所有點的密度時計算距離的平均次數，n2為劃分空間時計算距離的平均次數.該算法的時間復雜度仍然接近O(n2)，速度的提升并不顯著.為了進一步擴展CFSFDP+A并提升算法的速度，該文作者還提出了一種基于代表點的近似算法CFSFDP+DE(clustering by fast search and find of density peaks based on exemplar clustering)，使用k-means所產生的每個簇的代表點來代替樣本點，利用代表點的密度關系來進行聚類.該算法的時間復雜度為O(nkmt+k2m)雖然速度相較于DPeak已經有所提升，但是復雜度大于O(nlogn).

為提升DPeak的效率和可擴展性，鞏樹鳳等人[57]提出了EDDPC(efficient distributed density peak clustering).該算法選擇Voronoi分割所需要的種子，再用2個完整的MapReduce[58]作業分別計算ρ與δ值.首先，將數據分組并獨立并行地處理各分組中的數據對象，在各分組內局部計算ρ值和δ值，以克服計算所有對象間的距離所造成的大量開銷.該文作者給出了1個數據對象復制模型和2個數據對象過濾模型，將部分其他分組內的必要對象復制到本分組內來確保數據獨立并行執行.此外，該文作者對比EDDPC和SDDPC(simple distributed density peak clustering)[57]后發現，EDDPC的運行速度明顯小于SDDPC.值得注意的是，DPeak在單片機上運行數據量小的情況下運行時間優于SDDPC，但是在運行大規模數據時會出現內存溢出的現象.Zhang等人[59]在證明了Basic-DDP(basic distributed density park clustering)解決方案具有很高的通信開銷后，提出了LSH-DDP(an app-roxima-tion algorithm for partitioning using local sensitive Hash).該算法利用局部敏感散列(local sensitive Hash, LSH)對輸入數據進行分區，以便近鄰點更有可能被分配到同一個分區，基于LSH的算法在每個分區內執行本地計算，然后聚合結果，得到最終的近似結果.該方法與EDDPC的聚類效果相似且速度是EDDPC的2倍，是Basic-DDP的1.7倍到70倍.

Chen等人[37]提出了FastDPeak(fast density peak clustering for large scale data based on KNN).基KNN搜索，該算法應用cover tree對密度計算進行加速.另外為避免在全局范圍內計算各個點的δ值，提出了局部密度峰值與非局部密度峰值點概念，用以對δ值計算進行加速.若數據點p在其最近的k個近鄰中密度最高，則稱其為局部峰值點，否則為非局部密度峰值點.對于非局部密度峰值點而言，其父節點一定在其k個近鄰內.對于局部密度峰值點，可逐漸增加k值來擴大搜索范圍，來尋找它的上層節點.因而，FastDPeak大幅減少了δ值的計算復雜度，約為O(dk),其中d為與數據分布有關的常數.

綜合來說，FastDPeak時間復雜度為O(nlogn)，空間復雜度為O(kn)，其中k為KNN中的k值.如果k值較大，則需要大量的存儲空間，因此該算法還需要改進從而優化算法.

表3所示的是8種算法分別在BigCross，KDD99，KDD04[60]等數據集上的速度測試結果.可以看出，與CFSFDP+A[26]，CFSFDP+DE[26]，EDDPC[57]，LSH-DDP[59]等算法比較，FastDPeak有較大改進.

Table 3 Runtime Comparison on Several Data Sets表3 幾個數據集上的運行時間比較 s

3.2 參數自適應化

由于DPeak算法中局部密度的原始定義是基于截斷計數測量的，因此很難推導出合理的參數估計準則和“最優”的參數.Wang等人[35]提出了ADPclust(fast clustering using adaptive density peak detection).首先，利用非參數的多元核估計來估計局部密度，并通過統計理論證明了模型參數的計算合理性.其次，該文作者在用戶交互選擇簇數目的基礎上，提出了一種基于輪廓優化算法的簇中心自動選擇方法.該方法無需迭代，在大數據分析中具有快速、實用的特點.dc的敏感性和密度的選擇是影響DPeak聚類效果的兩大問題.高斯核是一種局部密度估計方法，但是對于小簇的估計難以保證精度.雖然可以通過調整參數dc來提升精度，但是這要求dc適應不同的簇，顯然難以實現.因此Hou等人[61]提出了一種新的局部密度估計方法，該方法僅采用最近鄰來估計密度.局部密度主要用于將聚類中心與其他數據分離，該文利用最近鄰數據中最遠的那些點來突出聚類中心的唯一性，并建議使用密度歸一化來處理簇之間的密度差異.該算法密度函數定義為

(4)

DPeak算法在人工選擇聚類中心的基礎上能夠得到滿意的結果，但這種選擇對于大量的聚類任務或具有復雜決策圖的數據集來說都很難實現.Ding等人[29]提出了DPC-GEV(density peaks clustering based on generalized extreme value distribution).受到DPeak的視覺選擇規則啟發，該文作者提出了判斷指數，并將其用于選擇聚類中心.判斷指數大致遵循廣義極值(generalized extreme value， GEV)分布，每個聚類中心的判斷指數要比其他點的判斷指數高得多.因此，如果它們的判斷指數大于GEV的上分位數，則選擇這些點作為聚類中心是合理的.考慮到計算復雜性，該文還提出了DPC-CI(alternative method based on density peak detection using Chebyshev inequality).DPC-CI通過計算判斷指標的期望和標準差，并根據切比雪夫不等式設置上界.DPC-GEV和DPC-CI在大多數數據集上可以達到與DPeak相同的精度，但消耗的時間要少得多.

(5)

(6)

(7)

ADPC-KNN只需一個參數就能自動聚類，總體時間復雜度與DPeak一樣都為O(n2),其空間復雜度與DPeak也是相同的.該方法可以正確且不遺漏地找到簇中心，但是簇數目的選取仍是由人工實現的.

固定掃描半徑主要有2個缺陷：1)對于高維數據來說，選擇固定的掃描半徑十分困難；2)對于存在假峰的數據集并不適合.如圖4，在圓與中心點c之間存在空白區域，r1是外半徑，r2是內半徑.大部分點位于圓環范圍內，從圓的內邊緣到中心存在一個沒有數據點的空白區域.顯然，在掃描半徑大于r1的情況下，點c為密度峰值.而掃描半徑小于r2時，它實際上是一個被排除在圓之外的離群點.這種現象被稱為“假峰”[47].因此，Chen等人[47]提出了DHeat(density heat-based algorithm for clustering with effective radius)方法，可以解決固定掃描半徑造成的缺陷.該方法基于2個假設：1)如果密度分布均勻，一個點在其鄰域半徑內的密度與鄰域的體積成正比.2)每個聚類可以劃分為不同的密度層，如邊緣、淺層、內層等.一個點所處的位置越是深入內層區域，這個點的密度就越高.

Fig. 4 “Fake Peak” illustration圖4 “假峰”說明圖[47-48]

DPeak需要使用不同的方法來估計不同數據集的密度，并且dc的估計很大程度上取決于主觀經驗.為了克服DPeak的局限性，Mehmood等人[63]提出了CFSFDP-HD(clustering by fast search and find of density peaks via heat diffusion).該方法結合了截止距離選擇和核密度估計的邊界校正以便更好地估計密度，從而達到更精確的聚類效果，更有效地將聚類點的噪聲分離出來.該方法對于大型數據集具有很好的魯棒性，但是仍需要利用人機交互的方式來選擇簇的數目.

基于以上分析，不難發現阻礙DPeak自動化的三大因素分別為中心的選擇、dc的選擇及簇數目的選取.其中已經有大量的相關研究對前2個因素進行改進，或采用非參數估計[63]來改善參數對聚類效果的影響.但是對于簇數目的選取仍然停留在人工干預選擇階段，缺少自動選擇簇數目的相關工作.

3.3 改進聚類精度和魯棒性

DPeak采用不同的方法確定不同數據集大小中點的局部密度.雖然DPeak對于大數據集的結果是穩健的，但對于小數據集則對dc非常敏感.此外，DPeak易產生多米諾骨牌效應，一旦一個點分配錯誤就會導致更多的點分配錯誤.為了增強DPeak的魯棒性，Xie等人[28]提出了FKNN-DPC(robust clustering by detecting density peaks and assigning points based on fuzzy weighted KNN).由式(4)可以得到密度ρi，無論k最近鄰點的數據集大還是小，該算法的局部密度ρi均與截止距離dc無關.將剩余點分配給最可能的簇有2種策略：1)通過從簇中心開始對每個點的k最近鄰進行廣度優先搜索來分配非異常值；2)使用模糊加權KNN技術，分配異常值和第1次分配過程未分配的點.主要技術如下：

定義點i和j之間的相似性wij，即

(8)

(9)

(10)

其中，yi是點j的簇標號.然后將點i分配給概率最高所對應的簇中.

Pang等人[64]提出了MrGDM(multi-granularity decomposition mechanism of complex tasks based on density peaks).首先，構建全局任務前導樹，將該樹看作是原始的求解空間，即包含全局信息概念的粗粒度層.該文作者對DPeak算法進行了改進，消除了DPeak算法難以準確定位聚類中心、分類困難等缺陷.然后，通過選擇冗余子任務的中心，測量子任務集的相似性，定義粒度規則，從而生成幾個多粒度任務求解空間.最后，根據實際問題來進行粒度優化，得到最優層來解決相應問題.該算法的時間復雜度為O(n2)+O(n)+O(st)，其中s為初始可取的冗余初始中心的任務數，t為自動算法終止的循環指標.

要獲得正確聚類，DPeak算法存在一個隱藏要求:數據集中的每個簇必須有且僅有一個密度峰值，否則DPeak將拆分為多個簇.當一個簇中有多個密度峰值，即“無峰值”時，此時的聚類效果并不好.為解決上述情況，Zhang等人[49]提出了E-CFSFDP(an extension of clustering by fast search and find of density peaks).該算法借鑒CHAMELEON[65]算法，根據數據點創建KNN圖使得圖分割成子類，然后合并子集.E_CFSFDP選擇盡可能多的簇中心，以克服DPeak僅在數據集的每個簇具有唯一密度峰值時表現良好的不足.類似地，Chen 等人[48]認為在可聚類成不同簇的數據中，每一個簇由一個核心區確定，而非一個峰值點所能代表，這個核心區是由多個緊密相連的高密度點構成.基于這一思路提出了DCore(decentralized clustering by finding loose and distributed density cores)算法，通過與mean shift近似的漂移方法找出若干局部密度中心點，對這些中心點先完成聚類，再按漂移過程中形成的層次結構對其他數據點指派類別.如圖5所示，紅色點即為所謂的核心區，每一個紅色數據點實際上都是一個局部密度中心點，它直接決定了一個簇的形狀與分布區域.藍色線條表示數據點的漂移軌跡，綠色點表示“假峰值點”.基于DCore思路,Xie等人[66]提出了DCNaN(a clustering algorithm based on the density core and the natural neighbor)算法，利用天然鄰居(natural neighbors)完成實現dc動態化.

Fig. 5 The density cores and shift stream of DCore[48]圖5 DCore 的密度核心區與數據漂移[48]

影響DPeak聚類精度的情況通常有：產生“假峰”、“無峰值”、簇丟失及多米諾骨牌效應等.不難發現這些現象均由dc或簇中心選取不當或不規則的數據分布所產生，因此如何最優選擇這2個參數，使其滿足合適的數據集仍是DPeak研究的一個難點和熱點.

3.4 高維數據處理

隨著大數據時代的到來，數據維數越來越高，歐氏距離度量在高維數據中變得沒有意義，基于距離計算的聚類效果也越來越差.如何有效處理高維數據已經成為一個亟待解決的難題.

Xu等人[34]提出了DenPEHC(density peak based hierarchical clustering method)引入網格粒度框架，使DenPEHC能夠聚類大規模和高維的數據集，具有很好的魯棒性、精確度和效率.Du等人[50]提出了DPC-KNN(a density peaks clustering based on KNN)，它將KNN的思想引入DPeak，提出了一種局部密度計算的方法，其算法復雜度為O(n2).為了克服在高維數據上表現不佳的問題，該文將主成分分析(principal component analysis， PCA)引入到DPC-KNN模型中，并進一步提出了DPC-KNN-PCA(DPC-KNN based on PCA).該算法的時間復雜度為O(M3+M2n+n2)，其中M為每個點的特征個數.DPC-KNN-PCA不僅具有良好的可行性，而且在聚類性能上優于經典的聚類算法(k-means和spectral clustering)和DPC算法.在低維數據集中，DPC-KNN的性能優于其他算法.在相對高維的數據集中，DPC-KNN-PCA取得了令人滿意的結果.但是當數據集呈現垂直條紋時，這2個算法的聚類效果均不佳.另外，Xu等人[52]通過實驗報告了基于Grid技術DPCG算法也具有較好的高維數據處理能力.FastDPeak[37]的實驗中也表明在較高維數據集KDD04(77維)與BigCross(57維)上取得較好效果.

目前針對高維數據進行改進的DPeak算法較少，效果還不是太令人滿意.這類問題需要針對具體應用場景選擇合適的降維算法來解決，如PCA、網格粒度框架、LDA[67]、流形學習[68-69]等，還有待進一步的研究.

3.5 主要改進算法匯總

表4匯總了DPeak的主要改進算法，通過對比不難發現：

1) DPeak的速度主要依靠KNN[28,37,50,61-62]算法、網格法[51-52]以及并行化[56]思想來提升.

2) DPeak的參數自動化研究主要通過密度估計[35,61]、自動計算參數dc[62]或通過KNN避開參數dc[37,61](但同時有可能帶來新參數k的選擇問題)、選擇聚類中心[29,35,62]來實現的.

Table 4 Comparisons of Improved DPeak Algorithms表4 DPeak的相關改進算法

Note: √ means “yes”; × means “No”.

3) 對于處理高維數據的改進方法中，目前主要以網格法[34,52]與PCA降維[50]，但效果不是很好.

4) 此外，許多聚類算法使用模糊聚類[28,70-73]的方法來提升DPeak的魯棒性.

4 DPeak算法的應用

雖然DPeak算法仍比較年輕，但具有過程較為簡單、效果好等優勢，已廣泛應用于各個領域，例如：圖像處理[74-76]、工業[77-79]、計算機[80-83]、生物醫學[84-86]、光學[87-89]及其他方面[90-92]等.下文將對其中3個主要的應用領域展開簡要介紹.

4.1 自然語言處理應用

近年來，交互可視化技術在分析文本文檔方面的發展勢頭十分迅猛.然而，要對一篇文檔進行抽象，并在相關的已作好標注的文檔空間中進行檢索仍然是個難題.面對這一問題，Heimerl等人[82]將DPeak算法用在高維空間中來估計給定文檔集的最佳簇數，并且基于數據的密度結構將其他所有文檔分配給其中一個峰值.但是DPeak在高維空間中的計算速度并不理想，存在速度較慢的問題.

多文檔新聞摘要(MDNS)的目的是在保留原始新聞文檔集的主要特征的同時，創建了一個濃縮的摘要.人們普遍認為，一個好的MDNS方法應該適當地考慮相關性和多樣性.大多數MDNS方法都專注于其中一方面的研究，而Wang等人[83]提出的句子評分法綜合考慮了相關性、多樣性和長度約束.該方法用DPeak來度量句子層次的相關性和多樣性，選擇代表性較強的句子，生成冗余較少的摘要，保證了多文檔新聞摘要的多樣性和長度約束.但是，如果出現多個峰值的情況時，就會出現關鍵句子冗余的情況.

4.2 生物醫學應用

通過計算機輔助折疊生物分子(特別是RNA)是計算結構生物學中最困難的難題之一.Kuhrova等人[84]引入了DPeak提出了一種新的算法，可以確定哪些分子力場破壞了折疊結構[93].造血干細胞(hematopoietic stem cell， HSC)出現在胚胎發育中的主動脈，目前已經可以通過移植的方法估計出HSC克隆的數量，但是在天然環境中生成的HSC的數量估計仍然具有挑戰性.為解決這一挑戰，在Henninger等人[85]所采用的方法中，使用DPeak聚類方法測量顏色空間中每個細胞的密度以及每個細胞距離密度更高細胞的距離，并繪制可以揭示聚類中心的結果圖.對大量歷史數據集進行分析可以得出疾病癥狀群.Chen等人[86]基于這2點，并根據目前疾病的階段，向醫生和患者推薦有價值的疾病診斷和治療方案.該文作者采用DPeak來識別疾病癥狀，再采用Apriori算法進行關聯分析，但是該方法對先驗知識的要求較高.

4.3 光學應用

利用高光譜傳感器在同一時刻對同一空間區域進行成像，獲得的高光譜圖像通常包含數百個波段圖像，這為精確分析和識別地面物體提供了可能.然而，由于在實踐中難以獲得足夠的標記訓練樣本，大量光譜帶可能導致“維數災難”.Jia等人[87]將DPeak算法進行改進，使其適用于高光譜波段選擇.該方法不僅可以保證所選頻帶子集的穩定性，而且可以避免聚類過程中參數調優困難這一問題.Sun等人[88]基于DPeak算法中的2個假設，提出了一種新的波段選擇方法(exemplar component analysis，ECA).ECA可以過濾掉許多噪聲數據，這增加了其精度.此外，采用排名方法避免了子集的搜索過程，大大減少了計算量.Mai等人[89]提出了一種基于DPeak的相干光接收機技術，在改進后的DPeak中引入一個更適合于信號Stokes空間分布的新參數，從而達到了更好的分類效果且算法復雜度適中.

4.4 其他應用

預測“暗物質暈”的結構性質是現代宇宙學的基本目標之一.Klypin等人[90]采用MultiDark宇宙模擬來研究“暗物質暈”密度分布、濃度和速度各向異性的演化.該方法通過對密度峰值的研究證明了暈的演化經歷了3個階段且預測精度高.

智能手機已經成為每個人的不可或缺的一部分，越來越多的基于位置的內置應用程序可以豐富著我們的日常生活.Wang等人[91]提出了一種新的室內分區定位方案，采用DPeak算法將“指紋眾包”聚類到不同的子區域，定位精度可以達到95%.

道路交通網絡規模迅速擴大，復雜性日益增加.為了簡化分析，保持交通順暢，可以將大型城市公路網看作是一組小的子網絡.Anwar等人[92]提出了一個基于DPeak算法的交通措施的大型城市道路網絡空間劃分框架，可將路況圖轉化為結構良好的壓縮密度峰值圖.在此基礎上，將基于譜理論的圖割應用于密度峰值圖的劃分，可得到不同的子網.

5 總結與展望

DPeak是目前最受關注的聚類算法之一，其算法思想簡單且能夠識別不同形狀的簇，它的提出具有非常重要的理論和實際意義.該算法可以劃歸為層次聚類、密度聚類和代表點聚類，是一種混合型聚類算法.在對DPeak與經典的5種聚類算法進行詳細比較后，我們發現DPeak算法和mean shift算法存在許多相似之處.兩者最大的區別在于DPeak的漂移步長是跳躍的，而mean shift則是影子梯度上升法.

DPeak算法可以將不同維度和形狀的數據進行聚類，但是該算法的復雜度高，在處理大規模數據時難以令人滿意.此外，該算法只適用于每個簇的密度較為均勻的數據集.對于特殊形狀的數據集可能會產生“假峰”或簇丟失等現象.目前，已經有大量學者對DPeak展開研究，也提出了許多改進的算法，主要優化方面有：提升速度、過程自適應、提高精度、適應高維數據.但仍然存在許多不足，還需要進一步深入研究，主要有5個方面.

1) 降低算法復雜度

在DPeak算法中，每個數據點都需要做2步計算：①在給定鄰域內計算數據點密度,密度的計算是近鄰搜索問題(RangeQuery)，原始DPeak算法使用暴力法對每個點做RangeQuery的時間復雜度是O(n2).②對每個數據點尋找比其密度更高的最近鄰,但原始DPeak算法仍然使用暴力法尋找每個點的密度更高的最近鄰，其復雜度也是O(n2).

我們認為：①計算數據點密度與搜索近鄰相關性很大，利用快速KNN算法如FLANN(fast library for approximate nearest neighbors)[94]，cover tree[95]，DCI(dynamic continuous indexing)[96]，semi-convex hull tree[97]， buffer kd tree[98]， revised kd tree[99]，可以有效地提升密度計算效率[37,49,100].②由于各個數據點之間的密度計算是相互獨立的，因而利用GPU并行化DPeak算法是一個可行之道.可以通過高性能硬件，實現成倍提升計算速度，但還需在數據調度策略上做有針對性的設計.③此外，因為數據分布具有局部性的特點，即局部區域密度大，采用分布式方法對數據分區進行處理也是一種可行的方法.但是分布式環境復雜(如復雜不平衡、同步障礙、網絡擁塞等)會影響聚類的精度[56]，因此分布式方法中對參數的合理選取變得尤為重要.

目前，已經有學者在這方面做出了有意義的嘗試與貢獻.如前文所述，FastDPeak[37]通過快速KNN算法來加速密度和δ值計算，但k值不能取太大，對高維數據(如100維以上)效果不好，EDDPC[57]和LSH-DDP[56]則通過分布式方法來加速；Li等人[56]通過GPU來加速DPeak等.總的來說這些算法改進 DPeak手段比較單一，還有較大提升的空間，可以從上述3方面綜合改進.

2) 過程自動化

隨著數據量爆炸性增長，對數據處理的自動化要求成了必然趨勢.DPeak的自動化實現存在2點挑戰：自動確定簇數目和參數的自適應.首先，現有的大多數對于DPeak的自動化方面的改進算法只能做到給定簇的數目之后，進行自動聚類.然而簇的數目是通過人工來確定的，并非自動確定的，因此不能算是完全意義上的自動聚類.例如：Hou等人[61]提出了一種新的局部密度估計方法，該方法可以在給定簇的數量且沒有人為干預的情況下完成聚類過程并改善聚類結果.其次，自動化的關鍵技術是要實現自適應的聚類.例如，Wang等人[35]提出了一種自適應密度峰值檢測的聚類方法，該算法可以自動選擇聚類中心.Hou等人[101]提出了將支配集和密度聚類相結合的方法，使得密度聚類無需提前輸入參數.基于上述研究現狀，將來可以從自動確定簇的數目和自適應的選擇聚類中心、dc以及無參數輸入方面來改進DPeak算法.

3) 提升精度和魯棒性

在大數據時代，數據量激增、數據呈現豐富的多樣性.不同的數據集適用于不同的算法，如何提升DPeak與數據集的匹配度已經成了當下的研究熱門.DPeak算法由于其算法本身的固有性質導致其無法識別“假峰”現象，且對“無峰值”現象聚類效果差.此外，dc選取不當還會導致簇的丟失或簇過大，這些都是影響DPeak算法精度的因素.現有的密度峰值聚類算法更傾向于選擇密集區域的聚類中心，從而容易忽略稀疏區域的聚類[102].如何將稀疏簇正確地檢測出來，而不是將其合并到其他簇中，或者被當作噪聲處理，這一問題還有待進一步的研究.改善上述這些問題也是DPeak未來研究的一個重要方向.

4) 高維數據處理

現有算法對于處理高維數據的表現仍不夠理想.DPeak雖然可以把高維數據映射成2維，再在2維上完成聚類.但在映射過程仍然是基于距離計算完成的，而這恰恰是處理高維數據的弱點.因為高維數據往往是稀疏的，要在高維空間中選擇一個合適的參數dc來計算密度是非常困難的.

現有算法對于處理高維數據的表現仍不夠理想.面對“維度災難”問題，對數據進行降維是一種有效可行的方法，如PCA在一定程度上揭示了高維數據的低維表達.此外，流形學習[68-69]是處理高維數據的有效手段.流形學習基于高維觀測數據采樣于一個潛在的低維流形上的假設，根據顯式或隱式的映射關系學習出該假設中存在的流形，并將原始數據從觀測空間投影到嵌入空間，在嵌入空間內保持原始數據的某些幾何屬性和內在結構.目前流形學習已經應用在了一些聚類算法的改進上[103]，如Cai等人[104]針對流形特性提出了快速高性能的聚類新模式，構建了基于流形對高維數據進行低維表達與學習的理論體系.目前，DPeak對高維數據處理方面只出現了基于PCA的改進方法[50]，基于流形學習的改進方式還未出現.

5) 與其他聚類的內在關系

對目前已有聚類算法的觀測與分析，可以發現DPeak與mean shift比較相近.特別地，DPeak根據峰值進行漂移的方式，可以看成是一種變步長的梯度上升法.正如k-means可以歸類為一種殊的mean shift一樣[22]，我們認為DPeak也可能是一種特定的means shift算法，或者至少是mean shift的一個非嚴格意義上的變種.DPeak是否可以在mean shift框架下進行解釋還不能確定.因而，DPeak是否可以歸類為mean shift算法族還有待進一步探索.