線性判別分析的迭代解法及其應用?

張建文, 劉新國

(中國海洋大學數學科學學院，山東 青島 266100)

?

線性判別分析的迭代解法及其應用?

張建文, 劉新國

(中國海洋大學數學科學學院，山東 青島 266100)

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

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

線性判別分析(LDA)是一種重要的統計學方法上的一種分析方法，已經廣泛應用于醫學的患者疾病分級以及人臉識別、模式識別、文本分類等領域。

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

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

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

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

(2)分析組內相關性對算法精度的影響；

(3)針對高維數據，對算法進行了改進，提高了效率。

1 線性判別分析

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

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

設樣本數據矩陣A分為k類，

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

顯然，上述3個矩陣滿足以下關系式：

St=Sw+Sb。

經過線性變換，在低維空間中可以得到類間、類內、總體散度矩陣為

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

(1)

當Sp=Sb,Sl=Sw時，(1)就是經典的LDA問題。

這一問題可以通過求解廣義特征值問題Sbwk=βkSwwk得到解決。其中βk是第k個最大的廣義特征值，矩陣W是由前l個最大特征值對應的特征向量構成。

本文要討論的是求解以下跡比最優化問題：

(2)

2 線性判別分析的迭代解法及其改進

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

求跡差分函數的零點λ*

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

定理2.2[12]假設A為實對稱矩陣，則滿足

其中λ1≥λ2≥…≥λm為A的m個特征值。假如φ1,φ2,…,φm為λ1,λ2,…,λm對應的單位正交特征向量，則有

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

2.1 對二分法收斂速度的改進

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

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

結合文獻[17]以及本文問題，給出改進的二分法，具體算法如下：

算法2.1

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

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

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

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

(iv)λ*=λ；

從而W為Sb-λ*St的前l個最大特征值對應的特征向量組成。

2.2ITR方法

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

算法2.2

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

(iii)構造跡差分問題

(iv)W*是由Sb-λSt的前l個最大特征值對應的特征向量構成，用W*更新W；

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

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

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

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

(ii)對于?xp∈S/S1，計算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。

由文獻[18]可知，問題最終可以轉化為

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

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

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

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

引理2.1[14]如果β(λ)為S(λ)=Sb-λSt的單特征值，w(λ)為對應的單位特征向量(w(λ)=1)，則特征值的導數為

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

(3)

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

(4)

(5)

Jia在文獻[14]中給出了該方法的算法流程。

算法2.4

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

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

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

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

因為涉及含未知量的排序，該算法的實現比較困難。結合文獻[15-16，19]，針對步驟(iv)，設計算法2.5如下：

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

(iv)取前l個最大的score(i)對應的向量wi，組成W=[wi1,wi2,…,wil]；

(vi)λ0=λ1；

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

3 實驗結果與分析

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

3.1 改進前后二分法收斂速度比較

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

3.2 初始迭代矩陣的選擇對精度的影響

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

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

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

3.3 組內相關性對精度的影響

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

表2 不同初始迭代矩陣對識別率與迭代次數的影響

表3 樣本相關性對精度的影響

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

3.4 改進前后的ITR算法判別性能比較

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

表4 收斂速度的比較

4 結語

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

[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] 王國棟, 張瑞平, 沐愛勤, 等. 基于線性插值的求解非線性方程二分法改進 [OL]. 中國科技論文在線, http://www.paper. edu. cn/releasepaper/content/200904-657.

[18] 周曉飛, 姜文瀚, 楊靜宇. 基于子空間樣本選擇的最近凸包分類器 [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] 謝達東, 吳及, 王作英. 線性判別分析在漢語語音識別中的應用 [J]. 計算機工程與應用, 2003, 23: 1-8.

[23] 胡煜. 線性判別分析和降維方法應用于基因芯片數據分析 [J]. 甘肅聯合大學學報(自然科學版), 2008, 22(1): 29-33.

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

AMS Subject Classification: 93B05

責任編輯 陳呈超

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

國家自然科學基金項目(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