適用于小樣本的雙鄰接圖判別分析算法

羅 璇 張 莉 薛楊濤 李凡長

(1.蘇州大學(xué)計算機科學(xué)與技術(shù)學(xué)院,蘇州,215006；2.蘇州大學(xué)機器學(xué)習(xí)與類腦計算國際合作聯(lián)合實驗室，蘇州，215006)

引 言

近年來，隨著科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)的數(shù)量和維度呈現(xiàn)出快速增長的趨勢。降維不僅可以簡化模型、降低模型的訓(xùn)練時間，而且可以提高模型的泛化能力。因為高維數(shù)據(jù)難以表達(dá)且需要較高的計算和存儲代價，所以降維方法成為機器學(xué)習(xí)和模式識別領(lǐng)域中的熱門研究方向，并已在人臉識別、手寫體識別等系統(tǒng)中取得了良好的效果。

降維方法可分為線性和非線性兩種。線性降維方法，如主成分分析法(Principal component analysis, PCA)[1]、線性判別分析(Linear discriminant analysis, LDA)[2]等，幾何表達(dá)簡單、計算成本較低，是分析高維數(shù)據(jù)的基礎(chǔ)。PCA由Karl Pearson于1901年提出,該方法使用正交線性變換將一組觀測的可能相關(guān)變量轉(zhuǎn)換為一組線性不相關(guān)變量，這些不相關(guān)變量叫做主成分。擁有最大方差，即盡可能不相關(guān)的數(shù)據(jù)稱為第一主成分，并以此類推。PCA算法的核心是對數(shù)據(jù)協(xié)方差矩陣進行特征分解。LDA算法與方差分析和回歸分析密切相關(guān)，它試圖找到一組特征的線性組合，能將多個對象盡量分開，即找到最佳投影方向。

如果所需的特征在一個低維的流形子空間中，那么傳統(tǒng)的線性降維算法并不能很好地提取出該非線性結(jié)構(gòu)，因此很多非線性的流形學(xué)習(xí)算法被提出，包括等距映射(Isomap)[3]、拉普拉斯特征映射(Laplacian eigenmaps, LE)[4]及局部線性嵌入(Locally-linear embedding, LLE)[5]等。

但是以上流形學(xué)習(xí)算法只考慮了訓(xùn)練樣本，處理過程中未能得到一個顯式映射，因此不能處理新樣本，即所謂的“out of sample”問題。針對這個問題，He等人提出了保局算法(Locality preserving projection, LPP)[6]和局部保持嵌入算法(Neighborhood preserving embedding, NPE)[7]:(1) LPP算法首先整合鄰近點信息建立一個圖，該圖可看做一個連續(xù)流形結(jié)構(gòu)的線性離散近似[6]，然后使用拉普拉斯算子計算出轉(zhuǎn)換矩陣將數(shù)據(jù)點映射到低維子空間;LPP算法使原始高維空間中距離相近點在降維后依舊保持近距離。(2) NPE算法的目的在于保持局部流形結(jié)構(gòu)。在一定范圍內(nèi)給定一些數(shù)據(jù)點，首先建立權(quán)重矩陣來描述數(shù)據(jù)點之間的關(guān)系，并將每個點用鄰近點線性表示;然后找到一個最佳嵌入使得該鄰近結(jié)構(gòu)在低維空間中得以保持。以上兩個利用局部信息進行降維的算法雖然沒有“out of sample”問題，但非局部信息在此過程中被忽略，即算法沒有考慮相隔較遠(yuǎn)的點之間的關(guān)系。2007年，Yang等人提出了非監(jiān)督判別投影(Unsupervised discriminant projection，UDP)算法[8]。該方法考慮了樣本點在低維表示后的局部和非局部性，最小化局部散度的同時最大化非局部散度，即使非局部散度與局部散度的比值盡可能大。但UDP是非監(jiān)督的學(xué)習(xí)方法，也就是不能利用樣本的類別信息，不利于分類；而且在處理過程中也出現(xiàn)小樣本問題[9]：當(dāng)訓(xùn)練樣本個數(shù)遠(yuǎn)小于樣本維數(shù)時，就會出現(xiàn)矩陣奇異問題。2012年，樓宋江等人提出的小樣本有監(jiān)督拉普拉斯判別分析算法(Supervised Laplacian discriminant analysis, SLDA)[9],通過將類內(nèi)拉普拉斯散度矩陣投影在去除零空間的總體拉普拉斯散度矩陣上，避免了小樣本問題。但是由于該方法中沒有明確最大化類間散度，因而導(dǎo)致在投影空間的可分性不夠好。2015年，丁春濤等人提出的基于雙鄰接圖的判別近鄰嵌入算法(Double adjacency graphs-based discriminant neighborhood embedding, DAG-DNE)[10], 融入了構(gòu)建雙鄰接圖的想法，解決了判別近鄰嵌入(Discriminant neighborhood embedding, DNE)圖嵌入降維方法在構(gòu)造權(quán)重矩陣時數(shù)據(jù)不平衡的問題。

受到DAG-DNE算法的啟發(fā)，本文提出了一種新的基于拉普拉斯判別分析的有監(jiān)督降維方法，稱為適用于小樣本的雙鄰接圖判別分析方法(Double adjacent graph-based discriminant analysis for small sample size, DAG-DA)。DAG-DA在構(gòu)建鄰接圖時考慮了樣本的不平衡問題，每個樣本點都至少建立兩個關(guān)聯(lián)，并將局部拉普拉斯散度矩陣與非局部拉普拉斯散度矩陣的差投影到總體拉普拉斯散度矩陣的秩空間中，然后在該空間中進行特征問題的求解，求得投影矩陣。通過在簡單人工數(shù)據(jù)集、Yale人臉庫和ORE人臉庫的實驗證明了DAG-DA算法的優(yōu)越性。

1 適用于小樣本的SLDA算法

針對小樣本問題，已有相應(yīng)的一些解決方案[9,11-12]，其中監(jiān)督化拉普拉斯判別分析算法和本文的工作緊密相關(guān)。該算法是一種有監(jiān)督的流形學(xué)習(xí)算法，其目標(biāo)是最小化局部散度，同時最大化非局部散度，即非局部散度與局部散度的比值盡可能大[13]，表達(dá)式為

(1)

式中：W為投影矩陣，JL為局部散度，JN為非局部散度，JT為總體散度，JT=JL+JN。

以上優(yōu)化問題(1)可以轉(zhuǎn)化為如下目標(biāo)函數(shù)

SLw=λSTw

(2)

式中：λ為特征分解得到的特征值，w為特征向量，SL為局部拉普拉斯散度矩陣，ST為丟棄零空間的總體拉普拉斯散度矩陣。

2 適用于小樣本的DAG-DA算法

2.1 雙鄰接圖判別分析

由于適用于小樣本的監(jiān)督化拉普拉斯判別分析算法在分子上僅考慮將局部拉普拉斯散度矩陣進行投影,忽略了非局部拉普拉斯散度矩陣。為了強調(diào)非局部信息，本文考慮在最優(yōu)化函數(shù)里引入非局部散度,表達(dá)式為

(3)

局部散度為

(4)

非局部散度為

(5)

式(4,5)中：F為相似度矩陣；B為差異度矩陣。與SLDA方法從數(shù)據(jù)點的K近鄰中找到同類和異類樣本點來構(gòu)建鄰接圖不同，本文在構(gòu)造鄰接圖時借用雙鄰接圖的思想，從同類和異類樣本點間分別找到K個近鄰點，再構(gòu)建F和B。

(6)

(7)

由式(4,6)可以得到

(8)

式中SL為局部拉普拉斯散度矩陣

(9)

同樣，由式(5，7)可以得到

(10)

(11)

由式(3,8,10)可推導(dǎo)出目標(biāo)函數(shù)等價于

?SDw=λSTw

(12)

式中：SD=SL-SN，α∈range(ST)。

2.2 秩空間

Λ=diag(λ1,λ2,…,λr,λr+1,…,λn)

其中特征值λ1≥λ2…≥λr，λr+1=λr+2=…=λn=0。特征值對應(yīng)的特征向量矩陣為

U={u1,u2,…,ur,ur+1,…,un}

其中特征值λi對應(yīng)的特征向量為ui。

(13)

因為差異拉普拉斯散度矩陣SD也是非負(fù)定的，所以對它進行特征值分解后的特征值可能為零，也可能為正。設(shè)分解后d個最小的特征值為μ1≤μ2≤…≤μd，其對應(yīng)向量分別為φ1,φ2,…,φd，令W2={φ1,φ2,…,φd}。最終的投影矩陣W=W1W2。DAG-DA算法的步驟如下:

輸出：投影矩陣W∈Rd×r。

(1)構(gòu)建相似度矩陣S和差異性矩陣B；

(3)對矩陣ST進行特征分解，取其非零特征值λi和非零特征值對應(yīng)的向量ui，分別組成矩陣Λ和U，其中Λ為對角矩陣且Λii=λi，U的第i列為ui，令W1=UΛ；

(5)最終投影矩陣：W=W1W2。

2.3 DAG-DA算法和SLDA算法比較

(1)在用鄰接圖來保持樣本的局部結(jié)構(gòu)信息時，SLDA算法找到近鄰后，利用類別信息再構(gòu)建類內(nèi)和類間鄰接圖，這樣可能會出現(xiàn)只有類內(nèi)近鄰或只有類間近鄰的數(shù)據(jù)不平衡問題。而在計算權(quán)值時，同等距離下類間近鄰比類內(nèi)近鄰的權(quán)值更大，這顯然不利于保持?jǐn)?shù)據(jù)的結(jié)構(gòu)。DAG-DA算法分別在類內(nèi)和類間找近鄰點，從熱核函數(shù)可以看出:若是類內(nèi)近鄰點，則賦予較大的權(quán)值；若是類間近鄰點，則權(quán)值較小。這樣可以擴大類內(nèi)距離縮小類間距離的影響，同時也解決了數(shù)據(jù)不平衡的問題，更好地保持了數(shù)據(jù)的流形結(jié)構(gòu)。

(2)在優(yōu)化問題選取目標(biāo)函數(shù)時，SLDA算法的目標(biāo)函數(shù)(式(1))分子上僅考慮了將局部拉普拉斯散度矩陣進行投影，而忽略了非局部拉普拉斯散度矩陣;而DAG-DA算法在最優(yōu)化函數(shù)(式(3))里引入了非局部散度，強調(diào)了類間散度，使得降維后的數(shù)據(jù)可分性更好。

(3)在對總體拉普拉斯散度矩陣進行特征分解后，SLDA算法選取的投影空間為特征向量乘以一個小于1的數(shù);而DAG-DA算法直接將非零向量作為投影空間，相當(dāng)于少乘一個縮小因子，使數(shù)據(jù)更加準(zhǔn)確。

3 實驗結(jié)果與分析

為驗證DAG-DA算法的有效性，在各類數(shù)據(jù)上對DAG-DA算法進行實驗，并與SLDA算法、LPP算法和DNE算法進行比較。這4種算法均可以對近鄰個數(shù)進行調(diào)節(jié)，其中SLDA算法和DAG-DA算法中的t和σ為可變參數(shù)。本文實驗均采用最近鄰分類器對降維后的數(shù)據(jù)進行分類。

3.1 人工數(shù)據(jù)

隨機生成兩類符合均勻分布的人工數(shù)據(jù)，一類是0～1之間的隨機數(shù)，另一類是0.7～1.7之間的隨機數(shù)，分別用SLDA算法和DAG-DA算法學(xué)習(xí)得到投影矩陣。圖1顯示了SLDA算法和DAG-DA算法學(xué)習(xí)投影矩陣后投影后的效果。從圖1中看到，圖1(b)中的類間點距離更大，類內(nèi)點距離更小，也就是DAG-DA算法相對比SLDA而言，降維效果有了明顯的提升，也更適合于分類。在對優(yōu)化函數(shù)進行等價替代后，SLDA算法的目標(biāo)函數(shù)里并沒有考慮類間距離，僅將局部拉普拉斯散度矩陣投影到總空間。DAG-DA算法對其進行改進，將局部拉普拉斯散度矩陣與非局部拉普拉斯散度矩陣的差進行投影，是一個更理想的目標(biāo)函數(shù)。

除了圖1能直觀地看出兩種算法的分類效果外，表1還給出了兩種算法在人工數(shù)據(jù)測試后的具體結(jié)果。從表1中可以看出，用DAG-DA算法降維比SLDA算法得到的類內(nèi)距離和更小，類間距離和更大，說明降維后分類效果更佳。

圖1 SLDA與DAG-DA在簡單人工數(shù)據(jù)集上的比較Fig.1 Comparison of SLDA and DAG-DA on artificial dataset

表1 SLDA與DAG-DA在人工數(shù)據(jù)上測試結(jié)果比較

3.2 Yale人臉數(shù)據(jù)庫

Yale人臉數(shù)據(jù)庫[14]共有165張人臉灰度圖像，每張圖像數(shù)字為32×32的像素矩陣，來自15個不同的人，每人11張。每個人的各張圖像有不同的光照條件(中央光照、左側(cè)光照、右側(cè)光照)和不同的表情(眼鏡/無眼鏡、高興、常態(tài)、悲傷、睡眠、驚訝和眨眼)。Yale人臉數(shù)中不同條件下的一些人臉圖像樣本如圖2所示。該實驗中，隨機選擇60%樣本作為訓(xùn)練樣本，其余的40%作為測試樣本。

圖2 Yale人臉圖像示例Fig.2 Face examples of Yale dataset

圖3 在Yale人臉庫上不同維數(shù)的識別率 Fig.3 Recognition rate of different algorithms on Yale dataset

在實驗時，為了減少大量的計算，先采用PCA方法對測試數(shù)據(jù)進行初始降維，初始降維的投影矩陣為A。再采用DAG-DA，SLDA，LPP，DNE四種算法進行再次降維，二次降維矩陣為W，最終投影矩陣為P=WA。利用P把訓(xùn)練樣本和訓(xùn)練樣本投影到低維空間，再用近鄰分類器進行分類，得到各個方法降維后的識別率。在構(gòu)造鄰接圖時，選取k=3，通過循環(huán)找到最佳的t和σ。圖3顯示了DAG-DA算法，SLDA算法，LPP算法和DNE算法在不同維數(shù)下的識別率。表2顯示了不同算法在Yale人臉庫上的最高識別率和特征維度。

表2 Yale人臉庫各算法最高識別率和特征維數(shù)

3.3 ORL人臉數(shù)據(jù)庫

ORL人臉數(shù)據(jù)庫[15]共有400張人臉灰度圖像，每張圖像為32×32的像素矩陣，來自40個不同的人，每人10張。每個人的各圖像有不同的人臉大小、人臉旋轉(zhuǎn)程度和不同的表情(睜眼/閉眼、高興/悲傷、戴眼鏡/不戴眼鏡等)。ORL人臉數(shù)據(jù)庫中不同條件下的一些人臉圖像樣本如圖4所示。該實驗中，隨機選擇60%樣本作為訓(xùn)練樣本，其余的40%作為測試樣本。

圖4 ORL人臉圖像示例Fig.4 Face examples of ORL dataset

圖5 在ORL人臉庫上不同維數(shù)的識別率Fig.5 Recognition rate of different algorithms on ORL dataset

同樣，為了減少大量的計算，先采用PCA方法對測試數(shù)據(jù)進行初始降維，再采用DAG-DA，SLDA，LPP和DNE四種算法進行再次降維，最后用近鄰分類器進行分類，得到各個方法降維后的識別率。本文選取k=3，通過循環(huán)找到最佳的t和σ。圖5顯示了DAG-DA算法，SLDA算法，LPP算法和DNE算法在不同維數(shù)下的識別率。表3顯示了不同算法在ORL人臉庫上的最高識別率和特征維度。

從實驗結(jié)果可以看出，DAG-DA算法達(dá)到的最佳識別率最高。SLDA算法的識別率高于LPP算法，因為SLDA算法考慮了非局部信息和樣本的類別信息。DNE算法也是監(jiān)督化學(xué)習(xí)方法，它構(gòu)建了類內(nèi)與類間的鄰接圖，讓同類數(shù)據(jù)在低維空間緊湊， 不同類數(shù)據(jù)盡可能分開， 識別率高于LPP算法。DAG-DA算法不僅考慮了非局部信息和樣本類別信息，而且考慮了數(shù)據(jù)不平衡問題，并在目標(biāo)函數(shù)內(nèi)加入了非局部拉普拉斯散度矩陣，所以最佳識別率不僅優(yōu)于LPP算法，也比SLDA和DNE算法更勝一籌。

表3 ORL人臉庫各算法最高識別率和特征維數(shù)

4 結(jié)束語

本文為了處理監(jiān)督化拉普拉斯判別分析方法中的鄰接圖數(shù)據(jù)不平衡問題，以及目標(biāo)函數(shù)中類間信息缺失問題，提出了適用于小樣本的雙鄰接圖判別分析算法DAG-DA，并在Yale和ORL人臉數(shù)據(jù)集上驗證了該方法的有效性。

但是，本文算法在實現(xiàn)過程中需要尋找熱核函數(shù)的最佳參數(shù)值，同時去掉了總體拉普拉斯散度矩陣的零空間，這兩步使得該算法的時間復(fù)雜度比LPP和DNE算法高。下一步工作將嘗試尋找時間復(fù)雜度較低且降維效果好的算法。

參考文獻(xiàn):

[1] Jolliffe I T. Principal component analysis [M]. Berlin:Springer-Verlag, 2002.

[2] Yan S, Xu D, Zhang B, et al. Graph embedding and extensions:A general framework for dimensionality reduction [J]. IEEE Trans Pattern Anal Mach Intell, 2006, 29 (1):40.

[3] Tenenbaum J B, De S V, Langford J C. A global geometric framework for nonlinear dimensionality reduction [J]. Science, 2000, 290 (5500):2319-2323.

[4] Belkin M, Niyogi P. Laplacian Eigenmaps for dimensionality reduction and data representation[J]. Neural Computation, 2003, 15(6):1373-1396.

[5] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding [J]. Science, 2009, 290(5500):2323-2326.

[6] Niyogi X. Locality preserving projections[J]. Advances in Neural Information Processing Systems, 2004, 16:153.

[7] He X, Cai D, Yan S, et al. Neighborhood preserving embedding[C]// Tenth IEEE International Conference on Computer Vision. [S.l.]:IEEE, 2005:1208-1213.

[8] Yang J, Zhang D, Yang J, et al. Globally maximizing, locally minimizing:Unsupervised discriminant projection with applications to face and palm biometrics [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(4):650-664.

[9] 樓宋江, 張國印, 潘海為，等. 人臉識別中適合于小樣本情況下的監(jiān)督化拉普拉斯判別分析[J]. 計算機研究與發(fā)展, 2012, 49(8):1730-1737.

Lou Songjiang, Zhang Guoyin, Pan Haiwei, et al. Supervised Laplacian discriminant analysis for small sample size problem with its application to face recognition[J]. Journal of Computer Research and Development, 2012, 49(8):1730-1737.

[10] Ding C T, Zhang L. Double adjacency graphs-based discriminant neighborhood embedding [J]. Pattern Recognition, 2015, 48(5):1734-1742.

[11] Huang R, Liu Q, Lu H, et al. Solving the small sample size problem of LDA[C]// 16th International Conference on Pattern Recognition. [S.l.]:IEEE Computer Society, 2002:30029.

[12] Jain A K, Duin R P W, Mao J. Statistical pattern recognition:A review [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2000, 22(1):34-37.

[13] Tao Y J, Yang J. Quotient vs. difference:Comparison between the two discriminant criteria [J]. Neurocomputing, 2010, 73(10/11/12):1808-1817.

[14] University of California, San Diego. The Yale face database[EB/OL]. http://vision.ucsd.edu/content/yale-face-database, 2013-12-21.

[15] AT&T Laboratories Cambridge.The ORL face database[EB/OL]. http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html, 2013-12-21.