張燕

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

近年來，子空間分割在圖像表示、計算機視覺和一些其他相關(guān)的領(lǐng)域起著非常重要的作用。所謂子空間分割，就是把數(shù)據(jù)樣本劃分到他們所屬的類別中。在目前的研究中[1-11],[20]，常用的子空間分割方法有：代數(shù)法[1]、迭代法[2]、統(tǒng)計法[3]和基于譜聚類的方法[4-11]。其中，譜聚類的方法在實際的應(yīng)用中取得了極大的成功。

一般來說，可以將基于譜聚類子空間分割算法分成兩大步驟：1）通過所給的數(shù)據(jù)集，利用相關(guān)算法計算得到相似矩陣；2）根據(jù)得到相似矩陣，利用相關(guān)譜聚類算法得到分割結(jié)果（常用的分割算法有Ncut[12]）。根據(jù)現(xiàn)有研究可以發(fā)現(xiàn)，在子空間分割任務(wù)中，相似矩陣的好壞直接影響著最后的分割結(jié)果。

目前，對于如何獲取相似矩陣的研究主要集中在自我表示模型上。自我表示模型的主要思想是指每個數(shù)據(jù)樣本可以被來自同一類數(shù)據(jù)集中的其他樣本線性表示。在此基礎(chǔ)上，Elhamifar等人首次提出了稀疏子空間分割算法（SSC）[13],該算法通過最小化l1范數(shù)[14]來計算每個數(shù)據(jù)樣本的系數(shù)矩陣，然后通過集中重構(gòu)系數(shù)矩陣向量得到系數(shù)相似矩陣。SSC旨在獲取每個數(shù)據(jù)樣本的最稀疏表示，但是該算法卻忽略了最終解的全局約束。為了解決有損數(shù)據(jù)的全局約束問題，Liu等人提出了低秩表示算法（LRR）[15]來獲取所有樣本的重構(gòu)系數(shù)矩陣，該算法通過最小化矩陣的核范數(shù)[16]來實現(xiàn)系數(shù)矩陣的最小秩的要求。相關(guān)實驗表明，最小核范數(shù)約束能夠更好地發(fā)掘有損數(shù)據(jù)的全局結(jié)構(gòu)。所以，在有損數(shù)據(jù)的子空間分割問題上，LRR的性能比SCC要好得多。

LRR在獲取相似矩陣上取得的成功也促使很多學(xué)者也在此基礎(chǔ)上做了很多相關(guān)的后續(xù)研究。例如，Chen等人[17]提出的用來獲取高維數(shù)據(jù)集的子空間結(jié)構(gòu)的對稱低秩表示算法；Zhuang等人[18]提出的從非線性流形混合數(shù)據(jù)集中獲取非直接的相似矩陣的局部低秩表示算法；Zhang等人[19]提出的通過一個有監(jiān)督的學(xué)習(xí)方法創(chuàng)建一個判別重構(gòu)字典的結(jié)構(gòu)化低秩表示算法；Wei等人也相繼提出了自我正則固定秩分割算法[20]和譜聚類指導(dǎo)低秩分割算法[21]。Zhuang等人[22]提出的一種將非負和稀疏約束結(jié)合應(yīng)用在LRR算法中的非負低秩稀疏表示（NNLRSR）。相關(guān)的實驗表明上述算法在不同的數(shù)據(jù)集的子空間分割應(yīng)用中都能夠獲得不錯的效果。

然而，傳統(tǒng)的LRR算法僅適用于子空間完全獨立的狀態(tài)。我們知道，在實際應(yīng)用中，子空間完全獨立的是一種非常特殊的情況。因此，Tang等人[23]提出了結(jié)構(gòu)化約束低秩表示算法（SCLRR）來改進LRR在不相交數(shù)據(jù)集中的應(yīng)用，該算法通過在LRR的目標函數(shù)中加入一個正則項來獲取數(shù)據(jù)集的結(jié)構(gòu)信息。事實證明該方法對于多重不相交子空間分割是非常有效的。而且在SCLRR的基礎(chǔ)上，Liu等人[24]提出了將低秩約束和結(jié)構(gòu)信息相結(jié)合于系數(shù)矩陣的結(jié)構(gòu)低秩字典學(xué)習(xí)算法；Wu等人[25]也提出了CS-LRR來獲取最佳譜聚類；前面提到的Wei等人[21]提出的SCSLRR算法也可以看作是SCLRR算法的拓展。以上的算法都表明，SCLRR是一個切實有效并得到廣泛認可的結(jié)構(gòu)化LRR算法。

對于SCLRR，新引入的正則項帶來了一個新的調(diào)節(jié)參數(shù)，并且該參數(shù)對算法的正確率有著直接的影響。但是我們知道，原始的LRR已經(jīng)有了一個調(diào)節(jié)殘差項的參數(shù)，因此，SCLRR算法變成了很難調(diào)節(jié)的雙參數(shù)問題。而且在SCLRR基礎(chǔ)上提出的其他算法[21],[24-25]也不可避免引入了新的參數(shù)。如圖1所示。

圖1 當參數(shù)λ固定時算法SCLRR對參數(shù)β的敏感度

我們給出了在數(shù)據(jù)集Fashion-MINIST[29]上的一個簡單測試來觀察算法SCLRR對參數(shù)β的敏感度。我們可以發(fā)現(xiàn)，算法SCLRR的性能隨著β的變化而發(fā)生很大的變化。因此，我們嘗試去尋找一種新的方式來在LRR中引入數(shù)據(jù)集的結(jié)構(gòu)化信息。在本文中，我們提出了一種改善的結(jié)構(gòu)化低秩表示算法ISLRR。在ISLRR中，我們將數(shù)據(jù)集的結(jié)構(gòu)化信息引入到LRR的等式約束的系數(shù)矩陣中，從而得到一個結(jié)構(gòu)化的系數(shù)字典來計算獲得結(jié)構(gòu)化的低秩解。相關(guān)的實驗表明，本文所提出的ISLRR在處理不相交數(shù)據(jù)集的子空間分割問題上簡易有效。

1 相關(guān)算法介紹

在本節(jié)中，我們對算法LRR和SCLRR進行簡要的介紹。

1.1 LRR算法

假設(shè)一組數(shù)據(jù) X=[x1,x2,...,xn]∈Rd×n，其中 d 是每個數(shù)據(jù)樣本的維度，n是所有數(shù)據(jù)樣本的數(shù)量。由于每個樣本能被來自相同子空間的其他樣本線性表示，我們可以將自我表達模型定義如下：

其中，A = [a1,a2,…,am]∈Rd×m是字典，Z 是系數(shù)表示矩陣。在LRR中，我們將數(shù)據(jù)集X本身作為數(shù)據(jù)字典，則模型可以寫為如下：

然而，在實際應(yīng)用中，數(shù)據(jù)點一般都是充滿噪聲或是受損的。而且我們知道，核范數(shù)可以用來實現(xiàn)低秩約束，所以考慮到這些因素，可以將標函數(shù)改寫如下：

我們可以ALM算法來解決公式（3）的最優(yōu)解問題。一旦求得了Z，定義G=[Z+ZT]/2作為相似矩陣并使用Ncut[12]算法獲取最后的分割結(jié)果。

1.2 SCLRR算法

我們知道，LRR算法只能在子空間完全獨立的情況下才能取得很好的效果。然而，獨立子空間在不相交子空間問題中是一種特殊的情況。為了改善LRR在不相交子空間分割中的應(yīng)用，SCLRR算法在LRR的目標函數(shù)中引入權(quán)值系數(shù)矩陣來改善其解的結(jié)構(gòu)。通過這種方式，秩的懲罰項將會比只考慮核范數(shù)的情況要小的多，也就是說，該種方式能夠很好地改善解的結(jié)構(gòu)?？紤]到噪聲等情況，SCLRR的目標函數(shù)定義如下：

其中⊙叫作Hadamard積[22],β和λ是兩個平衡參數(shù)。如果有兩個相同大小m×n的矩陣，則Hadamard積表示如下：

相關(guān)的實驗表明，SCLRR比LRR更能發(fā)掘不同數(shù)據(jù)集的子空間結(jié)構(gòu)。

2 改良的結(jié)構(gòu)化LRR算法

在本節(jié)中，我們提出了一種改良的結(jié)構(gòu)化LRR算法并將其命名為ISLRR，并給出了算法的一般求解步驟。

2.1 算法提出動機

從文獻[10]、[23]中我們得到，LRR得到的解的結(jié)構(gòu)直接影響著最后的分割結(jié)果。根據(jù)LRR在獨立子空間問題中的解的結(jié)構(gòu)中發(fā)現(xiàn)，我們希望得到的塊對角結(jié)構(gòu)的解能夠準確揭露類內(nèi)數(shù)據(jù)樣本之間較強的關(guān)系和類間數(shù)據(jù)樣本之間較弱的關(guān)系。

并且我們知道，LRR在處理不相交子空間情況下的能力是比較弱的。為了改善LRR的相關(guān)性能，我們需要找到一種能夠準確地將得到的解進行結(jié)構(gòu)化的方法。而且在LRR算法中引入結(jié)構(gòu)特征的目的也是希望能夠獲得一個能夠用于不相交子空間問題中的塊對角矩陣。從對SCLRR的介紹中，我們知道SCLRR算法比LRR更能準確地揭露不相交數(shù)據(jù)集的子空間結(jié)構(gòu)，但是該算法卻引入了額外的參數(shù)β來增加了算法的調(diào)節(jié)難度。

因此，我們希望能夠有一個不引入新的參數(shù)但是卻能準確獲取到數(shù)據(jù)集的結(jié)構(gòu)信息的方法。在LRR[7][8]中，我們知道系數(shù)矩陣Z用來表示數(shù)據(jù)集的內(nèi)部結(jié)構(gòu)。在SCLRR的描述中，權(quán)值矩陣M可以準確揭露數(shù)據(jù)樣本之間的關(guān)系。我們假設(shè)能夠在一組數(shù)據(jù)集X=[x1,x2,...,xn]∈Rd×n中獲得權(quán)值矩陣 M ，那我們可以得到一個新的結(jié)構(gòu)化系數(shù)矩陣M⊙Z來反映數(shù)據(jù)集的結(jié)構(gòu)信息。不同于SCLRR的是，我們將該結(jié)構(gòu)化的系數(shù)矩陣應(yīng)用于LRR的等式約束項中，從而形成一個新的結(jié)構(gòu)化公式來準確表示每個數(shù)據(jù)樣本，并最終得到一個結(jié)構(gòu)化的低秩解用于子空間分割。綜上，考慮到噪聲等原因，我們將ISLRR的目標函數(shù)表示如下：

很明顯，當我們把M的所有元素設(shè)置為1時，我們可以將ISLRR轉(zhuǎn)化為LRR。也就是說，我們可以將LRR考慮為ISLRR的一種特殊情況。當?shù)玫浇Y(jié)構(gòu)化的低秩解Z，我們定義G=(Z+ZT)/2坐為相似矩陣并用于最后的子空間分割。

一般來說，我們期望權(quán)值矩陣M的元素取值情況是類間樣本的權(quán)值盡可能小而類內(nèi)樣本的權(quán)值盡可能大。根據(jù)文獻[23]，本文也將權(quán)值矩陣M定義如下：

2.2 最優(yōu)化相關(guān)解及算法步驟

為了獲取問題（6）的最優(yōu)化解，我們引入兩個輔助參數(shù)J和T在目標函數(shù)中，并將公式（6）表示如下：

則公式（8）的增廣拉格朗日函數(shù)可以表示如下：

其中Ya,Yb和Yc是拉格朗日乘子，μ＞0是一個參數(shù)。我們可以通過一個迭代算法來最優(yōu)化以上未知項。

然后我們可以得到Z, J, T, E的每次更新如下：

其中，μmax和ρ是兩個調(diào)節(jié)參數(shù)，t是迭代次數(shù)。根據(jù)以上描述，算法ISLRR的基本步驟可以總結(jié)如下（通過計算得到低秩矩陣Z,得到相似矩陣G=(Z+ZT)/2,再通過Ncut切割算法得到最后的分割結(jié)果）：

算法1：ISLRR

輸入：數(shù)據(jù)集X,參數(shù)λ,權(quán)值矩陣M,最大迭代次數(shù)Maxiter.

輸出：系數(shù)矩陣T,低秩矩陣Z和噪聲矩陣。

1.初始化參數(shù)：

2.while||X-XT-E||∞＞ ε,||Z-J||∞＞ εand t＜Maxiter.執(zhí)行

3.更新錯誤!不能通過編輯域代碼創(chuàng)建對象。根據(jù)公式.(14)-1,2,3,4

5.t=t+1;

6.end while

7.return系數(shù)矩陣T=Tt,低秩矩陣Z=Zt,噪聲矩陣E=Et

3 實驗結(jié)果

為了驗證ISLRR算法的可行性和算法效果，我們采取一些常用的人臉數(shù)據(jù)集：Extended Yale B[27]和AR[28]和圖像數(shù)據(jù)集Fashion_MNIST[29]來驗證我們的算法。并且，我們也選用幾個經(jīng)典的子空間分割算法SSC[4],LRR[7-8]和SCLRR[23]來進行對比試驗。

本次實驗的硬件配置是環(huán)境是Intel Core i5-6500 3.20GHz處理器，4GB運行內(nèi)存，500G的硬盤內(nèi)存。軟件環(huán)境是64位Windows 7 Professional操作系統(tǒng)，MATLAB R2014a。

下面，我們將對實驗中3個數(shù)據(jù)集進行簡單的介紹：

Fashion-MNIST數(shù)據(jù)集是一個商品數(shù)據(jù)集，一共包含60000個訓(xùn)練樣本和10000個測試樣本。它們被分為十個大類，分別是：T恤、褲子、連衣裙、外套、襯衫、運動鞋、涼鞋、包和短靴。在本次實驗中，我們選取訓(xùn)練集中每個類別的前50張照片作為實驗數(shù)據(jù)集，每張照片的大小為20×20。Fashion-MNIST樣本圖片如圖2（a）。

圖2 靜態(tài)圖像樣本

Extended Yale B人臉數(shù)據(jù)集包含38個不同的對象一共2414張圖像，每個成員對象有9個不同的姿勢，每個姿勢有64個不同的灰度級。并且，這些圖像還擁有不同命的光照環(huán)境和人臉表情。在本次實驗中，我們將每張照片裁剪成32×32大小，樣本圖片見圖2（b）。

AR人臉數(shù)據(jù)集擁有126個對象超過4000張的圖片。每個對象擁有2模式26張圖片，也就是說，每個模式又15張圖片。這些圖片都是在不同的視角和光照條件下拍攝而成的。在本次實驗中，我們選取每個成員對象的前120張照片（一共2000張）作為實驗數(shù)據(jù)集，我們將每張圖片的大小裁剪為50×40。樣本圖片見圖 2（c）。

圖3 不同的算法在不同的數(shù)據(jù)集上隨著分類數(shù)量變化準確率的變化和其他算法的對比

為了驗證算法的有效性和可行性，本文將ISLRR算法與SSC、LRR和SCLRR幾個經(jīng)典的子空間分割算法進行對比試驗。

我們針對每個數(shù)據(jù)集選取不同數(shù)量的類別進行實驗。在實驗中，我們選取q類（q的值選取范圍為3～數(shù)據(jù)樣本的類別總量）來計算相應(yīng)的準確率。參數(shù)β的選取范圍為[0.001,20]，參數(shù)λ的設(shè)置范圍為[0.0001,50]，相應(yīng)的最佳值如圖3所示。

從圖3可以看出：1）隨著數(shù)據(jù)集類別數(shù)量的增加，所有算法的準確率都在下降；2）對于人臉數(shù)據(jù)集Extended Yale B，相對于其他幾個算法，ISLRR算法在大部分情況下能夠取得相對比較好的結(jié)果。

以上表明，ISLRR算法在一定的情況下用于的圖像的子空間分割上能夠取得不錯的結(jié)果，也就是說，ISLRR在不相交子空間的分割應(yīng)用中是一個有效的子空間分割算法。

4 結(jié)語

本文提出了一種新的子空間分割算法ISLRR，在ISLRR中，我們將數(shù)據(jù)集的結(jié)構(gòu)信息引入到LRR的等式約束項中來改善解得的結(jié)構(gòu)。對比SCLRR算法，ISLRR避免了帶來新的參數(shù)，也就是說，該算法解決了SCLRR中調(diào)節(jié)雙參數(shù)的困難。為了證實算法的有效性，我們用了三個相關(guān)的算法在四個常用的圖像數(shù)據(jù)庫上進行對比實驗。最后的實驗結(jié)果表明，ISLRR算法在解決不相交的子空間分割問題是簡單可行的。