圖正則化稀疏判別非負矩陣分解

徐慧敏，陳秀宏

（江南大學 數(shù)字媒體學院，江蘇 無錫 214000）

有效的數(shù)據(jù)低維表示不僅能夠發(fā)現(xiàn)數(shù)據(jù)集中的潛在信息，還能去除原始數(shù)據(jù)中的冗余特征，快速處理高維數(shù)據(jù)，其中最具代表性的方法包括主成分分析[1]、線性判別分析[2]及非負矩陣分解[3]。然而PCA 和LDA 得到的數(shù)據(jù)低維表示中可能會包含負值元素，這在實際的應用中缺少合理的解釋；而NMF 是一種非負約束下的矩陣分解方法，僅允許原始數(shù)據(jù)的加法而非減法組合，因此它有利于稀疏的且基于部分的表示，比非稀疏的全局表示更穩(wěn)健。

經(jīng)典的NMF 是一種無監(jiān)督學習算法，不能充分利用原始數(shù)據(jù)的類別信息。為了提高NMF 的判別能力，Wang 等[4]提出了Fisher-NMF(FNMF)，而Zafeiriou 等[5]和Kotsia 等[6]在NMF 的目標函數(shù)中增加了散度差項，建立起判別子空間法。由于LDA[2]中Fisher 準則的比值形式很難處理，集成在NMF 模型中會出現(xiàn)“小樣本問題”。為此，可考慮最大間距準則(max margin criterion，MMC)[7-8]，該準則是以類中心及類散度為度量依據(jù)，使得降維后不同類樣本之間距離越遠而同類樣本之間距離越近，在充分使用原始數(shù)據(jù)類別信息的基礎(chǔ)上使得改進后的NMF(如NDMF[9])具有良好的判別性質(zhì)。

另外，為了揭示和利用數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)，出現(xiàn)了許多基于流形特征的NMF，例如GNMF[10]、GDNMF[11]、LCGNMF[12]和NLMF[13]等，這些方法通過添加圖拉普拉斯正則化項達到了提高圖像聚類或分類性能的目的。Shang 等[14]同時考慮數(shù)據(jù)流形和特征流形，提出了圖對偶正則化NMF(DNMF)。而Meng 等[15]則在圖對偶模型中加入了稀疏性(DSNMF)和正交性的約束[16]，有效地簡化了高維計算，揭示數(shù)據(jù)和特征之間的雙流形結(jié)構(gòu)。

由于NDMF[9]具有良好的判別性質(zhì)，而NLMF[13]又利用了數(shù)據(jù)的圖結(jié)構(gòu)來提升其分類性能，故本文將兩種方法結(jié)合起來提出一種基于圖正則化的稀疏判別非負矩陣分解算法(GSDNMFL2,1)，在充分利用數(shù)據(jù)的類別信息的同時，不僅保持了數(shù)據(jù)樣本之間的局部流形結(jié)構(gòu)，而且能提取稀疏的特征，進而提升了其分類性能。若干圖像數(shù)據(jù)集上的實驗結(jié)果表明，該方法在特征提取與分類性能等方面優(yōu)于其他各對比算法。

1 相關(guān)工作

1.1 非負矩陣分解(NMF)

假設(shè)由n個非負樣本數(shù)據(jù)xi∈Rm(i=1,2,···,n)組成的非負數(shù)據(jù)矩陣X=[x1x2···xn]∈R+m×n，非負矩陣分解[3]的目標是將非負數(shù)據(jù)矩陣X分解為基矩陣W=[w1w2···wr]∈R+m×r和系數(shù)矩陣H=[h1h2···hn]∈R+r×n的乘積，即X≈WH，當r≤min(m,n)時，矩陣X就達到了有效壓縮。NMF 可表示為以下最小化問題：

其中 ∥·∥F表示Frobenius 范數(shù)。該問題的求解采用以下乘性迭代規(guī)則：

1.2 圖正則化非負矩陣分解(GNMF)

圖正則化非負矩陣分解(graph regularized non-negative matrix factorization，GNMF)[9]考慮了數(shù)據(jù)樣本之間的流形結(jié)構(gòu)，希望數(shù)據(jù)樣本在低維空間中盡可能多地保持其近鄰結(jié)構(gòu)，從而尋找數(shù)據(jù)在低維空間中的緊致嵌入。該問題可用以下優(yōu)化模型表示：

其中L=D-S為拉普拉斯矩陣，S是權(quán)矩陣，D為對角矩陣

求解該問題的乘性迭代規(guī)則為

1.3 最大間距準則(MMC)

設(shè)有C類樣本，最大間距準則的主要思想是尋找一個投影矩陣P使得投影后同類樣本之間的散度最小而不同類樣本之間的散度最大，達到保持原始數(shù)據(jù)判別信息的目的，它可表示為以下優(yōu)化問題：

2 本文算法

根據(jù)流形學習的圖嵌入思想[17-19]，數(shù)據(jù)在高維空間中的局部鄰域關(guān)系在低維樣本空間中應得到保持，同時也希望原始數(shù)據(jù)集的散度關(guān)系得到保持，因此在NMF 的目標函數(shù)中通過添加圖正則化約束和判別約束可達到提高算法分類性能的目的。

2.1 構(gòu)建權(quán)重矩陣

基于圖嵌入的流形學習法其前提是構(gòu)建相應的鄰接圖及權(quán)矩陣。傳統(tǒng)的流形學習方法通常是利用k-近鄰法或ε-鄰域法來構(gòu)建圖和權(quán)矩陣，但此類方法的性能依賴于參數(shù)k或ε。本文利用基于同類樣本的稀疏表示方法選擇鄰域樣本，該方法是自適應且與參數(shù)無關(guān)的，對噪聲數(shù)據(jù)具有魯棒性。

圖1 比較了兩種方法選擇的鄰域樣本。其中，k-近鄰法選擇的鄰域樣本包含了數(shù)據(jù)集中不同類別的人臉，人臉角度變化與標注圖像一致。相比而言，本文方法所選的樣本不僅和標注人臉具有相似角度，而且最接近其正面的人臉圖像，且相應的稀疏表示系數(shù)越大，越接近標注樣本。所以，基于同類樣本的稀疏表示方法構(gòu)建的權(quán)重矩陣不僅包含了樣本的類別信息，而且還包含了樣本間的局部鄰域結(jié)構(gòu)，從而具有良好的判別性質(zhì)。

圖1 k-近鄰法與稀疏表示法確定的近鄰Fig.1 Neighbor samples determined by k-nearest neighbor method and sparse representation

式中：Xc為第c類所有樣本組成的矩陣，表示系數(shù)向量中的每一個分量描述了與同類的其他相應樣本在表示時的貢獻大小，從而可以用來表示樣本之間的相似性。c(xi) 表示樣本的類標簽，nc表示第c類樣本的數(shù)量，且從而，有以下基于稀疏表示的樣本權(quán)矩陣：

2.2 正則化約束

圖正則化是基于鄰域保持嵌入的，它將訓練樣本之間的局部鄰域關(guān)系通過權(quán)矩陣S在由NMF的系數(shù)矩陣H的列向量hj所張成的子空間中得到保持，因此得到以下圖正則化約束項：

式中：SH為權(quán)矩陣；LH=DH-SH為拉普拉斯矩陣；DH為對角矩陣且對角元素為

以NMF 中的基矩陣W為投影矩陣，使得投影后同類樣本之間的散度最小而不同類樣本之間的散度最大[19]，以保留訓練樣本的判別特征，從而有以下基于MMC 準則的判別約束項：

為滿足NMF 的非負約束的要求，式(9)可改寫為

式中：SB表示由所有訓練樣本的類間散度矩陣；和分別表示SB的正元素和非正元素的絕對值構(gòu)成的矩陣；SW表示類內(nèi)散度矩陣；和分別表示SW的正元素和非正元素的絕對值構(gòu)成的矩陣。

對于圖像數(shù)據(jù)，其特征維度和冗余程度都很高，基于稀疏編碼的思想[20]，將樣本xi表示為基圖像的稀疏線性表示，可以減少高維樣本的計算量，得到更具魯棒性的特征：

通常使用L0范數(shù)對系數(shù)矩陣進行稀疏性約束，但L0范數(shù)的求解屬于NP 難問題，常用L1范數(shù)作為其凸近似進行近似求解：

系數(shù)矩陣H的每一列可看作原始數(shù)據(jù)X在子空間中的低維表示，L1范數(shù)使得系數(shù)矩陣H整體保持稀疏，本文使用L2,1范數(shù)對系數(shù)矩陣H進行列稀疏約束，使得每一個低維表示hj保持稀疏，能夠在特征空間中用盡可能少的特征重構(gòu)原始數(shù)據(jù)：

其中hj為矩陣H的第j列向量。

2.3 優(yōu)化模型與求解

由以上分析，利用圖正則化約束來保持樣本之間的鄰域結(jié)構(gòu)；以最大間距準則保持數(shù)據(jù)集的判別性；以L2,1范數(shù)進行稀疏性約束[21]，建立優(yōu)化模型：

令 Φik與 Ψk j為拉格朗日乘子，構(gòu)造拉格朗日函數(shù)：

式中：Q為對角矩陣，且為系數(shù)矩陣H的轉(zhuǎn)置的第i列。

使用交替迭代方法求解。先固定H，更新W；然后固定W，更新H。式(15)對W求偏導并令導數(shù)等于0，得：

于是，有以下關(guān)于W的更新規(guī)則：

同理，得到關(guān)于H的更新規(guī)則：

在每次迭代得到基圖像矩陣W后，對其每一列進行歸一化處理，使非負矩陣分解得到的結(jié)果保持縮放不變性。設(shè)置最大迭代次數(shù)T0，使算法在最大迭代次數(shù)下收斂。

綜合以上討論，得到圖正則化稀疏判別非負矩陣分解法：

算法1圖正則化稀疏判別非負矩陣分解算法(GSDNMF-L2,1)

輸入訓練樣本X∈Rm×n，樣本類別Y，特征

+數(shù)r，正則化參數(shù)λ、β、μ，最大迭代次數(shù)T0。

1)利用式(6)和式(7)計算權(quán)重矩陣SH；

2) 利用式(9) 計算類內(nèi)散度SW和類間散度SB；

利用式(18) 得到更新后的W，并對W的每一列進行歸一化處理，利用公式(19)得到更新后的H；

End

輸出基矩陣W和系數(shù)矩陣H。

2.4 算法復雜度

設(shè)m為樣本維度，n為樣本個數(shù)，k為特征數(shù)。算法GSDNMF-L2,1主要由1)、2)和4)組成，其(中步) 驟1)是構(gòu)建數(shù)據(jù)圖的權(quán)矩陣，其復雜度為On2m；步驟2) 則是(計算)類內(nèi)散度SW和類間散度SB， 其復雜度為Om2；對步驟4)，一次迭代計算W和H的復雜度O(mnk) ，假設(shè)算法在T0次迭代后收斂，則整個步驟4)的復雜度為O(T0mnk)。綜上可知，GSDNMF-L2,1算法的總體時間復雜度為O

3 實驗分析

為了說明GSDNMF-L2,1算法在圖像特征提取中的有效性，分別在ORL 和AR 人臉數(shù)據(jù)集和COIL20 實物數(shù)據(jù)集上進行實驗，并將之與NMF[3]、GNMF[10]、NDMF[9]等算法進行比較，同時比較利用L1范數(shù)進行稀疏約束的模型(GSDNMF-L1)。將數(shù)據(jù)集按0.5 的比例隨機劃分為訓練集和測試集，利用訓練集進行特征提取，獲得基矩陣W。利用測試集計算分類精度：測試樣本x∈Rm在低維子空間中的表示為y≈W+x∈Rr，其中W+=(WTW)-1WT為矩陣W的Pseudo 逆，使用傳統(tǒng)的k-近鄰分類器(k-NN)預測類標簽。每次實驗獨立隨機，重復20 次取平均識別率和方差作為最后實驗結(jié)果。

3.1 數(shù)據(jù)集

ORL 人臉數(shù)據(jù)庫包含了40 個人的人臉圖像，每個人有10 張，圖像具有不同面部表情(睜/閉眼，笑/不笑)、面部細節(jié)(眼鏡/無眼鏡)及不同光照條件。

AR 數(shù)據(jù)集包含了120 個人的人臉圖像，每個人有26 張圖像，圖像具有不同的面部表情、照明條件和遮擋(太陽眼鏡/圍巾)。

COIL20 數(shù)據(jù)集包含了20 個不同的物體(玩具小鴨、招財貓、杯子等)，其中，每個物體在水平面上每隔5°拍攝一張圖片，因此每個物體一共有72 幅圖片，整個數(shù)據(jù)集共計l 440 幅圖片。

實驗中，所有圖像均壓縮成32×32 大小的灰度圖，將其每列相連構(gòu)成大小為1 024 維的向量，并做歸一化處理。如圖2 所示。

圖2 數(shù)據(jù)集示例Fig.2 The instances of datasets

3.2 參數(shù)選擇

GSDNMF-L2,1算法包含了圖正則化約束參數(shù)λ、判別約束參數(shù) β 和稀疏參數(shù) μ 等3 個關(guān)鍵參數(shù)。為說明3 個參數(shù)對識別率的影響，分別在兩個數(shù)據(jù)集上采取固定兩個參數(shù)來確定另一個參數(shù)的方法進行討論，設(shè)參數(shù)的取值范圍為[0,1]，取數(shù)據(jù)集的類別數(shù)作為基圖數(shù)(ORL 取40，AR 取120，COIL20 取20)，最大迭代次數(shù)為300 次，實驗所得的平均識別率與正則化參數(shù)的關(guān)系如圖3 所示。

圖3 參數(shù)對識別率的影響Fig.3 The influence of parameters

3.3 實驗結(jié)果及分析

由圖3 可知，圖正則化參數(shù)λ對識別率的影響較大，在[0,0.01]的范圍內(nèi)，識別率隨參數(shù)的增大而增大，在[0.01,1]的范圍內(nèi)，識別率隨參數(shù)的增大而減少。判別約束參數(shù)和稀疏參數(shù)對識別率的影響較小，在[0,1] 范圍內(nèi)一直保持較高識別率。經(jīng)過多次實驗，最終確定算法的最優(yōu)參數(shù)組合為λ=0.005，β=1，μ=0.5。

取基圖數(shù)分別為3、4、5、6、7、8 的平方，在3 種數(shù)據(jù)集上獨立隨機地進行20 次實驗，計算平均識別率及方差。表1～3 給出了5 種算法在3 種數(shù)據(jù)集上的平均識別率隨基圖像個數(shù)的增加而變化的情況。在大多數(shù)情況下，GSDNMF-L2,1的識別率要優(yōu)于其他幾種算法，且方差更小，說明在NMF 的目標函數(shù)中結(jié)合圖正則化約束和判別約束能夠有效提高圖像特征提取的準確率和穩(wěn)定性。圖4 比較了在ORL 數(shù)據(jù)集上5 種算法的訓練時間(取類別數(shù)40 作為基圖數(shù)目)，可以發(fā)現(xiàn)NMF 和GNMF 的訓練時間較短，NDMF 訓練時間最長，GSDNMF-L2,1和GSDNMF-L1比NDMF 時間短。可知，利用稀疏編碼的思想對系數(shù)矩陣H添加稀疏性約束，在每一迭代更新的過程中能夠盡可能少地選擇基圖像重構(gòu)訓練樣本，提高了運算速度。

表1 ORL 數(shù)據(jù)集上的平均識別率(方差)Table 1 Average recognition rate (variance) on ORL dataset

表2 AR 數(shù)據(jù)集上的平均識別率 (方差)Table 2 Average recognition rate (variance) on AR dataset

表3 COIL20 數(shù)據(jù)集上的平均識別率 (方差)Table 3 Average recognition rate (variance) on COIL20 dataset

圖4 訓練時間隨基圖數(shù)變化的曲線Fig.4 Variation curve of training time

圖5 給出了GSDNMF-L2,1算法在3 種數(shù)據(jù)集上的收斂情況，當?shù)螖?shù)小于10 次時損失函數(shù)值迅速下降；而當?shù)螖?shù)大于100 時，隨著迭代次數(shù)的增加其損失函數(shù)值的下降趨于平緩，并收斂于一個固定值。本文所有實驗均設(shè)置最大迭代次數(shù)為300 次，以保證算法收斂。

為了刻畫和評價基圖像矩陣的特點，Hoyer[20]提出采用向量的 L1范數(shù)和 L2范數(shù)的差異來度量向量的稀疏度，其計算方式為

圖5 損失函數(shù)的變化曲線Fig.5 Variation curve of loss function

其中向量 xi是其第i 個分量。稀疏度值域是[0,1]，值越大，說明向量越稀疏。表4 比較了5 種算法在3 種數(shù)據(jù)集上迭代300 次后生成的基圖的平均稀疏度(基矩陣的每一列表示一個基圖)。圖6 比較了3 種具有判別性質(zhì)的NMF 算法：NDMF[9]、GSDNMF-L1和 GSDNMF-L2,1得到的基圖。對比發(fā)現(xiàn)，3 種算法都能得到的圖像的局部化表示，且都包含了每類物體的判別信息，但GSDNMF-L2,1和 GSDNMF-L1得到的基圖比 NDMF[9]得到的基圖更稀疏。由實驗結(jié)果可知，本文提出的算法，能夠在保證稀疏性的條件下，保持良好分類水平，說明算法分解得到了更有效的基圖特征。

表4 比較基圖像W 的稀疏度Table 4 Comparison of sparsity of the base matrix W

圖6 比較NDMF，GSDNMF-L1 和GSDNMF-L2,1 算法在ORL、AR 和COIL20 數(shù)據(jù)集上得到的基圖Fig.6 Comparison of basic images computed by NDMF,GSDNMF-L1 and GSDNMF-L2,1 algorithm on ORL,AR and COIL20 dataset

4 結(jié)束語

本文給出了一種新的圖正則化稀疏判別NMF 算法(GSDNMF-L2,1)。該方法在對圖像進行特征提取時，充分利用了數(shù)據(jù)集的標簽信息來構(gòu)造權(quán)重矩陣和判別約束項。與已有的圖正則化方法不同的是，GSDNMF-L2,1算法用同類樣本的稀疏線性組合來構(gòu)建權(quán)重矩陣，很好地保持了樣本內(nèi)的相似性和樣本間的差異性，在最大間距準則下使得類內(nèi)離散性最小而類間分離性最大，從而獲得很強的判別能力。另外，GSDNMF-L2,1在稀疏性約束條件下得到了稀疏系數(shù)矩陣，從而提高了矩陣分解的速度。下一步研究的方向是如何處理新樣本，及自動選擇最佳特征數(shù)量，使算法更加完善。