基于共享逆近鄰與指數(shù)核的密度峰聚類算法

高 月,楊小飛,馬盈倉,汪義瑞

(1.西安工程大學(xué) 理學(xué)院,陜西 西安 710048;2.安康學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,陜西 安康 725000)

0 引 言

聚類分析是模式識(shí)別、圖像處理、生物信息分析等領(lǐng)域[1-3]重要的研究分支之一,也是最為常見且具有潛力的發(fā)展方向之一。聚類分析是根據(jù)某種相似性度量分析數(shù)據(jù)集,將沒有標(biāo)簽的數(shù)據(jù)劃分成若干個(gè)不同的簇,使得同一個(gè)簇中的樣本點(diǎn)彼此相似,不同簇中的樣本點(diǎn)彼此不同。常用的聚類方法主要有5種:基于劃分的方法[4-5],基于層次的方法[6-8],基于網(wǎng)格的方法[9-10],基于模型的方法[11],基于密度的方法[12-13]。

密度峰聚類算法(clustering by fast search and find of density peaks, DPC)是2014年由Rodriguea[13]提出的，該算法可以自動(dòng)選取樣本的聚類中心點(diǎn),而且可以處理任意形狀的數(shù)據(jù)。算法選取聚類中心的原則是:具有較高局部密度,且與其他高密度點(diǎn)之間的“距離”較大。盡管DPC算法相比其他聚類算法具有明顯優(yōu)勢,但也存在一些缺點(diǎn)。①算法的局部密度定義問題。算法的相似度與密度僅通過歐氏距離與截?cái)嗑嚯xdc確定,使得算法在高維或多密度數(shù)據(jù)集中的聚類效果相對較差[14]。②算法的聚類策略問題。算法將樣本點(diǎn)劃分到距其最近且密度比其大的樣本所在的簇,這樣的分配策略很容易出現(xiàn)多米諾骨牌效應(yīng),即一個(gè)樣本點(diǎn)分配錯(cuò)誤進(jìn)而導(dǎo)致一連串的樣本點(diǎn)分配錯(cuò)誤。

對此一些相應(yīng)的改進(jìn)算法被提出[15-18]。 KNN-DPC算法[15]是一種基于k個(gè)最近鄰居的密度峰聚類,算法將k個(gè)最近鄰居的思想引入DPC算法中構(gòu)造相似度。樣本的近鄰點(diǎn)可以更好地反映數(shù)據(jù)集的局部分布特征,有效提高了DPC算法的聚類效果。謝娟英等[16]提出了一種基于K-近鄰的快速密度峰值搜索并高效分配樣本的聚類算法,算法通過樣本點(diǎn)的K-近鄰定義局部密度,并且提出2種基于K-近鄰的樣本分配策略,由于該算法發(fā)現(xiàn)數(shù)據(jù)集的隱藏信息,從而提高了數(shù)據(jù)集的聚類效果。NDPC算法[17]基于逆近鄰構(gòu)造局部密度,有效解決了密度不均衡問題。文獻(xiàn)[18]提出一種基于共享K-近鄰的密度峰算法,算法通過共享K-近鄰定義新的相似度與密度,并提出兩步分配策略,有效解決了DPC算法中局部密度定義問題和聚類分配策略問題。

目前,大部分密度峰聚類算法在構(gòu)造樣本點(diǎn)的相似度時(shí)都忽略了兩點(diǎn)之間的共享逆近鄰,兩點(diǎn)的共享逆近鄰能更好表示數(shù)據(jù)之間的相似性。為了更好地解決上述問題,本文提出一種基于共享逆近鄰與指數(shù)核的相似度,通過該相似度構(gòu)造一種新的密度,并通過DPC算法初始聚類后應(yīng)用到凝集層次聚類(GDL)算法中,形成基于共享逆近鄰與指數(shù)核的密度峰聚類算法(SRNNEK-DPC)。

1 相關(guān)算法

1.1 DPC算法

DPC算法[13]假定每個(gè)簇中密度最大的點(diǎn)為聚類中心,并且該點(diǎn)被所在簇中的其他密度較低的點(diǎn)所包圍,同時(shí)每個(gè)簇中的聚類中心點(diǎn)都相距較遠(yuǎn)。 DPC算法中的相關(guān)定義如下:

定義1局部密度 設(shè)樣本集X={x1,x2,…,xN},DPC算法通過截?cái)嗑嚯x和樣本點(diǎn)之間的歐氏距離計(jì)算樣本的局部密度ρ。假設(shè)樣本點(diǎn)xi∈X,則樣本點(diǎn)xi的局部密度定義為

(1)

當(dāng)數(shù)據(jù)集較小時(shí),DPC算法借助指數(shù)核函數(shù)定義樣本的局部密度

(2)

定義2距離 如果樣本點(diǎn)xj的密度ρj高于xi的密度ρi,則距離δi為樣本點(diǎn)xi與xj的最小距離。此外,如果xi的密度ρi最大,則δi為xi到其他點(diǎn)的最遠(yuǎn)距離定義為

(3)

定義3聚類中心 樣本的聚類中心點(diǎn)由樣本點(diǎn)的局部密度ρ和距離δ共同確定。理想的聚類中心定義為相距較遠(yuǎn)且密度較高的點(diǎn),即局部密度ρ和距離δ相對較大。定義如下:

γi=ρiδi

(4)

選取前L個(gè)較大的γ值所對應(yīng)的點(diǎn)為聚類中心點(diǎn),這里L(fēng)為最終聚類個(gè)數(shù)。

1.2 GDL算法

GDL算法[19]是一種簡單有效的基于圖的凝聚層次聚類算法,用于聚類高維數(shù)據(jù)。算法首先生成多個(gè)初始類簇,然后迭代選擇具有最大親和度的2個(gè)類簇進(jìn)行合并。主要通過平均入度和平均出度的乘積定義簇的相似度度量。平均入度反映樣本附近的密度,平均出度刻畫樣本周圍的局部密度。該算法具有性能好,易于實(shí)現(xiàn),計(jì)算效率高等優(yōu)點(diǎn)。

GDL算法中的初始類簇L′=e×L,其中e為要設(shè)置的自由參數(shù),L為最終聚類簇?cái)?shù)。該算法聚類相似度定義如下:

設(shè)樣本X={x1,x2,…,xN},構(gòu)建有向圖G=(V,E),其中V是對應(yīng)于X中樣本的頂點(diǎn)集,E是連接頂點(diǎn)的邊集。該圖與加權(quán)鄰接矩陣W=[wij]相關(guān)聯(lián),其中wij是從頂點(diǎn)i到j(luò)的邊的權(quán)重。為了捕獲高維空間中的流形結(jié)構(gòu),該算法使用KNN圖,其中權(quán)重被定義為

(5)

(6)

簇Cb到Ca的相似度定義為

(7)

那么Ca和Cb之間的對稱相似度為

ACa,Cb=ACb→Ca+ACa→Cb

(8)

2 SRNNEK-DPC算法

2.1 定義

定義4共享逆近鄰[20]設(shè)R(i)為樣本點(diǎn)xi的逆近鄰,R(j)為樣本點(diǎn)xj的逆近鄰,則樣本點(diǎn)xi與xj的共享逆近鄰Rs(i,j)定義如下:

Rs(i,j)=R(i)∩R(j)

(9)

定義5相似度 假設(shè)樣本點(diǎn)xi,xj∈X,則樣本點(diǎn)xi與xj之間的相似度S(i,j)定義如下:

S(i,j)=|Rs(i,j)|·

(10)

式中:||表示集合元素的個(gè)數(shù);q為樣本點(diǎn)xi與xj的共享逆近鄰點(diǎn)。

由式(10)可得,當(dāng)xi、xj與其共享逆近鄰點(diǎn)的距離較大或共享逆近鄰數(shù)較少時(shí),這2個(gè)點(diǎn)的相似度較小;當(dāng)xi、xj與其共享逆近鄰點(diǎn)的距離較小或共享逆近鄰數(shù)較多時(shí),這2個(gè)點(diǎn)的相似度較大。說明了該相似度同時(shí)涉及到距離信息和局部結(jié)構(gòu)信息,從而能更好地解決密度不均衡問題和高維數(shù)據(jù)的分布問題。

樣本點(diǎn)的逆近鄰能更好地反映密度變化[20]。因此,樣本點(diǎn)的密度定義為每個(gè)點(diǎn)與其逆近鄰點(diǎn)的相似度之和。

定義6密度 假設(shè)樣本點(diǎn)xi∈X,則樣本點(diǎn)xi的密度定義如下:

(11)

DPC算法與SRNNEK-DPC算法在人工數(shù)據(jù)集上的聚類結(jié)果如圖1所示。從圖1(a)可看出，該數(shù)據(jù)集為多密度人工數(shù)據(jù)集,由2個(gè)稀疏簇和1個(gè)密集簇組成。從圖1(b)、(c)中可以看出,由于DPC算法的局部密度定義問題導(dǎo)致聚類中心選取錯(cuò)誤,在密集簇中有2個(gè)聚類中心,而其中1個(gè)稀疏簇中沒有聚類中心。由于算法的聚類中心選取問題和聚類策略問題進(jìn)而導(dǎo)致聚類結(jié)果不精確。而本文提出的SRNNEK-DPC算法較DPC算法的聚類結(jié)果更準(zhǔn)確的找出了該數(shù)據(jù)集中稀疏簇和密集簇的聚類中心,并且將其余樣本點(diǎn)準(zhǔn)確的劃分到簇中。由上可得,本文提出的算法有效改善DPC算法的缺陷并且可以更加準(zhǔn)確地對數(shù)據(jù)進(jìn)行聚類。

2.2 SRNNEK-DPC算法流程

輸入:樣本X={x1,x2,…,xN}，初始聚類簇?cái)?shù)為L′,最終聚類簇?cái)?shù)為L。

輸出:聚類結(jié)果C={C1,C2,…,CL}。

步驟1 通過式(10)計(jì)算每個(gè)樣本點(diǎn)xi與其逆近鄰點(diǎn)的相似度。

步驟3 通過式(3)計(jì)算每個(gè)點(diǎn)xi對應(yīng)的距離δi。

步驟5 首先對得到的γ={γ1,γ2,…,γN}進(jìn)行降序排序,然后在排序后的列表中選取前L′個(gè)樣本點(diǎn)作為聚類中心。

步驟10 如果L′>L,轉(zhuǎn)到步驟7,否則,轉(zhuǎn)到步驟11。

步驟11 返回C。

2.3 時(shí)間復(fù)雜度

SRNNEK-DPC算法的時(shí)間復(fù)雜度主要由4部分構(gòu)成:①計(jì)算樣本點(diǎn)之間的相似度,時(shí)間復(fù)雜度為O(n2)。②計(jì)算樣本點(diǎn)的密度,時(shí)間復(fù)雜度為O(n2)。③生成初始類簇,時(shí)間復(fù)雜度為O(n)。④生成最終類簇,時(shí)間復(fù)雜度為O(n3)。綜上可得,SRNNEK-DPC算法的整體時(shí)間復(fù)雜度為O(n3)。

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

以準(zhǔn)確率(accuracy,ACC)[21]和標(biāo)準(zhǔn)化互信息(normalized mutual information,NMI)[22]為評價(jià)指標(biāo)驗(yàn)證SRNNEK-DPC算法的有效性,在真實(shí)數(shù)據(jù)集上進(jìn)行聚類實(shí)驗(yàn),并與K-means 算法、DPC算法、KNN-DPC算法、CLR算法、GDL算法和NDPC算法進(jìn)行比較。

實(shí)驗(yàn)參數(shù)設(shè)置如下:對于K-means算法,每個(gè)數(shù)據(jù)集分別做10次實(shí)驗(yàn)并取結(jié)果的平均值;對于DPC算法,設(shè)置p%位置對應(yīng)的距離為算法的截?cái)嗑嚯xdc,根據(jù)文獻(xiàn)[14],設(shè)置參數(shù)p的取值范圍為[1,2,5,10,20,60];對于KNN-DPC算法,參數(shù)k的值由k=p×N確定,其中N為數(shù)據(jù)集中樣本點(diǎn)的個(gè)數(shù),p的取值范圍與DPC算法相同;對于GDL算法,根據(jù)文獻(xiàn)[19]設(shè)置參數(shù);對于SRNNEK-DPC算法,設(shè)置近鄰參數(shù)k為[1,25],初始聚類簇?cái)?shù)e的取值范圍為{5,10},由于該算法中參數(shù)較多,設(shè)定構(gòu)建KNN圖的參數(shù)k的取值范圍為[5,20],參數(shù)a為1;對于NDPC算法,根據(jù)文獻(xiàn)[17],設(shè)置參數(shù)p的取值范圍為{1,3,10}。

本小節(jié)選取8個(gè)數(shù)據(jù)分布各不相同的數(shù)據(jù)集[23-26]對各個(gè)算法進(jìn)行聚類實(shí)驗(yàn)。詳細(xì)信息如表1所示。

表 1 真實(shí)數(shù)據(jù)集Tab.1 The real datasets

各算法在真實(shí)數(shù)據(jù)集中的聚類結(jié)果如表2～3所示,表中加粗?jǐn)?shù)據(jù)為該數(shù)據(jù)集在幾個(gè)算法中的最優(yōu)值。由表2可知,除了Iris數(shù)據(jù)集,在其他數(shù)據(jù)集中SRNNEK-DPC算法的聚類精度要優(yōu)于其他算法,而在Iris數(shù)據(jù)集中,KNN-DPC算法的聚類精度優(yōu)于SRNNEK-DPC算法,但2個(gè)算法的聚類精度相差不大。由表3可知,在 Yeast數(shù)據(jù)集與Uspst數(shù)據(jù)集中GDL算法的標(biāo)準(zhǔn)互信息值要高于SRNNEK-DPC算法,而其他數(shù)據(jù)集中SRNNEK-DPC算法的實(shí)驗(yàn)結(jié)果都是最優(yōu)的。綜上可得,SRNNEK-DPC算法實(shí)驗(yàn)結(jié)果在多數(shù)情況下優(yōu)于其他幾種對比算法。

表 2 實(shí)驗(yàn)算法在真實(shí)數(shù)據(jù)集中的準(zhǔn)確率Tab.2 Accuracy of experimental algorithms in real datasets

表 3 實(shí)驗(yàn)算法在真實(shí)數(shù)據(jù)集中的標(biāo)準(zhǔn)互信息Tab.3 Standard mutual information of experimental algorithms in real datasets

為了更好地說明SRNNEK-DPC算法在高維數(shù)據(jù)的聚類效果,選取ORL人臉數(shù)據(jù)集[26]中前20個(gè)人的人臉圖像進(jìn)行聚類實(shí)驗(yàn),并將SRNNEK-DPC算法與DPC算法對比。ORL-20數(shù)據(jù)集總共包含20個(gè)人的人臉圖像, 每人均有10張不同表情和角度的圖像。圖2、3分別為DPC算法和SRNNEK-DPC算法在ORL-20人臉數(shù)據(jù)集上的聚類效果圖,同一類簇用相同顏色表示。

對比圖2、3可以看出,在ORL-20人臉數(shù)據(jù)集第3類和第4類(即聚類效果圖中第2行的人臉數(shù)據(jù)) 中,SRNNEK-DPC算法僅有一個(gè)錯(cuò)誤聚類的人臉,而DPC算法將這2類人臉數(shù)據(jù)錯(cuò)誤聚成了4類;在第5類(第3行左)和第13類(第7行左)中,DPC算法將2類人臉數(shù)據(jù)錯(cuò)誤聚成了一類,而

SRNNEK-DPC算法對這2類的聚類結(jié)果完全正確。結(jié)合表2可得,SRNNEK-DPC算法的精度要高于DPC算法。因此,本文所提出的算法有效提高了高維數(shù)據(jù)的聚類精度。

4 結(jié) 語

SRNNEK-DPC算法借助逆近鄰與指數(shù)核定義了一種新的相似度與密度,這種新的密度被應(yīng)用到DPC算法中可以更準(zhǔn)確的發(fā)現(xiàn)數(shù)據(jù)集的聚類中心,有效解決了DPC算法中局部密度定義問題;進(jìn)而與GDL算法結(jié)合有效提高了高維數(shù)據(jù)的聚類精度。但是,SRNNEK-DPC算法的時(shí)間復(fù)雜度要高于DPC算法,優(yōu)化算法的整體復(fù)雜度以及與其他聚類算法有效結(jié)合有待進(jìn)一步研究。