邊界流形嵌入在特征提取中的應用

龔思聰，徐 潔，萬鳴華

1.廣東工業大學 自動化學院，廣州 510006

2.南京審計大學 信息工程學院，南京 211815

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

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

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

1 相關算法

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

1.1 邊界Fisher分析（MFA）

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

1.2 鄰域保持嵌入（NPE）

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

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

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

利用拉格朗日算子，將式（3）優化問題轉換為：

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

2 邊界流形嵌入（MME）

2.1 算法基本思想

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

2.2 尋找邊界

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

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

2.3 目標函數

對于類內權值矩陣Ww通過求解式（5）獲得：

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

給定一線性投影矩陣A，訓練樣本集X通過線性投影矩陣A嵌入到低維空間后，類內的重構誤差為：

訓練樣本集X通過投影矩陣A嵌入到低維空間后，類間的重構誤差為：

為了獲得更好判別性能的低維數據，需要最大化類間重構誤差，最小化類內重構誤差，那么進一步可重新表述為：

利用拉格朗日算子可將上式的優化問題轉化為：

A=[a1,a2,…,ad]由式（10）中最大的d個特征值所對應的特征向量構成。

2.4 算法步驟

輸入已知訓練集樣本矩陣X=[x1,x2,…,xn]∈RD×N，與樣本點對應的標簽l=[c1,c2,…,cn]∈R1×N，測試集樣本xj∈RD×1，樣本點的約簡維數d，訓練樣本點的異類近鄰點個數k1，訓練樣本點的同類近鄰點個數k2。

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

（1）計算訓練集每個樣本點xi∈RD×1和異類樣本點的歐氏距離，取距離xi最近k1個樣本點構成集合，再計算的均值mb。

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

（3）通過式（5）和式（6）計算類內權值矩陣Ww和類間權值矩陣Wb。

（4）求解式（10）d個最大特征值對應的特征向量，構成投影矩陣A∈RD×d。

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

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

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

圖2 MFA算法的邊界點分析圖Fig.2 Marginal samples analysis graph of MFA algorithm

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

圖3 LSDA算法的邊界點分析圖Fig.3 Marginal samples analysis graph of LSDA algorithms

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

圖4 MME算法的邊界點分析圖Fig.4 Marginal samples analysis graph of MME algorithm

3 實驗仿真

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

3.1 ORL人臉庫實驗

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

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

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

表1 各算法在ORL數據集的最優平均識別率對比（均值±標準差）Table 1 Top average classification accuracy and corresponding standard deviation on ORL database單位：%

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

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

3.2 PIE人臉庫實驗

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

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

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

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

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

表2 各算法在PIE數據集中的最優平均識別率對比（均值±標準差）Table 2 Top average classification accuracy and corresponding standard deviation on PIE database單位：%

3.3 YaleB人臉庫實驗

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

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

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

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

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

表3 各算法在YaleB數據集中的最優平均識別率對比（均值±標準差）Table 3 Top average classification accuracy and corresponding standard deviation on YaleB database單位：%

4 結束語

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

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