混合最小二乘回歸的稀疏子空間聚類算法

王 越 嚴 亮 張 強

(重慶理工大學計算機科學與工程系 重慶 400054)

混合最小二乘回歸的稀疏子空間聚類算法

王 越 嚴 亮 張 強

(重慶理工大學計算機科學與工程系 重慶 400054)

稀疏子空間聚類的關鍵在于在求得真實反映數據集的相似度矩陣，然后將相似度矩陣代入譜聚類求解。相似度矩陣既要刻畫數據集的子空間特性，同時也要反映出同一類數據點之間的兩兩相關程度，稀疏子空間聚類(SSC)專注于每一個數據表示系數的最大稀疏性，缺乏對數據集全局結構的描述;最小二乘回歸(LSR)保證了同一類數據的結構相關性，但是不夠稀疏。將最小二乘回歸引入稀疏子空間聚類算法中，從而保證數據的相似度矩陣兼具稀疏性和分組效應。在運動分割和人臉聚類的實驗中，將該算法和SSC、LSR算法對比，可以發現該算法在準確率上的優勢。

稀疏子空間聚類 最小二乘回歸 譜聚類 運動分割 人臉聚類

0 引 言

在聚類算法這個領域里，隨著數據維度劇增，結構復雜化，很多聚類算法出現數據類之間差異無法判斷，計算困難等問題。稀疏子空間聚類算法從2009年問世，如今在機器學習、計算機視覺、圖像處理等眾多領域有廣泛用途。

在稀疏子空間聚類這個大家族中，涌現了許多卓越的算法，2009年Elhamifar等[1]提出稀疏子空間聚算法(SSC)用稀疏表示揭示了數據的本質特征，通過數據點的線性表示來劃分不同的子空間，采用向量稀疏表示追求用最少的基或者字典原子來線性表示數據，過分追求數據的稀疏性，忽略了數據集的全局結構。2010年Liu等[2-3]提出的低秩子空間聚類(LRR)，選擇通過相似度矩陣秩的最小化作為目標函數，秩是矩陣的稀疏度量(二維稀疏性)，雖然保證數據的全局結構，數據有噪聲時稀疏差，不能準確反映子空間特性。2012年Lu等[4]提出最小二乘回歸子空間聚類(LSR)，每一個數據點的線性表示時，通過采用最小二乘回歸的方法來保證數據的全局結構，相比于LRR算法有較大進步。

本文通過考慮各種算法的優缺點，決定將最小二乘回歸引入稀疏子空間聚類算法中，從而得到能反映數據的全局結構的同時又有足夠稀疏性的相似的矩陣。在求解中引入最小二乘法的約束，從而避免過稀疏的缺點，同時添加數據集全局結構的因素，改善了稀疏子空間聚類算法不足，進而提高算法的魯棒性和準確率。

1 相關工作

子空間聚類將高維數據表示成多個低維子空間的并，每一類對應一個子空間如圖1。子空間聚類的求解方法有代數方法、迭代方法、統計學方法和基于譜聚類[5]的方法。前三種算法，在子空間的維數和個數未知的情況下，很難求解，并且奇異點和噪聲對算法比較敏感。基于譜聚類的子空間分割方法，由于基于圖譜理論，可以自動識別子空間維數和個數。

圖1 三維空間可以看成是一個二維平面子空間和兩個線性一維子空間

聚類融合[6]是利用不同的算法或同一算法尋找算法之間的切合點，以切合點為橋梁，將不同算法融合，來得到更高效穩定的聚類結果。本文研究重點是如何求解能真實逼近數據關系的相似度矩陣，針對兩種不同算法考慮的側重點不同，將他們融合進行取長補短，使得相似的矩陣更加準確。

2 原理及相關算法

2.1 稀疏子空間聚類

稀疏子空間聚類算法[7-10]，是運用子空間的基或者少量線性無關的向量來表示，讓矩陣大部分系數都為0的子空間聚類算法。稀疏性的表現往往可以從系數矩陣的稀疏性看出。

設有n個D維的數據X={x1,x2,…,xn}，為了獲得每個數據點的最稀疏的表示，經過凸松弛處理，稀疏最優化模型為：

(1)

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

初始化： Z=J=0,E=0,Y1=0,Y2=0,μ=10-6

maxu=1010,ρ=1.1,ε=10-8

While(‖X-XZ-E‖∞<ε&‖Z-J‖∞<ε)

Z=(I+XtX)-1(XtX-XtE+J+(XtY1-Y2)/μ)

Y1=Y1+μ(X-XZ-E)

Y2=Y2+μ(Z-J)

μ=min(ρμ,maxμ)

輸出：系數矩陣Z

當子空間獨立的時候，數據的系數矩陣成對角塊結構，很好地將一個類區別開，每一個Zi代表一個子空間，Zi的個數代表子空間的個數，Zi的維度代表子空間數據點的個數。在得到數據點的系數后，由于每一個點所用的基不同，所以Zi,j≠Zj,i，為了保證對稱性，令W=|Z|+|Z|T將系數矩陣W代入NJW譜聚類求得聚類結果。

SSC的缺點：

1) 在追求用盡可能少的基或者字典原子來表示數據時候，如果太過稀疏，同一類的數據點在相似度矩陣上的稀疏可能為0，這導致可能將同一類數據點劃分到不同的類。

2) 如果同一類的數據兩兩之間相關性比較強，算法是隨機選擇子空間的基來表示，所以系數矩陣不能反映同一類數據兩兩之間相關性程度。

3) 不能高效地求解每一個數據點的l1-范數最小化問題，時間復雜度太高。

2.2 最小二乘回歸(LSR)[4]

當子空間獨立的時候，SSC、LRR[11]、MSR等算法都能保證相似度矩陣的塊對角結構。稀疏子空間強調稀疏性，不僅是類間稀疏，同一類里面也同樣稀疏，忽視了同一類數據相互間的結構關系，子空間分割中同一類里面的數據的相關性也是非常重要的，當數據充足的情況下，數據間往往具有較強的相關性。文獻[4]當每一個數據被線性表示時，引入最小二乘法求解在整體上最佳逼近數據的表示系數，由于是NP問題，松弛為求解矩陣的Frobenius范數。

最小二乘回歸優化模型：

(2)

得到相似度矩陣W=|Z|+|Z|T，再將矩陣代入NJW譜聚類算法，求得聚類結果。

通過最小二乘法在求解相似度矩陣時，將每一數據的線性表示聯合考慮，很好地保證數據的結構相關性，但是這樣就會導致相比于SSC不夠稀疏。

2.3 混合最小二乘的稀疏子空間聚類算法

目前考慮數據全局結構相關性最好的算法為最小二乘回歸(LSR)算法，其充分利用數據之間的結構關系，在數據間的結構關系是用Frobenius范數的最小求解代替，可以保證數據間的結構關系，將Frobenius范數引入稀疏子空間聚類的。類間的稀疏性約束，是通過Z的l1-范數最小求解來達到的，為了平衡兩者間的權重，將兩者融合，選取適當的權重因子λ1。通過求解兩者融合的目標函數，從而得到更逼近真實數據的相似度矩陣。于是本文提出將兩種算法結合兼顧數據的稀疏性和分組性。

求相似度矩陣優化模型為：

(3)

算法

輸入：n個D維的數據X={x1,x2,…,xn}。

1. 解決最小化問題得到Z=[z1,z2,…,zn]。

3. 得到相似度矩陣W=|Z|+|Z|T。

4. 對相似度矩陣W使用譜聚類。

輸出：數據集的類分配。

3 實驗內容

3.1 人工數據集進行實驗

為了進一步詳細了解數據的相似度矩陣，采用文獻[12]的數據構造方法，構造方法其實就是兩個自定義矩陣相乘，針對250個200維的數據集，數據由五個子空間構成，每個子空間為50×200的矩陣。實驗結果如圖2所示。

圖2 三種算法的系數矩陣

實驗結果表明：每一個方塊代表一個子空間(代表一類)，圖2(a)是用SSC算法求解的系數矩陣，屬于一個子空間的相似度矩陣的系數不為0，其子空間內系數表示比較稀疏。圖2(b)是用LSR算法求解的相似度系數矩陣，子空間系數比較均勻但不稀疏。圖2(c)是用混合最小二乘回歸的稀疏子空間聚類算法求解的系數矩陣，可以看到效果比較好。

為了檢測本文的算法的性能，我們將算法分別在運動分割和人臉聚類進行實驗，同時對比SSC和LSR算法。對于運動分割，采用Hopkins 155數據集，對于人臉聚類，采用Extended Yale B數據集。

實驗中，采用聚類錯誤率來評價聚類算法的性能：

實驗分別采用SSC、LRR、LSR、本文算法進行實驗，并對比實驗結果。

3.2 運動分割實驗

運動分割[13]是指根據場景中的不同運動對一個包含多個運動物體的視頻序列進行分割。傳統的運動分割是根據多幅圖像之間的相關信息進行運動估計，從而計算出運動場，再進行運動物體的分割。本文的運動分割是依據具有相同運動軌跡的點在同一個線性子空間上，通過子空間進行聚類。數據集為x為2F×N維，其中F為視頻的幀數，N為二維軌跡的數目。這些二維軌跡通過跟蹤算法提取。

Hopkins 155數據集包含兩個或者三個運動的155個視頻序列，其中兩個運動物體的120個視頻序列，三個運動物體的35個視頻序列，由于單個固定運動的子空間維數不超過4，所以將數據點從2F維降到4n(n為聚類的數量)。如果直接進行使用會造成誤差，降低準確率，通過降維，我們可以減少冗余信息造成的誤差，從而提高聚類精度。數據進行降維實驗，將實驗結果可視化如圖3所示。

圖3 三種算法在car3數據上的可視化實驗結果

不同算法在Hopkins 155上的實驗結果如表1-表2所示。

表1 三種算法在Hopkins 155上的實驗結果

*Means(all)=

實驗結果分析：本文采用不準確ALM算法來求解，因為求解需要反復迭代，所以算法運行時間較長，三種算法在運行時間是上相差不大。由于實驗量比較大，本文選取均值和中值兩個指標來評判實驗的結果，從實驗的數據上來看，當運動的個數增加的時候算法的錯誤率會有所增加，但是本文算法在均值和中值上面依舊錯誤率明顯降低。

3.3 人臉聚類實驗

人臉聚類[14]是將多個人在不同的光照，角度，表情下的一組圖像集合進行聚類，依據同一個人的面部特征會處于同一個子空間理論，于是我們可以將Extended Yale B人臉數據集運用于子空間聚類。

Extended Yale B人臉數據集包含38個人，每一個人在不同光照、角度、表情下的人臉圖像64張，將38人進行標號為1～38號。為了進行實驗，將數據集分為1～10、11～20、21～30、31～38四組，每一組單獨進行聚類實驗，為了降低實驗的計算復雜度，我們將192×168的圖片抽樣到48×42的圖片，將一幅圖片作為一個2 016維的數據點，來進行聚類。下面以兩人不同光照和角度的20張圖片為例，如圖4所示。

圖4 兩個人的20張圖的數據集

人臉實驗的實驗結果如表3所示。

表3 三種算法在Extended Yale B數據集上的結果

表4 三種算法在Extended Yale B上的運算時間/min

在實驗中，對于四組數據集，我們對每一組進行單獨實驗，隨機抽取數據進行聚類。由于聚類數低于5，準確率幾乎100%，所以本文主要采用聚5類和聚8類，因為聚類數越多，各種算法之間的差異性就體現出來了。本文算法在人臉聚類實驗中，算法運行時間并沒有顯著變化，但在準確率上高于目前流行的SSC、LSR算法。

4 結 語

本文將最小二乘回歸融于稀疏子空間聚類中，從而得到兼具稀疏性和分組性的相似度矩陣，通過在Hopkins 155運動分割集和Extended Yale B中實驗聚類效果優異。本文缺點是無法自動確定比重，其次算法都是針對線性子空間的，對于非線性子空間就不適用。這兩點也是進一步研究的重點。

[1] Elhamifar E,Vidal R.Sparse subspace clustering[C]//Computer Vision and Pattern Recognition,2009.CVPR 2009.IEEE Conference on.IEEE,2009:2790-2797.

[2] Liu G,Lin Z,Yu Y.Robust Subspace Segmentation by Low-Rank Representation[C]//International Conference on Machine Learning.DBLP,2010:663-670.

[3] Liu G,Yan S.Latent Low-Rank Representation for subspace segmentation and feature extraction[C]//International Conference on Computer Vision.IEEE Computer Society,2011:1615-1622.

[4] Lu C Y,Min H,Zhao Z Q,et al.Robust and Efficient Subspace Segmentation via Least Squares Regression[M].Computer Vision-ECCV 2012.Springer Berlin Heidelberg,2012:347-360.

[5] Chen G,Lerman G.Spectral Curvature Clustering (SCC)[J].International Journal of Computer Vision,2009,81(3):317-330.

[6] 陽琳贇,王文淵.聚類融合方法綜述[J].計算機應用研究,2005,22(12):8-10.

[7] 李小平,王衛衛,羅亮.圖像分割的改進稀疏子空間聚類方法[J].系統工程與電子技術,2015,37(10):2418-2424.

[8] 付剛,吳觀茂.迭代加權的稀疏子空間聚類[J].電腦知識與技術,2015,11(28):30-31.

[9] 李濤,王衛衛,翟棟.圖像分割的加權稀疏子空間聚類方法[J].系統工程與電子技術,2014,36(3):580-585.

[10] 歐陽佩佩,趙志剛,劉桂峰.一種改進的稀疏子空間聚類算法[J].青島大學學報(自然科學版),2014,27(3):44-48.

[11] 劉建華.基于隱空間的低秩稀疏子空間聚類[J].西北師范大學學報(自然科學版),2015(3):49-53.

[12] 劉紫涵,吳鵬海,吳艷蘭.三種譜聚類算法及其應用研究[J].計算機應用研究,2017(4):1026-1031.

[13] 任永功.視頻運動對象分割技術的研究[J].小型微型計算機系統,2004,6(3):1082-1085.

[14] 魏衍君,楊明莉.基于聚類建模的三維人臉識別技術研究[J].陜西科技大學學報(自然科學版),2012,30(2):77-81.

SPARSESUBSPACECLUSTERINGALGORITHMBASEDONLEASTSQUARESREGRESSION

Wang Yue Yan Liang Zhang Qiang

(CollegeofComputerScienceandEngineering,ChongqingUniversityofTechnology,Chongqing400054,China)

The key of sparse subspace clustering is to get the true reflection of the similarity matrix of data set. And then the similarity matrix is brought into the spectral clustering algorithm. Similarity matrix not only describes the data set, but also reflects the correlation of the within-cluster data. The sparse subspace clustering (SSC) focuses on the maximum sparsity of each data representation coefficient, lacks overall structure description of data sets. The least-squares regression (LSR) ensures the relevance structure of the within-cluster data, but is not sparse enough. We introduce the least-squares regression into sparse subspace clustering algorithms, so as to ensure the similarity matrix of the data is sparseness and grouping effect. Compared with SSC, LSR algorithm, our algorithm can produce more accurate results in the experiment.

Sparse subspace clustering Least-squares regression Spectral clustering Motion segmentation Face clustering

TP391.1

A

10.3969/j.issn.1000-386x.2017.10.042

2016-09-14。王越，教授，主研領域：數據庫技術及應用，數據挖掘及應用。嚴亮，碩士生。張強，碩士生。