基于低秩表示的判別特征提取算法

蘇雅茹，許智杰，吳小惠

(1.福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108; 2.廈門大學(xué)航空航天學(xué)院，福建 廈門 361005)

0 引言

隨著數(shù)據(jù)類型越來(lái)越豐富，數(shù)據(jù)結(jié)構(gòu)也越來(lái)越復(fù)雜.比如，數(shù)據(jù)庫(kù)文本、Web 數(shù)據(jù)、各種各樣的圖像數(shù)據(jù)和視頻數(shù)據(jù)等，這給數(shù)據(jù)的分析、處理和應(yīng)用帶來(lái)了困難與挑戰(zhàn).這些數(shù)據(jù)往往具有很高的維數(shù)和復(fù)雜的結(jié)構(gòu)，數(shù)據(jù)形式通常是稀疏的，帶有大量的冗余信息，數(shù)據(jù)的這些特點(diǎn)不僅增加了分析處理負(fù)擔(dān)，使得時(shí)間和空間復(fù)雜度迅速上升從而導(dǎo)致算法性能下降，甚至容易掩蓋數(shù)據(jù)的真實(shí)結(jié)構(gòu)從而導(dǎo)致錯(cuò)誤的分析處理結(jié)果.高維復(fù)雜數(shù)據(jù)的諸多應(yīng)用需求使得對(duì)高維數(shù)據(jù)的分析處理在科學(xué)研究領(lǐng)域占據(jù)著越來(lái)越重要的地位.

充分利用高維復(fù)雜數(shù)據(jù)的結(jié)構(gòu)對(duì)學(xué)習(xí)問(wèn)題進(jìn)行建模是利用數(shù)據(jù)信息的關(guān)鍵所在.關(guān)聯(lián)矩陣是描述數(shù)據(jù)結(jié)構(gòu)的一種形式，用于度量樣本和樣本之間的相關(guān)性.相關(guān)性高的樣本通常會(huì)被聚集到一塊，關(guān)聯(lián)矩陣的理想表現(xiàn)是假設(shè)樣本按類別排好，其對(duì)應(yīng)的關(guān)聯(lián)矩陣是塊對(duì)角矩陣.近年來(lái)，利用低秩表示構(gòu)造的關(guān)聯(lián)矩陣被應(yīng)用于聚類[1-6]、維數(shù)約簡(jiǎn)[7-9]、噪聲人臉識(shí)別[10]、閉塞人臉識(shí)別[11-12]等問(wèn)題，并取得很好的效果.

本研究提出一種低秩表示判別映射(low-rank representation discriminant projections，LRDP)，基于低秩表示(low-rank representation, LRR)構(gòu)造關(guān)聯(lián)矩陣并用于判別特征提取，并利用人臉數(shù)據(jù)集的實(shí)驗(yàn)證明了LRDP的特征提取有效性.

1 低秩判別映射

首先，給定一組來(lái)自若干相鄰子空間的樣本，低秩表示把樣本向量看成其它所有樣本向量的線性組合，并尋找最低秩表示，低秩表示的構(gòu)造特點(diǎn)決定了LRDP的良好數(shù)據(jù)全局結(jié)構(gòu)表達(dá)能力和判別結(jié)構(gòu)表達(dá)能力[1].然后，基于表達(dá)數(shù)據(jù)關(guān)系結(jié)構(gòu)的低秩表示引入充分利用數(shù)據(jù)判別信息的判別準(zhǔn)則，這些特點(diǎn)使得LRDP很好地利用了數(shù)據(jù)樣本信息.

1.1 低秩表示

低秩表示的數(shù)學(xué)描述如下[1]：

給定一個(gè)樣本集X=[X1,X2, …,Xn]∈Rd×n，n表示樣本個(gè)數(shù)，d表示樣本維數(shù)，每個(gè)樣本Xi∈Rd都可以表示為“字典”A=[a1,a2, …,am]中的基的線性組合，則模型描述為：

X=AZ

(1)

其中:Z=[Z1,Z2, …,Zm]是一個(gè)由系數(shù)向量組成的系數(shù)矩陣，系數(shù)向量Zi對(duì)應(yīng)著樣本Xi.

因?yàn)锳的復(fù)雜性，樣本集X的系數(shù)矩陣Z通常有多個(gè)可行解，上述模型可以通過(guò)以下的優(yōu)化問(wèn)題來(lái)求解：

其中: “最低秩表示”Z*表示最優(yōu)解.

由秩rank(Z)的非凸性，上述模型的優(yōu)化問(wèn)題通常很難解決.于是，采用矩陣計(jì)算方法[13-14]，優(yōu)化問(wèn)題(2)可以替換為以下凸優(yōu)化問(wèn)題：

(4)

經(jīng)過(guò)理論證明[1]，當(dāng)滿足兩個(gè)條件： 樣本數(shù)據(jù)充足，即nk>rank(Xk)=dk，且子空間獨(dú)立時(shí)，優(yōu)化問(wèn)題(4)可以得到一個(gè)塊對(duì)角陣解：

(5)

低秩表示用樣本自身來(lái)表示數(shù)據(jù)向量，其原因是解空間為I-null(X)，當(dāng)rank(X)

1.2 目標(biāo)函數(shù)

給定樣本集X=[X1,X2, …,Xn]∈Rd×n，假定均值為零，包含K個(gè)類別的樣本，并得到最低秩表示Z*：

(6)

定義樣本Xi的最低秩表示向量：Zi=[Zi, 1,Zi, 2, …,Zi, n]T，并設(shè)k個(gè)類別中的第l個(gè)樣本的最低秩表示向量為Zkl.

給定線性映射Y=VTX，對(duì)于單個(gè)樣本Xi∈Rd，可以從d維空間映射到dr維空間，得到Y(jié)i∈Rdr； 對(duì)于樣本集X，也可以從d維空間映射到dr維空間，得到Y(jié)，其中dr<

定義映射空間樣本集的類內(nèi)殘差：

(7)

其中:δk(Zkl)實(shí)現(xiàn)只保留最低秩表示向量Zkl中第k個(gè)類別的所有樣本系數(shù)的功能. 同時(shí), 定義映射空間樣本集的類間殘差：

(8)

其中:δk′(Zkl)實(shí)現(xiàn)只保留最低秩表示向量Zkl中第k′個(gè)類別的所有樣本系數(shù)的功能.

判別準(zhǔn)則的目標(biāo)是盡量減小類內(nèi)殘差并盡量增大類間殘差，通過(guò)最大化以下目標(biāo)函數(shù)來(lái)實(shí)現(xiàn)：

(9)

其中:β系數(shù)用于平衡類內(nèi)殘差和類間殘差.

(10)

(11)

J(V)=tr(VT(βRB-RW)V)

(12)

(13)

采用拉格朗日乘子法求解上述目標(biāo)函數(shù)：

(14)

(15)

其中，λ是拉格朗日乘數(shù).那么

(βRB-RW)Vi=λiVi

(16)

其中:λi(i=1, 2, …,d)是(βRB+RW)和XXT的廣義特征值，Vi(i=1, 2, …,d)是相應(yīng)的廣義特征向量.

1.3 低秩判別映射(LRDP)

表1 低秩判別映射

低秩判別映射(LRDP)的算法步驟如表1所示.

為了對(duì)比低秩表示和稀疏表示對(duì)數(shù)據(jù)結(jié)構(gòu)的表達(dá)能力，提出一種基于稀疏表示的判別特征提取算法-稀疏表示判別映射(sparse representation discriminant projections, SRDP).SRDP和LRDP的不同在于，SRDP的樣本關(guān)聯(lián)矩陣是基于稀疏表示構(gòu)造的, 而LRDP基于低秩表示.稀疏表示可以通過(guò)以下的凸優(yōu)化問(wèn)題求解[16-17]：

(17)

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

表2 Yale、UMIST數(shù)據(jù)集

本實(shí)驗(yàn)采用Yale和UMIST人臉數(shù)據(jù)集, 數(shù)據(jù)集信息如表2所示.實(shí)驗(yàn)數(shù)據(jù)集被分為訓(xùn)練集和測(cè)試集兩部分，假設(shè)實(shí)驗(yàn)為P-train，則每類隨機(jī)取P個(gè)樣本作為訓(xùn)練樣本，其余作為測(cè)試樣本.實(shí)驗(yàn)要選擇合適的P值，因?yàn)镻值太大信息不充分，太小容易過(guò)擬合.

對(duì)每組實(shí)驗(yàn)數(shù)據(jù)，分別采用主成分分析(PCA)、線性判別分析(LDA)、譜回歸判別分析(SRDA)、邊沿Fisher分析(MFA)、SRDP、LRDP六種算法進(jìn)行特征提取，統(tǒng)一采用SRC分類方法的分類準(zhǔn)確率來(lái)評(píng)價(jià)各種特征提取算法的性能.為了準(zhǔn)確地評(píng)估六種算法的性能，對(duì)每個(gè)P值進(jìn)行20次隨機(jī)實(shí)驗(yàn)，并取20次隨機(jī)實(shí)驗(yàn)的分類準(zhǔn)確率的平均值作為分類準(zhǔn)確率.

假設(shè)樣本類別數(shù)為K，樣本數(shù)為n，則LDA和SRDA最多可以取K-1個(gè)特征，而其它算法的特征數(shù)可以達(dá)到n-1.實(shí)驗(yàn)結(jié)果給出了分類準(zhǔn)確率(分類性能)隨特征數(shù)變化的曲線圖(詳見(jiàn)圖1～2)，并在表3～4中給出最佳分類準(zhǔn)確率(最佳分類性能)、相應(yīng)的標(biāo)準(zhǔn)差和特征數(shù).

圖1 Yale數(shù)據(jù)上分類性能隨特征數(shù)變化的曲線Fig.1 Recognition accuracy vs.feature dimension on Yale data set

算法4-train5-train6-train7-trainPCA69.19±4.44(58)73.42±3.99(73)77.80±3.40(87)79.50±4.96(97)LDA67.67±6.11(14)72.83±3.13(14)75.93±5.24(14)78. 02±3.80(14)SRDA68.76±4.91(12)73.37±2.97(14)78.40±5.07(14)80.01±4.04(14)MFA67.86±4.37(12)71.94±5.56(16)73.87±4.25(16)75.17±5.16(20)SRDP68.86±4.34(59)73.49±3.95(74)78.13±4.06(89)79.25±3.88(96)LRDP73.81±4.31(47)77.50±3.66(65)82.47±3.46(66)84.03±4.81(94)

從圖1～2可以看出，LRDP的性能幾乎總是優(yōu)于其它的算法.對(duì)各個(gè)P值，各個(gè)算法在特征數(shù)比較少時(shí)，分類性能隨著特征數(shù)的增加而快速上升，當(dāng)特征數(shù)達(dá)到一定值后，性能上升變得緩慢甚至有少許下降，說(shuō)明隨著特征數(shù)的增加，判別信息的增加變得不明顯，其原因?yàn)槭艿饺哂嗵卣鞯呢?fù)面影響.隨著P值的增加，即訓(xùn)練樣本數(shù)的增加，各個(gè)算法的性能都有一定的提高，說(shuō)明訓(xùn)練樣本的特征是判別信息的主要來(lái)源.從表3～4可以看出，LRDP最佳性能總是優(yōu)于其它算法(包括MFA).

圖2 UMIST數(shù)據(jù)上分類性能隨特征數(shù)變化的曲線Fig.2 Recognition accuracy vs.feature dimension on UMIST data set

算法6-train8-train10-train12-trainPCA84.44±2.34(91)92.84±2.15(119)95.60±1.21(67)96.81±1.53(103)LDA85.40±1.98(19)89.49±2.65(19)92.16±1.46(19)94.09±1.86(19)SRDA88.09±2.08(19)92.84±2.16(19)96.00±1.24(19)96.73±1.61(19)MFA90.32±2.35(34)93.83±2.18(33)95.77±1.49(59)96.85±1.27(39)SRDP88.48±2.23(115)93.10±2.46(33)96.12±1.37(49)97.15±1.36(67)LRDP90.34±2.15(23)94.68±2.34(29)97.23±1.20(39)98.05±1.42(31)

3 小結(jié)

本研究利用低秩表示和判別準(zhǔn)則，提出低秩表示判別映射LRDP.經(jīng)過(guò)理論分析和對(duì)比實(shí)驗(yàn)，發(fā)現(xiàn)存在以下三個(gè)因素： 1) 在子空間獨(dú)立的假設(shè)下，通過(guò)低秩表示獲得關(guān)聯(lián)圖，其類內(nèi)關(guān)聯(lián)系數(shù)大，類間關(guān)聯(lián)系數(shù)小，表現(xiàn)出一定的判別結(jié)構(gòu)表達(dá)能力； 2) LRDP和SRDP都不是采用標(biāo)準(zhǔn)基作為基函數(shù)，而是利用樣本自身作為基函數(shù)，稀疏表示單獨(dú)為每個(gè)樣本尋找稀疏表示，而低秩表示對(duì)所有樣本尋找低秩表示，因此，低秩表示對(duì)數(shù)據(jù)全局結(jié)構(gòu)的表達(dá)能力比稀疏表示更強(qiáng)； 3) 采用縮小類內(nèi)殘差和增大類間殘差的判別準(zhǔn)則，更好地利用了樣本的類別信息.有鑒于此, 本研究認(rèn)為L(zhǎng)RDP具有良好的穩(wěn)定性和魯棒性.總之，LRDP是一種有效的特征提取算法，是一種全局性算法，同時(shí)還有較強(qiáng)的判別性，能夠比較準(zhǔn)確地描述數(shù)據(jù)集的全局結(jié)構(gòu)和數(shù)據(jù)樣本的判別關(guān)系.下一步工作將考慮引入一些約束，用非凸替換來(lái)求解目標(biāo)函數(shù)，或者從矩陣擴(kuò)展到張量形式的分析.