一種稀疏圖正則化的非負低秩矩陣分解算法

劉國慶，盧桂馥，張 強

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

0 引 言

聚類在特征學習和計算機視覺中是一項非常具有挑戰(zhàn)的任務，許多聚類方法[1-3]被提出并在很多領域得到了成功應用，如圖像分類[4]，圖像檢索[5]，圖像分割[6]，圖像索引[7]，圖像聚類[8]等。然而對于圖像聚類任務，一個非常重要的步驟是找到原始數(shù)據(jù)的有效低維表示。為此，很多研究者做了大量的工作來挖掘原始數(shù)據(jù)內在結構中的有用信息，使新的數(shù)據(jù)表示具有更好的識別能力[9-12]。矩陣分解是一類被廣泛使用的數(shù)據(jù)表示技術，有奇異值分解(singular value decomposition，SVD)[13]、矢量量化(vector quantization，VQ)[14]和非負矩陣分解算法(non-negative matrix factorization，NMF)[15]等，NMF也是一種有效的圖像表示工具[16]。1999年Lee和Seung在《Nature》雜志上提出NMF方法，以用人臉識別中的基于局部特征提取，該方法使得分解之后的矩陣中的所有元素都是非負的。NMF在心理學和生理學上的構造依據(jù)是其對整體的感知是由組成整體的部分感知所構成的，這恰恰也符合人類大腦對事物的直觀理解。NMF在模式識別、信息恢復、神經網絡、語音識別等很多領域已被廣泛應用，且取得了很好的應用效果。

自NMF被提出以來，便得到學者的廣泛關注和重視，并對其進行了深入的研究。為了提高NMF算法的識別率和有效性，人們在NMF算法的基礎上提出了許多改進的NMF算法。Cai等[17]在標準NMF的基礎上提出了圖正則非負矩陣分解算法(graph regularized non-negative matrix factorization for data representation，GNMF)，該算法針對流形數(shù)據(jù)，在矩陣分解過程中考慮了數(shù)據(jù)所攜帶的幾何信息。Hoyer[18]把稀疏編碼和標準NMF算法結合，提出非負稀疏編碼算法(non-negative sparse coding，NSC)，NSC算法使得矩陣分解后系數(shù)矩陣的稀疏性較好，這樣可以用更少的有用信息來表達原有信息，在一定程度上提高了運算的效率。Li等[19]在標準的NMF目標函數(shù)中引入了局部化約束，提出了局部非負矩陣分解(local non-negative matrix factorization，LNMF)。Serhat等[20]提出了一種增量式非負矩陣分解算法(incremental non-negative matrix factorization，INMF)，它避免了新訓練樣本加入后對基矩陣和系數(shù)矩陣的重新計算，從而節(jié)省了大量的運算時間。一般給定圖像數(shù)據(jù)的有用信息常常是嵌入在高維歐式空間中的非線性低維流形上[21]。為了能夠獲得更加有效的低維數(shù)據(jù)表示，Li等[22]提出了圖正則化非負低秩矩陣分解算法(graph regularized non-negative low-rank matrix factorization，GNLMF)。

研究表明，一方面，給定圖像的有效信息常隱藏在數(shù)據(jù)的低秩結構中，數(shù)據(jù)通常是從嵌入在高維中的低維流形上進行采樣的；另一方面，對數(shù)據(jù)加以稀疏約束可以在一定程度上提高相應算法抗噪聲干擾的能力和魯棒性。為了改善NMF算法的魯棒性和可解釋性，本文將原始數(shù)據(jù)的有效低秩結構和數(shù)據(jù)的幾何信息引入到NMF中，同時又對基矩陣加以稀疏約束，提出了一種稀疏圖正則化非負低秩矩陣分解算法(sparse graph regularized non-negative low-rank matrix factorization，SGNLMF)，通過在ORL和YaleB人臉數(shù)據(jù)庫上進行實驗，驗證了本文所提出的SGNLMF算法比現(xiàn)有的其他算法優(yōu)異。

1 相關的工作

1.1 非負矩陣分解

目前矩陣分解技術主要有主成分分析、獨立成分分析、奇異值分解等方法，這些方法雖然在分解時附加的限制條件不同，但它們都將原始數(shù)據(jù)矩陣表示為幾個矩陣乘積的形式，這在數(shù)學上是對的，但在實際應用中往往缺乏直觀的物理意義。NMF是一種被廣泛應用的矩陣因式分解方法，也是一種有效的圖像表示工具，它使得分解后的所有分量均是非負的，此方法使得矩陣元素具有實際的物理意義，為矩陣分解問題提供了一種新的思路。給定一個圖像數(shù)據(jù)的非負矩陣X=[x1,x2,x3,…,xn]∈Rm×n+，它試圖找到2個非負矩陣W=[w1,w2,w3,…,wl]∈Rm×l+和H=[h1,h2,h3,…,hn]∈Rl×n+，使其乘積最佳逼近原始矩陣X，即X≈WH，NMF的目標函數(shù)為

s.t.W≥0,H≥0

(1)

(1)式中，‖·‖2F表示矩陣的Frobenius范數(shù)，矩陣W可以看作是對原始矩陣X進行逼近的一組基，而矩陣H是樣本集X在基矩陣W上的非負投影系數(shù)矩陣，系數(shù)矩陣是原始矩陣降維后的結果。

Lee和Seung在文獻[16]中給出的乘性迭代規(guī)則為

(2)

(3)

1.2 圖正則非負矩陣分解

在現(xiàn)實世界中，許多數(shù)據(jù)是嵌入在高維歐式空間中非線性低維流行上的，然而，NMF算法和許多改進的NMF算法在對原始數(shù)據(jù)處理時，沒有考慮數(shù)據(jù)的內蘊幾何結構。為了能夠發(fā)現(xiàn)數(shù)據(jù)隱藏信息的表示方法，同時又考慮數(shù)據(jù)內在的幾何信息，Cai等[17]通過將圖正則化項融入到標準的NMF框架中，提出了圖正則非負矩陣分解算法。該算法假設2個數(shù)據(jù)點在原始數(shù)據(jù)空間中的幾何距離如果是鄰近的話，則其在基于新的基向量低維表示中相對應的數(shù)據(jù)點也應該離得很近。與傳統(tǒng)的降維算法相比，流形學習算法能夠揭示原始數(shù)據(jù)內在的幾何結構，尋找高維數(shù)據(jù)在低維空間中的緊致嵌入。GNMF的目標函數(shù)為

s.t.W≥0,H≥0

(4)

(4)式中：tr(HLapHT)是圖正則項；Lap是圖拉普拉斯矩陣，圖正則化參數(shù)λ>0。

Cai等在文獻[17]中給出了如下的迭代規(guī)則

(5)

(6)

(5)—(6)式中，Dap是對角矩陣，Lap=Dap-Wap。

1.3 圖正則非負低秩矩陣分解

大多數(shù)現(xiàn)有的對NMF改進的方法直接將NMF方法應用于高維圖像數(shù)據(jù)集上，來計算原始圖像的低維表示。然而，事實上，給定原始圖像數(shù)據(jù)的有用信息常常是嵌入在高維歐式空間中的非線性低維流形上的。為了能夠挖掘數(shù)據(jù)圖像中的有效低秩結構部分，Li等[22]提出非負低秩矩陣分解算法(non-negative low-rank matrix factorization，NLMF)，并進一步構造出圖正則非負低秩矩陣分解算法(GNLMF)。與傳統(tǒng)算法相比，該算法將流形結構信息結合到非負低秩矩陣分解的目標函數(shù)中，使得其識別率和魯棒性都有一定的提高。GNLMF算法的目標函數(shù)為

minL,S‖X-L-S‖2F+αtr(HLapHT)+βtr(WWT)

s.t.L,W,H≥0

(7)

(7)式中，α，β是圖正則化參數(shù)。

Li等在文獻[22]中給出的迭代更新公式為

(8)

(9)

2 稀疏圖正則非負低秩矩陣分解

近年來，稀疏優(yōu)化在圖像處理，信息恢復，模式識別等領域都得到了成功的應用。被很多科研人員所重視，研究表明，對數(shù)據(jù)加以稀疏約束可以在一定程度上提高相應算法的抗噪聲干擾能力和魯棒性。為了提高NMF算法的魯棒性和可解釋性，本文提出一種稀疏圖正則化的非負低秩矩陣分解算法(SGNLMF)，該算法不僅考慮了原始數(shù)據(jù)的有效低秩結構和幾何信息，還對基矩陣加以稀疏約束。

2.1 SGNLMF的算法模型

一般來說，給定圖像的有用信息常常隱藏在它們的低秩結構中，為了挖掘原始數(shù)據(jù)的有效低秩結構部分，X可以近似表示為L+S的和。其中，L表示原始數(shù)據(jù)X的低秩部分，S表示稀疏噪聲部分，求出低秩部分L之后再對其進行NMF操作，來獲得原始數(shù)據(jù)圖像的低維表示。

minL,S‖X-L-S‖2F

s.t.L=WH，L,W,H≥0

rank(L)≤r，card(S)≤s

(10)

(10)式中：W是基矩陣；H是系數(shù)矩陣；r表示矩陣L秩的范圍集；s表示矩陣S的稀疏范圍集；rank(L)表示矩陣L的秩；card(S)表示矩陣S的非零元素個數(shù)。

為了確?；仃嘩的的光滑性，對基矩陣W進行Tikhonov正則化處理

(11)

(11)式中，tr(·)表示矩陣的跡，結合(10)式和(11)式，可以得到

minL,S‖X-L-S‖2F+βtr(WWT)

(12)

(12)式中，β是Tikhonov正則化參數(shù)。

結合數(shù)據(jù)的幾何結構信息，對(12)式引入圖正則化項tr(HLapH)，則有

minL,S‖X-L-S‖2F+αtr(HLapHT)+βtr(WWT)

(13)

(13)式中：α是圖正則化參數(shù)；Lap=Dap-Wap是圖拉普拉斯矩陣；Wap是對稱權重矩陣；Dap為一個對角矩陣。

稀疏性和低秩性對于數(shù)據(jù)的表示和分析具有非常重要的意義，將稀疏編碼理論和GNLMF算法結合為稀疏圖正則化非負低秩矩陣分解算法，該算法可以在給定基向量集的基礎上，產生對高維數(shù)據(jù)的低維近似表示。對于約束項的選擇，是約束W的稀疏度，還是約束H的稀疏度，或者是約束兩者的稀疏度，取決于具體的應用，由于基矩陣W包含原始數(shù)據(jù)的特征信息，對W作稀疏約束可以提高基矩陣存儲和計算的便利性。為了提高NMF算法的準確率和魯棒性，本文對基矩陣W加以稀疏約束，將稀疏約束項融入到(13)式中，可以得到SGNLMF算法的最小化目標函數(shù)

minL,S‖X-L-S‖2F+αtr(HLapHT)+

βtr(WWT)+γ‖W‖1

s.t.L=WH，L,W,H≥0

rank(L)≤r，card(S)≤s

(14)

(14)式中：γ為基矩陣W的稀疏約束參數(shù)；‖·‖1表示L1范數(shù)。

2.2 SGNLMF的求解算法

考慮到(14)式關于W和H是非凸的，本文采用交替迭代方法來學習圖像數(shù)據(jù)X低秩結構的低維表示，SGNLMF算法可以通過求解下面的2個子問題來解決：①低秩矩陣的恢復；②NMF的相關子問題。詳細過程如下。

1)低秩矩陣的恢復。低秩恢復子問題的目標函數(shù)為

minL,S‖X-L-S‖2F

s.t. rank(L)≤r

card(S)≤s

(15)

(15)式中：r是低秩結構L的秩；s表示矩陣S的稀疏范圍集。雖然(15)式對于L和S是非凸的，但是，如果L或S中的一個被固定，則下面的子問題是凸的。

(16)

因此，(16)式中的2個子問題可以通過固定其中的一個更新另一個來解決，直到收斂為止。實際上，在每一次的迭代中，對X-St-1進行奇異值分解是比較耗時的，本文使用了雙邊隨機投影(Bilateral Random Projection，BRP)[23]來求解(15)式。對于給定的矩陣X∈Rm×n，Y1，Y2表示為

Y1=XA1

(17)

Y2=XTA2

(18)

(17)—(18)式中：A1∈Rn×r；A2∈Rm×r都是隨機矩陣，則L為

L=Y1(AT2Y1)-1AT2

(19)

(20)

(21)

(22)

通過對Y1和Y2進行QR分解，則L表示為

(23)

在計算出L之后，再對L進行NMF分解以獲得圖像數(shù)據(jù)集的低維表示。

2)NMF的相關子問題。圖正則化非負低秩矩陣分解，Tikhonov正則化和稀疏約束子問題的目標函數(shù)為

minW,H≥0‖L-WH‖2F+αtr(HLapHT)+

βtr(WWT)+γ‖W‖1

(24)

針對稀疏約束子問題，需要進行相應的稀疏優(yōu)化：對于一個給定的線性系統(tǒng)如：Ax=b，A∈Rm×n，我們知道，當矩陣A中有m

根據(jù)上述的稀疏優(yōu)化相關模型，當想要得出模型的解能夠呈現(xiàn)出稀疏的性質時，簡單的方法就是在目標函數(shù)中直接添加一個稀疏懲罰項，本文中這個懲罰項加在基矩陣W上，為了保持模型的凸性，采用L1范數(shù)進行懲罰。則(24)式的表達式可以重寫為

F(W,H)=tr((L-WH)(L-WH)T)+

αtr(HLapHT)+βtr(WWT)+γ‖W‖1=

tr(LLT-2WHLT+WHHTWT)+αtr(HLapHT)+

βtr(WWT)+γ‖W‖1

(25)

Q=tr(LLT-2WHLT+WHHTWT)+

αtr(HLapHT)+βtr(WWT)+tr(ΨWT)+

tr(ΦHT)+γ‖W‖1

(26)

函數(shù)Q對W，H求得偏導的結果如下

(27)

(28)

根據(jù)KKT條件，滿足ψilwil=0，φljhlj=0，則可以得到關于wil和hlj的方程如下

-(LHT)ilwil+(WHHT)ilwil+(βW)ilwil+

(29)

(WTWH)ljhlj+(αHDap)ljhlj=

(WTL)ljhlj+(αHWap)ljhlj

(30)

由(29)式和(30)式可以得到wil和hlj的更新規(guī)則如下

(31)

(32)

2.3 與梯度下降法之間的聯(lián)系

問題(24)可以通過梯度下降法來解決[25]，相應的更新規(guī)則如下

(33)

(33)式中，ηil，δlj為迭代步長參數(shù)。

為了方便，令δlj=-hlj/2(WTWH+αHDap)lj，則

(-2WTL+2WTWH+2αHLap)lj=

(34)

同理，令ηil=-wil/2(WHHT+βW+γI/2)il，則有

(-2LHT+2WHHT+2βW+γI)il=

(35)

從上述過程可以看出(31)式和(32)式是梯度下降算法的一個特例，在這些更新規(guī)則下可以得出(24)式是非增的，同時可以確保矩陣W和H的非負性。

2.4 收斂性分析

定義1 設G(w,w′)是F(w)的輔助函數(shù)，滿足條件：G(w,w′)≥F(h)，G(w,w)=F(w)。

引理1 如果G(w,wt)是F(w)的輔助函數(shù)，則F(w)在下面迭代更新規(guī)則下是非增的

wt+1=argminwG(w,wt)

證明：由上述可以得出結論：當w=wt+1時函數(shù)G(w,wt)取最小值，根據(jù)定義1，G(wt+1,wt)大于等于F(wt+1)，可以用不等式表示為

可以注意到，F(xiàn)(wt+1)=F(wt)只有當wt為G(w,wt)的局部極小點時才成立。如果函數(shù)F的導數(shù)存在且在wt的一個極小領域內連續(xù)，則微分F(wt)=0。通過引理1可以得到一列收斂到局部極小點wmin=argminwF(w)的序列

F(wmin)≤…≤F(wt+1)≤

F(wt)≤…≤F(w1)≤F(w0)

可以看到，通過定義輔助函數(shù)G(w,wt)，對于目標函數(shù)(24)式，其相應的迭代規(guī)則可以滿足wt+1=argminwG(w,wt)。

2.5 稀疏圖正則非負低秩矩陣分解算法步驟

輸入：數(shù)據(jù)矩陣X∈Rm×n+，參數(shù)p,α,β,γ。

輸出：最優(yōu)稀疏基矩陣W和數(shù)據(jù)的低維表示矩陣H。

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

2)對Y1和Y2進行QR分解，計算出矩陣X的低秩結構L；

3)對矩陣L進行NMF分解；

4)計算

5)求得最優(yōu)稀疏基矩陣W和數(shù)據(jù)的低維表示矩陣H。

3 實驗與結果分析

3.1實驗使用的數(shù)據(jù)庫

為了對本文所提出的稀疏圖正則非負低秩矩陣分解算法的有效性進行評估，分別在ORL和YaleB 2個人臉數(shù)據(jù)庫上進行實驗。

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

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

3.2 算法比較

為了驗證SGNLMF算法的優(yōu)越性，將它與K-means，PCA，NMF，GNMF，GNLMF等算法進行了比較，詳細算法如下。

1)K-means:在原始數(shù)據(jù)集上進行，而不使用樣本中包含的任何信息；

2)PCA:能夠有效地提取原始數(shù)據(jù)集中的主要成分；

3)NMF:試圖找出2個非負低維矩陣，其乘積近似為原始矩陣；

4)GNMF:試圖通過構造一個簡單的圖來包含數(shù)據(jù)中的內在幾何結構信息。最近鄰數(shù)p設置5，圖正則化參數(shù)設置為100；

5)GNLMF:最近鄰數(shù)設置為5，圖正則化參數(shù)設置100，Tikhonov正則化參數(shù)也設置為0.000 1。

6)SGNLMF:考慮原始數(shù)據(jù)的低秩結構和幾何信息，并對基矩陣加以稀疏約束，最近鄰數(shù)設置為5，圖正則化參數(shù)設置為100，Tikhonov正則化參數(shù)設置為0.000 1, 稀疏約束參數(shù)設置為2。

3.3 評價準則

聚類性能的評價通過原始樣本的類別信息和使用算法所得結果的對應程度進行評價，本文采用正確率(accuracy，AC)和歸一化互信息(normalized mutual information，NMI)2種常用準則來評價聚類性能。AC的定義如下

(36)

(36)式中：n為整個數(shù)據(jù)集的規(guī)模大??；gndi是數(shù)據(jù)集提供的實際標簽；如果a=b，則δ(a,b)=1，否則，δ(a,b)=0；zi是使用本文的算法所得出的樣本X的標簽；map(zi)是將本文的算法得出的標簽映射到數(shù)據(jù)集提供的實際標簽的最優(yōu)置換函數(shù)。

NMI是另一種被廣泛用于評價聚類結果的方法，NMI是C和C′相似性的度量，在這里C為由已知的類提供的真實值，C′是由本文的算法所獲得的類。互信息(mutual information，MI)可以看成是一個隨機變量中包含的關于另一個隨機變量的信息量，則C和C′的互信息可定義為

(37)

(37)式中：p(ci)和p(c′j)分別是任意選擇的樣本X屬于C和C′的概率；p(ci,c′j)是樣本X既屬于C類又屬于C′類的概率，NMI的定義為

(38)

(38)式中：H(C)是類C的熵；H(C′)是C′的熵；NMI是C和C′相似性的度量。

3.4 性能的評價和比較

通過在ORL和YaleB數(shù)據(jù)庫上進行實驗來驗證本文所提出的SGNLMF算法的優(yōu)異性。

在實驗中，當本文提出的SGNLMF算法其最近鄰數(shù)p設置為5，圖正則化參數(shù)設置為100，Tikhonov正則化參數(shù)設置為0.000 1，稀疏約束參數(shù)設置為2時，其圖像識別率和歸一化互信息比設置其他參數(shù)表現(xiàn)要好。表1～表4和圖3～圖6給出了在選取不同的類別數(shù)K時，6種算法在ORL人臉數(shù)據(jù)庫和YaleB人臉數(shù)據(jù)庫上的識別率和歸一化互信息。本文在進行實驗時，隨機選取數(shù)據(jù)樣本，并重復20次，最終實驗結果為20次實驗結果的平均值。從上述的實驗結果中我們發(fā)現(xiàn)，在類別數(shù)K取不同的數(shù)值時，本文所提出的SGNLMF算法因其考慮了原始數(shù)據(jù)的低秩結構，利用了數(shù)據(jù)內部的幾何信息，同時又對基矩陣加以稀疏約束，使得它比其他算法的聚類性能要優(yōu)異。

表1 不同算法在ORL數(shù)據(jù)庫上的聚類結果ACTab.1 Clustering results of different methods on ORL database AC %

表2 不同算法在ORL數(shù)據(jù)庫上的聚類結果NMITab.2 Clustering results of different methods on ORL database NMI %

表3 不同算法在YaleB數(shù)據(jù)庫上的聚類結果ACTab.3 Clustering results of different methods on YaleB database AC %

表4 不同算法在YaleB數(shù)據(jù)庫上的聚類結果NMITab.4 Clustering results of different methods on YaleB database NMI %

4 結束語

針對現(xiàn)有的NMF算法存在對噪聲敏感，魯棒性差等缺點，為了提高NMF算法的魯棒性和可解釋性，本文提出了SGNLMF算法，通過利用原始數(shù)據(jù)的的低秩結構，并將數(shù)據(jù)的幾何信息融入到NMF中，同時對基矩陣加以約束，使得該算法在ORL和YaleB數(shù)據(jù)庫上的實驗表現(xiàn)出較高的識別率和較好的魯棒性以及可解釋性。下一步我們將調整稀疏懲罰項，使其能夠適應更多的問題，得到更好的應用效果。