何家玉+許峰

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

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

DOIDOI：10.11907/rjdk.161953

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2016）008-0023-03

0 引言

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

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

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

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

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

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

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

1.1 譜聚類矩陣

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

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

常用的譜聚類矩陣如下：

1.3 高斯核參數(shù)

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

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

2 基于特征向量自動選取的譜聚類算法

2.1 算法理論基礎(chǔ)

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

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

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

（2）Lrw具有n個非負、實的特征值：0=λ1≤λ2≤…≤λn。

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

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

2.2 算法原理

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

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

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

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

雖然本征間隙法理論上并不能保證找出全部包含聚類信息的特征向量，但由于此方法簡單易行，而對特征向量分段常值性的檢驗能在一定程度上彌補此方法的缺陷。

2.3 算法步驟

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

3 數(shù)值實驗

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

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

4 結(jié)語

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

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

參考文獻：

[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]孔萬增，孫志海，楊燦，等.基于本征間隙和正交特征向量的自動譜聚類[J].電子學報，2010，38（8）： 1880-1885.

（責任編輯：陳福時）