基于空間平滑的線性和線性判別分析

基于空間平滑的線性和線性判別分析

1基于滑變換的滑維算法線性評價分析（lda）作為一種典型的監(jiān)督、降水方法，廣泛應(yīng)用于人臉識別等領(lǐng)域。目標是找到有效的分類方向，將數(shù)據(jù)映射到低維空間后，平均類和平均類之間的散射度比盡可能大。然而，為了提取圖像特征，lda的定向操作破壞了圖像原有的空間結(jié)構(gòu)，忽視了圖像圖像之間的空間關(guān)系，并影響其識別性能。現(xiàn)在，空間信息的空間篩選過程主要有兩種方法。1）空間平滑的空間研究方法（sssl），具體地將空間拉普拉斯平滑懲罰規(guī)則轉(zhuǎn)換為目標空間研究的目標函數(shù)，以實現(xiàn)圖像空間結(jié)構(gòu)的使用。2）對于普通的歐位距離測量，為了測量圖像之間的相似性，這種方法是典型的圖像低于e0。imed不僅適用于直接嵌入分類算法進行成像，而且還可以確定與圖像相關(guān)的新的廣義圖像之間的位置關(guān)系。例如，拉普拉斯平滑變換（lst），并應(yīng)用于lda和其他低維算法。為了簡化描述，本工作將上述兩種類型的算法進行了線性評價方法（平面位線性評價方法，swda）和基于空間平面位移的線性評價方法（imeda）。SLDA和IMEDA作為兩種空間平滑算法,前者通過空間正則化將空間結(jié)構(gòu)信息加入LDA的目標函數(shù),圖像間的距離度量仍用歐氏距離,而后者則通過對距離的改造,用圖像歐氏距離(IMED)替代常用的歐氏距離,由此免去對目標函數(shù)的空間正則化.盡管SLDA和IMEDA以不同方式實現(xiàn)對空間結(jié)構(gòu)信息的利用,但具體實現(xiàn)時的目標是兩者均通過優(yōu)化平均類內(nèi)和平均類間散度之比獲得投影矩陣,然后將樣本空間投影到低維空間后,所得最壞類間散度(或分離度)并非最大.受Zhang等的最壞情況(最壞的類內(nèi)和類間散度)線性判別分析(Worst-CaseLinearDiscriminateAnalysis,WLDA)啟發(fā)和諸多被證明利于分類的“間隔”方法,如支持向量機,臨界Fisher分析等,本文針對SLDA和IMEDA,提出相應(yīng)的改進算法,具體是在基于約束平均而非最壞類內(nèi)散度上界的前提下,最大化最壞類間散度(或分離度),以使類間間隔盡可能大.但對此目標的優(yōu)化遇到挑戰(zhàn),因本文提出的改進算法比SLDA和IMEDA復雜,原有通過廣義特征值方程求解投影矩陣的方法不再有效.同時此優(yōu)化目標為非凸,自然增加求解難度.為此考慮將待解的投影方向w重新參數(shù)化為wwT=M形式,如此,能將原有非凸優(yōu)化問題轉(zhuǎn)化為線性約束和對M半正定約束下的凸半正定規(guī)劃(Semi-DefiniteProgramming,SDP)問題.從而可采用現(xiàn)成的半正定規(guī)劃SDP軟件包求解.可是,當處理諸如圖像等高維數(shù)據(jù)時,SDP的計算復雜度相當高.本文借鑒Ying等提出的特征值優(yōu)化的距離度量學習框架以解決此優(yōu)化問題,延伸出新的求解SLDA和IMEDA投影矩陣的學習方法,將它們分別稱為平均緊性約束下的最壞分離空間平滑線性判別分析(WorstSLDA,WSLDA)和平均緊性約束下的最壞分離空間平滑歐氏距離線性判別分析(WorstIMEDA,WIMEDA).此類方法將原本用SDP求解的凸優(yōu)化問題最終歸結(jié)為最小化對稱矩陣的最大特征值問題,通過融合SSSL、IMED(LST)、Frank-Wolfe優(yōu)化算法和Nesterov的優(yōu)化技術(shù)等,不僅降低計算復雜度,而且還避免諸多降維算法中需要求解完整特征值分解的問題.在Yale、AR和FERET標準人臉數(shù)據(jù)集上的實驗驗證WSLDA和WIMEDA具有比原算法更優(yōu)的分類性能.本文簡單回顧SLDA和IMEDA算法;繼而介紹平均緊性約束下的最壞分離空間平滑線性判別分析(WSLDA)和平均緊性約束下的最壞分離空間平滑歐氏距離線性判別分析(WIMEDA);然后進行實驗及其結(jié)果分析;最后總結(jié)全文,并給出下一步的研究方向.2平均編碼機表示假設(shè)有n張c類M×N人臉圖像可用,將它們用向量表示為X=[x1,x2,…xn],nk表示第k(1≤k≤c)類樣本的個數(shù),且n1+n2+…+nc=n,每類樣本用符號Πk表示.2.1空間平滑的傳統(tǒng)算法SSSL是用空間拉普拉斯懲罰作為正則化項嵌入至子空間學習的降維目標函數(shù)中,實現(xiàn)對圖像空間結(jié)構(gòu)信息的利用.其優(yōu)化目標如下:其中,W是(M×N)×(M×N)的對稱陣,D為對角陣,且Dii=∑jWij,α(0≤α≤1)用于控制平滑度,j(b)=‖Δ·b‖2=bTΔTΔb為離散化拉普拉斯平滑函數(shù)(詳見文獻).W作為權(quán)矩陣,不同的設(shè)置可得到不同的線性降維算法,如空間平滑的線性判別分析(SLDA),空間平滑的局部保持投影(SpatiallySmoothLocalityPreservingProjection,SLPP),空間平滑的鄰域保持嵌入(SpatiallySmoothNeigh-borhoodPreservingEmbedding,SNPE),空間平滑的臨界Fisher分析(SpatiallySmoothMarginalFisherAnalysis,SMFA)和空間平滑的局部判別嵌入(SpatiallySmoothLocalDiscriminantEmbedding,SLDE)等.在SLDA算法中,W對應(yīng)于此時,可驗證D=I.顯然式(1)最大化問題可通過求解式(2)的廣義特征值方程得到所期望的子空間或投影矩陣,即2.2維空間域中拉普拉斯矩陣的計算拉普拉斯平滑變換(LST)是一種圖像的降維方法,其將二維空間域的圖像映射成頻域上的一維向量,直接濾除高頻信息,平滑圖像.其典型的優(yōu)點為獨立于數(shù)據(jù)而僅與2D空間域相關(guān),且計算復雜度較低.圖像的LST通過以下3個步聚完成:step1根據(jù)圖像二維空間域,構(gòu)造拉普拉斯矩陣LMN,具體構(gòu)造方法見文獻;step2計算LMN的前k(0<k<MN)個最小特征值所對應(yīng)的特征向量step3令Γ=(e0,e1,…,ek-1),則g=ΓTf即為圖像f在低頻系數(shù)k下變換后的向量.樣本集X=[x1,x2,…,xn],經(jīng)變換后記為經(jīng)LST降維后的圖像用于LDA,即所謂的IMEDA,其優(yōu)化目標為其中,分別是變換空間后的類間散布矩陣和類內(nèi)散布矩陣,即3線性判別分析本節(jié)詳細介紹平均緊性約束下的最壞分離空間平滑線性判別分析(WSLDA)和平均緊性約束下的最壞分離空間平滑歐氏距離線性判別分析(WIMEDA).假設(shè)d×d的對稱矩陣和半正定矩陣空間分別表示為Sd和S+d,yi為樣本xi的類標號,Ss和Dd分別表示相似(類內(nèi))和非相似(類間)數(shù)據(jù)對,為方便敘述,將數(shù)據(jù)對(xi,xj)簡記為τ=(i,j),若X,Y∈Rd×n,記Tr(XTY)=〈X,Y〉,其中Tr(·)為矩陣的跡.3.1從圖像的結(jié)構(gòu)信息獲取SLDA的最終目標為分類,其通過最大化平均類間和平均類內(nèi)散度之比獲得投影矩陣,故優(yōu)化目標式(2)可近似為其中,故式(4)可寫為WSLDA的思想是約束平均類內(nèi)散度(或緊性),讓類間間隔盡可能大.故其優(yōu)化時無需考慮平均類間散度(或分離度),僅將最小類間間隔最大化,即可滿足分類需求.令M=bbT,則WSLDA的優(yōu)化目標可寫為從式(6)可看出:1)圖像的空間結(jié)構(gòu)信息被加入約束平均類內(nèi)散度(或緊性)的線性函數(shù)中以實現(xiàn)對其的利用;2)WSLDA的優(yōu)化目標,即在約束平均類內(nèi)散度(或緊性)的同時,最大化最壞類間散度(或分離度),其求解恰好落在Ying等提出的特征值優(yōu)化方法的框架里,故可通過其求解度量矩陣M,進而獲得投影矩陣.假設(shè)P={M∈S+d:Tr(M)=1},樣本集X=[x1,x2,…,xn],考慮優(yōu)化形如下式的凸目標問題:其中,Xτ和XSs均為使用樣本數(shù)據(jù)定義的半正定矩陣,顯然此目標可采用SDP軟件包求解,然而,SDP在處理高維數(shù)據(jù)時,計算復雜度相當高,而Ying等提出特征值優(yōu)化方法,將優(yōu)化目標轉(zhuǎn)化為式(8),巧妙地把SDP問題轉(zhuǎn)化成特征值問題,而最小化對稱矩陣的特征值問題又可采用近似的Frank-Wolfe算法求解(詳見算法1),具體推導和求解詳見文獻.此方法是一個一般性的框架,凡落入式(7)的優(yōu)化目標,均可被轉(zhuǎn)化為式(8)的形式,進而采用近似Frank-Wolfe算法求解其中的半正定矩陣S.其中,,且假設(shè)XSs可逆,為矩陣的最大特征值.3.2種新的分類目標與SLDA類似,IMEDA的最終目標也為分類,可通過最大化平均類間散度和平均類內(nèi)散度之比獲得投影矩陣,其優(yōu)化目標式(3)可進一步寫為WIMEDA的思想也不再繼承LDA的優(yōu)化框架,而是約束平均類內(nèi)散度(或緊性),最大化最壞類間散度(或分離度),進而獲得投影矩陣,從而達到分類目標.令M=wwT,則WIMEDA的優(yōu)化目標可寫為其中,,從式(10)可看出:1)LST是一種線性變換,故變換矩陣Γ最終可直接表示在度量矩陣中;2)WIMEDA中圖像的空間結(jié)構(gòu)信息體現(xiàn)在平滑變換里,其先把原有圖像作平滑變換,而后針對平滑后的圖像約束平均類內(nèi)散度(或緊性),并最大化最壞類間散度(或分離度),其優(yōu)化目標同樣滿足Ying等提出的框架,也可采用特征值優(yōu)化方法求解度量矩陣,進而獲得投影矩陣.4實驗與結(jié)果分析4.1實驗數(shù)據(jù)的獲取本實驗使用Yale、AR和FERET標準人臉數(shù)據(jù)集,相關(guān)信息見表1.在實驗中,從每類圖像中隨機選擇其中m張作為訓練樣本,剩下n張作為測試樣本(記為Gm/Pn),實驗重復執(zhí)行20輪,對不同子空間維數(shù)均采用最近鄰法分類,以最高平均正確識別率作為最終性能的衡量指標.4.2特征值空間算法與其他算法的比較實驗對SLDA、IMEDA、WSLDA和WIMEDA這4種算法在Yale、AR和FERET標準人臉數(shù)據(jù)集上的識別率進行比較,同時選取具有最優(yōu)的判別性能的正則化線性判別分析(RegularizedLinearDiscriminantAnalysis,RLDA)作為基線,與上述4種算法進行比較,結(jié)果見表2.觀測結(jié)果如下:1)嵌入圖像空間結(jié)構(gòu)信息的空間算法(SLDA、IMEDA、WSLDA和WIMEDA)識別率均高于未考慮圖像空間結(jié)構(gòu)信息的RLDA;2)采用特征值優(yōu)化方法的WSLDA和WIMEDA識別率均一致高于原方法,且優(yōu)勢明顯;3)在Yale人臉數(shù)據(jù)集上WSLDA優(yōu)勢明顯,在AR和FERET人臉數(shù)據(jù)集上WSLDA和WIMEDA性能相當.三組標準人臉數(shù)據(jù)集的實驗結(jié)果驗證WSLDA和WIMEDA的有效性,即在約束平均類內(nèi)散度(或緊性)上界的同時,最大化最壞類間散度(或分離度)的優(yōu)化目標要優(yōu)于優(yōu)化平均類內(nèi)和平均類間散度之比.4.3對wlda算法的敏感性分析本文還探究參數(shù)對實驗結(jié)果的影響.實驗中μ取103,最大迭代次數(shù)取1000,討論SLDA及WSLDA中η(轉(zhuǎn)換為α)和IMEDA及WIMEDA中低頻系數(shù)k對實驗結(jié)果的影響.由于,假設(shè)α(0≤α≤1)每間隔0.1取1次,即α∈[0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9],可得相應(yīng)的η,對比結(jié)果分別見圖1(橫坐標已轉(zhuǎn)換為α)和圖2.由η和α的等式關(guān)系可知,η隨著α的增大而增大,故由圖1可得,隨著參數(shù)η的變化SLDA算法的識別率變化平穩(wěn),而WSLDA算法的識別率隨著參數(shù)η的增大先波動性增大而后趨于平穩(wěn),故WSLDA對參數(shù)η的敏感性比SLDA強,且當參數(shù)η過大時,對進一步提高識別率可能不再有效.由圖2可見,隨著低頻系數(shù)k的增大,IMEDA和WIMEDA算法的識別率趨