孫 靜，蔡希彪，孫福明

(遼寧工業(yè)大學 電子與信息工程學院，遼寧 錦州 121001) (*通信作者電子郵箱sunjing616@foxmail.com)

基于特征融合的多約束非負矩陣分解算法

孫 靜*，蔡希彪，孫福明

(遼寧工業(yè)大學 電子與信息工程學院，遼寧 錦州 121001) (*通信作者電子郵箱sunjing616@foxmail.com)

針對非負矩陣分解后數(shù)據(jù)的稀疏性降低、單一圖像特征不能夠很好地描述圖像內(nèi)容的問題，提出一種基于特征融合的多約束非負矩陣分解算法。該算法不僅考慮了少量已知樣本的標簽信息和稀疏約束，還對其進行了圖正則化處理，而且將分解后的具有不同稀疏度的圖像特征進行了融合，從而增強了算法的聚類性能和有效性。在Yale-32和COIL20數(shù)據(jù)集上進行的對比實驗進一步驗證了該算法具有更好的聚類精度和稀疏性。

非負矩陣分解；標簽信息；稀疏約束；圖正則；特征融合

0 引言

近幾年來，隨著社交媒體的興起以及互聯(lián)網(wǎng)技術的發(fā)展，圖像數(shù)據(jù)產(chǎn)生了爆炸性的增長。圖像視覺特征與高層語義之間“語義鴻溝”的存在成為了圖像檢索領域發(fā)展的瓶頸。因此，如何有效地表示圖像的視覺特征是提高圖像內(nèi)容的利用效率、縮小語義鴻溝的核心問題。圖像特征表示是指利用統(tǒng)計學習的方法(也常稱為維數(shù)約簡)將樣本從輸入空間(底層視覺特征)線性或者非線性地映射到一個低維空間，從而獲得關于原數(shù)據(jù)集一個比較緊致的低維表示。一般情況下，都會用向量來表示圖像數(shù)據(jù)，即向量中的元素表示圖像樣本的特征，將其按照逐行或者逐列的順序拉伸成為一個向量來表示圖像數(shù)據(jù)。但是，該方法常常因其維數(shù)過高導致計算呈指數(shù)增長從而造成“維數(shù)災難”[1]。為了解決圖像數(shù)據(jù)表示中存在的“維數(shù)災難”問題，人們提出了若干維數(shù)約簡的方法。典型的維數(shù)約簡算法主要包括主成分分析[2]、線性判別分析[3]、獨立分量分析[4]、奇異值分解[5]、非負矩陣分解(Non-negative Matrix Factorization, NMF)[6]及流形學習[7]等。其中，NMF算法與其他維數(shù)約簡方法不同，它的獨特之處在于矩陣分解過程中施加了非負約束，即在矩陣分解過程中所有元素都是非負的。NMF將原始矩陣分解為左右兩個非負矩陣的乘積，稱左側(cè)的矩陣為基矩陣，右側(cè)的矩陣稱為系數(shù)矩陣。因此，可以將原始矩陣的列向量用基矩陣中列向量的加權和來表示，這里的權重系數(shù)就是系數(shù)矩陣。這種向量組合具有直觀的語義解釋，符合人類思維中“局部構成整體”的概念[8]。由于非負約束的引入使得NMF具有良好的純加性和數(shù)據(jù)描述性，從而使其更加貼近應用領域。

NMF算法自提出后得到了學術界的廣泛關注和深入研究，并獲得了大量的研究成果。為了提高NMF算法的有效性，滿足一定的需求并且達到期待的效果，大量學者在NMF框架中引入了各種約束，比如稀疏性、流形、正交性和判別性等，提出了若干種改進的NMF算法，并被成功地應用到各個領域，取得了良好的實驗效果。Cai等[7]將流形學習與NMF相結(jié)合提出了圖正則化非負矩陣分解(Graph Regularized Nonnegative Matrix Factorization，GNMF)算法，該算法考慮了原始數(shù)據(jù)中蘊含的幾何結(jié)構，使得低維表示很好地保留了原始數(shù)據(jù)樣本的近鄰結(jié)構；但是由于它沒有考慮數(shù)據(jù)集中的已知標簽信息，同時其稀疏性也不是很理想，因而限制了GNMF算法的應用。Liu等[9]提出一種半監(jiān)督約束非負矩陣分解(Constrained Nonnegative Matrix Factorization，CNMF)算法，該算法將已知標簽信息約束到NMF分解中，缺陷是沒有考慮樣本的幾何結(jié)構以及未施加稀疏約束。后來，胡學考等[10]在CNMF的基礎之上增加了稀疏約束，提出了基于稀疏約束的半監(jiān)督非負矩陣分解(Constrained Nonnegative Matrix Factorization with Sparseness，CNMFS)，該方法不僅考慮標簽信息，還對基矩陣進行了稀疏約束，實驗結(jié)果表明該算法的聚類精度高；但CNMFS算法并沒有考慮到原始數(shù)據(jù)所隱藏的幾何信息，因此限制了其應用范圍。隨后，姜小燕等[11]提出了基于圖正則化和稀疏約束的半監(jiān)督非負矩陣分解(Graph-regularized and Constrained Nonnegative Matrix Factorization with Sparseness，GCNMFS)算法，該算法在保持數(shù)據(jù)幾何結(jié)構的同時還利用已知樣本的標簽信息進行半監(jiān)督學習，并且對基矩陣施加稀疏約束，使分解后的人臉圖像有更高的識別率。以上算法均存在一定的不足，即單一的圖像特征并不能夠很好地描述圖像的內(nèi)容，所以不少學者提出了基于特征融合的NMF算法[12-14]，實驗結(jié)果表明這些算法相對于傳統(tǒng)的維數(shù)約簡方法有更好的效果。

本文通過深入分析基于NMF的圖像特征表示原理，探討如何通過綜合多種約束增強NMF的特征表示能力以及如何通過融合具有不同稀疏度的特征來提高部件的學習能力，提出了基于特征融合的多約束非負矩陣分解(Multi-Constraint Nonnegative Matrix Factorization based on Feature Fusion, MCNMFFF)的圖像分類算法，將非負矩陣分解用于圖像分類問題，最終獲得具有稀疏性和判別性的圖像低維特征，提高圖像分類的準確率。本文的主要工作在于：1)在NMF框架中同時施加先驗約束、稀疏約束和圖正則化，提高基矩陣的稀疏度，增強系數(shù)矩陣的鑒別能力。本文提出的MCNMFFF算法能夠較好地揭示圖像內(nèi)在的局部幾何特征。2)目前現(xiàn)存的基于特征融合的NMF方法均是將全局和局部等特征或形狀和顏色等特征進行融合，忽略了基矩陣的稀疏度，若基矩陣的稀疏度增加則學習部件的能力也會相應地提高，所以稀疏性對NMF是至關重要的。本文將NMF分解后的具有不同稀疏度的圖像特征進行了融合，解決了單一種類的圖像特征不能很好地描述所有不同語義圖像視覺內(nèi)容的問題，從而有效地提高了圖像的表示能力和聚類性能。3)給出了MCNMFFF算法的迭代更新公式，并證明了該算法的收斂性；同時，在兩個常用數(shù)據(jù)集上進行了聚類實驗，實驗結(jié)果驗證了MCNMFFF算法的有效性。

1 非負矩陣分解

對矩陣進行分解時，得到的結(jié)果并不一定是唯一解。同樣，矩陣進行NMF時往往也是不盡相同的。對于給定的n個非負樣本xi(i=1,2,…,n),每一個xi∈Rm都是m維的列向量，組成矩陣X=[x1,x2,…,xn]∈Rm×n。NMF算法的目的就是尋找兩個非負矩陣U∈Rm×k和V∈Rn×k(k≤mn/(m+n))，使得X≈UVT,也就是使X與UVT的差異值最小，即優(yōu)化目標函數(shù)。其中，U是基矩陣，V是系數(shù)矩陣，并且U和V中的元素都是非負的。NMF算法可用歐氏距離來描述目標函數(shù)：

(1)

s.t.U≥0,V≥0

其中:‖‖F(xiàn)是矩陣的Frobenius范數(shù)。式(1)是通過求解分解前后兩個矩陣元素差的平方來衡量X與UVT的相似度，其值越小，則說明X與UVT的相似度越高，即分解前后的矩陣距離越小；反之越大。

上述目標函數(shù)在對U和V同時求解時并不是凸函數(shù)，只有在單獨對U或者V求解時才是凸函數(shù)，且能得到最優(yōu)解。利用最速下降法和迭代法推導出目標函數(shù)(1)的乘性迭代更新公式如下：

(2)

(3)

其中:U=[uik],V=[vjk]。經(jīng)過推導證明，目標函數(shù)(1)在迭代更新規(guī)則下是收斂的，文獻[6]證明了NMF算法的收斂性。

2 基于特征融合的多約束非負矩陣分解

2.1 相關算法

GNMF算法在進行矩陣分解的同時，要求在低維空間中繼續(xù)保持樣本的幾何結(jié)構，也就是要求分解后的數(shù)據(jù)保持原始數(shù)據(jù)固有的結(jié)構信息。GNMF假設兩個數(shù)據(jù)點xi和xj在原始空間是鄰近點，那么在新基下相應的vi和vj也是鄰近點。

設G為原始數(shù)據(jù)點構成的圖，其中Rij表示權重矩陣，Np(xi)表示xi的p個近鄰，當xi或者xj屬于Np(xi),則Rij為1;否則為0。定義L=D-S,D是對角矩陣，L是拉普拉斯矩陣。GNMF算法的最小化目標函數(shù)為：

(4)

s.t.U≥0,V≥0

CNMFS在進行矩陣分解的同時不僅將已知標簽信息約束到NMF分解中，還對基矩陣進行了稀疏化。CNMFS算法的最小化目標函數(shù)為：

(5)

s.t.U≥0,Z≥0

GCNMFS綜合了GNMF和CNMFS算法的優(yōu)點，在保留數(shù)據(jù)蘊含的幾何結(jié)構的同時利用樣本的標簽信息進行半監(jiān)督學習，并且對基矩陣施加稀疏性的約束。GCNMFS算法的最小化目標函數(shù)為：

(6)

s.t.U≥0,Z≥0

2.2 MCNMFF目標函數(shù)

針對目前改進的NMF算法的優(yōu)缺點，同時考慮到單一種類的特征不可能對所有不同語義的圖像視覺內(nèi)容都能獲得滿意的描述結(jié)果，本文將多種約束引入NMF算法中，并將NMF分解的具有不同稀疏度的圖像特征進行融合，提出了MCNMFFF算法。首先，分別用CNMFS和GNMF模型在NMF算法中加入先驗約束、稀疏約束和圖正則化，這樣不僅能夠充分利用已知標簽信息來提高算法的鑒別能力，還能夠在低維的數(shù)據(jù)空間保持樣本的幾何結(jié)構，同時還可以提高基圖像的稀疏度；其次，將CNMFS和GNMF分解的具有不同稀疏度的圖像特征進行融合，從而解決單一種類的特征不能夠很好描述所有不同語義圖像視覺內(nèi)容的問題，進一步提高部件的學習能力；最后，將以上兩個部分整合到一個目標函數(shù)中，用數(shù)學理論進行推導證明來描述本文算法。本文提出的MCNMFFF算法的目標函數(shù)如下：

(7)

s.t.U1≥0,Z≥0,U2≥0,V≥0

其中:參數(shù)θ∈(0,1)是融合系數(shù)；參數(shù)β∈(0,1)為稀疏系數(shù),為了使優(yōu)化求解過程變得穩(wěn)定、快速，這里用Frobenius范數(shù)來約束稀疏項；λ≥0為正則化參數(shù)；U1是經(jīng)CNMFS分解后得到的基矩陣，U2是經(jīng)GNMF分解后得到的基矩陣；A是標簽約束矩陣，Z是輔助矩陣，且系數(shù)矩陣V=AZ。

MCNMFFF算法的目標函數(shù)與GCNMFS算法的目標函數(shù)略微不同：GCNMFS是將圖正則化和稀疏約束引入到NMF模型中與重構誤差作為一個整體來表示GCNMFS的目標函數(shù)；而MCNMFFF算法是將NMF模型分解后的具有不同稀疏度的圖像特征進行融合，該圖像特征由GNMF模型分解特征的和CNMFS模型分解的特征兩部分組成，所以MCNMFFF的目標函數(shù)主要是用兩個模型目標函數(shù)的加權來表示，其中每一部分均包含重構誤差和正則項。

2.3 MCNMFF迭代更新規(guī)則

由式(7)可知，目標函數(shù)單獨對于變量U1、Z、U2和V而言是凸函數(shù)，但是同時對于四個變量而言則是非凸函數(shù)，所以找到全局的最優(yōu)解是非常困難的。針對這一問題，本文采用最速下降法和迭代法來推導目標函數(shù)(7)的乘性迭代更新規(guī)則來尋找局部最優(yōu)解。

通過代數(shù)運算，目標函數(shù)(7)可以重寫為：

OF=θTr((X-U1ZTAT)(X-U1ZTAT)T)+

(1-θ)λTr(VTLV)

s.t.U1≥0,Z≥0,U2≥0,V≥0。

定義拉格朗日乘子δ、ε、φ和ρ,分別約束u1、z、u2和v。則由拉格朗日定理可得拉格朗日函數(shù)為：

(8)

1)更新變量U1。

將拉格朗日函數(shù)(8)對變量U1求偏導數(shù)，同時令偏導數(shù)為零，可得：

(9)

通過利用KKT(Karush-Kuhn-Tucker)條件δiju1ij=0,可將式(9)化簡為：

-(XAZ)u1+(U1ZTATAZ)u1+βU1u1=0

(10)

根據(jù)式(10)可以進一步得到變量U1的迭代更新規(guī)則：

(11)

2)更新變量Z。

將拉格朗日函數(shù)(8)對變量Z求偏導數(shù)，同時令偏導數(shù)為0，可得：

(12)

通過利用KKT條件εijzij=0,可將式(12)化簡為：

(13)

根據(jù)式(13)可以進一步得到變量Z的迭代更新規(guī)則：

(14)

3)更新變量U2。

將拉格朗日函數(shù)(8)對變量U2求偏導數(shù)，同時令偏導數(shù)為零，可得：

(15)

通過利用KKT條件φiju2ij=0,可將式(15)化簡為：

-(XV)u2+(U2VTV)u2=0

(16)

根據(jù)式(16)可以進一步得到變量U2的迭代更新規(guī)則：

(17)

4)更新變量V。

將拉格朗日函數(shù)(8)對變量V求偏導數(shù)，同時令偏導數(shù)為零，可得：

2(1-θ)λLV+ρ=0

(18)

通過利用KKT條件ρijvij=0,可將式(18)化簡為：

(19)

根據(jù)式(19)可以進一步得到變量V的迭代更新規(guī)則：

(20)

2.4 MCNMFFF收斂性證明

對于乘性更新規(guī)則式(11)、(14)、(17)和(20)，得出以下理論。

定理1 對于U1≥0、Z≥0、U2≥0和V≥0,目標函數(shù)(7)在式(11)、(14)、(17)和(20)的更新規(guī)則下是收斂的，即非增。

為了證明定理1，首先定義輔助函數(shù)。

定義1 若函數(shù)G(u,u′)是函數(shù)F(u)的輔助函數(shù)，則滿足G(u,u′)≥F(u),且G(u,u)=F(u)。

引理1 若函數(shù)G(u,ut)是函數(shù)F(u)的輔助函數(shù)，那么函數(shù)F(u)在以下更新規(guī)則下是非增的：

(21)

證明 很明顯，當u=ut時函數(shù)G(u,ut)取得最小值。由定義1可知，G(ut+1,ut)′≥F(ut+1)可表示為：

從中可看出，當ut為G(u,ut)的局部極小值時才有F(ut+1)=F(ut)。如果函數(shù)F(u)存在導數(shù)，并且在ut的一個微小鄰域內(nèi)連續(xù)，則有▽F(ut)=0。

由式(21)可以得到收斂到局部極小值點umin的序列：

F(umin)≤…≤F(ut+1)≤F(ut)≤…≤

F(u1)≤F(u0)

所以，通過定義輔助函數(shù)G(u,ut),可以使目標函數(shù)(7)的迭代規(guī)則滿足式(21)。

證畢。

需要證明更新規(guī)則(14)和式(21)是一致的。為此，用FZij表示目標函數(shù)中僅與Z中任一元素zij有關的部分，于是得到：

其中，F(xiàn)Zij′(zij)和FZij″(zij)分別表示函數(shù)FZij對變量zij的一階偏導數(shù)和二階偏導數(shù)。

引理2 定義目標函數(shù)中關于變量zij的輔助函數(shù)如下：

(22)

FZij(zij)的泰勒級數(shù)展開式如下：

(23)

(24)

根據(jù)線性代數(shù)可得如下不等式：

(25)

證畢。

最后證明定理1的收斂性。

證明 用輔助函數(shù)(22)代替式(21)中的G(u,ut),可以得到以下更新規(guī)則：

因為式(22)是函數(shù)的輔助函數(shù)，因此，采用當前規(guī)則更新是非遞增的。同時，目標函數(shù)(7)具有下界。綜上所述，定理1的收斂性獲證。

證畢。

由于目標函數(shù)(7)中的U1和Z是對稱的，U2和V也是對稱的，所以在U1、U2和V的迭代更新規(guī)則下同樣可用相似的證明過程來證明定理1。

3 實驗與分析

3.1 數(shù)據(jù)集及參數(shù)選擇

常用的人臉圖像和物體的數(shù)據(jù)集有Yale-32[15]、ORL、COIL20和PIE-pose27等，由于本文算法在幾個數(shù)據(jù)集上的實驗效果大致相同，所以在實驗中為了展示MCNMFF算法的有效性以及減少程序運行時間，選擇在Yale-32和COIL20兩個具有代表性的常用物體和人臉數(shù)據(jù)庫上進行驗證實驗。Yale-32數(shù)據(jù)集包含15名志愿者的面部表情圖像，因為所取表情不同所以每個人有11幅表情不一的圖像，每個志愿者的姿態(tài)表情包括：微笑、大笑、嚴肅、生氣等；面部是否有飾物等。該數(shù)據(jù)集共有165幅圖片。COIL20數(shù)據(jù)集包含20個不同的物體 (玩具小鴨、招財貓、杯子等)，其中，每個物體在水平面上每隔5°拍攝一張圖片，因此每個物體一共有72幅圖片，整個數(shù)據(jù)集共計1 440幅圖片。

MCNMFFF模型有三個關鍵的參數(shù)：融合系數(shù)θ、稀疏系數(shù)β和正則化參數(shù)λ。目標函數(shù)中的融合系數(shù)θ通常是由實驗的結(jié)果來決定的，一般說來，不同數(shù)據(jù)集對應的最佳融合系數(shù)值也不同。圖1給出了Yale-32數(shù)據(jù)集在取不同k值的情況下不同θ值對應的準確率。

從圖1中θ值與類別數(shù)k和準確率(Accuracy，AC)的關系曲線可以看出：在θ=[0.1,0.2]時，AC是隨著θ值的增大而增大的；在θ=(0.2,0.9]時，AC的大致趨勢是隨著θ值的增大而減??；因此，θ的最佳取值為0.2。由于GNMF、CNMFS目標函數(shù)中不包含融合系數(shù)θ,所以準確率不會受到θ的影響，但是GNMF、CNMFS的準確率會受到類別數(shù)k的影響，大致趨勢是隨著類別數(shù)k的增加呈下降趨勢，盡管有時會因?qū)嶒灜h(huán)境等因素出現(xiàn)一定的波動，即圖1中的趨勢與GNMF、CNMFS等并不是一致的。

圖1 θ值對準確率的影響曲線

此處之所以沒有給出融合系數(shù)在COIL20數(shù)據(jù)集上對準確率的影響曲線圖，是因為在該數(shù)據(jù)集上θ對不同類別數(shù)k的準確率影響不大，所以COIL20數(shù)據(jù)集與Yale-32數(shù)據(jù)集的θ值取值相同。

同樣地，稀疏系數(shù)β和正則化參數(shù)λ也是由實驗結(jié)果確定的。在實驗中，如果β值過大則會使得圖像過于稀疏以至于不能很好地表示圖像。經(jīng)過不斷的實驗，選取β=0.3。通過對實驗結(jié)果的分析可知，當λ從10到1 000變化時，MCNMFFF算法對AC和歸一化互信息(Normalized Mutual Information, NMI)的影響不太大。所以，根據(jù)實驗的經(jīng)驗選取λ=100。在本文實驗中，將選取每類樣本中的前20%作為標記樣本，剩余的作為未標記樣本，并從其中隨機地選擇k類樣本進行聚類實驗，每個k值運行20次取平均值作為最后的結(jié)果。由于各參數(shù)的選取對目標函數(shù)的收斂速度并沒有明顯的影響，基本上在迭代50次以內(nèi)就已經(jīng)收斂得非常好了，所以考慮到程序的運行時間，設置最大迭代次數(shù)為200。

3.2 實驗與分析

實驗中用準確率(AC)[16]和歸一化互信息(NMI)[17]兩個評價指標來驗證MCNMFFF在Yale-32和COIL20兩個數(shù)據(jù)集上的聚類性能。所以，需要在矩陣分解和特征融合后對低維數(shù)據(jù)進行聚類，然后根據(jù)聚類結(jié)果來分析數(shù)據(jù)的表示性能。

為了證明MCNMFFF算法的有效性，將NMF算法、GNMF算法、CNMFS算法和GCNMFS算法作為聚類實驗的對比對象。為了使實驗結(jié)果具有說服性，對每個k值均運行20次，取平均數(shù)作為最后的實驗結(jié)果。表1～2列出了各算法在兩個數(shù)據(jù)集上的聚類準確率；表3～4列出了聚類的歸一化互信息值。

圖2 各算法在兩個數(shù)據(jù)集上的聚類準確率曲線

圖3 各算法在兩個數(shù)據(jù)集上的歸一化互信息曲線

由表1～2可知，在兩個數(shù)據(jù)集上，MCNMFFF算法的聚類準確率平均值相對于其他對比算法的聚類準確率平均值均有了較大的改善。在Yale-32數(shù)據(jù)集上，MCNMFFF算法比NMF算法的聚類準確率平均提高了9.69個百分點，比GNMF算法平均提高了4.97個百分點，比CNMFS算法平均提高了3.24個百分點，比GCNMFS算法平均提高了1.68個百分點。在COIL20數(shù)據(jù)集上，MCNMFFF算法比NMF算法的聚類準確率平均提高了8.6個百分點，比GNMF算法平均提高了4.81個百分點，比CNMFS算法平均提高了4.32個百分點，比GCNMFS算法平均提高了2.51個百分點。

表1 不同算法在Yale-32數(shù)據(jù)集上聚類的準確率

表2 不同算法在COIL20數(shù)據(jù)集上聚類的準確率

同樣，由表3～4可看出，在兩個數(shù)據(jù)集上，MCNMFFF算法、GCNMFS算法、CNMFS算法和GNMF算法的歸一化互信息平均值均比NMF算法平均值高得多。在Yale-32數(shù)據(jù)集上，MCNMFFF算法比NMF算法的聚類準確率平均提高了15.76個百分點，比GNMF算法平均提高了9.72個百分點，比CNMFS算法平均提高了5.81個百分點，比GCNMFS算法平均提高了2.56個百分點。在COIL20數(shù)據(jù)集上，MCNMFFF算法比NMF算法的聚類準確率平均提高了14.6個百分點，比GNMF算法平均提高了10.22個百分點，比CNMFS算法平均提高了6.34個百分點，比GCNMFS算法平均提高了3.6個百分點。

為了能夠更加直觀地展示MCNMFFF算法的聚類效果，根據(jù)實驗數(shù)據(jù)分別給出了聚類準確率和歸一化互信息的對比曲線，如圖2～3所示。從中不難看出：1)MCNMFFF算法要比其他對比算法的聚類準確率和歸一化互信息值要高得多，盡管有時候會因外部等因素使結(jié)果有一定的波動；2)由于MCNMFFF算法中結(jié)合了特征融合的思想，所以相對于GCNMFS等算法在聚類結(jié)果上有一定的提升，從而進一步說明特征融合技術可以進一步提升學習質(zhì)量；3)NMF和GNMF屬于無監(jiān)督方法，CNMFS、GCNMFS和MCNMFFF屬于半監(jiān)督方法，這三種方法的聚類準確率和歸一化互信息值較其他兩種方法更高，說明監(jiān)督方法要比無監(jiān)督方法的聚類性能更好；4)由于CNMFS、GCNMFS和MCNMFFF三種方法均添加了稀疏約束，使得三種算法能夠得到更好的基于部分的表示，從而得到了比NMF和GNMF算法更好的聚類效果。

表3 不同算法在Yale-32數(shù)據(jù)集上歸一化互信息

表4 不同算法在COIL20數(shù)據(jù)集上歸一化互信息

3.3 復雜度分析

根據(jù)MCNMFFF算法的迭代更新式(11)、(14)、(17)和(20)可以計算出每一次迭代更新的計算復雜度。考慮到在實際應用中m和n會遠遠大于k,因此，迭代更新式(11)、(14)的主要計算復雜度大約為O(mnk)；經(jīng)過類似的分析，迭代更新式(17)、(20)的主要計算復雜度大約也為O(mnk)。由于MCNMFFF算法引入了融合系數(shù)θ,完成一次所有向量的更新計算復雜度大約為O(mnk),而乘性算法完成一次迭代的計算復雜度大約也為O(mnk)?？梢?，本文提出的MCNMFFF算法在每次更新中，具有與現(xiàn)有算法類似的計算復雜度O(mnk)。

表5為本文提出的MCNMFFF算法以及其他四種對比算法對每個k值均運行20次，取平均數(shù)作為最后的平均運行時間的數(shù)據(jù)對比。

表5 各算法在兩個數(shù)據(jù)集上的平均運行時間 s

由表5可知，從時間復雜度上來分析，改進NMF算法的時間主要用在矩陣分解的迭加上，其他步驟的時間復雜度不會超過NMF算法的時間復雜度。因為各種約束的引入，使得本文提出的MCNMFFF算法的運行時間要明顯少于NMF、GNMF和CNMFS算法的運行時間;但由于MCNMFFF是將GNMF和CNMFS模型分解后的具有不同稀疏度的圖像特征進行融合，導致其運行時間略長于GCNMFS算法。因為各種約束以及信息融合技術的引入使得MCNMFFF算法在提高部件學習能力的同時還解決了單一種類特征不能夠很好地描述圖像語義內(nèi)容的問題，所以其聚類準確率和歸一化互信息依然是幾種算法中最高的。因此，綜合考慮，本文提出的MCNMFFF算法取得了較好的聚類效果。

3.4 稀疏度度量

在本節(jié)實驗中，Yale-32和COIL20數(shù)據(jù)集的特征維數(shù)分別取36和20。在兩個數(shù)據(jù)集上分別利用GNMF、CNMFS、GCNMFS和MCNMFFF對原始非負矩陣X進行矩陣分解可以得到基圖像，用文獻[18]中的稀疏度度量函數(shù)來計算其稀疏度。兩個數(shù)據(jù)集的部分基圖像示例如圖4～5所示。

圖4 不同算法在Yale-32數(shù)據(jù)集的基圖像

圖5 不同算法在COIL20數(shù)據(jù)集的基圖像

通過在Yale-32和COIL20這兩個數(shù)據(jù)集上對比幾種算法基圖像的稀疏度可以看出，GNMF算法的稀疏度較差，CNMFS算法的稀疏度一般，而GCNMFS算法的稀疏度略好，MCNMFFF算法的稀疏度最好。由此，表明MCNMFFF算法能夠得到圖像的最佳局部表示。

4 結(jié)語

本文提出了基于特征融合的多約束非負矩陣分解算法，并給出了相應的迭代更新規(guī)則和收斂性證明。在Yale-32和COIL20兩個數(shù)據(jù)集上對本文算法進行了聚類實驗，用聚類準確率和歸一化互信息兩個評價指標來衡量該算法的聚類性能。從實驗結(jié)果可以看出，MCNMFFF算法明顯優(yōu)于其他幾種對比算法，足以說明MCNMFFF算法的有效性。最后，考察了MCNMFFF算法的稀疏性，結(jié)果顯示該算法的稀疏度值最高。因此可以得出結(jié)論：相對于NMF、GNMF、CNMFS和GCNMFS四種對比算法，MCNMFFF算法能夠更好地得到圖像的局部表示，使基圖像的判別能力更強。但本文算法中的融合系數(shù)θ需要通過不斷地搜索得到最優(yōu)值，因此如何有效地選擇融合系數(shù)θ是以后研究的重點之一。

References)

[1] 甘俊英, 何國輝, 何思斌.核零空間線性鑒別分析及其在人臉識別中的應用[J]. 計算機學報, 2014, 37(11): 2374-2379. (GAN J Y, HE G H, HE S B. Kernel null space linear discriminant analysis and its applications in face recognition [J]. Chinese Journal of Computers, 2014, 37(11): 2374-2379.)

[2] 史衛(wèi)亞, 郭躍飛, 薛向陽.一種解決大規(guī)模數(shù)據(jù)集問題的核主成分分析算法[J]. 軟件學報, 2009, 20(8): 2153-2159. (SHI W Y, GUO Y F, XUE X Y. Efficient kernel principal component analysis algorithm for large-scale data set [J]. Journal of Software, 2009, 20(8): 2153-2159.)

[3] 尹洪濤, 付平, 沙學軍.基于DCT和線性判別分析的人臉識別[J]. 電子學報, 2009, 37(10): 2211-2214. (YIN H T, FU P, SHA X J. Face recognition based on DCT and LDA [J]. Acta Electronica Sinica, 2009, 37(10): 2211-2214.)

[4] KOIDOVSKY Z, TICHAVSKY P, OJA E. Efficient variant of algorithm FastICA for independent component analysis attaining the Cramér-Rao lower bound [J]. IEEE Transactions on Neural Networks, 2006, 17(5): 1265-1277.

[5] WEI J-J, CHANG C-J, CHOU N-K, et al. ECG data compression using truncated singular value decomposition [J]. IEEE Transactions on Information Technology in Biomedicine, 2001, 5(4): 290-299.

[6] PAATERO P, TAPPER U. Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values [J]. Environmetrices, 1994, 5(2): 111-126.

[7] CAI D, HE X, HAN J, et al. Graph regularized non-negative matrix factorization for data representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1548-1560.

[8] 李樂, 章毓晉.非負矩陣分解算法綜述[J]. 電子學報, 2008, 36(4): 737-743. (LI L, ZHANG Y J. A survey on algorithms of nonnegative matrix factorization [J]. Acta Electronica Sinica, 2008, 36(4): 737-743.)

[9] LIU H, WU Z, LI X, et al. Constrained non-negative matrix factorization for image representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1299-1311.

[10] 胡學考, 孫福明, 李豪杰.基于稀疏約束的半監(jiān)督非負矩陣分解算法[J]. 計算機科學, 2015, 42(7): 280-284. (HU X K, SUN F M, LI H J. Constrained non-negative matrix factorization with sparseness [J]. Computer Science, 2015, 42(7): 280-2284.)

[11] 姜小燕, 孫福明, 李豪杰.基于圖正則化和稀疏約束的半監(jiān)督非負矩陣分解[J]. 計算機科學, 2016, 43(7): 77-82, 105. (JIANG X Y, SUN F M, LI H J. Semi-Supervised non-negative matrix factorization based on graph regularization and sparseness constraints [J]. Computer Science, 2016, 43(7): 77-82, 105.)

[12] 李振華, 鄭琳川.全局和局部特征相融合的人臉識別算法[J]. 計算機工程與應用, 2015, 51(14): 131-135. (LI Z H, ZHENG L C. Image recognition algorithm based on global and local features exaction [J]. Computer Engineering and Applications, 2015, 51(14): 131-135.)

[13] 梅蓉.基于特征融合的人臉圖像識別方法研究[J]. 河南科技學院學報(自然科學版), 2014(4): 70-74. (MEI R. Study of face recognition method based on feature fusion [J]. Journal of Henan Institute of Science and Technology (Natural Sciences Edition), 2014(4): 70-74.)

[14] 蘭佩, 方超.基于全局與局部特征融合的人臉識別方法[J]. 計算機與現(xiàn)代化, 2014(3): 109-113. (LAN P, FANG C. Face recognition method based on global and local features fusion [J]. Computer and Modernization, 2014(3): 109-113.)

[15] RODRIGUEZ J D, PEREZ A, LOZANO J A. Sensitivity analysis ofk-fold cross validation in prediction error estimation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(3): 569-575.

[16] DING C, LI T, PENG W, et al. Orthogonal nonnegative matrix tri-factorizations for clustering [C]// KDD 2006: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2006: 126-135.

[17] CHENG Q, LI S Z, ZHANG H, et al. Learning spatially localized, parts-based representation [C]// CVPR 2001: Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2001: 207-212.

[18] BERRY M W, PULATOVA S A, STEWART G W. Algorithm 844: computing sparse reduced-rank approximations to sparse matrices [J]. ACM Transactions on Mathematical Software, 2004, 31(2): 252-269.

Multi-constraintnonnegativematrixfactorizationalgorithmbasedonfeaturefusion

SUN Jing*, CAI Xibiao, SUN Fuming

(SchoolofElectronicsandInformationEngineering,LiaoningUniversityofTechnology,JinzhouLiaoning121001,China)

Focusing on the issues that the sparseness of data is reduced after factorization and the single image feature cannot describe the image content well, a multi-constraint nonnegative matrix factorization based on feature fusion was proposed. The information provided by few known labeled samples and sparseness constraint were considered, and the graph regularization was processed, then the decomposed image features with different sparseness were fused, which improved the clustering performance and effectiveness. Extensive experiments were conducted on both Yale-32 and COIL20 datasets, and the comparisons with four state-of-the-art algorithms demonstrate that the proposed method has superiority in both clustering accuracy and sparseness.

Non-negative Matrix Factorization (NMF); label information; sparseness constraint; graph regularization; feature fusion

2017- 02- 24;

2017- 04- 19。

國家自然科學基金資助項目(61572214);遼寧省高等學校優(yōu)秀人才支持計劃項目(LR2015030)。

孫靜(1992-),女,遼寧阜新人,碩士研究生,主要研究方向：圖像語義理解; 蔡希彪(1972-),男,遼寧盤錦人,副教授,博士,主要研究方向：圖像語義理解、移動通信; 孫福明(1972-),男,遼寧大連人,教授,博士,CCF會員,主要研究方向：圖像語義理解、機器學習。

時間 2017- 09- 05 13:08:27。 網(wǎng)絡出版地址 http://kns.cnki.net/kcms/detail/51.1307.TP.20170905.1308.002.html。

1001- 9081(2017)10- 2834- 07

10.11772/j.issn.1001- 9081.2017.10.2834

TP181

A

This work is partially supported by the National Natural Science Foundation of China (61572214), the Program for Liaoning Excelent Talents in University (LR2015030).

SUNJing, born in 1992, M. S. candidate. Her research interests include image semantic understanding.

CAIXibiao, born in 1972, Ph. D., associate professor. His research interests include image semantic understanding, mobile communication.

SUNFuming, born in 1972, Ph. D., professor. His research interests include image semantic understanding, machine learning.