張建文, 劉新國(guó)

(中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山東 青島 266100)

?

線性判別分析的迭代解法及其應(yīng)用?

張建文, 劉新國(guó)

(中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山東 青島 266100)

線性判別分析(LDA)作為一種降維技術(shù)，已成功應(yīng)用于許多分類問題中，如語(yǔ)音識(shí)別、人臉識(shí)別、信息提取等領(lǐng)域。本文研究并改進(jìn)求解跡比問題的兩種主要方法：二分法、迭代跡比法(ITR法)。主要研究成果有：給出了一種基于線性插值的求解非線性方程二分法的改進(jìn)算法；對(duì)這兩種迭代方法與基于比跡準(zhǔn)則的方法進(jìn)行比較；對(duì)于ITR算法，選擇好的初始迭代矩陣使得算法的收斂速度有明顯的提高；分析了組內(nèi)樣本的相關(guān)性對(duì)識(shí)別精度的影響。

線性判別分析；迭代解；跡比問題

線性判別分析(LDA)是一種重要的統(tǒng)計(jì)學(xué)方法上的一種分析方法，已經(jīng)廣泛應(yīng)用于醫(yī)學(xué)的患者疾病分級(jí)以及人臉識(shí)別、模式識(shí)別、文本分類等領(lǐng)域。

針對(duì)小樣本問題以及由數(shù)據(jù)維數(shù)高帶來的計(jì)算復(fù)雜性問題，近年來提出了很多基于LDA的判別分析方法，包括PCA+LDA[7,9-10]，正則化LDA[8]，廣義逆LDA，LDA/GSVD[11]等。這些方法均是基于比跡準(zhǔn)則而設(shè)計(jì)的。

Guo[12]通過廣義變換提出跡比問題和跡差分問題，給出了一種基于二分法的迭代算法。但是該算法收斂較慢，且不穩(wěn)定。Wang提出了一種更為有效的算法[13](ITR算法)，該算法穩(wěn)定，收斂較快。近期還提出了ITR算法的改進(jìn)[14-16]。

本文研究跡比問題的求解及應(yīng)用，所做的主要工作包括以下幾個(gè)方面：

(1)選擇好的初始迭代矩陣提高ITR算法精度和速度；

(2)分析組內(nèi)相關(guān)性對(duì)算法精度的影響；

(3)針對(duì)高維數(shù)據(jù)，對(duì)算法進(jìn)行了改進(jìn)，提高了效率。

1 線性判別分析

給定一個(gè)樣本數(shù)據(jù)矩陣A∈Rm×n，尋找一個(gè)線性變換WT∈Rl×m，使得A的每一列ai，從m維空間中映射到l維空間中，即

WT:ai∈Rm→yi=WTai∈Rl,l<

設(shè)樣本數(shù)據(jù)矩陣A分為k類，

在判別分析中，定義如下3個(gè)矩陣，分別為類間、類內(nèi)、總體散度矩陣：

顯然，上述3個(gè)矩陣滿足以下關(guān)系式：

St=Sw+Sb。

經(jīng)過線性變換，在低維空間中可以得到類間、類內(nèi)、總體散度矩陣為

給定2個(gè)半正定矩陣Sp∈Rm×m,Sl∈Rm×m，比跡問題就是尋找一個(gè)m×l(l

(1)

當(dāng)Sp=Sb,Sl=Sw時(shí)，(1)就是經(jīng)典的LDA問題。

這一問題可以通過求解廣義特征值問題Sbwk=βkSwwk得到解決。其中βk是第k個(gè)最大的廣義特征值，矩陣W是由前l(fā)個(gè)最大特征值對(duì)應(yīng)的特征向量構(gòu)成。

本文要討論的是求解以下跡比最優(yōu)化問題：

(2)

2 線性判別分析的迭代解法及其改進(jìn)

定理2.1[12]跡比問題等價(jià)于求解下述跡差分問題：

求跡差分函數(shù)的零點(diǎn)λ*

即f(λ*)=0，則可以由下式計(jì)算：

定理2.2[12]假設(shè)A為實(shí)對(duì)稱矩陣，則滿足

其中λ1≥λ2≥…≥λm為A的m個(gè)特征值。假如φ1,φ2,…,φm為λ1,λ2,…,λm對(duì)應(yīng)的單位正交特征向量，則有

由以上定理可知，求解跡比問題可轉(zhuǎn)化為求解跡差分問題。

2.1 對(duì)二分法收斂速度的改進(jìn)

Guo等在文獻(xiàn)[12]中提出了一種基于二分法的迭代方法，與基于比跡準(zhǔn)則的方法相比較，識(shí)別率有明顯提高。但是，二分法的收斂速度較慢，要求的精度越高，需迭代的次數(shù)也越來越多，所以此方法須進(jìn)一步改進(jìn)。

文獻(xiàn)[17]提出了一種基于線性插值的求解非線性方程二分法的改進(jìn)方法，其基本思想是在每進(jìn)行一次平分隔根區(qū)間后，接著進(jìn)行一次線性插值，然后根據(jù)插值得到的點(diǎn)處的函數(shù)值與中點(diǎn)處的函數(shù)值進(jìn)行比較，可以得到有根區(qū)間，由此取得的區(qū)間均小于基于二分法取得的區(qū)間，從而加快了收斂速度。

結(jié)合文獻(xiàn)[17]以及本文問題，給出改進(jìn)的二分法，具體算法如下：

算法2.1

(i)令λ1=0，λ2=1，λ=(λ1+λ2)/2；

(iii)計(jì)算f(λ1),f(λ2),f(λ)；

(1)若f(λ)<0，對(duì)點(diǎn)λ1與λ進(jìn)行線性插值，則得到直線與x軸的交點(diǎn)c，其表達(dá)式為：

(2)若f(λ)>0，對(duì)點(diǎn)λ2與λ進(jìn)行線性插值，則得到直線與x軸的交點(diǎn)c，其表達(dá)式為：

(iv)λ*=λ；

從而W為Sb-λ*St的前l(fā)個(gè)最大特征值對(duì)應(yīng)的特征向量組成。

2.2ITR方法

Wang在文獻(xiàn)[13]提出一種有效算法(ITR)，簡(jiǎn)要概述如下：

算法2.2

(i)初始化W為任意的列正交矩陣；

(iii)構(gòu)造跡差分問題

(iv)W*是由Sb-λSt的前l(fā)個(gè)最大特征值對(duì)應(yīng)的特征向量構(gòu)成，用W*更新W；

(v)迭代(ii)-(iv)，直至收斂。

2.2.1 初始點(diǎn)策略 前述ITR算法選取任意的列正交矩陣為初始點(diǎn)。我們選取比跡問題的解作為ITR的初始迭代矩陣。數(shù)值實(shí)驗(yàn)結(jié)果表明，這一策略可以提高ITR的收斂速度，具體結(jié)果見實(shí)驗(yàn)部分。

2.2.2 組內(nèi)相關(guān)性對(duì)算法精度的影響 訓(xùn)練樣本集A=[A1,…,Ak]，Ak代表一個(gè)子類。如果分類較精確，則Ai的列向量幾乎線性相關(guān)，樣本之間的特征差異不明顯，不能有效的表征類別信息。從訓(xùn)練集表征的角度來看，樣本選擇可以有效的精簡(jiǎn)訓(xùn)練集，去除相似、重復(fù)、噪聲、以及信息冗余的樣本，實(shí)現(xiàn)以小規(guī)模樣本子集來表征整體訓(xùn)練集分布。子空間樣本選擇算法如下[18]：

算法2.3 設(shè)樣本包含S個(gè)樣本，已選樣本集Sl，l是已選擇樣本數(shù)，S=[x1,…,xn]。

(ii)對(duì)于?xp∈S/S1，計(jì)算xp到子空間的距離平方d2(xp,span(S1))。則

令mxd=d2(zl+1,span(S1))。

(iii)若mxd>ε，則Sl=S∪zl+1，更新l=l+1；否則退出。

(iv)返回(ii)，迭代(ii)-(iii)，直至l=m。

由文獻(xiàn)[18]可知，問題最終可以轉(zhuǎn)化為

d2(xp,span(S1))=(xp,xp)-kTK-1k。

k=((z1,xp),(z2,xp),…,(zl,xp))T。

上述選擇方法不僅能夠很好的反映樣本分布，而且使得選擇的樣本對(duì)其他樣本的重構(gòu)誤差迅速減少，選擇的樣本是線性無關(guān)的。

由于矩陣S與λ有關(guān)，因此所有的特征值與特征向量實(shí)際上是關(guān)于λ的函數(shù)，所以把它們寫做λ的函數(shù)βi(λ),wi(λ)更合適。

引理2.1[14]如果β(λ)為S(λ)=Sb-λSt的單特征值，w(λ)為對(duì)應(yīng)的單位特征向量(w(λ)=1)，則特征值的導(dǎo)數(shù)為

β′(λ)=-wT(λ)Sbw(λ)≤0。

(3)

引理2.1可以使用一階泰勒展開式來估計(jì)βk在λt處的特征值。

(4)

(5)

Jia在文獻(xiàn)[14]中給出了該方法的算法流程。

算法2.4

(i)初始化λt=0,t=0；

(ii)Sb-λtSt的特征值分解；

(iii)計(jì)算(4)(5)式；

該算法與ITR算法不同之處在于步驟(iv)，ITR算法是選取矩陣Sb-λSt最大的l個(gè)特征值對(duì)應(yīng)的特征向量，然而f(λ)=0的解并不一定是由這l個(gè)特征向量組成。因此，本算法在每一次迭代過程中得到的跡比值λ往往要大于ITR算法所得，收斂更快。

因?yàn)樯婕昂粗康呐判?，該算法的?shí)現(xiàn)比較困難。結(jié)合文獻(xiàn)[15-16，19]，針對(duì)步驟(iv)，設(shè)計(jì)算法2.5如下：

(iii)按降序排列score(i),i=1,2,…,m；

(iv)取前l(fā)個(gè)最大的score(i)對(duì)應(yīng)的向量wi，組成W=[wi1,wi2,…,wil]；

(vi)λ0=λ1；

從上面可以看出，該算法無需計(jì)算特征值分解，且相對(duì)于特征值分解而言，計(jì)算量可以忽略。

3 實(shí)驗(yàn)結(jié)果與分析

本文使用ORL人臉庫(kù)和YALE人臉庫(kù)來測(cè)試算法性能。ORL人臉庫(kù)由劍橋大學(xué)ATT實(shí)驗(yàn)室創(chuàng)建，包含40人，共400張面部圖像，尺寸大小為112×92像素大小。為便于計(jì)算，大小選為56×46，選取200張為訓(xùn)練集，余下為測(cè)試集。YALE人臉庫(kù)包含15位志愿者的165張人臉圖像，每人各有11幅圖像，尺寸為320×243像素大小。采用的分類方法為3階近鄰分類法(3-NearestNeighbor)。

3.1 改進(jìn)前后二分法收斂速度比較

從表中可以看出，在相同的誤差范圍內(nèi)，改進(jìn)后的二分法要比之前的二分法迭代的次數(shù)明顯減少，收斂速度比較快，說明了該方法的有效性。

3.2 初始迭代矩陣的選擇對(duì)精度的影響

表1 算法的收斂速度比較(迭代次數(shù))

(1)基于跡比最優(yōu)化準(zhǔn)則的識(shí)別率要高于基于比跡最優(yōu)準(zhǔn)則，同時(shí)也說明了比跡問題的最優(yōu)解并不是跡比問題的最優(yōu)解；

(2)選擇好的初始迭代矩陣使得算法的求解速度有明顯的提高。

3.3 組內(nèi)相關(guān)性對(duì)精度的影響

實(shí)驗(yàn)選用2組數(shù)據(jù)：ORL人臉庫(kù)，大小為56×46，從每組10個(gè)樣本中選取5個(gè)為訓(xùn)練集，余下為測(cè)試集；YALE人臉庫(kù)，大小為64×64，從每組11個(gè)樣本中選取5個(gè)為訓(xùn)練集，其余6個(gè)為測(cè)試集(ITR1表示隨機(jī)選擇樣本，ITR2表示選擇樣本后的ITR算法)。

表2 不同初始迭代矩陣對(duì)識(shí)別率與迭代次數(shù)的影響

表3 樣本相關(guān)性對(duì)精度的影響

從表中可以看出，樣本的相關(guān)性對(duì)識(shí)別精度有重要的影響。選擇線性無關(guān)的樣本，將會(huì)提高識(shí)別率，特別是對(duì)于大規(guī)模數(shù)據(jù)集的樣本識(shí)別中，識(shí)別樣本個(gè)數(shù)增多，存儲(chǔ)矩陣所需的內(nèi)存空間要求也增加。因此，用盡可能少的樣本來取得更高的效率，顯得極為重要，這就需要篩選好的樣本組成訓(xùn)練集。

3.4 改進(jìn)前后的ITR算法判別性能比較

雖然二種算法的識(shí)別率是一樣的，但是從表中可以看出，改進(jìn)后的ITR算法(ITR1)的迭代次數(shù)比ITR算法少，CPU花費(fèi)時(shí)間也明顯少于ITR算法。說明改進(jìn)后的ITR算法的收斂速度高于ITR，效率更高，優(yōu)于ITR算法。

表4 收斂速度的比較

4 結(jié)語(yǔ)

本文針對(duì)二分法收斂較慢的問題，在每次迭代之后增加了一次線性插值，提高了其收斂速度。分析了初始迭代陣的選擇、組內(nèi)樣本相關(guān)性對(duì)ITR算法精度的影響，給出了改進(jìn)后的ITR算法，并取得了很好的識(shí)別效果。

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

[2] Sammon J W. An optimal discriminant plane [J]. IEEE Trans Comput, 1970, 19: 826-829.

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

[4] Tian Q. Image classification by the Foley-Sammon transform [J]. Opt Eng, 1986, 25(7): 834-839.

[5] Hong ZQ. Algebraic feature extraction of image for recognition [J]. Pattern Recognition, 1991, 24(3): 211-219.

[6] Liu K, Cheng Y Q, Yang J Y. An efficient algorithm for Foley-Sammon optimal set of discriminant vectors by algebraic method [J]. Int J Pattern Recognit Artif Intell, 1992, 6(5): 817-829.

[7] Sweet D L, Weng J. Using discriminant eigenfeatures for image retrieval [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1996, 18(8): 831-836.

[8] Friedman J H. Regularized discrimination analysis [J]. Journal of the American Statistical Association, 1989, 84(405): 165-175.

[9] Belhumeur P N, Hespanha J P, Kriegman D J. Eigenfaces vs FIsherfaces:recognition using class specific linear projection [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1997, 23(2): 711-720.

[10] Howland P, Park H. Equivalence of several two-stage methods for linear discriminant analysis [C]. Florida： Fourth SIAM International Conference on Data Mining, 2004.

[11] Howland P, Jeon M, Park H. Structure preserving dimension reduction for clustered text data based on the generalized singular value decomposition [J]. SIAM J Matrix Anal Appl, 2003, 25: 165-179.

[12] Guo Y, Li S, Shu T, Wu L. A generalized Foley-Sammon transform based on generalized fisher discriminant criterion and its application to face recognition [J]. Pattern Recognition Letters, 2003, 24(1): 147-158.

[13] Wang H, Yan S, Xu D， Huang T S. Trace ratio vs ratio trace for dimensionality reduction [J]. Proceeding of conference on Computer Vision and Pattern Recognition(CVPR), 2007: 1-8.

[14] Jia YQ, Nie F P， Zhang C S. Trace ratio problem revisited [J]. IEEE Transactions on Neural Networks, 2009, 20(4): 729-735.

[15] Nie FP, Xiang SM, Jia Y Q, Zhang C S. Semi-supervised orthogonal discriminant analysis via label propagation [J]. Pattern Recognition, 2009, 42: 2615-2627.

[16] Nie F P, Xiang S M. Trace ratio criterion for feature selection [C]. Chicago： Proceeding of the Twenty-Third AAAI Conference on artificial Intelligence, 2008: 671-176.

[17] 王國(guó)棟, 張瑞平, 沐愛勤, 等. 基于線性插值的求解非線性方程二分法改進(jìn) [OL]. 中國(guó)科技論文在線, http://www.paper. edu. cn/releasepaper/content/200904-657.

[18] 周曉飛, 姜文瀚, 楊靜宇. 基于子空間樣本選擇的最近凸包分類器 [J]. 計(jì)算機(jī)工程, 2008, 34(12): 167-168.

[19] Zhao M B, Zhang Z, Chow W S. ITR-Score algorithm: an efficient trace ratio criterion based algorithm for supervised dimensionality reduction [C]. Portland： Proceeding of International Joint conference on Neural Networks, 2011: 145-152.

[20] Ye J. Characterization of a family algorithm for generalized discriminant analysis on undersampled problems [J]. J Mach Learn Res, 2005, 6: 483-502.

[21] Chu D L, Goh S T. A new and fast orthogonal linear discriminant analysis on undersampled problems [J]. SIAM J SCI Comput, 2010, 32(4): 2274-2297.

[22] 謝達(dá)東, 吳及, 王作英. 線性判別分析在漢語(yǔ)語(yǔ)音識(shí)別中的應(yīng)用 [J]. 計(jì)算機(jī)工程與應(yīng)用, 2003, 23: 1-8.

[23] 胡煜. 線性判別分析和降維方法應(yīng)用于基因芯片數(shù)據(jù)分析 [J]. 甘肅聯(lián)合大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008, 22(1): 29-33.

[24] 魯曉春, 施先亮. 應(yīng)用Fisher線性判別分析法評(píng)估物流規(guī)劃項(xiàng)目 [J]. 分析與決策, 2007, 26(8): 76-79.

AMS Subject Classification: 93B05

責(zé)任編輯 陳呈超

The Iterative Solution of Linear Discriminant Analysis and Its Application

ZHANG Jian-Wen,LIU Xin-Guo

(School of Mathematical Sciences, Ocean University of China, Qingdao 266100, China)

Linear discriminant analysis(LDA) has been successfully used as a dimensionality reduction technique to many classification problems,such as speech recognition,face recognition and information retrieval.We study some efficient iterative procedures to directly solve the trace ratio optimization problem,namely,bisection method,iterative trace ratio.We made some improvements to these methods.The main research achievement are as follows:we present an improved bisection method based on linear interpolation for solving nonlinear equation;we compare these two methods against ratio trace solution to LDA;for the ITR algorithm,a good choice of initial iterative matrix makes the convergence speed of our method improved significantly;we analyze the influence of the correlation of sample to recognition accuracy.

linear discriminant analysis；iterative solution; trace ratio problem

國(guó)家自然科學(xué)基金項(xiàng)目(11371333)資助

2013-07-10；

2014-01-15

張建文(1987-)，男，碩士生。E-mail:ahzhang1108@163.com

O212.5

A

1672-5174(2015)11-119-06

10.16441/j.cnki.hdxb.20130328