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

孫 靜，蔡希彪，孫福明

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

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

孫 靜*，蔡希彪，孫福明

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

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

非負(fù)矩陣分解；標(biāo)簽信息；稀疏約束；圖正則；特征融合

0 引言

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

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

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

1 非負(fù)矩陣分解

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

(1)

s.t.U≥0,V≥0

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

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

(2)

(3)

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

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

2.1 相關(guān)算法

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

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

(4)

s.t.U≥0,V≥0

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

(5)

s.t.U≥0,Z≥0

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

(6)

s.t.U≥0,Z≥0

2.2 MCNMFF目標(biāo)函數(shù)

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

(7)

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

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

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

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

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

通過(guò)代數(shù)運(yùn)算，目標(biāo)函數(shù)(7)可以重寫(xiě)為：

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)對(duì)變量U1求偏導(dǎo)數(shù)，同時(shí)令偏導(dǎo)數(shù)為零，可得：

(9)

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

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

(10)

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

(11)

2)更新變量Z。

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

(12)

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

(13)

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

(14)

3)更新變量U2。

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

(15)

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

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

(16)

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

(17)

4)更新變量V。

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

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

(18)

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

(19)

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

(20)

2.4 MCNMFFF收斂性證明

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

定理1 對(duì)于U1≥0、Z≥0、U2≥0和V≥0,目標(biāo)函數(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)

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

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

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

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

F(u1)≤F(u0)

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

證畢。

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

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

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

(22)

FZij(zij)的泰勒級(jí)數(shù)展開(kāi)式如下：

(23)

(24)

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

(25)

證畢。

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

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

因?yàn)槭?22)是函數(shù)的輔助函數(shù)，因此，采用當(dāng)前規(guī)則更新是非遞增的。同時(shí)，目標(biāo)函數(shù)(7)具有下界。綜上所述，定理1的收斂性獲證。

證畢。

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

3 實(shí)驗(yàn)與分析

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

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

MCNMFFF模型有三個(gè)關(guān)鍵的參數(shù)：融合系數(shù)θ、稀疏系數(shù)β和正則化參數(shù)λ。目標(biāo)函數(shù)中的融合系數(shù)θ通常是由實(shí)驗(yàn)的結(jié)果來(lái)決定的，一般說(shuō)來(lái)，不同數(shù)據(jù)集對(duì)應(yīng)的最佳融合系數(shù)值也不同。圖1給出了Yale-32數(shù)據(jù)集在取不同k值的情況下不同θ值對(duì)應(yīng)的準(zhǔn)確率。

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

圖1 θ值對(duì)準(zhǔn)確率的影響曲線

此處之所以沒(méi)有給出融合系數(shù)在COIL20數(shù)據(jù)集上對(duì)準(zhǔn)確率的影響曲線圖，是因?yàn)樵谠摂?shù)據(jù)集上θ對(duì)不同類別數(shù)k的準(zhǔn)確率影響不大，所以COIL20數(shù)據(jù)集與Yale-32數(shù)據(jù)集的θ值取值相同。

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

3.2 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

3.3 復(fù)雜度分析

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

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

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

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

3.4 稀疏度度量

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

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

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

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

4 結(jié)語(yǔ)

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

References)

[1] 甘俊英, 何國(guó)輝, 何思斌.核零空間線性鑒別分析及其在人臉識(shí)別中的應(yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào), 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)亞, 郭躍飛, 薛向陽(yáng).一種解決大規(guī)模數(shù)據(jù)集問(wèn)題的核主成分分析算法[J]. 軟件學(xué)報(bào), 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] 尹洪濤, 付平, 沙學(xué)軍.基于DCT和線性判別分析的人臉識(shí)別[J]. 電子學(xué)報(bào), 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] 李樂(lè), 章毓晉.非負(fù)矩陣分解算法綜述[J]. 電子學(xué)報(bào), 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] 胡學(xué)考, 孫福明, 李豪杰.基于稀疏約束的半監(jiān)督非負(fù)矩陣分解算法[J]. 計(jì)算機(jī)科學(xué), 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)督非負(fù)矩陣分解[J]. 計(jì)算機(jī)科學(xué), 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] 李振華, 鄭琳川.全局和局部特征相融合的人臉識(shí)別算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 梅蓉.基于特征融合的人臉圖像識(shí)別方法研究[J]. 河南科技學(xué)院學(xué)報(bào)(自然科學(xué)版), 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] 蘭佩, 方超.基于全局與局部特征融合的人臉識(shí)別方法[J]. 計(jì)算機(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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61572214);遼寧省高等學(xué)校優(yōu)秀人才支持計(jì)劃項(xiàng)目(LR2015030)。

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

時(shí)間 2017- 09- 05 13:08:27。 網(wǎng)絡(luò)出版地址 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.