陶 洋，鮑靈浪，胡 昊

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

0 概述

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

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

1 相關(guān)工作

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

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

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

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

在此基礎(chǔ)上，本文將獲得的相似度矩陣W應(yīng)用于譜聚類方法（如文獻(xiàn)［16］方法）中，得到最終的聚類結(jié)果。

2 引入結(jié)構(gòu)和對(duì)稱約束的LRR 子空間聚類

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

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

為使所獲得的Z對(duì)噪聲更具魯棒性并且避免NP 問(wèn)題，構(gòu)建結(jié)構(gòu)約束的對(duì)稱低秩表示（SCSLR）模型，如式（5）所示：

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

2.1 模型優(yōu)化

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

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

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

算法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 結(jié)構(gòu)約束對(duì)稱低秩圖的構(gòu)造

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

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

SCSLR 算法描述如下：

算法2SCSLR

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

輸出聚類結(jié)果。

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

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

3）將W輸入到標(biāo)準(zhǔn)分割算法NCuts 中，獲得聚類結(jié)果。

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

由于SCSLR 算法的聚類性能受到β、λ、α參數(shù)的影響，并且聚類結(jié)果在參數(shù)λ和α的更改過(guò)程中受到很大影響，因此筆者根據(jù)經(jīng)驗(yàn)固定參數(shù)β=0.03，而僅改變?chǔ)撕挺痢D3 顯示了SCSLR 的平均聚類誤差隨參數(shù)λ和α不同組合的變化。通常，較小的α?xí)?dǎo)致較差的聚類性能，但較大的α必須配合縮小λ的范圍才能獲得較好的性能。由圖3（a）～圖3（c）可以看出，當(dāng)λ∈｛0.50，0.75，…，2.50｝且α=1 時(shí)，聚類誤差高達(dá)50%。由圖3（d）可以看出：當(dāng)λ范圍在1.00～1.75 之間且α=1 時(shí)，聚類誤差在10.16%～17.34%之間變化；當(dāng)λ范圍在1.00～1.75 之間且α=2 時(shí)，聚類誤差在1.25%～2.81%之間變化；當(dāng)λ范圍在1.00～1.75 之間且α=3 時(shí)，聚類誤差在1.72%～11.56%之間變化?？傮w而言，SCSLR 必須縮小λ的范圍至1.00～1.50 才能獲得更好的結(jié)果。由圖3（e）可以看出，在通過(guò)PCA 獲得的50 維數(shù)據(jù)上，SCSLR 表現(xiàn)良好?？傮w而言，當(dāng)λ和α的組合恰當(dāng)時(shí)，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ù)集上不同算法的平均聚類誤差對(duì)比如表1所示，其中加粗?jǐn)?shù)據(jù)為最優(yōu)數(shù)據(jù)?？梢钥闯?，SCSLR 在原始數(shù)據(jù)和通過(guò)PCA 獲得的500 維、300維、100維數(shù)據(jù)上較其他算法表現(xiàn)出更優(yōu)秀的聚類性能。例如，r=100時(shí)SCSLR 的平均聚類誤差非常低，僅為1.25%，與LRR、LRSC、LRR-PSD、LSA 和SSC 相比聚類精度提高了至少20%。雖然LRRSC在總體上取得了良好的結(jié)果，但SCSLR的聚類精度仍比LRRSC提高了2.3%～3.1%。上述結(jié)果表明，在具有非預(yù)期噪聲的數(shù)據(jù)上，SCSLR算法所獲得的表示矩陣可以顯著提高聚類精度。

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

3.2 運(yùn)動(dòng)分割數(shù)據(jù)集上的聚類效果

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

對(duì)于每個(gè)運(yùn)動(dòng)對(duì)象，使用跟蹤器自動(dòng)提取運(yùn)動(dòng)軌跡。為評(píng)估SCSLR 在運(yùn)動(dòng)分割中的性能，本文設(shè)計(jì)了以下兩種實(shí)驗(yàn)方案：實(shí)驗(yàn)方案1 使用原始軌跡的特征軌跡，實(shí)驗(yàn)方案2 使用PCA 將原始數(shù)據(jù)投影到4n維子空間（n是子空間的數(shù)量）上。特別地，將系數(shù)的總和設(shè)置為1，因?yàn)樗鼈兌荚诜律渥涌臻g中實(shí)現(xiàn)。

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

所有算法在Hopkins 155 數(shù)據(jù)集上的平均聚類誤差和時(shí)間對(duì)比如表2 和表3 所示，其中加粗?jǐn)?shù)據(jù)為最優(yōu)數(shù)據(jù)?？梢钥闯?，SCSLR 的平均聚類誤差明顯低于其他算法，分別為1.37%和1.43%，與LRRSC 相比分別提高了0.13%和0.13%，證實(shí)了結(jié)構(gòu)約束的對(duì)稱低秩表示在揭示子空間自然結(jié)構(gòu)方面具有優(yōu)勢(shì)。同時(shí)由于LRR會(huì)對(duì)系數(shù)矩陣進(jìn)行處理，因此其性能優(yōu)于SSC，這也證實(shí)了使用低秩表示的結(jié)構(gòu)來(lái)構(gòu)造相似度矩陣是有必要的。此外，在兩個(gè)實(shí)驗(yàn)中，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ù)集上不同算法的聚類性能（實(shí)驗(yàn)方案1）Table 2 Clustering performance of different algorithms on Hopkins 155 dataset（experimental scheme 1）

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

4 結(jié)束語(yǔ)

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