基于密度峰值算法的三支聚類

姜冬勤,王平心,楊習(xí)貝

(1.江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院, 鎮(zhèn)江 212100)

(2.江蘇科技大學(xué) 理學(xué)院, 鎮(zhèn)江 212100)

傳統(tǒng)聚類算法大多屬于二支聚類,即類簇之間有著清晰的邊界,但在實(shí)際應(yīng)用中常常會遇到信息不充分的情況,如果將信息不充分的數(shù)據(jù)對象強(qiáng)行劃分到某一類簇,會造成誤分類的概率增加,導(dǎo)致聚類精度降低.針對傳統(tǒng)聚類方法的不足,文獻(xiàn)[1]將三支決策的思想引入到聚類分析中并提出了三支聚類算法[2-3].不同于傳統(tǒng)的硬聚類,三支聚類用核心域和邊界域來描述一個(gè)簇,能夠更加精確的描述類簇的結(jié)構(gòu)特征.基于這一框架,近年來,三支聚類研究也取得了大量的成果[4-8].文獻(xiàn)[9]提出了密度峰值聚類(clustering by fast search and find of density peaks, DPC)[9],可以識別任意一個(gè)形狀的類簇,而且可以自動地確定每個(gè)類簇的質(zhì)心,克服了DBSCAN面臨的不同類簇的密度差別大、鄰域范圍難以確定等問題.但DPC算法存在以下不足:① 截?cái)嗑嚯xdc需要人工設(shè)置,具有隨機(jī)性;② 假如一個(gè)樣本分配錯(cuò)誤,就會帶來后面一系列的分配錯(cuò)誤.

為了對DPC算法的優(yōu)化,文獻(xiàn)[10]提出利用k-近鄰來定義局部密度,且給了兩種新的分配策略;文獻(xiàn)[11]計(jì)算點(diǎn)到它的k-最近鄰點(diǎn)的距離作為局部密度,并使用k最近鄰點(diǎn)和模糊加權(quán)k-最近鄰點(diǎn)依次將剩余的點(diǎn)進(jìn)行分配;文獻(xiàn)[12]將k-最近鄰引入局部密度計(jì)算中并提出了新的分配策略,提高了聚類準(zhǔn)確度;文獻(xiàn)[13]提出基于共享最近鄰的DPC(SNN-DPC)算法,該算法結(jié)合共享最近鄰,不僅消除了截?cái)嗑嚯x對DPC算法的影響,也避免了連帶分配錯(cuò)誤,但其算法需要人工選擇k值,不可以做到自適應(yīng).

基于上述問題,文中引入了自然最近鄰算法,使得每個(gè)數(shù)據(jù)點(diǎn)的鄰居數(shù)不再依賴于手動設(shè)置的參數(shù),而是自適應(yīng)的根據(jù)每個(gè)點(diǎn)的自然最近鄰獲取鄰居個(gè)數(shù),以此來確定每個(gè)點(diǎn)的局部密度和距離,通過決策圖選取聚類中心,再融合三支決策思想,滿足論文中所給判定條件歸入核心域,再將剩余點(diǎn)分配到邊界域中,最終得到三支聚類的結(jié)果,數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的綜合性能.

1 相關(guān)工作

1.1 密度峰值聚類算法

密度峰值算法的核心思想是聚類中心滿足以下兩點(diǎn):① 聚類中心被密度比它低的近鄰點(diǎn)包圍;② 聚類中心之間的距離大.選取局部密度大、距最近的較大密度點(diǎn)的距離都很大的數(shù)據(jù)點(diǎn)作為聚類中心.因此DPC算法有兩個(gè)待計(jì)算量為局部密度ρi和數(shù)據(jù)點(diǎn)距離δi.

第i個(gè)數(shù)據(jù)點(diǎn)的局部密度ρi為:

(1)

第i個(gè)數(shù)據(jù)點(diǎn)距離是指數(shù)據(jù)點(diǎn)的局部密度大于ρi,且與第i個(gè)數(shù)據(jù)點(diǎn)最近的點(diǎn)與該數(shù)據(jù)點(diǎn)之間的相對距離:

(2)

具體密度峰值算法流程如下:

算法1 DPC算法輸入:數(shù)據(jù)集.輸出:每個(gè)數(shù)據(jù)點(diǎn)的所屬類簇.1: 初始化參數(shù):截?cái)嗑嚯xdc.2: ① 計(jì)算任意兩個(gè)數(shù)據(jù)點(diǎn)之間的距離;② 根據(jù)截?cái)嗑嚯x算出任意數(shù)據(jù)點(diǎn)的局部密度ρi;③ 對于任意數(shù)據(jù)點(diǎn)計(jì)算出其距離δi;④ 以ρi為橫軸,以δi為縱軸構(gòu)造出決策圖;⑤ 利用決策圖,選取ρi和δi都相對較大的值標(biāo)記為聚類中心,選取ρi低但δi相對較高的點(diǎn)標(biāo)記為噪聲點(diǎn);⑥ 將剩下的點(diǎn)劃分到密度比它大且離它最近的數(shù)據(jù)點(diǎn)所屬的簇.3: 輸出:聚類結(jié)果.

1.2 自然最近鄰居

最近鄰算法中比較常用的是k-最近鄰和ε-最近鄰.k-最近鄰是人為給定參數(shù)k,再找k個(gè)距離最小的樣本點(diǎn).ε-最近鄰是人為給定半徑ε,再找出每個(gè)樣本點(diǎn)在其半徑ε內(nèi)的鄰居個(gè)數(shù).但這兩種算法需要人工設(shè)定參數(shù),人為因素直接影響結(jié)果,而自然最近鄰很好的解決了這個(gè)問題.自然最近鄰居[14](natural nearest neighbor, NNN)不需要設(shè)定任何參數(shù),依靠數(shù)據(jù)集自身特點(diǎn)搜索得到,在密度較大的區(qū)域的點(diǎn)的鄰居多,反之則鄰居少.該算法可以很好地反映數(shù)據(jù)集的分布特征.

定義1(最近鄰)NNr(xi)代表樣本點(diǎn)xi的r最近鄰,其中r由自然最近鄰搜索算法自動生成.

定義2(逆近鄰)RNNr(xi)表示樣本點(diǎn)xi的r逆最近鄰:

RNNr(xi)={xj∈X|xi∈NNr(xj),i≠j}

(3)

定義3(自然最近鄰)NNN(xi)表示樣本點(diǎn)xi的自然最近鄰:

NNN(xi)={xj∈X|xi∈NNr(xj),xj∈RNNr(xi)}

(4)

定義4(自然鄰居特征值supk)當(dāng)所有的樣本點(diǎn)都有逆近鄰或者當(dāng)樣本中逆近鄰個(gè)數(shù)為0的樣本點(diǎn)個(gè)數(shù)不變時(shí),自然近鄰搜索過程到達(dá)自然穩(wěn)定狀態(tài),此時(shí)的搜索次數(shù)稱為自然特征值,記為:

supk={r|?x?y(y≠x∩x∈NNr(y))}

(5)

自然最近鄰算法如下:

1.3 三支聚類

2010年,文獻(xiàn)[15]提出三支決策理論,其核心思想是將研究對象分為POS(C)(正域)、NEG(C)(邊界域)、BND(C)(負(fù)域),分別對應(yīng)3種決策規(guī)則:接受、不承諾以及拒絕規(guī)則.

在三支聚類中類簇用Co(C)、Fr(C)、Tr(C)3個(gè)集合來表示,即為核心域、邊界域和瑣碎域.其中Co(C)中的樣本點(diǎn)一定屬于類C,Fr(C)中的樣本點(diǎn)無法確定是不是屬于類C,Tr(C)中的數(shù)據(jù)對象一定不屬于類C[7].

在三支聚類過程中,瑣碎域可通過Tr(Ci)=U-Co(Ci)-Fr(Ci)進(jìn)行表示,并且在實(shí)際聚類中,劃分出一定不屬于某類簇的數(shù)據(jù)對象沒有意義,對于一定屬于某類簇的數(shù)據(jù)對象或者可能屬于某類簇的數(shù)據(jù)對象,才是類簇劃分與表示中的研究重點(diǎn),文中劃分只提供核心域與邊界域的表示,表示結(jié)果:CS={{Co(C1),Fr(C1)},…,{Co(Ck),Fr(Ck)}},該式中集合滿足如下性質(zhì):

(1)Co(Ci)≠?i=1,2,…,k

(3)Co(Ci)∪Fr(Ci)∪Tr(Ci)=U

性質(zhì)(1)表明集合Co(C)不為空集,即每個(gè)類的核心域中至少要有一個(gè)對象.

性質(zhì)(2)確保集合U中每個(gè)對象至少被劃分到一個(gè)類中.

性質(zhì)(3)要求任何一個(gè)類簇3個(gè)集合的并集為U.

2 基于密度峰值算法的三支聚類

2.1 基于密度峰值算法的三支聚類

基于SNN-DPC算法[13],引入自然最近鄰算法,重新計(jì)算了局部密度和距離函數(shù),消除鄰域大小對聚類算法的影響.SNN-DPC中的SNN的實(shí)現(xiàn)依賴KNN算法,需要人為指定k值,選取的k值直接決定了算法結(jié)果的好壞,具有隨機(jī)性.文中選擇自然最近鄰算法計(jì)算共享近鄰,避免了參數(shù)選擇的隨機(jī)性,在此基礎(chǔ)上融入三支決策思想,將傳統(tǒng)的硬聚類轉(zhuǎn)換成三支聚類,進(jìn)一步提升了聚類的質(zhì)量,由于三支聚類的特性,使得本算法更加貼合實(shí)際生活場景.所提算法即基于密度峰值聚類算法的三支聚類,簡稱3W-DPC.

定義5(共享近鄰SNN)點(diǎn)i和j是數(shù)據(jù)集D中的任意兩個(gè)點(diǎn),點(diǎn)i和點(diǎn)j的自然最近鄰集合分別為NNN(i)和NNN(j),那么它們的SNN為各自近鄰集合的交集,記為:

SNN(i,j)=NNN(i)∩NNN(j)

(6)

定義6[16](共享近鄰相似度Sim)點(diǎn)i和j是數(shù)據(jù)集D中的任意兩個(gè)點(diǎn),p是共享鄰居集合里的點(diǎn),Sim定義為:

(7)

式中:|SNN(i,j)|為點(diǎn)i和點(diǎn)j的共享鄰居的數(shù)量,用|SNN(i,j)|除以點(diǎn)i和點(diǎn)j到所有共享鄰居的距離之和可以視為這兩點(diǎn)周圍的密度,同時(shí)利用共享鄰居數(shù)量和密度來定義相似度,得到的結(jié)果也更準(zhǔn)確.僅當(dāng)它們都位于彼此的自然最近鄰中,才會計(jì)算兩者的共享近鄰相似度,否則相似度為0.

定義7(SNN局部密度)點(diǎn)i是數(shù)據(jù)集中的任一點(diǎn),L(i)={x1,x2,...,xsupk}是與點(diǎn)i具有最相似的點(diǎn)的集合,點(diǎn)ρi的局部密度為L(i)內(nèi)所有點(diǎn)相似度的和,記為:

(8)

如果自然最近鄰域中的數(shù)據(jù)點(diǎn)分布較密時(shí),該點(diǎn)密度就較大,反之較小.

定義8(數(shù)據(jù)點(diǎn)距離δi)點(diǎn)i是數(shù)據(jù)集中的任一點(diǎn),j是局部密度比i高的點(diǎn),p為點(diǎn)i的自然最近鄰域集合中的點(diǎn),q為點(diǎn)j自然最近鄰域集合中的點(diǎn):

(9)

對于密度最高的點(diǎn),則可以取:

δi=max(δj)

(10)

很多數(shù)據(jù)集上的數(shù)據(jù)點(diǎn)分布并不均勻,通過上述計(jì)算方法,在數(shù)據(jù)點(diǎn)集中的區(qū)域縮短了數(shù)據(jù)點(diǎn)的距離δi,在數(shù)據(jù)點(diǎn)稀疏的區(qū)域放大了數(shù)據(jù)點(diǎn)之間的距離δi,考慮了每個(gè)點(diǎn)的鄰居信息.

得到每個(gè)點(diǎn)的ρi和δi值后,生成決策圖,并在圖中選取ρi和δi都大的值作為聚類中心.

定義9設(shè)xi∈CI,CI為類簇中心集合,xj∈NNNnb(xi)(xi),如果滿足下式,則歸入核心域:

|NNNnb(xi)(xi)∩NNNnb(xj)(xj)|≥|NNN(xj)|/3

(11)

選擇出聚類中心后,設(shè)聚類中心點(diǎn)xi有m個(gè)自然最近鄰居,樣本點(diǎn)xj是樣本點(diǎn)xi的自然最近鄰居之一且未被劃分到核心類簇,樣本點(diǎn)xj的自然最近鄰居個(gè)數(shù)為n,如果此時(shí)樣本點(diǎn)xj和樣本點(diǎn)xi的共享自然鄰居個(gè)數(shù)大于等于xj點(diǎn)自然最近鄰居個(gè)數(shù)的1/3,則將xj歸入聚類中心xi所屬類簇的核心域,反之將樣本點(diǎn)xj歸為邊界域.

經(jīng)過上述處理得到核心域和邊界域,針對邊界域中的數(shù)據(jù)對象的處理策略是:將其劃分到和該點(diǎn)最近的點(diǎn)xi在的類簇的邊界域中.原則上,此類數(shù)據(jù)點(diǎn)是屬于所屬類簇的邊界域,但是在計(jì)算聚類質(zhì)量時(shí),將同一類簇的核心域中數(shù)據(jù)點(diǎn)和邊界域中數(shù)據(jù)點(diǎn)合并作為最終聚類結(jié)果,并在此結(jié)果集上評價(jià)聚類質(zhì)量.由于邊界域中的數(shù)據(jù)點(diǎn)存在更高概率的誤分類,按照這樣的計(jì)算標(biāo)準(zhǔn),更加能證明所提出算法的優(yōu)越性.

基于密度峰值算法的三支聚類算法如下:

算法3 基于密度峰值算法的三支聚類輸入:數(shù)據(jù)集輸出:數(shù)據(jù)點(diǎn)xi的所屬類簇1:初始化參數(shù):無2:① 計(jì)算任意兩個(gè)數(shù)據(jù)點(diǎn)之間的距離; ② 計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的自然鄰居NNN(xi)以及該點(diǎn)鄰居個(gè)數(shù)nb(xi); ③ 根據(jù)式(8)算出任意數(shù)據(jù)點(diǎn)xi的局部密度ρi; ④ 根據(jù)式(9)和式(10)得到任意數(shù)據(jù)點(diǎn)xi距離δi; ⑤ 以ρi為橫軸,以δi為縱軸構(gòu)造出決策圖; ⑥ 構(gòu)建決策圖,選取ρi和δi都大的值標(biāo)記為聚類中心CI={Co(C1),…,Co(Ck)}; ⑦ 取xi∈CI,xj∈NNNnb(xi)(xi),滿足式(11),則xj歸入xi所在類簇的核心域Co(xi); ⑧ 剩下的點(diǎn)歸類到是它的最近鄰并且密度大于它的數(shù)據(jù)點(diǎn)在的簇的邊界域.3:輸出:數(shù)據(jù)點(diǎn)xi的所屬類簇.

2.2 算法分析

使用自然最近鄰算法對DPC算法進(jìn)行改進(jìn),將改進(jìn)后的算法與三支聚類相結(jié)合,聚類的質(zhì)量得到了進(jìn)一步的保證,但三支聚類僅提供了一種進(jìn)行軟聚類的策略,即可以通過制定相對應(yīng)的規(guī)則來規(guī)定不同數(shù)據(jù)簇的核心區(qū)域和邊界區(qū)域,具體的規(guī)則實(shí)現(xiàn)各有不同,但都不可避免地要進(jìn)行相關(guān)閾值參數(shù)選取.由專家經(jīng)驗(yàn)可得,此閾值參數(shù)一般可設(shè)置為1/2、1/3或1/4.文中選取1/3作為三支聚類的閾值,在人工數(shù)據(jù)集Aggregation上驗(yàn)證不同閾值的聚類質(zhì)量,以證明該參數(shù)的合理性及魯棒性.圖1顯示不同閾值下的聚類結(jié)果,表1則對應(yīng)著不同閾值下的性能評價(jià)結(jié)果,包括準(zhǔn)確率(accuracy,ACC) 、調(diào)整蘭德指數(shù)(adjusted rand index,ARI)、調(diào)整互信息(adjusted mutual information,AMI)和FM指數(shù)(fowlkes and mallows index, FMI).

表1 不同閾值聚類結(jié)果

圖1 不同三支閾值下3W-DPC在Aggregation上結(jié)果

從圖1中的6個(gè)子圖中可以看出,當(dāng)閾值由1/2減小為1/7時(shí),聚類的效果由差到好再到差,即存在一個(gè)聚類效果峰值,這個(gè)峰值對應(yīng)的閾值恰好為1/3.由圖1(a)可以看出原本屬于C3的數(shù)據(jù)對象被錯(cuò)誤地分配到了C2,同樣地,C5和C6也存在這樣的問題;觀察圖1(b)、(c)和(d),著眼于C3,圖1(b)的聚類結(jié)果要稍遜于圖1(c),因?yàn)槠湓贑3存在3個(gè)數(shù)據(jù)對象的誤判,但在C4上,圖1(b)的聚類結(jié)果要明顯好于圖1(c),圖1(c)在C4上存在15個(gè)點(diǎn)左右的誤判,圖1(d)相較于圖1(c),在C3上多了3個(gè)數(shù)據(jù)對象的誤判,綜合看來,三者之中圖1(b)更加優(yōu)秀;同樣地,可以看出圖1(b)要優(yōu)于圖1(e)和(f).

由表1可以看出,當(dāng)閾值選取為1/3時(shí),各項(xiàng)指標(biāo)表現(xiàn)最為優(yōu)異,與圖1分析一致.且仔細(xì)觀察可知,當(dāng)閾值選取小于1/6時(shí),各項(xiàng)性能指標(biāo)不會隨著閾值的減小而變化.分析式(11)可得,閾值與因子NNN(xj)相乘作為判定的條件,當(dāng)兩者相乘的結(jié)果小于1,便不會對數(shù)據(jù)集區(qū)分出粒度,式(11)的效果也就等價(jià)于如果xj與核心點(diǎn)xi存在交集,則將xj歸入核心點(diǎn)xi所屬類簇,雖然這樣也屬于是三支聚類的一種策略,但是設(shè)置的區(qū)分粒度太大,聚類效果可能不好,通過分析,結(jié)合自然鄰居的特性可知,當(dāng)閾值小于1/Max(nb(xi)),便不會產(chǎn)生區(qū)分粒度的變化.由專家經(jīng)驗(yàn)可得這個(gè)閾值在1/2至1/Max(nb(xi))產(chǎn)生,通過實(shí)驗(yàn)證明選取1/3作為閾值具有一定的優(yōu)越性和魯棒性.

2.3 復(fù)雜度分析

2.3.1 空間復(fù)雜度分析

每個(gè)數(shù)據(jù)對象到所有數(shù)據(jù)對象(包括自身)的空間復(fù)雜度,即存儲距離矩陣為O(N2),其中N為數(shù)據(jù)對象總個(gè)數(shù),存儲每個(gè)數(shù)據(jù)對象的自然鄰居個(gè)數(shù)的空間復(fù)雜度為O(N*supk),supk為穩(wěn)定狀態(tài)時(shí)的搜索次數(shù).所以3W-DPC算法空間復(fù)雜度為O(N2),和原始密度峰值算法一樣.

2.3.2 時(shí)間復(fù)雜度分析

3W-DPC算法時(shí)間復(fù)雜度主要取決于:

(1) 每個(gè)數(shù)據(jù)對象的距離矩陣,其時(shí)間復(fù)雜度為O(N2);

(2) 每個(gè)數(shù)據(jù)對象的自然鄰居,因?yàn)閷?shù)據(jù)放入k-d樹,使用了k-d進(jìn)行搜索,搜索i的第r個(gè)近鄰時(shí)間復(fù)雜度為O(log(N)),因此時(shí)間復(fù)雜度為O(supk*N*log(N));

(3) 局部密度ρ,由自然最近鄰集合可知時(shí)間復(fù)雜度為O(supk*N);

(4) 數(shù)據(jù)點(diǎn)距離δ,時(shí)間復(fù)雜度為O(N2)找到中心點(diǎn)并將剩余點(diǎn)分配到其屬于的類簇,時(shí)間復(fù)雜度為O(N2),所以總的時(shí)間復(fù)雜度為O(N2),與未該改進(jìn)前的DPC算法相同.

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

選用2組Synthetic數(shù)據(jù)集、5組UCI數(shù)據(jù)集和4組Shape(人工)數(shù)據(jù)集[17]進(jìn)行實(shí)驗(yàn).數(shù)據(jù)集如表2～4.

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

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

表4 Shape數(shù)據(jù)集

不同的數(shù)據(jù)集有不同預(yù)處理方式,對于UCI數(shù)據(jù)集,由于該數(shù)據(jù)集中會出現(xiàn)不是數(shù)字或者為空的屬性,也就是類別型屬性,這類屬性往往存在離散值問題,既想保留盡可能多的數(shù)據(jù)信息,同時(shí)也要考慮到字符數(shù)據(jù)的離散程度,所以需要將不是數(shù)字的屬性進(jìn)行One-hot編碼,然后,進(jìn)行歸一化處理,使得每個(gè)維度所占比重相同.對于Shape數(shù)據(jù)集和Synthetic數(shù)據(jù)集,由于不會出現(xiàn)不是數(shù)字的屬性,所以只進(jìn)行歸一化處理.

4 實(shí)驗(yàn)結(jié)果

3W-DPC算法與傳統(tǒng)DPC,SNN-DPC算法在數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對比,實(shí)驗(yàn)結(jié)果如表5～7.

表5 Synthetic數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表6 UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表7 Shape數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

從表5～7中的實(shí)驗(yàn)結(jié)果可以看出,在AMI、FMI、ACC指標(biāo)上,提出的3W-DPC算法相比于SNN-DPC、DPC算法明顯優(yōu)秀很多.在ARI指標(biāo)上,也只有Dermatology數(shù)據(jù)集,SNN-DPC比SNN-DPC結(jié)果稍好,其余數(shù)據(jù)集上3W-DPC算法都是比3W-DPC、DPC算法優(yōu)秀.3W-DPC算法與SNN-DPC、DPC算法的聚類結(jié)果相比,有效提升了算法性能.

5 結(jié)論

(1) 借助自然最近鄰算法提出了一種基于改進(jìn)的DPC算法的三支聚類.該算法首先利用自然最近鄰定義共享鄰居,確定DPC算法的兩個(gè)待計(jì)算量:局部密度βi和數(shù)據(jù)點(diǎn)距離δi,通過決策圖得到密度峰值點(diǎn),即聚類中心,解決了需要人為指定k值的不足.

(2) 算法融合了三支聚類,通過閾值將確定的元素劃分到核心域,將不確定的元素劃分到邊界域延遲決策,在多組數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證,并與SNN-DPC、DPC算法進(jìn)行比較,實(shí)驗(yàn)結(jié)果表明此方法可以提高聚類的精度以及提升算法的性能表現(xiàn).

(3) 自然最近鄰是一個(gè)新興的鄰居概念,有關(guān)定義以及應(yīng)用有待完善,在后續(xù)工作中,將討論如何利用自然最近鄰更貼切的定義DPC算法的兩個(gè)計(jì)算量,以及對不確定元素進(jìn)行更巧妙的分配.