一種基于局部和判別特性的降維算法

摘 要:提出了一種基于LPP和LDA的降維算法。該算法不僅考慮了LPP能保持局部鄰近關系屬性，還考慮了LDA能使降維后的數據更易于分類屬性，并且該算法是線性的，很容易將新樣本映射到目標空間。在人臉識別中的實驗驗證了算法的正確性和有效性。

關鍵詞:維數約簡; 局部保持投影; 線性判別分析; 人臉識別

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3324-02

doi:10.3969/j.issn.1001-3695.2009.09.035

Dimension reduction algorithmbased on locality and discriminant characteristics

ZHANG Guo-yin， LOU Song-jiang， WANG Qing-jun， CHEN Hui-jie

(College of Computer Science Technology， Harbin Engineering University， Harbin 150001， China)

Abstract:This paper proposed a dimension reduction algorithm based on LPP and LDA， which not only utilized that LPP could preserve locality， but also took into account that the LDA made the data more discriminant and thus made classification mare easier. The proposed algorithm was linear， which could map the out of sample data to the target space easily. Experiments in face recognition validate the correctness and effectiveness of the algorithm.

Key words:dimension reduction; locality preserving projection(LPP); linear discriminant analysis(LDA); face recognition

0 引言

在生物特征識別系統中，人臉識別由于具有成本較低、不侵犯使用者的隱私權、應用前景廣闊等特點，受到了極大的關注，是當前模式識別、圖像處理和計算機視覺等學科非常活躍的研究熱點[1]之一。

正是因為人臉識別的這些特點，在過去的幾年時間里，出現了很多人臉識別算法。其中，基于子空間的算法起到了主導作用，最著名的是主成分分析[2](principal component analysis)和線性判別分析[3](linear discriminant analysis)。主成分分析算法的主要思想是通過估計數據的二階統計性質來發現數據的本征線性維數，它是在全局最小重構誤差的條件下把高維觀察數據投影到低維空間上，通過求解數據點協方差矩陣的最大幾個特征值所對應的特征向量張成的子空間而得到。線性判別分析算法就是求出一個線性子空間，使得所有樣本在這個子空間中，類內樣本散度最小，類間樣本的散度最大，用它降維后的低維嵌入坐標非常有利于進行樣本的分類。

上述兩種方法是線性算法，但人臉空間更可能存在于非線性子空間中。最近相關人員提出了幾種流形學習算法，主要用于非線性降維，如等距映射(ISOMAP)[4]、局部線性嵌入算法(LLE)[5]、拉普拉斯特征映射(LE)[6]等。但是它們都不能解決out of sample問題，即不能直接映射新數據，因此不能直接用于人臉識別。基于以上問題，He等人[7]提出了一種線性算法LPP，該算法是拉普拉斯特征映射的線性版本，能保持數據集的局部鄰近關系，又能較容易地映射新樣本。

LPP雖然能保持數據的局部結構，但是沒有利用數據集的類別信息，從而不利于分類問題。本文基于LPP和LDA的優點，既考慮LPP的局部保持特性，同時又利用LDA的易于分類問題這一特點，提出了一種基于局部特性和判別特性的降維算法。

1 基于局部特性和判別特性降維算法

1.1 LPP簡介

LPP目標是保持數據之間的相似性，即原始空間上相鄰的數據點在投影空間上也保持相應的鄰近關系。假定數據集X={x1，x2，…，xn}含有n個樣本點，每個樣本點xi屬于D維歐式空間，即xi∈RD，且樣本數據來自一本征維數為d(d<

Wopt=argminW∑ij(yi-yj)2Sij=argminW∑ij(W Txi-W Txj)2Sij=argminW WTXLXTW(1)

其中:Sij刻畫了兩數據xi、xj之間的相似性。

Sij=exp(-xi-xj2)/txi，xj為鄰近點0其他

附加約束條件W TXDX TW=1，拉普拉斯算子L=D-S。其中:D為對角矩陣，其元素為對稱矩陣S的列向量(或行向量)元素之和，即Dij=∑jSij。最后可以通過以下特征方程求解:

XLXTw=λXDXTw(2)

假定w0，w1，…，wd-1為特征方程式(2)的d個解，它們所對應的特征值分別為λ0，λ1，…，λd-1，那么可以得到如下映射:xi→yi=W Txi。其中:yi為d維向量;W為變換矩陣。

1.2 LDA簡介

對于分類問題，希望能找到某個投影方向，使得不同類的數據在投影后能盡量分開。LDA算法就是找到這樣一投影方向，使得數據在低維空間中同類數據盡量靠近，不同類數據盡量分離，從而保留豐富的辨別信息，使數據具有最大的可分性。

給定分別屬于J類的n個數據樣本X={x1，x2，…，xn}，Cj表示第j類元素構成的集合，nj表示屬于第j類元素的個數，μj=(1/n)j∑xi∈Cjxi表示第j類的均值，μ表示樣本的總體均值。

令Sb、Sw分別為類間散度矩陣和類內散度矩陣，即

Sb=(1/n)∑Ji=1ni(μi-μ)(μi-μ)T(3)

Sw=(1/n)∑Jj=1∑xi∈Cj(xi-μj)(xi-μj)T(4)

問題歸結為求以下特征方程:

Sbw=λSww(5)

設w1，w2，…，wd是對應于矩陣Sw-1Sb的前d個最大特征值的特征向量，則令W=[w1，w2，…，wd]，投影后的數據為yi=WTxi，i∈n。

1.3 基于局部和判別特性的降維算法

基于以上的簡單介紹可以看出LPP能有效降低數據維數，并能保持數據間的鄰近關系，LDA能找到一投影，使得投影后的數據更加有利于分類。本節將LPP和LDA的這兩個特性結合起來，形成既保持數據點之間的關系又有利于分類的新穎降維算法。

找到一投影，使得目標函數W T(Sw+σXLX T)W/(WTSbW)最小(Sw、Sb、L定義同上)，并受到一限制條件WTXDXTW=1。所以問題最后歸結為以下優化問題:

Wopt=argminW W T(Sw+σXLX T)W/(W TSbW))s.t. W  TXDX TW=1(6)

這里假設Sb可逆，即假設Sb非奇異，則該優化問題可以簡化成

Wopt=argminW W TSb-1(Sw+σXLXT)Ws.t.W TXDXTW=1(7)

通過Lagrange乘數法，令

L(W)=W TSb-1(Sw+σXLX T)W-λ(W TXDX TW-1)(8)

對W求偏導，得到

L(W)/W=2Sb-1(Sw+σXLXT)W-2λXDXTW(9)

令L(W)/W=0，即

Sb-1(Sw+σXLXT)W-λXDXTW=0(10)

最后求解以下廣義特征方程

Sb-1(Sw+σXLXT)w=λXDXTw(11)

假定w0，w1，…，wd-1為式(11)的d個解，它們所對應的特征值分別為λ0，λ1，…，λd-1，那么可以得到如下映射:xi→yi=W Txi。其中:yi為d維向量;W為變換矩陣。

在求解過程中，Sb有可能是奇異的，為了解決該問題，可以先通過PCA算法，使得Sb變成非奇異。所以具體算法步驟如下:

a)對原數據先進行主成分分析，一方面既可以消除噪聲，又可以避免Sb的奇異性，映射圖像X到PCA子空間，即Y=WTPCAX。

b)根據式(3)(4)求得Sw、Sb，以及拉普拉斯L和D。

c)根據式(10)解決特征函數問題，得到特征值和所對應的特征向量，求得Wopt。

d)令W=WPCAWopt，根據Y=WTX，將圖像X映射到目標子空間，求得目標圖像。

2 實驗結果及其分析

本算法采用公共人臉數據庫ORL庫來驗證算法的正確性和有效性。實驗過程為:先將人臉庫中的圖像進行光照預處理;再利用本文所提出的算法進行低維人臉特征提取;最后使用NN(nearest neighborhood)分類器進行識別。實驗中比較了該算法與PCA、LDA、LPP的識別率。

ORL人臉數據庫包含40人，每人有10張人臉圖片，共400張圖片。其中有一些圖像是在不同時期拍攝的，人的表情和臉部細節有著不同程度的變化，如睜眼和閉眼，是否帶有眼鏡等。人臉姿態也有一定程度的變化，深度旋轉和平面選擇可達20°，人臉大小也有多達10%的變化。圖1是ORL人臉數據庫中的第一個人的樣本。

為了有效地計算，所有圖像都縮放成32×32像素，即每一圖像可以看成是D=32×32=1 024維向量。參數σ是決定局部信息和類別信息對識別率貢獻的大小，這個很難確定，在實驗中，取σ=1，即假設局部信息和類別信息同等重要。每人分別隨機選擇3、4、5、6、7幅圖像用做訓練樣本，其他圖像用于測試樣本，重復20次，最后取平均值作為識別結果。該算法(姑且稱它為DRLD)與著名算法PCA、LDA、LPP進行了比較，實驗結果如

實驗結果表明，LDA算法的識別率高于PCA，這是因為LDA考慮了類別信息，更加有利于分類問題。而LPP雖然高于PCA， 但是沒有LDA理想，原因是雖然考慮了人臉的局部信息，但是沒有考慮類別信息，所以在人臉識別上的效果不如有監督的學習算法LDA。DRLD算法優于其他算法，這是因為它不僅考慮了人臉的局部信息，而且還考慮了類別信息，使不同類之間的可區分度加強了。顯然隨著訓練樣本數的增加，算法的識別率提高了。

3 結束語

本文提出了一種基于局部特性和判別特性的一種新穎數據降維算法，在一定程度上解決了流形學習方法應用于模式分類中存在的問題。該算法不僅保持了數據點之間的局部鄰近關系，而且也考慮了數據之間的類別關系。它是一種線性算法，能將新數據映射到目標空間，即解決流形問題中的out of sample問題。算法中有一參數σ，它是確定類別信息與局部信息對分類問題的貢獻大小。如何確定參數σ，如何將算法擴展成非線性使其能更好地用于實際應用(在此可以用核技巧kernel trick，先將數據映射到高維空間，再利用本文提出的算法)，以及將算法用于其他領域是今后的一個研究方向。

參考文獻:

[1]ZHAO W， CHELLAPPA R， ROSENFELD A，et al.Face recognition: a literature survey， CVL technical report[R]. Maryland: University of Maryland， 2000.

[2]TURK M， PENTLAND A. Eigenfaces for recognition [J]. Cognitive Neurosci， 1991，3(1):71-86.

[3]BELHUMEUR P N， KRIEGMAN D J. Eigenfaces vs. Fisherfaces: recognition using class specific linear projection[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 1997，19(7):711-720.

[4]TENENBAUM J B， DeSILVA V， LANGFORD J C. A global geome-tric framework for nonlinear dimensionality reduction[J/OL]. [2000-12-22]. http://www.sciencemag.org/content/vol290/issue5500/.

[5]ROWIES S， SAUL L. Nonliear dimensionality reduction by locally linear embedding[J/OL]. [2000-12-22]. http://www.sciencemag.org/cgi/content/full/290/5500/2323.

[6]BELKIN M， NIYOGO P. Laplacian eigenmaps for dimensionality reduction and data representation[J]. Neural Computation， 2003，15(6):1373-1396.

[7]HE Xiao-fei， NIYOGI P. Locality preserving projections[C]//Advances in Neural Information Processing Systems. Cambridge: MIT Press， 2004:327-334.