蘇雅茹，許智杰，吳小惠

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

0 引言

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

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

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

1 低秩判別映射

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

1.1 低秩表示

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

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

X=AZ

(1)

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

因為A的復雜性，樣本集X的系數(shù)矩陣Z通常有多個可行解，上述模型可以通過以下的優(yōu)化問題來求解：

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

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

(4)

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

(5)

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

1.2 目標函數(shù)

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

(6)

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

給定線性映射Y=VTX，對于單個樣本Xi∈Rd，可以從d維空間映射到dr維空間，得到Yi∈Rdr； 對于樣本集X，也可以從d維空間映射到dr維空間，得到Y，其中dr<

定義映射空間樣本集的類內殘差：

(7)

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

(8)

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

判別準則的目標是盡量減小類內殘差并盡量增大類間殘差，通過最大化以下目標函數(shù)來實現(xiàn)：

(9)

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

(10)

(11)

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

(12)

(13)

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

(14)

(15)

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

(βRB-RW)Vi=λiVi

(16)

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

1.3 低秩判別映射(LRDP)

表1 低秩判別映射

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

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

(17)

2 實驗結果與分析

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

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

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

假設樣本類別數(shù)為K，樣本數(shù)為n，則LDA和SRDA最多可以取K-1個特征，而其它算法的特征數(shù)可以達到n-1.實驗結果給出了分類準確率(分類性能)隨特征數(shù)變化的曲線圖(詳見圖1～2)，并在表3～4中給出最佳分類準確率(最佳分類性能)、相應的標準差和特征數(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)于其它的算法.對各個P值，各個算法在特征數(shù)比較少時，分類性能隨著特征數(shù)的增加而快速上升，當特征數(shù)達到一定值后，性能上升變得緩慢甚至有少許下降，說明隨著特征數(shù)的增加，判別信息的增加變得不明顯，其原因為受到冗余特征的負面影響.隨著P值的增加，即訓練樣本數(shù)的增加，各個算法的性能都有一定的提高，說明訓練樣本的特征是判別信息的主要來源.從表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 小結

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