1.2　国内外研究现状

1.2.1　非负矩阵分解发展历史

非负矩阵分解[31]最早发表在1999年的Nature杂志上，Lee和Seung[35]给出了一个简单、实用且高效的乘法更新规则算法，非负矩阵分解迅速引起研究人员的广泛关注。如图1.1所示，有关非负矩阵分解的最初两篇文章的ISI[1]引用次数呈逐年增长趋势。2001年，Li等人[32]为了提高非负矩阵分解的局部特征提取能力，改进非负矩阵分解算法。2004年，Donoho和Stoddenp[36]讨论了非负矩阵分解算法提取局部特征的问题，指出仅考虑数据的非负性质和矩阵因子的非负约束不能保证提取局部特征。因此，非负矩阵分解算法在某些数据集上得到的数据表示不一定是稀疏的。Hoyer[37]分析了这一问题，结合稀疏编码的研究成果，提出显式地约束表示系数的稀疏性。

从数据及其误差分布的角度看，非负矩阵分解虽然不像传统数据降维算法那样假设数据的分布结构，但是它通常假设数据及其误差的分布性质。假设数据服从泊松分布，得出用Kullback-Leiblur散度度量近似误差的非负矩阵分解算法[31]；假设数据中的误差服从高斯分布，得出用欧几里得距离度量近似误差的非负矩阵分解算法[38]。最近，Févotte等人[39]假设数据中含有γ分布的乘性误差，得出用Itakura-Saito距离度量近似误差的非负矩阵分解算法；Cichocki等人[40,41]使用带参数的和距离度量数据与其重构数据的分布之间的距离，提出相应的非负矩阵分解算法。

从数据非负特性的角度看，非负矩阵分解得到的非负低维空间坐标可以认为是数据在低维空间各个方向（基向量对应的坐标轴）上出现的概率，因此若视所得到的非负基向量为聚类中心，则非负矩阵分解具有天然的聚类能力。事实上，Lee和Seung[31]从最开始就用文本聚类评估非负矩阵分解算法的有效性。Ding等人[42,43]在这方面做了大量的工作，他们证明了非负矩阵分解扩展算法与若干聚类算法等价，揭示了数据非负特性带来的聚类优势。经过多年的发展，非负矩阵分解已经在文本聚类等领域得到广泛而成功的应用。

从计算复杂性的角度看，Vavasis[44]证明非负矩阵分解是NP-难题，所以只存在近似算法。非负矩阵分解最典型的近似算法是乘法更新规则算法[38]，Lin[45]提出投影梯度法，最近Kim等人[46]又提出Block Principal Pivoting（BPP）算法。虽然非负矩阵分解本身不是凸问题，但是其每个子问题是凸问题，可把凸优化领域的研究成果用于非负矩阵分解。因此，非负矩阵分解的优化算法研究仍然是十分活跃的领域。最近，随机规划方法[47,48]和并行算法[49]被用于非负矩阵分解问题。面向流数据处理应用，还发展出在线非负矩阵分解算法[49-51]。

经过多年的研究，非负矩阵分解已成功应用于模式识别、信息检索、在线监控、图像处理、盲信号处理、生物与医学数据分析和谱数据分析等领域。从非负数据降维的角度看，Zafeiriou等人[33]在非负低维空间寻找最优化Fisher判别信息，提出判别非负矩阵分解（Discriminative NMF，DNMF）。然而，无论是非负矩阵分解还是判别非负矩阵分解，它们都属于线性降维算法的范畴，因此在非线性数据上的应用效果不理想。2008年，Cai等人[52,34]假设数据分布于流形上，考虑数据的非负特性，提出非线性非负数据降维算法，并将其成功应用于图像聚类应用中，引起了学术界的高度关注。经过近几年的飞速发展，非线性非负数据降维算法在理论和应用上都取得了一定成果，但是非负数据降维算法的研究目前仍然处于起步阶段，还有很多理论和应用问题亟待解决。

1.2.2　国内外研究机构

非负矩阵分解提出十多年来，已经取得了丰富的研究成果，它的应用已经拓展到信息数据处理的大多数领域，引起了国内外多家研究机构的高度关注。很多研究机构都取得了重要的研究成果，本书无法一一列举，只介绍较有代表性的研究机构所取得的成果。

国内方面，微软亚洲研究院是最早开展非负矩阵分解的研究机构，他们开展了非负矩阵分解基于局部的特征提取方面研究，并将研究成果应用于人脸识别等领域；浙江大学开展了非负矩阵分解在高光谱图像分析中的应用研究，进行了非线性非负数据降维方面的有益探索。

国外方面，美国贝尔试验室和美国剑桥大学最早开展非负矩阵分解的研究，他们主要是从认知科学的角度，分析数据非负特性在机器学习中的生理学和心理学依据；美国斯坦福大学开展了有关非负矩阵分解基于局部的数据表示的重要探索；美国田纳西大学阿灵顿分校最早开展非负矩阵分解聚类特性的理论研究，取得了丰硕的研究成果，奠定了非负矩阵分解在聚类领域的应用基础；美国佐治亚理工学院、田纳西大学奥斯汀分校在非负矩阵分解高效优化算法方面开展了研究工作；美国维克森林大学、韩国浦项理工大学开展了非负矩阵分解在医学图像分析中的应用研究；法国巴黎电信研究所开展非负矩阵分解在语音分析和音乐分析中的应用研究；日本RIKEN脑科学研究所在非负矩阵分解应用于信号处理方面做出了重要贡献，开发了NMFLAB软件包。

1.2.3　非负数据降维研究现状

非负矩阵分解[31]（NMF）是典型的非负数据降维算法，然而测试表明它在有些数据集上无法提取局部特征，失去了非负数据降维算法的优势。为了弥补这一缺点，Li等人[32]提出局部非负矩阵分解算法（LNMF），LNMF在最小化近似误差的同时在降维过程中引入三种先验知识：（1）受人脸中局部特征分布在不同位置的启发，引入基向量尽可能地正交的先验；（2）由于非负基向量的正交意味着同一维度只允许出现一个非零元素，可能产生无效的解，所以在基归一化的条件下最小化基向量的L2范数，使基向量保持尽可能多的非零元；（3）最大化表示系数的Tikhonov罚分项以尽可能多地保持能量。通过引入三种先验，LNMF在大多数数据集上都能得到基于局部的数据表示，充分利用数据的非负特性。然而，LNMF要求基向量归一化，导致近似误差过大，在某些应用中对后续处理影响较大。另一方面，与NMF类似，LNMF也属于线性算法，在非线性分布的数据中往往不能得到理想的降维效果。Cai等人[34]结合利用数据非负特性和基于流形的非线性结构，提出图正则非负矩阵分解（GNMF），GNMF在最小化近似误差的同时最小化样本与其有限最近邻之间的距离，从而在低维空间保持数据的几何结构。GNMF规避了数据线性分布的假设，通过基于流形的方法挖掘数据非线性结构，解混潜在控制变量之间的关系，属于非线性非负数据降维算法。按照样本标签分，GNMF与NMF、LNMF一样，都属于无监督非负数据降维算法。由于它们没有利用样本标签信息，可能导致所得到低维空间区分性较差，在分类应用中效果不理想。Zafeiriou等人[33]结合Fisher判别信息和数据的非负特性，提出判别非负矩阵分解算法（DNMF）。DNMF在最小化近似误差的同时最小化类内散度、最大化类间散度，使数据在低维空间具有较强的区分性。然而，DNMF假设数据服从高斯分布，即数据采集是由相互独立的潜在变量控制的，属于线性降维算法。高斯分布假设的限制过于强，导致DNMF在不服从高斯分布的非线性数据中效果较差。根据上述分析，非负数据降维算法的研究存在许多挑战，现有非负数据降维算法亟待进一步深入研究，以发展出更加健壮、稳定的非负数据降维算法。

1.2.3.1　非负数据降维算法面临的挑战

虽然非负数据降维算法研究已经取得了一些成果，但是还有很多问题未能彻底解决：

（1）算法框架问题。非负数据降维算法各自存在不同的假设，限制条件各不相同。如果不能放宽这些条件，这些算法只能用于各自的领域，无法得到推广。这是因为它们是研究人员根据自身需要和经验设计的，既不能用于大多数情况，也无法分析它们相互之间的差异。算法框架从统一的角度分析各算法的数学模型，看清算法的本质差异和内在联系。如果能开发非负数据降维算法的理论框架，在框架的层面上对非负数据降维算法展开研究，那么研究成果能够很容易地推广到各应用领域。因此，本文主要讨论非负数据降维算法的算法框架问题。

（2）维数选择问题。与传统数据降维算法一致，非负数据降维算法也需要预先设定低维空间维数。在某些基于谱分解的传统数据降维算法（如PCA）中，维数按照信号能量排序，研究人员通常可以按照能量高低依次抽取指定维数的向量。然而，在非负数据降维算法中，低维空间的维数是自由参数，无法用传统的方式确定。研究人员通常用交叉验证法选择合适的维数，Owen和Perry[53]提出二维交叉验证法，Kanagal等人[54]发展了Owen方法，但是这些方法的计算开销巨大，未能很好地解决维数选择问题。

（3）邻域选择问题。在某些基于流形学习的非负数据降维算法（如GNMF）中，构建邻接图时选择多少最近邻组成邻域是具有挑战性的问题。在流形学习领域，这个问题尚未得到解决。通常的做法是依靠经验或用交叉验证法设置邻域样本数量。

（4）高效优化问题。近年来，非负矩阵分解优化算法得到很大发展，但是这些算法推广到非负数据降维模型优化还有很多问题需要研究。目前，非负数据降维模型优化主要采用乘法更新规则算法，收敛速度慢，限制了非负数据降维算法的应用领域。因此，非负数据降维的高效优化算法是亟待解决的问题。本书在框架的层面上开展高效优化算法的研究，研究成果可推广到各种非负数据降维模型优化中。

1.2.3.2　非负数据降维算法框架研究现状

经过近几年的发展，研究人员指出有两类非负矩阵分解算法可视为非负数据降维算法框架：非负图嵌入模型NGE[55]（Non-negative Graph Embedding）和图正则非负矩阵分解模型GNMF[56]。

NGE模型在样本集上构建两个邻接图，即内蕴图（Intrinsic Graph）和罚分图（Plenty Graph）表示数据的统计特性，通过优化基于图拉普拉斯的目标函数在低维空间揭示数据非线性分布结构。NGE模型存在以下问题：

（1）NGE模型认为各算法的区别在于内蕴图和罚分图的设计及其嵌入方式 [25]。因此，NGE模型构建邻接图编码嵌入在非线性流形上的样本的空间位置关系，难以显式地刻画非线性非负数据降维的“全局非线性”性质。

（2）NGE模型把低维空间强制分解成两个子空间，分别在两个子空间优化内蕴图和罚分图上所设计的目标函数。然后，把两个子空间的基向量和坐标排列分别组成低维空间的基向量和坐标。这种方法得到的低维空间一部分坐标轴只包含内蕴图上提取的非线性结构信息，另一部分坐标只包含罚分图上提取的非线性结构信息，因此在低维空间分布不均匀。

（3）NGE模型用乘法更新规则算法求解，且每次迭代包含一个矩阵求逆运算，因此时间开销过大。

GNMF模型结合非负矩阵分解和图拉普拉斯技术，通过构建邻接图在低维空间保持数据统计特性。样本标签信息[57,58]可用于构建各种邻接图，将GNMF拓展成监督非负数据降维算法。GNMF模型存在以下问题：

（1）GNMF模型从图拉普拉斯的角度得到非负数据降维算法，并没有显式地给出理论框架。

（2）因为GNMF没有定义理论框架，所以其难以分析现有非负数据降维算法，更难以帮助设计新的算法。

（3）GNMF[56]的乘法更新规则用于优化基于图拉普拉斯的非负数据降维算法模型，收敛速度慢，且难以应用到其他非负数据降维模型优化。