基于KL散度的密度峰值聚類算法

丁志成，葛洪偉，周 競

(1.江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214122；2. 江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

0 引 言

聚類是根據(jù)某些特定的準(zhǔn)則，通過在數(shù)據(jù)中發(fā)現(xiàn)的對(duì)象及其關(guān)系將未劃分類的數(shù)據(jù)分割為不同的簇，令同一簇內(nèi)數(shù)據(jù)點(diǎn)相似性盡可能大，同時(shí)不同簇間的數(shù)據(jù)點(diǎn)相似性盡可能小[1]的分析方法。聚類作為一種無先驗(yàn)知識(shí)的統(tǒng)計(jì)方法，能夠分析數(shù)據(jù)的聚類屬性、潛在結(jié)構(gòu)以及數(shù)據(jù)存儲(chǔ)容量[2-3]，是數(shù)據(jù)挖掘的重要分支[4]，如今其在模式識(shí)別、web搜索、人工智能、生物及航天等領(lǐng)域[5-6]已得到普遍推廣和應(yīng)用。

如今有許多優(yōu)秀的算法被相繼提出，其中最為典型的算法有基于劃分的K-means[7]，K-medoids[8]聚類；基于網(wǎng)格的STING[9]聚類；基于層次的CURE[10]聚類以及基于密度的DBSCAN[11]，OPTICS[12]聚類算法。其中，密度聚類DBSCAN算法相較于基于劃分和基于層次的聚類而言，具有無需事先確定生成簇的數(shù)量、可以探測擁有任何形狀簇類的優(yōu)點(diǎn)。算法對(duì)整個(gè)數(shù)據(jù)空間進(jìn)行鄰域搜索，能夠有效識(shí)別正確的簇并且可以準(zhǔn)確發(fā)現(xiàn)離群點(diǎn)。但DBSCAN也具有明顯的缺陷：算法調(diào)用的是全局鄰域值，對(duì)局部密度的變化趨勢不能有效反映，無法有效處理密度不均勻的數(shù)據(jù)集且算法對(duì)輸入?yún)?shù)十分敏感。盡管之后也提出過一些針對(duì)以上缺點(diǎn)的改進(jìn)算法但許多缺陷仍無法避免。

2014年，Alex，Alessandro等提出了一種新的基于密度的聚類算法：快速搜索與發(fā)現(xiàn)密度峰值聚類(clustering by fast search and find of density peaks, DPC)[13]算法。DPC算法無需額外參數(shù)，通過決策圖人工選取聚類中心后將其余數(shù)據(jù)點(diǎn)自動(dòng)分配到相應(yīng)聚類中心從而完成聚類。盡管DPC算法簡單高效，卻無法自動(dòng)確定聚類中心，特別是選取一些特殊的密度峰值點(diǎn)時(shí)人工操作容易出現(xiàn)錯(cuò)誤。針對(duì)這一缺點(diǎn)，本文擬通過引入新的聚類中心選擇策略，提出一種基于KL散度的密度峰值聚類算法(density peaks clustering based on Kullback-Leibler divergence，KLDPC)。KLDPC算法可以根據(jù)KL散度的差異性度量準(zhǔn)則賦予數(shù)據(jù)點(diǎn)一個(gè)新的Dkl值，并在Dkl排序圖上通過拐點(diǎn)分辨出聚類中心點(diǎn)，從而自動(dòng)確定聚類中心。實(shí)驗(yàn)證明， KLDPC提高了算法的準(zhǔn)確率，擺脫了經(jīng)驗(yàn)值影響及復(fù)雜的人工干預(yù)，可以獲得更優(yōu)的聚類效果。

1 DPC算法及其缺陷

DPC算法只需要一個(gè)輸入?yún)?shù)，無需預(yù)先指定簇類數(shù)量，能夠自動(dòng)生成相應(yīng)簇類并一步完成簇的分配。算法將滿足下列條件的數(shù)據(jù)點(diǎn)定義為聚類中心點(diǎn)：被局部密度相對(duì)較低的數(shù)據(jù)點(diǎn)包圍并且這些點(diǎn)距離其他擁有更高局部密度的點(diǎn)有相對(duì)較大的距離。

對(duì)于數(shù)據(jù)點(diǎn)Xi，計(jì)算局部密度ρi為以dc為半徑的圓內(nèi)其他數(shù)據(jù)點(diǎn)的數(shù)目

(1)

dc=dround(P·M)

(2)

(2)式中：di為任意點(diǎn)間的歐式距離升序排列的結(jié)果；P取值為(0,1)；M=N(N-1)/2，N為數(shù)據(jù)總數(shù)；round(·)函數(shù)表示對(duì)P·M四舍五入取整數(shù)值；dc為可調(diào)參數(shù)，在實(shí)驗(yàn)中調(diào)試P的值選取最佳聚類。

距離具有更大密度的點(diǎn)的最短距離δi定義為

δi=min(dij),j:ρj>ρi

(3)

具有全局最高密度的數(shù)據(jù)點(diǎn)，默認(rèn)為聚類中心點(diǎn)，并令其δi=max(dij)。以下是DPC算法的具體步驟描述。

步驟1根據(jù)(1)式和(2)式，由對(duì)象數(shù)據(jù)集確定dc和所有數(shù)據(jù)點(diǎn)的局部密度ρi。

步驟2根據(jù)(3)式計(jì)算出所有點(diǎn)的δi并和ρi一起存儲(chǔ)在相對(duì)應(yīng)的記號(hào)中。

步驟3生成有關(guān)ρi和δi的關(guān)系決策圖(decision graph)并手動(dòng)選取聚類中心點(diǎn)。

步驟4將非聚類中心點(diǎn)分配到距離最近的聚類中心所屬類簇中并計(jì)算邊界區(qū)域密度。邊界區(qū)域密度定義為歸屬某簇但與其余簇所屬點(diǎn)間的間隔小于dc的點(diǎn)的數(shù)目。

步驟5對(duì)聚類結(jié)果進(jìn)行除噪：將局部密度ρi高于邊界區(qū)域密度的數(shù)據(jù)點(diǎn)視為所屬簇的核心點(diǎn)，否則視為噪聲點(diǎn)，完成聚類。

通過實(shí)驗(yàn)，我們發(fā)現(xiàn)DPC算法在面對(duì)以下情況時(shí)會(huì)產(chǎn)生較大誤差。

1)由于原DPC算法同時(shí)考察ρ和δ值，只有2個(gè)參數(shù)值同時(shí)滿足大于選取點(diǎn)時(shí)才會(huì)被選為聚類中心點(diǎn)。而事實(shí)上除了同時(shí)具有較大ρ和δ值的明顯的密度峰值點(diǎn)，有一些具有較大ρ和較小δ值或是較小ρ和較大δ值的點(diǎn)也可能作為聚類中心，如圖1所示，而這類數(shù)據(jù)點(diǎn)卻被忽略，導(dǎo)致聚類中心點(diǎn)出現(xiàn)少選、漏選。

圖1 DPC算法由決策圖1a少選聚類中心Fig.1 DPC gets less clusters by decision graph 1a

2)因?yàn)閮H關(guān)注ρ和δ值整體的大小，并沒有研究參數(shù)值變化的趨勢，也會(huì)在人工選取具有較多簇類中心的數(shù)據(jù)集時(shí)造成多選聚類中心的結(jié)果，導(dǎo)致同一個(gè)簇的點(diǎn)被錯(cuò)誤地劃分為多個(gè)簇，如圖2所示。

圖2 DPC算法由決策圖2a多選聚類中心Fig.2 DPC gets more clusters by decision graph 2a

觀察圖2a可以發(fā)現(xiàn)，同時(shí)具有較大ρ和δ值的點(diǎn)有10個(gè)，而正確的簇類中心為7個(gè)，因此，通過人工選取并不能準(zhǔn)確選取聚類真正的中心。而如果在選擇聚類中心出現(xiàn)了錯(cuò)誤，那么在接下來的數(shù)據(jù)點(diǎn)分配簇類上會(huì)產(chǎn)生連鎖反應(yīng)，最終使得聚類效果不理想。即便利用密度峰值算法的決策圖選取到了正確的聚類中心，也是通過了大量的手動(dòng)選取、反復(fù)對(duì)比所得到的理想狀態(tài)下的最優(yōu)效果，在工程應(yīng)用中并無實(shí)際意義。

3)處理高維數(shù)據(jù)或數(shù)據(jù)量大的數(shù)據(jù)集時(shí)，更難以選擇聚類中心，需要大量的嘗試，并且因?yàn)镈PC的選取原則，部分點(diǎn)會(huì)由于數(shù)據(jù)過密導(dǎo)致無法準(zhǔn)確選取。

2 基于KL散度的密度峰值聚類算法

2.1 聚類中心選擇策略

定義1γi為衡量點(diǎn)i是否為聚類中心點(diǎn)的參數(shù)，稱之為中心指標(biāo)，定義為

γi=ρi·δi

(4)

對(duì)于具有較大ρ或δ的聚類中心來說，γ值也具有較大值，因此，γ可作為判斷數(shù)據(jù)點(diǎn)能否作為聚類中心的標(biāo)準(zhǔn)。記數(shù)據(jù)集為U(x)，數(shù)據(jù)點(diǎn)總數(shù)為N，排序圖選取樣本比例為Pγ，對(duì)γi進(jìn)行降序排列，做前NP=[N·Pγ] 個(gè)數(shù)據(jù)點(diǎn)的γ排序圖。對(duì)γ排序圖進(jìn)行實(shí)驗(yàn)可避免由于單獨(dú)考察ρ或δ所帶來的誤差。

本文通過大量實(shí)驗(yàn)選用γ排序圖的比例Pγ=4%作為經(jīng)驗(yàn)值進(jìn)行相關(guān)數(shù)據(jù)實(shí)驗(yàn)，不同聚類中心指標(biāo)在數(shù)據(jù)集aggregation上的表現(xiàn)效果如圖3所示。從圖3a可看出，由于存在多個(gè)拐點(diǎn)，所以僅憑γ排序圖很難區(qū)分出數(shù)據(jù)集的聚類中心點(diǎn)。通過觀察可知，疑似聚類中心的數(shù)據(jù)點(diǎn)都有較高的相似度,而非聚類中心點(diǎn)的γ值數(shù)值較低且趨于一致。因此，本文擬用KL散度的概念對(duì)γ進(jìn)行再處理以得到KL中心指標(biāo)來確定正確的聚類中心。

圖3 不同聚類中心指標(biāo)在數(shù)據(jù)集aggregation上的 表現(xiàn)效果Fig.3 Effects of different central indexes for dataset aggregation

定義2KL中心指標(biāo)為基于KL散度的參數(shù)指標(biāo)，用于描述數(shù)據(jù)集點(diǎn)與其他點(diǎn)γ值的差異度之和，差異度越大，值越趨近于0。公式表示為

(5)

KL散度即相對(duì)熵[14]，原定義為在相同的事件空間中，2個(gè)概率分布P(x)，Q(x)的差異程度，得到的KL散度為概率分布中每個(gè)點(diǎn)的差異度累加值，值越大，差異越大。

(6)

由于同樣是描述點(diǎn)集的數(shù)據(jù)相似度并且擁有一致的參數(shù)取值區(qū)間，本文在考察數(shù)據(jù)點(diǎn)是否為聚類中心時(shí)，選擇運(yùn)用此差異性度量準(zhǔn)則加以判別。已知在概率分布間，通過KL散度能夠?qū)﹄x散概率進(jìn)行定量的計(jì)算。而將相對(duì)熵的差異性度量準(zhǔn)則應(yīng)用到點(diǎn)的分布上雖然無法定量計(jì)算，但通過實(shí)驗(yàn)證明，其依然可以滿足對(duì)數(shù)據(jù)點(diǎn)是否為聚類中心的定性的劃分。

(7)

在數(shù)據(jù)集中，僅有少數(shù)點(diǎn)是聚類中心點(diǎn)。所以對(duì)于聚類中心而言，多數(shù)與之差異度很大，因此，Dkl值較?。幌喾?，非聚類中心點(diǎn)的Dkl值則很大。所以利用KL中心指標(biāo)可以將兩者清楚地劃分，以便選取到正確的聚類中心。對(duì)于更多的數(shù)據(jù)集，γ排序圖與Dkl排序圖的對(duì)比效果如圖4—圖7所示。

圖4 數(shù)據(jù)集spiral的γ排序圖和Dkl排序圖的對(duì)比 (維數(shù)為2，類別為3)Fig.4 Comparison of γ sorting graph and Dkl sorting graph on spiral with 2 dimensions and 3 clusters

圖5 數(shù)據(jù)集wine的γ排序圖和Dkl排序圖的對(duì)比 (維數(shù)為15，類別為3)Fig.5 Comparison of γ sorting graph and Dkl sorting graph on wine with 15 dimensions and 3 clusters

圖6 數(shù)據(jù)集seeds的γ排序圖和Dkl排序圖的對(duì)比 (維數(shù)為7，類別為3)Fig.6 Comparison of γ sorting graph and Dkl sorting graph on seeds with 7 dimensions and 3 clusters

由實(shí)驗(yàn)效果圖可知，無論是在高維(數(shù)據(jù)集seeds，wine)還是在低維(數(shù)據(jù)集spiral，test)的處理上，使用KL中心指標(biāo)的Dkl排序圖總比γ排序圖能獲得更優(yōu)的聚類效果，并且Dkl排序圖上的聚類中心與其他點(diǎn)間存在一個(gè)Dkl值增長幅度最大的拐點(diǎn)cn，在此，可以引入該點(diǎn)作為KL中心指標(biāo)的分界點(diǎn)。

定義3將Dkl排序圖中位于拐點(diǎn)cn前的i個(gè)點(diǎn)稱作候選聚類中心cci，滿足條件

cci={i|i<=cn,i=1,2,…,NP}

cn={j|max(sj),j=2,3,…,NP-1}

(8)

圖7 數(shù)據(jù)集test的γ排序圖和Dkl排序圖的對(duì)比 (維數(shù)為2，類別為3)Fig.7 Comparison of γ sorting graph and Dkl sorting graph on test with 2 dimensions and 3 clusters

2.2 KLDPC算法步驟

綜上所述，KLDPC算法的具體步驟描述如下。

輸入：實(shí)驗(yàn)數(shù)據(jù)集U(x)={x1,x2, …,xn}，數(shù)據(jù)點(diǎn)的近鄰點(diǎn)數(shù)目占數(shù)據(jù)總數(shù)的比例P。

輸出：聚類結(jié)果。

步驟1通過P值計(jì)算截?cái)嗑嚯xdc。

步驟2計(jì)算數(shù)據(jù)集中所有點(diǎn)的局部密度ρi以及最短距離δi。

步驟3計(jì)算Dkl并升序排列，以Dkl排序圖的拐點(diǎn)作為分界點(diǎn)篩選出聚類中心cci。

步驟4根據(jù)DPC原文定義，將γ值最大點(diǎn)定義為實(shí)際聚類中心，在候選聚類中心cci中計(jì)算距離dist(i,j)，其中，idc，點(diǎn)j被確定為聚類中心，否則，被歸并到i點(diǎn)所屬的簇類中。

步驟5重復(fù)步驟4，直到j(luò)=cci，自動(dòng)選取所有的聚類中心點(diǎn)。

步驟6將其余點(diǎn)分配到最近的聚類中心點(diǎn)，通過計(jì)算邊界地區(qū)密度進(jìn)行去噪處理，完成聚類。

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

假定聚類實(shí)驗(yàn)的數(shù)據(jù)集共有n個(gè)數(shù)據(jù)，根據(jù)第1節(jié)的描述，DPC算法的時(shí)間復(fù)雜度主要由計(jì)算歐式距離(O(n2))、對(duì)歐式距離進(jìn)行快速排序降序排列(O(n2lbn))和計(jì)算ρ和δ(O(n2))組成，因此，DPC的時(shí)間復(fù)雜度為O(n2lbn)。而根據(jù)2.2節(jié)的描述，KLDPC在對(duì)歐式距離的計(jì)算、降序排列和參數(shù)ρ和δ的處理上與DPC算法一致，而計(jì)算γ，KL中心指標(biāo)Dkl的時(shí)間復(fù)雜度為O(n2lbn)，自動(dòng)選取聚類中心的復(fù)雜度為O(n2)，去噪處理的時(shí)間復(fù)雜度為O(n2)。綜上所述，KLDPC的算法時(shí)間復(fù)雜度也為O(n2lbn)。

3 仿真實(shí)驗(yàn)與性能分析

為驗(yàn)證KLDPC算法的效果與性能，本文將KLDPC算法與DPC算法、同樣自動(dòng)確定密度峰值聚類中心的，基于全局簇中心權(quán)值的CFSFDP算法[15]和基于γ線性擬合的DenPEHC[16]算法分別在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。

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

在仿真實(shí)驗(yàn)中，使用如表1所示的相關(guān)信息的3個(gè)人工數(shù)據(jù)集，依次運(yùn)行CFSFDP，DenPEHC，DPC和KLDPC算法，實(shí)驗(yàn)效果如圖8—圖11所示。

表1 3個(gè)人工數(shù)據(jù)集信息Tab.1 Three synthetic data sets

圖8 CFSFDP算法在人工數(shù)據(jù)集上的聚類結(jié)果Fig.8 Clustering results on synthetic datasets by CFSFDP

圖8為CFSFDP算法得到的聚類效果圖，算法利用全局簇中心權(quán)值只能在數(shù)據(jù)集aggregation上得到正確的聚類結(jié)果，無法準(zhǔn)確處理環(huán)形簇和密集的團(tuán)狀簇。圖9為DenPEHC算法在人工數(shù)據(jù)集上的聚類結(jié)果，圖9中的DenPEHC算法雖然在數(shù)據(jù)集spiral和DS31上可以得到正確的聚類結(jié)果，但是將數(shù)據(jù)集aggregation錯(cuò)誤地分成了10個(gè)簇類，算法無法處理分布不均勻的球形簇。圖10為DPC算法在人工數(shù)據(jù)集上的聚類結(jié)果，圖10中的DPC算法能夠在大量嘗試后通過人工挑選比對(duì)，得到理想狀態(tài)下的聚類效果，但卻有很大的不確定性，算法不夠穩(wěn)定。圖11為KLDPC算法在人工數(shù)據(jù)集上的聚類結(jié)果，圖11中的KLDPC算法在DPC的基礎(chǔ)上，通過引入?yún)?shù)γ擴(kuò)大了聚類中心的選取范圍、應(yīng)用KL散度的差異性度量準(zhǔn)則從而科學(xué)有效地區(qū)分出聚類中心點(diǎn)、使用Dkl排序圖自動(dòng)確定聚類中心以跳過手工選取階段，這3個(gè)方法分別解決了原DPC算法存在的少選、多選以及無法準(zhǔn)確選取聚類中心點(diǎn)的問題。最終算法可以對(duì)環(huán)形、團(tuán)狀、球狀這3類數(shù)據(jù)集都自動(dòng)選取到正確的類簇。上述實(shí)驗(yàn)證明，KLDPC算法避免了DPC算法需要手動(dòng)經(jīng)驗(yàn)選取合適的聚類中心的不足，并且較之部分自動(dòng)確定聚類中心的密度峰值算法，KLDPC能夠更準(zhǔn)確地選取數(shù)據(jù)集的聚類中心。

圖9 DenPEHC算法在人工數(shù)據(jù)集上的聚類結(jié)果Fig.9 Clustering results on synthetic datasets by DenPEHC

圖10 DPC算法在人工數(shù)據(jù)集上的聚類結(jié)果Fig.10 Clustering results on Synthetic datasets by DPC

圖11 KLDPC算法在人工數(shù)據(jù)集上的聚類結(jié)果Fig.11 Clustering results on Synthetic datasets by KLDPC

3.2 UCI數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析

為了進(jìn)一步驗(yàn)證KLDPC算法的性能，采用F-measure[17]與ARI[18]兩類聚類評(píng)價(jià)指標(biāo)并利用4個(gè)真實(shí)數(shù)據(jù)集的信息對(duì)4種算法進(jìn)行對(duì)比實(shí)驗(yàn)，如表2所示。

兩類聚類評(píng)價(jià)指標(biāo)的取值為[0,1]，數(shù)值越大代表聚類效果越好。實(shí)驗(yàn)結(jié)果如表3、表4所示(正確的聚類中心數(shù)和最優(yōu)的聚類效果數(shù)值都已加下劃線表示)

表2 4個(gè)真實(shí)數(shù)據(jù)集信息Tab.2 Four real data sets

由表3、表4的實(shí)驗(yàn)結(jié)果可知， KLDPC和DPC算法都可以得到4個(gè)真實(shí)數(shù)據(jù)集的聚類中心點(diǎn)的準(zhǔn)確個(gè)數(shù)，而CFSFDP和DenPEHC算法則都只能得到其中2個(gè)正確的聚類中心點(diǎn)。由聚類評(píng)價(jià)指標(biāo)值可見，KLDPC算法在使用F-measure和ARI兩類評(píng)價(jià)指標(biāo)時(shí)除了在數(shù)據(jù)集seeds上結(jié)果相同，在其他數(shù)據(jù)集上均對(duì)DPC進(jìn)行了一定的提升，并且皆是4種算法中最優(yōu)的聚類效果。綜上，KLDPC算法對(duì)DPC算法進(jìn)行了成功改進(jìn)并且相對(duì)其他的改進(jìn)算法，能夠得到更好的聚類效果和更高的聚類中心準(zhǔn)確率。

表3 4種算法在真實(shí)數(shù)據(jù)集上的F-measure值和中心數(shù)Tab.3 F-measure index value and centers of four methods on real data sets

表4 4種算法在真實(shí)數(shù)據(jù)集上的ARI值和中心數(shù)Tab.4 ARI index value and centers of three methods on real data sets

4 結(jié)束語

針對(duì)DPC需要人工選取聚類中心的問題，本文提出了一種KLDPC算法。該算法在繼承了原算法迅捷高效優(yōu)勢的同時(shí)，去除了復(fù)雜的人工，實(shí)現(xiàn)了聚類中心的自動(dòng)確定，并使選取聚類中心的準(zhǔn)確度得到了一定的提升。通過人工以及真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)皆可證明，和原DPC算法以及部分密度峰值優(yōu)化算法相比，KLDPC算法具有更好的準(zhǔn)確率以及更優(yōu)的聚類效果。

但KLDPC算法主要是對(duì)選取聚類中心進(jìn)行優(yōu)化改進(jìn)，對(duì)于具有復(fù)雜數(shù)據(jù)集結(jié)構(gòu)的對(duì)象來說，算法仍有可能無法獲得理想的聚類效果。針對(duì)這一問題，需要考慮使用合適的距離度量來更好地反映數(shù)據(jù)間的相對(duì)關(guān)系并且需要進(jìn)一步改進(jìn)算法的分配機(jī)制。因此，如何使KLDPC算法能夠更有效地處理具有復(fù)雜數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)集，將會(huì)是下一步的研究目標(biāo)。