NMF 非负矩阵分解 -- 原理与应用

快来打我* 2022-06-10 11:28 199阅读 0赞

[原文地址][Link 1]

# 1.原理 #

发现写关于非负矩阵的博文还是蛮多的，还是以自己的角度总结一下自己的最近看的若干东西以及对非负矩阵分解有用的一些资料链接。NMF，全称为non-negative matrix factorization，中文呢为“非负矩阵分解”。

![NMF][]

NMF的思想：V=WH（W权重矩阵、H特征矩阵、V原矩阵），通过计算从原矩阵提取权重和特征两个不同的矩阵出来。属于一个无监督学习的[算法][Link 2]，其中限制条件就是W和H中的所有元素都要大于0。

写得有点匮竭难懂，看不懂建议去看看原论文，在《NMF引用》一文中有，下面是对于NMF符号偶的定义。

V(F∗N)=W(F∗K)∗H(K∗N)

V : F∗N 的矩阵   
\- F 为特征（行）   
\- N 可以为观察值、例子、特征向量（列）

vn=(v1n,v2n,...,vfn)T,在集合N中第N个特征向量

W:F∗K 的字典矩阵   
\- wfk 为W中的一个系数   
\- wk 是K个元素的基向量

H:K∗N 扩展矩阵   
\- hn 列向量 the columsn vector of activation coeffcients for observation vn   
\- hk 行向量 the row cector of activation coefficients relating to basis vector wk

--------------------

很好奇的就是为什么分解的矩阵式非负的呢，网上流传一种很有利的解释就是非负为了使数据有效，负数对于数据是无效的。这种方法我个人认为有道理，但论文作者实际的解释是：

*  非负性会引发稀疏
 *  非负性会使计算过程进入部分分解

![NMF][NMF 1]

--------------------

回顾一下NMF的历史，其实距离现在已经有35年历史啦！在计算还没有普及的年代NMF已经被发明了。

*  nonnegative rank fatorisation非负排名因子分解 (Jeter and Pye, 1981; Chen, 1984)里面有个华人哦
 *  positive matrix fatorisation 正矩阵因子分解(Paatero and Tapper, 1994)
 *  直到1990年大神Lee(libSVM的作者)和 Seung 发了篇申神论文“[learning the parts of objects][]”，NMF就名声大噪，从那开始划时代的变化就来临啦，NMF被广泛引用到各种领域当中。

--------------------

当然，讲到这里NMF好像很简单，只是对矩阵进行分解。不过仔细想想如果只是简单对矩阵进行分解早就被人提出来引用了，正是因为如何分解矩阵才能更好地对矩阵进行可解析性，也就是如何解NMF矩阵本身就是一个难题。另外还有下面一些问题值得我们一起去探讨的：

### K选择困难症 ###

很多人（其实是我啦）发现对于K的选择无棱两可，但是对于一个适当的K选择在于分解的时候又好重要，其中不同的K对于不同模型情况如下：

*  数据拟合：K越大那么对于数据拟合更好
 *  模型复杂性：一个更小的K模型更简单（易于预测、少输入参数等）

因此一个正确的K选择就像我前一篇文章《NMF实站》里面所说的应该根据数据矩阵V和实际业务去分析，没有一个标准的答案。下面为声频处理时候不同K的表现

![K][]K

### 解不唯一 ###

对于V=WH;W>=0,H>=0，那么任意一个矩阵Q有   
WQ>=0，Q−1H>=0

这就提供了一个可以替换的因子V=WH=(WQ)(Q−1H)，特殊情况下，Q可以为任意非负广义置换矩阵。虽然解不唯一，但是也不用太担心，一般情况下解不唯一仅仅是基向量Wk的缩放和转置，意思就是换来换去还是它自己本身。

### 几何意义 ###

NMF假设数据是由W所产生的一个凸角Cw，对于Cw来说就很郁闷啦，因为可以有很多个不用的wi来决定，因此很难确定到底是哪个Cw。那，怎么解决这个问题呢，学数学的人（我不是哈）就知道应该引入约束式来限制wi的选择。对于怎么选择约束，业界已经出现了很多种方法：

*  稀疏约束：(e.g., Hoyer, 2004; Eggert and Korner, 2004);
 *  形状约束
 *  对hk的空间或时间约束 : activations are smooth (Virtanen, 2007; Jia and Qian, 2009; Essid and Fevotte, 2013)
 *  跨模态对应约束(Seichepine et al., 2013; Liu et al., 2013; Yilmaz etal., 2011)
 *  几何约束: 例如，选择特殊的角点Cw(Klingenberg et al.,   
    2009; Essid, 2012)

![Which cw][]

# 2.应用概述 #

对比了一圈，NMF可以应用的领域很广，源于其对事物的局部特性有很好的解释。在众多应用中，NMF能被用于发现[数据库][Link 3]中的图像特征，便于快速自动识别应用；能够发现文档的语义相关度，用于信息自动索引和提取；能够在DNA阵列分析中识别基因等等。我们将对此作一些大致的描述。但是最有效的就是图像处理领域，是图像处理的数据降维和特征提取的一种有效方法。

## 2.1 特征学习 ##

这一点思想类似（Principal Component Analysis）主成分分析，但是在实际工程环境当中都要比PCA效果要好，其中思想如下：

*  测试数据在NMF算法上学习 Vtrain→dictionaryW
 *  利用W去分解新的测试examples Vn:

vn≈∑n=1Khknwk，其中kn>=0

*  把hn作为example n的特征向量

下面是对人物脸部特征学习的NMF算法，图为把人的脸部的不同特征显示出来：

![NMFFACE][]

## 2.2 图像分析 ##

NMF最成功的一类应用是在图像的分析和处理领域。图像本身包含大量的数据，计算机一般将图像的信息按照矩阵的形式进行存放，针对图像的识别、分析和处理也是在矩阵的基础上进行的。这些特点使得NMF方法能很好地与图像分析处理相结合。人们已经利用NMF算法，对卫星发回的图像进行处理，以自动辨别太空中的垃圾碎片；使用NMF算法对天文望远镜拍摄到的图像进行分析，有助于天文学家识别星体；美国还尝试在机场安装由NMF算法驱动的识别系统，根据事先输入计算机的恐怖分子的特征图像库来自动识别进出机场的可疑恐怖分子。

学术界中：（1）NMF首次被Lee教授用于处理人脸识别。（2）LNMF被宋教授后面提出用于提取人脸子空间，将人脸图像在特征空间上进行投影，得到投影系数作为人脸识别的特征向量，用来进行人脸识别。一定程度上提高了识别率。（3）GNMF被杨教授提出，该算法是基于gamma分布的NMF进行构建特征子空间，采用最小距离分类对ORL人脸库部分图像进行识别。

对于人脸识别，其中以LNMF最为有效突出，比普通的NMF高效且精度高。

## 2.3 话题识别 ##

文本在人类日常接触的信息中占有很大分量，为了更快更精确地从大量的文本数据中取得所需要的信息，针对文本信息处理的研究一直没有停止过。文本数据不光信息量大，而且一般是无结构的。此外，典型的文本数据通常以矩阵的形式被计算机处理，此时的数据矩阵具有高维稀疏的特征，因此，对大规模文本信息进行处理分析的另一个障碍便是如何削减原始数据的维数。NMF算法正是解决这方面难题的一种新手段。NMF在挖掘用户所需数据和进行文本聚类研究中都有着成功的应用例子。由于NMF算法在处理文本数据方面的高效性，著名的商业数据库软件[Oracle][]在其第10版中专门利用NMF算法来进行文本特征的提取和分类。为什么NMF对于文本信息提取得很好呢？原因在于[智能][Link 4]文本处理的核心问题是以一种能捕获语义或相关信息的方式来表示文本，但是传统的常用分析方法仅仅是对词进行统计，而不考虑其他的信息。而NMF不同，它往往能达到表示信息的局部之间相关关系的效果，从而获得更好的处理结果。

话题识别的话跟Probabilistic Latent Semantic Analysis概率隐语义分析相似。

*  首先假设V=\[vfn\]是一个单词-文件的矩阵，vfn是单词mf在文件dn的出现频率；
 *  假设wfk=P(tk)P(mf|tk)和hkn=P(dn|tk)；
 *  那么模型可以变成：
 *  \[P(mf,dn)\]=\[vfn\]=WH

在这里，wk 可以被解释成为与数据hk的主题相关度

![NMP][]

## 2.4 语音处理 ##

语音的自动识别一直是计算机科学家努力的方向，也是未来智能应用实现的基础技术。语音同样包含大量的数据信息，识别语音的过程也是对这些信息处理的过程。NMF算法在这方面也为我们提供了一种新方法，在已有的应用中，NMF算法成功实现了有效的语音特征提取，并且由于NMF算法的快速性，对实现机器的实时[语音识别][Link 5]有着促进意义。也有使用NMF方法进行音乐分析的应用。复调音乐的识别是个很困难的问题，三菱研究所和MIT(麻省理工学院)的科学家合作，利用NMF从演奏中的复调音乐中识别出各个调子，并将它们分别记录下来。实验结果表明，这种采用NMF算法的方法不光简单，而且无须基于知识库。

NMF处理声频产生局部特征数据

![NMF part-based][]

## 2.5 时序分割（temporal segmentation） ##

这里的话思想可以引用隐马尔科夫模型hidden markov models HMM，可以处理时间序列的数据，例如音频视频：

![NMP][NMP 1]

NMF可以通过阈值设置把文件序列数据分割成不同兴趣主题，下面为挖掘电影剪辑结构的一个例子：

![NMP][NMP 2]

同样基于时序分割的想法下有了这样一个语音处理项目，对很多人说的一段话进行语音特征分割，识别出每段话属于哪个人说的：

![NMP][NMP 3]   
![NMP][NMP 4]

## 2.6 聚类 ##

聚类最常用的方法是K-means，俗称K均值算法，NMF算法比K-means算法更优之处因为它是一种软聚类方法（也就是一个元素可以被分为多种类型，不是K-means那种非彼则此），对于有可能重复的聚类方法NMF是简单高效哦。

![NMF][NMF 2]

半年前做姓名聚类的时候一个老外的名字叫 Handsome Yokota, 有时候又写成Hand. Yokota，当大量这种情况出现对于聚类是很不和谐的，用软聚类可以有效过滤这种情况，降低后续数据处理压力。

## 2.7 机器人控制 ##

如何快速准确地让[机器人][Link 6]识别周围的物体对于机器人研究具有重要的意义，因为这是机器人能迅速作出相应反应和动作的基础。机器人通过传感器获得周围环境的图像信息，这些图像信息也是以矩阵的形式存储的。已经有研究人员采用NMF算法实现了机器人对周围对象的快速识别，根据现有的研究资料显示，识别的准确率达到了80%以上。

## 2.8 生物医学工程和化学工程 ##

生物医学和化学研究中，也常常需要借助计算机来分析处理试验的数据，往往一些烦杂的数据会耗费研究人员的过多精力。NMF算法也为这些数据的处理提供了一种新的高效快速的途径。科学家将NMF方法用于处理核医学中的电子发射过程的动态连续图像，有效地从这些动态图像中提取所需要的特征。NMF还可以应用到遗传学和药物发现中。因为NMF的分解不出现负值，因此采用NMF分析基因DNA的分子序列可使分析结果更加可靠。同样，用NMF来选择药物成分还可以获得最有效的且负作用最小的新药物。

## 2.9 滤波和源分离 ##

参考 Independent Component Analysis, ICA 独立成分分析

![NMF][NMF 3]

而滤波当中一篇SIC使用了一个例子，就是使用深度轮廓进行动作识别Action Recognition using depth silhouettes，NMF算法作为特征学习的算法。最后论文使用微软开源的Kinect的骨骼特征、PCA算法、NMF算法进行轮廓特征学习对比，发现NMF的精确率最高91%，而微软开源的骨骼特征识别度只达到78%。

![NMF][NMF 4]

最后不是我在卖弄，确实NMF在简单算法里面效果显著，值得留意，看了很多[机器学习][Link 7]的书，都没有提到该算法，值得mark一下。对于NMF的实现引用例子可以参考我另外一篇文章[《NMF实践》][NMF 5]

[Link 1]: http://blog.csdn.net/qq_26225295/article/details/51211529
[NMF]: /images/20220610/7eb60f32363b4080ac9554fa525181e0.png
[Link 2]: http://lib.csdn.net/base/datastructure
[NMF 1]: /images/20220610/d34d158fbfdd4e16b4e2279c6daec01e.png
[learning the parts of objects]: https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiXlOfXuZ_MAhWCs4MKHUFNCXcQFggdMAA&url=http://www.columbia.edu/~jwp2128/Teaching/W4721/papers/nmf_nature.pdf&usg=AFQjCNHOf7BKOMfBKKs1wJ2SxSwfj7bgaA&sig2=EBdP0_78dVJDv9it1E_0GQ
[K]: /images/20220610/5c1a73a80bb94e5d83d9e9ddf1dc241b.png
[Which cw]: /images/20220610/02c8762d627c4aeaaaaf5338e35062f9.png
[Link 3]: http://lib.csdn.net/base/mysql
[NMFFACE]: /images/20220610/a19d9d1aacf3449a99d2e696a646aff1.png
[Oracle]: http://lib.csdn.net/base/oracle
[Link 4]: http://lib.csdn.net/base/aiplanning
[NMP]: /images/20220610/4b515b0f2bcb4ef2b3e4a662b39ca69e.png
[Link 5]: http://lib.csdn.net/base/vras
[NMF part-based]: /images/20220610/54003f0455f1475a8f24c02191cee2fe.png
[NMP 1]: /images/20220610/7e34874aec6a48e3a63817b43741fbfb.png
[NMP 2]: /images/20220610/2b18ea91ea9b45dfaada5930a585ef6a.png
[NMP 3]: /images/20220610/b3fac453828245f49645b88ec43f7ea6.png
[NMP 4]: /images/20220610/128dd14d1b2f414695fd6b688eee6c50.png
[NMF 2]: /images/20220610/82edae2767864ffcad9050bc6dff5f04.png
[Link 6]: http://lib.csdn.net/base/robot
[NMF 3]: /images/20220610/28a512e0b4444425bbdd63b2b7e6c5ba.png
[NMF 4]: /images/20220610/6395dba79715482bb027e97495f2a0a3.png
[Link 7]: http://lib.csdn.net/base/machinelearning
[NMF 5]: http://blog.csdn.net/qq_26225295/article/details/51165858