李　根，王亞剛，周小偉，張鳳登

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093)

?

一種基于密度均值的譜聚類算法

李根，王亞剛，周小偉，張鳳登

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093)

傳統(tǒng)譜聚類算法在構(gòu)造相似度矩陣時，高斯核函數(shù)參數(shù)選取的無規(guī)律性會對聚類結(jié)果造成嚴(yán)重影響。針對的這一缺陷，提出一種基于密度均值的譜聚類算法。與傳統(tǒng)算法不同，該算法選取樣本點(diǎn)到周圍K個樣本點(diǎn)的平均距離作為尺度參數(shù)，并引入樣本點(diǎn)的密度信息，使得聚類結(jié)果更符合實(shí)際樣本的分布。同時，由于相似矩陣能自適應(yīng)不同的局部密度，使得該算法對樣本的空間分布并不敏感。在不同類型數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了算法的有效性和較高的魯棒性。

譜聚類；平均密度；相似矩陣；多尺度

譜聚類是一種多尺度算法。近年來該算法在語音識別、圖像分割[1]和文本檢索中應(yīng)用廣泛，尤其是在大數(shù)據(jù)的分類上越發(fā)引起人們的重視。建立在譜圖理論上的譜聚類算法具有將非線性不可分的樣本點(diǎn)空間轉(zhuǎn)化為凸樣本分布的能力，相比于傳統(tǒng)的聚類算法(如K-means)，其能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解[2]。

譜聚類算法具有比其他聚類算法更優(yōu)越的數(shù)據(jù)聚類性能，但由于其本身在構(gòu)造相似度矩陣時對尺度參數(shù)(核函數(shù)的寬度參數(shù)，控制了函數(shù)的徑向作用范圍)比較敏感，在處理多重尺度數(shù)據(jù)集時也存在結(jié)果不理想等問題。針對這一突出缺點(diǎn)，Zelnik-Manor和Perona提出的自調(diào)整譜聚類算法[3]，利用局部密度信息來給推導(dǎo)出局部尺度參數(shù)，從而形成了基于多尺度參數(shù)的相似度矩陣，相比統(tǒng)一尺度參數(shù)更能反映真實(shí)數(shù)據(jù)點(diǎn)之間的關(guān)系。實(shí)驗(yàn)表明，該算法可準(zhǔn)確分離出稀疏簇內(nèi)部包含的緊密簇，更加準(zhǔn)確地反映了數(shù)據(jù)點(diǎn)間的內(nèi)在聯(lián)系。但算法對數(shù)據(jù)點(diǎn)的位置分布沒有做全面的考慮, 仍存在不足之處。王玲[4]等人為了實(shí)現(xiàn)數(shù)據(jù)的全局一致性，提出了一種密度可調(diào)節(jié)的相似性度量矩陣，通過最短路徑算法對較高密度區(qū)域上的相似性進(jìn)行改進(jìn)，形成了完全不同于高斯核的另一種相似性度量方式。

本文在文獻(xiàn)[5]的基礎(chǔ)上進(jìn)行了改進(jìn), 提出一種基于密度均值的具有自適應(yīng)性的譜聚類算法。算法將樣本點(diǎn)與相鄰K個樣本點(diǎn)的距離平均值視為核函數(shù)尺度參數(shù)σ，自適應(yīng)地調(diào)整各個樣本之間的相似度,并引入鄰域密度信息，充分挖掘出了各樣本點(diǎn)內(nèi)在聯(lián)系，同時也避免了聚類結(jié)果對人為給定參數(shù)的影響。仿真結(jié)果表明，本文所提算法在處理簇密度相差較大的多重尺度數(shù)據(jù)集時具有良好的簇類效果，提高了聚類性能和質(zhì)量，且有一定的自適應(yīng)性和魯棒性。

1　譜聚類

1.1譜聚類原理

譜聚類算法來源于譜圖的劃分。其的核心思想是將樣本點(diǎn)聚類的問題轉(zhuǎn)化為一個無向圖的多路劃分的問題。樣本數(shù)據(jù)點(diǎn)被看成是無向G(V,E)，將其頂點(diǎn)視為集合V，帶權(quán)值的加權(quán)邊集合E={Sij}表示基于某一相似性度量，基于此計算的兩點(diǎn)間的相似度，用W表示待聚類數(shù)據(jù)點(diǎn)之間的相似度矩陣。在圖G中就把聚類問題轉(zhuǎn)化為在圖G上最優(yōu)圖劃分的問題，即將圖G(V,E)劃分為k個互不相交的子圖V1,V2,…,Vk，劃分后保證每個子集Vi內(nèi)的相似度程度較高，不同集合Vi和Vj之間的相似度程度較低[6]。

在譜聚類算法中，常用3種反映相似度的連接圖：ε鄰近連接圖、k最近臨階連接圖和全連接圖。多數(shù)文獻(xiàn)中均采用全連接圖。令sij表示xi和xj兩點(diǎn)之間的連接權(quán)值，以高斯核函數(shù)來定義兩個頂點(diǎn)之間的權(quán)值，其中參數(shù)σ稱為尺度參數(shù)。sij定義為

(1)

對于最優(yōu)圖譜的劃分，一個切實(shí)有效的求解方法就是將原有問題轉(zhuǎn)化為求解拉普拉斯矩陣的特征值和對應(yīng)的特征向量的問題。利用這些特征向量構(gòu)造出一個簡化的數(shù)據(jù)空間，在該空間中的數(shù)據(jù)分布結(jié)構(gòu)會更加明顯，并與原數(shù)據(jù)空間分部信息保持一致[7]。

1.2傳統(tǒng)譜聚類算法

傳統(tǒng)的譜聚類算法有眾多，其中最具代表性算法是Ng等人提出的NJW算法。NJW算法本質(zhì)是是利用相似矩陣的特征向量進(jìn)行聚類。選取全的譜圖劃分構(gòu)造相似矩陣，并求取其對應(yīng)的拉普拉斯矩陣，然后求出拉普拉斯前K個最大特征值對應(yīng)的特征向量，這樣在K維空間中形成與源數(shù)據(jù)一一對應(yīng)的映射，最后利用傳統(tǒng)的K-means或其他算法聚類，從而得到聚類結(jié)果。NJW算法步驟如下。

輸入 數(shù)據(jù)集經(jīng)X={x1,x2,…,xn}和聚類數(shù)目k。

輸出k個聚類結(jié)果Y1,Y2,…,Yk。

(1)根據(jù)高斯核函數(shù)構(gòu)造相似矩陣W;

(3)計算L的前k個最大特征向量u1,u2,…,uk，單位化得到矩陣V;

(4)通過K-means或其他經(jīng)典聚類算法對V向量進(jìn)行聚類，得到聚類結(jié)果{Y1,Y2,…,Yk}。

盡管NJW算法能將非凸數(shù)據(jù)空間轉(zhuǎn)化為線性可分的凸數(shù)據(jù)空間，但在使用高斯核函數(shù)構(gòu)造相似矩陣W時，聚類結(jié)果由于受尺度參數(shù)σ的影響，使得其結(jié)果具有不確定性。當(dāng)處理多重尺度數(shù)據(jù)集時，這種不確定性變得更加嚴(yán)重。一個有效的解決方法就是取多組尺度參數(shù)，重復(fù)多次聚類，最后得到最優(yōu)解，但這將導(dǎo)致計算機(jī)的開銷過大。圖1顯示了同一數(shù)據(jù)集在選取不同尺度參數(shù)時的聚類效果，可看出尺度參數(shù)的不同對聚類結(jié)果產(chǎn)生的影響。因此，只有選取特定的參數(shù)時(在本實(shí)驗(yàn)中取0.6或者0.8)，才能得到滿意的聚類結(jié)果。

圖1　不同尺度參數(shù)下的聚類結(jié)果

2　基于密度平均值的譜聚類算法

2.1算法提出

由于標(biāo)準(zhǔn)的譜聚類算法使用的是全局尺度參數(shù)，并未考慮到樣本點(diǎn)鄰域數(shù)據(jù)分布對聚類結(jié)果產(chǎn)生的影響，當(dāng)數(shù)據(jù)集具有多重尺度，密集簇和稀疏簇相互交錯時，傳統(tǒng)的譜聚類算法就無法得到較好的結(jié)果。

圖2　多重尺度數(shù)據(jù)集1

圖2顯示的是一個多重尺度數(shù)據(jù)集，其是由兩個半圓月亮形組成的密集簇和夾在之間的稀疏簇組成，其中樣本點(diǎn)A和B是位于上半弧形數(shù)據(jù)簇中，C是位于下半弧形數(shù)據(jù)簇中。在此假設(shè)AB和AC的距離相等即d(AB)=d(AC),由于傳統(tǒng)譜聚類算法是利用空間歐式距離來表征樣本點(diǎn)之間的相似度，由假設(shè)即可得出W(A,B)=W(A,C),即AB之間的相似度和AC之間的相似度相等，但客觀情況是由于AB位于同一個密集數(shù)據(jù)簇，其間的相似度應(yīng)該大于位于不同密度的AC之間的相似度。顯然傳統(tǒng)譜聚類算法不能較好地處理這類數(shù)據(jù)集的聚類。

為解決這種由于使用全局參數(shù)帶來的無法將密集和稀疏數(shù)據(jù)集帶來的問題，學(xué)者提出了Self-Tuning(STSC)算法。該算法將每個樣本點(diǎn)鄰域信息引入到相似矩陣的計算中，由此定義了可隨樣本點(diǎn)改變的自適應(yīng)參數(shù)，得到了這種情況下的相似度函數(shù)

(2)

其中，σi=d(si,sk)，表示樣本點(diǎn)si到其第k個最近樣本點(diǎn)的歐氏距離。同樣對于圖2，由于引入了鄰域的信息值，有σB>σC，使得σAσB>σAσC，繼而有W(A,B)>W(A,C)，這樣在同一密集區(qū)的樣本點(diǎn)更容易被聚集在一起，稀疏區(qū)的樣本點(diǎn)劃分為另一類。

雖然STSC能自動的對位于不同區(qū)域的樣本點(diǎn)間的相似度進(jìn)行微調(diào)，但其仍有不足之處。

圖3　多重尺度數(shù)據(jù)集2

如圖3所示，樣本點(diǎn)A位于稀疏區(qū)，樣本點(diǎn)B,C位于密集區(qū)，由STSC的理論卻依舊只能得到σB=σC，σAσB=σAσC，A,B和A,C之間的相似度W(A,B)=W(A,C)，這樣還是無法獲得正確的聚類結(jié)果。原因是樣本點(diǎn)所在鄰域的密度對數(shù)據(jù)之間的相似性有著嚴(yán)重的影響，兩個樣本點(diǎn)所在區(qū)域的密度相近時，其被劃分在一個類的概率越大，密度相差越遠(yuǎn)時，其被劃分在不同類的概率也就越大。

尺度針對這兩種算法的不足，在尺度自調(diào)整的思想上，提出基于密度均值的譜聚類算法(ADSC)。其基本思想是：在對具有多重尺度的數(shù)據(jù)聚類問題上，單一用歐氏距離來表征樣本點(diǎn)間的相似性無法全面的反映實(shí)際樣本點(diǎn)的相互聯(lián)系。在對STSC算法改進(jìn)的基礎(chǔ)上，將待聚類眼樣本點(diǎn)的密度值也引入相似度的計算過程中，用密度權(quán)值和距離權(quán)值綜合在一個相似矩陣中。通過數(shù)據(jù)點(diǎn)的歐式距離大小和密度信息來不斷調(diào)整相似度的值，這樣更加符合實(shí)際數(shù)據(jù)的相互關(guān)系。

2.2ADSC算法實(shí)現(xiàn)

基于上述分析，本文在文獻(xiàn)[3]和文獻(xiàn)[5]的基礎(chǔ)上重新定義了相似度函數(shù)表達(dá)式

(3)

輸入 數(shù)據(jù)集X={x1,x2,…,xn}和聚類目k。

輸出k個聚類結(jié)果{Y1,Y2,…,Yk}。

(4)通過K-means或其他經(jīng)典聚類算法對V向量進(jìn)行聚類，得到聚類結(jié)果{Y1,Y2,…,Yk}。

選取L前k個最大的特征值和其所對應(yīng)的特征向量的原因在于：可證明若空間上存在k個嚴(yán)格彼此分離的有限數(shù)據(jù)簇，矩陣L的前k個最大特征值全為1，第k+1個最大特征值嚴(yán)格小于1，且這兩個特征值之間的差值越大，反映出相同類間樣本分布越密集，不同類間分布越稀疏[8]。圖4顯示的是對于文章前面提到的STSC算法不能很好地產(chǎn)生聚類結(jié)果，但用ADSC算法就可以準(zhǔn)確地被聚合成兩個密集類和一個稀疏類，顯然更加符合實(shí)際。

圖4　ADSC在數(shù)據(jù)集2上的聚類結(jié)果

圖5顯示了在3維空間內(nèi)運(yùn)用ADSC算法的實(shí)現(xiàn)過程，圖5(a)表示原始數(shù)據(jù)集，在空間中程花瓣狀[9]，各坐標(biāo)值表示實(shí)際屬性值(下同)；圖5(b)表示帶有鄰域距離和密度信息的相似圖；圖5(c)表示該數(shù)據(jù)集在ADSC聚類結(jié)果；圖5(d)表示Silhoutette聚類性能評價指標(biāo)[10](幅值越接近1表示與聚類結(jié)果原數(shù)據(jù)集接近程度更高)。

圖5　基于密度平均算法的實(shí)現(xiàn)過程

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

為驗(yàn)證本文所提出算法的有效性和優(yōu)越性，本文分別在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上對傳統(tǒng)NJW譜聚類算法、共享鄰域自適應(yīng)譜聚類算法(STSC)和基于密度均值的譜聚類算法(ADSC)的聚類結(jié)果進(jìn)行對比實(shí)驗(yàn)。

3.1人工數(shù)據(jù)集

圖6給出了一個由兩條螺旋線構(gòu)成的數(shù)據(jù)集。圖6(a)為原始數(shù)據(jù)集，是由1 000個樣本點(diǎn)，2個屬性值構(gòu)成；圖6(b)是傳統(tǒng)NJW聚類方法聚類出來的結(jié)果，算法中高斯核參數(shù)σ取0.8，由于參數(shù)選取的不確定性導(dǎo)致了結(jié)果的不唯一；圖6(c)是在具有自動尺度調(diào)整的STSC聚類方法下的結(jié)果(鄰域樣本數(shù)k=7)，雖然大部分樣本點(diǎn)均有效地劃分在同一屬性的區(qū)域，但由于相似矩陣中沒有鄰域的密度信息，仍有部分的樣本點(diǎn)被錯誤的劃分在其他類中。

圖6　3種聚類方法結(jié)果對比

3.2真實(shí)數(shù)據(jù)集

為近一步驗(yàn)證本文所提出算法的聚類性能，選取UCI數(shù)據(jù)集上的Cancer、Diabetes、Ionospher、Iris數(shù)據(jù)集作為測試樣本數(shù)據(jù)。表1給出了真實(shí)數(shù)據(jù)集的樣本個數(shù)、類的個數(shù)和屬性的個數(shù)。

表1　4類真實(shí)數(shù)據(jù)集特征

表4給出了表列出的4種真實(shí)數(shù)據(jù)集在3種算法(NJW,STSC,ADSC)下的性能指標(biāo)。聚類性能采用誤差率來表示，誤差率越小，表示聚類的效果越好?？煽闯霰疚奶岢龅幕诿芏染档木垲愃惴ㄓ兄玫木垲愋Ч?。

表2　不同聚類算法下的誤差率

4　結(jié)束語

本文在文獻(xiàn)的基礎(chǔ)上，結(jié)合STSC聚類算法，提出了一種基于平均密度的聚類算法ADSC。將數(shù)據(jù)集鄰域密度的信息融合到了相似度矩陣的計算中，通過歐氏空間距離和平均密度來調(diào)整每個樣本點(diǎn)同其他樣本點(diǎn)之間的相似度。在人工數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集上同其他算法作了比較，結(jié)果表明該算法在聚類效果上有著明顯的提高。但算法在高維數(shù)據(jù)聚類的過程中，占用計算機(jī)資源較大，運(yùn)算時間較長，下一步將就這一缺陷做進(jìn)一步的研究。

[1]Agrawal D P,Zeng Q A. Introduction to wireless and mobile systems[M].Canada:Thomson Learning,2002.

[2]Von Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.

[3]Zelnik Manor L,Perona P.Self-tuning spectral clustering[J].Advances in Neural Information Processing Systems,2004,17(6):1601-1608.

[4]王玲,薄列峰,焦李成.密度敏感的半監(jiān)督譜聚類[J].軟件學(xué)報,2007,18(10):2412-2422.

[5]王雅琳,陳斌,王曉麗,等.基于密度調(diào)整的改進(jìn)自適應(yīng)譜聚類算法[J].控制與決策,2014,29(9):1681-1687.

[6]Malik J,Belongie S,Leung T,et al. Contour and texture analysis for image segmentation[J].International Journal of Computer Vision,2001,43(1):7-27.

[7]Ng A Y,Jordan M L,Weiss Y. On spectral clustering: analysis and an algorithm[C].Cambridge: Advances in Neural Information Processing Systems, MIT Press,2002.

[8]田錚,李小斌,句彥偉.譜聚類的擾動分析[J].中國科學(xué)E輯:信息科學(xué),2007,37(4):527-543.

[9]Hamidian A,Nilsson A.Performance of internet access solutions in mobile ad networks[J].Lecture Notes in Computer Science(LNCS),2004(3427):189-201.

[10] 蔡曉妍,戴冠中,楊黎斌.譜聚類算法綜述[J].計算機(jī)科學(xué),2008,35(7):14-18.

A Spectral Clustering Algorithm Based on Average Density

LI Gen, WANG Yagang, ZHOU Xiaowei, ZHANG Fengdeng

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

Choosing the scale parameter of gauss kernel function irregularly has a serious effect on clustering results when using traditional spectral clustering algorithm to construct similarity matrix. A spectral clustering algorithm based on average density is proposed, which usesKaverage neighbourhood distance as the scale parameter and introduces the local data density information, making clustering results in conformity with the practical data distribution. The adaptation of the similarity matrix to different local densities also makes the algorithm relatively insensitive to the spatial distribution of datasets. Experimental results on both different datasets show the effectiveness and good robustness of this proposed algorithm.

spectral clustering; average density; similarity matrix; multiple scales

10.16180/j.cnki.issn1007-7820.2016.08.022

2015-11-22

上海市自然科學(xué)基金資助項(xiàng)目(15ZR1429300)

李根(1990-)，男，碩士研究生。研究方向：嵌入式控制等。

TP301.6

A

1007-7820(2016)08-074-05