非負矩陣分解（NMF）及一個小實例

04-21

最近在做一道題，題目的要求如下圖，其中如2-digits這張圖，圖中每兩個數字構成一個子圖（橫著看，比如第一行為41,43,42,14,12,14,23,41），對應的右圖為左圖的一個主成分元素，即2-digits這張圖中的每個單一的數字都是一個主成分，要求利用主成分分析等方法將圖中的數字一一分離出來，如左圖所示。可以看出左圖是由右圖的一個組合構成的，在實際操作中，我是採用非負矩陣分解的方式來嘗試解這道題。

什麼是非負矩陣分解（Non-negative Matrix Factorization）

NMF的基本思想可以簡單描述為：對於任意給定的一個非負矩陣V，NMF演算法能夠尋找到一個非負矩陣W和一個非負矩陣H，使得滿足，從而將一個非負的矩陣分解為左右兩個非負矩陣的乘積。如下圖所示，其中要求分解後的矩陣H和W都必須是非負矩陣。

矩陣V分解為左矩陣W和右矩陣H，可理解為原始矩陣V的列向量是H中的所有列向量的加權和，對應的權重係數則是W的列向量的元素，所有H稱為基矩陣，W稱為係數矩陣。

NMF在人臉識別的應用中和PCA還有VQ分解不同。VQ分解是用一張完整的圖像直接代表源臉部圖像；PCA是將幾個完整人臉加減壓成一張臉；而NMF是取甲的眼睛，乙的鼻子，丙的嘴巴直接拼成一張臉，也就是說NMF分解後的基矩陣H是每張人臉的一個特徵部分，例如眼睛，鼻子，嘴巴等，然後權重矩陣對這些特徵進行加權處理從而得到一張完整的人臉。如下圖所示3種矩陣分解方式的區別。

對於非負矩陣分解的一些更為詳細的介紹可以參考這篇博客：非負矩陣分解NMF - 皮皮blog - 博客頻道 - CSDN.NET

以及原始論文：Algorithms for Non-negative Matrix Factorization - Daniel D.Lee、H. Sebastian Seung

具體演算法流程

非負矩陣分解中，代碼採用的是原始論文中提及的基於乘法更新發展的迭代更新演算法，其將矩陣分解演算法轉化為如下的優化問題，即最小化兩個矩陣之間的歐幾里得距離的優化問題：

$min|V - V |^2 = sum_{ij}(V_{ij}-V_{ij})^2$

其中 $V$ 為原始矩陣， $V$ 為分解後的矩陣重構而成的矩陣，即 $V=H*W$ ，乘法更新規則如下：

H矩陣的更新： $H_{amu}leftarrow H_{amu} frac{(W^TV)_{amu}}{(W^TWH)_{amu}} ... (1)$ ，其中 $amu$ 是指矩陣的第 $a$ 行第 $mu$ 列元素，當 $(W^TWH)_{amu}$ =0時，對應位置元素不做更新。

W矩陣的更新： $W_{ia}leftarrow W_{ia} frac{(VH^T)_{ia}}{(WHH^T)_{ia}} ... (2)$ ，其中 $ia$ 是指矩陣的第 $i$ 行第 $a$ 列元素，當 $(WHH^T)_{ia}$ =0時，對應位置元素不做更新。

綜上，針對博文開頭的題目，我們要分出8個主特徵，即r=8,。原始圖像中的每兩個數字構成一個子圖，由64*64個像素組成，共有64個子圖，每個子圖被張成一個4096（64^2）的向量，因此V矩陣為4096*64維的矩陣。

因此演算法流程為：

1、隨機初始化一個4096行8列的矩陣H和一個8行64列的矩陣W，設定誤差閾值 $epsilon$ 和迭代輪數 $iternum$

2、按照上述的乘法更新規則更新（即(1)和(2)式）W和H矩陣，迭代進行第二步
3、輸出H矩陣，H矩陣的每一列即為一個特徵，即對應的一個數字。將每一列重新展開為一個64*64的矩陣，轉置後繪製出來，可看到對應的8個數字，得到結果如下圖（1000輪迭代，大約9秒完成）。可看出非負矩陣分解可以很好地將原圖中的特徵提取出來。

代碼

源代碼地址：undersunshine/machine_learning_algorithms

其中data.csv是經過預處理的圖片，具體看代碼注釋，你也可以嘗試使用data1.csv，此時需要將代碼中的image_shape改成(128,128)

請用Python3.x運行代碼，代碼庫要求：pandas， numpy， matplotlib