基于自適應近鄰圖嵌入的局部鑒別投影算法

王永茂 徐正光 趙 珊

①(北京科技大學自動化學院 北京 100083)

②(河南理工大學計算機科學與技術學院 焦作 454000)

1 引言

降維是高維數據壓縮、可視化和分類的重要預處理手段之一。PCA(Principle Component Analysis), FDA(Fisher Discriminant Analysis)[1]是最流行的降維方法，但其本質上是線性的，不能有效描述高維數據的非線性變化。基于流形的非線性降維方法是近年來興起的一類降維方法，等距映射(ISOMAP)[2]，局部線性嵌入(Locally Linear Embedding, LLE)[3]和拉普拉斯映射(Laplacian Eigenmap, LE)[4]是其典型代表，它們通過在降維過程中保持數據的局部信息來學習非線性流形結構，但是基于流形的降維方法的一大缺陷是不能直接映射新的測試點[5]，為了解決這一問題，許多學者先后提出局部保形投影(Locality Preserving Projection,LPP)[6]，近鄰保形嵌入(Neighborhood Preserving Embedding, NPE)[7]等基于流形的線性降維算法，它們分別為LE算法與LLE算法的線性逼近。盡管LPP, NPE在降維過程中能夠保持數據的局部信息，但在降維過程中未利用數據的類別信息，是一種無監督的降維方法，而傳統的FDA是一種有監督的線性降維方法，在降維過程中不能保持數據的局部信息。為此，文獻[8]將LPP的基本思想引入到FDA中提出了LFDA(Local Fisher Discrimiant Analysis)算法，在人臉識別[9]、人耳識別[10]等領域取得了較好的效果。然而LFDA在處理高維數據時仍有一些不足：(1)LFDA未考慮不同類別數據間的近鄰關系，相距較遠的不同類別間的數據在類間離差度量時占據較大比重，以致在處理某些數據時得不到正確的最優投影方向[11]；(2)為描述數據的局部信息，LFDA需要尋找數據的近鄰點，同其他基于流形的降維算法一樣，近鄰點個數的選擇對于最優的投影方向影響較大[12]。

為了解決LFDA存在的不足，本文提出了一種新的局部鑒別分析方法：基于自適應近鄰圖嵌入的局部鑒別投影(neighborhood graph embedding based Local Adaptive Discriminant Projection,LADP)算法，根據數據分布自適應構造描述局部信息的類內與類間近鄰圖，避免了近鄰點個數對于投影子空間的影響，在得到的低維子空間內，使得相同類別的近鄰點盡量靠近，而不同類別的近鄰點盡量分離。

2 局部Fisher鑒別分析(LFDA)

2.1 通用圖嵌入框架

許多降維方法可以利用通用圖嵌入框架進行解釋[13]，其形式化描述如下：由n個樣本組成的樣本集記作X=[x1,x2,…,xn]D×n，樣本xi是一個D維向量，li∈L={1,2,…,Nc}為樣本xi的類別標號，Nc為類別總數，nl定義為第l類樣本個數。線性降維是按照某種最優化標準得到一個D×d變換矩陣V，將樣本集X投影到低維空間得到Y=VTX=[y1,y2,…,yn]d×n，其中yi是xi的低維投影，維數為d，且d＜D。在此框架中優化準則通常可以表示為

2.2 LFDA的權值矩陣

在LFDA中，權值矩陣Ww和Wb定義為

Aij是樣本xi和xj之間的一種相似性度量，xi和xj差別越小，Aij值越大，反之越小，這里用高斯函數定義Aij，即

其中Nk(xj)表示樣本xj同類別的k個近鄰點集合，從式(2)和式(3)可以看出，LFDA中的權值體現了鑒別信息與局部信息，與xi和xj是否同類以及是否相鄰有關。

在式(3)權值矩陣的定義下，式(1)中VTX(Db-Wb)XTV對應為LFDA算法中的局部類間離差矩陣，由不同類別的所有樣本點以及同類別近鄰點決定，VTX(Dw-Ww)XTV對應為LFDA算法中的局部類內離差矩陣，僅由同類別的近鄰點決定。

2.3 LFDA的不足

在LFDA中，最優投影方向依賴于近鄰點個數k值的選擇；同時在計算類間離散度時，未考慮不同類別數據之間的近鄰關系，對于某些數據，LFDA得不到正確的最優投影方向，下面通過兩個例子加以說明。

圖1 人工數據 1

(1)不考慮不同類別數據之間的近鄰關系對于最優的投影方向的影響 在圖1中，聚類A與聚類B的距離小于聚類A與聚類C的距離，顯然最優的投影方向應該為垂直方向，但LFDA在類間離差度計算中所有不同類別的數據點間的距離的系數都是相同的，均為1/n，距離越大在類間離差度所占的比重也越大，因此，在圖1中，AC之間的距離占主導地位，在水平投影方向上AC之間的距離要大于在垂直方向上的投影，因此得到的最優投影方向為水平方向。相反，如果考慮不同類別數據之間的近鄰關系，這時C中的數據點就不會成為A中數據點的近鄰點，類間離差度僅由類間近鄰點決定，這時，應該使得AB兩個聚類有最大分離程度，顯然在垂直方向上滿足要求。因此在定義權值矩陣時需要考慮不同類別數據之間的近鄰關系。

(2)近鄰點個數k的選擇對于最優投影方法的影響 很顯然，對于圖 2(a)～圖 2(d)中的人工數據，最優的投影方向均為水平方向，但是數據與其距離最遠的數據點之間的距離隨著垂直方向上方差的增加而不斷增大，因為數據點與不同類別的數據點之間的權值均相等，因此與最遠端的數據點之間的距離在類間離差度的計算中占有比較大的比重，又因為在垂直方向的方差遠大于水平方向上的方差，因此投影方向隨著方差的增加而逐漸向垂直方向靠近，這時就需要增加類內近鄰點的個數，也就是k值來抵消遠端數據點在類間離差度中所占的比重，圖3為對于圖2(d)中的數據，投影方向隨近鄰點個數k的變化情況，圖中的直線代表不同近鄰點個數k對應的最優投影方向。

從圖 3可以看出隨著k值的增加，投影方向逐漸向水平方向靠近。因此近鄰點個數k對于最優的投影方向有較大的影響，需要根據數據的分布自適應確定數據之間的近鄰關系。

3 基于自適應近鄰圖嵌入的局部鑒別分析算法

基于上節提到的LFDA的不足，本文提出一種新的局部鑒別分析算法：基于自適應近鄰圖嵌入的局部鑒別投影算法(LADP)。LADP算法的步驟如下：

步驟 1 根據數據分布特性以及數據間的相似度自適應計算數據類內以及類間的近鄰點；

步驟 2 根據數據的類內類間近鄰點的個數定義局部類內與類間離差矩陣中的權值矩陣；

圖2 人工數據2

圖3 LFDA在不同k值下的最優投影方向對比

步驟 3 最大化局部類間離差度最小化局部類內離差度，得到最優子空間。

3.1 自適應近鄰點計算

首先根據式(4)計算樣本xi與所有其他樣本之間的平均相似度AS(xi)。

其中參數β取式(5)定義的所有樣本之間的歐式距離的平均值。

接著，根據式(6)和式(7)自適應確定xi的類內近鄰點集合Nw(xi)以及xi的類間近鄰點集合Nb(xi)。

根據式(6)和式(7)的定義，Nw(xi)為相似度大于平均相似度的與xi同類別的樣本集合，Nb(xi)是相似度大于平均相似度的與xi不同類別的樣本集合。

3.2 權值矩陣

這里，依據樣本的類內類間近鄰點的個數定義式(1)中的權值矩陣Ww和Wb：

其中kw(i)為樣本點xi同類別的近鄰點的個數，其值為類內近鄰點集合Nw(xi)中樣本點的個數，kb(i)為樣本點xi不同類別的近鄰的個數，其值為類間近鄰點集合Nb(xi)中樣本點的個數。

3.3 最優嵌入

為提高算法的靈活性，與式(1)優化準則不同，在本文采用的優化準則中，類間離差度與類內離差度所占的比重不同。

最大化式(1)等價于：

其中Lb=Db-Wb。

在約束條件VTXDwXTV=I下，最小化式(10)等價于最大化式(12)：

因此，由式(11)和式(12)，最優化問題變為

其中0≤α≤1為調節參數，令B=αLb+(1-α)·Ww，式(13)變為

式(14)的最優化問題轉換為廣義特征向量的求解：

令v1,v2,…,vd為式(15)最大的d個特征值對應的特征向量，則最優的變換矩陣為V=[v1,v2,…,vd]D×d。

3.4 時間復雜度分析

LFDA與LADP算法的時間復雜度主要由兩個方面決定：(1)類內類間近鄰點的計算；(2)廣義特征向量的求解。

在LFDA算法中，類內類間近鄰點計算的時間復雜度為O(Dn2+kn2)，其中O(Dn2)代表計算任意兩個樣本的歐式距離的時間復雜度，D為樣本的維數，n為樣本的個數，O(kn2)代表尋找同類別k個近鄰點的時間復雜度，又有局部類內類間離差矩陣均為D×D矩陣，求解廣義特征向量的時間復雜度為O(D3)，可知 LFDA算法的時間復雜度為O(Dn2+kn2+D3)，由于k遠小于樣本維數D和樣本個數n,O(kn2)的變化趨勢遠小于O(Dn2)與O(D3)，所以 LFDA算法的時間復雜度近似于O(Dn2+D3)。LADP與LFDA區別在于自適應確定類內類間近鄰點，計算任意兩個樣本的相似度的時間復雜度為O(Dn2)，得到每一個樣本的平均相似度的時間復雜度為O(n2)，與平均相似度進行比較確定類內和類間近鄰點集合的時間復雜度為O(n2)，求解廣義特征向量的時間復雜度為O(D3)，所以LADP算法的時間復雜度為O(Dn2+2n2+D3)，由于O(2n2)的變化趨勢遠小于O(Dn2)與O(D3)，LADP算法的時間復雜度近似于O(Dn2+D3)。因此LADP與LFDA的時間復雜度相當，僅由樣本的個數n和維數D決定。

4 實驗與結果

為了評估算法的性能，我們設計兩類實驗，實驗1將LADP應用分類任務，比較LADP與經典的PCA, FDA以及LFDA等算法的分類性能；實驗2通過低維特征抽取時間比較LFDA與LADP算法的運算效率。

4.1 分類識別

為了驗證本文提出的LADP算法在分類識別任務中的有效性，本文在ORL人臉庫，COIL20圖像庫以及ISOLET語音庫上進行實驗，比較LADP算法與 PCA[1], FDA[1], LFDA[8]等算法的分類識別性能。

4.1.1數據集介紹ORL人臉庫是由英國劍橋大學建立，共有40個人，每人10張圖像，共有400張人臉圖像，圖像的面部表情和面部細節有著不同程度的變化，人臉姿勢也有相當的程度變化，比較充分地反映了同一人不同人臉圖像的變化和差異，圖4是ORL人臉庫的部分樣本。COIL20圖像庫由20個物體的1440幅圖像組成，每一個物體旋轉一周每隔5°采集一幅圖像共有72幅圖像，圖5是COIL20圖像庫中的部分樣本。ORL人臉庫以及COIL20圖像庫中的圖像經剪切后大小均為 32×32，用一個1024維的向量表示。ISOLET語音庫是UCI機器學習數據集中的一個標準數據庫，由30個人的1560個語音樣本組成，采集每個人誦讀26個字母的語音各 2次共 52個語音樣本，每一個語音樣本用一個617維的向量表示。

圖4 ORL人臉數據庫中的部分人臉圖像

圖5 COIL20圖像庫中的部分樣本圖

4.1.2調節參數α選擇本節討論 LADP算法中類內和類間離散度的調節參數α對于識別性能的影響。這里采用交叉驗證方法進行調節參數α的選擇。在ORL人臉庫，COIL20圖像庫以及ISOLET語音庫上分別隨機選擇4幅圖像作為訓練樣本，其余所有圖像作為測試樣本，進行 10次重復試驗，取10次的平均識別率，圖6顯示了在調節參數α不同取值的情況下，LADP算法的平均識別率。可以看出，調節參數α對于識別性能有較大的影響，α的值越大，識別性能越好，在后續的實驗中取α=0.9。

圖6 平均識別率隨調節參數α的變化情況

4.1.3識別性能比較本節分別在 ORL人臉庫，COIL20圖像庫以及ISOLET語音庫對比本文提出的LADP算法與PCA, FDA, LFDA等算法的識別性能，使用最近鄰分類器完成分類識別。在實驗中，從每類圖像中隨機選取i張圖像作為訓練集，剩下的作為測試集，重復進行10次，共獲得10對不同的訓練集和測試集，用iTrain表示不同數量的訓練樣本數，取10次實驗的平均識別率。圖7～圖9分別為ORL人臉庫，COIL20圖像庫以及ISOLET語音庫上的平均最高識別率。

4.1.4討論

(1)由于實驗所用的樣本的維數很高，其存在的冗余信息可能影響圖像的識別率，從實驗結果也驗證了這一點，在PCA, FDA, LFDA以及LADP等降維算法得到的低維子空間內的識別率高于在原始空間內的識別率；

(2)FDA, LFDA以及LADP的識別率高于PCA方法，這是因為FDA, LFDA以及LADP在尋找最優子空間的過程中利用了數據的鑒別信息，而PCA尋找的最優子空間其重構誤差最小，沒有考慮有利于分類的鑒別信息；

(3)LFDA與 LADP在降維的過程中能夠保持數據的局部信息，尤其在訓練樣本不足的情況下，其性能要優于全局降維方法FDA；

圖7 ORL人臉數據庫上平均最高識別率

圖8 COIL20圖像庫上的平均最高識別率

圖9 ISOLET語音庫上的平均最高識別率

(4)LADP的識別率是最高的，這主要取決于以下幾個方面：(a)LADP充分考慮類內近鄰以及類間近鄰點對于分類結果的影響；(b)自適應確定類內以及類間近鄰點的個數，避免了近鄰點個數對于分類結構的影響；(c)在定義目標函數時，類內離差度與類間離差度所占比重不同。

4.2 低維特征抽取時間比較

本節利用低維特征抽取所花費的時間來比較LFDA與LADP算法的效率。LFDA與LADP算法采用 matlab7.0編寫，在配置主頻為 2.93 GHz的CPU(Intel酷睿2雙核E7500)以及2 G內存的計算機上運行。在 ORL人臉庫，COIL20圖像庫以及ISOLET語音庫上分別隨機選擇4幅圖像作為訓練樣本，其余所有圖像作為測試樣本，表1為LFDA與LADP算法進行低維特征抽取所花費時間。可以看出LFDA與LADP算法進行低維特征抽取所花費的時間相當，也就是說LADP算法在提高識別性能的同時算法的執行時間并沒有增加。

表1 低維特征抽取時間(s)

5 結束語

在分析了LFDA算法不足的基礎上，本文提出了一種新的基于局部保持的鑒別分析方法：基于自適應近鄰圖嵌入的鑒別投影方法，自適應計算數據的近鄰點集合，不僅能夠很好保持流行的局部結構，同時也能夠保持數據的鑒別信息，在人工數據以及標準數據庫上均取得了較好的效果。LADP本質上是一種線性降維方法，在應用LADP算法時，需要將圖像的2維結構轉換為向量形式，這就容易出現小樣本問題，基于張量表示的LADP算法是下一步研究的重點。

[1]Martinez A and Kak A. PCA versus LDA[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001, 23(2): 228-233.

[2]Tenenbaum J, Silva V, and Langford J. A global geometric framework for nonlinear dimensionality reduction[J].Science,2000, 290(5500): 2319-2323.

[3]Roweis S and Saul L. Nonlinear dimensionality reduction by locally linear embedding[J].Science, 2000, 290(5500):2323-2326.

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

[5]張大尉, 朱善安. 基于核鄰域保持判別嵌入的人臉識別[J]. 浙江大學學報(工學版), 2011, 45(10): 1842-1847.

Zhang Da-wei and Zhu Shan-an. Face recognition based on kernel neighborhood preserving discriminant embedding[J].Journal of Zhejiang University(Engineering Science), 2011,45(10): 1842-1847.

[6]He Xiao-fei and Niyogi P. Locality preserving projections[C].Proceedings of the 16th Advances in Neural Information Processing Systems, Vancouver, 2003: 153-160.

[7]He Xiao-fei, Cai Deng, Yan Shui-cheng,et al.. Neighborhood preserving embedding[C]. Proceedings of the 10th IEEE International Conference on Computer Vision, Beijing, 2005:1208-1213.

[8]Sugiyama M. Dimensionality reduction of multimodal labeled data by local fisher discriminant analysis[J].Journal of Machine Learning Research, 2007, 8(5): 1027-1061.

[9]Huang Hong, Feng Hai-liang, and Peng Cheng-yu. Complete local Fisher discriminant analysis with Laplacian score ranking for face recognition[J].Neurocomputing, 2012, 89(7):64-77.

[10]Huang Hong, Liu Jiamin, Feng Hailiang,et al.. Ear recognition based on uncorrelated local Fisher discriminant analysis[J].Neurocomputing, 2011, 74(17): 3103-3113.

[11]謝鈞, 劉劍. 一種新的局部判別投影方法[J]. 計算機學報,2011, 34(11): 2243-2250.

Xie Jun and Liu Jian. A new local discriminant projection method[J].Chinese Journal of Computers, 2011, 34(11):2243-2250.

[12]Raducanu B and Dornaika F. A supervised non-linear dimensionality reduction approach for manifold learning[J].Pattern Recognition, 2012, 45(6): 2432-2444.

[13]俞璐, 謝鈞, 朱磊. 一種基于目標空間的局部判別投影方法[J].電子與信息學報, 2011, 33(10): 2390-2395.

Yu Lu, Xie Jun, and Zhu Lei. A local discriminant projection method based on objective space[J].Journal of Electronics&Information Technology, 2011, 33(10): 2390-2395.