一種快速的統(tǒng)計(jì)不相關(guān)LDA求解算法

謝玉凱，盧桂馥

(安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241000)

?

一種快速的統(tǒng)計(jì)不相關(guān)LDA求解算法

謝玉凱，盧桂馥

(安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241000)

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

特征提取；線性鑒別分析；統(tǒng)計(jì)不相關(guān)LDA；QR分解

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

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

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

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

1 統(tǒng)計(jì)不相關(guān)LDA算法

(1)

(2)

=Sb+Sw

(3)

LDA算法的目標(biāo)函數(shù)為：

(4)

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

(5)

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

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

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

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

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

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

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

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

(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的目標(biāo)函數(shù)式(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的目標(biāo)函數(shù)式(5)的解。

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

(14)

由于：

(15)

而：

(16)

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

(17)

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

輸入：數(shù)據(jù)矩陣X。

輸出：投影矩陣G。

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

3)根據(jù)式(17)計(jì)算H；

4)計(jì)算HTH及其相應(yīng)的特征值分解HTH=VΣVT；

5)計(jì)算G=HVΣ-1。

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

3 試驗(yàn)分析

為了驗(yàn)證ULDA/new的有效性，筆者在AR人臉圖像庫進(jìn)行了試驗(yàn)，編程環(huán)境為MATLAB 2008，操作系統(tǒng)為Windows 7，試驗(yàn)中使用的分類器是最近鄰分類器。

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

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

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

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

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

表2 不同算法運(yùn)行時(shí)間比較

4 結(jié)語

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

[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

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

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

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

TP391

A

1673-1409(2016)25-0008-06

[引著格式]謝玉凱，盧桂馥.一種快速的統(tǒng)計(jì)不相關(guān)LDA求解算法[J].長江大學(xué)學(xué)報(bào)(自科版)，2016,13(25)：8～13.