何家玉+許峰

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

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

DOIDOI：10.11907/rjdk.161953

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

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

0 引言

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

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

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

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

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

1 譜聚類(lèi)算法的基本概念與原理

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

1.1 譜聚類(lèi)矩陣

設(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)過(guò)某種適當(dāng)?shù)淖儞Q而得，這樣就得到一個(gè)基于樣本點(diǎn)相似度的無(wú)向加權(quán)圖G（V，E，W），從而將數(shù)據(jù)集{p1，p2，…，pn}的聚類(lèi)問(wèn)題轉(zhuǎn)化為在圖G（V，E，W）上的最優(yōu)劃分問(wèn)題。

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

常用的譜聚類(lèi)矩陣如下：

1.3 高斯核參數(shù)

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

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

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

2.1 算法理論基礎(chǔ)

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

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

（1）λ，x分別是Lrw的特征值和特征向量的充要條件是λ，x是廣義特征值問(wèn)題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的理想情形包含不同類(lèi)間完全分離的情形，即Lrw的理想情形一般優(yōu)于相似矩陣和Laplace矩陣的理想情形。另外，Lrw的包含聚類(lèi)信息的特征向量構(gòu)成的矩陣具有分段常值性，即它反映的聚類(lèi)信息比較明顯。綜上，本文算法中選用Lrw作為譜聚類(lèi)矩陣。

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

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

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

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

2.3 算法步驟

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

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

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

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

4 結(jié)語(yǔ)

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

需指出的是，本文提出的算法較適用于獨(dú)立子空間情形，而對(duì)于不滿(mǎn)足獨(dú)立子空間的情形或者是復(fù)雜的多流形情形效果欠佳。另外，與經(jīng)典的譜聚類(lèi)算法相比，本文算法具有較高的復(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]孔萬(wàn)增，孫志海，楊燦，等.基于本征間隙和正交特征向量的自動(dòng)譜聚類(lèi)[J].電子學(xué)報(bào)，2010，38（8）： 1880-1885.

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