羅 璇 張 莉 薛楊濤 李凡長(zhǎng)

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

引 言

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

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

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

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

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

1 適用于小樣本的SLDA算法

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

(1)

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

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

SLw=λSTw

(2)

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

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

2.1 雙鄰接圖判別分析

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

(3)

局部散度為

(4)

非局部散度為

(5)

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

(6)

(7)

由式(4,6)可以得到

(8)

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

(9)

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

(10)

(11)

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

?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。特征值對(duì)應(yīng)的特征向量矩陣為

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

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

(13)

因?yàn)椴町惱绽股⒍染仃嘢D也是非負(fù)定的，所以對(duì)它進(jìn)行特征值分解后的特征值可能為零，也可能為正。設(shè)分解后d個(gè)最小的特征值為μ1≤μ2≤…≤μd，其對(duì)應(yīng)向量分別為φ1,φ2,…,φd，令W2={φ1,φ2,…,φd}。最終的投影矩陣W=W1W2。DAG-DA算法的步驟如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

但是，本文算法在實(shí)現(xiàn)過(guò)程中需要尋找熱核函數(shù)的最佳參數(shù)值，同時(shí)去掉了總體拉普拉斯散度矩陣的零空間，這兩步使得該算法的時(shí)間復(fù)雜度比LPP和DNE算法高。下一步工作將嘗試尋找時(shí)間復(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] 樓宋江, 張國(guó)印, 潘海為，等. 人臉識(shí)別中適合于小樣本情況下的監(jiān)督化拉普拉斯判別分析[J]. 計(jì)算機(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.