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

由從哲 舒振球 范洪輝

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

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

中圖分類號：TP391.4? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? 文獻標識碼：2095-7394（2020）04-0078-08

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

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

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

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

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

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

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

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

3? ? 實驗

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

使用子空間聚類誤差，

作為聚類算法性能的評價指標。

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

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

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

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

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

3.2? ?視頻場景分割

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

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

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

3.3? 人臉聚類

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

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

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

4? ? 結(jié)論

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

參考文獻：

[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.

責任編輯? ? 祁秀春