一種快速的統計不相關LDA求解算法

謝玉凱，盧桂馥

(安徽工程大學計算機與信息學院，安徽 蕪湖 241000)

?

一種快速的統計不相關LDA求解算法

謝玉凱，盧桂馥

(安徽工程大學計算機與信息學院，安徽 蕪湖 241000)

為進一步提高ULDA算法的求解效率，提出了一種新的快速的統計不相關LDA求解算法(ULDA/new)。ULDA/new只需對一個(c-1)×(c-1)的矩陣進行一次特征值分解就可以求得所有的投影向量(c指的是樣本量類別數)，從而進一步大幅度地提高了計算效率。理論分析和在圖像庫上的試驗表明，ULDA/new與現有的ULDA求解算法在理論上是等價的，其識別率相同，但遠比現有的ULDA算法要高效。

特征提??；線性鑒別分析；統計不相關LDA；QR分解

基于Fisher準則線性鑒別分析(Linear Discriminant Analysis, LDA)[1]是一種經典的特征抽取算法，在模式識別和機器學習領域中有著廣泛的應用[2]。LDA算法的基本思想是尋找一組投影向量集，使得原始樣本向這組向量集投影后的特征之間的類內的距離最小，而類間的距離最大。

在1975年，Foley等[3]發展了經典的LDA，提出了Sammon最佳鑒別平面的技術，該方法找到的投影向量是相互垂直的。Foley等提出的方法只能用于解決2類問題，進一步的，Duchene等[4]推廣了Foley等的方法，并給出了適合于多類問題的正交向量集的求解公式。雖然Foley等和Duchene等的算法求得的投影向量是相互垂直的，但并不能保證得到的特征是統計不相關的，為了解決這一問題，Jin等[5，6]提出了統計不相關LDA(Uncorrelated LDA, ULDA)算法。與Foley等和Duchene等算法求得的投影向量集不同，ULDA算法求得的投影向量集是相互共軛正交的，并且利用ULDA算法得到的特征是統計不相關的。

Jin等雖然在文獻[6]中給出了求解統計不相關投影向量集的精確算法，但是需迭代求解，較為復雜，所耗費的計算量較大。當總體散布矩陣非奇異時，Ye等[7，8]證明了ULDA算法求得的投影向量集與傳統LDA算法求得的投影向量集是等價的。對于模式識別和機器學習中經常遇到高維小樣本問題，由于總體(或類內)散布矩陣往往是奇異的，使得因此Jin等的ULDA算法難以直接計算。因此，Ye等[7]對ULDA算法進行了進一步地推廣，使得其能應用于高維小樣本問題。通過對3個散度矩陣同時對角化，Ye等提出了一種新的ULDA求解算法(稱為ULDA/SVD)，Ye等的求解算法可以一次性地求得所有的投影向量，使得其算法復雜度比Jin等的求解算法有了大幅降低。雖然Ye等的ULDA求解算法可以一次性的求得所有的投影向量，但是其求解算法需進行多次奇異值分解(Singular Value Decomposition, SVD)，與矩陣的QR分解相比，對矩陣進行奇異值分解的效率較低[9]。為此，Chu等[10]提出了一種基于QR分解的ULDA求解算法(稱為ULDA/MQR)，使得算法復雜度得到了進一步地降低。但是，Chu等的求解算法需進行多次QR分解。為了進一步地提高計算效率，最近，Chu等[11]提出了一種計算效率更高的ULDA求解算法(稱為ULDA/SQR)，該算法只需進行一次QR分解，從而進一步地降低了算法復雜度。對ULDA/SQR算法進行分析可以發現，ULDA/SQR需對所有樣本組成的矩陣進行QR分解，使得當樣本數較多時，其計算效率仍較低。

為了降低ULDA算法的算法復雜度，筆者設計了一種新的快速的ULDA求解算法(稱為ULDA/new)。

1 統計不相關LDA算法

(1)

(2)

=Sb+Sw

(3)

LDA算法的目標函數為：

(4)

式中，G為所有投影向量組成的投影矩陣； trace(?)表示求矩陣的跡。

(5)

式中， (?)+表示求矩陣的偽逆。

利用奇異值分解，通過對類內、類間和總體散布矩陣同時對角化，Ye等在文獻[7]設計了ULDA的求解算法(稱為ULDA/SVD)，其算法復雜度為：

14dn2+4dnc+14nc2-2n3-2c3+O(dn)

為了提高ULDA算法的求解效率，Chu等[10]提出了另一種ULDA的求解算法(稱為ULDA/MQR)。ULDA/MQR主要通過QR分解而不是SVD分解來求解投影矩陣，由于當矩陣的大小相同時，QR分解要比SVD分解高效，從而使得ULDA/MQR的算法復雜度比ULDA/SVD的算法復雜度要低。ULDA/MQR的算法復雜度為：

對于高維小樣本問題，一般地，有d?n?c，因此ULDA/MQR的算法復雜度要低于ULDA/SVD。

最近，Chu等[11]又提出了一種更快的ULDA求解算法(稱為ULDA/SQR)。與ULDA/MQR相比，ULDA/SQR只需進行一次QR分解就可以求得投影矩陣，而ULDA/MQR則需進行多次QR分解才能求得最終的投影矩陣，從而進一步提高了ULDA的計算效率。ULDA/SQR的算法復雜度為：

2 新的快速的ULDA求解算法(ULDA/new)

對ULDA/SQR進行分析可知，ULDA/SQR需對所有樣本組成的矩陣進行QR分解，使得當樣本數較多時，其計算效率仍較低。為了進一步地提高ULDA算法的求解效率，筆者提出一種新的快速的ULDA求解算法，ULDA/new只需對一個(c-1)×(c-1)的矩陣進行一次特征值分解就可以求得最佳投影矩陣G，從而進一步大幅度地提高了計算效率。

(6)

其中， X1∈Rd；X2∈Rd×(c-1)；X3∈Rd×(n-c)。則有：

(7)

HTH=VΣVT

(8)

其中，V∈R(c-1)×(c-1)為特征向量矩陣；Σ∈R(c-1)×(c-1)為特征值矩陣，其特征值從大到小排列，且為對角矩陣。

則G=HVΣ-1即為ULDA的目標函數式(5)的解。

證明 由H的定義，有：

=0

(9)

=0

(10)

由式(10)可以得到：

GTSwG =Σ-1VTHTSwHVΣ-1

=0

(11)

由于：

St=Sb+Sw

(12)

故由式(12)、(11)、(7)和(9)可以得到：

GTStG =GTSbG+GTSwG

=GTSbG

=Σ-1VTHTHHTHVΣ-1

=Σ-1VTVΣVTVΣVTVΣ-1

=Ic-1

(13)

由式(13)可知， 即為ULDA的目標函數式(5)的解。

為了求出G，需先得到H，接下來考慮如何快速地求出H。為了求出H，需先得到X2和X3，而如果直接對式(6)進行矩陣相乘來求解X2和X3，則其算法復雜度為O(dn2)，計算效率較低。由于Wi是Householder矩陣，故其可以表示為：

(14)

由于：

(15)

而：

(16)

由于P為置換矩陣，因此，只需根據P交換相應的列就可以得到一個矩陣與P的乘積。與式(16)類似，由于W也為Householder矩陣，故一個矩陣與W相乘也可以轉化為矩陣與向量的乘積，從而降低算法復雜度。因此，根據式(6)來計算X2和X3的算法復雜度為O(dn)。

(17)

綜上所述，筆者提出的ULDA/new總結如下：

輸入：數據矩陣X。

輸出：投影矩陣G。

1)根據式(6)計算X2和X3；

3)根據式(17)計算H；

4)計算HTH及其相應的特征值分解HTH=VΣVT；

5)計算G=HVΣ-1。

由于對于高維小樣本問題，一般地，有d?n?c。很明顯，和ULDA/SVD，ULDA/MQR和ULDA/SQR求解算法相比，ULDA/new的算法復雜度要低的多。

3 試驗分析

為了驗證ULDA/new的有效性，筆者在AR人臉圖像庫進行了試驗，編程環境為MATLAB 2008，操作系統為Windows 7，試驗中使用的分類器是最近鄰分類器。

AR人臉數據庫包含126個人(70位男性，56位女性)的4000多張彩色人臉圖像，這些圖像由不同光照，不同表情和不同的遮擋情況下的正面人臉圖像組成。大部分人的圖像是在相隔2周的時間下拍攝的2個像集。試驗中采用了其中120個人(65位男性，55位女性)的26幅人臉圖像，共計3120幅人臉圖像，圖像處理成120×80的形式。圖1為AR人臉圖像庫中某人的26幅圖像。

圖1 AR人臉庫中的26幅圖像

下面比較ULDA/new和ULDA/SVD，ULDS/MQR以及ULDA/SQR等統計不相關LDA求解算法的識別性能。隨機在AR人臉庫庫中選擇i(i=7,8)幅圖像作為訓練樣本，剩余的圖像作為測試樣本。試驗重復了20次，結果見表1，表中給出了20次試驗的平均識別率和標準方差。從表1可以看出，新的ULDA求解算法ULDA/new與其他幾種ULDA求解算法的識別率相同，這也驗證ULDA/new與其余幾種ULDA求解算法是等價的。

表1 在AR人臉庫中不同方法的識別率對比

接下來比較ULDA/new和其他ULDA求解算法的運行時間。表2記錄了各種不同ULDA求解算法在AR人臉庫上20次所需的平均時間。從表2可以看出，新的ULDA求解算法ULDA/new的運行時間要比其余幾種ULDA求解算法要小的多，這與前面的算法復雜度分析是一致的。

表2 不同算法運行時間比較

4 結語

介紹了統計不相關LDA算法，提出了一種快速的統計不相關LDA求解算法。該算法對一個(c-1)×(c-1)的矩陣進行一次特征值分解就可以求得所有的投影向量，大幅度地提高了計算效率。該算法與現有的ULDA算法相比雖然識別率相同，但運行時間上要小的多。

[1]Fisher R A.The use of multiple measurements in taxonomic problems [J].Annals of Eugenics, 1936,7:178～188.

[2] Duda R O, Hart P E, Stork D G. Pattern Classification[M] .2nd ed. John Wiley & Sons, New York, 2000.

[3] Foley D H, Sammon J W J. An optimal set of discriminant vectors [J].IEEE Trans. on Computers, 1975,24 (3):281～289.

[4] Duchene J, Leclercq S. An optimal Transformation for discriminant and principal component analysis [J].IEEE Trans. Pattern Analysis and Machine Intelligence, 1988,10 (6):978～983.

[5] Jin Z, Yang J Y, Tang Z M, et al. A theorem on the uncorrelated optimal discriminant vectors [J], Pattern Recognition, 2001,34 (10):2041～2047.

[6] Jin Z, Yang J Y, Hu Z S, et al. Face recognition based on the uncorrelated discriminant transformation [J].Pattern Recognition, 2001,34 (7):1405～1416.

[7] Ye J.Characterization of a family of algorithms for generalized discriminant analysis on undersampled problems [J].Journal of Machine Learning Research, 2005(6):483～502.

[8] Ye J, Janardan R, Li Q, et al. Feature reduction via generalized uncorrelated linear discriminant analysis [J].IEEE Trans Knowledge and Data Engineering, 2006,18 (10):1312～1322.

[9] Golub G H, Loan C F V. Matrix Computations[M]. 3rd ed. The Johns Hopkins University Press,1996.

[10] Chu D, Goh S T, Hung Y S. Charcterization of all solutions for undersampled uncorrelated linear discriminant analysis problems [J].SIAM J. Matrix Analysis and Applications, 2011,32 (3):820～844.

[11] Chu D, Liao L Z, Ng M K P, et al. Incremental linear discriminant analysis: A fast algorithm and comparisons [J].IEEE Trans on Neural Networks and Learning Systems, 2015,26 (11):2716～2735.

[12] Chu D, Thye G S. A new and fast implementation for null space based linear discriminant analysis [J].Pattern Recognition, 2010,43 (4):1373～1379.

[編輯] 洪云飛

2016-05-17

國家自然科學基金項目(61572033 , 71371012)；安徽高校自然科學研究項目重大項目(KJ2015ZD08)；教育部人文社會科學規劃項目(13YJA630098)。

謝玉凱(1990-)，男，碩士生，現主要從事計算機視覺方面的研究工作。

盧桂馥(1976-)，男，博士(后)，副教授，現主要從事人工智能、模式識別方面教學與研究工作；E-mail:luguifu_jsj@163.com。

TP391

A

1673-1409(2016)25-0008-06

[引著格式]謝玉凱，盧桂馥.一種快速的統計不相關LDA求解算法[J].長江大學學報(自科版)，2016,13(25)：8～13.