k 近鄰密度支配域代表團(tuán)密度峰值聚類算法

呂鴻章，楊易揚(yáng)，，楊戈平，鞏志國

1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006

2.澳門大學(xué) 計(jì)算機(jī)與信息科學(xué)系，澳門 999078

聚類分析是處理數(shù)據(jù)分析發(fā)掘知識的重要手段。其中，密度聚類在應(yīng)對非凸數(shù)據(jù)集時，具有很強(qiáng)的健壯性[1]。利用核密度估計(jì)，可以靈活地發(fā)掘數(shù)據(jù)中任意形狀的簇。從而被廣泛用于計(jì)算機(jī)視覺、目標(biāo)檢測等場景[2]。MeanShift是經(jīng)典的密度聚類算法，它利用密度爬山的策略重塑樣本分布，每個樣本點(diǎn)朝密度增加最大的方向，即核密度加權(quán)均值處移動，直到所有點(diǎn)收斂于局部密度峰值處，最終得到聚類結(jié)果[3]。具有較強(qiáng)的理論基礎(chǔ)和健壯性，但因?yàn)榭紤]了eps帶寬參數(shù)，導(dǎo)致其會出現(xiàn)過少分割和過度分割的情況。此外，該算法不能產(chǎn)生指定簇?cái)?shù)目K的聚類結(jié)果，即不滿足K劃分需求。MeanShift 在樣本量十分龐大時，由于每次移動都需要計(jì)算核密度加權(quán)均值向量，因此會非常耗時[4]。為了避免上述核密度加權(quán)均值點(diǎn)的重復(fù)計(jì)算，Sheikh 等人[5]于2007 年ICCV 上提出Medoidshifts，它將每個數(shù)據(jù)點(diǎn)的移動方向設(shè)定為實(shí)際存在的樣本點(diǎn)，而且沿著該方向密度增加最大，所有這些點(diǎn)組成的有向路徑的終點(diǎn)為實(shí)際存在的局部密度峰值點(diǎn)。最后形成若干棵樹，每棵樹聚成一類。該算法在估計(jì)密度和判別方向時候還是考慮了所有樣本點(diǎn)，不適合大規(guī)模聚類，而且依舊帶有eps參數(shù)的缺陷。Vedaldi 等人[6]在2008 年ECCV 上的QuickShift 算法改進(jìn)了Medoidshifts 減少了計(jì)算樣本點(diǎn)移動方向的負(fù)擔(dān)，它直接考慮tau半徑內(nèi)的樣本點(diǎn)，以tau半徑鄰域內(nèi)最近且密度更大的點(diǎn)為下一個移動方向。該思想也是密度支配思想的運(yùn)用，然而帶寬參數(shù)影響依舊沒有消除。Jiang 等人[7]在ICML 2018 上的QuickShift++使用mutualk-NN圖生成種子簇來替代上述移動路徑的峰值終點(diǎn)，一定程度上解決了過度分割的問題，也具有QuickShift 計(jì)算量較少的優(yōu)點(diǎn)。然而上述所有針對MeanShift的改進(jìn)均未能實(shí)現(xiàn)K劃分。

除了mutualk-NN圖以外，密度支配距離也可以作為解決過度分割的另一途徑，而且實(shí)現(xiàn)方式更簡單。密度峰值聚類DPC算法便是結(jié)合了密度及密度支配距離的聚類算法，它于2014年發(fā)表在Science上。該算法簡潔明了，直接綜合考慮樣本點(diǎn)的密度和密度支配距離快速獲得簇心，再利用支配關(guān)系構(gòu)建的支配樹，從簇心峰值處由上到下實(shí)現(xiàn)聚類[8]。此處密度支配關(guān)系類似上文QuickShift算法，只不過DPC 的考慮范圍涵蓋所有樣本點(diǎn)。密度支配距離使得簇心選擇不易集中，同樣緩解了密度聚類中過度分割的情況。將密度支配距離與各樣本點(diǎn)密度值相結(jié)合，例如直接相乘算子γ值，還可以選擇指定數(shù)目的簇心，從而實(shí)現(xiàn)密度聚類中指定簇?cái)?shù)目K的K劃分聚類。

雖然DPC算法思想簡明且具備許多密度聚類不具有的優(yōu)點(diǎn)。但面對大規(guī)模的樣本數(shù)據(jù)，效率依舊不高，主要體現(xiàn)在為每個點(diǎn)建立支配關(guān)系的過程上[9]。為此，增強(qiáng)DPC 應(yīng)對大規(guī)模聚類能力具有很大意義，許多研究人員對此問題提出了不少方案。有的工作集中在使用大數(shù)據(jù)框架進(jìn)行改進(jìn)[10]，有的則使用空間劃分索引樹的方式來簡化核密度估計(jì)和參數(shù)調(diào)整[11]，有的則使用小團(tuán)簇劃分和代表點(diǎn)的方式減少聚類任務(wù)負(fù)載，從而實(shí)現(xiàn)加速的效果[12-13]。其中以小團(tuán)簇代表點(diǎn)來增強(qiáng)的方式是近幾年解決此類問題的常用思路。

2019 年Zheng 等人提出的QuickDSC（clustering by quick density subgraph estimation）則使用mutualk-NN的方式構(gòu)建小團(tuán)簇，以小團(tuán)簇密度峰值點(diǎn)作為代表點(diǎn)，最后參照DPC的思路利用關(guān)鍵小團(tuán)簇代表點(diǎn)間的支配關(guān)系合并小團(tuán)簇，從而完成聚類[12]。不僅有效地改進(jìn)了QuickShift++不能實(shí)現(xiàn)指定數(shù)目K的聚類的缺陷，還極大地提高了DPC 的速度。與QuickDSC 類似，2022 年ECML PKDD 上的FastDEC（clustering by fast dominance estimation）算法首次提出k-NN 密度支配域小團(tuán)簇生成方式，并將此運(yùn)用至DPC 的改進(jìn)中。相比較依靠mutualk-NN連通性生成小團(tuán)簇，它直接使用k-NN范圍內(nèi)的密度支配規(guī)則生成密度支配域作為小團(tuán)簇，將團(tuán)簇內(nèi)密度峰值點(diǎn)作為代表點(diǎn)。因此，F(xiàn)astDEC只關(guān)注各支配域代表點(diǎn)，以點(diǎn)代面執(zhí)行DPC 完成聚類。這使得DPC的效率得到進(jìn)一步提高。此外，k-NN密度支配域的并集涵蓋所有樣本點(diǎn)，省去了考慮偏僻樣本點(diǎn)的時間，產(chǎn)生團(tuán)簇的方式也更直接[13]。

k-NN 密度支配域的改進(jìn)策略其效果雖然顯著，但存在代表點(diǎn)代表能力不足的問題。在密度支配域規(guī)模較小時，單個峰值代表點(diǎn)有能力代表整個支配域進(jìn)行聚類，但密度支配域過大時，支配域的形狀也會任意變動，此時僅僅一個代表點(diǎn)不足以代表整個支配域，導(dǎo)致聚類出現(xiàn)錯誤。因此，增加代表點(diǎn)，從密度支配域中采樣少量代表團(tuán)可以作為解決這個問題的一個思路。然而，僅僅是隨機(jī)采樣依舊不能保證選出來的代表可以具有代表性。因此，可以參考KMeans++的初始化思路來優(yōu)化代表團(tuán)的產(chǎn)生過程[14]。這樣產(chǎn)生的代表團(tuán)能夠更好地反映一個團(tuán)簇的分布狀況。由于各支配域的代表從單個代表點(diǎn)變成了代表團(tuán)，密度支配域間的距離衡量也是一個挑戰(zhàn)。對此，采用高斯核加權(quán)平均的方式計(jì)算兩兩支配域間的距離也是可供考慮的解決方案。解決了支配域距離衡量的問題，DPC 算法便可以繼續(xù)執(zhí)行，盡管相比較FastDEC減少了一些效率，但依舊可以應(yīng)付大規(guī)模聚類問題，更關(guān)鍵是聚類質(zhì)量得到了保證，這便是新的密度聚類算法DWG-DPC（delegations weighted-Gaussian similarities based density peaks clustering）。

綜上，密度聚類具有很好的健壯性，DPC 算法是密度算法中支持K劃分需求的算法，但不適合大規(guī)模數(shù)據(jù)集聚類。k-NN 密度支配域小團(tuán)簇加速是解決該問題的一個思路，但面臨代表代表能力點(diǎn)不足的缺陷。新算法DWG-DPC采用密度支配域團(tuán)簇生成方式，以代表團(tuán)策略改進(jìn)了k-NN 密度支配域代表點(diǎn)代表能力不足的缺陷，它繼承了密度支配域的高效優(yōu)點(diǎn)和DPC 的聚類特性。為了使代表團(tuán)的代表能力更強(qiáng)，借助KMeans++的初始化方式進(jìn)行采樣優(yōu)化。針對域間距離的度量問題，提出了一種以近鄰關(guān)系為主的高斯核域間加權(quán)距離計(jì)算方式。DWG-DPC 在繼承密度支配域小團(tuán)簇策略快速聚類優(yōu)點(diǎn)的同時，也保證了聚類質(zhì)量，更滿足指定數(shù)目為K的聚類需求。對聚類分析工作具有一定的實(shí)用性。

1 預(yù)備知識

本章主要介紹密度支配，小團(tuán)簇代表點(diǎn)聚類加速技巧和密度支配域。為方便介紹上述概念，先規(guī)定如下符號。算法的輸入數(shù)據(jù)集為X∈?n×m特征矩陣。樣本個數(shù)為n，任意樣本xi∈X,xi∈?m。小寫k代表近鄰數(shù)，大寫K代表聚類簇?cái)?shù)。Ti表示密度支配域或密度支配樹。TS={Ti}表示密度支配域集合或密度支配森林。sub表示各對象的密度支配從屬關(guān)系，sub(xi)=xj表示xi的上級密度支配點(diǎn)為xj。N(xi)表示xi的近鄰節(jié)點(diǎn)集，根據(jù)衡量方式的不同有k近鄰Nk(xi)和r半徑近鄰Nr(xi)。dist(xi,xj)表示xi與xj的距離，通常是歐氏距離‖xi-xj‖。δi表示xi的密度支配距離。kde(xi)為核密度估計(jì)函數(shù)用于估計(jì)點(diǎn)xi的密度ρi，核密度估計(jì)可選擇平核、高斯核等[15]，如公式（1）、（2）所示：

密度支配的概念源于DPC 算法，它將離樣本點(diǎn)xi最近且密度比xi更大的點(diǎn)作為上級密度支配點(diǎn)。該算法的思想是通過綜合考慮每個點(diǎn)的密度ρi和密度支配距離δi快速得到簇中心，最后利用全域密度支配關(guān)系由上到下傳播類標(biāo)簽完成聚類。FastDEC 繼承了該思想，它將支配關(guān)系由全域X拓展到k近鄰Nk(xi)下。此時，全域的密度支配范圍X則是k=n時的特殊情況。如不考慮具體的近鄰衡量方式，則密度支配規(guī)則可描述為[8，13]：

定義1（密度支配）對?xi∈X,如果?xj∈X,xj=,則稱xi被xj密度支配或xj密度支配xi,點(diǎn)xj稱為xi的上級密度支配點(diǎn)，記作sub(xi)=xj。否則，xi為全局密度峰值點(diǎn),sub(xi)=xi。

在DPC中，對于全局密度峰值點(diǎn)，它的密度支配距離設(shè)置為已有δ值的最大值，以保證該點(diǎn)能入選為簇心。除此之外，δi=dist(xi,sub(xi))。由于每個點(diǎn)要么沒有密度支配上級，即全局密度峰值點(diǎn)，要么只有一個密度支配上級，由此而形成了樹狀密度支配關(guān)系。

利用代表點(diǎn)的處理結(jié)果粗略得到整體的運(yùn)行結(jié)果是應(yīng)對大規(guī)模聚類的實(shí)用技巧，如mini batch Kmeans中的小批次樣本點(diǎn)[16]。LSC（landmark-based spectral clustering）算法中的Landmark代表點(diǎn)[17]。小團(tuán)簇合并加速聚類屬于其中一種，核心思想是將樣本集分為p個互不相交的小團(tuán)簇，p?n。每個團(tuán)簇選出一個代表點(diǎn)，通過聚類少部分代表點(diǎn)來實(shí)現(xiàn)所有樣本點(diǎn)的聚類。從而提升一些聚類算法應(yīng)對大規(guī)模聚類的能力。不同于原始的代表點(diǎn)思路，小團(tuán)簇合并加速技術(shù)需要先構(gòu)建小團(tuán)簇，然后再從中得到代表點(diǎn)。

已有的小團(tuán)簇生成方式有如Quickshift++中的mutualk-NN mode 生成方式，F(xiàn)astDEC 中k-NN 密度支配域生成方式。前者需要在建立k-NN 的基礎(chǔ)上遍歷探尋mutualk-NN，之后還得歸類未在mutualk-NN中的邊緣樣本點(diǎn)。后者在k-NN 圖的基礎(chǔ)上直接使用密度支配規(guī)則形成支配域。由于k-NN的限制，原始的DPC密度支配關(guān)系樹就劃分成若干棵小樹，成為密度支配森林。其中，每棵小樹即為一個支配域。令sub(x)w表示x的w階上級密度支配點(diǎn)，即在密度支配關(guān)系樹上對x連續(xù)求w次父節(jié)點(diǎn)，0

定義2（密度支配域）對于非空集合Tj?X而言，如果?w和yj∈Tj使得sub(xi)w=yj對?xi∈Tj都成立，則Tj是以yj為峰值點(diǎn)的密度支配域。

k-NN 密度支配域代表點(diǎn)技巧在極大提升DPC 速度的同時也存在峰值代表點(diǎn)代表能力不足的問題。在團(tuán)簇規(guī)模小的時候，單個密度峰值點(diǎn)的代表性尚可，但在小團(tuán)簇規(guī)模大時，團(tuán)簇?cái)?shù)據(jù)分布的凹凸性和不規(guī)則性會削弱峰值點(diǎn)的代表能力，從而引起錯誤聚類。新提出的支配域代表團(tuán)策略則是對上述問題的改進(jìn)。如圖1所示，從左到右代表兩者不同的劃分方式。圖1（a）表示A，B 和C 三個小團(tuán)簇初始分布。圖1（b）是僅考慮局部密度峰值的情況，圖1（c）是理想的合并結(jié)果。由于A和C的局部密度峰值代表點(diǎn)更近，因此只考慮峰值代表點(diǎn)就有可能會出現(xiàn)圖1（b）的情況，錯誤地合并A和C而不是A和B。

圖1 局部密度峰值點(diǎn)代表能力不足的情況Fig.1 Insufficient representative capacity of local density peaks

2 算法介紹

針對上文局部密度峰值點(diǎn)代表能力不足的情況，選取更多的代表點(diǎn)組成區(qū)域代表團(tuán)是解決問題的途徑之一。但代表團(tuán)成員的選擇方式同樣決定著其代表能力的大小。構(gòu)成代表團(tuán)后，各區(qū)域間的距離衡量也是需要解決的問題。為方便描述，先給出如下符號定義。設(shè)代表團(tuán)規(guī)模為rep，高密度候選點(diǎn)占代表團(tuán)規(guī)模比例為α，低密度邊緣候選點(diǎn)估計(jì)數(shù)為Out，密度支配域（小團(tuán)簇）Ti規(guī)模為|Ti|。

2.1 密度支配域代表團(tuán)

從密度支配域（小團(tuán)簇）中采樣代表團(tuán)，首先需要先確定采樣區(qū)。高密度點(diǎn)處在本區(qū)域內(nèi)樣本分布密集的地方，這些高密度點(diǎn)對周邊樣本點(diǎn)具有一定的代表能力，所以代表團(tuán)采樣需要考慮高密度成員。其次，對圖1（b）中的錯誤合并方式而言，如果代表點(diǎn)能夠反映支配域的空間分布輪廓并將其考慮進(jìn)合并規(guī)則，那么上述錯誤發(fā)生的幾率會減少很多。因此，可以考慮在支配域的周邊采樣部分代表點(diǎn)。而支配域周邊的密度通常比較低，所以可以從低密度區(qū)進(jìn)行采樣。這樣，采樣區(qū)可以確定為高密度候選區(qū)和低密度候選區(qū)。

之后就是確定上述采樣區(qū)的分界，對于一個有序密度序列，如密度降序序列，僅需確定一個低密度區(qū)點(diǎn)數(shù)Out即可進(jìn)行高低密度區(qū)域劃分。對于密度降序序列，密度最小的后Out個樣本作為低密度候選區(qū)。而對于密度升序序列，則是前Out個樣本作為低密度候選區(qū)。雖然支配域分布形狀是任意的無法給出統(tǒng)一的衡量標(biāo)準(zhǔn)，但是在操作上可以假定一個較為理想的分布情況進(jìn)行估計(jì)。這里給出類似均勻分布的其中d維超正方體分布估計(jì)方案。該方案假設(shè)所有團(tuán)簇Ti以d維超立方體的形式排列，中心部分密度一樣，邊緣部分密度較低。選擇它的一個原因是計(jì)算上比較方便。這樣最外層的低密度邊緣點(diǎn)估計(jì)數(shù)Out可由公式（3）給出：

證明公式（3）證明如下：

∵對長度為(l-2)的d維超正方體Ql-2而言，它的樣本點(diǎn)數(shù)為|Ql-2|=(l-2)d。

又∵在Ql-2的最外層再增加一層點(diǎn)，數(shù)目為Out，使其變成長度為l的d維超正方體Ql，則樣本點(diǎn)數(shù)為|Ql|=ld。

∴Out=|Ql|-|Ql-2|。利用l將|Ql-2|用|Ql|表示即可得到，證畢。

注意公式（3）的前提條件，如果|Ti|≤2d則表明支配域太小，無需進(jìn)行采樣，全員參與代表團(tuán)。只有|Ti|>2d后Out才有值。在DWG-DPC中，Out存在時則需要判斷所需低密度代表團(tuán)規(guī)模rep-int(rep?α)與Out的關(guān)系。rep-int(rep?α)

至于高密度代表團(tuán)，則直接中選擇選密度最大的int(rep?α)個點(diǎn)。這兩次選擇可能存在非空交集，因此需要做并集操作。從而形成支配域代表團(tuán)，上述過程如圖2所示。

圖2 在支配域A中采樣代表團(tuán)Fig.2 Sampling delegation in dominator component A

為了保證低密度代表點(diǎn)能夠盡可能均勻分布在小團(tuán)簇邊緣處，描述其分布狀況。算法采用KMeans++的采樣思路，即每次從低密度采樣區(qū)中不放回地選擇距離已有樣本點(diǎn)集均值最遠(yuǎn)的一個，使得選擇的樣本點(diǎn)盡可能分散。需要再次說明，采樣能夠進(jìn)行的前提是，低密度采樣區(qū)足夠大，即rep-int(rep?α)

算法1SampleDelegates

輸入：支配域Ti，代表團(tuán)規(guī)模rep，低密度比例α，樣本點(diǎn)密度ρ。

輸出：代表團(tuán)Mi。

步驟1根據(jù)公式（3）計(jì)算邊緣低密度估計(jì)數(shù)Out。令high=int(rep?α),low=rep-high。

步驟2對Ti的每個點(diǎn)，從ρ中獲取各點(diǎn)密度并將樣本按密度降序排列，用dt表示。

步驟3判斷|Ti|與2d的大小關(guān)系。如果|Ti|≤2d則進(jìn)入步驟9；否則，判斷l(xiāng)ow與Out之間的大小。如果low

步驟4取dt最后面Out個點(diǎn)作為低密度候選區(qū)，剩余的納入高密度候選區(qū)，初始化集合S1和S2，將低密度候選區(qū)點(diǎn)全部加入S1中，選擇S1中密度最低的點(diǎn)作為v點(diǎn)。

步驟5將v從S1中彈出加入S2中；計(jì)算S2的均值點(diǎn)u；再從S1中選擇距離u最遠(yuǎn)的點(diǎn)作為新的v。

步驟6重復(fù)步驟5直到|S2|=low。跳至步驟8。

步驟7直接將低密度候選區(qū)全部納入S2。

步驟8從高密度候選區(qū)中取密度最大的前high個作為S3。令Mi=S2∪S3。返回Mi，結(jié)束算法。

步驟9直接令Mi=Ti，返回Mi，結(jié)束算法。

2.2 高斯域間相似度

衡量兩個團(tuán)簇間的距離常用的辦法有Jaccard共享近鄰，核函數(shù)相似度加權(quán)或者代表點(diǎn)馬氏距離等[18-19]。前文已說單個代表點(diǎn)雖然可以極大地加快團(tuán)簇距離的衡量，但存在代表能力不足而錯誤聚類的風(fēng)險。因此可以借助少量代表團(tuán)減少上述誤差。雖說馬氏距離同樣可以依靠簇方差進(jìn)行一定程度的增強(qiáng)，但不能很好地反映團(tuán)簇形狀的分布。Jaccard 共享近鄰雖體現(xiàn)了近鄰的本質(zhì)，但權(quán)重統(tǒng)一，未能區(qū)分成員點(diǎn)的遠(yuǎn)近。但如果將近鄰的思想跟核函數(shù)的相似度衡量特性相結(jié)合，則可以同時體現(xiàn)近鄰關(guān)系，也可以體現(xiàn)成員的先后關(guān)系，同時給予不同權(quán)重。因此，借助域間成員近鄰關(guān)系和加權(quán)平均和核函數(shù)這兩個想法，可以導(dǎo)出高斯域間相似度的衡量方式。此處給出方案是近鄰圖鏈入鏈出關(guān)聯(lián)概率作為權(quán)重進(jìn)行高斯核進(jìn)行加權(quán)平均。這種方式特地增強(qiáng)支配域間的較近代表點(diǎn)的距離權(quán)重，還可以使得各簇進(jìn)一步區(qū)分。

令p=|TS|為支配域個數(shù)，代表點(diǎn)集為n′=|MS|,n′?n。對任意兩個支配域Ti與Tj，對MS中每個點(diǎn)建立n′近鄰圖，并將鏈入鏈出數(shù)用鄰接矩陣An′×n′表示。通過n′近鄰圖在域間的相互關(guān)系。其中，任意兩個密度支配域的近鄰關(guān)系如圖3所示。

圖3 域間近鄰關(guān)系Fig.3 Nearest neighbor relationship between dominator component

設(shè)域間關(guān)聯(lián)概率為p(Ti,Tj)，將其作為高斯核加權(quán)權(quán)重，則高斯域間相似度WG(Ti,Tj)可表示成公式（4）。因此，該相似度也可稱為Weighted-Gaussian 相似度，簡稱WG相似度[15]。

由于任意兩個支配域近鄰關(guān)系鏈入鏈出優(yōu)先順序不同，所以此處有三個計(jì)算模式，分別是側(cè)重考慮自身鏈入情況的“in”模式，側(cè)重考慮自身鏈出其他支配域情況的“out”模式，兩者皆考慮的“out-out”模式。結(jié)合鄰接矩陣An′×n′，這三種模式對應(yīng)的WG相似度可由公式（5）表示：

有了相似度，支配域間的距離可通過取倒數(shù)的形式進(jìn)行衡量。設(shè)上述記錄于距離矩陣Dn′×n′中，Ti與Tj之間的距離Dij可由公式（6）得出：

后續(xù)只需要把每個支配域當(dāng)成新的大樣本點(diǎn)，將上述距離當(dāng)成大樣本點(diǎn)的距離即可執(zhí)行傳統(tǒng)DPC 算法。取核密度估計(jì)函數(shù)為kdeG。此時對每個支配域，支配域密度與域間支配距離則分別如公式（7）、（8）所示[8]：

由于n′?n，算法耗時會明顯減少，有力地增強(qiáng)了它在大規(guī)模數(shù)據(jù)集上的聚類能力。

2.3 算法流程

將前文k-NN 密度支配域，支配域代表團(tuán)策略，高斯域間相似度等關(guān)鍵步驟匯總可得新的密度峰值聚類改進(jìn)算法DWG-DPC。該算法關(guān)鍵參數(shù)只有近鄰數(shù)k,k越小，近鄰探尋范圍越小，近鄰支配域劃分越精細(xì)，時間消耗也越大。k越大，近鄰探尋范圍越大，近鄰支配域劃分越粗糙，時間消耗也越少。非關(guān)鍵參數(shù)有rep、α和mode。默認(rèn)情況下rep=30,α=0.2,mode=“out-out”。算法DWG-DPC流程如下：

算法2DWG-DPC

輸入：特征矩陣數(shù)據(jù)集Xn×m，簇?cái)?shù)目K,近鄰數(shù)k。

輸出：簇標(biāo)簽數(shù)組l。

步驟1建立k-NN圖G。根據(jù)公式（2）進(jìn)行核密度估計(jì)，得到所有點(diǎn)的密度ρ。

步驟2利用G和ρ，根據(jù)密度支配規(guī)則，構(gòu)建密度支配域小團(tuán)簇集TS={Ti}。

步驟3對每個密度支配域Ti根據(jù)算法1采樣對應(yīng)代表團(tuán)Mi，組成代表點(diǎn)集MS=∪Mi。

步驟4利用MS代表點(diǎn)的近鄰關(guān)系構(gòu)建各代表點(diǎn)鄰接矩陣A。

步驟5利用公式（5）計(jì)算WG 相似度。再利用公式（6）計(jì)算距離矩陣D。

步驟6利用公式（7）、（8）和密度支配關(guān)系計(jì)算支配域密度數(shù)組與域間支配距離數(shù)組。

步驟7令取最大的前K個支配域作為聚類簇心支配域。

步驟8初始化簇心支配域成員的簇標(biāo)簽，利用域間支配關(guān)系，傳播簇標(biāo)簽，完成聚類。返回簇標(biāo)簽數(shù)組。結(jié)束算法。

上述算法的Python代碼實(shí)現(xiàn)已開源于gitee（https：//gitee.com/lvhzgit/dwg-dpc）和github（https：//github.com/lvhzgit/DWG-DPC）平臺上。算法的流程圖如圖4所示。

圖4 DWG-DPC算法流程圖Fig.4 Flow chart of DWG-DPC

2.4 算法復(fù)雜度分析

步驟1 中k-NN 圖可用kdtree 空間索引算法構(gòu)建，時間復(fù)雜度約為O(nm2+n?lbn)，核密度估計(jì)復(fù)雜度約為O(nkm?lbm+nk?lbn)[20]。步驟2 構(gòu)建密度支配域，每個點(diǎn)掃描近鄰密度狀況，時間復(fù)雜度約為O(nk)。步驟3 代表團(tuán)采樣中，快速排序樣本密度數(shù)組ρ耗時約O(n?lbn)，之后對p=|TS|個支配域采樣代表團(tuán)，耗時約。步驟4構(gòu)建鄰接矩陣耗時約O(n′2)。步驟5到步驟8的時間復(fù)雜度約為O(3p2+p)。由于n′和p遠(yuǎn)小于n。因此，算法整體復(fù)雜度約為O(nm2+n(1+k)?lbn+nkm?lbm+n)。相比較原始的DPC 算法，核密度估計(jì)不需要O(n2m?lbm+n2?lbn)的復(fù)雜度進(jìn)行全局掃描計(jì)算，構(gòu)建密度支配關(guān)系同樣不需要O(n2)的復(fù)雜度進(jìn)行全局掃描。當(dāng)樣本數(shù)據(jù)規(guī)模越大時，DWG-DPC的優(yōu)勢就越明顯。

3 實(shí)驗(yàn)介紹

3.1 實(shí)驗(yàn)準(zhǔn)備

本節(jié)介紹實(shí)驗(yàn)測試，用于描述該算法在聚類中的表現(xiàn)。主要展示本算法與其他9 個密度聚類算法在不同數(shù)據(jù)集上的表現(xiàn)。除了上文的DBSCAN、MeanShift、QuickShift、QuickShift++、QuickDSC、FastDEC 和DPC，還有FINCH[21]和SNN-DPC[22]。FINCH 是層次密度聚類算法，默認(rèn)使用一階近鄰進(jìn)行合并。SNN-DPC 是DPC在合并上的改進(jìn)，使用共享近鄰的方式衡量樣本點(diǎn)間的相似性。上述算法參數(shù)及其設(shè)置如表1所示。

表1 實(shí)驗(yàn)算法Table 1 Algorithms in experiments

數(shù)據(jù)集方面，實(shí)驗(yàn)過程中選取了seed、banknote、segmentation、phonemes、MFCCs 和MNIST 共6 個實(shí)際數(shù)據(jù)集。前5 個是UCI 機(jī)器學(xué)習(xí)公開數(shù)據(jù)集[23]，下載鏈接為https：//archive.ics.uci.edu/ml/datasets.php。后一個MNIST 是規(guī)模較大的手寫數(shù)字?jǐn)?shù)據(jù)集[24]，下載鏈接為http：//yann.lecun.com/exdb/mnist/。另外還有Flame[25]、S2[26]、R15[27]和banana-ball共4個人工數(shù)據(jù)集。前3個可從http：//cs.uef.fi/sipu/datasets/下載，banana-ball 可利用sklearn 工具包，按照Myhre 等人[28]提出的生成方式生成，生成的數(shù)據(jù)下載鏈接為https：//github.com/lvhzgit/DWG-DPC/blob/main/data/banana-ball.csv。這些數(shù)據(jù)集的信息如表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Datasets in experiments

3.2 對比實(shí)驗(yàn)

本部分實(shí)驗(yàn)主要用于對比DWG-DPC 和上文所述9 種密度聚類算法的聚類表現(xiàn)，實(shí)驗(yàn)中聚類的效果使用調(diào)整蘭德指數(shù)（adjusted rand index，ARI），歸一化互信息（normalized mutual information，NMI）和調(diào)整互信息（adjusted mutual information，AMI）三個指標(biāo)進(jìn)行衡量。這三個指標(biāo)越接近1，說明聚類的效果越好。分別令真實(shí)標(biāo)簽向量，預(yù)測標(biāo)簽向量為。由l和可分別導(dǎo)出樣本X的K劃分Π和。由此可得列聯(lián)表如表3所示。

表3 聚類列聯(lián)表Table 3 Cluster contingency table

記max(0,ai+bj-n)=(ai+bj-n)+,根據(jù)表3可得ARI、NMI、AMI指標(biāo)分別如公式（9）～（11）所示[29]：

實(shí)驗(yàn)環(huán)境為64 位操作系統(tǒng)，Python 3.7 解釋器，主要工具包為numpy、sklearn。硬件上，機(jī)器的內(nèi)存64 GB，Intel?Core i7-12700F CPU（2.10 GHz）。對于運(yùn)行時間超6 h 或報內(nèi)存錯誤的情況，其結(jié)果將用“—”替代。實(shí)驗(yàn)結(jié)果如表4～6所示。

表4 實(shí)驗(yàn)結(jié)果中的NMI指標(biāo)Table 4 NMI in experimental results

分析表4 的NMI 指標(biāo)表現(xiàn)可知，表現(xiàn)最好的是QuickShift。該算法在Flame、S2、R15、banana-ball 和banknote 五個數(shù)據(jù)集上均達(dá)到了最高的指標(biāo)值。但對于規(guī)模較大的MFCCs 則表現(xiàn)得相對不強(qiáng)，MNIST 更是無法得出結(jié)果。其次便是QuickShift++、SNN-DPC、FastDEC和DWG-DPC。相比較QuickShift而言，Quick-Shift++在phonemes和MFCCs上取得了最高的NMI值。SNN-DPC則在seeds和segmentation上表現(xiàn)最佳。然而對于規(guī)模最大的MNIST 而言，只有DWG-DPC 表現(xiàn)突出，NMI分?jǐn)?shù)高達(dá)0.734 6。表現(xiàn)最好的QuickShift甚至無法在有限的時間空間內(nèi)運(yùn)行出結(jié)果。DWG-DPC 在其他數(shù)據(jù)集中除phonemes和seeds外，都非常接近最佳指標(biāo)，差距在0.01左右。

對表5 的ARI 指標(biāo)而言，QuickShift、FastDEC 和DWG-DPC 均在5 個數(shù)據(jù)集上表現(xiàn)最優(yōu)。QuickShift 僅在S2有優(yōu)勢，分?jǐn)?shù)為0.941 5。FastDEC則在phonemes上有優(yōu)勢，分?jǐn)?shù)為0.935 9。而DWG-DPC則在segmentation和MNIST 數(shù)據(jù)集上有優(yōu)勢，尤其是MNIST 表現(xiàn)最優(yōu)，高達(dá)0.595 0。其余數(shù)據(jù)集距離最佳ARI 差距大多在0.01到0.08之間。

表5 實(shí)驗(yàn)結(jié)果中的ARI指標(biāo)Table 5 ARI in experimental results

對表6的AMI指標(biāo)而言，其結(jié)果基本與表4的NMI分?jǐn)?shù)相同。表現(xiàn)最好的依舊是QuickShift。表現(xiàn)其次的是QuickShift++、SNN-DPC、FastDEC 和DWG-DPC，有四個數(shù)據(jù)集AMI 指標(biāo)最優(yōu)。但是對于MNIST 數(shù)據(jù)集DWG-DPC依舊保持著突出的表現(xiàn)。DWG-DPC在其余非最優(yōu)的數(shù)據(jù)集上表現(xiàn)，同樣非常接近最優(yōu)AMI分?jǐn)?shù)，差距大多在0.01左右。

表6 實(shí)驗(yàn)結(jié)果中的AMI指標(biāo)Table 6 AMI in experimental results

上述實(shí)驗(yàn)結(jié)果可知，在數(shù)據(jù)規(guī)模不大時，QuickShift算法表現(xiàn)很好，但不適合應(yīng)對大規(guī)模聚類。DWG-DPC雖然從評價指標(biāo)上看，表現(xiàn)并非最好，但應(yīng)對大規(guī)模聚類任務(wù)效果突出。此外，相比較僅使用單個代表點(diǎn)的FastDEC 來說，DWG-DPC 做到了保持大規(guī)模聚類能力的同時改進(jìn)聚類效果。這就證明代表團(tuán)改進(jìn)策略是有效的。當(dāng)然對于原始的DPC而言，提升更是顯著的，首先原始DPC 算法在MNIST 數(shù)據(jù)集上無法得出結(jié)果，但DWG-DPC 不僅可以做到出結(jié)果還可以做到最優(yōu)聚類結(jié)果。其次DWG-DPC 還幫助DPC 在某些數(shù)據(jù)集上提升了聚類質(zhì)量，如對segmentation的聚類NMI從0.331 4提升到0.739 7，ARI 從0.159 2 提升到0.595 1，AMI 從0.328 4提升到0.738 6。

3.3 三種模式下的對比實(shí)驗(yàn)

表4到表6一定程度上證明了DWG-DPC的良好聚類能力以及代表團(tuán)策略的有效性。但公式（5）的三種WG相似度還需要更詳細(xì)的測驗(yàn)。第一，需要確定是哪一種模式幫助代表團(tuán)策略發(fā)揮了作用，第二，需要確定這些計(jì)算模式它們之間在實(shí)驗(yàn)表現(xiàn)中有什么不同。第三，將“out-out”設(shè)計(jì)為默認(rèn)選項(xiàng)是否合理。驗(yàn)證實(shí)驗(yàn)選擇的算法有DPC、QuickDSC、FastDEC，以及三種WG相似度衡量方式下的DWG-DPC。評價指標(biāo)依舊選擇上文中的NMI、ARI和AMI。實(shí)驗(yàn)過程中的參數(shù)設(shè)置和實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)準(zhǔn)備中所述一致。結(jié)果如表7所示。

表7 WG相似度有效性測試結(jié)果Table 7 WG similarities validity verification results

由表7 的實(shí)驗(yàn)結(jié)果可知，聚類結(jié)果最好的指標(biāo)分?jǐn)?shù)大都集中在FastDEC 和DWG-DPC 的三個模式中。FastDEC 的三個指標(biāo)分?jǐn)?shù)在seed 和banknote 上表現(xiàn)得比DWG-DPC 好。但DWG-DPC 的三種模式下的表現(xiàn)在segmentation 與MNIST 上均比FastDEC 更優(yōu)異。尤其是MNIST 部分的提升是非常明顯的，“in”模式下的NMI 由0.679 7 提升到0.734 6，ARI 由0.481 4 提升到0.595 0，AMI由0.679 5提升到0.734 5。“out”和“out-out”模式下的NMI 則提升到0.728 0，ARI 提升到0.588 1，AMI提升到0.727 9。這表明三種WG相似度計(jì)算模式，一定程度上幫助代表團(tuán)策略發(fā)揮了作用，但哪一種影響最大則要視具體數(shù)據(jù)集而定，因此可以作為域間距離的衡量方式。

另外，根據(jù)表7 的DWG-DPC 三種計(jì)算方式下的指標(biāo)分?jǐn)?shù)可知，三種模式效果上幾乎沒什么差別，最大差距也在0.006 左右。另外，針對具體的數(shù)據(jù)集有時候存在個別最優(yōu)，雖說默認(rèn)情況下“out-out”模式不一定最優(yōu)，但它綜合考慮了代表團(tuán)鏈入鏈處關(guān)系中的“in”和“out”兩種情況。因此，從三種模式的差距來看，將“outout”視為默認(rèn)情況是合理的。

4 結(jié)語

針對原始密度峰值DPC算法處理大規(guī)模數(shù)據(jù)能力欠缺以及FastDEC 密度支配域代表點(diǎn)代表能力不足的問題，一種新的密度代表團(tuán)策略和支配域相似度衡量方式被提出。密度代表團(tuán)策略采用了Kmeans++的采樣思想，使得代表團(tuán)能夠更均勻地分布于支配域中，更好地反映支配域的空間分布，從而彌補(bǔ)了單個代表點(diǎn)代表能力不足的缺陷。而針對代表團(tuán)的域間相似度衡量，新算法采用基于代表團(tuán)近鄰圖的概率加權(quán)高斯核函數(shù)作為相似度衡量方式。使得其更注重代表團(tuán)中最相近的代表點(diǎn)的距離。使其比一般的均值衡量更加合理。該相似度也可稱為Weighted-Gaussian相似度，簡稱WG相似度。對應(yīng)的新算法也命名為DWG-DPC?？紤]到近鄰的連入連處關(guān)系有鏈入鏈出兩種情況，DWG-DPC給出了三種計(jì)算方式?！癷n”模式側(cè)重考慮自身鏈入情況，“out”模式側(cè)重考慮自身鏈出其他支配域情況，“out-out”模式綜合考慮了前兩者。默認(rèn)的模式為“out-out”。對比實(shí)驗(yàn)表明，這種策略不僅可以有效提高原始DPC 算法的聚類質(zhì)量，增強(qiáng)其應(yīng)對大規(guī)模數(shù)據(jù)聚類的能力，對Fast-DEC 在大規(guī)模聚類任務(wù)上的表現(xiàn)也有所提升。進(jìn)一步的三種模式對比實(shí)驗(yàn)表明，這三種可以作為支配域代表團(tuán)域間相似度的衡量方式，盡管不同數(shù)據(jù)集各種模式發(fā)揮的作用不同，但差距不大，考慮到“out-out”更加一般化，因此將其設(shè)為默認(rèn)模式是合理的。

DWG-DPC算法雖在部分?jǐn)?shù)據(jù)集上取得了成就，實(shí)驗(yàn)也表明代表團(tuán)策略配合高斯域間相似度確實(shí)有一定效果，但也存在個別效果不好的情況。因此，該算法還有一定改進(jìn)空間。目前考慮到的改進(jìn)點(diǎn)如下。第一，各區(qū)域代表團(tuán)的規(guī)模是固定的，可以考慮針對不同的支配域大小來靈活設(shè)定，進(jìn)而改進(jìn)算法。第二，邊緣密度點(diǎn)估計(jì)可以考慮使用更為一般性的幾何空間分布來更好地獲取樣本數(shù)，文中的超立方體均勻分布是一種非常理想的假設(shè)，僅僅是為了方便計(jì)算。第三，高斯域間相似度只是考慮到高斯核函數(shù)的放縮特性，以及近鄰圖的關(guān)聯(lián)關(guān)系得出的比較合理的衡量方式，因此在度量方法上也有提升空間。這些改進(jìn)點(diǎn)可作為后續(xù)DPC算法改進(jìn)研究的出發(fā)點(diǎn)。