王 越 嚴(yán) 亮 張 強

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

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

王 越 嚴(yán) 亮 張 強

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

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

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

0 引 言

在聚類算法這個領(lǐng)域里，隨著數(shù)據(jù)維度劇增，結(jié)構(gòu)復(fù)雜化，很多聚類算法出現(xiàn)數(shù)據(jù)類之間差異無法判斷，計算困難等問題。稀疏子空間聚類算法從2009年問世，如今在機器學(xué)習(xí)、計算機視覺、圖像處理等眾多領(lǐng)域有廣泛用途。

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

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

1 相關(guān)工作

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

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

聚類融合[6]是利用不同的算法或同一算法尋找算法之間的切合點，以切合點為橋梁，將不同算法融合，來得到更高效穩(wěn)定的聚類結(jié)果。本文研究重點是如何求解能真實逼近數(shù)據(jù)關(guān)系的相似度矩陣，針對兩種不同算法考慮的側(cè)重點不同，將他們?nèi)诤线M行取長補短，使得相似的矩陣更加準(zhǔn)確。

2 原理及相關(guān)算法

2.1 稀疏子空間聚類

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

設(shè)有n個D維的數(shù)據(jù)X={x1,x2,…,xn}，為了獲得每個數(shù)據(jù)點的最稀疏的表示，經(jīng)過凸松弛處理，稀疏最優(yōu)化模型為：

(1)

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

初始化： 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μ)

輸出：系數(shù)矩陣Z

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

SSC的缺點：

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

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

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

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

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

最小二乘回歸優(yōu)化模型：

(2)

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

通過最小二乘法在求解相似度矩陣時，將每一數(shù)據(jù)的線性表示聯(lián)合考慮，很好地保證數(shù)據(jù)的結(jié)構(gòu)相關(guān)性，但是這樣就會導(dǎo)致相比于SSC不夠稀疏。

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

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

求相似度矩陣優(yōu)化模型為：

(3)

算法

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

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

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

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

輸出：數(shù)據(jù)集的類分配。

3 實驗內(nèi)容

3.1 人工數(shù)據(jù)集進行實驗

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

圖2 三種算法的系數(shù)矩陣

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

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

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

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

3.2 運動分割實驗

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

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

圖3 三種算法在car3數(shù)據(jù)上的可視化實驗結(jié)果

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

表1 三種算法在Hopkins 155上的實驗結(jié)果

*Means(all)=

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

3.3 人臉聚類實驗

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

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

圖4 兩個人的20張圖的數(shù)據(jù)集

人臉實驗的實驗結(jié)果如表3所示。

表3 三種算法在Extended Yale B數(shù)據(jù)集上的結(jié)果

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

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

4 結(jié) 語

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

[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].計算機應(yīng)用研究,2005,22(12):8-10.

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

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

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

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

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

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

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

[14] 魏衍君,楊明莉.基于聚類建模的三維人臉識別技術(shù)研究[J].陜西科技大學(xué)學(xué)報(自然科學(xué)版),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。王越，教授，主研領(lǐng)域：數(shù)據(jù)庫技術(shù)及應(yīng)用，數(shù)據(jù)挖掘及應(yīng)用。嚴(yán)亮，碩士生。張強，碩士生。