NMF（非负矩阵分解）算法

NMF，非负矩阵分解，它的目标很明确，就是将大矩阵分解成两个小矩阵，使得这两个小矩阵相乘后能够还原到大矩阵。而非负表示分解的矩阵都不包含负值。

信息时代使得人类面临分析或处理各种大规模数据信息的要求，如卫星传回的大量图像、机器人接受到的实时视频流、数据库中的大规模文本、Web上的海量信息等。处理这类信息时，矩阵是人们最常用的数学表达方式，比如一幅图像就恰好与一个矩阵对应，矩阵中的每个位置存放着图像中一个像素的空间位置和色彩信息。由于实际问题中这样的矩阵很庞大，其中存放的信息分布往往不均匀，因此直接处理这样的矩阵效率低下，这对很多实际问题而言就失去了实用意义。为高效处理这些通过矩阵存放的数据，一个关键的必要步骤便是对矩阵进行分解操作。通过矩阵分解，一方面将描述问题的矩阵的维数进行削减，另一方面也可以对大量的数据进行压缩和概括。

在科学文献中，讨论利用矩阵分解来解决实际问题的分析方法很多，如PCA(主成分分析)、ICA(独立成分分析)、SVD(奇异值分解)、VQ(矢量量化)等。在所有这些方法中，原始的大矩阵V被近似分解为低秩的V=WH形式。这些方法的共同特点是，因子W和H中的元素可为正或负，即使输入的初始矩阵元素是全正的，传统的秩削减算法也不能保证原始数据的非负性。在数学上，从计算的观点看，分解结果中存在负值是正确的，但负值元素在实际问题中往往是没有意义的。例如图像数据中不可能有负值的像素点；在文档统计中，负值也是无法解释的。因此，探索矩阵的非负分解方法一直是很有意义的研究问题，正是如此，Lee和Seung两位科学家的NMF方法才得到人们的如此关注。

NMF通过寻找低秩，非负分解那些都为非负值的矩阵。这在现实的应用中有很多例子，如数字图像中的像素一般为非负数，文本分析中的单词统计也总是非负数，股票价格也总是正数等等。研究指出，非负矩阵分解是个NP问题，可以划为优化问题用迭代方法交替求解U和V。NMF算法提供了基于简单迭代的求解U，V的方法，求解方法具有收敛速度快、左右非负矩阵存储空间小的特点，它能将高维的数据矩阵降维处理，适合处理大规模数据。

参考文献：

《非负矩阵分解：数学的奇妙力量》

http://blog.sciencenet.cn/blog-248606-466811.html

(介绍NMF的基本内容及其应用)

《NMF算法简介及python实现》

http://blog.csdn.net/inte_sleeper/article/details/7294003

(以自动推荐为例，介绍NMF应用，对参数求解给出简单的迭代方法)

《Non-negative Matrix Factorization and Probabilistic Latent Semantic Analysis》

http://ezcodesample.com/plsaidiots/NMFPLSA.html

(NMF与pLSA的对比)

NMF工具

http://www.csie.ntu.edu.tw/~cjlin/nmf/

(作者 Chih-Jen Lin，也是libSVM的作者)