杜 漢，龍顯忠*，李 云

（1.南京郵電大學計算機學院、軟件學院、網(wǎng)絡空間安全學院，南京 210023；2.江蘇省大數(shù)據(jù)安全與智能處理重點實驗室（南京郵電大學），南京 210023）

（?通信作者電子郵箱lxz@njupt.edu.cn）

0 引言

非負矩陣分解（Non-negative Matrix Factorization，NMF）是將非負約束整合到一般的矩陣分解中［1-2］，其目標是找到兩個非負矩陣，使其乘積能夠最大可能地近似原矩陣。具體而言，NMF 是使用基向量的線性組合來表示原始數(shù)據(jù)，并且線性組合和基向量中的元素值都是非負的。這與大腦對于事物認知的方式是一致的，都是對于事物整體的認知是基于對事物整體的部分的認知［3-5］。已有研究表明，當基向量的數(shù)量較大時，NMF是一個NP-hard問題［6-8］，并且相應的文獻已經(jīng)證實了在何種條件下NMF 是可解的［9］。NMF 應用在諸多方面，如文檔聚類［10］、人臉識別［11］、DNA 基因表達［12］、疾病關聯(lián)預測［13］等。其中最具代表性的研究工作是用于人臉識別的局部非負矩陣分解（Local Non-negative Matrix Factorization，LNMF）［11］和用于圖像聚類的圖正則非負矩陣分解（Graph Regularized Non-negative Matrix Factorization，GNMF）［14］。研究人員將基于NMF 的方法分為四大類［15］，并從理論上對其進行分析，分別是：非負矩陣分解（Basic NMF），僅添加了非負的約束；受限的非負矩陣分解（Constrained NMF），即增加了一些額外的約束，如添加正則化項等；結構化的非負矩陣分解（Structured NMF），修改了標準的因式分解公式；廣義非負矩陣分解（Generalized NMF），在廣義上突破了傳統(tǒng)的數(shù)據(jù)類型或因式分解的模式。此外，在傳統(tǒng)NMF 的基礎上，通過結合深度學習提出了一些新穎的人臉識別方法，其中性能較為先進的是采用三層金字塔模型獲取圖像多尺度信息和采用生成對抗網(wǎng)絡訓練人臉與草圖之間的映射關系［16］。對于人臉識別，在損失函數(shù)中嵌入自適應圖學習的思想，實現(xiàn)了一種新的人臉識別訓練策略，并且該方法調(diào)整了不同訓練階段中容易識別樣本和難識別樣本的相對數(shù)量比例［17］。

近年來，諸多研究發(fā)現(xiàn)高維數(shù)據(jù)通常位于非線性的低維流形空間中。因此，提出了各種各樣的流形學習算法用以發(fā)現(xiàn)高維數(shù)據(jù)在低維空間中的非線性表示［18］。針對流形學習的優(yōu)點，提出了幾種基于流形學習的NMF 的方法，如圖正則非負矩陣分解（GNMF）［14］、保持鄰域正交投影非負矩陣分解［19］、魯棒性的基于圖重構非負矩陣分解［20］以及稀疏對偶圖正則化深度非負矩陣分解［21］。然而，在這些方法中，構造圖的過程和NMF 的迭代過程是相互獨立的。即這些算法一旦被用來構造圖，在隨后的矩陣分解過程中，它的圖結構不會再發(fā)生變化。為了解決這一問題，已有文獻提出了下面幾種算法：自適應圖正則的低秩矩陣分解［22］、魯棒自動圖正則判別的非負矩陣分解［23］、基于自適應稀疏圖正則化的非負矩陣分解［24］、自適應離散超圖匹配［25］、自適應近鄰的NMF［26］和局部受限的自適應圖NMF［27］。在這些算法的迭代過程中，可以同時學習系數(shù)矩陣、基矩陣以及圖的權重矩陣。

樣本的標簽信息對于分類任務十分重要，于是有研究提出了幾種半監(jiān)督NMF 算法，例如約束NMF［28］、基于半監(jiān)督的NMF［29］和基于共性提取和半監(jiān)督的NMF［30］。

本文的主要工作如下：

1）利用子空間學習中的自表示模型獲得自表示系數(shù)，并生成權重矩陣，從而得到拉普拉斯矩陣。本文將流形學習中拉普拉斯矩陣、子空間學習中的自表示以及用于判別的標簽信息結合到NMF 框架中，提出了圖學習正則判別非負矩陣分解（Graph Learning Regularized Discriminative Non-negative Matrix Factorization，GLDNMF）算法，在它的迭代求解過程中，由于對自表示系數(shù)進行更新，所以該算法中的拉普拉斯矩陣在每一次迭代過程中都會被更新。

2）利用訓練集的標簽信息構造類別指示矩陣，并分別用降維后的訓練樣本和權重系數(shù)矩陣分別重構類別指示矩陣，從而得到兩個不同的正則項，使得學習到的投影矩陣保持了數(shù)據(jù)的判別信息。

1 相關工作

從模式識別的角度看，NMF 可以看作是無監(jiān)督學習。通過添加樣本的標簽信息，NMF 可進一步擴充為監(jiān)督學習，即判別NMF。它現(xiàn)在正被成功地應用于圖像分類任務中，如人臉識別和面部表情識別。

目前，大量的分類文章大多以廣義KL 散度（Kullback-Leibler Divergence）為基礎，通過引入不同的判別約束來構造目標函數(shù)。在此基礎上，又出現(xiàn)了大量的判別NMF 應用于人臉識別，分別是加上局部約束的非負矩陣分解（LNMF）［11］，加上拉普拉斯矩陣的非負矩陣分解（GNMF）［14］，以及加上流形學習和判別信息的圖正則判別非負矩陣分解（Graph Regularized Discriminative Non-negative Matrix Factorization，GDNMF）［31］。

本章將介紹NMF 算法以及它的幾種典型變體，同時回顧了兩種經(jīng)典的降維算法：主成分分析（Principal Component Analysis，PCA）［32］和局部保持投影（Locality Preserving Projections，LPP）［33］算法。設矩陣X=[x1，x2，…，xn]∈Rm×n，每一列代表一幅m維的圖像。一般來說，當數(shù)值m較大時，會導致維數(shù)災難，從而導致識別精度低并且識別速度慢，因此，有必要在人臉識別之前進行降維，下面將介紹六種常用的維數(shù)約減算法。

1.1 非負矩陣分解

NMF 即對于任意給定的一個非負矩陣X∈Rm×n能夠分解成兩個非負矩陣W∈Rm×r和H∈Rr×n(r?min(m，n))相乘的形式，如下所示：

為解決NMF 的優(yōu)化問題［2，7］，提出了如乘性更新算法、交替最小二乘算法和梯度下降算法等。

利用歐氏距離度量NMF重構誤差的優(yōu)化問題如下：

其中：||?||F表示Frobenius范數(shù)；X∈Rm×n是數(shù)據(jù)矩陣；W∈Rm×r為基矩陣；H∈Rr×n為系數(shù)矩陣。矩陣X、W和H中的元素都是非負的。對應的乘性更新規(guī)則如（3）所示：

1.2 圖正則非負矩陣分解

基于流形學習理論，研究人員提出了GNMF 模型［14］。在該模型中，高維空間中相鄰的數(shù)據(jù)點在低維流形空間中仍然保持相鄰。

利用歐氏距離度量GNMF重構誤差的優(yōu)化問題如下：

其中：Tr（）為矩陣的跡；L為拉普拉斯矩陣；正則化參數(shù)λ≥0控制重構誤差與正則項之間的平衡性。

1.3 圖正則判別非負矩陣分解

在GNMF 的目標函數(shù)中加入標簽信息來構造圖正則判別非負矩陣分解（GDNMF）［31］，此模型能夠使分類的精確度比GNMF更高。

利用歐氏距離度量GDNMF重構誤差的優(yōu)化問題如下：

其中：參數(shù)λ和β的值都是非負的；Y是一個類別指示矩陣；A是一個隨機初始化的非負矩陣。

1.4 局部非負矩陣分解

在NMF 的基礎之上，通過添加局部約束提出了局部非負矩陣分解（LNMF）［11］，能夠更進一步地提取圖像的局部特征。LNMF 對基矩陣添加了空間局部性的約束，所以在學習基矩陣的過程中，表現(xiàn)出了比NMF 更加優(yōu)異的性能，并且隨著原始圖像維數(shù)的增加，LNMF所學習到的特征更加局域化。

利用KL散度度量LNMF重構誤差的優(yōu)化問題如下：

其中：參數(shù)α和β大于0；D(X‖WH)表示KL 散度；U=WTW；V=HHT。

1.5 主成分分析

主成分分析（PCA）是一種最廣泛的數(shù)據(jù)降維算法。它的主要思想是將m維特征映射到d維上，這d維是全新的正交特征，也被稱為主成分，即在原有m維特征的基礎上重新選擇出來的d維特征。假設數(shù)據(jù)樣本已經(jīng)中心化，即；再假設投影變換后得到的新坐標系為{b1，b2，…，bm}，其中bi是標準正交基向量。若丟棄新坐標系中的部分坐標，即將維度降低到d（d＜m）維，則樣本點xi在低維坐標系中的投影是zi=(zi1；zi2；…；zid)，其中是xi在低維坐標系下第j維的坐標。

考慮整個數(shù)據(jù)矩陣X，原樣本點xi和基于投影重構的樣本點之間的距離用歐氏距離可表示為：

其中：矩陣B為矩陣X投影變化后得到的新坐標系；矩陣I為單位矩陣。

1.6 局部保持投影

局部保持投影（LPP）是非線性降維方法的線性化，進一步可理解為相互間有某種非線性關系的樣本點在降維之后仍然保持這種非線性關系，如原始空間內(nèi)距離較近的樣本點，映射后對應樣本的距離仍然較近。

根據(jù)原始數(shù)據(jù)構造一個鄰接圖，對應的權重矩陣為E（鄰接圖中點相鄰為1，否則為0），令映射后的數(shù)據(jù)矩陣為T=(t1，t2，…，tn)。原始樣本與映射后的數(shù)據(jù)樣本之間的重構誤差為：

2 圖學習正則判別非負矩陣分解

2.1 GLDNMF模型

受子空間聚類中自表示學習的啟發(fā)，利用得到的自表示系數(shù)構造親和矩陣（權重矩陣）［34］。根據(jù)親和矩陣進一步構造拉普拉斯矩陣，并使其在迭代過程中不斷更新。為了更進一步利用標簽信息，構造一個類別指示矩陣Y∈Rr×n，其定義如下：

其中：sj∈{1，2，…，r}表示第j個樣本xj的標簽；r和n分別是訓練集X中的樣本類別數(shù)和樣本總數(shù)。Y中每個行向量的代數(shù)和表示從每類中隨機選取的用來構造訓練集的圖像個數(shù)。

圖學習正則判別非負矩陣分解的模型如下：

其中：參數(shù)λ、γ和β是三個非負常數(shù)；C∈Rn×n為自表示的系數(shù)矩陣，diag(C)=0 表示矩陣C的主對角線上的元素全為0；P=(C+CT)/2 是一個親和矩陣，根據(jù)P可得到對角矩陣Q∈Rn×n，Q的主對角線上的元素Qii是P的第i行（或第i列，因為P是對稱的）之和，即；拉普拉斯矩陣L=Q-P，L∈Rn×n；A∈Rr×r是一個隨機初始化的非負矩陣。

式（11）中的第一項為NMF 的基本公式，第二項是子空間學習中的自表示約束，它可以學習到一個新的自表示系數(shù)矩陣C，然后通過C構造L所需的P和Q。通過引入自表示約束正則項，使式（11）中的L不斷地被更新，在每次迭代過程中均能構造出最優(yōu)的圖結構，提升模型保相似性的能力。第4 項和第5 項是利用訓練集的標簽信息構造類別指示矩陣，并分別用降維后的訓練樣本和權重系數(shù)矩陣重構類別指示矩陣，增強模型的判別能力。

從本質(zhì)上講，GLDNMF 是將子空間學習、圖學習、流形學習和標簽信息一起整合到NMF 的框架中。通過求解式（11）得到的基矩陣W不僅具有保相似性結構的能力，同時蘊含了很好的判別能力。

2.2 GLDNMF的更新規(guī)則

雖然式（11）對于（W，H，C，A）不是凸函數(shù)，但當固定式（11）的其他變量時，對于（W，H，C，A）中的一個變量是凸函數(shù)。式（11）的目標函數(shù)可以進一步地寫成如下形式：

應用矩陣跡的性質(zhì)Tr(AB)=Tr(BA)和Tr(A)=Tr(AT)。令φ、ψ、Ω和θ分別為W、H、C、和A的拉格朗日乘子，則J對應的拉格朗日函數(shù)的形式為：

分別對Lf中的W、H、C和A求偏導數(shù)：

由KKT 條件φijWij=0、ψjkHjk=0、ΩkkCkk=0 和θjj Ajj=0，可以得到下面的公式：

于是，式（11）中關于W、H、C和A的乘性更新規(guī)則為：

在式（22）～（25）的更新規(guī)則下，目標函數(shù)

是非增的。目標函數(shù)中的W、H、C和A分別進行迭代，直到迭代次數(shù)超過設置的最大值或者式（11）的值趨于不變。具體流程如算法1所示：

算法1 圖學習正則判別非負矩陣分解。

輸入 訓練集矩陣X∈Rm×n，類別指示矩陣Y∈Rr×n，參數(shù)λ、γ、β和r（r為訓練集中樣本的類別總數(shù)）；

輸出 基矩陣W。

過程

①初始化：隨機初始化4 個矩陣W∈Rm×r，H∈Rr×n，C∈Rn×n，diag(C)=0，A∈Rr×r；計算P和Q；

②通過式（22）～（25）依次更新W、H、C、A；

③更新diag（C）=0；

④計算P=(C+CT)/2，；

⑤迭代步驟②～④直到目標函數(shù)的值趨于不變或者迭代次數(shù)到達所設定的最大值。

2.3 RCGLDNMF模型

RCGLDNMF 模型去掉了GLDNMF 中的自表示學習正則項，其中RC是Remove C 的英文簡寫，即不與GLDNMF 中學習到的自表示系數(shù)矩陣C結合，其模型為：

參數(shù)設置和矩陣語義均與GLDNMF 保持一致，但采用GNMF 中的相同方式構造拉普拉斯矩陣L所需的矩陣P和Q，并使用式（22）、（23）和（25）迭代更新W、H和A，在更新過程中不再修改矩陣L。

2.4 算法1的收斂性證明

為了證明本文所提出的算法1，需要證明O1在式（22）～（25）的更新步驟下不增加。對于目標函數(shù)O1，如果僅更新W，需要固定H、C和A，所以O1的第一項和第四項存在；同樣，如果更新C，需要固定W、H和A，則O1的第二項存在。因此，本文對圖學習正則判別非負矩陣分解中的W、C和A的更新公式與NMF中的公式相同。于是，本文利用NMF的收斂性證明來證明O1在式（22）、（24）和（25）的更新步驟下是不增加的。而NMF 的收斂性已被證實［2］，因此，本文只需要證明O1在式（23）的更新步驟下是不增加的。本文遵循其中描述的過程，利用輔助函數(shù)可以證明O1的收斂性。

定義當G(h，h′)滿足以下條件為F(h)的輔助函數(shù)：

此輔助函數(shù)對于以下的引理非常重要。

引理1如果G是F的輔助函數(shù)，那么F在更新的過程中是非遞增的。

現(xiàn)在證明在式（23）中對H的更新等同于對在上述輔助函數(shù)的條件下對式（28）的更新。

考慮任意元素hab∈H，用Fab表示在O1中只與Hab有關的元素。通過對其求偏導易得出下列式子：

由于更新的本質(zhì)是基于元素的，所以這足以說明在式（23）的更新步驟下每個Fab都是非遞增的。于是，引入以下引理。

引理2函數(shù)

是Fab的輔助函數(shù)。

證明 由于G(h，h)=Fab(h)是顯而易見的，所以僅證明。因此，首先考慮用Fab(h) 的泰勒展開公式：

并且存在以下事實：

和

由于式（32）為輔助函數(shù)，所以在此更新規(guī)則下Fab是非遞增的。

3 實驗與結果分析

本文在兩個人臉數(shù)據(jù)集UMIST［35］和Yale［36］（部分示例如圖1 所示）上測試了所提算法的識別性能，并與已有的典型算法進行對比，包括：PCA、LPP、NMF、LNMF、GNMF、GDNMF 和RCGLDNMF，而且實驗中不同算法的相同參數(shù)都取一樣的值。

圖1 UMIST和Yale數(shù)據(jù)集中的人臉圖像示例Fig.1 Face image examples of UMIST and Yale datasets

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

兩個數(shù)據(jù)集的統(tǒng)計描述如表1所示。

表1 兩種數(shù)據(jù)集的統(tǒng)計Tab.1 Statistics of two datasets

UMIST 人臉數(shù)據(jù)集包含20 個人的575 張PGM 格式的圖像，每一類的樣本數(shù)從19～48 張不等。將每幅圖像下采樣為40×40 像素陣列，然后使陣列中的每一列首尾相接拼成一個列向量。Yale 人臉數(shù)據(jù)集包含15 個人的165 張GIF 格式的圖像，每一類的樣本數(shù)為11 張圖像。將每幅圖像下采樣為40×40 像素陣列，然后使陣列中的每一列首尾相接拼成一個列向量。

3.2 實驗過程

實驗中使用的所有人臉圖像都是手動對齊和裁剪的。每張人臉圖像都被表示為一個列向量，而后將其特征（像素值）縮放到［0，1］（即每個像素點的值除以255）。從每個類中隨機選取一些圖像構造訓練集，例如表2中的5train 表示每類中隨機選取5 個樣本構造訓練集，剩余的圖像構造測試集，其他情況以此類推。如表1 所示，在UMIST 和Yale 數(shù)據(jù)集中，UMIST 中每類的樣本數(shù)目為19～48，而Yale 中每類的樣本數(shù)目為11，所以在UMIST 數(shù)據(jù)集中可以選擇11train，而在Yale數(shù)據(jù)集中最多只能選擇9train。將訓練集輸入到不同的模型中學習低維空間的基矩陣，并將學習到的基矩陣作為投影矩陣分別對訓練集和測試集進行降維。測試集用于測試在得到的低維空間中人臉識別的準確性。在本文實驗中，使用1-近鄰分類器。在計算基矩陣W的過程中，NMF及基于NMF的各種改進算法都要進行1 000 次的重復迭代。這些實驗獨立進行10次，然后計算出平均精度，以保證實驗結果的準確性。

3.3 實驗參數(shù)選擇

本文提出的GLDNMF 存在三個正則化參數(shù)，即λ、γ和β。在實驗中，固定從每類中選取的樣本數(shù)量，以此來分析參數(shù)對識別精度的影響，實驗中隨機從每類中選取5 張圖像構造訓練集，每類中剩余的圖像構造測試集。本文算法在不同數(shù)據(jù)集上的平均識別精度會隨著參數(shù)值的變化而變化。

圖2 是固定γ和β時，準確率與λ的關系曲線，可以看出，隨著λ的增大，識別精度并未表現(xiàn)出明確的規(guī)律性，波動幅度較大，但在λ＜100 時，隨著λ的增大，識別精度雖有劇烈波動，但大體趨勢是逐漸升高，并在λ=100 時達到頂峰，而后λ繼續(xù)增大時，識別精度的大體趨勢是逐漸減小。圖3是固定λ時，準確率與γ和β的關系曲線，可以看出，隨著γ的增大，識別精度在逐漸提高，但是，隨著β的增大，識別精度時好時壞，綜合UMIST 和Yale 數(shù)據(jù)集中的表現(xiàn)，選擇γ較大，β較小。綜合考慮三個參數(shù)的取值在兩個數(shù)據(jù)集上的實驗結果，折中選擇的實驗參數(shù)取值為：λ=100，γ=0.6，β=0.2。

圖2 γ和β不變時準確率與λ的關系Fig.2 Relationship between accuracy and λ with fixed γ and β

圖3 λ不變時準確率與γ和β的關系Fig.3 Relationship among accuracy and γ，β with fixed λ

表2 與表3 中的RCGLDNMF 是在設置相同參數(shù)值時，去掉自表示的正則化項后進行的模型測試結果，即在該模型的學習過程中，不再更新拉普拉斯矩陣。表2和表3中的粗體表示在相同參數(shù)的情況中，不同算法用于人臉識別的最佳平均準確率。

表2 不同算法在UMIST數(shù)據(jù)集上的平均準確率Tab.2 Average accuracies of different algorithms on UMIST dataset

表3 不同算法在Yale數(shù)據(jù)集上的平均準確率Tab.3 Average accuracies of different algorithms on Yale dataset

從表2、3 的實驗數(shù)據(jù)可以看出，GLDNMF 比RCGLDNMF在識別精度上最多達到5 個百分點的提升，這說明在模型學習過程中更新拉普拉斯矩陣對識別精度是有益的。而且在此實驗中，數(shù)據(jù)集要降到的維數(shù)r為訓練集中樣本的類別總數(shù)：對于UMIST數(shù)據(jù)集，r=20；對于Yale數(shù)據(jù)集，r=15。

圖4 驗證了本文算法的收斂性，隨著迭代次數(shù)的增加重構誤差趨于平緩并且不變。

圖4 迭代次數(shù)與重構誤差之間的關系Fig.4 Relationship between iteration number and reconstruction error

4 結語

本文提出了圖學習正則判別非負矩陣分解算法GLDNMF，同時引入了子空間聚類中的自表示學習、流形學習和標簽信息。在非負矩陣分解的迭代過程中不斷更新圖的拉普拉斯矩陣，可以更好地保持高維數(shù)據(jù)在低維空間中的結構信息，利用訓練集的標簽信息可以提高投影矩陣的判別能力。實驗結果表明，與PCA、LPP、非負矩陣分解及其幾種有代表性的變體相比，GLDNMF 具有更強的判別能力和更高的識別精度。