基于隨機(jī)游走的密度峰值聚類算法

占志文，劉君

(南昌大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，江西 南昌 330031)

聚類的主要目的是對一組對象進(jìn)行分類，使得同一類對象盡可能相似，異類之間的對象盡量不相似[1]。聚類算法在模式識別、圖像處理、風(fēng)險管理和生物信息學(xué)等領(lǐng)域中得到了廣泛的應(yīng)用[2-3]。聚類算法一般可以分為：基于劃分的方法、基于密度的方法、基于層次的方法、基于圖論的方法、基于網(wǎng)格的方法[4-8]。K-means[9]是一種經(jīng)典的劃分聚類算法，該算法只適用于球狀簇，且聚類結(jié)果易受初始聚類中心的影響?；诿芏鹊脑肼晳?yīng)用空間聚類(DBSCAN)算法[10]，可以找到任意形狀的簇，但其聚類結(jié)果易受閾值和鄰域半徑這兩個參數(shù)的影響。

Rodriguez等[11]提出了密度峰值聚類(density peaks clustering,DPC)算法，該算法認(rèn)為聚類中心的密度高于其周圍數(shù)據(jù)點(diǎn)的密度，且與其他高密度的數(shù)據(jù)點(diǎn)距離較遠(yuǎn)。但是該算法僅根據(jù)數(shù)據(jù)點(diǎn)之間的歐氏距離計(jì)算局部密度以及相對距離，不適用于形狀、密度復(fù)雜的數(shù)據(jù)集；在基于距離分配數(shù)據(jù)點(diǎn)時，算法魯棒性低，而且聚類結(jié)果對于截?cái)嗑嚯x較敏感。

針對DPC存在的問題，Liu等[1]基于共享最近鄰計(jì)算數(shù)據(jù)點(diǎn)之間的局部密度和相對距離，可以對復(fù)雜密度的數(shù)據(jù)集進(jìn)行有效聚類；Hou等[12]根據(jù)數(shù)據(jù)點(diǎn)之間的密度與距離關(guān)系計(jì)算數(shù)據(jù)點(diǎn)之間的從屬關(guān)系來計(jì)算數(shù)據(jù)點(diǎn)的局部密度；Xu等[13]基于數(shù)據(jù)點(diǎn)之間的最短距離重新構(gòu)建數(shù)據(jù)點(diǎn)之間的距離，然后再根據(jù)新的距離對數(shù)據(jù)點(diǎn)進(jìn)行聚類分析；Cheng等[14]基于自然k最近鄰來計(jì)算數(shù)據(jù)點(diǎn)之間的局部密度。

為了解決DPC算法的問題，本文提出了一種基于隨機(jī)游走的密度峰值聚類算法。假設(shè)數(shù)據(jù)點(diǎn)會向其最近K個數(shù)據(jù)點(diǎn)進(jìn)行概率轉(zhuǎn)移，通過到達(dá)概率來計(jì)算數(shù)據(jù)點(diǎn)的局部密度，并且利用首次到達(dá)概率來計(jì)算數(shù)據(jù)點(diǎn)之間的相對距離。同時本文設(shè)計(jì)了一種逐步分配數(shù)據(jù)點(diǎn)的分配方法，使得算法的魯棒性更強(qiáng)。進(jìn)行了多次的實(shí)驗(yàn)，其結(jié)果表明本文所提的算法有較好的聚類性能。

1 DPC算法及其分析

1.1 DPC算法

DPC算法通過快速搜索和密度峰值查找，構(gòu)造決策圖來人工選擇聚類中心，采用一種跟隨策略對數(shù)據(jù)進(jìn)行聚類，能夠快速發(fā)現(xiàn)任意形狀數(shù)據(jù)集的密度峰值點(diǎn)，是一種快速的、高效的聚類算法。DPC算法基于兩個假設(shè)：聚類中心的局部密度高于其周圍的數(shù)據(jù)點(diǎn)的局部密度；不同的聚類中心之間有較大的距離?；谶@兩個假設(shè)，DPC算法的精髓之處就是在定義樣本點(diǎn)xi的局部密度ρi的基礎(chǔ)上，進(jìn)一步定義樣本點(diǎn)xi到局部密度比它大且距離它最近的樣本xj的距離δi，其定義如下所示：

(1)

(2)

式中：dij為數(shù)據(jù)對象之間的距離；dc為截?cái)嗑嚯x，由人工確定，通常是所有的數(shù)據(jù)對象之間的距離按升序排列后取2%位置處的數(shù)值作為截?cái)嗑嚯x。當(dāng)數(shù)據(jù)集較小時式(1) 局部密度ρi的定義對于截?cái)嗑嚯xdc非常敏感，因此會采用式(2)的局部密度定義。相對距離δi的定義如下：

(3)

由式(3)看出，δi是比數(shù)據(jù)點(diǎn)xi局部密度更大且離它最近數(shù)據(jù)點(diǎn)的距離，當(dāng)數(shù)據(jù)點(diǎn)為所有數(shù)據(jù)點(diǎn)中局部密度最大時，將擁有最大的相對距離。為了簡化聚類中心的選擇，DPC算法計(jì)算每個數(shù)據(jù)點(diǎn)的決策值γi，式(4)給出了定義：

γi=ρi·δi

(4)

DPC算法聚類過程主要分為兩個步驟。第1步：對于每個數(shù)據(jù)點(diǎn)xi首先需要計(jì)算其二維數(shù)組(ρi,δi)，畫出二維決策圖，決策圖中低ρ高δ將其看作為噪聲點(diǎn)，對于決策圖上高ρ高δ視為聚類中心;第2步：數(shù)據(jù)點(diǎn)分配，將剩余的數(shù)據(jù)分配給比其局部密度大的最近的數(shù)據(jù)點(diǎn)所在的類簇。

1.2 DPC算法分析

雖然文獻(xiàn)[11]用了很多的實(shí)驗(yàn)結(jié)果來證明DPC算法在許多的情況下都能取得很好的效果，但是它的缺點(diǎn)也很明顯。

(1) DPC算法有兩種不同的局部密度定義公式，對于比較大的數(shù)據(jù)集采用式(1)cut-off kernel來定義，計(jì)算領(lǐng)域內(nèi)的數(shù)據(jù)點(diǎn)的個數(shù)作為局部密度，對截?cái)嗑嚯x依賴性較強(qiáng)。而對于較小的數(shù)據(jù)集則采用Gaussian kernel來定義，計(jì)算公式如式(2)所示，這種方式考慮了每個點(diǎn)與其他點(diǎn)的距離，計(jì)算量偏大，并且不能完全體現(xiàn)出每個點(diǎn)的局部密度信息。而且對于數(shù)據(jù)集的大小沒有一個客觀的判斷標(biāo)準(zhǔn)，需要主觀意識來判斷。局部密度定義的方法選擇不一樣，得出來的聚類結(jié)果就會不同，如圖1所示。

(2) 對于一些弧形較大較長以及稀疏差別較大的類簇不能很好地進(jìn)行聚類，如圖2所示。其原因是DPC算法在計(jì)算相對距離時直接采用了歐式距離，采用歐式距離定義相對距離并不能準(zhǔn)確度量出數(shù)據(jù)點(diǎn)的差異性。

(3) DPC算法在分配策略上沒有很強(qiáng)的魯棒性，有時會因?yàn)?個數(shù)據(jù)點(diǎn)的分配錯誤而造成后續(xù)很多數(shù)據(jù)點(diǎn)的分配錯誤，并且沒有考慮數(shù)據(jù)點(diǎn)局部分布情況。

2 基于隨機(jī)游走的密度峰值聚類

2.1 相關(guān)定義

設(shè)樣本數(shù)據(jù)集X={x1,x2,…,xn}，其中每樣本點(diǎn)xi有p個屬性。

(a) Guass kernel

(b) cut-off kernel圖1 DPC算法在Flame數(shù)據(jù)集上的聚類效果Fig.1 Clustering results of DPC algorithm on Flame data set

(a) 原始數(shù)據(jù)分布

x(b) Guass kernel 局部密度

(c) Guass kernel相對距離

(d) Guass kernel聚類結(jié)果圖2 DPC算法在Jain數(shù)據(jù)集上的聚類效果Fig.2 Clustering results of DPC algorithm on Jain data set

定義1由K近鄰來定義一步轉(zhuǎn)移概率矩陣P

(5)

式中：dij為數(shù)據(jù)點(diǎn)xi與數(shù)據(jù)點(diǎn)xj之間的歐氏距離，而KNN(i)表示離數(shù)據(jù)點(diǎn)xi最近的K個數(shù)據(jù)點(diǎn)的集合。并且設(shè)定pii=0即數(shù)據(jù)點(diǎn)xi不會在本身停留。由此可得到數(shù)據(jù)點(diǎn)之間的n階隨機(jī)游走矩陣:

P(n)=P(n-1)P(1)

(6)

當(dāng)任意數(shù)據(jù)點(diǎn)不再游走到達(dá)新的數(shù)據(jù)點(diǎn)時，則停止隨機(jī)游走并記為Pn0。

定義2(首次轉(zhuǎn)移到達(dá)概率矩陣)假設(shè)n階隨機(jī)游走矩陣為任意兩個數(shù)據(jù)點(diǎn)之間的首次轉(zhuǎn)移到達(dá)概率矩陣S:

(7)

定義3(不相似矩陣)由首次到達(dá)概率矩陣得到任意兩個數(shù)據(jù)點(diǎn)之間的不相似矩陣M，其定義如下：

(8)

(9)

(10)

定義6數(shù)據(jù)點(diǎn)的決策值：

(11)

根據(jù)定義4和定義5求得局部密度和相對距離后，畫出其決策二維圖，選取聚類中心。

2.2 數(shù)據(jù)點(diǎn)分配方法

DPC算法的數(shù)據(jù)點(diǎn)分配策略采用的是一步分配歸類，其魯棒性較差并且容錯率較低。本章考慮一種新的數(shù)據(jù)點(diǎn)分配方法。

經(jīng)過選取出c個聚類中心，將每個聚類中心的最近的K個數(shù)據(jù)點(diǎn)劃分到其類簇中形成c個集合S1,S2,…,Sc。然后構(gòu)建一個矩陣，其行數(shù)為所有數(shù)據(jù)點(diǎn)的數(shù)量，列數(shù)為聚類中心的數(shù)量。

步驟1計(jì)算R中的數(shù)值rij，即

(12)

步驟2若max(rij)=K，將數(shù)值為K的行數(shù)所代表的數(shù)據(jù)點(diǎn)分配給列數(shù)代表的類簇，返回步驟1；

若0

若max(rij)=0，結(jié)束數(shù)據(jù)點(diǎn)的分配。

2.3 算法流程

本算法的具體實(shí)現(xiàn)步驟如下。

輸入數(shù)據(jù)集D，類簇?cái)?shù)目c。

輸出聚類結(jié)果S1,S2,…,Sc。

步驟1根據(jù)式(5)計(jì)算得到數(shù)據(jù)點(diǎn)的一階概率轉(zhuǎn)移矩陣P。

步驟2根據(jù)式(6)及式(7)得到各數(shù)據(jù)點(diǎn)的首次到達(dá)概率矩陣S。

步驟3根據(jù)式(8)得到數(shù)據(jù)點(diǎn)之間的轉(zhuǎn)移距離矩陣M。

步驟4根據(jù)式(9)及式(10)計(jì)算出各數(shù)據(jù)點(diǎn)局部密度ρ′以及相對距離δ′。

步驟5根據(jù)式(11)計(jì)算出數(shù)據(jù)點(diǎn)的決策值γ′。

步驟6將步驟5得到的γ′按大到小選取前面的c個數(shù)據(jù)點(diǎn)作為聚類中心點(diǎn)。

步驟7將剩余的數(shù)據(jù)點(diǎn)按照2.2小節(jié)中的分配方法進(jìn)行分配。

步驟8返回聚類結(jié)果S1,S2,…,Sc。

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

本文RW-DPC算法保留了DPC算法尋找密度峰值的核心思想，通過隨機(jī)游走來刻畫數(shù)據(jù)點(diǎn)之間的距離，適用于任意規(guī)模的數(shù)據(jù)集。

DPC算法由于主要存儲了距離矩陣，因此它的空間復(fù)雜度為o(n2)(n為數(shù)據(jù)集中樣本數(shù))。RW-DPC算法主要是存儲隨機(jī)游走矩陣，因此它的空間復(fù)雜度為o(n0·n2)(n0?n)，而它的時間復(fù)雜度由以下幾部分決定：計(jì)算不相似矩陣、局部密度值ρ′、相對距離值δ′、樣本點(diǎn)分配。

對樣本數(shù)為n的數(shù)據(jù)集：得到樣本點(diǎn)不相似矩陣，時間復(fù)雜度為o(n2)；計(jì)算樣本點(diǎn)的局部密度ρ′，時間復(fù)雜度為o(n2)；計(jì)算每個樣本點(diǎn)的相對距離δ′，時間復(fù)雜度為o(n2)；樣本點(diǎn)分配，考慮樣本點(diǎn)的k近鄰，因此單個數(shù)據(jù)點(diǎn)的時間復(fù)雜度為o(kn)，總的時間復(fù)雜度為o(kn2)；因此RW-DPC算法的時間復(fù)雜度量級為o(n2)與DPC算法同一級別。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集與評價指標(biāo)

實(shí)驗(yàn)選擇6個人工合成數(shù)據(jù)集和4個來自UCI上的真實(shí)數(shù)據(jù)集以及1個人臉數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集的具體屬性如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental data set

在所有基準(zhǔn)數(shù)據(jù)集上比較聚類算法的精確度(ACC)、調(diào)整蘭德爾系數(shù)(ARI)、調(diào)整互信息(AMI)標(biāo)準(zhǔn)來衡量聚類結(jié)果的好壞。ACC標(biāo)準(zhǔn)的范圍為[0,1],ARI 和AMI的范圍都是[-1,1],這3個指標(biāo)其值越大表示聚類結(jié)果越好。

3.2 算法實(shí)驗(yàn)結(jié)果分析

在上述數(shù)據(jù)集本章算法將與K-means、DPC、DBSCAN算法進(jìn)行比較。其中DPC算法中需要確定dc的值，所有的數(shù)據(jù)對象之間的距離按升序排列后取2%位置處的數(shù)值作為dc，而DBSCAN算法的參數(shù)是根據(jù)實(shí)驗(yàn)聚類效果調(diào)到最優(yōu)，并且其會將數(shù)據(jù)點(diǎn)劃分為噪聲點(diǎn)，所以在聚類指標(biāo)只是用精確度(ACC)一個指標(biāo)。對于近鄰參數(shù)K的選取，如果K較小則會出現(xiàn)每個數(shù)據(jù)點(diǎn)都是獨(dú)立的簇，取值較大的話就會將一些類簇歸為一類中，因此我們一般選取的范圍為[7,50]。經(jīng)過多次的實(shí)驗(yàn)驗(yàn)證其最優(yōu)取值為8。

3.2.1 人工數(shù)據(jù)聚類結(jié)果可視化以及分析

根據(jù)各算法在人工數(shù)據(jù)集上的可視化結(jié)果圖3～圖8以及人工數(shù)據(jù)集的各算法的聚類指標(biāo)表2可得結(jié)論如下：由于K-means算法只能發(fā)現(xiàn)球狀的簇以及難以識別相近的類簇，K-means 算法在給出的數(shù)據(jù)集其聚類效果不佳；而DBSCAN算法在對分布稀疏的數(shù)據(jù)集會將其識別為噪聲點(diǎn)，因此DBSCAN算法除了在Jain以及Compound數(shù)據(jù)集上聚類效果不佳，在其他數(shù)據(jù)集上能夠很好識別；DPC算法對于分布疏密程度差異大以及分布跨度大的類簇的聚類效果不佳，所以在類簇分布跨度大的數(shù)據(jù)集，例如Threecircles、LineBlob、Sticks、Compound數(shù)據(jù)集以及分布疏密程度差異大的Jain數(shù)據(jù)集上聚類效果不佳；而RW-DPC算法能夠在分布疏密程度差異大以及分布跨度大的類簇進(jìn)行很好地識別。

由上述可得，在給出的人工數(shù)據(jù)集，RW-DPC算法優(yōu)于其他算法。

表2 人工數(shù)據(jù)集上各聚類算法的聚類評價指標(biāo)值Tab.2 Clustering evaluation index value of each clustering algorithm on manual data set

(a) RW-DPC

(b) DPC

(c) DBSCAN

(d) K-means

(a) RW-DPC

(b) DPC

(c) DBSCAN

(d) K-means

(a) RW-DPC

(b) DPC

(c) DBSCAN

(d) K-means

(a) RW-DPC

(b) DPC

(c) DBSCAN

(d) K-means

(a) RW-DPC

(b) DPC

(c) DBSCAN

(d) K-means

(a) RW-DPC

(b) DPC

(c) DBSCAN

(d) K-means

3.2.2 真實(shí)數(shù)據(jù)聚類結(jié)果可視化以及分析

真實(shí)實(shí)驗(yàn)數(shù)據(jù)集采用的是測試機(jī)器學(xué)習(xí)算法和數(shù)據(jù)挖掘算法性能的UCI數(shù)據(jù)庫中具有代表性的Iris數(shù)據(jù)集、Wine數(shù)據(jù)集、Seed數(shù)據(jù)集、Ionosphere數(shù)據(jù)集。從表3可以看出本文RW-DPC算法在4個真實(shí)數(shù)據(jù)集上的各個性能指標(biāo)都是優(yōu)于其他算法的，并且在Ionosphere數(shù)據(jù)集上其聚類效果顯著。

3.2.3 人臉數(shù)據(jù)聚類結(jié)果可視化以及分析

在對人臉數(shù)據(jù)集進(jìn)行聚類中，畫出本文RW-DPC以及DPC算法的決策值(γ)圖，如圖9所示，則本文算法確定的聚類類簇?cái)?shù)為8以及DPC算法確定的類簇?cái)?shù)為7。而K-means算法則是將其按照10個類簇進(jìn)行聚類，DBSCAN是進(jìn)行多次調(diào)參之后的最優(yōu)結(jié)果。從圖10可以看出對于人臉數(shù)據(jù)集聚類效果，本文RW-DPC算法最優(yōu)，其次是DPC算法、K-means算法以及DBSCAN算法。

表3 真實(shí)數(shù)據(jù)集上各聚類算法的聚類評價指標(biāo)值Tab.3 Clustering evaluation index value of each clustering algorithm on real data set

n(a) RW-DPC決策值

n(b) DPC決策值

(a) RW-DPC

(b) DPC

(c) DBSCAN

(d) K-means

4 結(jié)語

針對DPC算法在數(shù)據(jù)集的數(shù)據(jù)分布密度以及分布結(jié)構(gòu)復(fù)雜時的聚類結(jié)果不夠理想的問題，本文提出一種基于隨機(jī)游走的密度峰值聚類算法。引入隨機(jī)游走性能夠更加準(zhǔn)確體現(xiàn)出數(shù)據(jù)集數(shù)據(jù)分布結(jié)構(gòu)復(fù)雜時數(shù)據(jù)點(diǎn)之間的距離。通過游走概率使得數(shù)據(jù)點(diǎn)之間的轉(zhuǎn)移只和數(shù)據(jù)點(diǎn)的局部數(shù)據(jù)分布密度相關(guān)，消除不同類簇?cái)?shù)據(jù)點(diǎn)分布疏密不同的問題。另外，在對數(shù)據(jù)點(diǎn)進(jìn)行分配時，考慮數(shù)據(jù)點(diǎn)周圍數(shù)據(jù)點(diǎn)的分布與類簇的關(guān)系，使得算法有更強(qiáng)的魯棒性。同時，本文進(jìn)行了多次實(shí)驗(yàn)，在6個人工數(shù)據(jù)集和4個真實(shí)數(shù)據(jù)集以及1個人臉數(shù)據(jù)集上，針對K-means、DPC、DBSCAN算法進(jìn)行了實(shí)驗(yàn)比較，實(shí)驗(yàn)表明本文RW-DPC算法在多個數(shù)據(jù)集上的聚類結(jié)果都是優(yōu)于其他算法的。

對于數(shù)據(jù)集最優(yōu)近鄰參數(shù)K，本文是通過多次的實(shí)驗(yàn)來確定的。未來的工作將進(jìn)一步研究如何能夠自動地確定數(shù)據(jù)集的最優(yōu)近鄰參數(shù)K，使得算法具有更強(qiáng)的魯棒性。