基于特征向量自動(dòng)選取的譜聚類算法

何家玉+許峰

摘 要：根據(jù)譜聚類矩陣特征向量組的分段常值性，提出一種基于特征向量組自動(dòng)選取的譜聚類算法。其基本思想是：首先根據(jù)數(shù)據(jù)集計(jì)算出非對(duì)稱規(guī)范Laplace矩陣，然后選擇其前個(gè)特征向量，最后利用本征間隙法從上述特征向量中自動(dòng)選取包含聚類信息的特征向量。實(shí)驗(yàn)表明，該算法在一定程度上解決了特征向量自動(dòng)選取問題，可以獲得質(zhì)量較高的聚類結(jié)果。

關(guān)鍵詞關(guān)鍵詞：譜聚類；特征向量；譜聚類矩陣；本征間隙

DOIDOI：10.11907/rjdk.161953

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2016）008-0023-03

0 引言

聚類分析是數(shù)據(jù)挖掘的一個(gè)重要研究領(lǐng)域，在統(tǒng)計(jì)學(xué)、生物學(xué)、模式識(shí)別、機(jī)器學(xué)習(xí)和社會(huì)科學(xué)中有著極為廣泛的應(yīng)用。所謂聚類，就是將數(shù)據(jù)對(duì)象分成多個(gè)類或簇，使得同一簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。k-均值聚類是聚類分析中最經(jīng)典的算法，算法簡(jiǎn)單，可用于多種類型數(shù)據(jù)的聚類。但當(dāng)數(shù)據(jù)集為非凸時(shí)，k-均值聚類往往陷于局部最優(yōu)，聚類的效果欠佳。此外，對(duì)于大小或密度不均勻的簇，k-均值聚類通常無法處理。

譜聚類是一種新型的聚類分析方法，可以克服k-均值聚類等經(jīng)典方法的某些缺陷。譜聚類方法以圖論中的譜圖理論為基礎(chǔ)，將聚類問題轉(zhuǎn)化為圖最優(yōu)劃分問題。在眾多圖的最優(yōu)劃分準(zhǔn)則中，歸一化割集準(zhǔn)則的劃分效果相對(duì)較好，是譜聚類中常用的劃分準(zhǔn)則。對(duì)于給定的劃分準(zhǔn)則和聚類數(shù)目k，譜聚類通常采用多路譜聚類算法將數(shù)據(jù)集劃分為k個(gè)簇。

最早的譜聚類算法是Ng、Bach和Jordan提出的多路譜聚類方法。代表性的譜聚類算法還有Meila提出的多路歸一化割譜聚類方法；Vidal 提出的子空間譜聚類方法；Wang等提出的多流形譜聚類方法；Cheng等提出的低秩譜聚類方法；Elhamifar等提出的稀疏子空間譜聚類方法。

在眾多譜聚類算法中，多路譜聚類方法和多路歸一化割譜聚類方法因其劃分效果較好，算法復(fù)雜度也較低，被廣大學(xué)者普遍接受。但這兩種算法尚有一些問題有待研究，例如：如何選取包含聚類信息的特征向量？如何確定較合理的聚類數(shù)？

本文在多路譜聚類算法的基礎(chǔ)上，對(duì)特征向量組的選取問題進(jìn)行研究，提出一種特征向量自動(dòng)選取的譜聚類算法，并根據(jù)數(shù)值實(shí)驗(yàn)對(duì)該算法進(jìn)行性能測(cè)試。

1 譜聚類算法的基本概念與原理

譜聚類的基本思想是將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題，利用圖的最優(yōu)劃分準(zhǔn)則，使劃分出的子圖之間的邊權(quán)之和較小，而子圖內(nèi)的邊權(quán)之和較大。本文算法設(shè)計(jì)過程中涉及到的基本概念、性質(zhì)及原理如下：

1.1 譜聚類矩陣

設(shè)數(shù)據(jù)集為{p1，p2，…，pn}，將pi視為圖G（V，E）的一個(gè)頂點(diǎn)vi，i=1，2，…，n，對(duì)邊賦權(quán)Wij，Wij通常是根據(jù)頂點(diǎn)vi，vj間的距離經(jīng)過某種適當(dāng)?shù)淖儞Q而得，這樣就得到一個(gè)基于樣本點(diǎn)相似度的無向加權(quán)圖G（V，E，W），從而將數(shù)據(jù)集{p1，p2，…，pn}的聚類問題轉(zhuǎn)化為在圖G（V，E，W）上的最優(yōu)劃分問題。

圖劃分準(zhǔn)則的合理性決定著聚類結(jié)果的優(yōu)劣。由于圖劃分問題是一個(gè)NP難問題，所以首先要將圖劃分問題轉(zhuǎn)化為連續(xù)松弛形式，進(jìn)而再將其轉(zhuǎn)化為某些譜聚類矩陣的譜分解問題[2]。

常用的譜聚類矩陣如下：

1.3 高斯核參數(shù)

在譜聚類算法中，通常先要計(jì)算頂點(diǎn)間的距離矩陣，然后再用高斯核函數(shù)法將距離矩陣轉(zhuǎn)換為相似矩陣，進(jìn)而得到各種譜聚類矩陣。根據(jù)所選高斯核參數(shù)的不同，高斯核函數(shù)可分為局部尺度高斯核函數(shù)和全局尺度高斯核函數(shù)兩類。通常采用全局尺度高斯核函數(shù)將距離矩陣轉(zhuǎn)化為相似矩陣，具體方法為：

在將距離矩陣轉(zhuǎn)換為相似矩陣的過程中，高斯核參數(shù)σ起著極為重要的作用。不同的高斯核參數(shù)可能導(dǎo)致不同的劃分結(jié)果。本文算法中采用Zhang等[11]提出的高斯核函數(shù)法。

2 基于特征向量自動(dòng)選取的譜聚類算法

2.1 算法理論基礎(chǔ)

下面給出幾個(gè)理論結(jié)果，它們是本文算法的理論基礎(chǔ)。

引理1：非對(duì)稱規(guī)范Laplace矩陣Lrw的性質(zhì)[2]。

（1）λ，x分別是Lrw的特征值和特征向量的充要條件是λ，x是廣義特征值問題Lx=λDx的解。

（2）Lrw具有n個(gè)非負(fù)、實(shí)的特征值：0=λ1≤λ2≤…≤λn。

引理2：連通子圖的數(shù)目與Lrw的譜之間的關(guān)系[2]。

Lrw的特征值0的重?cái)?shù)等于圖GV，E，W的連通子圖V1∪V2∪…∪Vk的數(shù)目；特征值0的特征空間由這些子圖的指示向量組成。

2.2 算法原理

引理1 確保了Lrw的特征值的實(shí)值性和非負(fù)性。引理2表明，Lrw的理想情形包含不同類間完全分離的情形，即Lrw的理想情形一般優(yōu)于相似矩陣和Laplace矩陣的理想情形。另外，Lrw的包含聚類信息的特征向量構(gòu)成的矩陣具有分段常值性，即它反映的聚類信息比較明顯。綜上，本文算法中選用Lrw作為譜聚類矩陣。

在經(jīng)典的譜聚類算法中，往往選定譜聚類矩陣的前k個(gè)特征向量，得到特征向量空間，再用k-均值聚類等傳統(tǒng)聚類算法對(duì)特征向量空間的特征向量進(jìn)行聚類，從而得出聚類結(jié)果。這種作法的局限性在于，當(dāng)k較大時(shí)，選取的k個(gè)特征向量不一定包含聚類信息，從而導(dǎo)致聚類結(jié)果出現(xiàn)偏差。特別是當(dāng)聚類數(shù)k有誤差時(shí)，聚類結(jié)果會(huì)較混亂[6]。

為了解決上述問題，本文提出兩個(gè)應(yīng)對(duì)策略。首先，為避免遺漏包含聚類信息的特征向量，選取較多的Lrw的特征向量進(jìn)行分析、判斷。當(dāng)n較大時(shí)，究竟選取多少特征向量進(jìn)行分析比較合理目前尚無定論。綜合考慮劃分效果和算法的復(fù)雜度，本文選取前l(fā)n（n）個(gè)特征向量進(jìn)行分析。其次，采用本征間隙法[12]判定選取的特征向量中是否包含聚類信息。

所謂本征間隙是指相鄰兩個(gè)特征值的差。本征間隙法的原理是，根據(jù)矩陣攝動(dòng)理論，本征間隙越大，選取的k個(gè)特征向量所構(gòu)成的子空間就越穩(wěn)定。

雖然本征間隙法理論上并不能保證找出全部包含聚類信息的特征向量，但由于此方法簡(jiǎn)單易行，而對(duì)特征向量分段常值性的檢驗(yàn)?zāi)茉谝欢ǔ潭壬蠌浹a(bǔ)此方法的缺陷。

2.3 算法步驟

根據(jù)上述分析，本文提出一種特征向量自動(dòng)選取的譜聚類方法，具體步驟如下：

3 數(shù)值實(shí)驗(yàn)

為了檢驗(yàn)新算法的聚類性能，本文選取了4組典型的子空間譜聚類仿真數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果如圖1～圖4所示。

圖1中的數(shù)據(jù)類數(shù)較多，但聚類難度并不大；圖2和圖3中的數(shù)據(jù)無法用傳統(tǒng)方法聚類，適合用譜聚類，其中圖3中的數(shù)據(jù)聚類有一定難度；圖4中的數(shù)據(jù)量大，且密度相差較大，經(jīng)典譜聚類算法的效果往往欠佳。上述聚類效果圖顯示，本文提出的特征向量自動(dòng)選擇譜聚類算法對(duì)各類子空間聚類問題具有極佳的聚類效果。

4 結(jié)語

本文根據(jù)非對(duì)稱規(guī)范Laplace矩陣特征向量組的分段常值性，增加了待分析特征向量的數(shù)量，并利用本征間隙方法判斷特征向量中是否包含聚類信息。數(shù)值實(shí)驗(yàn)表明，這種算法對(duì)典型的譜聚類問題可獲得質(zhì)量較高的聚類結(jié)果，在一定程度上解決了特征向量的自動(dòng)選取問題。

需指出的是，本文提出的算法較適用于獨(dú)立子空間情形，而對(duì)于不滿足獨(dú)立子空間的情形或者是復(fù)雜的多流形情形效果欠佳。另外，與經(jīng)典的譜聚類算法相比，本文算法具有較高的復(fù)雜度。

參考文獻(xiàn)：

[1]JAIN A，MURTY M，F(xiàn)LYNN P.Data clustering： a review[J].ACM Computing Surveys，1999，31（3）： 264-323.

[2]LUXBRUG U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17（4）： 395-416.

[3]VERMA D，MEILA M.A comparison of spectral clustering algorithm[R].Washington： University of Washington，2003.

[4]NG A，JORDAN M，WEISS Y.On spectral clustering： analysis and an algorithm[C].Advances in Neural Information Processing Systems.Cambridge： MIT Press，2001： 849-856.

[5]BACH F，JORDAN M.Learning spectral clustering[C].Advances in Neural Information Processing Systems.Cambridge： MIT Press，2004： 1-13.

[6]MEILA M，XU L.Multiway cuts and spectral clustering[R].Washington： University of Washington，2003.

[7]VIDAL R.Subspace clustering[J].IEEE Signal Processing Magazine，2011，28（2）：52-68.

[8]WANG Y，JIANG Y，WU Y，et al.Spectral clustering on multiple manifolds[J].IEEE Transactions on Neural Networks，2011，22（7）：1149-1161.

[9]CHENG B，LIU G，WANG J，et al.Multi-task low rank affinity pursuit for image segmentation[J].ICCV，2011（15）：36-39.

[10]ELHAMIFAR E，VIDAL R.Sparse subspace clustering：algorithm，theory，and applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）：2765-2781.

[11]ZHANG X，LI J，YU H.Local density adaptive similarity measurement for spectral clustering[J].Pattern Recognition Letters，2011（16）： 352-358.

[12]孔萬增，孫志海，楊燦，等.基于本征間隙和正交特征向量的自動(dòng)譜聚類[J].電子學(xué)報(bào)，2010，38（8）： 1880-1885.

（責(zé)任編輯：陳福時(shí)）