改進的基于譜聚類的子空間聚類模型

高 冉，陳花竹

（中原工學(xué)院理學(xué)院，鄭州 451191）

（?通信作者聯(lián)系郵箱nygr@163.com）

0 引言

子空間聚類得到了廣泛的關(guān)注和大量的研究，它的任務(wù)是將數(shù)據(jù)分割到其本質(zhì)上所屬的子空間。子空間聚類是對傳統(tǒng)聚類方法的一種擴展，近20年來，人們提出了大量的子空間聚類方法，這些方法大致可以分為四類：迭代方法［1-2］、代數(shù)方法［3-4］、統(tǒng)計方法［5-6］和基于譜聚類的方法［7］。迭代方法將數(shù)據(jù)點分配到不同的子空間，并應(yīng)用數(shù)據(jù)點擬合每個子空間。該方法通常需要預(yù)先設(shè)置每個子空間的維數(shù)，最終的結(jié)果取決于初始化。代數(shù)方法的一個典型代表是基于分解的方法，它通過閾值相似矩陣（由數(shù)據(jù)矩陣的分解構(gòu)造）的元素來搜索初始分割。這些方法在子空間獨立時具有嚴格的理論保證；然而，它們對數(shù)據(jù)噪聲或異常值沒有魯棒性。統(tǒng)計方法通常假設(shè)每個子空間內(nèi)的數(shù)據(jù)遵循某種分布，如高斯分布。在此基礎(chǔ)上，采用期望最大化（Expectation Maximization，EM）算法交替進行數(shù)據(jù)聚類和子空間估計。這些方法的主要缺點是依賴于估計精確的子空間模型?；谧V聚類的方法由于其易于實現(xiàn)、對初始化和數(shù)據(jù)損壞不敏感等優(yōu)點而越來越流行。這類方法通常將問題劃分為兩個獨立的階段：首先，通過自表示學(xué)習(xí)從數(shù)據(jù)中學(xué)習(xí)一個相似度矩陣，如稀疏子空間聚類（Sparse Subspace Clustering，SSC）［8-9］、低秩表示（Low-Rank Representation，LRR）［10-11］和一些基于SSC 或LRR 的擴展模型）如魯棒子空間聚類的最小二乘回歸（Least Square Regression，LSR）［12］、相關(guān)自適應(yīng)子空間聚類（Correlation Adaptive Subspace Segmentation，CASS）［13］、隱低秩表示（Latent Low-Rank Representation，LatLLR）［14］、隱光滑表示子空間聚類（Latent SMooth Representation clustering，LSMR）［15］、塊對角表示（Block Diagonal Representation，BDR）［16］等，它們主要研究如何從數(shù)據(jù)中學(xué)習(xí)一個好的相似度矩陣來提高聚類性能。其次，應(yīng)用Normalized cuts（N-cut）［17］或稀疏譜聚類（Sparse Spectral Clustering，SSpeC）［18］等譜聚類方法，利用相似度矩陣推斷數(shù)據(jù)的標簽，得到數(shù)據(jù)最終的聚類結(jié)果。這些兩階段法中，SSpeC 模型是對傳統(tǒng)譜聚類的改進，通過分析隱相似度矩陣的稀疏性引入稀疏正則項，以此來增強聚類判別能力；但該正則項對于隱相似度矩陣的稀疏性是模糊的，因為它沒有顯式地捕獲數(shù)據(jù)的自表示矩陣和聚類指標矩陣之間的自然關(guān)系，沒有考慮隱相似度矩陣中哪些元素為0。SSpeC 模型雖然優(yōu)于傳統(tǒng)的譜聚類方法，但也沒有充分利用相似度矩陣與數(shù)據(jù)標簽之間的關(guān)系，聚類性能并未達到最優(yōu)。

結(jié)構(gòu)稀疏子空間聚類（Structured Sparse Subspace Clustering，SSSC）［19-20］將兩階段合并，同時得到相似度矩陣和聚類結(jié)果。將相似度矩陣學(xué)習(xí)和標簽學(xué)習(xí)集成到一個統(tǒng)一的優(yōu)化框架中，并利用其中一個來引導(dǎo)另一個，使兩者都具有優(yōu)點：一方面，它利用標簽將來自不同類的數(shù)據(jù)點對應(yīng)的相似度強制為零；另一方面，它使用相似度矩陣來引導(dǎo)標簽推斷，使得同一類中的數(shù)據(jù)點具有相同的標簽。SSSC的聚類性能優(yōu)于上述兩階段法，但SSSC只強制來自相同子空間的數(shù)據(jù)具有相同的聚類標簽，沒有考慮來自不同子空間的數(shù)據(jù)具有不同的聚類標簽。結(jié)構(gòu)塊對角表示（Structured Block Diagonal Representation，SBDR）［21］和判別相關(guān)子空間聚類（Discriminative and Coherent Subspace Clustering，DCSC）［22］都是兩個階段的統(tǒng)一優(yōu)化模型，它們是對SSSC 方法的改進，但是它們主要集中在對自表示學(xué)習(xí)時的改進，使用相似度矩陣來引導(dǎo)標簽推斷時仍然應(yīng)用的是傳統(tǒng)的譜聚類算法（N-cut）。

本文在SSpeC 模型的稀疏性基礎(chǔ)上，給出一個新的數(shù)據(jù)自適應(yīng)稀疏正則項，并采用SSSC 的統(tǒng)一優(yōu)化框架，以保持相似度矩陣學(xué)習(xí)和聚類指標推斷的相互引導(dǎo)。一方面，利用數(shù)據(jù)對的相關(guān)性來指導(dǎo)隱相似度矩陣的稀疏性，克服了SSpeC中稀疏性懲罰的盲目性；另一方面，它傾向于強制來自不同子空間的數(shù)據(jù)具有不同的聚類指標，從而補充了SSSC 只強制來自相同子空間的數(shù)據(jù)具有相同的聚類指標的缺陷。

1 相關(guān)工作

為方便起見，在回顧相關(guān)理論之前，由表1 給出了本文中使用的符號的定義。

表1 符號說明Tab.1 Symbol description

令X=(x1，x2，…，xN)∈Rn×N是N個數(shù)據(jù)的集合，每一列xi都是一個n維特征向量。假設(shè)數(shù)據(jù)分別來自維數(shù)未知的的K個相互獨立的子空間的并集。子空間聚類的目的是通過聚類來揭示每個數(shù)據(jù)的子空間屬性，一類對應(yīng)一個子空間。基于譜聚類方法取得了很好的效果，它假設(shè)子空間中的任何數(shù)據(jù)都可以表示為其他數(shù)據(jù)的線性組合的前提下，利用自表示矩陣Z構(gòu)造相似度矩陣。這些方法通過求解以下優(yōu)化問題得到自表示矩陣Z：

其中：Ω(Z)和C 是對Z的約束；E表示誤差值、損壞值或異常值；Φ(E)是E的約束函數(shù)，一般來說用于高斯噪聲，‖E‖1用于異常值；λ是一個權(quán)衡參數(shù)。不同聚類方法之間的主要區(qū)別在于Ω(Z)的選擇，設(shè)計合適的Ω(Z)使得模型得到的矩陣Z滿足類間稀疏、類內(nèi)一致的性質(zhì)。例如，SSC 使用‖Z‖1來增強Z的稀疏性，LRR 使用核范數(shù)‖Z‖?來尋求對所有數(shù)據(jù)的低秩表示。得到問題（1）的最優(yōu)解Z*后，就構(gòu)造出相似度矩陣。然后，通過譜聚類算法得到聚類結(jié)果。具體地，通過優(yōu)化以下問題得到最終聚類結(jié)果：

其中：L=D-A是Laplace 矩陣；D是一個對角元素為Djj=的對角矩陣。約束Γ是聚類指標矩陣的集合，定義為：

其中F為聚類指標矩陣。具體地，定義為：

第i行的非零元所在的列表示數(shù)據(jù)xi的所在的類，F(xiàn)的第j列表示哪些數(shù)據(jù)屬于第j類。F1=1 表示每個數(shù)據(jù)點只在一個子空間中。約束rank(F)=K是為了確保F只有K行不同，因為子空間的類的個數(shù)是K。問題（2）通常由F∈Γ松弛為FTF=I，其中I是單位矩陣。所以譜聚類問題松弛為以下優(yōu)化問題：

問題（4）的最優(yōu)解F的列是L的K個最小特征值的對應(yīng)的特征向量。將K-均值（K-means）聚類算法作用于F的每一行，得到最終聚類結(jié)果。

FFT在某種程度上是稀疏的，SSpeC 模型通過‖F(xiàn)FT‖1來考慮稀疏性，所以SSpeC模型表示為：

SSpeC 表明FFT矩陣隱含了相似度矩陣A的可判別性或|FFT|可視為一個新的相似度矩陣，稱為隱相似度矩陣。但它是盲目的，因為它沒有考慮兩個數(shù)據(jù)點是否來自不同的子空間。只有數(shù)據(jù)點xi與xj來自不同的子空間，才有(FFT)ij=0。此外，SSpeC 是一個兩階段的方法，沒有充分利用相似度矩陣和數(shù)據(jù)標簽之間的關(guān)系。

SSSC 通過以下模型將子空間聚類問題表述為一個統(tǒng)一的框架：

α＞0和λ＞0權(quán)衡參數(shù)，SSSC中，自表示矩陣Z和聚類指標矩陣F彼此交互，使得它們有一些有利于聚類的特性。

SSSC 模型雖然將相似度矩陣和聚類指標矩陣結(jié)合成一個統(tǒng)一的框架，是統(tǒng)一優(yōu)化模型，優(yōu)于兩階段聚類方法，但是它沒有考慮來自不同子空間的數(shù)據(jù)具有不同的聚類指標，本文旨在針對聚類指標矩陣的學(xué)習(xí)對SSSC方法進行改進。

2 本文提出的模型

2.1 本文模型

根據(jù)前面對SSpeC模型的分析，當xi和xj不在同一個子空間時，隱相似度矩陣的元素|(FFT)ij為零。直觀地說，如果數(shù)據(jù)點xi和xj之間的距離很遠，那么很可能xi和xj|來自不同的子空間。在此基礎(chǔ)上，利用下面的加權(quán)稀疏性來懲罰隱相似度矩陣的稀疏性：

將式（7）代入SSSC 模型，且將F∈Γ松弛為FTF=I，可得：

2.2 模型求解

通過交替求解以下兩個子問題，設(shè)計了模型（8）的有效算法：

1）固定X和Z，求解F；

2）固定F，通過求解表示問題找到Z和E。

2.2.1 求聚類指標矩陣F

當Z和E固定時，式（8）轉(zhuǎn)化為下式：

又因為

所以式（9）可寫為下式：

為了式（10）的目標函數(shù)能變量分離，引入輔助變量J，然后將其改寫為如下等價公式：

該問題可以用交替方向乘子法（Alternating Direction Method of Multipliers，ADMM））［23-24］來解決。式（11）的增廣Lagrange函數(shù)為：

其中：Y是Lagrange乘子，μ＞0是懲罰算子。當別的變量固定時，依次更新F、J和Y。

1）F子問題：固定J和Y，通過下式更新F。

其中：F為最大的K（K為類別個數(shù)）個特征值對應(yīng)的特征向量組成的矩陣。

2）J子問題：固定F和Y，通過下式更新J。

式（14）的解為：

其中：S為軟閾值算子，||W是對矩陣的每個元素求絕對值。

3）Y子問題：乘子的更新是標準的梯度上升過程：

將問題（11）的整個求解方法總結(jié)在算法1中，其中k是迭代次數(shù)。

2.2.2 求自表示矩陣Z和誤差矩陣E

這是SSSC模型。具體求解參考文獻［11］。

3 實驗結(jié)果

本章分別在Extended Yale B 數(shù)據(jù)庫［25］、Hopkins 155 數(shù)據(jù)庫［26］及USPS 數(shù)據(jù)庫［27］進行實驗，以評估本文模型的聚類性能，并與當前較好的聚類模型進行聚類誤差率比較，如SSC［8-9］、LRR［10-11］、LSR（包含LSR1和LSR2兩個模型）［12］、CASS［13］、LatLRR［14］、LSMR［15］、BDR［16］、SSC+SSpeC（Sparse Subspace Clustering+Spare Spectral Clustering）［18］、N-cut［17］、BDSSC（Block Diagonal Sparse Subspace Clustering）［28］、SSSC［19-20］、LRSC［29-30］、BDLRR（Block Diagonal Low-rank Representation）［28］、TSC（Thresholding-based Subspace Clustering）［31］、NSN（Nearest Subspace Neighbor）［31］、正交匹配追蹤（Orthogonal Matching Pursuit，OMP）［32］和K-means。為了在所有實驗中進行公平的比較，使用作者源代碼中默認或建議參數(shù)設(shè)置的實驗結(jié)果，或者直接從其原始論文中引用最佳實驗結(jié)果，從而獲得所有比較模型的最佳性能。

采用上述參考文獻中使用的子空間聚類誤差率error=Nerror/Ntotal作為聚類性能度量，其中：Nerror表示錯誤聚類的數(shù)據(jù)點的個數(shù)，Ntotal表示數(shù)據(jù)點總數(shù)。

3.1 Extended Yale B 數(shù)據(jù)庫實驗

Extended Yale B 人臉數(shù)據(jù)庫包含38 個人的2 414 張人臉圖像，每一個人在不同可控光實驗室條件下大約有64 張人臉圖像，部分圖像如圖1所示。

圖1 Extended Yale B人臉數(shù)據(jù)庫的樣本圖像Fig.1 Sample images of Extended Yale B face data base

為了減少算法的計算時間和降低存儲空間，參考SSSC［19-20］，先將所有圖像的大小壓縮為48×42，然后向量化為2 016 維數(shù)據(jù)點。和SSSC 一樣，將38 類數(shù)據(jù)分為4 組，而不是對整個數(shù)據(jù)集進行聚類，以評估本文模型在平均意義上的聚類性能。具體而言，四組分別對應(yīng)1～10 類、11～20 類、21～30類、31～38 類。對于前三組中的每一組，考慮K={2，3，5，8，10}類的所有選擇；對于最后一組，考慮K={2，3，5，8}類的所有選擇。實驗中Φ(E)=‖E‖1。該實驗結(jié)果與SSC、LRR、LSR、CASS、LatLRR、LSMR、BDR、SSC+SSpeC、N-cut、BDSSC、SSSC、LRSC、BDLRR、TSC、NSN、OMP 和K-means進行比較。

實驗表明，當K=2 時，本文模型在參數(shù)α=0.1，β=0.001，λ=0.5 時通常會得到“最佳”平均聚類精度，另外在該數(shù)據(jù)集上所有實驗的參數(shù)都選擇這個設(shè)置。

為了展示本文模型的性能，從每個組中任選所有K類進行實驗，例如，當K=2 時，共有種情況。然后每類的所有情況的聚類錯誤率的均值（Ave.）、標準差（“±”符號后的數(shù)據(jù)）和中值（Med.）如表2 所示，其中“—”表示未報告數(shù)據(jù)，最好的結(jié)果用粗體表示。為了更加直觀，還繪制了不同模型的平均聚類錯誤率與類的個數(shù)的關(guān)系曲線如圖2所示。

表2 Extended Yale B人臉數(shù)據(jù)庫上的聚類錯誤率 單位：%Tab.2 Clustering error rate on Extended Yale B face data base unit：%

通過表2 和圖2 可以看到，在所有模型中，后兩種模型的聚類誤差率的平均值、中值明顯低于前幾種模型，說明同時得到相似度矩陣和聚類結(jié)果的統(tǒng)一模型優(yōu)于兩步法模型；本文模型的平均聚類誤差率最低，且對應(yīng)的標準差明顯較小，表明本文模型較其他方法更加穩(wěn)定。當K=2，3，5，8，10 時，平均聚類誤差率分別為0.18%、0.25%、0.309%、0.302% 和0.26%。由此可見，本文模型的平均聚類誤差率對類別個數(shù)的增加具有較強的魯棒性。

圖2 Extended Yale B數(shù)據(jù)庫上的聚類錯誤率與類的個數(shù)的關(guān)系Fig.2 Relationship between clustering error rate and the number of classes on Extended Yale B data dase

當K=2，3，5，8，10 時，與次優(yōu)的LSMR 相比，本文模型將聚類誤差率從0.53%、0.98%、1.44%、1.80%和1.67%降到0.18%、0.25%、0.309%、0.302%和0.26%；與SSC+SSpeC 相比，本文模型將聚類誤差率從1.92%、3.33%、4.49%、3.67%和2.71% 降到0.18%、0.25%、0.309%、0.302% 和0.26%。與SSSC 相比，隨著類別的個數(shù)的增加，本文模型的平均誤差率增大較為緩慢，說明該模型更適合大數(shù)據(jù)。本模型優(yōu)于另兩種的兩個原因：一方面使用數(shù)據(jù)間的距離來指導(dǎo)隱相似度矩陣的稀疏性，克服了SSpeC 稀疏懲罰的盲目性；另一方面，它建立了相似度矩陣和聚類指標矩陣之間的關(guān)系，是統(tǒng)一的優(yōu)化模型。

此外，為了更好地比較SSC+SSpeC、SSSC 以及本文模型，將這些模型應(yīng)用于Extended Yale B 人臉數(shù)據(jù)庫（K=5時），并將所得到的相似度矩陣A、隱相似度矩陣FFT和聚類指標矩陣F可視化?？梢暬Y(jié)果如圖3所示。理想情況下，來自不同聚類的數(shù)據(jù)點的相似度矩陣和隱相似度矩陣（對角塊之外的元素）應(yīng)為零，從而表現(xiàn)出區(qū)分性。與圖3（a）、（b）所示的SSC+SSpeC 和SSSC 的相似度矩陣相比，本文模型產(chǎn)生了一個更好的相似矩陣，其對角塊外的非零項非常少，如圖3（f）所示，本文模型所得隱相似性矩陣基本上是對角塊，具有更好的辨別性。

圖3 三種模型在Extended Yale B人臉數(shù)據(jù)庫上所得到的相似度矩陣、隱相似度矩陣和聚類指標矩陣的可視化（K=5）Fig.3 Visualization of affinity matrix，latent affinity matrix and clustering indicator matrix obtained by three models on Extended Yale B face data base（K=5）

3.2 Hopkins 155數(shù)據(jù)庫實驗

Hopkins 155 數(shù)據(jù)庫是一個運動分割數(shù)據(jù)庫，包括155 個視頻序列，每個視頻中有2個或3個類，對應(yīng)于2個或3個低維子空間。圖4 是來自Hopkins 155 數(shù)據(jù)庫的樣本圖像。使用來約束E。本實驗將本文模型與SSC、LRR、LSMR、N-cut、SSSC、K-means、SSC+SSpeC、LSR1、LSR2、BDLRR、BDSSC、LSA（Local Subspace Affinity）［33］和DCSC［22］作比較。

圖4 Hopkins 155數(shù)據(jù)庫的樣本圖像Fig.4 Sample images of Hopkins 155 data base

表3 Hopkins 155數(shù)據(jù)庫上的聚類錯誤率對比 單位：%Tab.3 Clustering error rates on Hopkins 155 data base unit：%

圖5 Hopkins 155數(shù)據(jù)庫上聚類錯誤率與類的個數(shù)的關(guān)系Fig.5 Relationship between clustering error rate and the number of classes on Hopkins 155 data base

3.3 USPS數(shù)據(jù)庫實驗

USPS 數(shù)據(jù)集是一個手寫數(shù)字數(shù)據(jù)集［27］，由10 類共9 298幅圖像組成，每個類的手寫數(shù)字為0～9。每幅圖像的像素為16×16，部分樣本如圖6所示。

圖6 USPS數(shù)據(jù)集的樣本圖像Fig.6 Sample images of USPS data base

本文實驗中使用標準的主分量分析（Principal Component Analysis，PCA）將256維數(shù)據(jù)降至40維，并且只使用每類圖像中的前100 幅圖像，。該實驗結(jié)果與SSC、LRR、LSMR、N-cut、SSSC、K-means、SSC+SSpeC、LSR、CASS 和光滑表示聚類（SMR）［34］進行比較。

實驗結(jié)果表明，當α=0.1，β=0.000 01，λ=2.5 時得到“好”的聚類結(jié)果。聚類誤差率如表4 所示，其中最好的結(jié)果用粗體表示。從表4 可以看出，與SSSC 相比，本文模型對USPS 數(shù)據(jù)集的聚類誤差率從8.20%降到7.70%，聚類效果良好。

表4 USPS數(shù)據(jù)庫上的聚類錯誤率 單位：%Tab.4 Clustering error rates on USPS database unit：%

4 結(jié)語

本文提出了一種新的子空間聚類模型，在SSSC 模型中加入了一個數(shù)據(jù)自適應(yīng)稀疏正則項。一方面，新的正則項利用數(shù)據(jù)對之間的距離來強化潛在相似度矩陣的聚類判別性質(zhì)，從而克服了SSpeC 中稀疏性懲罰的盲目性；另一方面，它建立了相似度矩陣和聚類指標矩陣之間的關(guān)系，克服了SSSC 只強制來自相同子空間的數(shù)據(jù)具有相同的聚類標簽的缺陷，且是統(tǒng)一的優(yōu)化模型。在三個常用數(shù)據(jù)集上的實驗表明，本文提出的方法優(yōu)于現(xiàn)有的兩階段方法和統(tǒng)一的SSSC優(yōu)化模型。