基于無窮范數的二值線性判別分析

摘 要： 線性判別分析（LDA）是監督式的特征提取方法，在人臉識別等領域得到了廣泛應用。為了提高特征提取速度，提出了基于無窮范數的線性判別分析方法。傳統LDA方法將目標函數表示為類內散布矩陣和類間散布矩陣之差的或者商的L2范數，且通常需要涉及到矩陣求逆和特征值分解問題。與傳統方法不同，這里所提方法將目標函數表示為類內散布矩陣和類間散布矩陣之差的無窮范數，而且最優解是以迭代形式得到，避免了耗時的特征值分解。無窮范數使得到的基向量實現了二值化，即元素僅在-1和1兩個數字內取值，避免了特征提取時的浮點型點積運算，從而降低了測試時間，提高了效率。在ORL人臉數據庫和Yale數據庫上的實驗表明所提算法是有效的。

關鍵詞： 線性判別分析； 無窮范數； 二值化； 特征提取

中圖分類號： TN911?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2013）22?0024?04

0 引 言

線性判別分析（LDA）[1?3]是模式識別中降維和特征提取的一種非常流行的方法，該方法的大致思想是尋找一組投影基向量使得類間散布矩陣與類內散布矩陣的差或比率最大，該方法是基于L2范數完成的。

LDA最近幾年在很多領域得到了廣泛的應用，比如文獻[4]將LDA用于雷達對目標的識別，文獻[5]則將LDA用于腦電信號的提取和分類，得到良好的效果。雖然LDA解決了很多領域的問題，但該方法識別率仍然有待提高，于是，近年來研究人員提出了一些提高識別率的方法。比如，文獻[6]對傳統的LDA施加[p]范數，得到了[p]取不同值時的識別率，這對約束項的選取具有參考價值。文獻[7]提出基于旋轉不變的L1范數的判別標準，可以更好的描述類內的緊密度和類間的分離度。

上面提到的方法雖然都不同程度的提高了傳統LDA的識別率，但卻沒有提高特征提取的速度。為此，本文提出利用無窮范數代替傳統的L2范數對目標函數施加約束，同時采用類間散布矩陣和類內散布矩陣之差而非商作為目標函數，借鑒文獻[8]的最優化過程，避免了傳統方法訓練中耗時的特征值分解，得到了基向量的元素僅為-1和1，即實現了基向量的二值化，將該算法命名為BLDA。這樣的基向量在做特征提取時，避免了浮點型內積運算，從而降低了檢測時間，提高了效率，同時BLDA擁有與傳統LDA相近的識別率。最后，在Yale 和ORL人臉數據庫上進行的實驗，說明所提的算法是有效的。

1 現有LDA方法

LDA是一種有監督的特征提取方法，其基本思想是將有標簽的高維樣本[xi∈RD]通過變換矩陣[W=[w1，…，wd]∈RD×d]（其中[wi]和[xi]都是[D]維向量）映射為具有最佳可分離性的最佳子空間中的低維樣本[yi∈Rd]：

其中[d<=wTjxi=yij]得到的。

通常，變換矩陣[W]即其列向量[wi]（稱為[d]維子空間的基向量）是在某一約束條件下，根據某最佳可區分準則求解得到的。下面具體介紹兩種常見的準則：基于商的準則和基于差的準則。其中基于差的準則與本文所提方法最為相關。

1.1 基于商的LDA方法

本文所提方法正是在這種基于差的LDA上進行的。

2 所提BLDA

2.1 BLDA模型

注意到上述基于商和基于差的LDA方法得到的基向量[w]是任意實數，所以利用式從高維樣本[x∈RD]中提取其低維特征向量[y∈Rd]時，需要計算該高維樣本[x∈RD]和高維基向量[w∈RD]的浮點數內積[y=]。該內積的計算量較大，耗時較多。

本文所用算法得到的基向量中元素為-1或1，在進行上述內積時，只需找到基向量[w]中-1和1對應的測試數據[x]中的元素，然后相加即可得到降維后的樣本[y]。而傳統的LDA則是對[w]和[x]直接相乘，需要基向量[w]的每個元素與測試數據[x]對應位置的元素先分別進行乘法再將這些乘積相加，而浮點型數值乘法相對麻煩，所以本文所提算法可以大大降低測試時間，提高檢測效率，下面具體講解本文所提的算法。

于是，式（11）取最大值當且僅當[wi=?signwi]，其中[wi]表示向量[w]第[i]個元素。注意到最優解必須滿足[wpp=1]，[p=∞]，因此，第[k+1]次迭代的最優值為[wk+1=wwp]。其中[p=∞]，這樣就得到了式（10）的最優解。容易發現，這樣得到的基向量[w]只含-1和1兩個值。該算法在實現過程中需要先初始化[w]，對此本文采用隨機得到，但同樣必須滿足[w0pp=1]。

3 實驗結果

本文分別在ORL人臉數據庫和Yale人臉數據庫上對所提的BLDA進行驗證，觀察該算法與傳統LDA不同基向量數目時的識別率。同時，由于本文的算法實現了基向量的二值化（-1，1），測試時只用進行加法操作而避免了浮點型數值的乘法操作，大大降低了測試時間，提高了效率，本實驗將在ORL人臉數據庫和Yale數據庫比較兩種方法的測試時間。

3.1 ORL人臉數據庫

為了計算的簡便，本實驗將每張圖像的大小縮小至56×46，隨機選擇每個人5張人臉圖像作為訓練數據，另外5張作為測試數據，這樣測試數據和測試數據均為200張。圖 1顯示所提BLDA算法與傳統LDA的識別率和基向量數之間的關系。

從圖 1看到，本文所提的BLDA與傳統的LDA識別率相近，當基向量數目逐漸增加時，前者的識別率在某些點甚至比后者高。

當取不同數量的基向量時，測試時的計算量也不同，傳統的方法是基向量矩陣和測試數據矩陣直接相乘，例如，當取20個基向量時，測試時是一個20×2 576的矩陣和一個2 576×200的矩陣相乘，一共需要20×200×（2 576+2 575）=20 604 000次計算；當取50個基向量時，一共需要51 510 000次計算；當取[n]個基向量，需要1 030 200[n]次計算。而本文的BLDA算法由于基向量中元素僅為-1和1兩個數值，所以不用進行乘法運算，計算量就會減少大約 [12]，例如，對于20個基向量，運算量為20×200×2 575=10 300 000；當取[n]個基向量，運算量為515 000[n]。表1顯示了ORL人臉數據庫下兩種算法不同基向量的運算量。

從表 1看出，本文所提的BLDA比傳統的LDA少大約一半的計算量，這將使得前者的測試時間比后者大約少一半，表 2顯示兩種算法的測試時間。

3.2 Yale人臉數據庫

與ORL人臉數據庫相同，隨機選取每個人5張圖像作為訓練數據，另外5張作為測試數據，由于該數據庫有15個人，所以訓練數據和測試數據均為75張。表3和圖2顯示了兩種算法在Yale人臉數據庫下不同基向量數的識別率和測試時間。

從圖 2可以看出，在Yale人臉數據庫上所提算法仍然和傳統的LDA識別率相近，當基向量數目增加到一定時，兩種算法的識別率曲線基本重合。與ORL數據庫上的結果對比，Yale數據庫上有更好的識別效果，這是因為Yale數據庫的人臉樣本比ORL數據庫少，當取相同數目的基向量做測試時，前者識別率高于后者。表3顯示在Yale數據庫上，所提算法測試時間仍然大約是傳統的LDA的[12]。

綜合以上兩個在不同數據庫上的實驗，說明BLDA在保持識別率和傳統LDA識別率相近的情況下，實現了基向量的二值化，避免了浮點數值的乘法運算，從而減少了大約[12]的測試時間，提高了測試效率。

4 結 語

本文采用基于差的LDA，對目標函數中施加無窮范數約束項，在最優化過程中利用逐次線性化技術和Holder不等式定理，得到了二值化（-1，1）的基向量，在識別率與傳統LDA相近的情況下降低了運算量，減少了檢測時間。

參考文獻

[1] BELHUMEUR P N， HESPANHA J P， KRIEGMAN D. Eigenfaces vs. fisherfaces： recognition using class specific linear projection [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence， 1997， 19（7）： 711?720.

[2] MARTINEZ A， KAK A. PCA versus LDA [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence， 1997， 19（7）： 711?720.

[3] LI H F， JANG T， ZHANG K S. Efficient and robust feature extraction by maximum margin criterion [J]. IEEE Transactions on Neural Networks， 2006， 17（1）： 157?165.

[4] 吳秋榮，楊萬麟.基于NMFs?LDA的雷達目標距離像識別[J].現代電子技術，2007，30（19）：63?65.

[5] 劉紀紅，丁俊杰，邊洪亮.一種基于FPGA的腦電分類算法實現[J].現代電子技術，2012，35（20）：107?110.

[6] JAE H O， NOJUN K. Generalization of linear discriminant analysis using Lp?norm [J]. Pattern Recognition Letters， 2013， 34（6）： 679?685.

[7] LI X， HU W， WANG H， et al. Linear discriminant analysis using rotational invariant L1 norm [J]. Neurocomputing， 2010， 73（13/15）： 2571?2579.

[8] LIANG Z Z， XIA S X， YONG Z， et al. Feature extraction based on Lp?norm generalized principal component analysis [J]. Pattern Recognition Letters， 2013， 34（9）： 1037?1045.

[9] JOURNEE M， NESTEROV Y， RICHTARIK P， et al. Gene?

ralized power method for sparse principal component analysis [J]. Journal of Machine Learning Research， 2010， 11： 517?553.

[10] YANG W H. On generalized holder inequality [J]. Nonlinear Analysis， 1991， 16（5）： 489?498.