基于隱空間的低秩稀疏子空間聚類

劉建華

(浙江工商職業(yè)技術(shù)學(xué)院電子與信息工程學(xué)院，浙江寧波　315012)

基于隱空間的低秩稀疏子空間聚類

劉建華

(浙江工商職業(yè)技術(shù)學(xué)院電子與信息工程學(xué)院，浙江寧波315012)

摘要：提出了一種基于隱空間的低秩稀疏子空間聚類算法，在聚類的過程中可以對高維數(shù)據(jù)進(jìn)行降維，同時在低維空間中利用稀疏表示和低秩表示對數(shù)據(jù)進(jìn)行聚類，大大降低了算法的時間復(fù)雜度.在運(yùn)動分割和人臉聚類問題上的實驗證明了算法的有效性.

關(guān)鍵詞：子空間聚類；稀疏表示；低秩表示；運(yùn)動分割；人臉聚類

中圖分類號：TP 391

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-988Ⅹ(2015)03-0049-05

Low-rank sparse subspace clustering in latent space

LIU Jian-Hua

(College of Electronics and Information Engineering,Zhejiang Business Technology Institute,

Ningbo 315012,Zhejiang,China)

Abstract:This paper proposed a novel algorithm named low-rank sparse subspace clustering in latent space(LatLRSSC),it can reduce the dimension and cluster the data lying in a union of subspaces simultaneously.The main advatages of our method is that it is computationally efficient.The effectiveness of the algorithm is demonstrated through experiments on motion segmentation and face clustering.

Key words:subspace clustering;sparse representation;low-rank representation;motion segmentation;face clustering

0引言

過去的幾十年人們見證了數(shù)據(jù)的爆炸式增長，這對于數(shù)據(jù)的處理工作提出了巨大的挑戰(zhàn)，特別是這些數(shù)據(jù)集通常都是高維數(shù)據(jù).數(shù)據(jù)的高維特性不僅增加了計算時間，而且由于噪聲和環(huán)境空間降低了算法的性能.實際上，這些數(shù)據(jù)的內(nèi)在尺度往往比實際空間中小得多，這就促使人們運(yùn)用一些技術(shù)發(fā)現(xiàn)高維數(shù)據(jù)的低維表示，比如低秩近似和稀疏表示等[1-3].實際上，在許多問題中，高維空間中的數(shù)據(jù)往往可以用低維子空間進(jìn)行表示.子空間聚類算法就是挖掘數(shù)據(jù)低維子空間的一種聚類算法[4]，它已經(jīng)被廣泛地應(yīng)用在許多領(lǐng)域，如計算機(jī)視覺中的運(yùn)動分割和人臉聚類，控制領(lǐng)域的混合系統(tǒng)辨識，社交網(wǎng)絡(luò)中的社區(qū)集群.為了解決高維數(shù)據(jù)聚類問題，目前已經(jīng)提出了很多聚類算法，如混合高斯模型、NMF和一些代數(shù)方法(如k-subspace)、混合概率主成分分析(MPPCA)、多階段學(xué)習(xí)與RANSAC.這些方法取得了一定的效果，但是還有很多局限性，如計算復(fù)雜度太高，對噪音敏感等.

最近，利用稀疏表示和低秩表示進(jìn)行子空間聚類的研究得到了廣泛的關(guān)注，研究人員提出了一系列相關(guān)的新型子空間聚類算法，如稀疏子空間聚類(SSC)[5,6]、低秩表示(LRR)[4,7]、低秩子空間聚類(LRSC)[8]和低秩稀疏子空間聚類(LRSSC)[9]，這些方法的本質(zhì)是每一個數(shù)據(jù)點可以通過其他數(shù)據(jù)點稀疏表示或者低秩表示得到.盡管稀疏子空間聚類(SSC)和低秩表示(LRR)取得了巨大的成功，仍然有很多問題沒有解決.特別是稀疏表示和低秩表示的計算復(fù)雜度相當(dāng)高，尤其是當(dāng)數(shù)據(jù)的維數(shù)很高的時候[6].為了解決這個問題，通常的做法是在應(yīng)用這類聚類算法之前對數(shù)據(jù)進(jìn)行降維預(yù)處理.一些降維方法如主成分分析(PCA)或者隨機(jī)投影(RP)可以有效降低數(shù)據(jù)維數(shù).然而，一個良好學(xué)習(xí)的投影矩陣可以在更低的數(shù)據(jù)維度上得到更好的聚類效果.基于低維隱空間的稀疏表示已經(jīng)有學(xué)者提出了一些方法[10,11]，但是這些方法都是為分類問題進(jìn)行設(shè)計，而非針對聚類問題.

基于上述問題，文中提出一種基于低維隱空間的低秩稀疏子空間聚類方法(LatLRSSC)，在數(shù)據(jù)降維的同時，發(fā)掘數(shù)據(jù)的稀疏和低秩表示.首先算法學(xué)習(xí)得到數(shù)據(jù)從原始空間到低維隱空間的變換矩陣，同時在這個低維的隱空間中得到數(shù)據(jù)的稀疏和低秩系數(shù)，最后利用譜聚類算法對數(shù)據(jù)樣本進(jìn)行分割.為了驗證文中提出方法的有效性，分別在HOPKINS 155 數(shù)據(jù)集和extended Yale B 數(shù)據(jù)集上進(jìn)行運(yùn)動分割和人臉聚類的實驗，實驗結(jié)果表明，文中提出的LatLRSSC算法具有較好的聚類性能.

1相關(guān)工作

1.1稀疏子空間聚類

根據(jù)文獻(xiàn)[5,6]，每一個數(shù)據(jù)點可以表示為其他數(shù)據(jù)點的稀疏線性組合，通過這些稀疏系數(shù)構(gòu)造清河矩陣進(jìn)行子空間聚類.也就是說，給定一個數(shù)據(jù)集X，希望找到一個系數(shù)矩陣C，滿足X=XC并且diag(C)=0.可以通過求解(1)式得到解.

(1)

當(dāng)數(shù)據(jù)集被噪聲G污染時，SSC算法假設(shè)每個數(shù)據(jù)點可以表示為X=XC+G,可以通過求解凸優(yōu)化問題(2)得到解.

(2)

1.2低秩表示(LRR)

低秩表示(LRR)算法和稀疏子空間聚類(SSC)算法非常類似，區(qū)別在于LRR算法的目標(biāo)是尋找數(shù)據(jù)的低秩表示，而SSC算法在于尋找數(shù)據(jù)的稀疏表示.LRR通過求解凸優(yōu)化問題(3)得到解.

(3)

當(dāng)數(shù)據(jù)集被噪聲G污染時，LRR通過求解凸優(yōu)化問題(4)得到解.

(4)

2基于低維隱空間的低秩稀疏子空間聚類

不同于傳統(tǒng)的稀疏子空間聚類算法(SSC)和低秩表示(LRR)，文中將數(shù)據(jù)映射到一個低維的隱空間中，同時在這個低維空間中尋求數(shù)據(jù)的低秩稀疏系數(shù).令P∈Rt×D為一個線性變換矩陣，它將數(shù)據(jù)從原始空間RD映射到一個維數(shù)為t的隱空間中.通過目標(biāo)函數(shù)的最小化，可以同時得到變換矩陣和數(shù)據(jù)集的低秩稀疏系數(shù):

(5)

其中

(6)

(6)式的第一項為求取數(shù)據(jù)集的低秩系數(shù);第二項為求取數(shù)據(jù)集的稀疏系數(shù);第三項的主要目的是去除噪聲影響;最后一項是類似于PCA的正則項，主要目的是保證映射變換不能過多丟失一些原始空間的信息;λ1和λ2為非負(fù)常數(shù).另外，要求P正交并且歸一化，這樣就避免了解的退化，并且保證了優(yōu)化方法的計算效率.

可以注意到，(6)式是能夠進(jìn)行擴(kuò)展的，這樣就可以對位于仿射子空間中的數(shù)據(jù)進(jìn)行處理.可以對優(yōu)化問題(5)增加一個約束條件得到

(7)

2.1優(yōu)化問題求解

根據(jù)上面的定義，有下面的命題.

命題1優(yōu)化問題(5)存在一個最優(yōu)化的解P*，對于某些Ψ∈RN×t，N為數(shù)據(jù)樣本數(shù)，P*具有以下形式

直觀上， 命題1是說投影變換可以寫成數(shù)據(jù)樣本的一個線性組合.文獻(xiàn)[12]中，這個形式已經(jīng)被應(yīng)用在字典學(xué)習(xí)的框架中.

基于命題1，目標(biāo)函數(shù)(6)可以寫為

(8)

其中K=YTY.約束條件變?yōu)?/p>

(9)

所以，優(yōu)化問題(5)可表示為

(10)

其中

這樣，可分別通過Ψ和C來求解這個優(yōu)化問題.

2.2Ψ的優(yōu)化步驟

首先固定C，目標(biāo)函數(shù)就變?yōu)?/p>

(11)

上式可以另寫為

(12)

其中Q=ΨΨT∈RN×N.由約束條件ΨTKΨ=I可得到新的約束條件ΨΨTKΨΨT=ΨΨT或者QKQT=Q,目標(biāo)函數(shù)(12)可以進(jìn)一步簡化為

(13)

使用同樣的約束條件，并且知tr(K)為一個常數(shù),利用K=VSVT的特征值分解，得到

利用ΨTKΨ=MTM和變換

得到等價于問題(11)的優(yōu)化問題:

(14)

優(yōu)化問題(14)就是經(jīng)典的最小特征值問題.它的解就是與Δ的前l(fā)個最小特征值相關(guān)聯(lián)的l個特征向量.一旦得到了最優(yōu)的M*，那么最優(yōu)的Ψ*就可以利用(5)式得到:

(15)

2.3C的優(yōu)化步驟

固定Ψ，通過求解下列優(yōu)化問題來得到C

(16)

其中 B=ΨTK.

接下來，推導(dǎo)了一個解決優(yōu)化問題(16)的有效方法.在ADMM框架下，引入兩個輔助變量C=C1=C2來區(qū)分兩個不同的范數(shù)，引入J來保證每一步都得到閉合解:

則增廣拉格朗日方程為

其中μ1和μ2為可調(diào)參數(shù).每一步中，通過分別求解J,C1和C2的梯度，更新對偶變量Λ1和Λ2，可以得到ADMM每一步的迭代公式.

(17)

(18)

Λ1和Λ2的更新規(guī)則如下:

3實驗

分別驗證文中提出的LatLRSSC算法在運(yùn)動分割和人臉聚類兩種問題上的性能.對于運(yùn)動分割問題，采用Hopkins155數(shù)據(jù)集，包含155個視屏序列.對于人臉聚類問題，采用ExtendedYaleB數(shù)據(jù)集，包含38類人臉圖像數(shù)據(jù).

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

對比算法采用了LRR，LRSC，SSC和LRSSC這4種應(yīng)用較為廣泛的子空間聚類算法.

3.1運(yùn)動分割實驗

運(yùn)動分割是指從視頻序列中對于不同的剛體運(yùn)動提取一組二維點軌跡，對這些軌跡進(jìn)行聚類，實現(xiàn)不同運(yùn)動物體的分割.這里，數(shù)據(jù)集X為2F×N維，其中N為二維軌跡的數(shù)目，F(xiàn)為視頻的幀數(shù).在仿射投影模型中，這些與剛體運(yùn)動相關(guān)聯(lián)的二維軌跡位于維數(shù)為1,2或3的仿射子空間R2F中.

實驗中，采用Hopkins155運(yùn)動分割數(shù)據(jù)集，其中120個視頻序列由2個運(yùn)動構(gòu)成，35個視頻序列由3個運(yùn)動構(gòu)成.平均來說，每一個包含2個運(yùn)動的視頻序列包含N=256個特征軌跡和F=30幀畫面，而每一個包含3個運(yùn)動的視頻序列包含N=398個特征軌跡和F=29幀畫面.對于每一個視頻序列，這些二維軌跡通過跟蹤器自動提取，并且噪音點已經(jīng)手動去除.

表1比較了不同算法在Hopkins155數(shù)據(jù)集上的聚類表現(xiàn).實驗中，除了文中提出的算法，對于其他算法，利用PCA進(jìn)行預(yù)處理，將數(shù)據(jù)集降維到4n維(n為子空間數(shù)目).

表1　不同聚類算法在Hopkins 155數(shù)據(jù)集上的

從表1 可以看出，對于2個或3個運(yùn)動，文中提出的算法LatLRSSC相較于其他4種方法具有較好的聚類性能，說明LatLRSSC對于運(yùn)動分割問題具有很好的效果.對比其他算法可知，相對于直接采用PCA進(jìn)行降維操作，LatLRSSC通過對數(shù)據(jù)集的學(xué)習(xí)能夠得到更加合理的映射矩陣.

3.2人臉聚類實驗

給定多個人在同一角度、不同光照的人臉圖像，希望將不同的人臉圖像劃分開來(圖1).在Lambertian假設(shè)下，物體圖像在固定角度、不同光照條件下位于一個近似的9維子空間中，因此，采集的多個人的人臉圖像也位于這樣的9維子空間中.

圖1　人臉圖像聚類示例

采用Extended Yale B數(shù)據(jù)集，數(shù)據(jù)集包含n=38個人的人臉圖像(192×168像素)，每個人有Ni=64張在不同光照條件下的正面圖像.為了降低計算成本和存儲代價，將每幅人臉圖像采樣到48×42像素，并將圖像向量化為2 016維，因此維度D=2 016.實驗中，除了文中提出的算法，對于其他算法，依然利用PCA進(jìn)行降維預(yù)處理.

為了研究這些算法對不同聚類數(shù)目的聚類性能，將38類人臉分成4組，前3組分別包含1～10,11～20,21～30個人的人臉圖像，第四組包含31～38個人的人臉圖像.對于前3組，取n∈{2,3,5,8,10}；對最后一組，取n∈{2,3,5,8}.實驗結(jié)果如表2所示.

表2　不同算法在Extended Yale B 數(shù)據(jù)集上的

從表2可以看出，文中提出的LatLRSSC對不同的聚類數(shù)目均得到了更低的聚類錯誤率，說明了該算法優(yōu)于其他算法.

4結(jié)束語

文中提出了一種基于隱空間的低秩稀疏子空間聚類算法.本算法是稀疏子空間聚類和低秩表示的一種擴(kuò)展，該算法在聚類的過程中可以對高維數(shù)據(jù)進(jìn)行降維，同時在低維空間中利用稀疏表示和低秩表示對數(shù)據(jù)進(jìn)行聚類.在運(yùn)動分割和人臉聚類上的實驗表明，該算法具有很好的聚類性能.

與大多數(shù)子空間聚類算法一樣，文中假設(shè)子空間是線性的，如何將本算法在非線性子空間上進(jìn)行擴(kuò)展是接下來需要繼續(xù)研究的工作.

參考文獻(xiàn):

[1]ABDI H,WILLIAMS L J.Principal component analysis[J].WileyInterdisciplinaryReviews:ComputationalStatistics,2010,2(4):433-459.

[2]LAUERF,SCHNORRC.Spectralclusteringoflinearsubspacesformotionsegmentation[C]//Proceedings of the 12 th International Conference on Computer Vision.Kyoto:IEEE,2009:678-685.

[3]WRIGHTJ,YANGAY,GANESHA,etal.Robustfacerecognitionviasparserepresentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(2):210-227.

[4]LIUG,LINZ,YUY.Robustsubspacesegmentationbylow-rankrepresentation[C]//Proceedings of the 27th International Conference on Machine Learning.Haifa:Omnipress,2010:663-670.

[5]ELHAMIFARE,VIDALR.Sparsesubspaceclustering[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Anchorage:IEEE,2009:2790-2792.

[6]ELHAMIFAR,VIDALR.Sparsesubspaceclustering:Algorithm,theory,andapplications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(11):2765-2781.

[7]LIUG,LINZ,YANS.Robustrecoveryofsubspacestructuresbylow-rankrepresentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(1):171-184.

[8]FAVAROP,VIDALR,RAVICHANDRANA.Aclosedformsolutiontorobustsubspaceestimationandclustering[C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.Colorado:IEEE,2011:1801-1807.

[9]WANGYX,XUH,LENGC.Provablesubspaceclustering:WhenLRRmeetsSSC[C]//Advances in Neural Information Processing Systems.Nevada:MITPress,2013:64-72.

[10]MAIRALJ,BACHF,PONCEJTask-drivendictionarylearning[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(4):791-804.

[11]NGUYENHV,PATELVM,NASRABADINM,etal.Sparseembedding:Aframeworkforsparsitypromotingdimensionalityreduction[M]//Computer Vision—ECCV 2012.Berlin:Springer,2012:414-427.

[12]RUBINSTEINR,ZIBULEVSKYM,ELADM.Doublesparsity:Learningsparsedictionariesforsparsesignalapproximation[J].IEEE Transactions on Signal Processing,2010,58(3):1553-1564.

(責(zé)任編輯惠松騏)

作者簡介：劉建華(1979—)，男，江西九江人，講師，碩士.主要研究方向為模式識別與圖像處理.

基金項目:浙江省自然科學(xué)基金資助項目(LY14F020009)

收稿日期：2015-01-19;修改稿收到日期:2015-03-24

E-mail:liujianhua_1979@126.com