基于SVD確定NMF初始化矩陣維數

陳劍軍++劉智秉

摘要：根據奇異值分解和奇異值的屬性，提出了確定非負矩陣分解中初始矩陣維數的方法：以矩陣奇異值的平方計算各自的貢獻率，以貢獻率之和接近給定閾值來確定所需奇異值的個數，并以之為初始矩陣的維數。避免了人為嘗試維數的缺陷。給出了相應的證明并解釋了方法的合理性。比較了使用奇異值確定初始矩陣維數的不同方法，證明且驗證了在相同貢獻率的情況下所需初始矩陣維數的大小關系。

關鍵詞：非負矩陣分解；初始化矩陣維數；奇異值分解；貢獻率

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2015）24-0116-03

The Dimension of NMF Initialization Matrix Based on SVD

CHEN Jian-jun 1， LIU Zhi-bing 2

（1.Guangdong University of Science and Technology， Dongguan 523083， China；2. College of Science， Jiujiang University， Jiujiang 332000， China）

Abstract： Based on the properties of singular value decomposition and singular value， the method of determining the initial matrix dimension of non negative matrix factorization is proposed. The contribution rate of the matrix singular value is calculated. To avoid the defect of the dimension of human attempt. The rationality of the method is given. A comparison is made on the different methods of determining the initial matrix dimension using the singular values， and it is proved that the size of the initial matrix dimension is required for the same contribution rate.

Key words： non negative matrix factorization； initialization matrix dimension； singular value decomposition； contribuion rate

NMF算法是Lee D D 和Seung H S 在《Nature》提出的矩陣分解新算法[1]。該算法通過簡單迭代將非負矩陣分解為兩個低階非負矩陣之積，從而使矩陣分解具有可解釋的實際意義。因此，NMF算法迅速引起了各科研領域的重視并將其廣泛應用于圖像分析、數據挖掘、語音處理、機器人控制、生物醫學工程和化學工程等諸多領域[2-7]，[12-13]。

算法概要如下[1]（其收斂性在[1]中已證）：

給定非負矩陣[V∈Rm×n+]，隨機產生隨機矩陣[W1∈Rm×r+，H1∈Rr×n+]；[r]是根據需要選擇的正整數（本文稱之為初始矩陣的維數）。

[Hk+1=（Hk）.（W'kV）.（W'kWkHk）.]，[Wk+1=（Wk）.（VH'k+1）.（WkHk+1H'k+1）.]。 （注：帶括號的乘、除為對應元素相乘、除。）

其中：[k=1，2，...，K]。[K]為迭代次數，據目標函數或需要來確定。目標函數之一為：[V-WH22]。

作為新方法，NMF算法雖然克服了傳統的矩陣分解方法的很多缺陷，但自身也存在一些缺點，如：分解結果不唯一導致全局最小點很難找到，初始化狀態不確定，等等[6-9]。NMF算法的合理初始化問題是目前國、內外研究NMF算法改進的熱點問題之一[4]，[6]，[8-9]。初始化問題可分為兩個方面：如何選擇初始化矩陣、如何確定初始矩陣的維數，后者直接關系到存儲、計算成本。然而，關注前者的研究較多[3-4]，[8]，對于后者，目前采用的方法是以不同的維數進行嘗試，經過計算、比較結果之后再選擇合適的維數，尚無直接確定該維數的合理方法或算法[6-7]，[9]，[14]。

本文提出NMF算法中確定初始矩陣維數的方法：用奇異值的平方計算各奇異值的平方的貢獻率，當貢獻率之和接近給定的閾值時，取所需要的奇異值的個數為初始矩陣的維數。采用的方法與文獻[10]不同且解釋了方法的合理性、證明并驗證了兩種方法在相同貢獻率的情況下所得初始矩陣維數大小關系。

1 NMF中初始矩陣維數的確定

由文獻[11]不難推導出如下的結論：

引理：給定非負矩陣[V∈Rm×n+]，記其奇異值分解如下：[V=PΣ1000QT]。式中：[Σ1=diag（σ1，σ2，...，σl）]，

[P∈Rm×m]和[Q∈Rn×n]為正交矩陣。[σ1≥σ2≥...≥σl>0]為非零奇異值，[l=rank（V）≤min（m，n）]。記[V=（v（i，j））]，設其元素為[m]信道的、已經過零均值化處理的觀測數據序列；[i=1，2，...，m；][j=1，2，...，n]。則：第[k]信道的信號功率[pk=1nσ2k]，[k=1，2，...，m]。

可見，此時奇異值的平方與能量相對應。

為直觀起見，下文的非負矩陣均以圖像為例。

定義1：設圖像矩陣[V∈Rm×n+]，定義原始圖像[V]與重構圖像[Vk]的相對距離誤差為[V-VkFVF]。

定義2：設圖像矩陣[V∈Rm×n+]的奇異值分解如引理所記，定義[σ2i]的貢獻率為：[εi=σi2/i=1lσj2]，[i=1，2，...，l]。

可見：若[j=1kεj=j=1kσj2/j=1lσj2]接近于1，則該圖像的主要信息包含在矩陣[Vk=j=1kσjpjqTj]中，而矩陣[j=k+1lσjpjqTj]表示次要信息。

定理1：設圖像矩陣[V∈Rm×n+]的奇異值分解如引理所記，給定重構圖像與原始圖像的相對誤差閾值[δ（0<δ<1）]。取最小的正整數[k0]，使得[δ≥1-j=1k0εj]。取[k0]為初始矩陣的維數，構作矩陣：[Vk0=j=1k0σjpjqTj]，則：[V-Vk0FVF≤δ]。

證明：[V-Vk0FVF=j=k0+1lσ2jj=1lσ2j=1-j=1k0εj≤δ]。

根據該定理，給出確定初始矩陣維數算法如下：

1）給定重構圖像與原始圖像的相對誤差閾值[δ（0<δ<1）]；

2）計算貢獻率：[εi=σi2/i=1lσj2]，[i=1，2，...，l]；

3）計算累計貢獻率：[j=1kεj，k=1，2，...，l]；

4）取[k0]，使得：[j=1k0εj≥1-δ2]且[j=1k0-1εj<1-δ2]。

因此，重構圖像[Vk0=j=1k0σjpjqTj]與原圖像的相對誤差不超過預定的閾值[δ]。

說明：文獻[10]提出：以[j=1kε′j=j=1kσjj=1lσj]來確定初始矩陣的維數（其中[ε′i=σi/i=1lσj]）。這與引理所表明的情況未能吻合。根據引理，采用奇異值平方計算貢獻率更為合理。

兩種方法求解初始矩陣維數的比較如下：

定理2：設圖像矩陣[V∈Rm×n+]的奇異值分解如引理所記。設[1≤p≤l]為整數。

記：[σ21+...+σ2pσ21+...+σ2l=ρ1]，[σ1+...+σpσ1+...+σl=ρ2]，則：[ρ1≥ρ2]。

證明：[ρ1-ρ2=（σ21+...+σ2p）（σ1+...+σl）（σ21+...+σ2l）（σ1+...+σl）—（σ21+...+σ2l）（σ1+...+σp）（σ21+...+σ2l）（σ1+...+σl）]

[=σ1（σ21+...+σ2p）+...+σl（σ21+...+σ2p）（σ21+...+σ2l）（σ1+...+σl）-σ1（σ21+...+σ2l）+...+σp（σ21+...+σ2l）（σ21+...+σ2l）（σ1+...+σl）=σp+1（σ21+...+σ2p）+...σl（σ21+...+σ2p）（σ21+...+σ2l）（σ1+...+σl）-σ1（σ2p+1+...+σ2l）+...+σp（σ2p+1+...+σ2l）（σ21+...+σ2l）（σ1+...+σl）]

[=（σ21σp+1-σ1σ2p+1）+...+（σ2pσp+1-σpσ2p+1）（σ21+...+σ2l）（σ1+...+σl）+（σ21σp+2-σ1σ2p+2）+...+（σ2pσp+2-σpσ2p+2）（σ21+...+σ2l）（σ1+...+σl）+]

[+...+（σ21σl-σ1σ2l）+...+（σ2pσl-σpσ2l）（σ21+...+σ2l）（σ1+...+σl）≥0]。

可見：在初始矩陣的維數相同的情況下[ρ1≥ρ2]，因此，若在相同累計貢獻率的情況下求初始矩陣的維數，則：采用奇異值的平方得到的維數不超過采用奇異值計算得到的維數。

2 圖像實驗

實驗條件：Windows7、Matlab7.0，CPU：1.8G，內存4.0G。圖像分辨率為：[512×512]。

貢獻率相同情況下，計算初始矩陣維數的結果如表1。

按照表1中維數[k0]，采用前段[k0]個奇異值重構圖像[Vk0=j=1k0σjpjqTj]。圖1對應于奇異值平方計算貢獻率，圖2對應于奇異值計算貢獻率，均按照表1中的累計貢獻率由低到高的順序排列。

可以看出：用不同的方法計算貢獻率，即使貢獻率相同，對應的圖像有較大的差異：這是因為貢獻率的計算方法不同。本文的方法一般取累計貢獻率在0.995乃至以上方可取得較好重構效果。

3 結束語

NMF中初始矩陣維數的選取關系到矩陣的計算、存儲成本。提出以奇異值平方來計算累計貢獻率以確定NMF中初始矩陣的維數。彌補了目前反復嘗試以確定初始矩陣維數的缺陷。引理及定理1保證了方法的合理性，定理2及表格1比較了兩種不同計算方法的效果。

NMF中初始矩陣維數與初始矩陣、迭代次數的關系有待進一步探索。

參考文獻：

[1] Lee D D，Seung H S. Learning the parts of objects by non-negative matrix factorization[J].Nature，1999，401（6755）：788- 791.

[2] 程明松，劉勺連.一種實用快速非負矩陣分解算法[J].大連理工大學學報，2013，53（1）：151-156.

[3] 高洪濤.非負矩陣因子分解算法理論和應用研究[D].上海：同濟大學，2005：8-18.

[4] 王炫盛，陳震，盧琳璋.Lanczos雙對角化：一種快速的非負矩陣初始化方法[J].廈門大學學報：自然科學版，2012，51（2）：149-152.

[5] 徐森，盧志茂.結合K均值和非負矩陣分解集成文本聚類算法[J].吉林大學學報：工學版，2011， 41（4）： 149-152.

[6] 李樂，章毓晉.非負矩陣分解算法綜述[J].電子學報，2008，36（4）：738-743.

[7] 徐泰燕，郝玉龍.非負矩陣分解及其應用現狀分析[J].武漢工業學院學報，2010，29（1）：109-114.

[8] Wild S， Curry J，Dougherty A.Improving non-negative matrix factorization through structured initialization [J].Pattern Recognition， 2004，37（11）： 2217-2232.

[9] Boutsidis C， Gallopoulos E.SVD based initialization：A head start for non-negative matrix factorization[J].Pattern Recognition， 2008，41（4）：1350-1362.

[10] Qiao H. New SVD based initialization strategy for Non-negative Matrix Factorization. arXiv：1410.2786v1，[cs.LG]10 Oct.2014.

[11] 張賢達.矩陣分析與應用[M].北京：清華大學出版社，2004：344-354，510-512.

[12] 林慶，李佳，雍建平，等.一種改進的基于NMF的人臉識別方法[J].計算機科學，2012，39（5）：243-245.

[13] 劉如京，王玲.一種NMF和SVD相結合的魯棒水印算法[J].計算機科學，2011，38（2）：271-273.

[14] Amy N. Langville， Carl D. Meyer， Russell Albright，et al. Algorithms，Initializations，and Convergence for the Non-negative Matrix Factorization. arXiv：1407.7299v1 [cs.NA] 28 Jul 2014.