邊界流形嵌入在特征提取中的應(yīng)用

龔思聰，徐 潔，萬鳴華

1.廣東工業(yè)大學(xué) 自動化學(xué)院，廣州 510006

2.南京審計大學(xué) 信息工程學(xué)院，南京 211815

降維是計算機(jī)視覺、模式識別、機(jī)器學(xué)習(xí)等領(lǐng)域[1-3]常見的數(shù)據(jù)分析和處理方法。在人臉識別[4-5]、數(shù)據(jù)可視化等領(lǐng)域[6-9]，通常需要從高維數(shù)據(jù)中提取有效的低維特征，以方便數(shù)據(jù)分析和處理。用于降維的特征提取算法不僅可以減少計算機(jī)的存儲空間和計算成本，還可以去除數(shù)據(jù)的冗余信息，提取數(shù)據(jù)的本質(zhì)特征[10-11]。降維算法主要包括線性降維算法和非線性降維算法。線性降維算法最典型的包括：主成分分析（principal component analysis，PCA）[12-14]和線性判別分析（linear discriminant analysis，LDA）[15-16]。PCA是一種無監(jiān)督的降維算法，其核心思想是找到一組正交基，將高維數(shù)據(jù)映射到低維空間，使降維后的數(shù)據(jù)方差最大，從而達(dá)到盡可能多地保留原始高維數(shù)據(jù)的信息。LDA是一種監(jiān)督的降維算法，其目標(biāo)是尋找一組最優(yōu)投影向量來最大化類間散度矩陣和類內(nèi)散度矩陣之間的比值，使得同一類數(shù)據(jù)盡可能聚集在一起，不同類數(shù)據(jù)盡可能分開。

但是這兩種算法都旨在保留原始高維數(shù)據(jù)的全局歐氏結(jié)構(gòu)，并不能挖掘到原始高維數(shù)據(jù)的局部流形特征。因此，眾多基于流形學(xué)習(xí)的非線性降維算法被廣泛研究，如：等距映射（isometric mapping，ISOMAP）[17-18]、局部線性嵌入（locally linear embedding，LLE）[19-20]、拉普拉斯特征映射（Laplacian eigenmaps，LE）[21-22]等。這些非線性流形學(xué)習(xí)降維算法，通過高維空間樣本點(diǎn)之間的近鄰關(guān)系來刻畫原始高維數(shù)據(jù)的局部流形特征，并且使數(shù)據(jù)降維后依然保留這種局部流形特征。然而這些非線性流形學(xué)習(xí)算法不僅計算成本高，而且僅僅定義在訓(xùn)練樣本集上，對于一個新的測試樣本，無法給出高維數(shù)據(jù)到低維數(shù)據(jù)的映射關(guān)系。為了解決這個問題，基于相似性保留的線性化流形學(xué)習(xí)方法被提出。典型的算法有：鄰域保持嵌入（neighborhood preserving embedding，NPE）[23-24]和局部保留投影（locality preserving projection，LPP）[25-26]，此類算法都通過線性嵌入來保留數(shù)據(jù)的局部流形特征，給出了高維數(shù)據(jù)到低維數(shù)據(jù)的映射關(guān)系，但僅通過保留原始高維數(shù)據(jù)的局部流形特征，并不能很好地表征原始高維數(shù)據(jù)的可分性[27]。于是，基于圖嵌入的降維算法——邊界Fisher分析（marginal Fisher analysis，MFA）[28-29]、局部敏感判別分析（locality sensitive discriminant analysis，LSDA）[30-31]、判別最大化邊界投影（discriminant maximum margin projections，DMMP）[32]相繼被提出。DMMP算法在保留原始高維數(shù)據(jù)局部流形特征的同時，最大化不同類樣本之間的邊界，然而，DMMP算法使用的類間權(quán)重不隨樣本之間的距離而改變，不能很好地反映出樣本在高維空間的邊界信息。MFA算法和LSDA算法利用數(shù)據(jù)的局部結(jié)構(gòu)為每個樣本點(diǎn)構(gòu)造本征圖和懲罰圖，使得同一類的樣本點(diǎn)投影后相互靠近，不同類的樣本點(diǎn)投影后相互遠(yuǎn)離。MFA算法分別尋找每個樣本點(diǎn)的同類近鄰點(diǎn)和異類近鄰點(diǎn)，來構(gòu)造本征圖和懲罰圖，這容易導(dǎo)致樣本點(diǎn)所選擇的同類近鄰點(diǎn)和異類近鄰點(diǎn)之間沒有必然的聯(lián)系。與MFA算法相比，LSDA算法首先給定每個樣本點(diǎn)的近鄰域半徑，然后根據(jù)近鄰點(diǎn)的標(biāo)簽信息將鄰域里的近鄰點(diǎn)分為同類近鄰點(diǎn)和異類近鄰點(diǎn)，進(jìn)而構(gòu)造出本征圖和懲罰圖。對于LSDA算法來說，由于未考慮樣本點(diǎn)的分布情況，容易導(dǎo)致樣本點(diǎn)的近鄰域里只有同類樣本點(diǎn)，離群點(diǎn)的近鄰域里只有異類樣本點(diǎn)，從而無法找到劃分同類樣本點(diǎn)和異類樣本點(diǎn)之間的邊界，這大大地削弱了LSDA算法在分類任務(wù)中的性能。為了減弱LSDA算法的離群點(diǎn)問題，提升的局部敏感判別分析（improved locality sensitive discriminant analysis，ILSDA）[33]和局部敏感判別投影（locality sensitive discriminant projection，LSDP）[34]相繼被提出。ILSDA算法在LSDA算法的基礎(chǔ)上引入樣本的全局結(jié)構(gòu)，通過最小化類內(nèi)散度來減弱離群點(diǎn)問題。LSDP算法在最小化同類近鄰樣本投影后距離的同時，為了使同類樣本投影后具有更強(qiáng)的緊密程度，最小化同類非近鄰樣本投影后的距離來減弱離群點(diǎn)問題。然而，這兩種算法仍然面臨為樣本點(diǎn)構(gòu)造近鄰域的時候，容易導(dǎo)致樣本點(diǎn)的近鄰域里只有同類樣本點(diǎn)的問題。

為了更有效地利用樣本點(diǎn)的邊界信息，更好地解決MFA算法和LSDA算法所面臨的問題，本文提出了一種新的圖嵌入降維算法——邊界流形嵌入（marginal manifold embedding，MME）。MME算法利用樣本點(diǎn)的標(biāo)簽信息，首先尋找到距離每個樣本點(diǎn)的最近異類邊界子流形（鄰域），再返回本類中尋找距離異類邊界子流形最近的同類邊界子流形（鄰域）。這樣一來，MME算法可以為每個樣本點(diǎn)尋找到位于邊界的緊密聯(lián)系的同類邊界子流形和異類邊界子流形，從而定義出同類樣本點(diǎn)和異類樣本點(diǎn)之間的邊界。受Fisher鑒別準(zhǔn)則啟發(fā)，MME算法在保留同類樣本點(diǎn)邊界局部鄰域結(jié)構(gòu)的同時，最大化每個樣本點(diǎn)的同類邊界子流形和異類邊界子流形之間的距離，從而得到具有鑒別意義的低維特征空間。另外，值得一提的是，MME算法很好地將徘徊在邊界的離群點(diǎn)收入到邊界鄰域里，這在一定程度上能夠減弱離群點(diǎn)給算法帶來的負(fù)面影響，實(shí)驗(yàn)也驗(yàn)證了MME算法的有效性。

1 相關(guān)算法

X=[x1,x2,…,xN]∈RD×N，X為給定N個樣本點(diǎn)所組成矩陣，其中每一個樣本xi∈RD為一個D維列向量。每個樣本xi所屬的類別記作l(xi)，共有c類樣本，即l(xi)∈{1,2,…,c}，第i類樣本點(diǎn)的個數(shù)為ni，樣本點(diǎn)總個數(shù)為定義線性投影矩陣A∈RD×d，經(jīng)過線性變換yi=ATxi，可將原始空間中的D維數(shù)據(jù)xi轉(zhuǎn)換為d維數(shù)據(jù)yi∈Rd，其中d?D。

1.1 邊界Fisher分析（MFA）

在MFA算法中，定義了類內(nèi)權(quán)重矩陣和類間權(quán)重矩陣，分別建立兩個鄰接圖：本征圖和懲罰圖。在本征圖中，對于每一個樣本點(diǎn)xi，定義類內(nèi)權(quán)重矩陣Ww，如果xj屬于xi同類的k個近鄰樣本點(diǎn)，那么Wijw=Wjiw=1，否則Wijw=Wjiw=0；在懲罰圖中，對于每一個樣本xi，定義類間權(quán)重矩陣Wb，如果xj屬于xi異類的k個近鄰樣本點(diǎn)，那么Wijb=Wjib=1，否則Wijb=Wjib=0。MFA算法通過邊界Fisher準(zhǔn)則尋找最佳投影方向：

1.2 鄰域保持嵌入（NPE）

假設(shè)在高維空間中一共有n個樣本點(diǎn)，NPE算法中，每一個樣本點(diǎn)xi可以被它的k個最近鄰樣本點(diǎn)線性重構(gòu)。首先構(gòu)造鄰接圖，對于每一個樣本點(diǎn)xi，如果樣本點(diǎn)xj屬于其k個近鄰樣本點(diǎn)，那么從xi到xj生成一條有向邊。定義權(quán)重矩陣W，如果從xi到xj存在有向邊，則存在權(quán)值Wij，否則為零。W可以通過求解如下最小化問題獲得：

NPE算法認(rèn)為高維空間中樣本點(diǎn)的重構(gòu)關(guān)系同樣會在低維空間中保持，因此線性投影矩陣A=可以通過求解以下最小化問題獲得：

其中，M=(I-W)T(I-W)，I為單位矩陣。

利用拉格朗日算子，將式（3）優(yōu)化問題轉(zhuǎn)換為：

線性投影矩陣A=[a1,a2,…,ad]由式（4）中最小的d個特征值所對應(yīng)的特征向量構(gòu)成。

2 邊界流形嵌入（MME）

2.1 算法基本思想

MME算法根據(jù)樣本點(diǎn)的標(biāo)簽信息，首先尋找距離每個樣本點(diǎn)最近的異類邊界子流形，再返回本類中尋找距離此異類邊界子流形最近的同類邊界子流形。這樣一來，每個樣本點(diǎn)都關(guān)聯(lián)著一對匹配的邊界子流形。在獲得有針對性的邊界后，MME算法利用同類邊界子流形的樣本點(diǎn)構(gòu)造本征圖，目的在于更好地保持同類樣本點(diǎn)邊界流形的局部鄰域結(jié)構(gòu)。但同時為了更好地實(shí)現(xiàn)分類，MME算法利用異類邊界子流形的樣本點(diǎn)構(gòu)造懲罰圖，目的在于增大同類樣本點(diǎn)和異類樣本點(diǎn)之間的距離。MME的目的很明確，樣本點(diǎn)嵌入到低維空間后，不僅能夠保留同類樣本點(diǎn)的局部邊界鄰域結(jié)構(gòu)，還能獲得更好的鑒別性能。

2.2 尋找邊界

如圖1所示，表示一個三分類問題。三類樣本點(diǎn)分別用不同的形狀表示。以第1類中的樣本點(diǎn)xi為例，計算樣本點(diǎn)xi與第2類和第3類所有樣本點(diǎn)的歐氏距離，取距離xi最近的k1個樣本點(diǎn)，構(gòu)成樣本點(diǎn)xi的異類近邊界鄰域集合。計算的均值mb，再計算mb與樣本點(diǎn)xi所在類別（即：第1類）的其他樣本點(diǎn)的歐氏距離，取距離mb最近的k2個樣本點(diǎn)，構(gòu)成樣本點(diǎn)xi的k2個同類邊界鄰域集合從圖1可以看出構(gòu)成的異類邊界鄰域集合和構(gòu)成的同類邊界鄰域集合是密切聯(lián)系的，通過減小樣本點(diǎn)xi與內(nèi)樣本點(diǎn)之間的距離，同時增大樣本點(diǎn)xi與內(nèi)樣本點(diǎn)之間的距離，能夠有效將第1類樣本點(diǎn)與第2類、第3類樣本點(diǎn)分開。

圖1 MME算法尋找邊界樣本點(diǎn)的示意圖Fig.1 Diagrammatic sketch of finding marginal samples by MME algorithm

2.3 目標(biāo)函數(shù)

對于類內(nèi)權(quán)值矩陣Ww通過求解式（5）獲得：

對于類間權(quán)值矩陣Wb通過求解式（6）獲得：

給定一線性投影矩陣A，訓(xùn)練樣本集X通過線性投影矩陣A嵌入到低維空間后，類內(nèi)的重構(gòu)誤差為：

訓(xùn)練樣本集X通過投影矩陣A嵌入到低維空間后，類間的重構(gòu)誤差為：

為了獲得更好判別性能的低維數(shù)據(jù)，需要最大化類間重構(gòu)誤差，最小化類內(nèi)重構(gòu)誤差，那么進(jìn)一步可重新表述為：

利用拉格朗日算子可將上式的優(yōu)化問題轉(zhuǎn)化為：

A=[a1,a2,…,ad]由式（10）中最大的d個特征值所對應(yīng)的特征向量構(gòu)成。

2.4 算法步驟

輸入已知訓(xùn)練集樣本矩陣X=[x1,x2,…,xn]∈RD×N，與樣本點(diǎn)對應(yīng)的標(biāo)簽l=[c1,c2,…,cn]∈R1×N，測試集樣本xj∈RD×1，樣本點(diǎn)的約簡維數(shù)d，訓(xùn)練樣本點(diǎn)的異類近鄰點(diǎn)個數(shù)k1，訓(xùn)練樣本點(diǎn)的同類近鄰點(diǎn)個數(shù)k2。

輸出最佳線性投影矩陣A∈RD×d，訓(xùn)練樣本集矩陣X的低維表示Y∈Rd×N，和測試集樣本xj的低維表示yj∈Rd×1。

（1）計算訓(xùn)練集每個樣本點(diǎn)xi∈RD×1和異類樣本點(diǎn)的歐氏距離，取距離xi最近k1個樣本點(diǎn)構(gòu)成集合，再計算的均值mb。

（2）計算mb與樣本點(diǎn)xi所在類別的其他樣本點(diǎn)的歐氏距離，取距離mb最近的k2個樣本點(diǎn)構(gòu)成集合

（3）通過式（5）和式（6）計算類內(nèi)權(quán)值矩陣Ww和類間權(quán)值矩陣Wb。

（4）求解式（10）d個最大特征值對應(yīng)的特征向量，構(gòu)成投影矩陣A∈RD×d。

（5）計算Y=ATX得到訓(xùn)練集樣本降維后的結(jié)果Y∈Rd×N，計算yj=ATxj，得到測試集樣本xj的降維結(jié)果yj∈Rd×1。

2.5 LSDA、MFA、MME算法邊界的比較

MFA算法分別尋找每個樣本點(diǎn)xi的k1個同類最近鄰樣本點(diǎn)，k2個異類最近鄰樣本點(diǎn)，構(gòu)造本征圖和懲罰圖，k2個異類樣本點(diǎn)構(gòu)成了樣本點(diǎn)xi的異類邊界點(diǎn)。如圖2所示，有兩類樣本點(diǎn)，分別用不同的形狀表示。以第一類樣本中的樣本點(diǎn)xi為例，當(dāng)k1和k2都取2時，樣本點(diǎn)xi所選擇的同類近鄰樣本點(diǎn)和異類邊界樣本點(diǎn)之間沒有必然聯(lián)系。減小樣本點(diǎn)xi與同類近鄰樣本點(diǎn)之間的距離，同時增大樣本點(diǎn)xi與異類邊界樣本點(diǎn)之間的距離并不能很好地表征同類樣本點(diǎn)和異類樣本點(diǎn)之間的可分性。

圖2 MFA算法的邊界點(diǎn)分析圖Fig.2 Marginal samples analysis graph of MFA algorithm

LSDA算法首先尋找每個樣本點(diǎn)的k個最近鄰樣本點(diǎn)，然后根據(jù)最近鄰樣本點(diǎn)的標(biāo)簽信息將每個樣本點(diǎn)的k個最近鄰樣本點(diǎn)劃分為同類鄰域和異類鄰域，進(jìn)而形成邊界，為保護(hù)樣本點(diǎn)的局部線性特征，k值選擇不能過大。如圖3所示，當(dāng)k值取4時，第一類樣本點(diǎn)中的樣本點(diǎn)xi只有同類近鄰點(diǎn)，而沒有異類近鄰點(diǎn)，從而無法為樣本點(diǎn)xi構(gòu)造懲罰圖。對于離群點(diǎn)來說，也容易遇到近鄰域里只有異類近鄰點(diǎn)的情況，從而無法為離群點(diǎn)構(gòu)造本征圖。這兩種情況都會削弱LSDA算法在分類任務(wù)中的性能。

圖3 LSDA算法的邊界點(diǎn)分析圖Fig.3 Marginal samples analysis graph of LSDA algorithms

本文中提出的MME算法，充分地利用了邊界樣本點(diǎn)的信息，并且能夠減弱離群點(diǎn)給算法帶來的負(fù)面影響。如圖4所示，以第一類樣本中的樣本點(diǎn)xi為例，首先尋找距離xi最近的2個異類邊界點(diǎn)構(gòu)成樣本點(diǎn)xi的異類邊界子流形，異類邊界點(diǎn)的均值mb能夠反映異類邊界點(diǎn)的分布情況，于是計算距離mb最近的2個第一類樣本點(diǎn)，構(gòu)成樣本點(diǎn)xi的同類邊界子流形。這樣一來，通過樣本點(diǎn)xi形成的同類邊界子流形和異類邊界子流形有著緊密的聯(lián)系，通過最大化樣本點(diǎn)xi與異類邊界子流形的距離，同時最小化樣本點(diǎn)xi與同類邊界子流形的距離，能夠有效地將第一類樣本點(diǎn)與第二類樣本點(diǎn)分開。同時，可以注意到離群點(diǎn)通常位于樣本點(diǎn)的邊界，MME算法在為每個樣本點(diǎn)構(gòu)造同類邊界鄰域和異類邊界鄰域的時候，很容易將離群點(diǎn)收入到邊界鄰域內(nèi)，這在一定程度上能夠減弱離群點(diǎn)給算法帶來的負(fù)面影響。

圖4 MME算法的邊界點(diǎn)分析圖Fig.4 Marginal samples analysis graph of MME algorithm

3 實(shí)驗(yàn)仿真

在本文實(shí)驗(yàn)中，采用MATLAB R2014b來實(shí)現(xiàn)各種算法，所用計算機(jī)內(nèi)存為8 GB，CPU為Intel?Core?i5-4200H CPU@2.80 GHz，主頻為2.80 GHz。為了驗(yàn)證MME算法的有效性，在ORL、PIE、YaleB人臉數(shù)據(jù)庫上進(jìn)行實(shí)驗(yàn)，與使用全局幾何結(jié)構(gòu)的PCA、LDA算法、局部結(jié)構(gòu)的流形學(xué)習(xí)算法LSDA、MFA、NPE、DMMP、ILSDA、LSDP算法對比。NPE算法中選取每個樣本點(diǎn)的其他同類樣本點(diǎn)構(gòu)造鄰接圖。實(shí)驗(yàn)中先用PCA算法對訓(xùn)練集樣本進(jìn)行預(yù)處理，保留99%的能量，以去除冗余信息，同時可以避免LDA、MFA、LSDA、NPE、LSDP、DMMP、MME算法的小樣本問題，再在訓(xùn)練集上求投影矩陣A，再對所有訓(xùn)練樣本和測試樣本進(jìn)行降維處理，最后用基于歐氏距離的最近鄰分類器對降維后的測試集數(shù)據(jù)進(jìn)行分類，得出準(zhǔn)確率。MME、LSDA、MFA、NPE、DMMP、ILSDA、LSDP算法涉及到參數(shù)選擇問題，本文經(jīng)過詳細(xì)的超參數(shù)搜索工作，使各個算法分類的準(zhǔn)確率達(dá)到最大，來獲取最優(yōu)參數(shù)。

3.1 ORL人臉庫實(shí)驗(yàn)

ORL數(shù)據(jù)集包括40個不同人的共400幅圖像，每人共有10幅圖像，包括面部表情、光照方向、面部朝向的方向、睜眼或者閉眼、是否戴眼鏡等多種變化。對ORL數(shù)據(jù)集的圖像進(jìn)行裁剪和縮放得到尺寸為32×32像素的灰度圖像，部分圖像如圖5所示。

圖5 ORL人臉庫兩個人各10幅圖像Fig.5 Two persons in ORL face database，10 images per person

實(shí)驗(yàn)中，在ORL人臉數(shù)據(jù)庫中，在每類樣本中隨機(jī)取p=2,3,4,5個樣本作為訓(xùn)練集，剩余樣本為測試集，對于固定的p值，進(jìn)行20次隨機(jī)實(shí)驗(yàn)，其均值作為算法最終的識別率。Baseline方法即為數(shù)據(jù)沒有降維直接采用最近鄰分類器分類。LDA算法的最大降維維度為c-1，c為ORL人臉數(shù)據(jù)庫類別數(shù)量。表1展示了各個算法最優(yōu)平均識別率的均值以及最優(yōu)平均識別率均值的標(biāo)準(zhǔn)差。圖6展示了4種劃分情況下，ORL人臉數(shù)據(jù)庫平均識別準(zhǔn)確率與投影維度變化曲線圖。

表1 各算法在ORL數(shù)據(jù)集的最優(yōu)平均識別率對比（均值±標(biāo)準(zhǔn)差）Table 1 Top average classification accuracy and corresponding standard deviation on ORL database單位：%

由表1和圖6可知，隨著樣本訓(xùn)練集的增加，各個算法的平均識別率都有顯著提升，無監(jiān)督的PCA算法在所有的算法中識別率最低，相對于Baseline方法基本沒有提升，這表明在分類任務(wù)中樣本的標(biāo)簽信息非常重要。MME算法的平均識別率在各個投影維度變化下均高于其余算法，在投影維度為1至40維時，MME算法的平均識別率提升顯著，并明顯優(yōu)于其他降維算法，這表明MME算法所提取的低維特征能夠獲得很好地表征不同類樣本點(diǎn)的可分性。同時，當(dāng)投影維度大于40維到70維時，隨著投影維度的增加，NPE、MFA、LSDA、ILSDA、LSDP算法識別率出現(xiàn)一定程度下滑，而MME算法在此情況下，平均識別率仍能很好地保持在最優(yōu)值附近，說明隨著維度的增加，MME算法所提取的低維特征能夠更有效地保留數(shù)據(jù)的判別信息和表征數(shù)據(jù)的本質(zhì)結(jié)構(gòu)，所保持的樣本點(diǎn)的局部邊界信息相比于MFA算法和LSDA算法能夠更好地表征同類樣本點(diǎn)和異類樣本點(diǎn)的可分性。隨著訓(xùn)練樣本數(shù)的增加，MME算法比較于LDA、NPE、DMMP算法的識別率也明顯要高很多，這表明樣本點(diǎn)的密切聯(lián)系的局部邊界信息對于分類具有重要意義。

圖6 ORL數(shù)據(jù)集平均識別準(zhǔn)確率與投影維度變化曲線圖Fig.6 Average classification accuracy versus projection vectors number on ORL database

3.2 PIE人臉庫實(shí)驗(yàn)

PIE人臉數(shù)據(jù)庫包含68位志愿者的41 368張多姿態(tài)、光照和表情的面部圖像，其中的姿態(tài)和光照變化圖像是在嚴(yán)格控制的條件下采集，每幅圖片大小為92×112像素。實(shí)驗(yàn)中，采用PIE人臉庫正面姿勢（C09）在不同的光照和表情下68個人的所有圖像，每個人24幅圖片，總計1 632張圖片進(jìn)行實(shí)驗(yàn)，所有圖像根據(jù)眼睛坐標(biāo)進(jìn)行旋轉(zhuǎn)、剪切、縮放到64×64像素的圖片，部分人臉圖像如圖7所示。

圖7 PIE人臉庫中兩個人的部分圖像Fig.7 Partial image of two people in PIE face database

實(shí)驗(yàn)中，在PIE人臉數(shù)據(jù)庫中，在每類樣本中隨機(jī)取p=6,8,10,12個樣本作為訓(xùn)練集，剩余樣本為測試集，對于固定的p值，進(jìn)行10次隨機(jī)實(shí)驗(yàn)，其均值作為算法最終的識別率。表2展示了各個算法最優(yōu)平均識別率的均值以及最優(yōu)平均識別率均值的標(biāo)準(zhǔn)差。圖8展示了4種劃分情況下，PIE人臉數(shù)據(jù)庫平均識別準(zhǔn)確率與投影維度變化曲線圖。

由表2和圖8可知，隨著訓(xùn)練樣本的增加，各個算法的平均識別率都有一定的提升，相對于有監(jiān)督的降維算法，無監(jiān)督的PCA算法在所有的算法中識別率最低，這與ORL庫的實(shí)驗(yàn)結(jié)論一致。在所有的監(jiān)督性降維算法中，保持?jǐn)?shù)據(jù)點(diǎn)局部結(jié)構(gòu)的MFA、LSDA、NPE、DMMP、ILSDA、LSDP、MME算法與僅保持?jǐn)?shù)據(jù)全局結(jié)構(gòu)的LDA算法相比，識別率更高，這在一定程度上表明了維持樣本局部流形特征對于分類的重要性。同時，隨著訓(xùn)練樣本數(shù)增加，ILSDA算法和LSDP算法在為樣本點(diǎn)構(gòu)造近鄰域的時候，容易導(dǎo)致其近鄰域里只有同類近鄰點(diǎn)，導(dǎo)致ILSDA算法和LSDP算法相比于LSDA算法，識別率提升不明顯，甚至沒有提升。同時，也可以注意到利用邊界局部信息的LSDA算法、MFA算法相比于只利用同類樣本點(diǎn)局部信息的NPE算法，識別率差別不大，這除了與數(shù)據(jù)集本身沒有體現(xiàn)出不同算法之間的差異性有關(guān)之外，也從一定程度上表明了LSDA算法和MFA算法所保留的邊界局部信息在一些情況下并不能很好地表征同類樣本點(diǎn)和異類樣本點(diǎn)的可分性。與之相比，MME算法投影維度較低的情況下，最優(yōu)平均識別率能夠優(yōu)于其他降維算法，而且隨著訓(xùn)練樣本數(shù)的增加，訓(xùn)練集包含更多的信息，MME算法的識別率上升得較快，優(yōu)于其他降維算法，這表明MME算法為每個樣本點(diǎn)尋找緊密相聯(lián)的同類邊界子流形和異類邊界子流形構(gòu)造本征圖和懲罰圖，所保留的邊界局部信息相比于MFA、LSDA、DMMP、ILSDA、LSDP算法能夠更好地表征同類數(shù)據(jù)點(diǎn)和異類數(shù)據(jù)點(diǎn)的可分性。

圖8 PIE數(shù)據(jù)集平均識別準(zhǔn)確率與投影維度變化曲線圖Fig.8 Average classification accuracy versus projection vectors number on PIE database

表2 各算法在PIE數(shù)據(jù)集中的最優(yōu)平均識別率對比（均值±標(biāo)準(zhǔn)差）Table 2 Top average classification accuracy and corresponding standard deviation on PIE database單位：%

3.3 YaleB人臉庫實(shí)驗(yàn)

Extend YaleB人臉數(shù)據(jù)庫包含38個人，每個人9種姿態(tài)有64種光照條件，共有圖像16 128幅圖像。在實(shí)驗(yàn)中，選取Extend YaleB人臉庫在不同光照條件下38個人的正面姿勢圖像，每人64幅圖像，總計2 432張圖片進(jìn)行實(shí)驗(yàn)，所有圖像根據(jù)眼睛坐標(biāo)進(jìn)行旋轉(zhuǎn)、剪切、縮放到32×32像素的圖片，部分圖像如圖9所示。

圖9 YaleB人臉庫中兩個人的部分圖像Fig.9 Partial image of two people in YaleB face database

實(shí)驗(yàn)中，在YaleB人臉數(shù)據(jù)庫中，在每類樣本中隨機(jī)取p=5,10,20,30個樣本作為訓(xùn)練集，剩余樣本為測試集，對于固定的p值，進(jìn)行10次隨機(jī)實(shí)驗(yàn)，其均值作為算法最終的識別率。表3展示了各個算法最優(yōu)平均識別率的均值以及標(biāo)準(zhǔn)差。圖10展示了四種劃分情況下，YaleB數(shù)據(jù)集的準(zhǔn)確率與投影維度的變化曲線圖。

通過表3和圖10可見，隨著訓(xùn)練樣本集增加，ILSDA算法相對于LSDA算法的識別率提升不明顯，這在一定程度上反映了ILSDA算法使用了類內(nèi)樣本的全局結(jié)構(gòu)，不利于樣本之間局部流形特征的維持，這削弱了算法在分類任務(wù)中的性能。而LSDP算法在最小化同類近鄰樣本的投影距離的同時，最小化同類非近鄰樣本的投影距離，一定程度上減弱了離群點(diǎn)給算法帶來的影響，相比于LSDA算法收獲了明顯更高的識別率。與之相比，MME算法在投影維度較高情況下最優(yōu)平均識別率能夠較明顯優(yōu)于其余算法，而且隨著訓(xùn)練樣本的增加，訓(xùn)練集包含更多的信息，所有算法的最優(yōu)平均識別率都有較明顯提高，但MME算法的最優(yōu)平均識別率上升更為明顯，使得MME算法在投影維度不斷增加的情況下，與其他算法相比，平均識別率的優(yōu)勢也越大。這表明MME算法提取的低維特征能夠很好地表征原始高維數(shù)據(jù)的可分性，所保留的邊界結(jié)構(gòu)信息相比于LSDA、MFA、DMMP、ILSDA、LSDP算法能夠更好地揭示原始高維數(shù)據(jù)的判別結(jié)構(gòu)。同時，在不同的訓(xùn)練樣本下，當(dāng)MME算法的識別率達(dá)到最大之后，隨著投影維度的增加，MME算法的識別率能夠很好地穩(wěn)定在最優(yōu)值附近，這也說明了MME算法具有一定的魯棒性。

圖10 YaleB數(shù)據(jù)集平均識別準(zhǔn)確率與投影維度變化曲線圖Fig.10 Average classification accuracy versus projection vectors number on YaleB database

表3 各算法在YaleB數(shù)據(jù)集中的最優(yōu)平均識別率對比（均值±標(biāo)準(zhǔn)差）Table 3 Top average classification accuracy and corresponding standard deviation on YaleB database單位：%

4 結(jié)束語

本文提出了一種新的圖嵌入降維算法——邊界流形嵌入（MME），MME算法充分利用了樣本點(diǎn)的邊界信息，通過為每個樣本點(diǎn)尋找緊密聯(lián)系的同類邊界子流形和異類邊界子流形，使得每個樣本點(diǎn)構(gòu)造本征圖和懲罰圖所選擇的同類邊界點(diǎn)和異類邊界點(diǎn)能夠很好地表征不同類樣本點(diǎn)的可分性。因此，MME算法將數(shù)據(jù)降維之后，能夠獲得較好的鑒別性能。在ORL數(shù)據(jù)集、PIE數(shù)據(jù)集、YaleB數(shù)據(jù)集的實(shí)驗(yàn)及分析表明了MME算法在多種情況下能夠取得較好的分類效果，適合分類任務(wù)。

雖然MME算法獲得了良好的改進(jìn)效果，但算法仍有可改進(jìn)的地方，由于MME算法需要人工選擇兩個參數(shù)，在實(shí)際應(yīng)用中會產(chǎn)生參數(shù)選擇的困難。如何自適應(yīng)確定參數(shù)值是未來需要進(jìn)一步研究的問題。