基于L1范數的二維鑒別局部保留投影的最大間距準則方法

謝玉凱，盧桂馥，宣東東

(安徽工程大學計算機與信息學院，安徽 蕪湖 241000)

基于L1范數的二維鑒別局部保留投影的最大間距準則方法

謝玉凱，盧桂馥，宣東東

(安徽工程大學計算機與信息學院，安徽 蕪湖 241000)

為避免基于L1范數的鑒別局部保留投影(DLPP-L1)方法中圖像數據向量化引起的矩陣計算的不穩定問題，提出了一種基于L1范數的二維鑒別局部保留投影的最大間距準則方法(2DDLPP-L1/MMC),目的是尋找一組最優投影向量使得投影變換后特征空間的類間離散度最大而類內離散度最小。2DDLPP-L1/MMC方法直接基于圖像矩陣并且利用了L1范數對野值處理的穩健性以及最大間距準則所具有的優勢，降低了計算量。人臉數據庫上的試驗結果表明，該方法具有較強的魯棒性和較高的識別率。

鑒別局部保留投影；L1范數；最大間距準則；魯棒性

在模式識別和機器學習領域中，數據中包含了很多的屬性和特征，使得數據都是以高維形式存在的，導致維數災難困擾著多種模式識別技術的應用和研究。為了解決高維數據面臨的一系列問題并使后續的數據應用的更加穩健，就需要對高維數據進行降維。目前最常用的2種降維方法是主成分分析(PCA)[1,2]和線性判別分析(LDA)[3,4]。PCA通過找尋一組最佳的正交投影向量，使投影后的數據方差最大化從而盡可能多的存儲可分性信息。然而，傳統的PCA忽略了類別屬性，重要的可分性信息也許包含在被忽略的投影方向中。LDA作為一種有監督的學習方法利用了該類別屬性，該方法的最佳投影方向是通過求解Fisher準則函數最大化而獲得，使得原始樣本向這組向量投影后的特征空間的類內離散度最小，類間離散度最大。然而，LDA總是遭遇小樣本問題，這主要是特征空間的維數高于訓練樣本的總數，繼而導致類內協方差矩陣的奇異性和不穩定性問題。

最近，He和Niyogi提出了一種新的特征提取方法，即局部保留投影(LPP)[5]。LPP是Laplacian Eigemap的一個線性投影方法，其本質是通過一個線性投影，盡可能的保持原始樣本數據在高維空間里的局部幾何結構以獲得良好的低維可視化效果。但是LPP不能利用訓練數據中的判別屬性。為此，文獻[6]提出了一種鑒別局部保留投影方法(Discriminant Locality Preserving Projection,DLPP),它通過在LPP中增加判別信息來充分利用類別信息。

從統計的角度來看，相比于L2范數，L1范數對野值更具魯棒性，因為L1范數中的絕對值操作減輕了對野值的影響。基于此，基于L1范數的相關方法開始被提出來，如基于L1范數的PCA[7,8]，基于L1范數的LDA[9,10]。PCA-L1實際上是將PCA模型中的L2范數改為L1范數來進行求解，其局部最優投影向量通過對特征空間中的基于L1范數的方差實現最大化求解而得到，但是PCA-L1計算較為復雜并且樣本數據中的類別屬性沒有得到運用。LDA-L1是將LDA模型中的L2范數改為L1范數來進行求解，在特征空間中使基于L1范數的類間散度和基于L1范數的類內散度的比率達到最大化的投影向量作為局部最優的投影向量。但是DLPP-L2[6]是基于L2范數的，L2范數中平方操作會放大野值的影響。

受L1范數啟發，一種基于L1范數的鑒別局部保留投影(DLPP-L1)[11]被提了出來，其目標函數是基于L1范數的。此外，文獻[12,13]提出了一種運用最大間距準則(MMC)思想的特征提取方法。在幾何角度上，基于MMC的特征提取是通過最大化類間散度與類內散度之間的差值求解出一組最優的投影向量集進行投影，從而實現最大化類間散度，最小化類內散度的目標。此外，注意到MMC方法和MMC-L1這些方法在處理訓練樣本過程中都是基于一維向量來求解。為此，考慮直接對圖像數據矩陣進行降維的可行性，筆者對DLPP-L1方法進行改進，提出了一種基于L1范數的二維鑒別局部保留投影的最大間距準則方法(2DDLPP-L1/MMC)。

1 問題的提出

在分離圖中第i個頂點和第j個頂點之間的邊被定義為第i類和第j類之間均值矩陣的權重：

式中,σb是一個調節因子。

式中,σw是一個調節因子。

對圖像數據進行降維操作時，需要最大化特征空間中分離圖的類間離散度Jb(w)：

(1)

與此同時，最小化特征空間中內聚圖的類內離散度Jw(w)：

(2)

因此，MMC最終的目標函數旨在解決最優化問題(3)，以尋求最佳鑒別矢量為投影軸進行投影變換：

(3)

其中，A=[a(1),a(2),…,a(m)]T，a(l)(l=1,…,m)指的是A的第l行的列向量形式，即A的第l行為a(l)的轉置；|·| 表示絕對值操作； ‖·‖1表示L1范數；α是權重參數，用來調節不同類別情況下分離圖的類間離散度和內聚圖的類內離散度對特征提取的影響；L1范數指向量中各個元素絕對值之和；L2范數指向量中各元素平方和然后求平方根。如果采用L2范數優化求解上述問題，其中的平方操作會放大噪聲的負面影響。

2 2DDLPP-L1/MMC提取單個投影向量

最優投影方向w可以通過梯度法迭代求解出。由于數學上絕對值操作不可微分，而目標函數J(w(t))中又留有絕對值符號，所以，在這里筆者定義2個符號函數來解除絕對值對目標函數的影響，在第t步迭代過程中，定義的符號函數如下：

(4)

(5)

i,j=1,…,Nkk=1,…,cl=1,…,m

把式(4)和式(5)代入式(3)得到：

(6)

通過w(t+1)=w(t)+γg(t)來更新最優投影方向w(t)，其中：

(7)

式中，γ表示學習步長，是一個非常小的正值(0<γ<1)。

最優投影向量w通過式(4)、式(5)和式(7)的循環交替求解出，如果J(w(t+1))在后續的迭代過程中不再保持增長，那么終止循環操作。否則，對式(4)和式(5)符號函數進行更新操作，然后繼續循環操作，一直到有符合條件的投影向量w出現。

式(4)、式(5)符號函數與式(7)梯度公式在每次循環交替計算當中，表明式(6)中的目標函數J(w(t+1))>J(w(t))，即J(w(t))一直維持著非降。那么對式(4)、式(5)符號函數與式(7)梯度公式的循環交替處理會使得迭代求解漸漸達到一個收斂的過程，但是，目標函數通過優化迭代方法求解出的投影向量w是基于局部最優的，并不符合全局最優解的條件。因此筆者嘗試挑選出一系列w(0)初始化值來運行這個迭代優化算法以最大限度的找尋到最佳的目標函數最大值。

2DDLPP-L1/MMC單個投影向量的算法(算法1)步驟如下：

輸出：單個投影向量w*。

1)初始化：設迭代次數t=0，生成一個s維的非零向量w(0)，并且歸一化w(0)=w(0)/‖w(0)‖2。

3)計算符號函數：

4)更新為w(t+1)=w(t)+γg(t)，其中γ>0是一個調節因子:

5)判斷是否收斂：若J(w(t+1))停止增長，則終止循環，并令w*=w(t+1)。否則，令t=t+1，返回步3)并繼續向下執行，直到找到符合條件的投影向量。

3 2DDLPP-L1/MMC求取多個投影向量

上面所述的迭代方法只能提取出一個最優投影向量，實際應用中，這是遠遠不夠的，所以有必要擴展到提取多個投影向量。為了求取r個投影向量，筆者采用一種緊縮的方法來提取剩余的基向量。

設Xl=(xl1,…,xln)∈Rd×n，1≤l≤d。第r個基向量wr可通過求解如下問題來提取：

(8)

輸出：w1，w2，…，wm，因此W=(w1，w2，…，wm)。

2)h=1,…,m，執行以下迭代操作。計算：

對數據集Th調用算法1，提取wh。

4 試驗

為了驗證所提出的2DDLPP-L1/MMC方法較其他相關方法的性能優勢，筆者在0RL人臉數據庫上進行試驗驗證。ORL人臉數據庫中包含40人總共400張人臉圖像，每人10張不同表情和姿態條件下的面部圖像。試驗中，圖像處理成灰度級為256，分辨率為112×92的形式。編程環境為Matlab 2014，操作系統為Windows 7。同類試驗在設置參數上不能出現差異，要保持一致，以確保試驗的公平與結果的可靠。

4.1 權重參數α對識別率的影響

權重參數α平衡最大化分離圖的類間離散度和最小化內聚圖的類內離散度2個不同目標，為了評估權重參數對2DDLPP-L1/MMC方法的識別率的影響，試驗選用的訓練樣本為ORL數據庫中每類前一半圖像，余下的作為測試樣本,把權重參數α依序設置為0.0001、0.0005、0.001、0.005、0.01、0.05、0.1、0.5、1、5、10，試驗結果如圖1所示。

由圖1可知，當權重參數α逐步增加時，2DDLPP-L1/MMC方法的識別率逐漸穩步上升，隨后開始趨于平緩，當權重參數足夠大時，該方法的識別率又開始逐漸平緩的下降。由此可知，權重參數α對2DDLPP-L1/MMC識別率有著潛移默化的影響，而選用一個合適的α值相當重要。因此，在后面的試驗中均選擇了較為合理的α值，以最大化發揮2DDLPP-L1/MMC方法的性能。

4.2 訓練集大小對識別率的影響

訓練集大小對識別率有著較大的影響，試驗中選擇ORL人臉數據庫中每類前n(n=3,4,5,6,7,8)幅圖像作為訓練樣本，余下的圖像作為測試樣本，以此來測試各種方法的識別性能。為了保持試驗結果的公平與合理性，所有方法的投影軸數都設置成20個，結果如圖2所示。

由圖2可知，在其他條件相同的情況下，各種方法的識別率在訓練樣本數開始逐步增加時都呈現出穩步上升的趨勢，隨后趨于緩慢提高。這表明訓練樣本數的大小影響著各種方法的識別率，與此同時，2DDLPP-L1/MMC方法的識別率相比較于其他方法一直是較高的。

4.3 投影軸數對識別率的影響

投影軸數對識別率的有著較大的影響，試驗選用ORL人臉數據庫中每類前5幅圖像當做訓練樣本，余下圖像作為測試樣本，依次選擇1、2、…,20個投影軸數來檢驗各種方法的識別性能，結果如圖3所示。

圖1 權重參數α對識別率的影響 圖2 訓練集大小對識別率的影響

圖3 投影軸數對識別率的影響

由圖3可知，各種方法的識別率隨著投影軸數不斷增加都開始逐步上升，隨后各種方法識別率上升的趨勢趨于飽和平緩，當投影軸數大于20時識別率都會有進一步緩緩上升的趨勢。圖3顯示，2DDLPP-L1/MMC方法的識別率明顯要高于其他方法，因此，其判別性能要好于其他方法。

5 結語

提出了基于L1范數的二維鑒別局部保留投影的最大間距準則方法(2DDLPP-L1/MMC)。2DDLPP-L1/MMC直接基于圖像矩陣空間充分利用L1范數及最大間距準則的相關優勢來提取低維特征，從而避免了矩陣計算的復雜性和不穩定性。并且，筆者提出了一個優化迭代算法來求解最優投影矩陣，同時增強了對異常值的魯棒性。試驗結果證明，該方法的識別性能和其他相關方法相比更加高效。值得注意的是，該算法由于只是收斂到局部最優并不能達到全局最優的條件，所以有待進一步完善，未來要開展的工作中主要是研究如何找到全局最優。

[1]Turk M, Pentland A.Eigenfaces for Recognition.J Cogn Neurosci[J].Journal of Cognitive Neuroscience, 1991, 3(1):71～86.

[2] Akbari R, Mozaffari S.Performance enhancement of PCA-based face recognition system via gender classification method[J].2010, 1(1):1～6.

[3] Yu H, Yang J.A direct LDA algorithm for high-dimensional data -with application to face recognition[J].Pattern Recognition, 2001, 34(10):2067～2070.

[4] Huang J, Yuen P C, Chen W S, et al.Choosing Parameters of Kernel Subspace LDA for Recognition of Face Images Under Pose and Illumination Variations[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society, 2007, 37(4):847～862.

[5] He X, Niyogi P.Locality Preserving Projections (LPP)[J].Advances in Neural Information Processing Systems, 2002, 16(1):186～197.

[6] Yu W, Teng X, Liu C, et al.Face recognition using discriminant locality preserving projections[J].Image and Vision Computing, 2006, 24(3): 239～248.

[7] Kwak N.Principal component analysis based on l1-norm maximization[J].IEEE Transactions on Pattern Analysis & Machine Intelligence, 2008, 30(9):1672～1680.

[8] Nie F, Huang H, Ding C, et al.Robust Principal Component Analysis with Non-Greedy 1-Norm Maximization[C].International Joint Conference on Artificial Intelligence,2011:1433～1438.

[9] Zhong F, Zhang J.Linear discriminant analysis based on L1-norm maximization[J].IEEE Transactions on Image Processing, 2013, 22(8):3018～3027.

[10] Liu Y, Gao Q, Miao S, et al.A Non-greedy Algorithm for L1-norm LDA[J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 2016, PP(99):1～1.

[11] Zhong F, Zhang J, Li D, et al.Discriminant Locality Preserving Projections Based on L1-Norm Maximization[J].IEEE Transactions on Neural Networks, 2014, 25(11): 2065～2074.

[12] Li H, Jiang T, Zhang K.Efficient and robust feature extraction by maximum margin criterion[J].IEEE Transactions on Neural Networks, 2006, 17(1):157～165.

[13] Song F, Zhang D, Chen Q, et al.Face recognition based on a novel linear discriminant criterion[J].Pattern Analysis and Applications, 2007, 10(3):165～174.

[編輯] 洪云飛

2017-01-27

國家自然科學基金項目(61572033,71371012)；安徽高校自然科學研究項目(重大項目)(KJ2015ZD08)；教育部人文社會科學規劃項目(13YJA630098)。

謝玉凱(1990-)，男，碩士生，現主要從事計算機視覺方面的研究工作，1509739519@qq.com。

TP391.4

A

1673-1409(2017)09-0038-05

[引著格式]謝玉凱，盧桂馥，宣東東.基于L1范數的二維鑒別局部保留投影的最大間距準則方法[J].長江大學學報(自科版)，2017,14(9)：38～42，78.