杜淑穎,施天豪,丁世飛

(1.中國礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 徐州 221116;2.徐州生物工程職業(yè)技術(shù)學(xué)院 信息管理學(xué)院,江蘇 徐州 221000)

進(jìn)入信息時(shí)代,信息科學(xué)技術(shù)廣泛地滲透到社會(huì)生活中的各個(gè)領(lǐng)域并產(chǎn)生了各種各樣的數(shù)據(jù)。如何從多樣的數(shù)據(jù)中獲取有用的信息是數(shù)據(jù)挖掘研究的焦點(diǎn)問題。聚類分析是數(shù)據(jù)挖掘領(lǐng)域的一項(xiàng)重要內(nèi)容,它能在標(biāo)簽未知的情況下通過數(shù)據(jù)間的相似度進(jìn)行分類,使同類的數(shù)據(jù)之間具有較高的相似度。聚類分析發(fā)掘數(shù)據(jù)的潛在聯(lián)系,得到關(guān)鍵信息從而支持決策。因此,它在模式識(shí)別、圖像分割、社區(qū)發(fā)現(xiàn)等諸多領(lǐng)域應(yīng)用廣泛[1,2]。

密度峰值聚類[3](Density peaks clustering,DPC)是由Rodriguez等于2014年提出的一種基于密度的簡單高效的聚類算法。算法通過密度ρ和相對(duì)距離δ兩個(gè)基本屬性完成聚類。DPC是密度聚類的一種代表算法,其無需迭代,可以對(duì)非球形的數(shù)據(jù)聚類并得到較為滿意的結(jié)果。密度峰值聚類的優(yōu)點(diǎn)較為突出,但是它的缺點(diǎn)仍然不容忽視:(1)人工選取聚類中心會(huì)導(dǎo)致較大的聚類誤差;(2)在密度不均勻的流形數(shù)據(jù)集上得不到正確的聚類結(jié)果。高密度的數(shù)據(jù)點(diǎn)通常被選取為聚類中心點(diǎn),因此在密度不均勻的數(shù)據(jù)集中低密度簇的中心點(diǎn)往往會(huì)被忽略,由于中心點(diǎn)的錯(cuò)誤選取而導(dǎo)致的“多米諾效應(yīng)”往往會(huì)造成錯(cuò)誤的聚類結(jié)果。密度峰值聚類需要進(jìn)一步研究和改進(jìn)。

為了改善上述不足,近些年來很多密度峰值改進(jìn)算法被提出[4-13]。針對(duì)第一個(gè)弊端的研究較少,Xu等[4]基于輪廓系數(shù)提出一種新指標(biāo)DCI能自動(dòng)得到聚類數(shù)目無需人工干預(yù)。Yan等[5]提出ADPC算法,其利用一種異常值統(tǒng)計(jì)檢測方法在決策圖中自動(dòng)找出聚類中心。而針對(duì)第二個(gè)弊端,學(xué)者們開展了廣泛的研究并提出較多的改進(jìn)算法。Xie等[6]提出FKNN-DPC算法,其利用K近鄰概念計(jì)算密度,并通過K近鄰和模糊加權(quán)K近鄰來改善分配過程,FKNN-DPC在流形數(shù)據(jù)集上具有比DPC更好的聚類結(jié)果。Liu等[7]提出了SNN-DPC算法,其利用了共享近鄰SNN重新定義了局部密度ρ和相對(duì)距離δ。SNN-DPC引入了兩步分配策略:必然從屬和可能從屬,使得聚類的精度大大提高。Du等[8]提出DP-DA算法,通過密度自適應(yīng)度量重新定義了數(shù)據(jù)點(diǎn)之間的相似度,相對(duì)于用歐氏距離作為相似度度量的DPC算法具有更好的聚類性能。Seyedi等[9]提出DPC-DLP算法,利用圖標(biāo)簽傳播對(duì)剩余點(diǎn)分配并形成最終簇類。這些算法一般都是通過K近鄰計(jì)算數(shù)據(jù)點(diǎn)局部密度,默認(rèn)這些近鄰點(diǎn)在密度計(jì)算過程中所起的作用是一致的,而這導(dǎo)致不同密度簇之間的密度差過大,低密度簇容易被忽略造成較大的聚類誤差。基于以上分析,本文提出一種基于電子分層模型和凝聚策略的密度峰值聚類(Density peaks clustering based on electronic shells model and merging strategy,EMDPC)。其仿照電子分層模型給不同的近鄰點(diǎn)分層,并在不同層次分配不同的權(quán)重,縮小了不同簇類之間的密度差,可以在具有不同密度簇的流形數(shù)據(jù)上更為輕易地識(shí)別出低密度簇,進(jìn)一步提高聚類精度。另外,EMDPC通過凝聚策略能很好適用于密度不均勻的流形數(shù)據(jù),較好地解決了DPC存在的問題。

1 DPC算法原理

DPC是近來提出的一種高效的聚類算法,它能將任意形狀的數(shù)據(jù)聚類且無需考慮數(shù)據(jù)空間的維度。DPC沒有迭代,不需要預(yù)設(shè)聚類數(shù)目,僅需要較少的參數(shù),因此它具有非常廣闊的應(yīng)用前景。算法的核心思想基于兩個(gè)基本假設(shè):(1)聚類中心點(diǎn)處于稠密區(qū)域,且其密度比周圍數(shù)據(jù)點(diǎn)的密度更大;(2)聚類中心點(diǎn)與比其密度大的數(shù)據(jù)點(diǎn)之間的距離更大。因此,DPC通過數(shù)據(jù)點(diǎn)的兩個(gè)基本屬性:密度ρ和相對(duì)距離δ來完成整個(gè)聚類過程。

假設(shè)有數(shù)據(jù)集X={x1,x2,…,xn},基于第一個(gè)假設(shè),DPC定義每個(gè)數(shù)據(jù)點(diǎn)的局部密度,如式(1)所示

(1)

χ(x)的定義如式(2)

(2)

式中:dist(i,j)表示點(diǎn)xi和xj之間的歐式距離;dc是一個(gè)輸入?yún)?shù),代表截?cái)嗑嚯x。這種方法得到xi的密度等于與點(diǎn)xi間的距離小于dc的所有數(shù)據(jù)點(diǎn)個(gè)數(shù)。而當(dāng)數(shù)據(jù)集規(guī)模較小時(shí),DPC也可以通過一種高斯核函數(shù)來計(jì)算數(shù)據(jù)點(diǎn)局部密度,如式(3)所示

基于第二個(gè)假設(shè),相對(duì)距離δi被定義為點(diǎn)xi與比它密度大的數(shù)據(jù)點(diǎn)之間的最小距離

(4)

而對(duì)于密度最大的數(shù)據(jù)點(diǎn),其相對(duì)距離為

(5)

在得到數(shù)據(jù)點(diǎn)的密度ρ和相對(duì)距離δ之后,以ρ為橫軸,δ為縱軸畫出決策圖,通過選擇具有較大ρ和δ值的點(diǎn)作為聚類中心,將數(shù)據(jù)標(biāo)簽分配到剩余的非中心點(diǎn)上,得到最終的聚類結(jié)果。如圖1所示,圖1(a)為28個(gè)二維數(shù)據(jù)點(diǎn)的分布圖,圖1(b)為對(duì)應(yīng)畫出的決策圖,不同的顏色表示不同的簇類,從決策圖中可以看出在右上區(qū)域的兩個(gè)點(diǎn)具有較大的ρ和δ值,因此這兩個(gè)點(diǎn)被選取為聚類中心,其余非中心點(diǎn)被分配到這兩個(gè)中心所形成的簇類中。

值得注意的是,DPC的關(guān)鍵步驟是通過決策圖選取聚類中心。這一步中通過人工干預(yù)選擇聚類中心點(diǎn)具有較大的誤差,聚類中心和非中心點(diǎn)之間的界限有時(shí)非常模糊,通過人工干預(yù)難以辨別。圖2是DPC在Jain數(shù)據(jù)集上的決策圖,圖中有顏色的兩個(gè)點(diǎn)為真實(shí)聚類中心,在中心點(diǎn)數(shù)目未知的情況下依靠人工精準(zhǔn)選擇十分困難。因此,提出一種改進(jìn)算法以解決這些不足勢在必行。

圖2 DPC在Jain數(shù)據(jù)集上的決策圖

2 EMDPC算法

2.1 基于電子分層模型的局部密度計(jì)算

EMDPC算法的提出是為了解決密度峰值在密度不均勻的流形數(shù)據(jù)上聚類性能不佳,需要人工干預(yù)選擇聚類中心進(jìn)而加大聚類誤差的問題。它基于這樣一個(gè)假設(shè):有一組數(shù)據(jù)規(guī)模為n的數(shù)據(jù)X={x1,x2,…,xn},對(duì)于其中的任意一個(gè)點(diǎn)xi,本文認(rèn)為xi的近鄰點(diǎn)對(duì)于xi密度計(jì)算的貢獻(xiàn)是不同的,這種不同不僅僅局限于它們之間的距離。因此本文將xi的近鄰點(diǎn)分成幾個(gè)不同的層次,給每個(gè)層次分配不同的權(quán)重,代表這個(gè)層次上的點(diǎn)對(duì)于xi密度的貢獻(xiàn)程度。另外,如果將剩余點(diǎn)按照與xi的相似度大小排序,會(huì)發(fā)現(xiàn)與xi較相似的點(diǎn)比較少,與xi不太相似的點(diǎn)更多,這符合電子分層模型中內(nèi)層電子少,外層電子數(shù)多的情況,如圖3(a)所示。因此,利用電子分層模型來改進(jìn)密度計(jì)算,縮小不同簇間密度差,進(jìn)一步提高聚類精度。

數(shù)據(jù)點(diǎn)分層模型如圖3(b)所示,每個(gè)數(shù)據(jù)點(diǎn)的層級(jí)軌道可以表示為l(1≤l≤L),其中L表示總軌道數(shù),在第l層軌道內(nèi)存在l+1個(gè)數(shù)據(jù)點(diǎn),則點(diǎn)xi的密度定義為

圖3 分層模型

(6)

式中:dij表示點(diǎn)xi與點(diǎn)xj之間的距離;dsum表示所有層級(jí)軌道內(nèi)的數(shù)據(jù)點(diǎn)與xi的距離之和;ω是每個(gè)層級(jí)軌道所分配到的權(quán)重,其計(jì)算為

ωl=exp(-l)

(7)

可以看到層級(jí)l越大,權(quán)重ωl就越小,即如果一個(gè)數(shù)據(jù)點(diǎn)距離xi越遠(yuǎn),所在的軌道數(shù)越大,它在xi密度計(jì)算過程中所起到的作用越小。

圖4為稠密區(qū)域內(nèi)數(shù)據(jù)點(diǎn)和稀疏區(qū)域內(nèi)數(shù)據(jù)點(diǎn)的層級(jí)差異,對(duì)每個(gè)層級(jí)軌道分配不同的權(quán)重,等效于縮小在外層軌道內(nèi)的點(diǎn)到核心點(diǎn)的距離。通過這種方式將低密度區(qū)域內(nèi)數(shù)據(jù)點(diǎn)的密度適當(dāng)增大,能縮小不同簇類之間的密度差,有效發(fā)現(xiàn)低密度簇。

圖4 稠密區(qū)域和稀疏區(qū)域的層級(jí)差異

2.2 子簇凝聚策略

在得到ρ和δ之后,畫出決策圖,得到盡可能多的子簇。然而如何合并子簇,使最終的聚類結(jié)果更精確是本文研究的主要問題之一。對(duì)于兩個(gè)高相似度子簇,要使得合并之后的結(jié)果盡可能與真實(shí)劃分保持一致。為此,兩個(gè)需要合并的子簇應(yīng)該具有以下特點(diǎn):(1)較多的共同近鄰;(2)平均密度應(yīng)該盡可能相近;(3)簇中心應(yīng)盡可能接近;(4)子簇間的最短距離應(yīng)盡可能小。

通過以上分析,首先得到下述定義:

定義1公共近鄰[14]。對(duì)于任意兩個(gè)點(diǎn)xi和xj,D(i)表示以xi為核心的L層軌道內(nèi)的所有數(shù)據(jù)點(diǎn)集合,則xi和xj在L層軌道內(nèi)的共同近鄰如式(8)所示

SNN(xi,xj)=D(i)∩D(j)

(8)

定義2簇間平均密度差。簇間平均密度差為兩個(gè)簇類平均密度的差的絕對(duì)值,其計(jì)算公式見式(9)

den_diff(ci,cj)=|ρa(bǔ)vg(ci)-ρa(bǔ)vg(cj)|

(9)

定義3簇間最短距離[15]。為了減小異常值的影響,最短距離dmin(ci,cj)選取兩個(gè)簇內(nèi)nij個(gè)點(diǎn)的最短距離的平均值,見式(10)

(10)

式中:nij=ceil(min(ni·10%,nj·10%)),ceil為取整函數(shù)。

定義4簇間相似度。假設(shè)有兩個(gè)簇ci和cj,簇ci內(nèi)共有ni個(gè)點(diǎn),則ci和cj之間的簇間相似度SIM(ci,cj)的定義如式(11)所示

(11)

式中:dij是ci和cj的簇中心點(diǎn)之間的距離。通過上述定義得到的簇間相似度,可以看出兩個(gè)簇之間的共同近鄰越多,簇間距離越短,簇間平均密度差越接近,則兩個(gè)簇之間的相似度就越高,這符合本文認(rèn)知中的相似度定義。在得到簇間相似度之后,可以將每兩個(gè)簇之間的簇間相似度按從大到小排序,把具有最大簇間相似度的兩個(gè)簇類聚合在一起,直至滿足結(jié)束條件之后停止子簇凝聚,得到最終的聚類結(jié)果。

定義5凝聚結(jié)束條件。具有最大相似度的兩個(gè)子簇在凝聚過程中如果滿足以下兩種情況中的任意一種,就認(rèn)為凝聚過程結(jié)束,如式(12)所示

(12)

聚類的目標(biāo)是最大化簇內(nèi)相似度,如果子簇凝聚后簇內(nèi)相似度不升反降,則說明不應(yīng)將子簇凝聚。因此,如果滿足以上兩個(gè)終止條件,則凝聚過程結(jié)束。

2.3 算法描述

算法描述見算法1。

算法1EMDPC算法

輸入:數(shù)據(jù)集X={x1,x2,…,xn},分層數(shù)L;

輸出:聚類結(jié)果Y;

1:計(jì)算任意兩點(diǎn)之間的距離得到距離矩陣D;

2:通過式(6)計(jì)算數(shù)據(jù)點(diǎn)局部密度ρ;

3:通過式(4)和式(5)計(jì)算數(shù)據(jù)點(diǎn)相對(duì)距離δ;

4:畫出決策圖,選擇盡可能多的具有相對(duì)較大ρ和δ值的點(diǎn)作為聚類中心;

5:將剩余非中心點(diǎn)分配到與其最近的高密度點(diǎn)所在的簇類中,形成子簇;

6:While不滿足凝聚結(jié)束條件:

7: 通過式(11)計(jì)算任意兩個(gè)子簇之間的相似度;

8: 將相似度最高的兩個(gè)子簇凝聚,子簇個(gè)數(shù)減1;

9:End

國有企業(yè)要完善內(nèi)部組織架構(gòu)，嚴(yán)格按照生產(chǎn)需要和發(fā)展目標(biāo)明確分工，提升工作效率。同時(shí)，利用科學(xué)手段，完善內(nèi)部控制管理體系，組建風(fēng)險(xiǎn)評(píng)估組和監(jiān)督部門，對(duì)企業(yè)進(jìn)行全面的風(fēng)險(xiǎn)評(píng)估和監(jiān)督工作，實(shí)現(xiàn)對(duì)企業(yè)內(nèi)部的有效監(jiān)管，如財(cái)務(wù)管理、資金流動(dòng)及財(cái)務(wù)審計(jì)等方面，進(jìn)而提升國有企業(yè)內(nèi)部溝通的效率[5]。通過高效溝通，不僅增強(qiáng)了國有企業(yè)應(yīng)對(duì)風(fēng)險(xiǎn)的能力，同時(shí)也實(shí)現(xiàn)了企業(yè)內(nèi)部控制的有效實(shí)施。

10:輸出結(jié)束條件終止后的最終結(jié)果Y。

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

EMDPC的前半部分的復(fù)雜度與DPC基本一致:(1)計(jì)算距離矩陣需要O(n2);(2)通過電子分層模型計(jì)算局部密度,需要O(n2);(3)計(jì)算相對(duì)距離,所需時(shí)間O(n2);(4)排序并分配標(biāo)簽,復(fù)雜度為O(nlogn+n),之后將子簇合并,合并過程中:(5)尋找子簇內(nèi)數(shù)據(jù)點(diǎn)的共享近鄰,時(shí)間復(fù)雜度為O(n2);(6)計(jì)算簇間密度差和簇間最短距離需要O(n2);(7)計(jì)算簇間相似度,所需時(shí)間O(n2);(8)合并子簇需要O(n)。因此,EMDPC算法總的時(shí)間復(fù)雜度為O(3n2+nlogn+n+λ(3n2+n))=(1+λ)(3n2+n)+nlogn,其中λ為選取簇類數(shù)與真實(shí)簇類數(shù)之差,即迭代次數(shù)。因?yàn)橛笑?n,故其時(shí)間復(fù)雜度可以近似為O(n2)。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證EMDPC的可行性和有效性,本文在8個(gè)合成數(shù)據(jù)集和8個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn),數(shù)據(jù)集詳細(xì)信息如表1和表2所示。EMDPC與近幾年提出的4種DPC的改進(jìn)算法:DPC-KNN、SNN-DPC、DPC-SFSKNN以及DPCSA進(jìn)行對(duì)比實(shí)驗(yàn)。這4種算法利用不同的改進(jìn)策略來提升DPC在不同數(shù)據(jù)集上的聚類精度,具有較好的實(shí)驗(yàn)結(jié)果,與EMDPC進(jìn)行對(duì)比更能體現(xiàn)出EMDPC的聚類優(yōu)越性。其中,DPC-KNN和SNN-DPC分別利用K近鄰和共享近鄰來重新定義數(shù)據(jù)點(diǎn)局部密度,提升原有DPC的聚類精度,聚類結(jié)果得到明顯改善;DPC-SFSKNN利用加權(quán)K近鄰計(jì)算數(shù)據(jù)局部密度,并使用相似度優(yōu)先算法來分配數(shù)據(jù)點(diǎn)標(biāo)簽,實(shí)驗(yàn)證明其具有不錯(cuò)的聚類結(jié)果;DPCSA用一種近鄰分配策略來提高DPC在密度分布不均的流形數(shù)據(jù)集上的聚類精度。這4種算法是較為典型的DPC改進(jìn)算法,其詳細(xì)信息見參考文獻(xiàn)[7,10,16,17]。

表1 合成數(shù)據(jù)集詳細(xì)信息

表2 真實(shí)數(shù)據(jù)集詳細(xì)信息

本文使用聚類精確度(Accuracy,ACC)、調(diào)整蘭德系數(shù)(Adjusted rand index,ARI)和調(diào)整互信息(Adjusted mutual information,AMI)3個(gè)常用的評(píng)價(jià)聚類性能的指標(biāo)來驗(yàn)證聚類結(jié)果的優(yōu)劣,它們?nèi)≈翟浇咏?表明聚類結(jié)果越好。

仿真實(shí)驗(yàn)在筆記本電腦上進(jìn)行,主要配置為Intel Core i7處理器、8 GB內(nèi)存、Windows10操作系統(tǒng),集成開發(fā)環(huán)境為MATLAB 2019b。

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

3.2.1 合成數(shù)據(jù)集實(shí)驗(yàn)分析

本節(jié)對(duì)8個(gè)合成數(shù)據(jù)集(http://cs.uef.fi/sipu/datasets/)進(jìn)行分析,它們的具體信息見表1。這些數(shù)據(jù)集具有不同的規(guī)模,不同的流形結(jié)構(gòu),不同的簇類數(shù)目,因此DPC很難在這些數(shù)據(jù)集上正確聚類。將EMDPC同DPC在二維圖形上進(jìn)行對(duì)比,通過圖形觀察聚類結(jié)果,更為直觀地了解EMDPC的優(yōu)越性,其中DPC的參數(shù)設(shè)置為dc∈{1%,2%,4%,6%}。EMDPC和DPC在8個(gè)合成數(shù)據(jù)集上的聚類結(jié)果分別如圖5～12所示。圖中(a)為EMDPC的聚類結(jié)果,(b)和(c)為DPC在參數(shù)dc分別取2%和4%的聚類結(jié)果。

圖5和圖6分別是在Jain和Flame上的聚類結(jié)果:從(b)和(c)可以看出,DPC都沒能將這兩個(gè)數(shù)據(jù)準(zhǔn)確聚類,其密度分布不均的流形結(jié)構(gòu)讓DPC產(chǎn)生了誤差;而EMDPC通過層級(jí)軌道劃分能得到正確的劃分結(jié)果,其聚類精度均為1,如圖5(a)和圖6(a)所示。Aggregation數(shù)據(jù)集如圖7所示:在dc=2時(shí),其結(jié)果有所偏差;EMDPC得益于密度計(jì)算方式和凝聚策略,能自適應(yīng)識(shí)別7個(gè)中心點(diǎn)并得到正確的聚類結(jié)果。從圖8可以看出,Two-circles內(nèi)圈的密度要比外圈的密度大。DPC無法將Two-circles正確聚類,所得到的兩個(gè)中心都必定分布在密度較高的內(nèi)圈中。EMDPC通過分層模型能準(zhǔn)確得到內(nèi)圈和外圈的中心點(diǎn),而不會(huì)將密度較低的外圈分配到高密度的內(nèi)圈中,再通過凝聚策略得到正確的聚類結(jié)果,其精度在DPC基礎(chǔ)上提升了100%左右。

圖5 Jain上的聚類結(jié)果

圖6 Flame上的聚類結(jié)果

DPC在Lineblob和Sticks上均不能準(zhǔn)確聚類,原因是這兩個(gè)數(shù)據(jù)集密度分布不均勻,DPC識(shí)別不出低密度簇。EMDPC通過電子分層模型準(zhǔn)確地識(shí)別出了這兩個(gè)數(shù)據(jù)集中的低密度簇,并通過子簇凝聚策略得到了正確的聚類結(jié)果,分別如圖9(a)和圖10(a)所示。

圖10 Sticks上的聚類結(jié)果

D31數(shù)據(jù)集和S1數(shù)據(jù)集是兩個(gè)規(guī)模較大的合成數(shù)據(jù)集,這兩個(gè)數(shù)據(jù)集中的不同簇類間部分?jǐn)?shù)據(jù)點(diǎn)的距離相對(duì)較近,簇類間區(qū)分的界限比較模糊,因此不容易準(zhǔn)確識(shí)別數(shù)據(jù)集中所有簇類。如圖11和圖12所示,EMDPC由子簇凝聚策略準(zhǔn)確識(shí)別出了簇類數(shù)目,其聚類結(jié)果與DPC十分接近。在表3中可以看到EMDPC在D31數(shù)據(jù)集上的聚類精度為0.971,略大于DPC精度0.967,在S1上,EMDPC取得與DPC一致的聚類結(jié)果,充分表明了EMDPC通過分層模型和凝聚策略進(jìn)行聚類的優(yōu)越性。

圖11 D31上的聚類結(jié)果

圖12 S1上的聚類結(jié)果

表3為在8個(gè)合成數(shù)據(jù)集上EMDPC以及其他5種對(duì)比算法的詳細(xì)聚類結(jié)果。Par表示相關(guān)參數(shù)(Parameter,Par),這些算法參數(shù)值為取得最佳聚類結(jié)果時(shí)的值。加粗的數(shù)據(jù)表示最佳結(jié)果。從表中可以看出EMDPC取得了8個(gè)數(shù)據(jù)集上最佳的聚類結(jié)果。其中,在Jain、Flame、Two-circles、Lineblob和Sticks數(shù)據(jù)集上EMDPC均能完美聚類,其聚類精度均為1。在D31和S1數(shù)據(jù)集上,雖然EMDPC的聚類精度不為1,但其精度在5個(gè)對(duì)比算法中都是最高的,這充分說明了EMDPC算法比其他聚類算法在密度分布不均的數(shù)據(jù)集上具有更為優(yōu)越的聚類性能。

表3 8個(gè)人工數(shù)據(jù)集上的聚類結(jié)果

3.2.2 UCI真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

為了進(jìn)一步驗(yàn)證EMDPC的優(yōu)良性能,將其與DPC,DPC-KNN,SNN-DPC,DPC-SFSKNN以及DPCSA在8個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。這8個(gè)真實(shí)數(shù)據(jù)集來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(http://archive.ics.uci.edu/ml/),其詳細(xì)信息見表2。

EMDPC與其他5種對(duì)比算法在真實(shí)數(shù)據(jù)集上的聚類結(jié)果如表4所示,其中加粗的數(shù)據(jù)表示最佳結(jié)果。可以看出,EMDPC在Glass、Heart、Ionosphere、Libras movement、Dermatology、WDBC以及Titanic上得到的聚類結(jié)果均比其他5種對(duì)比算法稍好些。這是因?yàn)檫@些真實(shí)流形數(shù)據(jù)集上的數(shù)據(jù)點(diǎn)密度不盡相同,其他對(duì)比算法容易將低密度簇中的數(shù)據(jù)點(diǎn)分配到標(biāo)簽不同的高密度簇中,從而導(dǎo)致不佳的聚類結(jié)果,而EMDPC通過電子分層模型縮小不同密度簇之間的密度差,使得低密度簇更容易被單獨(dú)識(shí)別出來,從而不被誤分類。在Ionosphere和Dermatology上,EMDPC取得6種對(duì)比算法中最高的ACC和ARI值,但其AMI值略低于DPC-SFSKNN的0.361 2和0.861 2,分別低了0.019 2和0.025 6。在Pima上,EMDPC的ACC值比其他5種對(duì)比算法略高,而DPC-SFSKNN取得了最高的ARI和AMI值。在Titanic上,EMDPC與SNN-DPC、DPC-SFSKNN、DPCSA取得一樣的ACC值為0.776 0,然而EMDPC的ARI和AMI結(jié)果要比SNN-DPC、DPC-SFSKNN和DPCSA的結(jié)果更高。在Titanic上DPC和DPC-KNN的結(jié)果沒有表示出來,原因是這兩種算法在Titanic上取不到聚類中心,不能將其聚類,故無法給出對(duì)應(yīng)的結(jié)果。

表4 8個(gè)真實(shí)數(shù)據(jù)集上的聚類結(jié)果

從表4中可以看出,EMDPC在大部分真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果要比其他5種對(duì)比算法更高。通過對(duì)比發(fā)現(xiàn)EMDPC的聚類性能在DPC的基礎(chǔ)上提升15%左右,這充分表明了在基于電子分層模型的局部密度和凝聚策略作用下的EMDPC具有優(yōu)良的聚類性能,能在密度分布不均的真實(shí)數(shù)據(jù)集上取得更為理想的聚類結(jié)果。

4 結(jié)束語

為了解決密度峰值聚類在密度不均勻的流形數(shù)據(jù)集上聚類性能不佳,由于人工干預(yù)增加聚類誤差的問題,本文提出了一種基于電子分層模型和凝聚策略的密度峰值聚類算法EMDPC。基于電子分層模型計(jì)算得到的數(shù)據(jù)點(diǎn)局部密度能有效縮小數(shù)據(jù)間過大的密度差,從而更易識(shí)別低密度簇。由一種新的簇間相似度將子簇凝聚,其能通過數(shù)據(jù)自身的特點(diǎn)自適應(yīng)得到聚類個(gè)數(shù),無需人工干預(yù)。通過分層模型得到的局部密度與凝聚策略能有效解決DPC在密度分布不均的流形數(shù)據(jù)上聚類效果不佳的問題。在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)進(jìn)一步驗(yàn)證了本文算法的有效性和優(yōu)越性。