非負矩陣分解NMF

非負矩陣分解(NMF,Non-negative matrix factorization)

NMF的發展及原理

　　著名的科學雜志《Nature》于1999年刊登了兩位科學家D.D.Lee和H.S.Seung對數學中非負矩陣研究的突出成果。該文提出了一種新的矩陣分解思想——非負矩陣分解(Non-negative Matrix Factorization，NMF)算法，即NMF是在矩陣中所有元素均為非負數限制條件之下的矩陣分解方法。該論文的發表迅速引起了各個領域中的科學研究人員的重視：一方面，科學研究中的很多大規模資料的分析方法需要通過矩陣形式進行有效處理，而NMF思想則為人類處理大規模資料提供了一種新的途徑；另一方面，NMF分解算法相較于傳統的一些算法而言，具有實作上的簡便性、分解形式和分解結果上的可解釋性，以及占用存儲空間少等諸多優點。為高效處理這些通過矩陣存放的資料，一個關鍵的必要步驟便是對矩陣進行分解操作。通過矩陣分解，一方面将描述問題的矩陣的維數進行削減，另一方面也可以對大量的資料進行壓縮和概括。

　　利用矩陣分解來解決實際問題的分析方法很多，如PCA(主成分分析)、ICA(獨立成分分析)、SVD(奇異值分解)、VQ(矢量量化)等。在所有這些方法中，原始的大矩陣V被近似分解為低秩的V=WH形式。這些方法的共同特點是，因子W和H中的元素可為正或負，即使輸入的初始矩陣元素是全正的，傳統的秩削減算法也不能保證原始資料的非負性。在數學上，從計算的觀點看，分解結果中存在負值是正确的，但負值元素在實際問題中往往是沒有意義的。例如圖像資料中不可能有負值的像素點；在文檔統計中，負值也是無法解釋的。

NMF的基本思想

　　NMF的基本思想可以簡單描述為：對于任意給定的一個非負矩陣A，NMF算法能夠尋找到一個非負矩陣U和一個非負矩陣V，使得滿足 ，進而将一個非負的矩陣分解為左右兩個非負矩陣的乘積。

NMF問題描述

   傳統的NMF問題可以描述如下

    給定矩陣

，尋找非負矩陣

和非負矩陣

，使得

。

    分解前後可了解為：原始矩陣

的列向量是對左矩陣

中所有列向量的權重和，而權重系數就是右矩陣對應列向量的元素，故稱

為基矩陣，

為系數矩陣。一般情況下

的選擇要比

小，即滿足

，這時用系數矩陣代替原始矩陣，就可以實作對原始矩陣進行降維，得到資料特征的降維矩陣，進而減少存儲空間，減少計算機資源。

    由于分解前後的矩陣中僅包含非負的元素，是以，原矩陣A中的一列向量可以解釋為對左矩陣U中所有列向量(稱為基向量)的權重和，而權重系數為右矩陣V中對應列向量中的元素。這種基于基向量組合的表示形式具有很直覺的語義解釋，它反映了人類思維中“局部構成整體”的概念。研究指出，非負矩陣分解是個NP問題，可以劃為優化問題用疊代方法交替求解U和V。NMF算法提供了基于簡單疊代的求解U，V的方法，求解方法具有收斂速度快、左右非負矩陣存儲空間小的特點，它能将高維的資料矩陣降維處理，适合處理大規模資料。利用NMF進行文本、圖像大規模資料的分析方法，較傳統的處理算法速度更快、更便捷。

由于NMF不允許基圖像或中間的權重矩陣中出現負值，是以隻有相加組合得到的正确基圖像才允許，最後通過處理後的重構圖像效果是比較滿意的(對矩陣非負的限制使得這種分解能夠達到用部分表達整體的效果,簡單地說就是,整體由部分的疊加而沒有了正負抵消 )。[Learning the parts of objects by non-negative matrix factorization]

非負矩陣分解NMF的一個示例解釋

　　在VQ分解中，每一列的

被限制為一個一進制矢量。其中隻有一個元素為1，其他元素為0。若

的第一列中，第r1個元素為1，那麼

中第一列的臉，就完全由基圖像中的第r1列資料表示。此時得到的基圖像稱為原型基圖像，這些原型圖像表示一張原型臉。

       在PCA分解中，

的各列之間互相正交，

各行之間互相正交。這個限制比VQ的松弛很多，也就是，

中的元素可為正也可為負。

中每一張臉的每一個像素點都是

中各列對應的像素點的一個權重和。由于權重矩陣

中元素符号的任意性，是以基矩陣

表示出來并不像VQ中原型臉那樣的直覺可解釋。此時将W的列資料畫出來并不一定能直接看到一張“臉”。但是在統計上可以解釋為最大方差方向，我們把這些“臉”稱為“特征臉”。

       在NMF中，由于加了非負限制。與VQ的單一進制素不為0不同，NMF允許基圖像H間的權重結合來表示臉部圖像V；與PCA不同，NMF的權重系數H中的元素都為非負的。前兩者得到的都是一個完整的臉部特征基圖像，而NMF得到的是臉部子特征。通俗點說，VQ是用一張完整的圖像直接代表源臉部圖像；PCA是将幾個完整人臉加減壓成一張臉；而NMF是取甲的眼睛，乙的鼻子，丙的嘴巴直接拼成一張臉。這樣解釋雖然細節上略有不妥，但不失其概念上的意義。

通過圖1中的面部特征提取例子可領略NMF處理資料的方式。最左邊的大矩陣由一系列的小圖組成，這些小圖是分析資料庫中包含的2429個臉部圖像的結果，每幅圖像由19×19個像素組成。傳統方法中這樣的小圖是一幅完整的人臉圖像，但是在NMF方法中，每個小圖是通過一組基圖像乘以一個權重矩陣而産生的面部特征圖，經過這樣處理的每幅小圖像恰好表示了諸如“鼻子”、“嘴巴”、“眼睛”等人臉局部概念特征，這便大大壓縮了存放的圖像資料量。左邊的大矩陣由每幅小圖像的19列一起組成矩陣的一列，那樣它就是19×19=361行，2429列。這個例子中，NMF方法用基圖像來代表眼、眉毛、鼻子、嘴、耳朵、胡子等，它們一起組成了資料庫中的臉。這樣給人最先的直覺就是它很好地壓縮了資料。事實上Lee和Seung在他們的論文中更深入地指出，與人類識别事物的過程相似，NMF也是一種優化的機制，近似于我們的腦分析和存儲人臉資料的過程。這個例子中，原圖像表示這些局部特征的權重組合，這與人類思維中“局部構成整體”的概念是相吻合的。是以，NMF算法似乎展現了一種智能行為。

                 圖1  NMF提取面部特征的執行個體

上圖的第一個方塊為矩陣W，組成的圖像。其中每一個小格為W的一列的19*19個元素重構而成的19*19的矩陣圖像。第二個方塊為H矩陣，其中紅色表示負數，灰黑表示正數， 顔色程度表示大小。右邊的圖像隻是V矩陣的一列的19*19個元素組成的一張原始臉。

NMF限制V,W,H都是非負的,而VQ限制H必須必須由機關向量(隻有一個元素為1,其餘為0)組成,PCA限制W的列是規範正交的,H的行是正交的,這導緻了有圖中三種不同的分解結果。

從結果可以看出:NMF分解結果與我們部分形成整體的直覺是相一緻的。NMF學習出一種基于部分的表達。

皮皮blog

非負矩陣分解NMF的應用

　　事實上，在Lee和Seung發表他們的研究成果之前，針對非負矩陣的研究早在20世紀70年代已經有數學家做了一些相關的工作，但是沒有引起過多的關注。20世紀90年代早期，科學家開始将數學上非負矩陣的研究成果用于環境處理和衛星遙控的應用，但是對于非負矩陣的應用意義和價值的了解仍隻局限于少數科學家中，人們還沒有廣泛重視這種方法。直到1999年Lee和Seung的非負矩陣研究成果發表在《Nature》雜志之後，這一切才得以改變。盡管同年有另兩位科學家也發表了與Lee和Seung相近的研究結果，但由于論文刊登在并非如《Nature》那樣具有極高聲譽的學術雜志上，是以其工作并沒有得到如Lee和Seung同樣的關注，這也從一個側面折射了高水準學術雜志對研究工作的推動作用。

　　二、應用領域

　　NMF是一個很有效的算法，它力圖在大規模的矩陣資料中發現具有解釋功能的關系，相比目前文獻中公布的其他方法來說，使用NMF的算法也是非常精确和快速的。NMF算法思想能為世界上權威的學術刊物所接受并非偶然，因為該理論本身蘊涵了巨大的潛能，這種潛在的力量将通過各種具體的應用來得以展現。

在衆多應用中，NMF能被用于發現資料庫中的圖像特征，便于快速自動識别應用；能夠發現文檔的語義相關度，用于資訊自動索引和提取；能夠在DNA陣列分析中識别基因等等。NMF能用于發現資料庫中圖像的特征，便于快速識别應用，比如實作錄入恐怖分子的照片，然後在安檢口對可疑人員進行盤查。在文檔方面，NMF能夠發現文檔的語義相關度，用于資訊的自動索引和提取。在生物學中，在DNA陣列分析中識别基因等。在語音識别系統中NMF也能發揮重要作用。有人已經将NMF應用于盲信号分離BSS領域，取得一定的效果，不過其研究的BSS有非欠定的要求（即源數不大于傳感器數），且混合矩陣等都是正的。

　　(1) 圖像分析

　　NMF最成功的一類應用是在圖像的分析和處理領域。圖像本身包含大量的資料，計算機一般将圖像的資訊按照矩陣的形式進行存放，針對圖像的識别、分析和處理也是在矩陣的基礎上進行的。這些特點使得NMF方法能很好地與圖像分析處理相結合。人們已經利用NMF算法，對衛星發回的圖像進行處理，以自動辨識太空中的垃圾碎片；使用NMF算法對天文望遠鏡拍攝到的圖像進行分析，有助于天文學家識别星體；美國還嘗試在機場安裝由NMF算法驅動的識别系統，根據事先輸入計算機的恐怖分子的特征圖像庫來自動識别進出機場的可疑恐怖分子。

　　(2) 文本聚類/資料挖掘

　　文本在人類日常接觸的資訊中占有很大分量，為了更快更精确地從大量的文本資料中取得所需要的資訊，針對文本資訊處理的研究一直沒有停止過。文本資料不光資訊量大，而且一般是無結構的。此外，典型的文本資料通常以矩陣的形式被計算機處理，此時的資料矩陣具有高維稀疏的特征，是以，對大規模文本資訊進行處理分析的另一個障礙便是如何削減原始資料的維數。NMF算法正是解決這方面難題的一種新手段。NMF在挖掘使用者所需資料和進行文本聚類研究中都有着成功的應用例子。由于NMF算法在處理文本資料方面的高效性，著名的商業資料庫軟體Oracle在其第10版中專門利用NMF算法來進行文本特征的提取和分類。為什麼NMF對于文本資訊提取得很好呢？原因在于智能文本處理的核心問題是以一種能捕獲語義或相關資訊的方式來表示文本，但是傳統的常用分析方法僅僅是對詞進行統計，而不考慮其他的資訊。而NMF不同，它往往能達到表示資訊的局部之間相關關系的效果，進而獲得更好的處理結果。

　　(3) 語音處理

　　語音的自動識别一直是計算機科學家努力的方向，也是未來智能應用實作的基礎技術。語音同樣包含大量的資料資訊，識别語音的過程也是對這些資訊處理的過程。NMF算法在這方面也為我們提供了一種新方法，在已有的應用中，NMF算法成功實作了有效的語音特征提取，并且由于NMF算法的快速性，對實作機器的實時語音識别有着促進意義。也有使用NMF方法進行音樂分析的應用。複調音樂的識别是個很困難的問題，三菱研究所和MIT(麻省理工學院)的科學家合作，利用NMF從演奏中的複調音樂中識别出各個調子，并将它們分别記錄下來。實驗結果表明，這種采用NMF算法的方法不光簡單，而且無須基于知識庫。

　　(4) 機器人控制

　　如何快速準确地讓機器人識别周圍的物體對于機器人研究具有重要的意義，因為這是機器人能迅速作出相應反應和動作的基礎。機器人通過傳感器獲得周圍環境的圖像資訊，這些圖像資訊也是以矩陣的形式存儲的。已經有研究人員采用NMF算法實作了機器人對周圍對象的快速識别，根據現有的研究資料顯示，識别的準确率達到了80%以上。

　　(5) 生物醫學工程和化學工程

　　生物醫學和化學研究中，也常常需要借助計算機來分析處理試驗的資料，往往一些煩雜的資料會耗費研究人員的過多精力。NMF算法也為這些資料的處理提供了一種新的高效快速的途徑。科學家将NMF方法用于處理核醫學中的電子發射過程的動态連續圖像，有效地從這些動态圖像中提取所需要的特征。NMF還可以應用到遺傳學和藥物發現中。因為NMF的分解不出現負值，是以采用NMF分析基因DNA的分子序列可使分析結果更加可靠。同樣，用NMF來選擇藥物成分還可以獲得最有效的且負作用最小的新藥物。[非負矩陣分解在分析癌症突變異質性中的作用]

　　此外，NMF算法在環境資料處理、信号分析與複雜對象的識别方面都有着很好的應用。近年來采用NMF思想的應用才剛展開，相信以後會有更多的成功應用。這些成功的應用反過來也将促進NMF的進一步研究。

　　三、結束語

　　數學如同計算機的靈魂，NMF通過計算機與各個領域結合後的應用取得了令人歎服的成效。NMF的故事還在繼續，NMF的應用領域還有待進一步的發掘，針對NMF的進一步研究也沒有停止過，其中諸如分解的存在性、惟一性和收斂性以及收斂的速度等問題的深入探讨必将使該思想能更好地服務于人類。 

[非負矩陣分解：數學的奇妙力量]

NMF的應用執行個體

示例1

無論是在需要将新聞分門别類的應用中還是在資訊檢索中判斷兩個網頁文本内容的相似度(進而判斷是否同類)的應用中,我們都需要從文檔中學習到一些主要的特征詞以代表這篇文檔并據此聚類。

有許多應用都需要将模式(文檔,圖像,聲音)進行壓縮或者概括,或者說,我們需要從這些模式中提取出少量的重要的特征,原來的模式可以用這些特征進行還原而不出現大的誤差。将矩陣分解為兩個低秩矩陣相乘提供一種解決此問題的思路,兩個矩陣相乘的結果是原矩陣低維的近似。

在圖像領域,需要将圖像壓縮表達為一些特征的組合。

實戰中可能多次實驗結果不同,需要強調這是局部最優,結果受初始值選取的影響。

示例2

請設計合适的主成分分析模型, 并提供相應算法, 使得當輸⼊為下圖左⼿邊資訊時, 可以傳回右⼿邊的主成分元素。

左圖是通過右圖8個部分通過一定的随機稀疏組合而成的8×8=64幅飛機圖，我們要做的就是給你左圖，求出右圖的成分。

這時使用NMF就可以輕松求解：（求解出的components向量可能是歸一化的，而原圖是01組成的，我們可以通過門檻值來将浮點數變成01）

estimators = decomposition.NMF(n_components=n_components, init='nndsvd', )

estimator.fit(data)

components_ = estimator.components_[:n_components]  # numpy.ndarray

plot_gallery(components_)

components_ = components_[sort_index]

plot_gallery('criterias', criterias, image_shape=image_shape)

components_[components_ > 0.1] = 1

components_[components_ <= 0.1] = 0

plot_gallery('%s - Train time %.1fs' % (name, train_time), components_, image_shape=image_shape)

error = spatial.distance.euclidean(criterias.reshape(-1), components_.reshape(-1))

不過如果使用下面進階主題中提到的Structured PCA，可能效果更好。

[LiuXin: 大資料優化算法]

皮皮blog

非負矩陣分解的算法和實作

NMF實作原理：NMF若幹更新法則

NMF求解問題實際上是一個最優化問題，利用乘性疊代的方法求解

和

，非負矩陣分解是一個NP問題。NMF問題的目标函數有很多種，應用最廣泛的就是歐幾裡得距離和KL散度。

關于更新法則，Daniel D. Lee和H. Sebastian Seung的文章《Algorithms for Non-negative Matrix Factorization》有詳細的公式推導證明。由于W與H的乘積是對V的近似估計，是以評價分解好壞的标準便是兩者之間的差異。文中在不同的代價函數下提出了不同的更新法則，包括乘性更新法則與加性更新法則。文中還通過構造輔助函數對疊代算法的收斂性進行了證明。

寫法1

   在NMF的分解問題中，假設噪聲矩陣為

，那麼有

   現在要找出合适的

和

使得

最小。

假設噪聲服從不同的機率分布，通過最大似然函數會得到不同類型的目标函數。接下來會分别以噪聲服從高斯分布和泊松分布來說明。

    （1）噪聲服從高斯分布

       假設噪聲服從高斯分布，那麼得到最大似然函數為

        取對數後，得到對數似然函數為 

        假設各資料點噪聲的方差一樣，那麼接下來要使得對數似然函數取值最大，隻需要下面目标函數值最小。 

       該損失函數為2範數損失函數，它是基于歐幾裡得距離的度量。又因為

       那麼得到 

       同理有 

        接下來就可以使用梯度下降法進行疊代了。如下

       如果選取

        那麼最終得到疊代式為 

        可看出這是乘性疊代規則，每一步都保證了結果為正數，一直疊代下去就會收斂，當然收斂性的證明省略。 

   （2）噪聲服從泊松分布

       若噪聲為泊松噪聲，那麼得到損失函數為 

       同樣經過推到得到

[非負矩陣分解（NMF） ]

寫法2

•  Cost function 1，歐幾裡得距離( Euclidean distance)：

                                                                 （1）

           在此代價函數下的乘性更新法則有：

       及      

                                 （2）

• cost function 2，分離度（divergence）：

                                                         （3）

              在此代價函數下的乘性更新法則為：

         以及      

                                   （4）

       另外有加性更新法則如下：

       歐幾裡得距離( Euclidean distance)下的加性更新為：

                                   （5）

 此時隻要疊代步長

的所有元素設為足夠小的正數那麼歐式距離會随着疊代而減小。而當疊代步長滿足：

，可以得到此時的加性更新等價于式子（2）中的乘性更新。

        分離度（divergence）下的加性更新為：

                                                （6）

同樣疊代步長若為足夠下的正數的話，分離度代價函數的值會随着更新而減小，而當疊代步長滿足：

，可同樣得到此時的加性更新等價于式子（4）中的乘性更新法則。 

[ 非負矩陣分解(NMF,Nonnegtive Matrix Factorization)  ]

收斂性證明

如上所述，《Algorithms for Non-negative Matrix Factorization》文中還通過構造輔助函數對疊代算法的收斂性進行了證明。小小整理如下：

[凱：非負矩陣分解Algorithms for Non-negative Matrix Factorization]

NMF的相關算法

Local NMF(LNMF),Discriminant NMF(DNMF),non-negative sparse coding(NNSC),non-smooth NMF(nsNMF),projective NMF,temporal NMF with spatial decorrelation constraints,shifted NMF,incremental NMF,sparse higher order NMF and polynomial NMF 等等，對于NMF分解的唯一性探讨也是NMF最近比較受關注的方面。

非負矩陣分解已經有了很多算法，例如Multiplicative   Update，Projected Gradient Method，Gradient Descent。交替最小二乘法比較符合上面的解釋，具有更好的統計意義，而且收斂性質很好，計算速度快。已有的交替最小二乘法都使用冷冰冰的二次規劃算法求解非負回歸，在bignmf中使用的最小角回歸的思路解非負回歸，更有統計的感覺，而且速度更快。

 非負矩陣分解的具體算法

輸入參數：Ｘ，Ｒ，MAXITER，其中Ｘ為被分解的矩陣，Ｒ為降階後Ｂ的秩，ＭＡＸＩＴＥＲ為疊代次數

輸出參數：Ｂ，Ｈ

１）：初始化矩陣Ｂ，Ｈ為非負數，同時對Ｂ的每一列資料歸一化

２）：for i=1:MAXITER

    ａ：更新Ｈ矩陣一行元素：H(i,j)=H(i,j)*(B'*X)(i,j)/(B'*B*H)(i,j)

    ｂ：更新B的一列元素：B(k,j)=B(k,j)*(X*H')(k,j)/(B*H*H')(k,j);

    c: 重新對B進行列歸一化

3）end

非負矩陣分解的實作代碼

matlab源程式如下：

dim=size(X);                                    %計算x的規格

X=double(X);

B=10*rand(dim(1),r);                            %初始化BH，為非負數

B=B./(ones(dim(1),1)*sum(B));                   %歸一化B的每一列

H=10*rand(r,dim(2));

maxiter=100;                                    %最大疊代次數

for iter=1:maxiter

    H=H.*(B'*(X./(B*H)));

    B=B.*((X./(B*H))*H');

    B=B./(ones(dim(1),1)*sum(B));

end

[matlab中的NMF函數及其使用說明NMFfuction- Mathworks]

[Chih-Jen Lin關于NMF的一些源代碼 NMF工具

MATLAB Scripts download nmf.m.

Python: nmf.py by Anthony Di Franco (numpy needed; see an example.py here).

Go: nmf.go by Dan Kortschak and examples.

C: NMF.c by Dong Li]

[NMF算法簡介及python實作]

[NMF的R實作:bignmf：https://github.com/panlanfeng/bignmf]

[NMF的Julia實作：https://github.com/JuliaStats/NMF.jl]

皮皮blog

非負矩陣分解相關的其它進階主題

[NMF與pLSA的對比《Non-negative Matrix Factorization and Probabilistic Latent Semantic Analysis》]

[除了NMF分解以外，還有一種非負分解也用的比較多，而且很有效，叫做非負張量分解法:http://www.doc88.com/p-8942237517189.html]

[淺析基于張量分解的隐變量模型參數學習]

[Structured PCA帶結構的主成分分析：主成分分析是找到給定資料的結構資訊的主要手段之一，然而對于某些特殊的輸入資料傳統的主成分分析, 并不能真正得到問題的主成分， 這時我們在模組化時就需要考慮到這些特殊的結構。

NMF分解和SSPAC分解在主成分較小的資料上，表現similarity，在主成分較多的資料上，SSPAC表現較好。（Jenatton R, Obozinski G, Bach F R. Structured Sparse Principal Component Analysis[C]//AISTATS. 2010: 366-373）

Structured Variable Selection with Sparsity-Inducing Norms

Structured  Principal Component Analysis.tar.gz ]

from: http://blog.csdn.net/pipisorry/article/details/52098864

ref: [wikipedia: Non-negative matrix factorization]

[1] Daniel D lee and H.SebastianSeung(1999).”Learning the parts of objects by non-negative matrix factorization”. Nature

[2] Daniel D.Leeand H.SebastianSeung(2001). Algorithms for Non negative Matrix Factorization.Advancesin Neural Information

[3] Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401(6755): 788-791.

[4] Bach F, Jenatton R, Obozinski G. Structured sparse principal component analysis[J]. J. Mach. Learn. Res, 366-373.

[5] Jenatton R, Obozinski G, Bach F R. Structured Sparse Principal Component Analysis[C]//AISTATS. 2010: 366-373.

[6] python sklearn http://scikitlearn.org/stable/modules/decomposition.html#pca