基于鄰域圖的低秩投影學(xué)習(xí)

胡文濤，陳秀宏

江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無(wú)錫 214122

特征提取在模式識(shí)別和計(jì)算機(jī)視覺(jué)等領(lǐng)域發(fā)揮著重要作用[1-3]。經(jīng)典的特征提取算法有主成分分析（Principal Component Analysis，PCA）[4]、局部保持投影（Locality Preserving Projections，LPP）[5]、鄰域保持嵌入（Neighborhood Preserving Embedding，NPE）[6]和稀疏保持投影（Sparsity Preserving Projections，SPP）[7]等，其中PCA是尋找最大方差的投影方向，使得降維之后的低維表示可以保留數(shù)據(jù)的主要信息，而LPP、NPE 和SPP 都是旨在保留數(shù)據(jù)降維之后的局部結(jié)構(gòu)。這些方法也可以看作是基于圖的特征提取算法[8]。

近年來(lái)，低秩表示（Low-Rank Representation，LRR）[9]因其對(duì)含噪數(shù)據(jù)的魯棒性且能保持?jǐn)?shù)據(jù)的整體結(jié)構(gòu)而受到了廣泛的關(guān)注。Liu 等[10]提出的隱式低秩表示（Latent Low-Rank Representation，LatLRR），通過(guò)從矩陣的縱向和橫向處理信息，恢復(fù)出有效的主要信息和隱藏的顯著信息，并取得了較好的實(shí)驗(yàn)效果。但是，LatLRR 并沒(méi)有把兩個(gè)低秩矩陣聯(lián)合學(xué)習(xí)，得到的結(jié)果不是全局最優(yōu)解。為了解決這個(gè)問(wèn)題，Yin 等[11]提出了雙低秩表示算法（Double Low-Rank Representation，DLRR），該算法通過(guò)聯(lián)合學(xué)習(xí)行低秩矩陣和列低秩矩陣來(lái)同時(shí)恢復(fù)數(shù)據(jù)的主要信息和顯著信息。然而，上述的無(wú)監(jiān)督特征提取方法只考慮了數(shù)據(jù)的局部或全局幾何關(guān)系。例如，NPE、LPP和SPP只利用最近鄰樣本的局部幾何關(guān)系，而基于LRR 的特征提取方法只保留了數(shù)據(jù)的全局結(jié)構(gòu)。一般地，全局結(jié)構(gòu)和局部結(jié)構(gòu)都反映了數(shù)據(jù)之間的關(guān)系，對(duì)于不同的數(shù)據(jù)集，僅僅保留一種結(jié)構(gòu)往往無(wú)法獲得良好的性能。Wen 等[12]提出的基于圖正則重構(gòu)的低秩投影學(xué)習(xí)算法（Low-Rank Preserving Projection via Graph Regularized Reconstruction，LRPP_GRR），通過(guò)在重構(gòu)項(xiàng)上施加圖約束來(lái)保持局部結(jié)構(gòu)，但算法沒(méi)考慮數(shù)據(jù)樣本本身含有的噪聲。Fang等[13]提出的增強(qiáng)近似低秩投影學(xué)習(xí)算法（Enhanced Approximate Low-rank Projection Learning，EALPL），使用重構(gòu)矩陣和投影矩陣近似表示LatLRR 算法中的低秩投影矩陣，從而在提取判別特征的同時(shí)有效地降維，但算法沒(méi)有考慮數(shù)據(jù)在重構(gòu)過(guò)程中的殘差，導(dǎo)致存在冗余特征，影響識(shí)別精度。文獻(xiàn)[14]提出的低秩線性嵌入算法（Low-Rank Linear Embedding，LRLE）通過(guò)在線性判別子空間構(gòu)造回歸模型，并在模型中用兩個(gè)矩陣近似地表示低秩系數(shù)矩陣，從而提取更多的判別特征，取得了不錯(cuò)的效果。最后，上述特征提取方法不具有很好的可解釋性，因?yàn)樘崛〉奶卣魇撬性继卣鞯暮?jiǎn)單線性組合，如PCA、LPP、SPP 等，這些方法提取出的特征沒(méi)有區(qū)分度，因此很難得到有鑒別性的特征；而且它們提取了許多包含離群點(diǎn)和噪聲的特征，這與特征提取的目的自相矛盾，因?yàn)樘卣魈崛〉哪康氖翘崛∮杏玫?、有判別性的特征。

為了解決以上述問(wèn)題，本文提出一種基于鄰域圖的低秩投影學(xué)習(xí)算法（Low-Rank Projection Learning based on Neighbor Graph，NGLRPL），首先在聯(lián)合低秩矩陣的重構(gòu)殘差項(xiàng)上施加圖約束，這樣就能同時(shí)保持?jǐn)?shù)據(jù)的局部結(jié)構(gòu)和整體結(jié)構(gòu)，從而保證算法能得到全局最優(yōu)值投影矩陣；其次，在算法模型中約束數(shù)據(jù)樣本存在的噪聲，同時(shí)利用L2，1范數(shù)獲得行稀疏的投影矩陣，提高投影矩陣的可解釋性；最后，模型通過(guò)交替迭代方法求解，并在多個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，說(shuō)明了算法的有效性。

1 相關(guān)工作

假設(shè)給定訓(xùn)練樣本矩陣X∈Rm×n，其中，每個(gè)列向量xi(i=1,2,…,n)為一個(gè)樣本，m為樣本的維數(shù)，n為訓(xùn)練樣本的個(gè)數(shù)。

1.1 基于低秩表示的特征提取

基于數(shù)據(jù)近似地從多個(gè)獨(dú)立的聯(lián)合子空間中提取的假設(shè)，LRR尋找數(shù)據(jù)集在過(guò)完備字典集上的最低秩表示，其模型如下：

式中，||Z||*是矩陣Z的核范數(shù)，即矩陣Z所有奇異值之和。系數(shù)矩陣Z中的每個(gè)元素zij表示了樣本xi和xj之間的“相似性”。針對(duì)模型（1）沒(méi)有學(xué)習(xí)用于特征提取的投影矩陣且沒(méi)有考慮樣本中含有的噪聲，Liu 等進(jìn)一步提出了以下LatLRR模型：

式中，E∈Rm×n是樣本中的噪聲矩陣，并對(duì)其施加了稀疏約束；L∈Rm×m是投影矩陣，能夠提取數(shù)據(jù)圖像的顯著特征。然而，LatLRR 提取的特征不能保留數(shù)據(jù)的全局結(jié)構(gòu)和主要信息。為了得到更具魯棒性的投影，Yin等[11]提出了雙低秩表示模型（DLRR）：

在這個(gè)算法中，學(xué)習(xí)到的投影矩陣L能夠同時(shí)保存數(shù)據(jù)的主要信息和全局結(jié)構(gòu)。上述算法很好的保持了數(shù)據(jù)樣本的整體機(jī)構(gòu)，但是卻忽視了數(shù)據(jù)樣本的局部結(jié)構(gòu)。

1.2 基于鄰域圖的流形學(xué)習(xí)

鄰域圖可以保持?jǐn)?shù)據(jù)的局部幾何結(jié)構(gòu)。對(duì)于一個(gè)含n個(gè)樣本的數(shù)據(jù)矩陣X=[x1,x2,…,xn] ∈Rm×n，基于鄰域圖的流形學(xué)習(xí)方法，首先要構(gòu)造一個(gè)鄰域圖W來(lái)表示樣本的局部關(guān)系，然后通過(guò)求解以下優(yōu)化問(wèn)題進(jìn)行投影學(xué)習(xí)：

式中，P是投影矩陣；圖矩陣W中每個(gè)元素wij定義為：

式中，Nk(xj)表示距離樣本xj最近的k個(gè)樣本的集合，wij=1 表示樣本xi是樣本xj的近鄰。

2 基于鄰域圖的低秩投影學(xué)習(xí)

DLRR算法只考慮了數(shù)據(jù)樣本的整體結(jié)構(gòu)，且提取的投影矩陣只是原始特征的線性組合，沒(méi)有很好的可解釋性，而且沒(méi)有對(duì)數(shù)據(jù)樣本進(jìn)行降維。為此，本文提出以下基于鄰域圖的低秩投影學(xué)習(xí)：

式中，Q∈Rm×d表示投影矩陣，P∈Rm×d表示重構(gòu)矩陣，d(d ＜m)是降維后特征的維數(shù)。QTX是算法提取的特征子空間，其維數(shù)d是可變的。目標(biāo)函數(shù)中第一項(xiàng)表示如果樣本xi和xj互為近鄰，那么樣本xi和重構(gòu)樣本PQTXzj也應(yīng)該彼此互為近鄰[12]，這樣既描述了數(shù)據(jù)樣本和重構(gòu)數(shù)據(jù)之間的殘差，又考慮了數(shù)據(jù)的局部結(jié)構(gòu)；第二項(xiàng)利用L2，1范數(shù)的行稀疏性質(zhì)來(lái)剔除冗余特征，以便提取顯著特征，提高投影矩陣的可解釋性；第三項(xiàng)用來(lái)保證噪聲矩陣是稀疏的；第四項(xiàng)用來(lái)保證最終得到的系數(shù)矩陣是低秩的，從而保留數(shù)據(jù)樣本的全局結(jié)構(gòu)。λ1、λ2和λ3是正則化參數(shù)。對(duì)矩陣P施加正交約束得到，避免式（6）出現(xiàn)平凡解。

模型（6）可使用交替方向乘子法[15]求解。首先，為了使模型（6）可分，引入兩個(gè)輔助變量Y和U：

該問(wèn)題的增廣Langrange函數(shù)可以定義為：

式中，D=diag(D11,D22,…,Dnn) 是一個(gè)對(duì)角矩陣，且Dii=，C1、C2、C3是Langrange乘子矩陣，μ是懲罰參數(shù)。于是，得到以下交替法求解方法。當(dāng)P、Q、E、Z、U固定時(shí)求Y。公式（8）可變?yōu)椋?/p>

關(guān)于Y求偏導(dǎo)并令其結(jié)果為0可得：

當(dāng)P、Q、E、Z、Y固定而求U時(shí)可得以下問(wèn)題：

此時(shí)，可通過(guò)奇異值閾值算子（Singular Value Thresholding operator，SVT）[16]得到解U。設(shè)矩陣的奇異值分解為：

式中，B和V均為列正交的矩陣，∑=diag(σ1,σ2,…,σr)，σ1,σ2,…,σr是奇異值且均為正數(shù)，則式（10）的解為：

當(dāng)P,Q,E,U,Y固定而求Z時(shí)，公式（8）可變?yōu)椋?/p>

關(guān)于Z求導(dǎo)并令其為0可得：

當(dāng)P,U,Y,E,Z固定而求Q時(shí)，公式（8）變?yōu)椋?/p>

關(guān)于Q求導(dǎo)并令其結(jié)果為0可得：

當(dāng)P、U、Q、Y、Z固定而求E時(shí)，得以下問(wèn)題：

由文獻(xiàn)[17]可知該問(wèn)題的解為：

當(dāng)Z、U、Q、Y、E固定而求P時(shí)，公式（8）轉(zhuǎn)化為以下問(wèn)題：

目標(biāo)函數(shù)關(guān)于P求偏導(dǎo)并令其結(jié)果為0得：

最后，Langrange乘子矩陣C1、C2、C3和懲罰參數(shù)μ的迭代規(guī)則如下：

式中，ρ和μmax都是常數(shù)。為了提高算法速度，本文實(shí)驗(yàn)首先通過(guò)PCA 初始化正交矩陣P，實(shí)驗(yàn)判定收斂的條件為迭代中最近兩次目標(biāo)函數(shù)值差值的絕對(duì)值小于0.000 1。綜上所述，本文NGLRPL算法步驟如下：

算法NGLRPL

輸入：數(shù)據(jù)集X，維數(shù)d，參數(shù)λ1、λ2和λ3

初始化：通過(guò)PCA 初始化正交矩陣P，Q=P，Z=W，U=Z，Y=QTXZ，C1=C2=C3=0，μ=0.1，ρ=1.01，μmax=105

while no convergence do

1. 通過(guò)（10）更新矩陣Y

2. 通過(guò)（13）更新矩陣U

3. 通過(guò)（15）更新矩陣Z

4. 通過(guò)（17）更新矩陣Q

5. 通過(guò)（19）更新矩陣E

6. 通過(guò)（22）更新矩陣P

7. 通過(guò)（23）、（24）、（25）、（26）更新矩陣C1、C2、C3和μ

end while；

輸出：投影矩陣Q

在算法迭代結(jié)束得到投影矩陣Q后，對(duì)測(cè)試樣本進(jìn)行降維。對(duì)于降維之后的測(cè)試樣本點(diǎn)，選擇距離該測(cè)試樣本點(diǎn)距離最小的訓(xùn)練樣本點(diǎn)標(biāo)簽作為類(lèi)別標(biāo)簽，直至所有測(cè)試樣本點(diǎn)完成分類(lèi)。

本文算法計(jì)算復(fù)雜度主要在矩陣求逆和矩陣SVD分解，暫不考慮矩陣乘法和加法的計(jì)算復(fù)雜度。對(duì)于m×m的矩陣，其求逆的計(jì)算復(fù)雜度為O(m3)。對(duì)于m×n的矩陣，其進(jìn)行SVD 分解的復(fù)雜度為O(mn2)。在上述算法中，計(jì)算復(fù)雜度最高的是在求Y、U、Z和Q上，分別為O(n3)、O(mn2)、O(n3)和O(m3)。所以，本文算法總的復(fù)雜度是O(τ(2n3+m3+mn2))，其中τ為最大迭代次數(shù)。

3 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)的硬件環(huán)境為Windows 10，Intel Core i5 3.3 GHz CPU，內(nèi)存為8 GB，編程軟件使用的是Matlab 2016a。為了驗(yàn)證本文算法的性能，分別在數(shù)據(jù)集COIL20、BioID和AR數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并將結(jié)果分別與EALPL、LRPP_GRR、LRLE、LatLRR和LPP等方法進(jìn)行比較。實(shí)驗(yàn)中首先將數(shù)據(jù)集圖像裁剪成大小的灰度圖，然后將這些灰度圖重構(gòu)為1 024維的向量，并做歸一化處理而構(gòu)成實(shí)驗(yàn)用的數(shù)據(jù)矩陣。所有實(shí)驗(yàn)均獨(dú)立隨機(jī)運(yùn)行了20次，對(duì)其平均最佳識(shí)別率進(jìn)行比較。

3.1 數(shù)據(jù)集

BioID（https：//www.bioid.com/facedb/）人臉數(shù)據(jù)集包含來(lái)自23個(gè)測(cè)試人員的1 521幅灰度圖像，這些圖像分別是在不同的光照，姿態(tài)和表情變化的情況下采集的。

COIL20（http：//www.cs.columbia.edu/CAVE/software/softlib/coil-20.php）數(shù)據(jù)集包含20 個(gè)物品的1 440 個(gè)圖像，每個(gè)物品姿勢(shì)間隔5度采集了72張圖像。

AR人臉庫(kù)包含來(lái)自126人的4 000多幅人臉圖像，包含56個(gè)女性和70個(gè)男性。每一個(gè)人的人臉圖像包含了表情變化、光照變化和遮擋變化（戴墨鏡和圍巾）等干擾。實(shí)驗(yàn)時(shí)隨機(jī)選取120人，每人26幅圖像。數(shù)據(jù)集部分圖像如圖1所示。

3.2 正則化參數(shù)對(duì)實(shí)驗(yàn)的影響

本節(jié)進(jìn)行算法的收斂性實(shí)驗(yàn)和討論正則化參數(shù)λ1、λ2和λ3對(duì)識(shí)別率的影響，分別在BioID、COIL20 和AR 人臉庫(kù)這3 個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，每個(gè)類(lèi)別分別選取21、20和16張作為訓(xùn)練集，其余的圖像用作測(cè)試集。

如圖2 是在COIL20 和AR 人臉庫(kù)上正則參數(shù)與平均識(shí)別率的關(guān)系圖。λ2控制噪聲的稀疏度，在AR 和COIL20 數(shù)據(jù)集上取10-4，在BioID 數(shù)據(jù)集上取10?5。對(duì)正則化參數(shù)λ1和λ3取值設(shè)置在[10?6，100]。本文算法在COIL20、AR、BioID 數(shù)據(jù)集上當(dāng)λ1分別取值在10?4、10?5、10?6，λ3分別取值在100、100、1時(shí)，識(shí)別效果達(dá)到最佳狀態(tài)。當(dāng)識(shí)別率達(dá)到最高時(shí)，λ3數(shù)值比較大，說(shuō)明在這3 個(gè)數(shù)據(jù)集上保持整體結(jié)構(gòu)的低秩矩陣對(duì)本文算法性能起比較大的作用。

3.3 特征維數(shù)對(duì)實(shí)驗(yàn)的影響

為了驗(yàn)證特征維數(shù)對(duì)于實(shí)驗(yàn)的影響，本節(jié)通過(guò)比較在不同維度下算法的識(shí)別效率來(lái)驗(yàn)證特征維數(shù)對(duì)實(shí)驗(yàn)的影響。在AR、COIL20 和BioID 數(shù)據(jù)集上分別選取16、20、21個(gè)圖像作為訓(xùn)練樣本。

圖1 數(shù)據(jù)集的部分圖像

圖2 正則化參數(shù)與平均識(shí)別率的關(guān)系圖

圖3 特征維數(shù)與平均識(shí)別率的關(guān)系圖

如圖3 是在各數(shù)據(jù)集上特征維數(shù)與平均識(shí)別率的關(guān)系圖（由于LatLRR并未對(duì)數(shù)據(jù)降維，故圖3并未列出LatLRR的曲線，每個(gè)數(shù)據(jù)集都是從10維開(kāi)始），本文算法在低維時(shí)識(shí)別率較其他算法偏低，但是從80 維左右開(kāi)始是所有算法中最高的，這是由于在低維時(shí)許多具有判別性的特征沒(méi)有提取出來(lái)，導(dǎo)致識(shí)別率偏低。當(dāng)維度升高時(shí)，由于L2，1具有行稀疏的性質(zhì)，可以剔除許多不具有判別性的特征和噪聲。同時(shí)，由于存在對(duì)系數(shù)矩陣的低秩約束，可以很好地剔除離散點(diǎn)的干擾。從圖3還可以看出LPP 算法對(duì)于維數(shù)比較敏感，而本文算法從100維開(kāi)始的識(shí)別率相對(duì)穩(wěn)定。

3.4 訓(xùn)練樣本數(shù)對(duì)識(shí)別精度的影響

本節(jié)討論了在各數(shù)據(jù)集上訓(xùn)練樣本數(shù)對(duì)識(shí)別精度的影響。在AR 和BioID 數(shù)據(jù)集上維數(shù)設(shè)置為200，在COIL20數(shù)據(jù)集上維數(shù)設(shè)置為180。表1至表3給出了本文算法和對(duì)比算法在不同訓(xùn)練樣本數(shù)下的識(shí)別精度。

在不同訓(xùn)練樣本數(shù)目下，NGLRPL算法均優(yōu)于其他5種算法且隨著訓(xùn)練樣本數(shù)的增加識(shí)別率也相應(yīng)增加。NGLRPL 算法識(shí)別率比LRPP_GRR 高是因?yàn)長(zhǎng)RPP_GRR 算法并未考慮到數(shù)據(jù)的樣本本身存在的噪聲的影響（如AR數(shù)據(jù)集中墨鏡和圍巾），使得在學(xué)習(xí)投影過(guò)程中不能較好地提取具有判別性的特征。EALPL算法的識(shí)別率比NGLRPL算法低，是由于其并未考慮算法在投影和重構(gòu)過(guò)程中產(chǎn)生的殘差，約束殘差可使得在學(xué)習(xí)投影的過(guò)程中剔除冗余特征。NGLRPL 算法比LatLRR、LPP 和LRLE 算法的識(shí)別率高，是因?yàn)長(zhǎng)atLRR算法和LPP 算法只單獨(dú)考慮了數(shù)據(jù)的整體結(jié)構(gòu)或者局部結(jié)構(gòu)而NGLRPL算法同時(shí)考慮兩種結(jié)構(gòu)，從而減小離散值的影響。同時(shí)，LRLE 算法盡管同時(shí)考慮了整體結(jié)構(gòu)和局部結(jié)構(gòu)，但是其并未對(duì)投影矩陣進(jìn)行稀疏約束導(dǎo)致其不能有效提取出顯著的特征。

表4 列出了各算法在COIL20 和BioID 上用不同訓(xùn)練樣本數(shù)所消耗的時(shí)間，除LPP 算法用時(shí)明顯較少，本文算法在大部分情況下計(jì)算時(shí)間小于其他4種算法，這得益于本文算法具有較好的收斂性，在數(shù)次迭代之后能快速收斂。

表1 AR人臉庫(kù)上各算法的平均識(shí)別率 %

表2 COIL20數(shù)據(jù)集上各算法的平均識(shí)別率%

表3 BioID人臉庫(kù)上各算法的平均識(shí)別率 %

表4 COIL20數(shù)據(jù)集和BioID人臉庫(kù)上算法所消耗的時(shí)間 s

4 結(jié)論

本文提出了一種基于鄰域圖的低秩投影無(wú)監(jiān)督學(xué)習(xí)算法，通過(guò)把鄰域圖和聯(lián)合低秩系數(shù)矩陣的數(shù)據(jù)重構(gòu)殘差相結(jié)合使算法在學(xué)習(xí)投影的過(guò)程中同時(shí)保持?jǐn)?shù)據(jù)的局部結(jié)構(gòu)和整體結(jié)構(gòu)。同時(shí)，對(duì)投影矩陣施加L2，1范數(shù)正則化的稀疏約束，以便能提取更具有判別性的特征。在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文算法取得了比其他算法更好的識(shí)別精度。本文提出的算法復(fù)雜度相對(duì)較高，在實(shí)際應(yīng)用中如何降低復(fù)雜度值得進(jìn)一步研究。