非負局部約束低秩子空間聚類算法

解 昊，趙志剛，呂慧顯，劉馨月，劉成士，董曉晨

1.青島大學 計算機科學技術學院，山東 青島 266000

2.青島大學 自動化與電氣工程學院，山東 青島 266000

1 引言

在過去幾十年中，子空間學習[1]和聚類問題在計算機視覺和機器學習領域成為重要的研究課題之一。通常高維的數據點是從多個低維子空間中抽取出來的，子空間聚類的基本任務是根據潛在的子空間對數據點進行聚類。根據聚類機制，目前已存在的子空間聚類方法可以分為代數方法[2-3]，迭代法[4]，統計方法[5-7]和譜聚類方法[8-11]。以上方法中，譜聚類是近年來最受歡迎的子空間聚類算法[12]。

譜聚類算法的關鍵步驟在于構建親和度圖。構建親和度圖的方案分為基于局部距離和基于全局線性表示兩種。基于局部距離的方法利用成對點之間的歐氏距離建立親和度圖，如拉普拉斯特征圖[13]，k近鄰[14]，若兩個數據點不相鄰，則將兩點之間的親和度置為0，否則置為1。基于局部距離的方案計算簡單，但是這種構建圖的方式對噪聲和異常值敏感。基于全局線性表示的方案假設每個數據點可以在一個過完備的字典（即X=DZ，其中D是過完備的字典）中被線性地表示。通過對表示矩陣Z應用不同范數正則化，可以得到不同親和度來構建圖，如線性平方回歸[8]，稀疏子空間聚類[9]，低秩表示[10]等。

與基于稀疏方法相比，基于低秩的方法旨在找到所有數據的最低秩表示，即rank(Z),s.t.X=XZ。此方法更適合追求數據空間的全局和內在信息。然而，低秩表示算法不能利用數據之間局部線性結構，這將導致構造的親和度矩陣通常是密集的，并且低秩表示中的負值在構建親和度矩陣上沒有任何意義。

為了兼顧數據的全局和局部結構，本文提出了非負局部約束低秩子空間算法，該算法在低秩表示的基礎上，將數據的局部稀疏結構作為約束集成到統一公式中。此外，原始數據作為字典不具有代表性，基于學習的字典對噪聲有良好的魯棒性。考慮到最終結果的準確性，在預處理數據時，采用Wei[20]基于矩陣分解的分析，對字典進行更新。

2 相關工作

2.1 子空間聚類問題

令 X=[x1,x2,…,xn]是來自于 k個線性子空間的m維數據向量的集合，其中子空間S的維度i為ri。子空間聚類的任務是將存在于同一個子空間中的數據向量分離出來。為了標記符號簡單，可以假設X=[X1,X2,…,Xk]，其中Xi由存在于子空間Si中的數據向量組成。同時，假設子空間Si相互獨立，di表示為Xi中的向量數。那么存在至少一個塊對角矩陣Z=diag{Z1,Z2,…,Zk}滿足等式：

其中第i個塊Zi的維度為di×di。式（1）具有無窮多的解。任何一個解都可稱為表示系數矩陣。值得注意的是，矩陣Z的塊對角結構直觀顯示了數據的分割（每個塊對應于一個簇。因此，聚類任務相當于找到塊對角線表示矩陣Z）。

2.2 低秩表示算法

低秩表示算法旨在探索多個子空間結構，從而找到一組數據向量的最低秩表示。

對于無噪聲的情況，低秩表示算法將數據本身作為字典，并尋找最低秩表示矩陣Z：

由于秩函數不是凸的難以求得最優值，式（2）最優化問題可以放寬到以下凸優化問題：

對于存在噪聲的情況，低秩表示算法通過向目標函數（3）添加列和范數項處理噪聲數據，使得噪聲稀疏：

雖然實驗結果表明[10]式（4）對于噪聲有強魯棒性，但是當噪聲影響嚴重，或者異常值所占百分比較大時。使用原始數據X本身作為字典將導致聚類效果明顯下降。Wei[20]對于字典提出了一種改進的低秩表示方法：

直觀地，該模型消除了大部分噪聲，并采用干凈數據作為字典，當數據本身嚴重損壞時，最終的聚類效果比低秩表示算法有明顯提升。

3 非負局部約束低秩子空間算法

3.1 非負局部約束低秩模型

在2.1節中，說明了對于塊對角矩陣Z如果字典是過于完備的（比如用數據本身作為字典）可以有無窮多個可行解，為了解決這個問題，對所求的表示矩陣Z加入稀疏與低秩約束：

式（6）中β＞0是正則項參數平衡稀疏性與低秩性，表示矩陣Z的每一列zi揭示了數據xi與字典A的線性關系。然而，求解式（6）是一個NP難問題，借由Liu[10]與Vidal[9]的處理將式（6）轉化如下：

同時，也要考慮到噪聲的影響，加入噪聲項E的同時，對字典進行更新：

該模型具體來說，每個數據點由其他數據點的線性組合得到，表示矩陣Z是非負且稀疏的[21]。非負值確保每個數據點位于其鄰點的凸包中，稀疏性確保所涉及的鄰點盡可能少。除了非負稀疏約束之外，表示矩陣Z強制為低秩，使相同子空間上的數據點聚類成同一個簇。

3.2 線性交替方向乘子法求解非負局部約束低秩模型

引理1令[U,S,V]=SVD(D)，則最優化問題，s.t.D=DZ的解是矩陣D的形狀相互作用矩陣，即Z*=VVT，目標方程最優值為：||Z*||*=rank(D)。

根據引理1可以將式（8）近似地轉化為如下兩式：

對于式（8），雖然在求解過程時固定其他變量求解單一變量可以確保函數為凸函數，但計算量仍非常巨大。因此在確定字典時，基于Wei[20]的分析結果，采用無噪聲時的低秩表示最優解等于數據形狀相互作用矩陣[20]方案。

式（9）用核范數近似替代秩函數（rank），利用增廣拉格朗日方法去除約束條件后，借由Lin[22]提出的非精準拉格朗日乘子算法（ALM）迭代求解最優化問題：

算法1求解式（9）

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

初始化參數：E0,Y0,u0＞0,umax＞u0,ρ＞1,ε＞0

1.更新D：

2.更新E：

3.更新乘子Y：

4.更新 u ：uk+1=min(ρuk,umax)

5.k←k+1

結束循環

輸出：新字典D

對于式（10），交替方向乘子法（ADM）在求解時需要引入兩個輔助變量，每個變量迭代都需要龐大的矩陣計算。因此，采用線性交替方向自適應法（LADMAP）[23]解決此最優化問題。

首先，引入輔助變量H使目標函數變量可分離：

式（12）的增廣拉格朗日方程為：

為后續計算簡便，式（13）化簡為：

線性交替方向自適應法（LADMAP）通過求解單一變量時，固定其他變量為最小值來交替更新變量Z、H和E，其中二次項在前一次迭代中被其一階導數近似代替，然后添加近似項Z-Zk完成變量更新[22]。通過一些代數運算，變量Z、H和E更新方案如下：

其中?為關于Z的偏微分操作，Θ、S、Ω分別是奇異值閾值操作、收縮閾值操作、l2-1最小值操作[10]，特別的，式中的

完整迭代算法流程見算法2。

算法2求解式（10）

當||X-DZk-Ek||F/||X||F≥ε1或者ε2時：

1.按照式（16）更新 Z

2.按照式（17）更新 H

3.按照式（18）更新 E

4.更新乘子Y1：

5.更新乘子Y2：

6.更新ρ：

輸入：數據矩陣X ，字典D，β＞0,λ＞0

初始化參數：

7.更新 u ：uk+1=min(ρuk,umax)

結束循環

輸出：系數矩陣Z*，噪聲矩陣E*

3.3 構建親和度矩陣

得到表示系數矩陣Z*之后，可以從中導出圖形鄰接結構和親和度矩陣。實際上，由于存在數據噪聲，數據點xi對應的表示系數向量密度較小，直觀表現為數值較小。由于構建親和度矩陣時只對數據的全局結構感興趣，所以可以對每個樣本的系數向量進行歸一化處理（即），并設定閾值將較小值置為0。經過閾值操作后會得到真正的稀疏表示系數矩陣，并將親和度矩陣W 定義為

3.4 非負局部約束低秩子空間算法

定義親和度矩陣W后，剩下工作為構建親和度圖，圖中的每個頂點對應著每個數據點xi，兩頂點xi,xj之間連線的權重對應著親和度矩陣W的元素wi,j，采用譜聚類算法如歸一化切割[24]對親和度圖進行劃分，劃分得到的每一部分為一個簇，即完成聚類操作。完整流程見算法3。

算法3非負局部約束低秩子空間算法

輸入：數據矩陣X,子空間數目k，閾值θ

步驟：

1.通過算法1得到干凈字典D

2.通過算法2得到表示系數矩陣Z*

3.對表示系數矩陣Z*數據歸一化：，并根據給定閾值θ篩選值：

4.對親和度矩陣W應用歸一化切割譜聚類算法，根據輸入的k值，分成k個聚類。

4 實驗

本章將評估非負局部約束低秩子空間算法（NLRSI）對合成數據和實際計算機視覺任務（運動分割和手寫數字聚類）的性能。為了直觀表達效果，將與基于譜聚類的最先進的子空間聚類算法，如稀疏子空間算法（SSC）[9]，低秩表示子空間算法（LRR）[10]，魯棒形狀相互作用矩陣算法（RSI）[20]和非負低秩稀疏表示算法（NNLRSR）[25]進行對比。選擇這些方法作為基準，是因為這些算法在上述任務中的表現效果很好。為了進行公平比較，根據Tron[26]定義的子空間聚類誤差作為性能的度量：子空間聚類誤差=錯誤分類數據點/總數據點。

對于比較的算法，采用引用文獻中的參數作為輸入參數，其中對于Hopkins155運動分割數據庫[27]，稀疏子空間算法λ=20；低秩表示子空間算法λ=4；魯棒形狀相互作用矩陣算法λ=10；低秩稀疏表示算法λ1=100,λ2=10；非負局部約束低秩子空間算法β=5,λ=4.2。對于USPS手寫數字數據庫，稀疏子空間算法λ=0.05；低秩表示子空間算法λ=0.18；魯棒形狀相互作用矩陣算法 λ=0.01；低秩稀疏表示算法 λ1=0.01,λ2=10；非負局部約束低秩子空間算法的參數為β=0.17,λ=5。

4.1 合成數據

圖1 各個算法對噪聲污染魯棒性

當 p=0與 p=0.3時，圖2與圖3顯示了親和度矩陣W 或者表示系數矩陣Z*（對于SSC，LRR，RSI算法）的塊對角結構。

圖2 p=0時得到的親和度矩陣或者系數矩陣塊對角結構

圖3 p=0.3時得到的親和度矩陣或者表示系數矩陣塊對角結構

通過圖2與圖3的對比可以看出，非負低秩稀疏表示算法（NNLRSR）與非負局部約束低秩算法（NLRSI）對噪聲的魯棒性能較好，這表明通過局部約束強制更改矩陣結構可以消除大量無關噪聲，使得聚類效果提升，這也在圖1的準確率變化趨勢圖中有所體現。

4.2 運動分割

運動分割是指從視頻序列中提取一組二維點軌跡，將軌跡對應于不同的剛體運動。這里，數據矩陣X的尺寸為2F×N，其中N是二維軌跡的數量，F是視頻中的幀數。在仿射投影模型下，n個不同運動對象相關聯的二維軌跡位于n個仿射子空間的組成的R2F空間中，至此運動分割問題轉化為將所有的二維軌跡聚類到不同的子空間中，每個子空間對應于一個運動對象。

本部分采用Hopkins155數據庫[27]（圖4為部分視頻序列效果截圖）測試算法效果，Hopkins155數據庫由155個序列組成，包括104個室內場景序列，38個戶外交通場景序列和13個非剛性序列。其中有120個序列具有2個運動物體，其余35個序列具有3個運動物體。為了測試簡便，根據運動物體數量將數據分為兩組，分別對這兩組數據進行實驗。

圖4 Hopkins155數據庫部分序列聚類效果截圖

表1顯示了Hopkins155數據庫中155個序列聚類誤差，圖5與圖6展示了155個序列應用非負局部約束低秩子空間算法（NLRSI）各自的聚類誤差，明顯的，二物體比三物體聚類誤差更小。同時從表1中的數據可以看出NLRSI算法的聚類誤差比其他算法誤差小，雖然低秩表示算法（LRR）的中位值更低，但是從平均值結果來看，低秩表示算法對于某些序列的聚類效果不穩定，導致了誤差過大，拉高了平均值。

表1 各類算法在Hopkins155數據庫中的聚類誤差 %

4.3 手寫數字

圖5 Hopkins155數據庫NLRSI算法兩物體序列聚類錯誤率

圖6 Hopkins155數據庫NLRSI算法三物體序列聚類錯誤率

手寫數字聚類是指由不同人筆跡構成的一組數字圖像，將數字相同的圖像分離出。這里采用美國郵政手寫數字數據庫（USPS）測試算法的聚類效果。圖7顯示了部分數據樣本。該數據庫包含9 298張圖像，每張圖像為一個數字（0～9任意一個，如圖7所示），圖像的大小為16像素×16像素，因此數據矩陣X的維度為256。由于數據樣本過于龐大，對每一個數字隨機抽取100張圖像，共1 000張圖像作為數據樣本。同時為了測試聚類效果的多樣性，聚類的數目k設置為2～9，即分別抽取2個數字到9個數字評估聚類結果。

圖7 USPS數據庫部分數據樣本

從表2可以看出非負局部約束低秩子空間算法（NLRSI）的聚類誤差相比其他算法較小，當聚類數目k處于小值的時候，各個算法的聚類誤差相差很小，隨著k值的增大，聚類誤差都在增大，圖8所示的子空間數據結構圖可以直觀看出隨著簇的數量增多，噪聲點隨之增多，這是由于聚類數目增多會導致一些數據點同時存在于多個子空間中，造成重復計算。從圖9變化趨勢圖中觀察到NLRSI算法聚類誤差率增長較為緩和，說明NLRSI算法對于這些異常點的甄別較為精準。

表2 各類算法在USPS數據庫中的聚類誤差%

圖9 各類算法隨著聚類數目增多聚類誤差變化走勢圖

5 總結

本文提出了非負局部約束低秩子空間算法（NLRSI），該算法利用數據的局部稀疏結構和子空間的全局低秩特征，構造體現數據向量之間特點的親和度矩陣。理論分析保證了算法獲得的最優親和度矩陣具有良好的聚類效果。同時實驗結果表明，非負局部約束低秩子空間算法在運動分割和手寫數字聚類任務中，優于現存的幾種最先進的聚類算法。但是該算法也存有不足之處：為了保證聚類準確性，優先對數據字典做去噪處理，增加了運算時間；其次對于聚類數目較多的數據，聚類結果誤差較大。未來的工作將在保證準確性的同時，縮短運算時間，減少聚類誤差。