覃 華，劉 政，蘇一丹

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

0 引 言

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

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

1 DPC的基本概念

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

(1)

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

(2)

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

樣本點(diǎn)與比其密度大且離其最近的點(diǎn)的距離δi的計(jì)算如下

(3)

對于密度最大的點(diǎn)

(4)

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

γi=ρiδi

(5)

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

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

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

(6)

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

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

(7)

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

(8)

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

(9)

(10)

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

(11)

(12)

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

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

(13)

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

(14)

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

(15)

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

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

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

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

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

(16)

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

(17)

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

(18)

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

所提算法流程如下：

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

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

步驟1 計(jì)算樣本點(diǎn)間的歐式距離dij。

步驟3 使用式(3)和式(4)計(jì)算樣本點(diǎn)的δi。

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集說明

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

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

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

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

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

本文算法與DPC算法[1]在人工數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較如圖3～圖6所示，被分為同一簇的樣本點(diǎn)在圖中擁有相同的形狀和灰度。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é)果顯示，在有兩個(gè)不同密度簇的數(shù)據(jù)集Jain上，DPC錯(cuò)誤的將密集程度相對較高的簇的樣本點(diǎn)選為密集程度相對較低的簇的中心，導(dǎo)致聚類結(jié)果不理想。而本文算法能夠正確找出不同密度簇的簇中心，并正確的對剩余點(diǎn)進(jìn)行分配，得到正確的聚類結(jié)果。

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

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

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

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

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

在UCI真實(shí)數(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)行評估，兩個(gè)指標(biāo)的取值范圍均為[0,1]，取值越大，表示得到的聚類結(jié)果越好。實(shí)驗(yàn)結(jié)果對比詳見表3和表4，兩表中的符號(hào)“-”表示相應(yīng)文獻(xiàn)未給出該數(shù)據(jù)集的計(jì)算結(jié)果，無法在此數(shù)據(jù)集進(jìn)行結(jié)果比較。

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

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

從表3和表4的實(shí)驗(yàn)結(jié)果對比得出。在iris數(shù)據(jù)集上對比原DPC算法與CDP算法和FN-DP算法，本文算法在兩個(gè)評估指標(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算法使用模糊邏輯原理，使樣本點(diǎn)的局部密度更能反映局部信息，而本文算法使用KNN馬氏距離能使樣本點(diǎn)的局部密度能更好反映局部信息。

在seeds數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果顯示，本文算法在兩個(gè)指標(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的實(shí)驗(yàn)結(jié)果顯示，本文算法在兩個(gè)指標(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的實(shí)驗(yàn)結(jié)果顯示，本文算法在兩個(gè)指標(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的實(shí)驗(yàn)結(jié)果顯示，本文的算法在兩個(gè)指標(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上的實(shí)驗(yàn)結(jié)果顯示，本文的算法在兩個(gè)指標(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ù)集上的實(shí)驗(yàn)結(jié)果顯示，本文的算法在兩個(gè)指標(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ù)集上的實(shí)驗(yàn)結(jié)果顯示，本文算法在兩個(gè)指標(biāo)上的表現(xiàn)低于CDP算法，高于原DPC算法。本文算法較原DPC算法在準(zhǔn)確率上提高3%，較CDP算法低7%。在標(biāo)準(zhǔn)化互信息上較原DPC算法提高2.6%，較CDP算法低4.4%。

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

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

5 結(jié)束語

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