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

許洪瑋

（廣東工業(yè)大學(xué)信息工程學(xué)院，廣東廣州 510006）

聚類算法是要將數(shù)據(jù)集中具有相似性的數(shù)據(jù)劃分為一類，而將不相似的數(shù)據(jù)劃分為不同類，最終實(shí)現(xiàn)將數(shù)據(jù)集劃分為若干類。其主要過程包括確定樣本數(shù)據(jù)、獲取特征、計(jì)算特征值、計(jì)算相似度、評估聚類結(jié)果的有效性等步驟。聚類算法可以按照聚類原理分為：劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法、基于圖論的方法等。

譜聚類算法（Spectral Clustering Algorithm）與K-means算法、EM算法和模糊C均值聚類算法（Fuzzy C-mean Clustering,FCM）等傳統(tǒng)的聚類算法不同，不需要聚類對象具有凸球形或其他特定形狀，就能在任意形狀的樣本空間上實(shí)現(xiàn)聚類。譜聚類算法的思想源自譜圖劃分理論[1]，該算法的核心思想是：計(jì)算樣本數(shù)據(jù)集所描述成數(shù)據(jù)點(diǎn)的相似度矩陣，通過特征分解，計(jì)算矩陣的特征值和特征向量（也就是譜信息），然后選擇合適的特征向量作為數(shù)據(jù)的低維空間描述，之后對選擇的特征向量應(yīng)用K-means等方法進(jìn)行聚類，聚類的結(jié)果最后映射回原數(shù)據(jù)空間。譜聚類算法是一種點(diǎn)對聚類算法，其本質(zhì)是用圖的最優(yōu)劃分思想處理聚類問題，解決了高維特征向量的奇異問題，因?yàn)樗缓蛿?shù)據(jù)集的規(guī)模有關(guān)，而與數(shù)據(jù)集的維數(shù)無關(guān)。

以下幾個方面，是譜聚類算法相比傳統(tǒng)聚類算法的優(yōu)點(diǎn)：

（1）譜聚類算法不對數(shù)據(jù)集的全局結(jié)構(gòu)進(jìn)行假設(shè)，其思想簡單、實(shí)現(xiàn)方便；

（2）譜聚類算法是一種點(diǎn)對聚類方法，它與數(shù)據(jù)的特征向量維數(shù)無關(guān)，只與數(shù)據(jù)的個數(shù)有關(guān)，可用于解決高特征向量維數(shù)的奇異性問題；

（3）譜聚類算法可以通過特征向量分解，在放松了的連續(xù)域中獲得全局最優(yōu)解。

因此，譜聚類算法成為解決實(shí)際應(yīng)用問題的新方法，可應(yīng)用于圖像分割、視頻分割、語音識別、文本挖掘等研究領(lǐng)域的問題解決。盡管譜聚類方法在一些問題的解決上取得了不錯的效果，但還有許多值得深入研究的問題。

本文主要對一些基本算法進(jìn)行概述，包括：圖譜和譜分解的基本概念、傳統(tǒng)譜聚類算法的概述、基于密度聚類算法概述和評價(jià)指標(biāo)Rand Index。

1 圖的譜及圖的譜分解概述

譜圖劃分理論是譜聚類算法的思想來源，圖的譜分布與圖的結(jié)構(gòu)之間的對應(yīng)關(guān)系是近年來興起的相當(dāng)活躍的研究課題，其中特征值及相關(guān)概念是研究的集中方向。下面簡要介紹譜的基本概念[2]。

圖的表示方法為G=(V,E)，其中V={v1,v2,...,vn}是頂點(diǎn)或點(diǎn)的集合，E={e1,e2,...,em}是連接任意兩個點(diǎn)的邊的集合，頂點(diǎn)的個數(shù)n=|V|，邊的個數(shù)m=|E|。如果連接頂點(diǎn)u、v的邊euv的值是無窮的，則稱頂點(diǎn)u、v是不相鄰的，否則是相鄰的；如果邊e1和e2有一個共同的頂點(diǎn)，則稱邊e1和e2是相鄰的，否則是不相鄰的。以頂點(diǎn)v為端點(diǎn)的邊數(shù)稱為頂點(diǎn)v的度，記為dv。

如果兩個頂點(diǎn)之間的邊數(shù)不止一條，則稱為多重邊；如果一條邊的兩個頂點(diǎn)是相同的，則稱為邊的環(huán)。不含有多重邊和環(huán)的圖稱為簡單圖，含有多重邊的圖稱為多重圖。每一對頂點(diǎn)間都有邊相連的無向簡單圖稱為完全圖。本文所討論的圖全部都是完全圖。

記A(G)表示圖G的鄰接矩陣，有如下的定義：

定義（1）圖G的特征值就是對應(yīng)鄰接矩陣A(G)的特征值，用λi(i=1,...,n)表示。

定 義（2）圖G的n個 特征值λi(i=1,...,n)的序 列（λ1≥λ2≥...≥λn）稱為圖G的譜。

定義（3）圖G的最大特征值λi稱為圖G的譜半徑。

定義（4）圖G的拉普拉斯特征值就是拉普拉斯矩陣L(G)的特征值。

拉普拉斯矩陣L(G)可表示為：L(G)=D(G)-A(G)，其中D(G)是圖G的度矩陣，A(G)是圖G的鄰接矩陣。

圖的特征值是圖的同構(gòu)不變量，是圖論的一個重要研究課題，而我們希望通過譜方法來實(shí)現(xiàn)對圖的描述。下面簡要介紹圖的譜分析與譜分解。

通過計(jì)算圖的鄰接矩陣的?？梢缘玫綀D的譜特征，我們以特征值的次序來決定特征向量的次序。

如果用鄰接矩陣的特征值來構(gòu)成圖G的譜特征，那么圖G的向量B可表示為：

其中λ1≥λ2≥...≥λn，這一向量就表示了圖G的譜。

如果用拉普拉斯矩陣的特征值來構(gòu)成譜特征，那么圖的向量B可表示為：

其中μ1≥μ2≥...≥μn，這一向量表示圖G的拉普拉斯。

圖的譜方法是通過圖的譜特征向量來表示圖的結(jié)構(gòu)信息，這樣，一旦獲得圖的特征向量，那么一張圖就可以在特征空間上表示為一組數(shù)據(jù)，這就成為進(jìn)一步處理圖數(shù)據(jù)的基礎(chǔ)。

圖的譜方法主要有兩個方面的優(yōu)點(diǎn)。第一：計(jì)算復(fù)雜度較低。因?yàn)閳D的譜方法可以只選取部分有效的特征來表達(dá)圖的信息，這樣就不用對圖本身進(jìn)行計(jì)算，其計(jì)算復(fù)雜就被大大降低了。第二：可以用于表達(dá)海量數(shù)據(jù)的圖。海量數(shù)據(jù)的圖需要用一個好的數(shù)學(xué)表達(dá)式才能很好地表達(dá)，而尋找一個好的數(shù)學(xué)表達(dá)式往往是非常苦難的，但圖的譜方法就可以實(shí)現(xiàn)這種表達(dá)。

圖的譜方法自身也存在一些不足。因?yàn)檫x取的譜特征是有限的，這樣就不能完整地表達(dá)圖的全部結(jié)構(gòu)信息，從而造成計(jì)算精確度的不夠；另外可能會出現(xiàn)不同的圖但它們的譜特征表達(dá)是一樣的，也就是一譜多圖的情況。

2 傳統(tǒng)譜聚類算法概述

譜聚類（Spectral Clustering）是基于圖論的方法把聚類問題轉(zhuǎn)換為組合優(yōu)化問題，具體來說，就是將數(shù)據(jù)集表示成一個圖中所有頂點(diǎn)的集合，用圖相應(yīng)的邊的權(quán)重表示數(shù)據(jù)之間的相似度，這樣就可以利用圖論和圖形學(xué)的原理進(jìn)行分析并實(shí)現(xiàn)數(shù)據(jù)聚類。

若把圖中的頂點(diǎn)V表示成數(shù)據(jù)集中的每一個樣本，連接頂點(diǎn)間的邊E上的權(quán)重值W相應(yīng)表示成樣本數(shù)據(jù)間的相似度，這樣就可以用無向加權(quán)圖G=(V,E,W)表示整個數(shù)據(jù)集及數(shù)據(jù)樣本間的關(guān)系。因此，可以應(yīng)用圖的劃分方法解決樣本數(shù)據(jù)集的聚類問題。圖論的最優(yōu)劃分理論，就是使得被劃分成的子圖內(nèi)部相似度盡可能大，而劃分成的若干子圖之間相似度盡可能小[3]。圖劃分準(zhǔn)則常用的有：規(guī)范割集、比例割集、平均割集、最小割集以及最小最大割集等劃分準(zhǔn)則。由于圖劃分問題的本質(zhì)是組合問題，其最優(yōu)解求解是一個NP難題，可以通過相似度矩陣或拉普拉斯(Laplacian)矩陣的譜分解方式來解決，這種處理方法統(tǒng)稱為譜聚類。

譜聚類算法根據(jù)不同的圖劃分準(zhǔn)則有不同的具體實(shí)現(xiàn)方法，下面是由Andrew Y.Ng[4]提出的譜聚類算法。

如果要將樣本空間上的數(shù)據(jù)集S={s1,...,sn}，劃分成k個子集（類），則具體實(shí)現(xiàn)步驟為：

（1）構(gòu)造數(shù)據(jù)集S的相似度矩陣A，矩陣A的構(gòu)造公式為：

（2）對角矩陣D的第（i,i）個元素的值是矩陣A的第i行全部元素的累加和，這樣就可構(gòu)造矩陣L，其計(jì)算公式為：

（3）計(jì)算矩陣L的特征值和特征向量，x1,x2,...,xk是最大的k個特征值所對應(yīng)的特征向量，可得到n行k列的矩陣X，X=[x1x2...xk]；

（4）將矩陣X歸一化為矩陣Y，歸一化公式為：

（5）對矩陣Y使用K-means算法進(jìn)行分類，矩陣Y的第i行對應(yīng)數(shù)據(jù)集S的第i個數(shù)據(jù)Si;

（6）矩陣Y的第i行所屬的類，就是數(shù)據(jù)集S中的數(shù)據(jù)si所屬的類，這樣就完成了對數(shù)據(jù)集的分類。

這里，尺度函數(shù)σ2是敏感參數(shù)，控制著兩個數(shù)據(jù)點(diǎn)之間歐氏距離的衰減程度，也直接影響著隨后的聚類效果。

譜聚類算法雖然能在一些數(shù)據(jù)集上取得較好的聚類結(jié)果如環(huán)形數(shù)據(jù)集，但對于分布比較復(fù)雜的數(shù)據(jù)集，如螺旋形數(shù)據(jù)集，該算法的聚類結(jié)果就差強(qiáng)人意了。這是因?yàn)樽V聚類算法是通過高斯核函數(shù)來表示數(shù)據(jù)間的相似度關(guān)系，也就是在新的空間對原始的數(shù)據(jù)關(guān)系，歐氏距離關(guān)系，重新建立起映射關(guān)系，而這種映射關(guān)系只對簡單的空間分布有效，而不能正確反映空間分布比較復(fù)雜的數(shù)據(jù)關(guān)系。鑒于該算法的不足之處，研究者們不斷提出了新的改進(jìn)方法。

3 DBSCAN聚類算法概述

DBSCAN[5]聚類算法是由Martin Ester等人在1996年提出的，該算法是典型的密度聚類算法，通過高密度連通性來快速發(fā)現(xiàn)任意形狀的類，并同時(shí)排除噪聲的干擾。

DBSCAN算法的核心參數(shù)有最小半徑Eps和最少對象數(shù)目MintPts，就是在其規(guī)定半徑Eps范圍內(nèi)，所包含的數(shù)據(jù)點(diǎn)數(shù)不能少于給定的數(shù)目MintPts。DBSCAN算法定義了密度可達(dá)的概念，是在一個類能夠被其中任意一個核心對象點(diǎn)所確定的前提下，劃分出數(shù)據(jù)集的各個類的。首先，選中數(shù)據(jù)集P中的任意對象點(diǎn)m，查找符合Eps和MinPts條件并從對象點(diǎn)m密度可達(dá)的所有對象點(diǎn)。如果對象點(diǎn)m是核心點(diǎn)，則根據(jù)算法可以確定一個類；如果對象點(diǎn)m是邊界點(diǎn)，且點(diǎn)m無法密度到達(dá)其他數(shù)據(jù)點(diǎn)，則點(diǎn)m被暫時(shí)標(biāo)注為噪聲點(diǎn)。然后，算法選取下一個數(shù)據(jù)點(diǎn)，并按同樣的方法進(jìn)行。

DBSCAN算法步驟：

（1）輸入?yún)?shù)值Eps和MinPts；

（2）選取數(shù)據(jù)集中的任意一個點(diǎn)m，對其進(jìn)行區(qū)域查詢；

（3）如果點(diǎn)m是核心點(diǎn)，則查找從m點(diǎn)密度可達(dá)的所有點(diǎn)，并形成一個類；

（4）否則，點(diǎn)m被暫時(shí)標(biāo)注為噪聲點(diǎn)；

選取下一個數(shù)據(jù)點(diǎn)，重復(fù)步驟（2）到（4），直到處理完數(shù)據(jù)集中的所有點(diǎn)。

由于DBSCAN算法的參數(shù)Eps和MinPts是全局參數(shù)，比較難以確定，都必須靠先驗(yàn)知識來設(shè)定，而且這兩個參數(shù)直接影響著算法的聚類性能，這樣就可能導(dǎo)致部分密度小的聚類被處理為噪聲；而對于邊界點(diǎn)，若該點(diǎn)附近密度較大就會形成單連通，出現(xiàn)錯誤分類結(jié)果。

4 聚類性能的評價(jià)指標(biāo)

聚類算法的最終結(jié)果是實(shí)現(xiàn)數(shù)據(jù)集的劃分，而聚類結(jié)果的好壞需要進(jìn)行有效性和質(zhì)量評價(jià)。聚類質(zhì)量的評價(jià)方法可以分為內(nèi)部度量、外部度量和相對度量三類，并且每種度量方法有不同的計(jì)算方式。這里對外部度量方法中的一種計(jì)算方式——Rand Index[6]進(jìn)行介紹。

Rand Index是由Milligan和Cooper提出的一種聚類質(zhì)量評價(jià)指標(biāo)，用于衡量聚類結(jié)果與數(shù)據(jù)的外部標(biāo)準(zhǔn)類之間的一致程度。

對于數(shù)據(jù)集X={x1,x2,...,xn}，假設(shè)S={s1,s2,...,sk}和R={r1,r2,...,rk}是數(shù)據(jù)集X的兩種不同劃分，其中S是外部標(biāo)準(zhǔn)劃分類，而R是算法的聚類結(jié)果。那么Rand Index的計(jì)算公式如下：

公式(6)中a表示S和R中都屬于相同類的個數(shù)，b表示屬于S中一類而不屬于R中同一類的個數(shù)，c表示屬于R中同一類而不屬于S中同一類的個數(shù)，d表示都不屬于S和R中同一類的個數(shù)。a和d反映了兩種劃分的一致性，而b和c放映了不一致性。

Rand Index的數(shù)值在[0,1]的區(qū)間內(nèi)，其值越大，則表示兩種劃分的一致性就越高，當(dāng)兩種劃分完全一致時(shí)，Rand Index取值為1。

5 結(jié)語

近年來，譜聚類算法成為聚類算法的熱門研究課題，也不斷涌出新算法和新研究成果。該算法可以很好地應(yīng)用于解決具有非凸分布的實(shí)際問題，而如何構(gòu)建一個正確反映數(shù)據(jù)間關(guān)系的相似度矩陣，是譜聚類算法研究的重點(diǎn)難點(diǎn)。希望本文對傳統(tǒng)譜聚類算法的介紹可以對初學(xué)者提供初步的學(xué)習(xí)借鑒。