結構約束的對稱低秩表示子空間聚類算法

陶 洋，鮑靈浪，胡 昊

（重慶郵電大學通信與信息工程學院，重慶 400065）

0 概述

在現實世界中，高維數據的局部結構和全局結構都較為復雜，且此類數據通常位于多個低維子空間的并集中。基于這一事實，許多對應子空間的聚類算法相繼被提出，用于解決高維數據的聚類問題。子空間聚類方法將數據分割至對應的子空間，用以揭示高維數據的潛在子空間結構，目前已被廣泛應用于顯著性檢測［1］、運動分割［2］、人臉聚類［3-4］和圖像分割［5］等領域。將基于表示的方法與譜聚類算法［6-8］相結合是其中一種具有代表性的方法，其先從給定的樣本數據中學習數據之間的相似度矩陣，再將相似度矩陣應用于譜聚類中以獲得最終的聚類結果。此類方法成功的關鍵是構造一個“好”的相似度矩陣。文獻［9］提出稀疏子空間聚類（Sparse Subspace Clustering，SSC）方法，通過l1范數最小化技術找到每個數據向量的稀疏表示矩陣，但其解缺乏全局約束。文獻［10］提出一種低秩表示（Low-Rank Representation，LRR）聚類方法，利用矩陣的核范數來查找所有數據的最低秩表示，從而捕獲數據的全局結構。文獻［11］提出一種對稱約束的低秩表示聚類（LRRSC）方法，將對稱約束應用于低秩表示中以提高原始低秩表示算法的聚類精度。文獻［12］通過將高斯場與調和函數合并到LRR 框架中，提出一種非負低秩表示聚類方法，在一個優化步驟中同時完成了相似度矩陣構建和子空間聚類。文獻［13］提出一種局部與結構正則化的低秩表示（LSLRR）聚類方法，該方法同時考慮數據的局部幾何結構和全局塊對角線結構，彌補了經典LRR 聚類方法的不足。

通過SSC 獲得的表示系數矩陣雖然具有很強的子集選擇能力，可以消除不同類型的樣本，但是矩陣過于稀疏，缺乏對相似樣本的聚集能力，從而無法有效地聚類高度相關的樣本數據。同理，雖然基于LRR 的方法可以聚合高度相關的數據，但是生成的表示系數矩陣非常密集，缺乏區分不同類型樣本的能力且無法引入數據的標簽信息。針對上述問題，本文提出一種結構約束的對稱低秩表示（Structure-Constrained Symmetric LRR，SCSLR）算法用于子空間聚類。通過引入結構約束和對稱約束平衡低秩表示系數矩陣的類間稀疏性和類內聚集性，從而更準確地揭示數據的子空間結構。

1 相關工作

基于譜聚類的子空間聚類方法首先找到一個表示矩陣Z∈?n×n，以表示其他樣本對選定樣本進行重建的貢獻度（見式（1）），然后通過對表示矩陣Z施加不同的約束項則，構造包含不同信息的相似度矩陣。

在此方面，LRR 是最具代表性的表示方法之一，計算公式為：

其中，Q是Z和E的懲罰函數，Ω是約束項。

文獻［14］通過在LRR 模型中定義Z≥0 實現PSD約束。文獻［11］通過定義Z=ZT保證每對數據點之間的權重具有一致性。文獻［15］通過定義Q(Z，E)=λ1‖Z‖1+λ2‖E‖2，1構造稀疏低秩表示矩陣。文獻［9］證明了低秩表示可以獲得塊對角解，當訓練樣本足夠時，其為子空間聚類的理想方法，但是當訓練樣本不足時，其效果非常差。本文對低秩表示的目標函數施加結構約束和對稱約束，以減小核函數對秩的懲罰，并獲得具有結構約束的對稱低秩圖。利用表示矩陣Z*構造相似度矩陣的計算模型，如式（3）所示：

在此基礎上，本文將獲得的相似度矩陣W應用于譜聚類方法（如文獻［16］方法）中，得到最終的聚類結果。

2 引入結構和對稱約束的LRR 子空間聚類

在子空間聚類研究中，對低秩表示解的結構施加約束能夠獲得較好的聚類結果。因此，本文提出結構約束的低秩表示子空間聚類方法，將結構約束和對稱約束引入低秩表示的解，以構造一個加權稀疏和對稱低秩的親和度圖。其中，低秩約束用于捕獲數據的全局結構，結構約束用于捕獲數據的局部線性結構，并且對稱約束可以確保每對數據點之間的權重具有一致性。事實上，結構約束即加權稀疏表示，其能揭示同類樣本之間的強親和力與不同類樣本之間的強分離性，即類內強親和性與類間強分離性。

為從數據的結構中獲得表示模型，可對LRR 模型解的結構施加約束項。本文通過在目標函數中添加|約束和zij=zji約束來限制解的結構（見式（4）），與僅考慮核范數的目標函數相比，這樣不僅可以提高解的秩，而且還可以保留數據點間的內在幾何結構，獲得更優的子空間聚類效果。

為使所獲得的Z對噪聲更具魯棒性并且避免NP 問題，構建結構約束的對稱低秩表示（SCSLR）模型，如式（5）所示：

實際上，當數據帶有標簽時，可以將SCSLR 看作半監督的LRRSC［8］。而對于不帶標簽的數據，可以利用數據的結構來構造權重R，即權重由角度確定。這意味著來自同一類的數據點之間的角度越小則樣本權重就越小，反之則越大。通過數據標準化處理，計算出數據點之間內積的絕對值后，理想的權重矩陣R構造如下：

2.1 模型優化

本文使用交替極小化方法求解式（5）中的目標函數。引入輔助變量J和L，將式（5）所示模型轉換為：

在式（7）所示模型中，增強拉格朗日函數表示為：

利用算法1 對式（8）所示函數進行推導，獲得所有子問題的解，并且數據矩陣X本身可以直接用作字典［4］以捕獲數據集X的基礎行空間。本文使用奇異值閾值運算［11，17］分步解決變量J和L的優化問題。

算法1式（8）所示模型的交替極小化方法求解

輸入數據矩陣X，參數λ＞0

輸出表示矩陣Z?

初始化Z=J=L=0，E=0，Y1=Y2=Y3=0，μmax=1010，ρ=1.1，ε=10-6

1）固定其他變量，更新J：

2.2 結構約束對稱低秩圖的構造

在此基礎上，應用NCuts 算法將樣本分割為相應的子空間。假設將圖G=(V，E，W)分為A和B兩部分，且這兩部分滿足條件A∪B=V和A∩B=?，則分割公式如下：

式（10）代表A和B兩部分的類間相似度，其值越小越好，式（11）則代表A部分和整體節點V的權重之和。求解出Ncut 的最小值即能得到較好的分割結果。

SCSLR 算法描述如下：

算法2SCSLR

輸入數據矩陣X，參數λ＞0

輸出聚類結果。

1）根據算法1 獲得表示矩陣Z?。

2）根據式（9）求出相似度矩陣W。

3）將W輸入到標準分割算法NCuts 中，獲得聚類結果。

3 實驗結果與分析

在Extended Yale B人臉數據集［18］和Hopkins 155運動分割數據集［19］上進行實驗，以證明本文算法的收斂性。圖1 顯示了目標函數值和迭代次數的關系。可以看出，在前幾次迭代中，目標函數值急劇減小，然后趨于平穩，說明SCSLR 能夠在幾個迭代步驟后收斂到局部最優解。

圖1 SCSLR 目標函數值與迭代次數的關系Fig.1 Relationship between objective function value of SCSLR and number of iterations

同樣使用上述兩個基準數據集，通過與低秩表示（LRR）［10］、稀疏子空間聚類（SSC）［9］、半正定低秩表示（LRR-PSD）［14］、局部子空間相似（LSA）［20］、低秩子空間聚類（LRSC）［21］和對稱約束的低秩表示（LRRSC）［11］這六種有效的子空間聚類算法進行實驗比較，評估SCSLR 的聚類效率和魯棒性。對比算法的源代碼從相應作者的主頁獲得。選取計算子空間聚類誤差來評估算法性能，如式（12）所示：

其中，Nerrror表示錯誤分類的數據點的數量，Ntotal表示總數據點的數量。在實驗過程中，LRR、LSA、SSC、LRSC、LRRSC 和LRR-PSD 的參數設置由其作者提供或手動調整。SCSLR 中包含β、λ、α三個參數。參數λ和β用于在低秩表示、加權稀疏表示和誤差之間進行平衡，如果β較大，則意味著模型強調加權稀疏性而不是低秩性，反之亦然。當數據“干凈”時，λ應相對較大，反之亦然。參數α的范圍為1～4，用于提高低秩表示的分離能力。

3.1 人臉數據集上的聚類效果

在Extended Yale B 人臉數據集上進行聚類效果對比。該數據集包含38 個對象，每個對象由在不同光照下拍攝的64 張圖像組成，分辨率為192 像素×168 像素，共2 414 幅圖像，本實驗將圖像分辨率調整為48 像素×42 像素。圖2 為Extended Yale B 數據集的前10 個對象的示例圖像。人臉聚類即是根據每個樣本的特征從多個樣本中對每組具有固定姿勢和變化照度的人臉圖像進行聚類操作。由于人臉圖像位于9 維子空間的并集，因此可以通過子空間聚類來解決上述問題。本文使用Extended Yale B 數據集前10 個對象的640 張正面人臉圖像。為進行公平比較，直接使用48 像素×42 像素的圖像而不進行預處理，通過PCA將這些圖像分別投影到500 維、300 維、100 維、50 維的特征空間。

圖2 Extended Yale B 數據集前10 個對象的示例圖像Fig.2 Example images of top10 objects on Extended Yale B dataset

由于SCSLR 算法的聚類性能受到β、λ、α參數的影響，并且聚類結果在參數λ和α的更改過程中受到很大影響，因此筆者根據經驗固定參數β=0.03，而僅改變λ和α。圖3 顯示了SCSLR 的平均聚類誤差隨參數λ和α不同組合的變化。通常，較小的α會導致較差的聚類性能，但較大的α必須配合縮小λ的范圍才能獲得較好的性能。由圖3（a）～圖3（c）可以看出，當λ∈｛0.50，0.75，…，2.50｝且α=1 時，聚類誤差高達50%。由圖3（d）可以看出：當λ范圍在1.00～1.75 之間且α=1 時，聚類誤差在10.16%～17.34%之間變化；當λ范圍在1.00～1.75 之間且α=2 時，聚類誤差在1.25%～2.81%之間變化；當λ范圍在1.00～1.75 之間且α=3 時，聚類誤差在1.72%～11.56%之間變化。總體而言，SCSLR 必須縮小λ的范圍至1.00～1.50 才能獲得更好的結果。由圖3（e）可以看出，在通過PCA 獲得的50 維數據上，SCSLR 表現良好。總體而言，當λ和α的組合恰當時，SCSLR 具有穩定且理想的聚類性能。

圖3 Extended Yale B 數據集上SCSLR 的平均聚類誤差隨參數λ 和α 的變化Fig.3 Change of average clustering error of SCSLR varies with parameter λ and α on Extended Yale B dataset

Extended Yale B 數據集上不同算法的平均聚類誤差對比如表1所示，其中加粗數據為最優數據。可以看出，SCSLR 在原始數據和通過PCA 獲得的500 維、300維、100維數據上較其他算法表現出更優秀的聚類性能。例如，r=100時SCSLR 的平均聚類誤差非常低，僅為1.25%，與LRR、LRSC、LRR-PSD、LSA 和SSC 相比聚類精度提高了至少20%。雖然LRRSC在總體上取得了良好的結果，但SCSLR的聚類精度仍比LRRSC提高了2.3%～3.1%。上述結果表明，在具有非預期噪聲的數據上，SCSLR算法所獲得的表示矩陣可以顯著提高聚類精度。

表1 Extended Yale B 數據集上不同算法的平均聚類誤差Table 1 Average clustering error of different algorithms on Extended Yale B dataset %

3.2 運動分割數據集上的聚類效果

Hopkins 155 運動分割數據集包含155 個單獨的序列，每個序列位于一個低維子空間中，并包含從兩個或三個運動中提取的39 個～550 個數據向量。運動分割是指將多個剛性運動對象的特征軌跡聚類到與每個運動對象相對應的子空間的問題。在仿射投影模型下，單個剛性運動對象的特征軌跡位于低維線性子空間中。因此，可以通過子空間聚類方法解決運動分割問題。

對于每個運動對象，使用跟蹤器自動提取運動軌跡。為評估SCSLR 在運動分割中的性能，本文設計了以下兩種實驗方案：實驗方案1 使用原始軌跡的特征軌跡，實驗方案2 使用PCA 將原始數據投影到4n維子空間（n是子空間的數量）上。特別地，將系數的總和設置為1，因為它們都在仿射子空間中實現。

β=0.03 情況下SCSLR 在Hopkins155 數據集上平均聚類誤差隨參數λ和α的變化如圖4所示。由圖4（a）和圖4（b）可以看出，SCSLR 的聚類誤差在不同參數設置下表現出相似的趨勢。當α=2 時，圖4（a）中SCSLR的聚類誤差在1.37%～2.53%之間變化，而圖4（b）中SCSLR 的最低聚類誤差僅為1.43%。

所有算法在Hopkins 155 數據集上的平均聚類誤差和時間對比如表2 和表3 所示，其中加粗數據為最優數據。可以看出，SCSLR 的平均聚類誤差明顯低于其他算法，分別為1.37%和1.43%，與LRRSC 相比分別提高了0.13%和0.13%，證實了結構約束的對稱低秩表示在揭示子空間自然結構方面具有優勢。同時由于LRR會對系數矩陣進行處理，因此其性能優于SSC，這也證實了使用低秩表示的結構來構造相似度矩陣是有必要的。此外，在兩個實驗中，LRSC、LRR-PSD 和LSA 均出現了較高的聚類誤差。

圖4 Hopkins 155 數據集上SCSLR 的平均聚類誤差隨參數λ 和α 的變化Fig.4 Change of average clustering error of SCSLR varies with parameter λ and α on Hopkins 155 dataset

表2 Hopkins 155數據集上不同算法的聚類性能（實驗方案1）Table 2 Clustering performance of different algorithms on Hopkins 155 dataset（experimental scheme 1）

表3 Hopkins 155數據集上不同算法的聚類性能（實驗方案2）Table 3 Clustering performance of different algorithms on Hopkins 155 dataset（experimental scheme 2）

4 結束語

針對子空間聚類問題，本文假設高維數據近似位于多個子空間的并集中，提出一種結構約束的對稱低秩表示算法SCSLR。將對稱約束和結構約束融合到高維數據表示的低秩屬性中，同時捕獲高維數據的全局對稱結構和子空間的加權局部線性結構，從而提高聚類性能。SCSLR 的實質是挖掘一個可以體現子空間自然結構的表示矩陣，通過進一步利用該矩陣主方向的角度信息得到用于譜聚類的相似度矩陣。在基準數據集上的實驗結果驗證了該算法優秀的聚類性能和魯棒性。后續將降低SCSLR 在處理大規模數據集時的計算復雜度，同時針對低秩表示算法尋找矩陣最優解時需要進行多次迭代的問題，尋找更有效率的求解算法。