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

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

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

?

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

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

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

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

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

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

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

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

1　譜聚類

1.1譜聚類原理

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

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

(1)

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

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

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

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

輸出k個聚類結果Y1,Y2,…,Yk。

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

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

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

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

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

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

2.1算法提出

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

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

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

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

(2)

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

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

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

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

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

2.2ADSC算法實現(xiàn)

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

(3)

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

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

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

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

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

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

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

3　實驗結果

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

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

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

圖6　3種聚類方法結果對比

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

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

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

表4給出了表列出的4種真實數(shù)據(jù)集在3種算法(NJW,STSC,ADSC)下的性能指標。聚類性能采用誤差率來表示，誤差率越小，表示聚類的效果越好。可看出本文提出的基于密度均值的聚類算法有著更好的聚類效果。

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

4　結束語

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

[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].軟件學報,2007,18(10):2412-2422.

[5]王雅琳,陳斌,王曉麗,等.基于密度調(diào)整的改進自適應譜聚類算法[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].中國科學E輯:信息科學,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].計算機科學,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

上海市自然科學基金資助項目(15ZR1429300)

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

TP301.6

A

1007-7820(2016)08-074-05