謝玉凱，盧桂馥，宣東東

(安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241000)

基于L1范數(shù)的二維鑒別局部保留投影的最大間距準(zhǔn)則方法

謝玉凱，盧桂馥，宣東東

(安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241000)

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

鑒別局部保留投影；L1范數(shù)；最大間距準(zhǔn)則；魯棒性

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

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

從統(tǒng)計(jì)的角度來看，相比于L2范數(shù)，L1范數(shù)對(duì)野值更具魯棒性，因?yàn)長1范數(shù)中的絕對(duì)值操作減輕了對(duì)野值的影響?；诖?，基于L1范數(shù)的相關(guān)方法開始被提出來，如基于L1范數(shù)的PCA[7,8]，基于L1范數(shù)的LDA[9,10]。PCA-L1實(shí)際上是將PCA模型中的L2范數(shù)改為L1范數(shù)來進(jìn)行求解，其局部最優(yōu)投影向量通過對(duì)特征空間中的基于L1范數(shù)的方差實(shí)現(xiàn)最大化求解而得到，但是PCA-L1計(jì)算較為復(fù)雜并且樣本數(shù)據(jù)中的類別屬性沒有得到運(yùn)用。LDA-L1是將LDA模型中的L2范數(shù)改為L1范數(shù)來進(jìn)行求解，在特征空間中使基于L1范數(shù)的類間散度和基于L1范數(shù)的類內(nèi)散度的比率達(dá)到最大化的投影向量作為局部最優(yōu)的投影向量。但是DLPP-L2[6]是基于L2范數(shù)的，L2范數(shù)中平方操作會(huì)放大野值的影響。

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

1 問題的提出

在分離圖中第i個(gè)頂點(diǎn)和第j個(gè)頂點(diǎn)之間的邊被定義為第i類和第j類之間均值矩陣的權(quán)重：

式中,σb是一個(gè)調(diào)節(jié)因子。

式中,σw是一個(gè)調(diào)節(jié)因子。

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

(1)

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

(2)

因此，MMC最終的目標(biāo)函數(shù)旨在解決最優(yōu)化問題(3)，以尋求最佳鑒別矢量為投影軸進(jìn)行投影變換：

(3)

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

2 2DDLPP-L1/MMC提取單個(gè)投影向量

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

(4)

(5)

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

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

(6)

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

(7)

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

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

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

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

輸出：單個(gè)投影向量w*。

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

3)計(jì)算符號(hào)函數(shù)：

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

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

3 2DDLPP-L1/MMC求取多個(gè)投影向量

上面所述的迭代方法只能提取出一個(gè)最優(yōu)投影向量，實(shí)際應(yīng)用中，這是遠(yuǎn)遠(yuǎn)不夠的，所以有必要擴(kuò)展到提取多個(gè)投影向量。為了求取r個(gè)投影向量，筆者采用一種緊縮的方法來提取剩余的基向量。

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

(8)

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

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

對(duì)數(shù)據(jù)集Th調(diào)用算法1，提取wh。

4 試驗(yàn)

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

4.1 權(quán)重參數(shù)α對(duì)識(shí)別率的影響

權(quán)重參數(shù)α平衡最大化分離圖的類間離散度和最小化內(nèi)聚圖的類內(nèi)離散度2個(gè)不同目標(biāo)，為了評(píng)估權(quán)重參數(shù)對(duì)2DDLPP-L1/MMC方法的識(shí)別率的影響，試驗(yàn)選用的訓(xùn)練樣本為ORL數(shù)據(jù)庫中每類前一半圖像，余下的作為測(cè)試樣本,把權(quán)重參數(shù)α依序設(shè)置為0.0001、0.0005、0.001、0.005、0.01、0.05、0.1、0.5、1、5、10，試驗(yàn)結(jié)果如圖1所示。

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

4.2 訓(xùn)練集大小對(duì)識(shí)別率的影響

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

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

4.3 投影軸數(shù)對(duì)識(shí)別率的影響

投影軸數(shù)對(duì)識(shí)別率的有著較大的影響，試驗(yàn)選用ORL人臉數(shù)據(jù)庫中每類前5幅圖像當(dāng)做訓(xùn)練樣本，余下圖像作為測(cè)試樣本，依次選擇1、2、…,20個(gè)投影軸數(shù)來檢驗(yàn)各種方法的識(shí)別性能，結(jié)果如圖3所示。

圖1 權(quán)重參數(shù)α對(duì)識(shí)別率的影響 圖2 訓(xùn)練集大小對(duì)識(shí)別率的影響

圖3 投影軸數(shù)對(duì)識(shí)別率的影響

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

5 結(jié)語

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

[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

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

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

TP391.4

A

1673-1409(2017)09-0038-05

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