非負低秩圖嵌入算法*

劉國慶，盧桂馥，周 勝，宣東東，曹阿龍

安徽工程大學 計算機與信息學院，安徽 蕪湖241000

1 引言

互聯網上的數據圖像、視頻、語音等都含有非常豐富的研究價值，這些數據通常是高維的，計算機是處理這些高維數據的重要工具，而數據在計算機中通常是以矩陣的形式進行存儲的，對高維數據的處理即是對高維矩陣的處理，因此矩陣分解被作為一種有效的數據處理方法。近年來，非負矩陣分解方法（non-negative matrix factorization，NMF）[1]在模式識別、圖像聚類[2]、語音識別等領域已得到了廣泛的應用，且都取得了很好的應用效果。1999年Lee 和Seung 在Nature雜志上所提出的非負矩陣分解算法[1]是一種基于局部特征提取的方法，也是一種有效的圖像表示工具[3]，該方法分解后矩陣中的所有元素均是非負的，NMF 在心理學和生理學上構造的依據是對整體的感知是由組成整體的部分感知所構成的，這恰恰也符合人類大腦對事物的直觀理解。

為了改善NMF 算法的性能，很多學者在NMF 算法的基礎提出了許多改進的算法，Cai 等在標準NMF方法的基礎上考慮數據所攜帶的幾何信息，提出了圖正則化非負矩陣分解算法（graph regularized nonnegative matrix factorization for data representation，GNMF）[4]。為了能夠獲取原始圖像數據的低秩結構，Li 等提出了圖正則化非負低秩矩陣分解算法（graph regularized non-negative low-rank matrix factorization for image clustering，GNLMF）[5]。Du 等提出一種圖嵌入正則化投影非負矩陣分解人臉圖像特征提取方法（graph embedding regularized projection nonnegative matrix factorization for face image feature extraction，GEPNMF）[6]，該方法將圖嵌入正則項融入到投影非負矩陣分解的目標函數中，使得其求得的子空間能在保持數據空間的流形幾何結構的同時，更具判別力。為了能夠同時利用數據的全局信息和局部信息來進行圖形的學習，Wen 等提出一種自適應圖正則化的低秩表示方法（low-rank representation with adaptive graph regularization，LRR-AGR）[7]。為了在多視角聚類過程中同時考慮特征權重和數據高維性問題，Liu等提出一種基于特征加權和非負矩陣分解的多視角聚類算法（multiview clustering algorithm based on feature weighting and nonnegative matrix factorization，FWNMF-MC）[8]。Yin 等提出一種拉普拉斯正則化低秩表示及其應用算法（Laplacian regularized low-rank representation and its applications，LLRR）[9]，該算法通過對圖形的正則化，既能表示數據的全局低維結構，又能捕獲數據中固有的非線性幾何信息。Wang 等提出一種降維局部約束圖優化算法（locality constrained graph optimization for dimensionality reduction，LCGODR）[10]，該算法將圖優化和投影矩陣學習結合到了一個框架中，由于圖是預先構造并保持不變的，使得其在降維過程中的圖形可以自適應更新。為了同時考慮數據空間和特征空間的流形結構，Meng 等提出一種具有稀疏和正交約束的對偶圖正則化非負矩陣分解（dual-graph regularized non-negative matrix factorization with sparse and orthogonal constraints，SODNMF）[11]。為了有效地處理非線性數據，Xiao 等提出一種魯棒核低秩表示算法（robust kernel low-rank representation，RKLRR）[12]。Wan 等提出一種低秩稀疏圖嵌入的半監督特征選擇方法（semi-supervised feature selection for low rank sparse graph embedding，LRSE）[13]，該方法充分利用有標簽數據和無標簽數據，分別學習其低秩稀疏表示，在目標函數中同時考慮數據降維前后的信息差異和降維過程中的結構信息，通過最小化信息損失函數使數據中的有用信息盡可能地保留下來，從而可以選擇出更具判別性的特征。為了在NMF 方法中融入幾何信息，研究人員嘗試將傳統圖嵌入框架[14]引入到NMF 方法中[15-16]。其中，非負圖嵌入算法（non-negative graph embedding，NGE）是一個統一的非負數據分解框架。它除了NMF 目標函數外，還給出一個嵌入圖的目標函數，該目標函數保留了由內在圖和懲罰圖描述的數據幾何信息，并將數據重構誤差進行最小化。由于NMF 數據重構的非負性，NGE 將最大化“內在”和最小化“懲罰”這兩個相反的目標函數轉化為單一的最小化目標函數，從而保持了目標函數有效解。盡管NGE 框架具有較好的優越性，但在現實世界的應用中它仍存在對噪聲數據和不可靠圖敏感以及魯棒性差的缺點。為了解決上述問題，本文提出了一種非負低秩圖嵌入算法（non-negative low rank graph embedding，NLGE），該算法同時考慮了原始圖像數據的幾何信息和有效低秩結構，使得其魯棒性有了進一步的提高。

本文的貢獻主要有以下三方面：（1）針對現實世界原始圖像數據集中普遍存在的噪聲數據，對原始圖像數據集進行低秩處理，獲取原始圖像數據集的有效低秩結構，提出一種非負低秩圖嵌入算法（NLGE）；（2）設計了一種求解NLGE 的有效迭代算法；（3）給出了該算法的收斂性證明。通過在標準數據庫上的實驗，驗證了NLGE 算法的優越性。

2 相關工作

2.1 非負矩陣分解（NMF）

設訓練樣本數據為Χ=[x1,x2,…,xN]，xi∈Rm，Ν是訓練樣本總數，相應的類標簽表示為{ci|ci∈{1,，Νc為類別數。NMF 方法試圖找到兩個非負矩陣W∈Rm×r，H∈Rr×N，其乘積最佳逼近原始矩陣Χ，NMF 的最小化目標函數如下：

2.2 圖正則非負矩陣分解（GNMF）

為了能夠發現數據隱藏信息的有效表示方法，同時又考慮數據的內蘊幾何結構，Cai 等通過將圖正則化項融入到標準的NMF 框架中提出了圖正則非負矩陣分解算法（GNMF）。該算法在矩陣分解過程中強調降維后的數據保持原始數據的幾何信息，并假設兩個數據點在原始數據空間中的幾何距離如果是鄰近的話，那么其在基于新的基向量低維表示中相對應的數據點也應該是鄰近的。與傳統的降維算法相比，流形學習算法能夠揭示原始圖像數據的內蘊幾何結構，尋找高維數據在低維空間中的緊密嵌入。GNMF 的目標函數表示如下：

其中，tr(HLapHT)是圖正則項，Lap是圖拉普拉斯矩陣，圖正則化參數λ>0 。Cai 等在文獻[4]中給出了如下的迭代更新規則：

其中，Dap是對角矩陣，Lap=Dap-Sap。

3 非負低秩圖嵌入（NLGE）

研究表明，現實世界中的數據往往是嵌入在高維歐式空間中的非線性低維流形上的[17]。另外，原始圖像數據中一般含有潛在的噪聲數據和不可靠圖，實際上有效信息常常隱藏在它的低秩結構中；致使NMF 方法和許多改進的NMF 方法在圖像聚類和分類應用中的表現性能不理想。為了提高NMF 算法在非監督聚類和監督分類中的有效性，本文提出了一種非負低秩圖嵌入算法，該算法明確考慮了原始圖像數據的有效低秩結構和數據的幾何信息。

3.1 NLGE 的算法模型

為了挖掘原始圖像數據的有效低秩結構部分，把X近似表示為L+S的加和，其中L表示數據X的低秩部分，S表示稀疏噪聲部分，之后再對L進行NGE 操作，以獲得原始數據圖像的有效低維表示。則有：

其中，min 表示當矩陣L、S滿足約束條件時，式（7）的最小取值，W為基矩陣，H是系數矩陣，l表示低秩矩陣L秩的范圍集，s表示矩陣S的稀疏范圍集，rank(L)表示矩陣L的秩，card(S)表示矩陣S中的非零元素的個數。

圖嵌入往往涉及到內在圖G，它描述了訓練數據間的有利關系，而懲罰圖Gp={X,Sp}則描述了訓練數據之間的不利關系，Lp=Dp-Sp。則有：

其中，NK(i)表示同一類中k最近鄰xi的索引集。

其中，NKp(i) 表示不同類中xi的Kp最近鄰的索引集。為了使NMF 和NGE 的符號保持一致，將系數矩陣H分為兩部分，即：

其中，W1∈Rm×d，W2∈Rm×(r-d)。

所需要的訓練數據的低維表示H1旨在保留內在圖的特性，同時避免懲罰圖的特性。在這里，(W2,H2)是(W1,H1)的互補空間，它們以相加的方式重建原始數據。以往的研究表明：一方面，內在圖和懲罰圖在NGE 中起著重要的作用，然而當圖像具有不需要的結構時，NGE 的性能會有所下降。另一方面，對同一類的樣本構造內在圖，而懲罰圖則將不同類的樣本連接起來，在現實應用中NGE 仍存在對噪聲數據和不可靠圖敏感以及魯棒性差的缺點。為了增強NGE算法的性能，在NGE 算法中融合圖像的低秩結構，其目標函數定義如下：

3.2 NLGE 的求解算法

本文通過迭代方法求解式（13），NLGE 算法可以通過求解下面兩個子問題來解決。

（1）低秩矩陣的恢復

低秩矩陣恢復子問題的目標函數可以表示如下：

其中，l是低秩結構L的秩，s是被稀疏噪聲影響的數量。雖然問題（14）對于L和S是非凸的，但是如果L或S中的一個被固定，則下面的子問題是凸的。

式（15）中的兩個子問題可以通過固定其的一個更新另一個來解決，直到收斂為止。本文使用了雙邊隨機投影（bilateral random projection，BRP）[18]求解問題（14）。對于給定的矩陣X∈Rm×N，則Y1和Y2表示如下：

其中，A1∈RN×r，A2∈Rm×r都是隨機矩陣，則L表示如下：

在文獻[18]中給出了獲取右隨機投影Y1用于建立更好的左投影矩陣A2，而Y2用于建立更好的右投影矩陣A1。為了防止矩陣X的奇異值退化，Roweis[19]提出了用來代替X ，則的BRP 和表示如下：

通過對Y1和Y2進行QR分解，求得L如下：

在求出低秩矩陣L之后，再進一步對L進行NGE 分解以獲得原始數據集的低維表示。

（2）優化W和H

在描述非負低秩圖嵌入的迭代過程之前，先介紹兩個概念：輔助函數和M矩陣，以及一些用于算法推導和收斂性證明的引理。

定義1函數G(A,A′)是F(A)的輔助函數，滿足下面條件：

定義2矩陣B被稱為M矩陣，滿足條件：（1）Bij≤0,i≠j；（2）矩陣B的所有特征值的實部都是正的。

引理1如果G是F的輔助函數，則F在下面迭代更新規則下是非增的。

其中，t表示第t次迭代。

引理2如果矩陣B是M矩陣，則矩陣B的逆矩陣中的元素是非負的，即

固定矩陣H優化W，對于給定的矩陣H，目標函數式（13）中關于基矩陣W的目標函數可以重寫如下：

根據上述函數，注意到矩陣W的不同行向量在優化時是彼此獨立的，因此式（25）可以進一步簡化為如下的形式：

其中，Wi表示W的第i行向量，Xi是矩陣X的第i行向量，定義，函數F(Wi)的輔助函數可以定義如下：

固定W優化H，對于給定的W，同樣式（13）關于H的目標函數可以寫為如下：

在這里定義f(H)=λ‖L-WH‖2，F(H)輔助函數被定義如下：

其中，g(H,Ht)被表示成如下形式：

根據文獻[1]中的相關證明，顯然有g(H,Ht) 是f(H)的輔助函數，則進一步可以得出G(H,Ht)是F(H)的輔助函數，然后通過求解函數G(H,Ht)關于H的最小化來計算Ht+1。

G(H,Ht)關于H的梯度矩陣設置如下：

如果i≤d，系數矩陣Ht+1的第i行向量表示為，使用下面的設置來更新

同樣，如果d

然后，計算出：

3.3 NLGE 算法的收斂性證明

定理1在NLGE 算法中給出的迭代過程收斂到局部最優。

證明在這里定義：

根據W的更新規則，有：

同樣，根據H的更新規則，有：

因此，可以得出如下的結論：

根據上述所給的目標函數有F(Wt,Ht)≥0，且F(Wt,Ht)單調下降有下界，因此NLGE 算法在所給迭代規則下收斂到局部最優。

3.4 NLGE 算法的步驟

輸入：數據矩陣X∈Rm×N，參數λ,r,d,K,Kp。

輸出：最優基矩陣和數據的低維表示矩陣H。

（1）對X進行BRP 操作，求出Y1和Y2；

（2）對Y1和Y2進行QR分解，求出數據矩陣X的低秩結構L；

（3）對矩陣L進行NGE 分解；

（4）計算

（5）求得最優基矩陣W和數據的低維表示矩陣H。

3.5 NLGE 算法的計算復雜度分析

對于一個算法來說在每一次的迭代過程中計算復雜度是至關重要的，在這一部分對NLGE 算法在每一次迭代過程中的計算復雜度進行詳細的分析。其中，N表示訓練樣本的總數，m表示特征維數，r表示原始圖像數據進行矩陣分解后的矩陣特征維數，通常有r?m，q表示整數。本文首先討論了關于快速低秩的近似問題，隨機矩陣Y1=XA1和Y2=XTA2是原始數據矩陣X的秩為r的近似值，L的計算包括一個r×r的逆矩陣和三個矩陣的乘積。因此，對于稠密矩陣X需要2Nmr次計算來獲得BRP。要獲得式（18）中的L需要r2(2N+r)+Nmr次的計算，式（18）中的L被認為是從Y1和Y2中恢復的秩為r的矩陣X，A1和A2是獨立的高斯隨機矩陣。

對于式（22）的方法，需要一個r×r的逆矩陣和五個矩陣的乘積。對于一個稠密矩陣X需要2(2q+1)×Nmr次計算來獲得BRP，進行QR分解需要2r2(N+2r)+Nmr次計算來獲得L。式（22）的方法通過增加q來減小式（18）方法的誤差，當A1和A2由Y1和Y2構成時，獲得BRP 需要額外增加Nmr次計算。

在式（18）和式（22）中本文使用了基于雙邊隨機投影（BRP）的低秩近似，根據上述總結如下：當整數q=0 時，對于稠密矩陣X，式（18）被使用，此時Y1和Y2不進行QR分解，在這種情況下，在每一次的迭代過程中要獲得矩陣L需要r2(2N+r)+4Nmr次計算；當整數q>0 時，式（22）被使用，這時要獲得L需要r2(m+3N+4r)+(4q+4)×Nmr次計算在每一次的迭代過程中。之前的研究表明，非負矩陣分解算法（NMF）在每一次的迭代過程中需要Nmr次計算，非負圖嵌入算法（NGE）在每一次的迭代更新過程中需要Nr2+Nmr+mr2次計算，本文所提出的非負低秩圖嵌入算法（NLGE）在q=0 時，在每一次的迭代更新過程中需要r2(2N+r)+4Nmr+Nr2+Nmr+mr2次計算；當q>0 時，需要r2(m+3N+4r)+(4q+4)×Nmr+Nr2+Nmr+mr2次計算。一般情況下，在NLGE 算法的計算復雜度中增加了Nr2和Nmr兩個加項，使得NLGE算法的魯棒性得到一定程度的提高。

4 實驗和結果分析

為了驗證NLGE 算法的優異性，分別在ORL、CMU PIE 和YaleB、USPS 四個數據庫上進行了實驗。在本文的實驗中，利用了Matlab 2016 平臺進行仿真實驗，操作系統為Windows 10，64 位的操作系統和基于X64 的處理器，運行內存為8 GB。

4.1 實驗所用數據庫

ORL 人臉庫是由劍橋大學實驗室所創建，圖像包括了表情、姿態、光照條件和面部表情的變化。它由40個人共400 張面部圖像組成，每個人有10 張灰度圖像，由于照片拍攝于不同的時期，人臉和面部表情有著不同程度的變化，深度旋轉和平面旋轉可達20°，在本文的實驗中，圖像的大小為32×32，圖1 是用于實驗的部分ORL 人臉圖像。

Fig.1 Example of some images in ORL database圖1 ORL 數據庫中的部分圖像示例

CMU PIE 人臉庫包含41 368 張68 名志愿者在13 種不同姿勢，43 種不同照明條件下的面部圖像，并有4 種不同的表情方式。在本文的實驗中，選擇姿態C05 中的圖像進行實驗，并將其壓縮為32×32 像素，圖2 是用于實驗的部分CMU PIE 人臉圖像。

YaleB 人臉數據庫由38個人的2 432 張人臉組成，每個人大約有64 張在不同光照條件下的灰度圖像，在本文的實驗中，圖像的大小為32×32，圖3 是用于實驗的部分YaleB 人臉圖像。

USPS 數據庫包含10個手寫數字，其類別從“0”到“9”不等，整個數據庫有9 298 張灰度圖像。圖4 是用于實驗的部分USPS 圖像。

Fig.2 Example of some images in CMU PIE database圖2 CMU PIE 數據庫中的部分圖像示例

Fig.3 Example of some images in YaleB database圖3 YaleB 數據庫中的部分圖像示例

Fig.4 Example of some images in USPS database圖4 USPS 數據庫中的部分圖像示例

4.2 算法比較

為了驗證NLGE 算法的有效性，將它與NMF、GNMF、NGE、NLMF、GNLMF、RNGEL1、RNGEL21等算法進行了比較，詳細算法如下：

NMF：非負矩陣分解算法[1]，它試圖找出兩個非負低維矩陣，其乘積近似為原始矩陣。

GNMF：圖正則化非負矩陣分解算法[4]，它試圖通過構造一個簡單的圖來包含數據中的內在幾何信息。

NGE：圖嵌入算法[14]，它明確考慮了原始數據圖像攜帶的幾何信息。

NLMF：非負低秩矩陣分解算法[5]，它試圖挖掘原始圖像數據集的有效低秩結構。

GNLMF：圖正則化非負低秩矩陣分解[5]，它將隱藏在圖像集中的有效低秩結構部分和數據的流行結構進行融合。

RNGEL1：L1范數的魯棒非負低秩圖嵌入算法[16]，該算法把L1 范數融入到標準圖嵌入算法的目標函數中。

RNGEL21：L21 范數的魯棒非負低秩圖嵌入算法[16]，該算法把L21 范數融入到標準圖嵌入算法的目標函數中。

4.3 實驗中各算法的主要參數設置

K-means：聚類的類別數設置為Nc（實際類別），重復運行次數設置成20。

NMF：最大迭代次數設置為100，重復運行次數設置成20。

GNMF：最大迭代次數設置為100，平衡參數λ設置為100，權重取0-1 權重，取最近鄰參數K=5，重復運行次數設置成20。

NGE：設置r=d，權重取0-1 權重，取最近鄰參數K=5，平衡參數λ的范圍設置成lgλ∈[-3,4]，迭代次數設置為1 000，參數norm（范數）設置為2，調整不同的矩陣維數d來得到最佳結果，重復運行次數設置成20。

NLMF：最大迭代次數設置成100，重復運行次數為20。

GNLMF：最近鄰數設置為5，圖正則化參數設置為100，重復運行次數為20。

RNGEL1：設置r=d，權重取0-1 權重，取最近鄰參數K=5，平衡參數λ的范圍設置成lgλ∈[-3,4]，迭代次數設置為1 000，參數norm（范數）設置為1，調整不同的矩陣維數d來得到最佳結果，重復運行次數設置成20。

RNGEL21：設置r=d，權重取0-1 權重，取最近鄰參數K=5，平衡參數λ的范圍設置成lgλ∈[-3,4]，迭代次數設置為1 000，參數norm（范數）設置為21，調整不同的矩陣維數d來得到最佳結果，重復運行次數為20。

NLGE：調整不同的維數d來得到最優的結果，內在圖S和懲罰圖SP的最近參數分別設置K=3，KP=30，平衡參數λ的范圍設置為lgλ∈[-3,4]，迭代次數設置為1 000，參數norm（范數）設置為2，重復運行次數為20。

4.4 評價準則

使用標準化互信息（normalized mutual information，NMI）從信息點來評估聚類的質量，該方法被廣泛用于聚類結果的評價，定義了集群分配之間的相互信息和類的基本真值標記，其標準化是集群分配和真值標記熵的平均值。NMI的定義如下：

這里，C={c1,c2,…,cN}是由已知的類提供的真實值標簽，S={s1,s2,…,sN}是一個特殊的聚類結果，I(S,C)是具有基本真值標簽聚類分配的相互信息，H(S)是聚類結果的熵。

正確率（AC）是另一種用于度量分類結果的方法，AC的定義為：

其中，δ(?,?)是delta 函數，ci為樣本的真實類別，si為用算法對樣本求出的類別。

4.5 性能的評價和比較

通過在4個數據庫上進行實驗來驗證本文所提出的NLGE 算法的優越性。

Fig.5 NMI of each algorithm on ORL database圖5 各算法在ORL 庫上的NMI

Fig.6 NMI of each algorithm on CMU PIE database圖6 各算法在CMU PIE 庫上的NMI

Fig.7 NMI of each algorithm on YaleB database圖7 各算法在YaleB 庫上的NMI

根據表1、圖5、圖6、圖7 和圖8 可以看出，NMF的聚類性能最差，均低于其他聚類算法。在聚類算法中，本文所提出的NLGE 算法由于考慮了數據的低秩結構和流形信息，使得它比其他算法的聚類性能要優異。由表2、圖9、圖10、圖11 和圖12 可知，NMF算法的分類正確率均低于其他算法，這是因為其他算法考慮了數據的流形結構或低秩結構，表明在矩陣分解過程中考慮數據幾何結構和低秩結構是非常重要的。由于NLGE 算法同時考慮了原始圖像數據的幾何信息和有效低秩結構，因此其分類準確率高于其他分類算法，這表明數據的幾何結構和低秩結構在特征提取中起著重要作用，進而提高分類的準確率。實驗中，隨機選取樣本數據，并重復進行20次，最終的結果是這20 次實驗結果的平均值。實驗結果表明本文所提出的NLGE 算法不僅可以有效獲取原始圖像數據集的有效低秩結構，還增強了抗噪聲的魯棒性，使得其在聚類和分類的情況下都表現出一定的優異性能。

Table 1 Clustering results NMI of each algorithm on 4 databases表1 各算法在4個數據庫上的聚類結果NMI %

Fig.8 NMI of each algorithm on USPS database圖8 各算法在USPS 庫上的NMI

Fig.9 AC of each algorithm on ORL database圖9 各算法在ORL 庫上的AC

Fig.10 AC of each algorithm on CMU PIE database圖10 各算法在CMU PIE 庫上的AC

Fig.11 AC of each algorithm on YaleB database圖11 各算法在YaleB 庫上的AC

Table 2 Classification results AC of each algorithm on 4 databases表2 各算法在4個數據庫上的分類結果AC %

Fig.12 AC of each algorithm on USPS database圖12 各算法在USPS 庫上的AC

根據表3可以看出，NMF的運行時間少于GNMF，這是因為NMF 只需要更新兩個變量，而GNMF 算法要先對原始數據構建圖，然后進行變量的更新。NGE 算法要完成內在圖和懲罰圖的構建和變量的更新，因此其運行時間大于NMF 和GNMF。本文所提出的NLGE 算法先對原始圖像數據進行低秩處理，然后進行內在圖和懲罰圖的構建，最后進行變量的更新，因此其運行時間一般大于其他算法的運行時間。

Table 3 Running time of each algorithm on 4 databases表3 各算法在4個數據庫上的運行時間 s

5 結束語

本文提出了一種非負低秩圖嵌入算法（NLGE），該算法明確考慮了原始圖像數據集的有效低秩結構和幾何信息，圖嵌入和數據重構的聯合稀疏性對噪聲有一定的魯棒性。另外，還給出了求解NLGE 算法的迭代公式和收斂性證明，使得NLGE 算法在有噪聲數據情況下表現出較好的性能。最后，NLGE 在ORL、CMU PIE、YaleB 和USPS 數據庫上的實驗表現出較高的識別率和較好優越性。