陳劍軍++劉智秉

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

關(guān)鍵詞：非負(fù)矩陣分解；初始化矩陣維數(shù)；奇異值分解；貢獻(xiàn)率

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：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]。該算法通過簡單迭代將非負(fù)矩陣分解為兩個低階非負(fù)矩陣之積，從而使矩陣分解具有可解釋的實際意義。因此，NMF算法迅速引起了各科研領(lǐng)域的重視并將其廣泛應(yīng)用于圖像分析、數(shù)據(jù)挖掘、語音處理、機(jī)器人控制、生物醫(yī)學(xué)工程和化學(xué)工程等諸多領(lǐng)域[2-7]，[12-13]。

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

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

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

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

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

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

1 NMF中初始矩陣維數(shù)的確定

由文獻(xiàn)[11]不難推導(dǎo)出如下的結(jié)論：

引理：給定非負(fù)矩陣[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））]，設(shè)其元素為[m]信道的、已經(jīng)過零均值化處理的觀測數(shù)據(jù)序列；[i=1，2，...，m；][j=1，2，...，n]。則：第[k]信道的信號功率[pk=1nσ2k]，[k=1，2，...，m]。

可見，此時奇異值的平方與能量相對應(yīng)。

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

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

定義2：設(shè)圖像矩陣[V∈Rm×n+]的奇異值分解如引理所記，定義[σ2i]的貢獻(xiàn)率為：[ε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：設(shè)圖像矩陣[V∈Rm×n+]的奇異值分解如引理所記，給定重構(gòu)圖像與原始圖像的相對誤差閾值[δ（0<δ<1）]。取最小的正整數(shù)[k0]，使得[δ≥1-j=1k0εj]。取[k0]為初始矩陣的維數(shù)，構(gòu)作矩陣：[Vk0=j=1k0σjpjqTj]，則：[V-Vk0FVF≤δ]。

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

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

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

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

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

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

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

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

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

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

記：[σ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]。

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

2 圖像實驗

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

貢獻(xiàn)率相同情況下，計算初始矩陣維數(shù)的結(jié)果如表1。

按照表1中維數(shù)[k0]，采用前段[k0]個奇異值重構(gòu)圖像[Vk0=j=1k0σjpjqTj]。圖1對應(yīng)于奇異值平方計算貢獻(xiàn)率，圖2對應(yīng)于奇異值計算貢獻(xiàn)率，均按照表1中的累計貢獻(xiàn)率由低到高的順序排列。

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

3 結(jié)束語

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

NMF中初始矩陣維數(shù)與初始矩陣、迭代次數(shù)的關(guān)系有待進(jìn)一步探索。

參考文獻(xiàn)：

[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] 程明松，劉勺連.一種實用快速非負(fù)矩陣分解算法[J].大連理工大學(xué)學(xué)報，2013，53（1）：151-156.

[3] 高洪濤.非負(fù)矩陣因子分解算法理論和應(yīng)用研究[D].上海：同濟(jì)大學(xué)，2005：8-18.

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

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

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

[7] 徐泰燕，郝玉龍.非負(fù)矩陣分解及其應(yīng)用現(xiàn)狀分析[J].武漢工業(yè)學(xué)院學(xué)報，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] 張賢達(dá).矩陣分析與應(yīng)用[M].北京：清華大學(xué)出版社，2004：344-354，510-512.

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

[13] 劉如京，王玲.一種NMF和SVD相結(jié)合的魯棒水印算法[J].計算機(jī)科學(xué)，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.