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

高 冉，陳花竹

（中原工學院理學院，鄭州 451191）

（?通信作者聯系郵箱nygr@163.com）

0 引言

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

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

本文在SSpeC 模型的稀疏性基礎上，給出一個新的數據自適應稀疏正則項，并采用SSSC 的統一優化框架，以保持相似度矩陣學習和聚類指標推斷的相互引導。一方面，利用數據對的相關性來指導隱相似度矩陣的稀疏性，克服了SSpeC中稀疏性懲罰的盲目性；另一方面，它傾向于強制來自不同子空間的數據具有不同的聚類指標，從而補充了SSSC 只強制來自相同子空間的數據具有相同的聚類指標的缺陷。

1 相關工作

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

表1 符號說明Tab.1 Symbol description

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

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

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

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

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

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

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

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

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

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

SSSC 模型雖然將相似度矩陣和聚類指標矩陣結合成一個統一的框架，是統一優化模型，優于兩階段聚類方法，但是它沒有考慮來自不同子空間的數據具有不同的聚類指標，本文旨在針對聚類指標矩陣的學習對SSSC方法進行改進。

2 本文提出的模型

2.1 本文模型

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

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

2.2 模型求解

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

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

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

2.2.1 求聚類指標矩陣F

當Z和E固定時，式（8）轉化為下式：

又因為

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

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

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

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

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

其中：F為最大的K（K為類別個數）個特征值對應的特征向量組成的矩陣。

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

式（14）的解為：

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

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

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

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

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

3 實驗結果

本章分別在Extended Yale B 數據庫［25］、Hopkins 155 數據庫［26］及USPS 數據庫［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。為了在所有實驗中進行公平的比較，使用作者源代碼中默認或建議參數設置的實驗結果，或者直接從其原始論文中引用最佳實驗結果，從而獲得所有比較模型的最佳性能。

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

3.1 Extended Yale B 數據庫實驗

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

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

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

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

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

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

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

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

當K=2，3，5，8，10 時，與次優的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 相比，隨著類別的個數的增加，本文模型的平均誤差率增大較為緩慢，說明該模型更適合大數據。本模型優于另兩種的兩個原因：一方面使用數據間的距離來指導隱相似度矩陣的稀疏性，克服了SSpeC 稀疏懲罰的盲目性；另一方面，它建立了相似度矩陣和聚類指標矩陣之間的關系，是統一的優化模型。

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

圖3 三種模型在Extended Yale B人臉數據庫上所得到的相似度矩陣、隱相似度矩陣和聚類指標矩陣的可視化（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數據庫實驗

Hopkins 155 數據庫是一個運動分割數據庫，包括155 個視頻序列，每個視頻中有2個或3個類，對應于2個或3個低維子空間。圖4 是來自Hopkins 155 數據庫的樣本圖像。使用來約束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數據庫的樣本圖像Fig.4 Sample images of Hopkins 155 data base

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

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

3.3 USPS數據庫實驗

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

圖6 USPS數據集的樣本圖像Fig.6 Sample images of USPS data base

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

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

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

4 結語

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