陶 洋，鮑靈浪，胡 昊

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

0 概述

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

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

1 相關工作

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

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

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

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

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

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

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

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

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

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

2.1 模型優(yōu)化

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

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

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

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

輸入數(shù)據(jù)矩陣X，參數(shù)λ＞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部分和整體節(jié)點V的權重之和。求解出Ncut 的最小值即能得到較好的分割結果。

SCSLR 算法描述如下：

算法2SCSLR

輸入數(shù)據(jù)矩陣X，參數(shù)λ＞0

輸出聚類結果。

1）根據(jù)算法1 獲得表示矩陣Z?。

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

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

3 實驗結果與分析

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

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

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

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

3.1 人臉數(shù)據(jù)集上的聚類效果

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

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

由于SCSLR 算法的聚類性能受到β、λ、α參數(shù)的影響，并且聚類結果在參數(shù)λ和α的更改過程中受到很大影響，因此筆者根據(jù)經(jīng)驗固定參數(shù)β=0.03，而僅改變λ和α。圖3 顯示了SCSLR 的平均聚類誤差隨參數(shù)λ和α不同組合的變化。通常，較小的α會導致較差的聚類性能，但較大的α必須配合縮小λ的范圍才能獲得較好的性能。由圖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%之間變化?？傮w而言，SCSLR 必須縮小λ的范圍至1.00～1.50 才能獲得更好的結果。由圖3（e）可以看出，在通過PCA 獲得的50 維數(shù)據(jù)上，SCSLR 表現(xiàn)良好?？傮w而言，當λ和α的組合恰當時，SCSLR 具有穩(wěn)定且理想的聚類性能。

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

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

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

3.2 運動分割數(shù)據(jù)集上的聚類效果

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

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

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

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

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

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

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

4 結束語

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