本书从算法框架入手，建立系列非负矩阵分解模型的抽象数学模型，即非负块配准模型，从统一的角度分析现有的非负矩阵分解模型，并用以开发新的非负矩阵分解模型。根据非负块配准模型的分析，本书提出非负判别局部块配准模型，克服了经典非负矩阵分解模型的缺点，提高了非负矩阵分解模型的分类性能。为了克服经典非负矩阵分解的优化算法收敛速度慢的缺点，本书提出在线搜索中利用牛顿法快速搜索步长，提出非负块配准的快速梯度下降算法。为了克服经典非负最小二乘问题的求解算法的缺点，本书利用最优梯度法在无需线搜索的情况下以二阶收敛速度求解非负最小二乘问题，提出非负矩阵分解的高效求解算法。在此基础上提出非负矩阵分解的高效求解算法，并开发非负块配准的最优梯度法。为了克服经典优化算法应用于流数据处理时计算开销过大的缺点，本书提出非负矩阵分解在线优化算法，利用鲁棒随机近似算法更新基矩阵，提出在线算法，提高在线优化算法的鲁棒性。本书结合非负矩阵分解的低秩表示特性和残差矩阵的稀疏特性，指出曼哈顿非负矩阵分解模型可以有效地抑制数据中的噪音和野值，并指出其与低秩和稀疏矩阵分解模型的等价关系。本书提出高效优化算法求解模型，即秩一残差迭代算法和加速梯度下降算法，前者将模型求解问题分解成若干加权中值问题并用快速算法求解，后者将模型求解问题分解成若干非负最小一乘问题并用平滑技术将其目标函数近似为可微函数，然后利用最优梯度法进行求解。

前 言 非负矩阵分解是20世纪90年代末兴起的数据降维方法，经过十几年的发展，已广泛应用于模式识别、数据挖掘和信息检索等领域。非负矩阵分解不同于经典的奇异值分解、正交三角分解和特征值分解等，其主要用于求解非负矩阵非负分解，即将非负矩阵分解成两个非负子矩阵的乘积。由于非负矩阵分解把数据表示成特征的“纯”加性叠加，这种数据表示方法天然地具有稀疏性，与人脑对信号的响应机制相一致，能够有效抑制信号噪声。同时，特征中不含任何负元素，符合真实世界的物理假设。因此，非负矩阵分解广泛应用于文本聚类、邮件监控、盲源信号分离、音频信号分析、人脸识别、图像标注、图像分割、光谱图像分析、基因微阵列数据分析等领域。近年来，非负矩阵分解引起越来越多的关注，中国的浙江大学，美国贝尔试验室、田纳西大学、维克森林大学、佐治亚理工学院，芬兰赫尔辛基大学，日本RIKEN脑科学研究所等研究机构都开展了非负矩阵分解的研究工作。他们的研究成果极大地推动了非负矩阵分解的发展，把非负矩阵分解的应用拓展到互联网、信息安全、遥感图像和数学模型求解等领域。因此，开展非负矩阵分解的研究具有重要的现实意义。 本书从模型的框架入手，建立系列非负矩阵分解模型的抽象数学框架，即非负块配准框架（Non-negative Patch Alignment Framework，NPAF），从统一的视角分析现有的非负矩阵分解模型，并用以开发新的非负矩阵分解模型。根据非负块配准框架分析，本书提出非负判别局部块配准模型（Non-negative Discriminative Locality Alignment，NDLA），弥补了经典非负矩阵分解模型的缺点，提高了非负矩阵分解模型的分类性能。为了弥补经典非负矩阵分解的优化算法收敛速度慢的缺点，本书提出在线搜索中利用牛顿法快速搜索步长，进而提出非负块配准框架的快速梯度下降（Fast Gradient Descent，FGD）算法。为了弥补经典非负最小二乘问题求解算法的缺点，本书利用最优梯度下降算法在无须线搜索的情况下以二阶收敛速度求解非负最小二乘问题，提出非负矩阵分解的高效求解算法，即NeNMF算法。在此基础上提出非负矩阵分解的高效求解算法，并开发非负块配准框架的最优梯度下降算法。为了弥补经典优化算法应用于流数据处理时计算开销过大的缺点，本书提出非负矩阵分解在线优化算法，利用健壮随机近似算法更新基矩阵，提出OR-NMF算法，提高在线优化算法的健壮性。本书的主要创新点包括以下几点。 （1）非负块配准框架。提出基于非负块配准的非负矩阵分解框架——非负块配准框架（NPAF）。自非负矩阵分解提出以后，研究人员提出多种改进模型。例如，利用局部视觉特征近似正交的特点，提出局部非负矩阵分解模型；利用流形学习技术，提出图正则非负矩阵分解模型以保持数据几何结构；利用Fisher判别技术，提出判别非负矩阵分解模型以引入标签信息。然而，这些非负矩阵分解模型是由研究人员根据各自的需求和经验而设计的，内在差异大，难以揭示和比较其模型性能，实际应用中给工程人员选择模型带来困难。本书基于块配准技术，建立非负块配准框架，从统一的角度理解已有非负矩阵分解模型，揭示其内在差异和共同特性，一方面指导工程人员选择模型，另一方面帮助研究人员开发新的非负矩阵分解模型。利用拉格朗日乘子法，提出乘法更新规则算法（Multiplicative Update Rule，MUR）优化非负块配准框架，并用辅助函数技术证明乘法更新规则算法的收敛性。该算法可用于求解非负块配准框架的大多数派生模型。 （2）非负判别局部块配准框架。根据非负块配准框架的分析，提出非负判别局部块配准框架。从非负块配准框架的角度出发，局部非负矩阵可分解为样本和基向量并分别建立由自身组成的样本块，在局部优化过程中保持数据的能量；图正则非负矩阵分解为样本建立由自身和有限最近邻组成的样本块，在局部优化过程中保持数据的几何结构，但是忽略样本判别信息；判别非负矩阵分解为样本和各类中心点建立样本块且样本块分别由所有同类样本和中心点组成，在局部优化过程中保持数据判别信息，但是由全部样本组成的样本块要求数据服从高斯分布。非负判别局部块配准模型弥补了已有非负矩阵分解模型的缺点，为每个样本建立两类样本块：类内块由同类样本中有限最近邻组成，局部优化过程中保持数据局部几何结构，放宽数据高斯分布假设；类间块由不同类样本中有限最近邻组成，局部优化过程中最大化类间边界，从而保持数据判别信息，提高非负矩阵分解的分类效果和健壮性。本书利用全局配准技术把两种局部优化过程映射到全局坐标系进行并把二者结合，套用非负块配准的乘法更新规则算法优化所提非负判别局部块配准模型。数值试验表明，非负判别局部块配准模型的分类效果优于其他非负矩阵分解算法。在有遮挡的情况下，其分类效果优于其他数据降维算法。 （3）非负块配准框架快速梯度下降算法。从梯度下降的角度改进非负块配准乘法更新规则算法，利用牛顿法实现快速线搜索，提出非负块配准快速梯度下降（FGD）算法。快速线搜索沿着调整负梯度方向搜索最优步长，在不超出第一象限边界的情况下更新矩阵因子，大大提高了乘法更新规则的收敛速度。本书证明了快速梯度法的收敛性。为了解决矩阵因子整体的最优步长可能蜕化为1的问题，本书为矩阵因子的列（或行）设置步长，用多变量牛顿法搜索步长向量，提出多步长快速梯度下降（Multi-variables FGD，MFGD）算法，并证明其收敛性。为了解决多变量牛顿法Hessian矩阵求逆开销大的问题，本书提出用伪牛顿法L-BFGS直接近似Hessian矩阵的逆与梯度的乘积，提出有限记忆快速梯度下降（Limited-memory FGD，L-FGD）算法。数值试验表明，FGD算法的收敛速度比乘法更新规则快近5倍，MFGD算法可以解决FGD步长蜕化的问题，L-FGD算法可处理较大规模数据。 （4）非负矩阵分解最优梯度下降算法。通过分析非负矩阵分解优化子问题的性质，利用最优梯度下降算法交替更新矩阵因子，提出非负矩阵分解最优梯度下降算法。非负矩阵分解优化问题是NP-难问题，继乘法更新规则之后出现了非负最小二乘法、投影梯度法、伪牛顿法和Active Set方法等一系列方法。然而，乘法更新规则收敛速度慢且存在零元素问题；非负最小二乘法无法从理论上保证收敛性；投影梯度法的线搜索过程计算开销过高；伪牛顿法在求解过程中计算Hessian矩阵的逆，计算开销大且存在数值不稳定问题；Active Set方法在矩阵不满秩时会出现数值问题。因此，非负矩阵分解的高效优化问题仍然是个开放性问题。本书将非负矩阵分解优化问题看成两个子问题，从数学上证明了每个子问题都是凸问题且其梯度是Lipschitz连续的，从而利用最优梯度下降算法以 的收敛速度求解每个子问题，提出非负矩阵分解高效优化算法，即NeNMF算法，弥补了经典非负矩阵分解优化算法的缺点。通过分析非负块配准框架优化问题的子问题的性质，本书成功地将NeNMF算法用于优化非负块配准框架，提出非负块配准框架的最优梯度下降算法。数值试验表明，NeNMF算法的收敛速度快于其他非负矩阵分解优化算法；基于NeNMF的非负块配准框架优化算法也快于常用的乘法更新规则算法等非负块配准框架优化算法。 （5）非负矩阵分解在线优化算法。提出非负矩阵分解在线优化（OR-NMF）算法，利用健壮随机近似算法以在线的方式更新基矩阵。非负矩阵分解在线优化算法的空间复杂度与样本维数和样本规模成正比，由于计算机内存容量的限制，难以满足流数据处理的需求。此外，新样本到达时，经典非负矩阵分解算法需要“重新启动”以更新分解结果，导致时间开销不断增加。因此，研究人员提出在线非负矩阵分解算法，利用新到达的样本更新分解结果，弥补经典非负矩阵分解算法时间复杂度高和空间复杂度高两方面的缺限。然而，已有的在线非负矩阵分解算法的收敛速度受噪声、矩阵不满秩等因素影响，存在数值不稳定的问题。本书提出在新样本到达时利用健壮随机近似算法以 的收敛速度更新基矩阵，提高在线非负矩阵分解的健壮性。利用准鞅理论，本书证明了所介绍算法的收敛性。为了弥补空间复杂度过高的缺点，本书提出用缓冲池技术存储有限的历史样本，用新样本替换缓冲池中的旧样本以保证基矩阵引入最新的样本统计信息。图像标注试验表明，OR-NMF算法可以更好地提取图像语义空间信息。

目 录 第1章 绪论 001 1.1 本书研究背景及意义 001 1.2 国内外研究现状 006 1.2.1 非负矩阵分解发展历史 006 1.2.2 国内外研究机构 008 1.2.3 非负数据降维研究现状 009 1.3 本书主要工作 012 1.4 本书组织结构 014 第2章 非负矩阵分解基础 016 2.1　非负矩阵分解模型 016 2.1.1　相似性度量 017 2.1.2　先验信息 024 2.1.3　扩展模型 032 2.2 非负矩阵分解理论问题 035 2.2.1 数据表示特性 035 2.2.2 维数选择 036 2.2.3 非负矩阵分解与聚类分析算法的等价关系 038 2.3　优化算法 040 2.3.1　初始化方法 040 2.3.2　不精确块迭代方法 041 2.3.3 精确块迭代方法 045 2.3.4　随机规划方法 048 2.3.5 多层分解方法 048 2.3.6 在线优化算法 049 2.3.7　并行与分布式算法 050 2.4 应用领域 052 2.4.1 数据挖掘 052 2.4.2 模式识别 054 2.5 本章小结与讨论 055 第3章 非负块配准框架 057 3.1 引言 057 3.1.1 局部优化 060 3.1.2　全局配准 060 3.2 非负块配准框架 061 3.2.1 基于KL距离的NPAF 063 3.2.2 基于欧几里得距离的NPAF 070 3.2.3 计算复杂性分析 076 3.2.4 非负数据降维算法框架比较 076 3.3 非负数据降维算法的分析 077 3.3.1 非负矩阵分解 078 3.3.2 局部非负矩阵分解 078 3.3.3 判别非负矩阵分解 080 3.3.4 图罚分非负矩阵分解 081 3.4 非负块配准框架派生模型实例 082 3.4.1 非负PCA模型 082 3.4.2 非负LLE模型 083 3.4.3 非负LTSA模型 084 3.5 本章小结与讨论 085 第4章 非负判别局部块配准模型 087 4.1 引言 087 4.2 模型定义 089 4.2.1 数学描述 090 4.2.2 两类NDLA模型 092 4.2.3 流形学习角度的解释 093 4.3 改进NDLA模型 094 4.4 模型求解算法 095 4.4.1 乘法更新规则 095 4.4.2 计算复杂性 098 4.5 试验结果 098 4.5.1 人脸识别 098 4.5.2 手写体识别 103 4.5.3 局部特征提取 105 4.5.4 结果分析 107 4.6 本章小结与讨论 109 第5章 非负块配准框架快速梯度下降算法 111 5.1　引言 111 5.2　改进乘法更新规则 113 5.3　快速梯度下降算法 118 5.3.1　单步长快速线搜索 119 5.3.2　多步长快速线搜索 122 5.3.3　平衡多步长快速线搜索 128 5.4　基于欧几里得距离的NPAF优化 131 5.4.1　NPAFE快速梯度下降算法 131 5.4.2　NPAFE投影梯度下降算法 137 5.4.3　计算复杂性分析 138 5.5　非负块配准框架派生模型优化 139 5.6　数值试验 139 5.6.1　单步长快速梯度下降算法 140 5.6.2　多步长快速梯度下降算法 143 5.7　本章小结与讨论 146 第6章 非负矩阵分解最优梯度下降算法 147 6.1 引言 147 6.1.1 非负矩阵分解优化算法研究现状 150 6.1.2　最优梯度下降算法 154 6.2 非负矩阵分解最优梯度下降算法 155 6.2.1　非负最小二乘优化算法 156 6.2.2 非负矩阵分解优化算法 164 6.2.3　扩展模型优化算法 166 6.3 非负块配准最优梯度下降算法 168 6.3.1 派生模型优化算法 171 6.4 试验结果 172 6.4.1 非负矩阵分解优化 172 6.4.2 图正则非负矩阵分解优化 182 6.5 本章小结与讨论 183 第7章 非负矩阵分解在线优化算法 185 7.1 引言 185 7.1.1 在线非负矩阵分解研究现状 186 7.1.2 INMF-VC算法 189 7.1.3 OMF-DA算法 190 7.1.4 鲁棒随机近似算法 191 7.2 基于RSA的在线非负矩阵分解算法 193 7.2.1 缓冲池策略 197 7.2.2 计算复杂性 199 7.2.3 收敛性分析 199 7.3 非负矩阵分解扩展模型的在线优化 203 7.3.1 滑动窗口更新扩展 204 7.3.2 距离度量扩展 204 7.3.3 稀疏约束扩展 205 7.3.4 平滑约束扩展 206 7.3.5 盒约束扩展 206 7.4 数值试验 207 7.4.1 在线非负矩阵分解效率比较 208 7.4.2 人脸识别 215 7.5 本章小结与讨论 217 第8章 非负矩阵分解典型应用实例 218 8.1　引言 218 8.2　模式识别 219 8.2.1　人脸识别 220 8.3　数据挖掘 229 8.3.1　文本聚类 230 8.4　信息检索 234 8.4.1　图像标注 234 8.5　本章小结与讨论 240 附录A 辅助函数技术 242 A.1 辅助函数的定义 242 A.2 辅助函数应用 242 附录B 一阶优化方法与收敛速度 244 B.1 收敛速度的定义 244 B.2 一阶优化方法假设 245 B.3 一阶优化方法的最优收敛速度 245 参考文献 246 后记 277