由從哲 舒振球 范洪輝

摘? ? 要：研究序列數(shù)據(jù)的子空間聚類問題，具體來說，給定從一組序列子空間中提取的數(shù)據(jù)，任務(wù)是將這些數(shù)據(jù)劃分為不同的不相交組?；诒硎镜淖涌臻g聚類算法，如SSC和LRR算法，很好地解決了高維數(shù)據(jù)的聚類問題，但是，這類算法是針對(duì)一般數(shù)據(jù)集進(jìn)行開發(fā)的，并沒有考慮序列數(shù)據(jù)的特性，即相鄰幀序列的樣本具有一定的相似性。針對(duì)這一問題，提出了一種新的低秩稀疏空間子空間聚類方法（Low Rank and Sparse Spatial Subspace Clustering for Sequential Data，LRS3C）。該算法尋找序列數(shù)據(jù)矩陣的稀疏低秩表示，并根據(jù)序列數(shù)據(jù)的特性，在目標(biāo)函數(shù)中引入一個(gè)懲罰項(xiàng)來加強(qiáng)近鄰數(shù)據(jù)樣本的相似性。提出的LRS3C算法充分利用空間序列數(shù)據(jù)的時(shí)空信息，提高了聚類的準(zhǔn)確率。在人工數(shù)據(jù)集、視頻序列數(shù)據(jù)集和人臉圖像數(shù)據(jù)集上的實(shí)驗(yàn)表明：提出的方法LRS3C與傳統(tǒng)子空間聚類算法相比具有較好的性能。

關(guān)鍵詞：低秩表示;稀疏表示;子空間聚類;序列數(shù)據(jù)

中圖分類號(hào)：TP391.4? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：2095-7394（2020）04-0078-08

序列數(shù)據(jù)特別是視頻數(shù)據(jù)往往具有高維屬性，利用傳統(tǒng)聚類算法進(jìn)行分析處理時(shí)，往往會(huì)遇到“維數(shù)災(zāi)難”的問題，于是研究人員提出了一系列基于表示的子空間聚類算法，如稀疏表示子空間聚類算法（SSC）和低秩表示算法（LRR），較好地解決了高維數(shù)據(jù)聚類的問題，從而得到了廣泛的關(guān)注，并在眾多領(lǐng)域得到成功的應(yīng)用。但是，這類算法是針對(duì)一般數(shù)據(jù)集設(shè)計(jì)開發(fā)的，在許多實(shí)際場(chǎng)景中，數(shù)據(jù)通常具有順序或有序的屬性，例如視頻、動(dòng)畫或其他類型的時(shí)間序列數(shù)據(jù)。然而，傳統(tǒng)的方法假設(shè)數(shù)據(jù)點(diǎn)獨(dú)立于多個(gè)子空間，而忽略了時(shí)間序列數(shù)據(jù)中的連續(xù)關(guān)系。如何充分利用空間序列數(shù)據(jù)這一特性提高聚類性能，是計(jì)算機(jī)視覺領(lǐng)域中一個(gè)重要但又具有挑戰(zhàn)性的問題。假設(shè)這類數(shù)據(jù)在時(shí)間或空間的特定點(diǎn)以均勻的間隔采樣，也就是時(shí)間序列數(shù)據(jù)。例如，作為時(shí)間函數(shù)的視頻數(shù)據(jù)具有序列結(jié)構(gòu)[1]，在該結(jié)構(gòu)中，可以假設(shè)大多數(shù)幀與其相鄰幀相似，直到場(chǎng)景發(fā)生變化。

子空間聚類是解決高維數(shù)據(jù)聚類的有效方法之一，其基本假設(shè)是高維數(shù)據(jù)往往存在于低維子空間的并集中[2]。近年來，利用稀疏表示或低秩表示進(jìn)行子空間聚類的研究受到廣泛關(guān)注，并提出了一系列與之相關(guān)的新的子空間聚類算法，如稀疏子空間聚類（SSC）[3-4]、低秩表示（LRR）[2，5]及其變體LRSC[6]。這些算法的基本假設(shè)是：數(shù)據(jù)是自表達(dá)的，即其子空間中的每個(gè)數(shù)據(jù)點(diǎn)可以表示為來自同一子空間的數(shù)據(jù)點(diǎn)的線性組合。其中，基于表示矩陣核范數(shù)和L1范數(shù)最小化的LRR和SSC算法最受關(guān)注。這些算法主要是針對(duì)不連續(xù)的獨(dú)立數(shù)據(jù)進(jìn)行設(shè)計(jì)開發(fā)的，并沒有特別考慮到處理時(shí)間序列數(shù)據(jù)的特殊性。此外，在時(shí)間序列數(shù)據(jù)的子空間聚類問題上，研究人員所做的工作并不是特別充分。

本文通過有效利用數(shù)據(jù)序列的性質(zhì)，提出了一種低秩稀疏空間子空間聚類方法（LRS3C）。具體地說，是在子空間聚類算法模型中加入了一個(gè)懲罰項(xiàng)來加強(qiáng)近鄰數(shù)據(jù)的相似性。采用交替方向乘子法（ADMM）[7]求解優(yōu)化問題。為了驗(yàn)證提出的LRS3C方法的有效性，將其應(yīng)用于視頻場(chǎng)景分割和人臉聚類的實(shí)際問題中。實(shí)驗(yàn)結(jié)果表明，該方法具有良好的性能。

1? ?相關(guān)工作

目前，大多數(shù)子空間聚類算法沒有充分考慮時(shí)間序列數(shù)據(jù)的序列性，也就是說，數(shù)據(jù)樣本要么是空間域中的鄰居，要么是時(shí)間域中的鄰居。視頻是時(shí)間序列數(shù)據(jù)的一個(gè)常見例子，每個(gè)幀可以被矢量化為單個(gè)列[Xi]，并與相鄰幀并排放置以形成數(shù)據(jù)矩陣[X]。這種順序應(yīng)反映在矩陣表示系數(shù)[Z]中，使得相鄰域具有相似性，即[Zi=Zi+1]。在文獻(xiàn)[8]中，Guo和Gao等人提出了空間子空間聚類（SpatSC）算法，其目標(biāo)函數(shù)定義如下：

2? ?空間序列低秩稀疏子空間聚類算法

盡管SpatSC和OSC兩種方法都是稀疏子空間聚類算法（SSC）的擴(kuò)展，在序列數(shù)據(jù)方面取得了良好的效果，但仍有一些問題有待解決。SSC算法簡(jiǎn)化了學(xué)習(xí)任務(wù)，降低了模型復(fù)雜度，但是，SSC算法得到的系數(shù)矩陣Z往往過于稀疏，無法保證所構(gòu)造的親和圖的連通性，這對(duì)后續(xù)譜聚類的處理有很大影響[10]。低秩表示（LRR）在捕獲數(shù)據(jù)的全局結(jié)構(gòu)方面要優(yōu)于SSC，但是，LRR算法要求數(shù)據(jù)嚴(yán)格符合子空間獨(dú)立的假設(shè)，這在實(shí)際應(yīng)用中很難得到滿足。因此，將這兩種算法結(jié)合起來，從而為序列數(shù)據(jù)帶來更好的聚類效果，特別是要恢復(fù)的底層表示矩陣同時(shí)是低秩和稀疏的情況。

在解決上述優(yōu)化問題后，得到數(shù)據(jù)矩陣的低秩稀疏表示系數(shù)矩陣[Z]。下一步是使用表示系數(shù)矩陣構(gòu)造親和圖，利用譜聚類算法對(duì)親和圖進(jìn)行分割，得到最終聚類結(jié)果。本文建立一個(gè)加權(quán)圖[Graph=ν，ε，W]，其中[W=Z+ZT]，然后將譜聚類[13]應(yīng)用于親和圖，得到最終的聚類結(jié)果。

3? ? 實(shí)驗(yàn)

在本節(jié)中，將評(píng)估LRS3C算法在三個(gè)數(shù)據(jù)集上的性能。首先，在一個(gè)合成數(shù)據(jù)集上對(duì)其進(jìn)行測(cè)試;然后，在兩個(gè)真實(shí)數(shù)據(jù)集上對(duì)其在視頻場(chǎng)景分割和人臉聚類兩個(gè)計(jì)算機(jī)視覺常見任務(wù)上的性能進(jìn)行評(píng)估。

使用子空間聚類誤差，

作為聚類算法性能的評(píng)價(jià)指標(biāo)。

此外，還評(píng)估了所提出的LRS3C算法在加入額外噪聲時(shí)的穩(wěn)健性。在本文中，加入了均值和單位方差為零的高斯噪聲，給出了該算法在不同噪聲強(qiáng)度下的性能。使用峰值信噪比（PSNR）衡量噪聲水平，其定義為：

其中，[I]是無噪聲數(shù)據(jù)，[K]是有噪聲近似值，[S]是[I]中的元素的最大可能值。PSNR值的降低表明噪聲量的增加。由于式（17）的分母在無噪聲情況下為0，將PSNR標(biāo)記為“Max”。實(shí)驗(yàn)中給出的PSNR值為平均值。

3.1? 人工數(shù)據(jù)集實(shí)驗(yàn)

本文創(chuàng)建了六個(gè)兩兩不相交的子空間，每個(gè)子空間的維數(shù)為4，并從每個(gè)子空間中抽取20個(gè)樣本（樣本維數(shù)為200）組成人工數(shù)據(jù)集。利用高斯噪聲對(duì)數(shù)據(jù)集進(jìn)行破壞，并評(píng)估LRS3C算法和對(duì)比算法OSC、SpatSC、LRR和SSC的聚類性能。每組實(shí)驗(yàn)重復(fù)了50次。

圖1中給出了五個(gè)算法得到的表示系數(shù)矩陣Z的可視化比較，并在圖2中給出了這些親合矩陣的聚類精度的結(jié)果。實(shí)驗(yàn)中，加入了20%量級(jí)的高斯噪聲，可以看到，所提出的LRS3C算法提供了更多的塊狀表示系數(shù)矩陣，這意味著它比其他方法包含更強(qiáng)的類內(nèi)權(quán)值和更多的類內(nèi)權(quán)值?？梢暬垲惤Y(jié)果也表明了LRS3C在實(shí)驗(yàn)中得到了最佳分割。另外兩種矩陣算法OSC和SpatSC算法對(duì)序列數(shù)據(jù)也都得到了很好的分割，但是LRR和SSC算法則存在誤分類的問題。

3.2? ?視頻場(chǎng)景分割

評(píng)估LRS3C算法在視頻場(chǎng)景分割方面的性能，其目的是從視頻序列中分割單個(gè)場(chǎng)景。測(cè)試視頻序列是從兩個(gè)短動(dòng)畫中提取出來的。圖3提供了要分割的序列的示例。序列的長(zhǎng)度約為10秒（約300幀），每個(gè)序列由三個(gè)場(chǎng)景組成。視頻1和視頻2分別包括19和24個(gè)序列。要分割的場(chǎng)景可以包含對(duì)象的意義或變形，以及透視或相機(jī)視角的變換。人工采集場(chǎng)景變化（或關(guān)鍵幀）形成真實(shí)數(shù)據(jù)。

為了滿足測(cè)試要求，將彩色視頻轉(zhuǎn)換成灰度視頻序列，采樣分辨率為129×96。序列中的每一幀被矢量化為[Xi∈R12 384]，并與連續(xù)幀連接形成數(shù)據(jù)矩陣[X∈R12 384×300]。

在視頻序列被不同程度的高斯噪聲污染的條件下，評(píng)估了各算法的聚類性能，表1提供了聚類結(jié)果。從表中可以清楚地看出，在大多數(shù)情況下，LRS3C優(yōu)于其他方法。當(dāng)噪聲增大時(shí)，與其它方法相比，LRS3C算法的誤差率始終較低。這表明該方法具有較好的魯棒性。

3.3? 人臉聚類

評(píng)估LRS3C在人臉圖像聚類中的性能，其目的是從一組人臉圖像中分割或聚類到不同的個(gè)體。雖然人臉聚類問題并不完全符合我們對(duì)序列數(shù)據(jù)的假設(shè)。但是，可以使用人臉圖像的空間信息，因?yàn)槊總€(gè)數(shù)據(jù)向量的鄰居可能屬于同一類。從擴(kuò)展的YaleB數(shù)據(jù)集[14]中提取數(shù)據(jù)，該數(shù)據(jù)集由38名受試者在不同光照下的大約64張照片組成。圖4提供了數(shù)據(jù)集的圖像樣本示例。對(duì)于每次實(shí)驗(yàn)，從數(shù)據(jù)集中隨機(jī)選擇3名受試者，并在每個(gè)受試者中隨機(jī)排列圖像的序列。在實(shí)驗(yàn)中，將圖像重新采樣到[42×48]形成數(shù)據(jù)向量[Xi∈R2 016]并連接在一起，以確保受試者不會(huì)混合。

在不同的高斯噪聲水平下重復(fù)了50次實(shí)驗(yàn)。各算法聚類結(jié)果如表2所示。

從表2可以看出，在大多數(shù)情況下，LRS3C優(yōu)于其他方法。隨著噪聲強(qiáng)度的增加，算法的精度不斷下降。與其他方法相比，LRS3C方法更穩(wěn)定，表現(xiàn)更可預(yù)測(cè)，尤其是在噪聲較大的情況下。這證明本研究提出的算法在實(shí)際應(yīng)用中更有效。

4? ? 結(jié)論

為了有效地解決序列數(shù)據(jù)的聚類問題，本文提出了利用給定數(shù)據(jù)的低秩表示和稀疏表示的LRS3C方法。該方法根據(jù)序列數(shù)據(jù)的連續(xù)性特點(diǎn)，利用稀疏表示和低秩表示，進(jìn)行子空間聚類。在人工數(shù)據(jù)集和實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與幾種最新的子空間聚類方法相比，本文提出的方法是有效的。

參考文獻(xiàn)：

[1] VIDAL Rene， MA Yi， SASTRY Shankar. Generalized principal component analysis （GPCA）[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2005， 27（12）：15.

[2] LIU Guangcan， LIN Zhouchen， YU Yong. Robust subspace segmentation by low-rank representation[C]//ACM.The 27th International Conference on Machine Learning， June 21-24， 2010， Haifa， Israel： 663-670.

[3] ELHANIFAR Ehan， VIDAL Rene. Sparse subspace clustering[C]//IEEE.2009 IEEE Conference on Computer Vision and Pattern Recognition， June 20-25， 2009， Miami， FL， USA： 2790-2797.

[4] ELHANIFAR Ehsan， VIDAL Rene. Sparse Subspace Clustering： Algorithm， Theory， and Applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（11）：2765-2781.

[5] LIU Guangcan， LIN Zhouchen， YAN Shuicheng. Robust Recovery of Subspace Structures by Low-Rank Representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（1）： 171-184.

[6] FAVARO Paolo， VIDL Rene， RAVICHANDRAN Avinash， et al. A closed form solution to robust subspace estimation and clustering[C]//IEEE. 2011 IEEE Conference on Computer Vision and Pattern Recognition， June 20-25， 2011， Providence， RI， USA：1801-1807.

[7] BOYD Stephen， PARIKH Neal， CHU Eric， et al. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[J]. Foundations & Trends in Machine Learning， 2010， 3（1）：1-126.

[8] GUO Yi， GAO Junbin， LI Feng， et al. Spatial subspace clustering for hyperspectral data segmentation[C]//IEEE.2013 International Conference on Digital Information Processing and Communications， January 30-February 1， 2013， Dubai， UAE： 180-190.

[9] TIERNEY Stephen， GAO Junbin， GUO Yi， et al. Subspace Clustering for Sequential Data[C]//IEEE.2014 IEEE Conference on Computer Vision and Pattern Recognition， June 23-28， Columbus， OH， USA：1019-1026.

[10] WANG Yuxiang， XU Huan， LENG Chenlei. Provable Subspace Clustering： When LRR meets SSC[J].IEEE Transactions on Information Theory， 2019， 65（9）：5406-5432.

[11] FRANCIS Bach， RODOLPHE Jenatton， JULIEN Mairal， et al. Convex optimization with sparsity-inducing norms[J]. In Optimization for Machine Learning， 2011：19-49.

[12] LIU Jun， YE Jieping. Efficient L1/Lq Norm Regularization[J]. Computer Science， 2010 ，arXiv：1009.4766.

[13] SHI Jianbo， MALIK Jitendra. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（8）： 888-905.

[14] GEORGHIADES Athinodoros S， BELHUMEUR Peter N， KRIEGMAN David J. From few to many： illumination cone models for face recognition under variable lighting and pose[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2002， 23（6）：643-660.

責(zé)任編輯? ? 祁秀春