李沛武，張永芳，黃逸翠，劉紫亮，居 翔

(南昌工程學(xué)院 信息工程學(xué)院，江西 南昌 330099)

數(shù)掘挖掘因具有數(shù)據(jù)過濾的高效性和獲取信息的便捷性而備受關(guān)注，聚類算法是其經(jīng)典的技術(shù)[1]。聚類算法無需先驗(yàn)知識，根據(jù)樣本點(diǎn)間的相似性將數(shù)據(jù)集劃分成對應(yīng)的簇[2]。聚類算法大致包括5種：基于劃分的聚類、基于層次的聚類、基于密度的聚類、基于網(wǎng)格的聚類和基于模型的聚類，每一種算法都有其對應(yīng)的優(yōu)點(diǎn)和缺點(diǎn)[3]。

Rodriguez[4]等在2014年提出密度峰值聚類算法(Density Peaks Clustering，DPC)，該算法不同于傳統(tǒng)的密度聚類，具有參數(shù)少、能發(fā)現(xiàn)非球狀簇、對噪聲點(diǎn)不敏感的特點(diǎn)。但對密度分布不均衡數(shù)據(jù)集聚類時，DPC算法未考慮樣本點(diǎn)空間分布，會導(dǎo)致聚類效果不佳，在分配過程中易產(chǎn)生連帶錯誤。為解決以上缺陷，很多研究者對DPC算法進(jìn)行改進(jìn)。針對局部密度計(jì)算方式存在的不足，文獻(xiàn)[5]引入最近鄰和共享近鄰的概念，定義兩步分配準(zhǔn)則，提出基于共享近鄰的密度峰值聚類算法(Shared-nearest-neighbor-based clustering by fast search and find of density peaks，SNN-DPC)，提高了算法對于不同數(shù)據(jù)集聚類的準(zhǔn)確性。文獻(xiàn)[6]引入逆K近鄰的思想改進(jìn)局部密度公式，緩解了DPC算法對密度不均數(shù)據(jù)集聚類效果不佳的問題。文獻(xiàn)[7]融合共享K近鄰和共享逆K近鄰改進(jìn)樣本點(diǎn)間的相似性，改善了DPC算法不能很好處理簇間密度分布不均的情況。文獻(xiàn)[8]將自然和共享近鄰算法結(jié)合重新定義局部密度的計(jì)算規(guī)則，使算法在性能等方面有明顯的提升。文獻(xiàn)[9]將密度比例思想引入密度峰值聚類中，通過計(jì)算兩個鄰域內(nèi)密度平均值之比來重新定義樣本的相對密度，提高了對于密度較小類簇中心的識別度。文獻(xiàn)[10]引入改進(jìn)凝聚度的思想，使用節(jié)點(diǎn)凝聚度替代樣本點(diǎn)相對密度的計(jì)算，通過在真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集上的實(shí)驗(yàn)證明，改進(jìn)算法能找到更高精度的聚類中心。針對樣本分配存在的不足，文獻(xiàn)[11]借鑒萬有引力公式，重新定義樣本點(diǎn)與簇間的相似性，將未分配樣本點(diǎn)劃分給相似性高的簇，提高了在復(fù)雜數(shù)據(jù)集中樣本點(diǎn)分配的正確率。文獻(xiàn)[12]提出了兩步分配策略，對于核心點(diǎn)按照密度遞減的順序分配給最近的簇中心點(diǎn)，對于離群點(diǎn)根據(jù)鄰近樣本點(diǎn)所屬簇信息進(jìn)行劃分。改進(jìn)算法不僅能很好處理含有噪聲點(diǎn)的數(shù)據(jù)集，而且能適應(yīng)大規(guī)模數(shù)據(jù)集。文獻(xiàn)[13]提出新的樣本分配策略，首先將簇中心的K個近鄰點(diǎn)分配給對應(yīng)的類簇，其次將未分配點(diǎn)劃分給相互近鄰度最高樣本點(diǎn)所在的類簇，解決了數(shù)據(jù)集密度不均聚類效果不佳的問題。雖然上述改進(jìn)算法都提高了算法的準(zhǔn)確度，但部分算法未重視樣本空間結(jié)構(gòu)的影響。文獻(xiàn)[14]提出樣本點(diǎn)進(jìn)行類簇分配時，不僅要考慮與密度較大點(diǎn)之間的距離，還要考慮K近鄰對樣本點(diǎn)的影響，改進(jìn)算法減少了對密度較大樣本點(diǎn)正確分配的依賴性。文獻(xiàn)[15]提出結(jié)合K近鄰思想的統(tǒng)計(jì)學(xué)習(xí)分配策略，根據(jù)樣本點(diǎn)K近鄰中屬于各類簇的樣本個數(shù)決定所屬類簇，改進(jìn)算法提高了樣本分配的準(zhǔn)確。文獻(xiàn)[16]提出微簇融合策略，根據(jù)簇間密度差和簇間距離進(jìn)行微簇合并，改善了剩余樣本點(diǎn)分配的容錯性，提高樣本分配的效率。文獻(xiàn)[17]利用第一宇宙速度建立兩步樣本點(diǎn)分配策略，通過每一個未分配樣本點(diǎn)與簇類中心點(diǎn)之間的第一宇宙速度比較，把未分配點(diǎn)劃分為必然屬于和可能屬于該類簇，針對可能屬于該簇的樣本點(diǎn)進(jìn)行再一次對比，此分配方法使剩余樣本點(diǎn)的分配更加準(zhǔn)確。文獻(xiàn)[18]將K近鄰算法與圖標(biāo)簽傳播結(jié)合改進(jìn)密度峰值聚類算法，利用K近鄰圖傳播動態(tài)地對剩余未分配樣本點(diǎn)進(jìn)行類簇劃分，提高了聚類的準(zhǔn)確性。

針對DPC算法存在的問題，本文提出了一種基于雙重密度和簇間近鄰度的密度峰值聚類算法(Density peak clustering based on dual density and inter cluster proximity，DI-DPC)。首先，DI-DPC算法根據(jù)樣本密度受局部特征和全局特征的影響，在融合K近鄰和截?cái)嗑嚯x的基礎(chǔ)上提出雙重密度計(jì)算準(zhǔn)則，提高了聚類結(jié)果的準(zhǔn)確率；其次，根據(jù)樣本點(diǎn)的相對密度和相對距離選出候選中心點(diǎn)，并將未分配樣本點(diǎn)分配給距離最近、密度更大的樣本點(diǎn)所在的簇，生成候選微簇；最后，根據(jù)簇與簇之間的近鄰度進(jìn)行簇間合并，緩解樣本點(diǎn)連鎖式錯誤分配的問題。通過實(shí)驗(yàn)證明，改進(jìn)的算法有效地改善了對密度分布不均衡數(shù)據(jù)集聚類效果不佳和對未分配點(diǎn)劃分類簇易出現(xiàn)連帶錯誤的情況。

1 DPC算法

DPC算法假設(shè)簇中心周圍近鄰點(diǎn)的密度相對較小，且簇中心與其它密度更大點(diǎn)距離相對較遠(yuǎn)。因此DPC算法定義了局部密度ρi和相對距離δi兩個變量。

假設(shè)數(shù)據(jù)集DN×M=[x1，x2，…，xN]T，其中N為樣本個數(shù)，M為樣本維數(shù)。DPC算法在計(jì)算局部密度ρi時，有兩種計(jì)算方法，如式(1)～(3)所示：

(1)

(2)

(3)

式中dc為截?cái)嗑嚯x，dij為樣本點(diǎn)i與樣本點(diǎn)j間的歐氏距離。式(1)稱為截距核，適用于數(shù)據(jù)量較大的數(shù)據(jù)集；式(3)稱為高斯核，適用于數(shù)據(jù)量較小的數(shù)據(jù)集。

相對距離δi指樣本點(diǎn)到最近局部密度更大點(diǎn)的距離。對于密度最大點(diǎn)，其相對距離δi表示樣本點(diǎn)間距離的最大值；反之，相對距離δi表示樣本點(diǎn)i與密度比其大的樣本點(diǎn)間的最短距離，如式(4)所示：

(4)

計(jì)算出以上兩個參數(shù)之后，構(gòu)造以ρ為橫坐標(biāo)，δ為縱坐標(biāo)的決策圖，選擇局部密度ρ和相對距離δ相對較大的樣本點(diǎn)作簇中心，最后將未分配樣本點(diǎn)劃分給比其密度大且最近的樣本點(diǎn)所在的簇。

2 DI-DPC算法

2.1 融合截?cái)嗑嚯x和K近鄰的雙重密度

針對DPC密度計(jì)算存在的問題，本文提出融合截?cái)嗑嚯x和K近鄰雙重密度計(jì)算方法，過程如下：

由于DPC算法聚類結(jié)果對dc取值比較敏感，本文根據(jù)文獻(xiàn)[17]定義的公式計(jì)算dc，如式(5)所示，以減少計(jì)算過程中參數(shù)的使用量。

(5)

定義1基于K近鄰的局部密度。根據(jù)樣本點(diǎn)與K個近鄰點(diǎn)的距離定義基于K近鄰的局部密度，如式(6)所示：

(6)

定義2基于截?cái)嗑嚯x的局部密度。在考慮樣本點(diǎn)間結(jié)構(gòu)的前提下，本文重新定義樣本點(diǎn)i與其截?cái)嗑嚯x范圍內(nèi)樣本點(diǎn)間的距離，如式(7)所示：

(7)

式中y_dc(i)為已劃分類簇的集合；n_dc(i)為未劃分類簇的集合。計(jì)算基于截?cái)嗑嚯x的局部密度步驟分三步進(jìn)行：(1)將樣本點(diǎn)i截?cái)嗑嚯x范圍內(nèi)的近鄰點(diǎn)根據(jù)距離降序排列，同時將樣本點(diǎn)i存入到y(tǒng)_dc(i)，將其它近鄰點(diǎn)依照排序存入n_dc(i)；(2)依次計(jì)算y_dc(i)中樣本點(diǎn)與n_dc(i)中樣本點(diǎn)的最小距離，并將計(jì)算出最小距離的樣本點(diǎn)由n_dc(i)移入中y_dc(i)并對計(jì)算出的距離求和；(3)直到n_dc(i)為空時，停止遍歷。

定義3雙重密度。融合K近鄰和截?cái)嗑嚯x的雙重密度計(jì)算公式，如式(8)～(9)所示：

ρa(bǔ)ve_i=(ρKnn_i+ρdc_i)/2，

(8)

(9)

2.2 基于簇間近鄰度的多簇合并準(zhǔn)則

針對DPC算法分配策略存在的問題，本文提出基于簇間近鄰度的多簇合并準(zhǔn)則。進(jìn)行多簇合并前需要生成候選簇，其過程為從依據(jù)式(4)～(9)計(jì)算出樣本點(diǎn)相對距離和相對密度構(gòu)造的決策圖中獲取p個候選簇中心點(diǎn)(C≤p≤5C，C表示實(shí)際類簇個數(shù))，然后將未分配樣本點(diǎn)依照密度降序劃分給距離最近、密度更大的樣本點(diǎn)所在的簇，顯然生成的候選簇?cái)?shù)量大于或等于實(shí)際的類簇?cái)?shù)量。為獲得更好的聚類結(jié)果，需要將相鄰的或距離相近的簇進(jìn)行合并，因此本文提出新的多簇合并算法規(guī)則定義如下：

定義4簇間近鄰度。統(tǒng)計(jì)每個簇邊緣點(diǎn)dc范圍內(nèi)其它簇的點(diǎn)個數(shù)，如式(10)所示：

(10)

(11)

式中截?cái)嗑嚯xdc根據(jù)式(5)定義；M(dij-dc)=1表示i點(diǎn)與j點(diǎn)不在同一個簇中且兩者間距離小于截?cái)嗑嚯x，否則M(dij-dc)=0。mij表示樣本點(diǎn)i所在簇與樣本點(diǎn)j所在簇之間的近鄰度，簇間近鄰度越大，表明簇間相似性越大。

基于簇間近鄰度的多簇合并過程主要計(jì)算候選簇間的近鄰度mij，將計(jì)算出的mij放入構(gòu)建的簇間近鄰度矩陣，從矩陣中選擇最大近鄰度對應(yīng)的兩個候選簇進(jìn)行合并，直到候選簇?cái)?shù)等于實(shí)際簇?cái)?shù)為止。

2.3 算法步驟及分析

綜上所述，改進(jìn)算法采用雙重密度法則計(jì)算樣本相對密度，依據(jù)DPC算法中類簇中心的選擇機(jī)制選出候選類簇中心，將剩余樣本點(diǎn)分配給鄰近候選類簇，最后依據(jù)改進(jìn)的類簇合并法則進(jìn)行剩余樣本點(diǎn)分配，從而形成最終的類簇。DI-DPC算法的具體流程如下：

step1 讀取數(shù)據(jù)，對數(shù)據(jù)進(jìn)行最大最小歸一化處理；

step2 按照式(6)～(9)計(jì)算局部密度；

step3 根據(jù)式(4)計(jì)算相對距離；

step4 構(gòu)建決策圖，選出候選簇中心點(diǎn)；

step5 將未分配點(diǎn)劃分給最近的密度較大點(diǎn)對應(yīng)的簇；

step6 根據(jù)式(10)～(11)計(jì)算候選簇間的相似性，構(gòu)建簇間近鄰度矩陣；

step7 遍歷簇間近鄰度矩陣獲得最大值，合并對應(yīng)的候選簇；

step8 直到候選簇的個數(shù)等于真實(shí)簇個數(shù)時，輸出聚類結(jié)果。

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

為更好地分析DI-DPC算法的時間復(fù)雜度，本文先對DPC算法的時間復(fù)雜度進(jìn)行分析。樣本數(shù)為n的數(shù)據(jù)集進(jìn)行密度峰值聚類的時間復(fù)雜度主要包括以下三個方面：(1)計(jì)算樣本點(diǎn)相對密度時，需要兩重循環(huán)遍歷所有樣本構(gòu)建樣本間的距離矩陣，因此其時間復(fù)雜度量級為O(n2)。(2)計(jì)算樣本點(diǎn)相對距離時，需要對所有樣本與其它樣本的距離和密度進(jìn)行比較，因此需要兩重循環(huán)所有樣本，其相應(yīng)的時間復(fù)雜度量級為O(n2)。(3)在進(jìn)行剩余樣本點(diǎn)的分配時，根據(jù)剩余樣本點(diǎn)與已選出的C(C表示實(shí)際類簇個數(shù))個聚類中心點(diǎn)間距離進(jìn)行比較，因此該階段的時間復(fù)雜度為O(n×C)。綜上所述，DPC算法的時間復(fù)雜度量級為O(n2)。

DI-DPC算法相較于DPC算法改進(jìn)部分的時間復(fù)雜度主要包括：(1)改進(jìn)的相對密度計(jì)算的時間復(fù)雜度包含以下兩個步驟：基于K近鄰的密度計(jì)算的時間復(fù)雜度為O(n×K)，其中K的取值遠(yuǎn)小于n的取值；基于截?cái)嗑嚯x的局部密度也需要雙重遍歷所有樣本構(gòu)建距離矩陣，其時間復(fù)雜度量級為O(n2)。因此該階段整體的時間復(fù)雜度量級為O(n2)。(2)進(jìn)行候選簇合并時，遍尋簇間近鄰度表的時間復(fù)雜度為O(p×n)，其中C≤p≤5C。綜上所述，DI-DPC算法的時間復(fù)雜度與DPC算法的時間復(fù)雜度量級一致為O(n2)。

3 實(shí)驗(yàn)結(jié)果與分析

本文使用9種經(jīng)典人工數(shù)據(jù)集以及9種UCI真實(shí)數(shù)據(jù)集證明DI-DPC算法的有效性，并將DI-DPC算法與DPC[4]、SNN-DPC[5]、FCM[20]、K-means[21]、DBSCAN[22]進(jìn)行性能對比，采用準(zhǔn)確率(ACC)[23]、調(diào)整蘭德系數(shù)(AMI)[24]、調(diào)整互信息(ARI)[24]作評價標(biāo)準(zhǔn)。采用Spyder進(jìn)行實(shí)驗(yàn)，所有程序均采用Python實(shí)現(xiàn)。

在實(shí)驗(yàn)之前，對所有的數(shù)據(jù)集進(jìn)行最大最小歸一化處理如式(12)所示，使數(shù)據(jù)的不同特征歸一到一個范圍下，降低算法運(yùn)算時間開銷。

(12)

式中max(xj)、min(xj)分別代表j列中的最大值和最小值。

3.1 算法參數(shù)設(shè)置

為更好客觀地測試各算法的聚類性能，本文對每種算法進(jìn)行了參數(shù)調(diào)優(yōu)。DI-DPC算法、SNN-DPC算法需要設(shè)置樣本近鄰數(shù)K，一般從1～20中選出最優(yōu)參數(shù)作為樣本近鄰數(shù)K。K-means算法需要給出類簇?cái)?shù)K，但K-means選取類簇中心點(diǎn)存在隨機(jī)性，所以需要進(jìn)行50次實(shí)驗(yàn)取最好結(jié)果。FCM算法需要事先指定類簇的個數(shù)K。DPC需要確定截?cái)嗑嚯xdc，取值參照文獻(xiàn)[4]規(guī)定，使落入圓中點(diǎn)個數(shù)占數(shù)據(jù)集總數(shù)的1%～2%。DBSCAN需要確定鄰域半徑ε和最小樣本點(diǎn)數(shù)Minpts，鄰域半徑ε取值從0.01～1.20，步長為0.01；最小樣本點(diǎn)數(shù)Minpts取值從1～50，步長為1。

3.2 人工數(shù)據(jù)集結(jié)果分析

采用人工數(shù)據(jù)集實(shí)驗(yàn)的主要目的是比較每種算法在不同數(shù)據(jù)集上的聚類效能。表1列出了9種人工數(shù)據(jù)集的具體屬性信息以及DI-DPC算法在9種人工數(shù)據(jù)集上的聚類結(jié)果。

表1 人工數(shù)據(jù)集及其聚類結(jié)果

表1是6種算法在人工數(shù)據(jù)集上的對比結(jié)果，加粗加黑的部分表示結(jié)果中相對較好的。具體情況是：在Jain數(shù)據(jù)上，DI-DPC算法的性能最好，評價標(biāo)準(zhǔn)的取值都可達(dá)到最大值1.000，而SNN-DPC、K-means及FCM的性能相對較差；在Aggregation和Flame數(shù)據(jù)集，DPC和DI-DPC算法相較于K-means和FCM聚類結(jié)果是較優(yōu)；在Spiral數(shù)據(jù)集上，K-means、FCM聚類效果較差，其余4種皆可取得最優(yōu)值；在R15數(shù)據(jù)集上，4種經(jīng)典算法及SNN-DPC算法的準(zhǔn)確率僅有0.992，而DI-DPC算法的準(zhǔn)確率為0.996，準(zhǔn)確率提高了0.4%；在Pathbased、D31、S2、Five_clusters數(shù)據(jù)集上，DI-DPC算法為6種算法中的最優(yōu)算法，ACC、AMI和ARI都有較大的提高。為更好證明DI-DPC算法的優(yōu)越性，本研究選取3種聚類算法在3組人工數(shù)據(jù)集上的聚類效果圖進(jìn)行詳細(xì)說明，其中效果圖中不同形狀的樣本點(diǎn)代表不同的類簇。

Jain數(shù)據(jù)集中兩個簇的密度相差較大，上半部分密度較為稀疏，下半部分密度較大。簇間密度不均導(dǎo)致聚類中心點(diǎn)選取易在一個簇中。通過圖1可以看出，3種算法中只有DI-DPC算法分類是正確的；DPC、SNN-DPC都錯誤地將一個簇劃分成兩個。相比之下，在處理Jain數(shù)據(jù)集時，DI-DPC算法更好。

圖1 3種算法對Jain數(shù)據(jù)集的處理結(jié)果

Five_clusters數(shù)據(jù)集中樣本點(diǎn)總體密度較大且數(shù)據(jù)集相對較為密集。從圖2可知，3種算法對于Five_clusters數(shù)據(jù)集處理的結(jié)果中，SNN-DPC算法和DI-DPC算法對于該數(shù)據(jù)集的分類是相對較好的，但DI-DPC算法對兩簇間的樣本點(diǎn)的聚類效果更好，DI-DPC算法的聚類效果更優(yōu)。DPC算法存在將一個簇劃分為2個簇的情況，聚類結(jié)果相對較差。

圖2 3種算法對Five_clusters數(shù)據(jù)集的處理結(jié)果

Aggregation數(shù)據(jù)集是由7個相對集中的類簇組成，其中部分類簇之間相互連接。由圖3可以看出，DPC、SNN-DPC算法錯誤地將一個完整的類簇劃分為兩個類簇；DI-DPC算法較好地保留了類簇的完整性。整體上來看，在Aggregation數(shù)據(jù)集上，DI-DPC算法的性能較好。

圖3 3種算法在Aggregation數(shù)據(jù)集上的處理結(jié)果

綜合上述內(nèi)容，可以看出DI-DPC算法在處理人工合成數(shù)據(jù)集的時候，可以獲得良好的聚類結(jié)果。

3.3 UCI數(shù)據(jù)集結(jié)果分析

為了進(jìn)一步驗(yàn)證算法的效果與性能，本文選擇了9種規(guī)模和維度有較大區(qū)別的UCI數(shù)據(jù)集。表2中總結(jié)了9種UCI數(shù)據(jù)集的相關(guān)屬性，以及DI-DPC算法與K-means、DPC、DBSCAN、SNN-DPC算法在ACC、AMI、ARI上的對比。

通過表2可看出，DI-DPC算法相對于其它4種算法有不同程度的提高。在Wine數(shù)據(jù)集上，DI-DPC算法的AMI和ARI取值次于SNN-DPC算法，但ACC值高于4種對比算法；在Movement_libras數(shù)據(jù)集上，本文算法的ACC值低于SNN-DPC算法，但其它兩個評價函數(shù)的取值高于其它算法；在其它數(shù)據(jù)集上，DI-DPC算法的聚類效果好于其它4種對比算法。通過上述分析可以得到，DI-DPC算法聚類效果更好。

表2 UCI數(shù)據(jù)集

4 結(jié)束語

針對DPC算法存在的問題，本文提出了基于雙重密度和簇間近鄰度的密度峰值聚類算法。DI-DPC算法提出了基于K近鄰和基于截?cái)嗑嚯x的雙重密度計(jì)算公式，提高了對密度不均衡數(shù)據(jù)集聚類時的準(zhǔn)確性，同時增強(qiáng)了不同空間結(jié)構(gòu)樣本的相互作用；提出了新的簇合并法則，改善了DPC算法分配策略的不足之處。通過在人工合成數(shù)據(jù)集以及UCI真實(shí)數(shù)據(jù)集聚類結(jié)果證明，DI-DPC算法相較于經(jīng)典聚類算法、SNN-DPC算法都取得良好的分配結(jié)果。但DI-DPC算法在選取聚類中心時，會受到人為選擇和經(jīng)驗(yàn)值的影響，造成額外的時間成本，因此自動獲取聚類中心將會是下一步實(shí)驗(yàn)的方向。