基于最優(yōu)密度估計的密度峰值聚類算法

覃 華，劉 政，蘇一丹

(廣西大學(xué) 計算機與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

密度峰值聚類算法(DPC)具有計算效率高、能檢測非球形簇等優(yōu)點[1,2]，但該算法密度計算方法存在兩大不足：一是密度計算所需的截斷閾值dc依靠經(jīng)驗選取，造成算法對特征復(fù)雜的實際數(shù)據(jù)集辨識能力偏低；二是需要手動選取聚類中心，存在較大的人為誤差。國內(nèi)外文獻(xiàn)對DPC的兩大缺陷展開了相關(guān)研究，文獻(xiàn)[3]提出用加權(quán)模糊K近鄰方法解決截斷閾值dc的選擇標(biāo)準(zhǔn)問題；文獻(xiàn)[4]引入勢場模型自動選擇截斷閾值dc； 文獻(xiàn)[5]用合并聚類中心方法實現(xiàn)自動選擇截斷閾值dc； 文獻(xiàn)[6]用布谷鳥算法實現(xiàn)截斷閾值dc的自動最優(yōu)化選擇；文獻(xiàn)[7,8]用果蠅算法、DNA遺傳算法優(yōu)化截斷閾值dc與聚類中心的選擇問題；文獻(xiàn)[9]提出用線性擬合方法自動選擇聚類中心。

受上述文獻(xiàn)啟發(fā)，為避免截斷閾值dc對密度計算的影響，本文提出一種最優(yōu)密度估計方法計算DPC的密度，首先使用最優(yōu)Oracle逼近[10]計算出最優(yōu)化協(xié)方差矩陣，再利用最優(yōu)協(xié)方差矩陣構(gòu)造馬氏距離，通過最優(yōu)協(xié)方差矩陣提高DPC對數(shù)據(jù)相似度的區(qū)分能力，實現(xiàn)DPC中對數(shù)據(jù)樣本密度的最優(yōu)估計，最后通過K近鄰算法計算出數(shù)據(jù)樣本的密度，構(gòu)造出基于最優(yōu)密度估計的密度峰值聚類算法(density peaks clustering algorithm based on optimal density estimation)。人工數(shù)據(jù)集、UCI真實數(shù)據(jù)集上的仿真實驗結(jié)果以及與其它DPC改進(jìn)算法計算結(jié)果的比較驗證了所提算法的可行性。

1 DPC的基本概念

密度峰值聚類算法基于兩種假設(shè)：①聚類中心被比其密度小的點所包圍。②密度中心離其它局部密度較大的點較遠(yuǎn)?；谏鲜黾僭O(shè)，樣本點的密度ρi和樣本點與比其密度大且離其最近的點的距離δi被應(yīng)用于聚類當(dāng)中。樣本點密度ρi的計算如下

(1)

當(dāng)x<0時χ(x)=1， 當(dāng)x≥0時χ(x)=0， 其中dc為截斷距離，dij為點i與點j的樣本相似度，通常為樣本點間的歐式距離。密度ρi表示為以點i為中心，dc為半徑的圓內(nèi)的點的個數(shù)。在DPC算法的源代碼中，作者提供了另一種ρi的計算方法

(2)

式(1)的使用可能會經(jīng)常使一些樣本點獲得相同的密度，影響聚類中心的選擇，式(2)使用高斯核來計算樣本點的密度，在一定程度上解決了式(1)存在的問題。式(1)和式(2)中唯一參數(shù)dc的選擇，影響著聚類的結(jié)果，原文建議取使以dc為半徑的圓內(nèi)包含的數(shù)據(jù)點為數(shù)據(jù)集總點數(shù)的2%的值[1]。

樣本點與比其密度大且離其最近的點的距離δi的計算如下

(3)

對于密度最大的點

(4)

DPC使用上述兩個變量構(gòu)建ρ-δ決策圖，將ρ和δ都較大的點選取成為聚類中心。然后把剩下的點分配到比其密度大且離其最近的已分配的點的所屬簇。為了實現(xiàn)聚類中心個數(shù)的自動確定與選取，原算法使用變量

γi=ρiδi

(5)

并對γi進(jìn)行降序排列，構(gòu)建γ決策圖，當(dāng)ρi和δi都較大時,γi的值會更大，中心點離非中心點的γi值會更遠(yuǎn)，在γ決策圖中會出現(xiàn)點的跳躍。使用啟發(fā)式方法可以在γ決策圖中確定聚類中心個數(shù)。

2 最優(yōu)Oracle估計的馬氏距離計算

馬氏距離[11]作為協(xié)方差距離，與歐式距離不同的是，馬氏距離考慮了數(shù)據(jù)的分布信息，測量的是樣本點x在分布D下與樣本點y相差的分布D的標(biāo)準(zhǔn)差的數(shù)量，分布D的信息體現(xiàn)在協(xié)方差矩陣S上，并且馬氏距離是一種無量綱的計算方法，馬氏距離的計算如下

(6)

其中，S-1為分布D的樣本協(xié)方差矩陣的逆矩陣。S為對稱矩陣，主對角線上的元素為分布D在各個維度上的方差。除主對角線元素外其它元素為樣本點所處分布D各個維度之間的協(xié)方差，是在分布D上樣本點的整體關(guān)系。計算馬氏距離，重點在于協(xié)方差矩陣的計算，協(xié)方差矩陣的計算受所選分布D與計算方法影響。

對于協(xié)方差矩陣的計算，傳統(tǒng)的樣本協(xié)方差矩陣計算方法為

(7)

當(dāng)樣本維數(shù)p大于樣本總數(shù)n時，上式計算得到的協(xié)方差矩陣不可逆。當(dāng)p/n的結(jié)果小于1且不可忽略時，上式計算協(xié)方差矩陣在進(jìn)行求逆運算后得到的結(jié)果會有很大的估計誤差，得到的協(xié)方差矩陣不是良好的。

(8)

假設(shè)所有的xi都是無關(guān)系的并且有相等的方差，則協(xié)方差矩陣的一種直觀估計為

(9)

(10)

綜上所述，想要得到一個良好的正定可逆的協(xié)方差矩陣的估計，需要滿足下述條件

(11)

(12)

其中，ρ*的最佳取值區(qū)間為[0,1]，將ρ*代入式(10)得到協(xié)方差的Oracle估計，然而在大多數(shù)情況下Σ是未知的，ρ*不能得到結(jié)果，只能對其進(jìn)行逼近。

OAS是Oracle估計的一種最佳逼近方法，OAS預(yù)先對Σ進(jìn)行假設(shè)，然后循環(huán)迭代這個假設(shè)直到收斂，最后得到的ρ*的近似值為

(13)

將上式代入式(10)得到最優(yōu)協(xié)方差矩陣

(14)

使用上式計算馬氏距離得最優(yōu)Oracle估計的馬氏距離(OAS馬氏距離)

(15)

使用最優(yōu)Oracle估計計算馬氏距離中的協(xié)方差矩陣，可以提升馬氏距離在維數(shù)高的數(shù)據(jù)集的適用性和相似度的區(qū)分能力，減小計算誤差。

3 基于最優(yōu)密度估計的密度峰值聚類算法

本文提出算法的基本思想為：使用樣本點的K個近鄰點作為分布計算樣本點與其K個近鄰點的OAS馬氏距離，并用于樣本點密度的計算。

設(shè)X=[x1,x2,…,xN]， 為N個樣本， NNk(xi) 為在歐式距離下，離xi最近的第K個樣本點，xi的K近鄰點定義如下

KNN(xi)={j∈X|d(xi,xj)≤d(xi,NNk(xi))}

(16)

基于OAS馬氏距離的K近鄰樣本密度

(17)

其中，ρi為使用樣本點xi的K個近鄰點作為分布D計算該點與其最近K個點的馬氏距離并求和。K取值與dc類似，可以為總點數(shù)的一個百分比。對ρi進(jìn)行進(jìn)一步改進(jìn)，對邊界點進(jìn)行懲罰，得到最優(yōu)密度估計方法為

(18)

上式中的第三項為懲罰項，用于使聚類中心的選取遠(yuǎn)離邊界點，ω為懲罰系數(shù)，使用上式最優(yōu)密度估計方法，可以提高DPC對數(shù)據(jù)相似度的區(qū)分能力，使密度計算不受數(shù)據(jù)量綱影響，提升聚類精度。

所提算法流程如下：

輸入：數(shù)據(jù)集X=[x1,x2,…,xN]，k、ω值。

輸出：數(shù)據(jù)集中樣本標(biāo)簽class。

步驟1 計算樣本點間的歐式距離dij。

步驟3 使用式(3)和式(4)計算樣本點的δi。

步驟4 使用式(5)計算樣本點的γi， 并建立γ決策圖，獲取聚類中心數(shù)目。

步驟6 將剩余未分配的點，按照原DPC算法對聚類中心以外的點的分配方式進(jìn)行分配[1]。

上述算法中，關(guān)鍵點是根據(jù)最優(yōu)密度估計建立決策圖并確定聚類中心，以下通過與原始DPC方法相比較，說明所提算法確定聚類中心的優(yōu)點。

圖1為使用DPC算法在隨機生成的多密度數(shù)據(jù)集上的聚類中心選取結(jié)果，實心點為被選取為聚類中心的點。從圖中可以看出，密集程度較小的棱形簇在DPC算法的密度計算方式下，擁有較小的密度，在ρ-δ決策圖上貼近于δ軸，不能被選取為簇中心，導(dǎo)致簇中心選取錯誤。

圖1 DPC聚類中心選取結(jié)果

圖2為使用本文算法在與圖1相同數(shù)據(jù)集上的聚類中心選取結(jié)果，實心點為被選取為聚類中心的點。從圖中可以看出，密集程度較小的棱形簇在本文算法的密度計算方式下，也能擁有相對較大的密度，從而能從決策圖中被選取為簇中心，并且中心點離其它非中心點在ρ-δ決策圖中的距離較遠(yuǎn)，便于簇中心的選取。

圖2 本文算法聚類中心選取結(jié)果

4 仿真實驗

在人工數(shù)據(jù)集和UCI真實數(shù)據(jù)集上檢驗所提算法的聚類效果和性能，實驗的硬件環(huán)境為Intel Core i7-6700HQ @2.6 Hz CPU, 16 GB內(nèi)存，在Windows7 x64平臺上用Matlab2016a實現(xiàn)算法。

4.1 實驗數(shù)據(jù)集說明

實驗用到4個人工數(shù)據(jù)集和8個UCI真實數(shù)據(jù)集，數(shù)據(jù)集的描述詳見表1和表2。

表1 人工數(shù)據(jù)集信息

表2 UCI真實數(shù)據(jù)集信息

4.2 實驗結(jié)果與分析

(1)人工數(shù)據(jù)集上的實驗結(jié)果及分析

本文算法與DPC算法[1]在人工數(shù)據(jù)集上的實驗結(jié)果比較如圖3～圖6所示，被分為同一簇的樣本點在圖中擁有相同的形狀和灰度。DPC算法在Aggregation、Flame、R15、Jain數(shù)據(jù)集上的dc設(shè)置分別為2%、3%、2%、1%[1]。本文算法在Aggregation和Flame數(shù)據(jù)集上的參數(shù)設(shè)置為k為2，ω為3，在R15和Jain數(shù)據(jù)集上的參數(shù)設(shè)置為k為3，ω為3[11]。

圖3 Jain數(shù)據(jù)集聚類結(jié)果對比

圖4 Flame數(shù)據(jù)集聚類結(jié)果對比

圖5 R15數(shù)據(jù)集聚類結(jié)果對比

圖6 Aggregation數(shù)據(jù)集聚類結(jié)果對比

圖3的聚類結(jié)果顯示，在有兩個不同密度簇的數(shù)據(jù)集Jain上，DPC錯誤的將密集程度相對較高的簇的樣本點選為密集程度相對較低的簇的中心，導(dǎo)致聚類結(jié)果不理想。而本文算法能夠正確找出不同密度簇的簇中心，并正確的對剩余點進(jìn)行分配，得到正確的聚類結(jié)果。

圖4的聚類結(jié)果顯示，在有兩個不同形狀簇的Flame數(shù)據(jù)集上，原DPC算法與本文算法都能識別兩個不同形狀的簇。對比原DPC算法，本文算法在簇的連接處識別率與原算法相當(dāng)差異較小，亦保持著較高的準(zhǔn)確率。

圖5是DPC算法與本文算法在擁有多個簇的R15數(shù)據(jù)集上的比較。由圖可知，兩種算法都能夠識別其中的15個簇，并且識別正確率相當(dāng)。

圖6是Aggregation典型團狀數(shù)據(jù)集兩種算法計算結(jié)果的比較，由圖可看出兩種算法均能準(zhǔn)確地識別出7個簇,聚類表現(xiàn)差距較小,聚類精確率相當(dāng)。

從上述實驗結(jié)果比較可看出，本文算法和DPC算法在有特定形狀的人工數(shù)據(jù)集上聚類效果相當(dāng)，說明原始DPC算法對有特定形狀的人工數(shù)據(jù)集本身就有較強的判斷、識別能力，本文改進(jìn)后聚類精度提高不明顯。

(2)在UCI真實數(shù)據(jù)集上的實驗結(jié)果及分析

在UCI真實數(shù)據(jù)集上，將本文所提算法與原DPC[1]算法及近年其它的改進(jìn)DPC算法CDP[14]算法和FN-DP[13]算法相比較，結(jié)果采用準(zhǔn)確率(accuracy，ACC)[14]、標(biāo)準(zhǔn)化互信息(normalized mutual information，NMI)[14]指標(biāo)進(jìn)行評估，兩個指標(biāo)的取值范圍均為[0,1]，取值越大，表示得到的聚類結(jié)果越好。實驗結(jié)果對比詳見表3和表4，兩表中的符號“-”表示相應(yīng)文獻(xiàn)未給出該數(shù)據(jù)集的計算結(jié)果，無法在此數(shù)據(jù)集進(jìn)行結(jié)果比較。

表3 各算法聚類準(zhǔn)確率(ACC)對比

表4 各算法標(biāo)準(zhǔn)化互信息值(NMI)對比

從表3和表4的實驗結(jié)果對比得出。在iris數(shù)據(jù)集上對比原DPC算法與CDP算法和FN-DP算法，本文算法在兩個評估指標(biāo)上獲得了較好的結(jié)果。本文算法較原DPC算法在準(zhǔn)確率上提高3.3%，較CDP算法提高0.7%，較 FN-DP 算法提高0.6%。在標(biāo)準(zhǔn)化互信息上較原DPC算法提高10.5%，較CDP算法提高1.6%，較FN-DP算法提高1.6%。FN-DP算法使用模糊邏輯原理，使樣本點的局部密度更能反映局部信息，而本文算法使用KNN馬氏距離能使樣本點的局部密度能更好反映局部信息。

在seeds數(shù)據(jù)集的實驗結(jié)果顯示，本文算法在兩個指標(biāo)上優(yōu)于原DPC算法和CDP算法。本文算法較原DPC算法在準(zhǔn)確率上相等，較CDP算法提高2.8%。在標(biāo)準(zhǔn)化互信息上較原DPC算法提高3.3%，較CDP算法提高8.6%。

在乳腺癌數(shù)據(jù)集WDBC的實驗結(jié)果顯示，本文算法在兩個指標(biāo)上的都優(yōu)于原DPC算法與CDP算法及FN-DP算法。本文算法較原DPC算法在準(zhǔn)確率上提高了4.1%，較CDP算法提高8.8%，較FN-DP算法提高3.4%。在標(biāo)準(zhǔn)化互信息上較原DPC算法提高22.6%，較CDP算法提高19.1%，較FN-DP算法提高6%。

在樣本數(shù)目較大的數(shù)據(jù)集waveform的實驗結(jié)果顯示，本文算法在兩個指標(biāo)上都優(yōu)于原DPC算法與CDP算法及FN-DP算法。本文算法較原DPC算法在準(zhǔn)確率上提高9%，較CDP算法提高13.8%，較FN-DP算法提高10.7%。在標(biāo)準(zhǔn)化互信息上較原DPC算法提高0.2%，較CDP提高1.4%，較FN-DP算法提高10.5%。

在大腸桿菌數(shù)據(jù)集ecoli的實驗結(jié)果顯示，本文的算法在兩個指標(biāo)上都優(yōu)于原算法與CDP算法。本文算法較原DPC算法在準(zhǔn)確率上提高28.2%，較CDP算法提高13.7%。在標(biāo)準(zhǔn)化互信息上較原DPC算法提高18.6%，較CDP算法提高16%。

在特征數(shù)較多的雷達(dá)數(shù)據(jù)集ionosphere上的實驗結(jié)果顯示，本文的算法在兩個指標(biāo)上都優(yōu)于原DPC算法與CDP算法及FN-DP算法。本文算法較原DPC算法在準(zhǔn)確率上提高19.6%，較CDP算法提高7.7%，較FN-DP算法提高1.2%。在標(biāo)準(zhǔn)化互信息上較原DPC算法提高3.2%，較CDP算法提高11%，較FN-DP算法提高2.5%。

在sonar數(shù)據(jù)集上的實驗結(jié)果顯示，本文的算法在兩個指標(biāo)上都優(yōu)于原DPC算法與CDP算法。本文算法較原DPC算法在準(zhǔn)確率上提高1.9%，較CDP算法提高1.9%。在標(biāo)準(zhǔn)化互信息上較原DPC算法提高7.8%，較CDP算法提高3.7%。

人臉數(shù)據(jù)集orl為樣本維度較高的數(shù)據(jù)集，在orl數(shù)據(jù)集上的實驗結(jié)果顯示，本文算法在兩個指標(biāo)上的表現(xiàn)低于CDP算法，高于原DPC算法。本文算法較原DPC算法在準(zhǔn)確率上提高3%，較CDP算法低7%。在標(biāo)準(zhǔn)化互信息上較原DPC算法提高2.6%，較CDP算法低4.4%。

從上述實際數(shù)據(jù)集的計算結(jié)果比較可看出，對于特征復(fù)雜的實際數(shù)據(jù)集，本文引入式(14)的最優(yōu)協(xié)方差矩陣用于描述數(shù)據(jù)集不同維度(特征變量)間的相關(guān)性，并在式(6)計算樣本相似度時考慮了各特征維度的重要程度，式(18)利用此相似度計算樣本的密度值后，通過計算出的密度值能更容易判別樣本的歸屬簇，例如在waveform、ionosphere、ecoli數(shù)據(jù)集上，本文算法能夠在密度不一的簇中尋找到合適的簇中心，并使非中心點能夠更正確地進(jìn)行分配，進(jìn)而提高了DPC的聚類精度。

綜述上所述，本文引入最優(yōu)密度估計改進(jìn)DPC的密度計算后，所提算法在UCI真實數(shù)據(jù)集上優(yōu)于相比較的其它DPC改進(jìn)算法，因此本文改進(jìn)DPC的思路是可行的、有效的。

5 結(jié)束語

傳統(tǒng)的DPC算法的密度計算存在dc參數(shù)優(yōu)化等缺陷，造成算法對沒有特定形狀的實際數(shù)據(jù)集聚類精度欠佳，針對此問題，本文利用Oracle最優(yōu)逼近估計和K近鄰算法計算數(shù)據(jù)樣本的密度，避免了截斷閾值dc取值對密度計算的不良影響，從而提高了DPC對實際數(shù)據(jù)集的特征辨識能力，提高了算法的聚類精度。在UCI真實數(shù)據(jù)集上的實驗結(jié)果顯示，本文算法能夠有效地提高DPC的聚類精度，具有良好的適用性。綜上所述，所提改進(jìn)DPC的思路是可行的。