国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

404 Not Found


nginx
404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx

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

2016-11-24 01:07:25謝玉凱盧桂馥
關(guān)鍵詞:識別率復(fù)雜度人臉

謝玉凱,盧桂馥

(安徽工程大學(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只需對一個(gè)(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個(gè)散度矩陣同時(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只需對一個(gè)(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)的列就可以得到一個(gè)矩陣與P的乘積。與式(16)類似,由于W也為Householder矩陣,故一個(gè)矩陣與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個(gè)人(70位男性,56位女性)的4000多張彩色人臉圖像,這些圖像由不同光照,不同表情和不同的遮擋情況下的正面人臉圖像組成。大部分人的圖像是在相隔2周的時(shí)間下拍攝的2個(gè)像集。試驗(yàn)中采用了其中120個(gè)人(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求解算法。該算法對一個(gè)(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);教育部人文社會(huì)科學(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.

猜你喜歡
識別率復(fù)雜度人臉
有特點(diǎn)的人臉
基于類圖像處理與向量化的大數(shù)據(jù)腳本攻擊智能檢測
基于真耳分析的助聽器配戴者言語可懂度指數(shù)與言語識別率的關(guān)系
一種低復(fù)雜度的慣性/GNSS矢量深組合方法
三國漫——人臉解鎖
提升高速公路MTC二次抓拍車牌識別率方案研究
求圖上廣探樹的時(shí)間復(fù)雜度
高速公路機(jī)電日常維護(hù)中車牌識別率分析系統(tǒng)的應(yīng)用
某雷達(dá)導(dǎo)51 頭中心控制軟件圈復(fù)雜度分析與改進(jìn)
出口技術(shù)復(fù)雜度研究回顧與評述
404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx
木兰县| 克山县| 平谷区| 万安县| 当雄县| 平顶山市| 方正县| 泾阳县| 百色市| 敖汉旗| 乐平市| 石屏县| 虹口区| 金阳县| 喀喇沁旗| 海南省| 甘孜| 通道| 平阴县| 崇左市| 石阡县| 宣威市| 通州区| 峨眉山市| 自治县| 涪陵区| 临邑县| 抚州市| 威宁| 遂宁市| 满城县| 砚山县| 昆山市| 合川市| 东乡族自治县| 东光县| 丽江市| 清原| 五峰| 洛扎县| 麻江县|