非負矩陣分解文獻綜述一、國內外研究現狀近年來,技術傳感器技術和計算機硬件的發展導致數據量的增加，許多經典數據分析工具被迅速壓倒?因為信息采集設備只有有限的帶寬，收集到的數據并不經常準確?其次,在很多情況下，從復雜現象觀察到的數據，其往往代表幾個相互關聯的變量共同作用的綜合結果?當這些變量更少的精確定義時，在原始數據中包含的實際信息往往是重疊的、模糊的.為了處理這些海量數據，科學家產生了新的關注?1999年,在刊物Nature上,DanielLee和SebastianSeung開始的一系列新的NMF的研究,數以百計的論文引用Lee和Seung的論文，但一些較不為人知的事實是,在Lee和Seung的論文發表之前,PenttiPaatero 開始了相關的工作.雖然Lee和Seung引用Paatero的論文丄ee和Seung將Paatero的工作稱為正矩陣分解，然而，Paatero的工作很少被后來的作者所引用.這是因為Paatero將其工作稱為正矩陣分解，這是誤導Paatero創建NMF算法。實際上Paatero年前發表了他最初的分解算法⑴.2005年,Lin為了加速Lee和Seung的NMF迭代算法的收斂速度，最近提出使用投影梯度有約束的優化方法［2］，該方法與標準的（乘法更新規則）的方法相比，計算似乎有更好的收斂性.使用某些輔助約束，可以降低分解有約束的優化假設，降低投影梯度方法的局限性.2007年,V.BIondel等對標準NMF算法進行了加權改進，提出了加權NMF方法［3］。通過加權，更好的表述了數據中的重要區域.其加權方法是：首先，定義數據中的重要區域，然后，在優化過程中，如果在該重要區域中重建錯誤，就給他分配更多的權重.國內對NMF的研究相對開始的較晚.2001年，原微軟中國研究院的李子青博士、張宏江博士等人發現Lee和Seung提出的經典NMF算法在人臉圖像未得到配準的情況下，不能學習得到人臉的部件.并提出了局部非負矩陣分解來解決這個問題⑷.Chen等人將LNMF算法應用于人臉檢測并取得了較好的效果.現為中科院自動化所生物識別與安全技術研究中心主任的李子青帶領他的團隊 ，于2009年,提出了基于吉布斯隨機場的NMF算法［4］，該算法的收斂速度較快，并且得到的分解結果具有較好的稀疏性和可解釋性.清華大學信息科學與技術國家實驗室的章毓晉教授、李樂博士對非負矩陣分解的研究做了大量的工作 ，對NMF算法的研究現狀進行了綜述，對已有的NMF算法進行了很好的分類，指出各個NMF算法的缺點，并提出了改進的算.針對NMF的先天缺陷，即數據描述能不強、推廣性差，提出了非負矩陣集分解的概念和相應的算法⑷.浙江大學計算機學院的蔡登教授等人針對流形數據提出了圖正則非負矩陣分解算法gnmF,該方法在矩陣分解過程中明確考慮了數據集攜帶的幾何信息： 如果數據點在原空間是鄰近點，那么對應到新的基下也是鄰近點?此外，他們還提出了局部保留NMF.可見，國內的研究機構和學者也逐漸加入NMF研究的行列，并取得了一定的成果?二、非負矩陣分解2.1非負矩陣分解原理信息或信號處理的許多數據具有非負性的特點[5],如灰度圖像、物質成分含量、文章中單詞出現的次數和統計學中的概率轉移矩陣等?在用線性表示方法處理這類數據時，往往要求分解的結果都是非負的?此時若采用傳統的因子分析方法,如主成份分析，因為其結果中含有負數而失去了物理意義，而采用非負矩陣分解方法就可以避免這一點?非負矩陣分解是一種多變量分析方法?它首先把高維的數據進行分解，得到低維的數據,然后再對低維的數據進行壓縮，以得到理想的壓縮效率?假設有m個n維空間的樣本數據，用Xnm表示.該數據矩陣中各元素都是非負的，即X0,對矩陣Xnm進行線性分解,有XnmBnrCrm,其中Bnr稱為基矩陣，Crm為系數矩陣?若選擇r比n小，即r<n,用系數矩陣代替原數據矩陣，就可以實現對原數據矩陣的降維，得到數據特征的降維矩陣.然后對系數矩陣C進行壓縮，從而減少存儲空間,節約計算資源.2.2非負矩陣分解的算法為了實現矩陣的非負分解，首先需要定義一個損失函數來刻畫分解前后的逼近程度,然后在非負性約束下求解?最早提出的正矩陣分解方法采用傳統的梯度下降算法與加性迭代規則⑹.現在我們對這種方法進行了改進，在此基礎上采用乘性迭代規則，更適合非負數據的特點，即在非負性初始化的基礎上，在迭代過程中能簡單地保持非負性，而加性迭代規則就需要一個強制將負值變為零的步驟 ?2.3非負矩陣分解算法的目標函數目標函數又稱為代價函數(CostFunction)是衡量分解前后矩陣相似度的量⑺.力求相似度最大亦即使得X與胡泊勺差異最小，兩種方式來衡量⑹歐氏距離和K-L散度.1mn2minf(u,v)； (Xj(uv)j)歐氏距離： 2i1j1 (1)且UiaO,Vj0，i,a,b,j。上式等價于矩陣的范數如下式(Xj(Xj(UV)ij)XUV其中，l?F二是佛羅貝尼烏斯(Frobrnius)范數,兩個矩陣中各個元素之差的平方,來衡量X與胡泊勺距離.很顯然當且僅當X=UV寸為0,這是使用最多的目標函數,而且研究起來非常方便.一般情況下利用此公式.另一目標函數是K-L散度形式：且Uia0,Vbj0， i,a,b,j。由于X與UV并不是對稱的，所以并不能稱為距離，而稱之為散度或者相對嫡?描述了UV相比X分散的程度.當ijXijjj(UV)ij1時散度為0而且此時的X與UV,為標準正態分布.目前，上述目標函數同時求解U和U時是不能得到最優解的，因為目標函數是非凸的,只有單獨對于U或者V時目標函數才是凸的，才有最優解.2.4迭代規則以及算法的收斂性2.4.1迭代規則：我們的目的是要使f(U,V)最小，即求如下最大似然解：{U,V}argmaxP(f(U,V)|U,V)argmin{logP(f(U,V)|U,V)}⑷首先，假設噪聲服從高斯分布,令E=f(W,H)(誤差函數),則：1 Ej2p(E/U,V)^^=exp(^-4)可將問題轉化為求下式iog(2j)L(U,V)2 (Xjiog(2j)2iiij的最小值.為了求出迭代規則，只需要求出Uij和Vj.假設所有數據點噪聲的方差是相同的，即j,i,j。由矩陣運算規則:(UV)ij UikVkik (-7\

可以推導出以下偏導式：所以：(WH)jWik(UV)ijHkj,^^VkjUikL(U,V)Uikc[Vkj可以推導出以下偏導式：所以：(WH)jWik(UV)ijHkj,^^VkjUikL(U,V)Uikc[Vkj(Xjj(UV)ij]c[(XVT)ik(UVVT)ik](9)L(U,V)Vkjc[UikXjiC是常數.如此以來對U和U(UV)ijUik)]c[(UTX)kj(UTUV)kj]i(10)從負梯度方向進行迭代:Uikn°Uikn)[(XVT)ik(UVVT)ik](11)Vikn1)Vikn)[(UTX)kj(UVUT)kj](12)進而,令:U；(UVVT)ikVk：(UVUT)kj可得乘性迭代規則Uik可得乘性迭代規則Uik1:(13)(14)Poisson分布(14)Poisson分布(泊松分布)經過類(15)(16)然后，在散度目標函數形式下，假設噪聲服從似的推導過程得迭代規則2:U U jVkjXij/(UV)ijUik UikjV—iUikXij/(UV)ijkjkjiuikiik242收斂性證明收斂性的證明需要用到輔助函數⑻，類似于EM(Expectation-Maximization，最大期望值)算法?G(v,vt) F(v),G(v,v)F(v)(17)定義1:設G(v,V)是F(h)的輔助函數G(v,vt) F(v),G(v,v)F(v)(17)引理1:假設G(v，V)是輔助函數,引理1:假設G(v，V)是輔助函數,那么函數F(v)在以下的更新規則下是非增的vt1argminG(v,vt)v可以非常容易的證明：(18)F(vt1)G(vt1,vt)G(vt,vt)F(vt)即證。三、NMF的問題給定一個非負矩陣，ARmn和一個正整數k<min{m,n},找到非負矩陣R和R的最小化功能[10]f(W,H)12AWH(19)乘積WF稱為A的NMF雖然A不一定等于乘積WH乘積WH是至多秩為k的近似因子分解，但我們將省略“近似”這個詞在本文的其余部分?適當的k的值決定在實踐中至關重要，但k是通常的選擇問題相關的.在大多數情況下，然而,k通常選擇這樣k>min(m,n)在這種情況下，WH可以被認為是一個壓縮的形式的數據.NMF的另一個關鍵問題是計算問題(19)的極小值，來抽取作為基向量W的隱含特征,然后可以用于識別和分類?不允許W和H中出現負數,NMF使部分的部分的非負組合形成一個整體[11].特性可能是部分圖像數據，主題或集群在文本數據，或特定吸收高光譜數據的特征?由于f(W,H)的非凸性,影響問題(19)的極小值的主要問題是局部最小值的存11在性.設D為任何非負可逆矩陣,且D也是非負的.進而,考慮WDDH,也可以看出問題(19)極小值計算的困難性.NMF在數據挖掘中有很好的應用，在實踐中,即使局部最小值可以提供理想的屬性數據壓縮.四、基本算法(乘法更新算法)乘法更新NMF算法W=rand(m,k);%初始化W為隨機稠密矩陣H=rand(k,n);%H 為隨機稠密矩陣進行初始化Fori=1:maxiter(MU)HH.*(WtA)./(WtWH109);T T 9(MU)WW.*(AH)./(WHH 10);End

-9為了避免被零除,在每個更新的規則加入10丄ee和Seung利用梯度的連續下降性,斷言上述算法收斂到局部最小，但后來該斷言被證明是不正確的[12].事實上，由Lee和Seung僅僅證明顯示一個連續下降性值,不排除下降到一個鞍點.要理解其中的原因,一個必須考慮Karush-Kuhn-Tucker最優性條件.首先,如果初始矩陣的W和H是嚴格的正，在整個迭代中，W和H保持為正，這由乘法原則很容易驗證的.其次，如果迭代序列(WH)收斂到 (W*，H*),且W* 0,H* 0那么(f/W)(W*,H*) 0和(f/H)(W*,H*) 0第二點可以利用H更新規則的補充形式HH[H./(WtWH)].*[Wt(AWH)] (20)來驗證.考慮到H中的(i,j)元素，假設H的極限點已經達到,H>0.然后從式(20),我們知道5

[WT5

[WTWH]ij([WTA]j[WTWH]j) 0由于Hij 這意味著何蝕[WTWH]j,這意味著[f/H]ij0將這兩點結合起來,滿足Karush-Kuhn-Tucker最優性條件下,這是唯一的極限點(W*H*),沒有任何元素等于0.W0,H0,(WHA)HT0,WT(WHA)0,(WHA)HT.*W0WT(WHA).*H0.盡管事實，例如，比0對于所有的迭代，這個元素可以收斂到一個極限值在(W,H)時[f/H]j0即使山0.因此，Hj0是可能的,在這種情況下,必須證明相應的互補松弛條件，(f/H)(W*,H*) 0,沒有明顯的使用乘法更新規則來做這個.綜上所述，我們只能對Lee和Seung乘法更新算法的收斂以下聲明，當算法算法融合在可行區域內的一個極限點 ，這個點是一個固定的點.這個固定點可以或可能不是局部極小.當極限點在于可行域的邊界，其平穩性無法確定.作為第一個著名的NM!算法,Lee和Seung乘法更新算法已成為基準的新算法進行了比較丄ee和Seung當他們收斂(這往往是在實踐中),是出了名的慢收斂.他們需要的迭代次數比梯度算法和ALS算法要多的多.每次迭代高由于每次迭代需要0(mnk工作.然而,優秀的改進算法可以改善其情況.例如,在W的更新規則,這就要求乘積首先被建立?為了克服這些缺點,研究人員已經提出了修改原來的Lee和Seung算法.例如,給出了一個修改算法間，加速Lee和Seung算法，但不幸的是,仍然有相同的收斂問題.最近丄in創建了一個修改，解決了一個收斂問題.即Lin的改造IED算法保證收斂到一個穩定點[14].然而,該算法要求每次迭代的計算量比已經慢 Lee和Seung算法略多.此外Dhillon和SRA導出乘法更新規則，將權重在逼近要素的重要性[15].五、總結在本文中，我們試圖勾勒出一些相關的非負矩陣分解的主要概念 .雖然非負矩陣分解理論提出不到二十年，但人們對其研究卻是非常重視的，所以非負矩陣分解理論才能有了如此快的發展，并成功應用到其他領域,尤其在模式識別領域內的應用越來越活躍.通過結合其他理論使得非負矩陣分解算法具有更好的性能是今后主要的發展方向.但是,非負矩陣分解算法依然存在著許多沒有解決的問題如：矩陣的初始化問題、算法的收斂性速度問題、迭代次數確定問題、降維數據維度的選擇問題、評判算法好壞的標準問題等等.這些問題有時候對實驗的結果有很大的影響，所以將來有必要對這些存在的問題做仔細的研究 ，我相信這些問題會很快得到解決的.參考文獻：MichaelWBerry,MurrayBrowne,AmyN.Langville,V.PaulPauca,RobertJ.Plemmon,Algorithmsandapplications forapproximatenonnegativematrixfactorization[J],Computational Statistics&DataAnalysis,2007,52(27),2-3.MichaelWBerry,MurrayBrowne,AmyN.Langville,V.PaulPauca,RobertJ.Plemmon,Algorithmsandapplications forapproximatenonnegativematrixfactorization[J],Computational Statistics&DataAnalysis,2007,52(27),3-4.胡俐蕊,非負矩陣分解方法及其在選票圖像識別中的應用 [D],安徽大學博士學位,2013.董云影,張慧，張紅，非負矩陣分解的研究現狀[J]，黑龍江科技信息，2015,28.⑸張永鵬，鄭文超，張曉輝，非負矩陣分解及其在圖像壓縮中的應用[J],西安郵電學院學報,2008,13(3)，1-2.⑹李樂，章毓晉，非負矩陣分解算法綜述[J],電子學報，2008,4(36),737-743胡學考,基于非負矩陣分解的圖像表示和分類研究 [D],遼寧工業大學碩士學位，2015.LeeD,SeungH,AlgorithmsforNon-NegativeMatrixFactorization.AdvancesinNeurallnformationProcessingSystems[J],MITPress,2001杜世強，石玉清，王維蘭,.基于圖正則化的半監督非負矩陣分解.計算機工程與應用[J],2012,48(36),194-200.MichaelWBerry,MurrayBrowne,AmyN.Langville,V.PaulPauca,RobertJ.Plemmon,Algorithmsandapplicationsforapproximatenonnegativematrixfactorization[J],Computational Statistics&DataAnalysis,2007,52(27),155-173.LeeD,SeungH,Learningthepartsofobjectsbynon-negativematrixfactorization[J],1999,Natu