密度峰值聚類算法綜述

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

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

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

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

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

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

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

1 DPeak聚類算法的原理

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

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

(1)

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

(2)

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

(3)

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

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

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

2 DPeak與其他算法的比較

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

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

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

1) 層次聚類

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

Xu等人[36]提出了前導(dǎo)樹的概念，除了根節(jié)點外，每個節(jié)點都是由其父節(jié)點引導(dǎo)加入同一個簇中的，即每個點的上一層節(jié)點是與其距離最近且密度更高的點，而整個數(shù)據(jù)集中密度最高的點是根節(jié)點.按前導(dǎo)樹規(guī)則，DPeak算法生成的聚類結(jié)構(gòu)實際上是一棵樹狀的層次結(jié)構(gòu)，如圖2所示.圖2(a)是數(shù)據(jù)分布圖；圖2(b)是根據(jù)圖2(a)畫出來的樹；圖2(c)是假設(shè)簇數(shù)為3時，所生成的森林.點5是密度最大的點因此也是樹的根節(jié)點.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算法的層次結(jié)構(gòu)

2) 代表點聚類

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

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

3) 密度聚類

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

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

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

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

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

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

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

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

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

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

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

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

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

以圖3為例，圖3(a)中局部峰值中心點有2和6，嚴格來說點2應(yīng)該向點6繼續(xù)漂移，如虛線箭頭方向所示.若以局部峰值中心點為聚類中心，則該圖可聚成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計算過程中，數(shù)據(jù)集S本身固定不變，是一個非模糊過程(non-blurring process)[21].在起始階段，DPeak把所有數(shù)據(jù)點都看成是臨時中心，并為每一個點迭代尋找最終中心.只不過在迭代程中有許多路徑是重疊或重復(fù)的，可以省略，使DPeak看起來顯得不用迭代，其復(fù)雜度相比mean shift較低.以圖2(b)為例，對于數(shù)據(jù)點17而言，對其做完整迭代的路徑是：17→8→12→20→5；對于數(shù)據(jù)點8而言，其路徑則為：8→12→20→5，2條路徑是交叉重疊的.因而，若數(shù)據(jù)點17的漂移路徑計算完成后，點8的迭代過程可以省略，數(shù)據(jù)點12，20類似.

3 DPeak算法的優(yōu)化

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

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

2) 過程不是自適應(yīng)的.不能自動調(diào)整內(nèi)在參數(shù).例如，不能自適應(yīng)選擇密度峰值與dc.

3) 精度易受影響.DPeak在計算局部密度時，如果沒有考慮到數(shù)據(jù)的局部結(jié)構(gòu)會導(dǎo)致許多簇的丟失、“假峰”[47-48]和“無峰值”[49]現(xiàn)象從而影響聚類的精度.

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

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

3.1 提升速度

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

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

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

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

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

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

為提升DPeak的效率和可擴展性，鞏樹鳳等人[57]提出了EDDPC(efficient distributed density peak clustering).該算法選擇Voronoi分割所需要的種子，再用2個完整的MapReduce[58]作業(yè)分別計算ρ與δ值.首先，將數(shù)據(jù)分組并獨立并行地處理各分組中的數(shù)據(jù)對象，在各分組內(nèi)局部計算ρ值和δ值，以克服計算所有對象間的距離所造成的大量開銷.該文作者給出了1個數(shù)據(jù)對象復(fù)制模型和2個數(shù)據(jù)對象過濾模型，將部分其他分組內(nèi)的必要對象復(fù)制到本分組內(nèi)來確保數(shù)據(jù)獨立并行執(zhí)行.此外，該文作者對比EDDPC和SDDPC(simple distributed density peak clustering)[57]后發(fā)現(xiàn)，EDDPC的運行速度明顯小于SDDPC.值得注意的是，DPeak在單片機上運行數(shù)據(jù)量小的情況下運行時間優(yōu)于SDDPC，但是在運行大規(guī)模數(shù)據(jù)時會出現(xiàn)內(nèi)存溢出的現(xiàn)象.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)對輸入數(shù)據(jù)進行分區(qū)，以便近鄰點更有可能被分配到同一個分區(qū)，基于LSH的算法在每個分區(qū)內(nèi)執(zhí)行本地計算，然后聚合結(jié)果，得到最終的近似結(jié)果.該方法與EDDPC的聚類效果相似且速度是EDDPC的2倍，是Basic-DDP的1.7倍到70倍.

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

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

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

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

3.2 參數(shù)自適應(yīng)化

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

(4)

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

(5)

(6)

(7)

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

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

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

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

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

3.3 改進聚類精度和魯棒性

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

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

(8)

(9)

(10)

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

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

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

Fig. 5 The density cores and shift stream of DCore[48]圖5 DCore 的密度核心區(qū)與數(shù)據(jù)漂移[48]

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

3.4 高維數(shù)據(jù)處理

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

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

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

3.5 主要改進算法匯總

表4匯總了DPeak的主要改進算法，通過對比不難發(fā)現(xiàn)：

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

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

Table 4 Comparisons of Improved DPeak Algorithms表4 DPeak的相關(guān)改進算法

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

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

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

4 DPeak算法的應(yīng)用

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

4.1 自然語言處理應(yīng)用

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

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

4.2 生物醫(yī)學(xué)應(yīng)用

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

4.3 光學(xué)應(yīng)用

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

4.4 其他應(yīng)用

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

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

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

5 總結(jié)與展望

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

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

1) 降低算法復(fù)雜度

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

我們認為：①計算數(shù)據(jù)點密度與搜索近鄰相關(guān)性很大，利用快速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].②由于各個數(shù)據(jù)點之間的密度計算是相互獨立的，因而利用GPU并行化DPeak算法是一個可行之道.可以通過高性能硬件，實現(xiàn)成倍提升計算速度，但還需在數(shù)據(jù)調(diào)度策略上做有針對性的設(shè)計.③此外，因為數(shù)據(jù)分布具有局部性的特點，即局部區(qū)域密度大，采用分布式方法對數(shù)據(jù)分區(qū)進行處理也是一種可行的方法.但是分布式環(huán)境復(fù)雜(如復(fù)雜不平衡、同步障礙、網(wǎng)絡(luò)擁塞等)會影響聚類的精度[56]，因此分布式方法中對參數(shù)的合理選取變得尤為重要.

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

2) 過程自動化

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

3) 提升精度和魯棒性

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

4) 高維數(shù)據(jù)處理

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

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

5) 與其他聚類的內(nèi)在關(guān)系

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