正交非负局部线性嵌入及优化算法研究

摘要

随着科技的不断发展，人们能够接触并获得的数据越来越多，规模越来越大，如互联网信息、气象数据等。这些数据一方面为人类社会和生活带来了极大便利，另一方面又带来了挑战：如何在规模庞大的数据中提取出有用的信息进行处理以反映事物本质特征。数据降维作为一种有效的处理方法应运而生。传统的降维方法如主成分分析、线性判别分析等已经得到了广泛的应用，但是它们提取的特征中含有负元素，而负数在某些实际应用中缺乏合理的解释。因此，约束特征非负的非负矩阵分解方法得到广泛关注，具有广阔的应用前景。
　　非负矩阵分解（NMF）将一个高维非负矩阵 m nV?R?近似分解为两个低维非负矩阵 m rW?R?和r nH?R?的乘积WH，分解后使V与WH之间的距离尽可能的小。W和H的非负约束的直观解释是：整体是由局部组成的，因此 NMF广泛应用于模式识别、数据挖掘和计算机视觉等领域。然而，某些高维数据可能分布于低维的流形表面，最初的NMF没有考虑数据的几何结构信息。为了考虑数据的几何结构信息，研究人员提出基于流形的非负矩阵分解模型及其扩展模型。在前人工作的基础上，本文提出一种新的基于流形的非负矩阵分解模型——正交非负局部线性嵌入（Orthogonal Nonnegative Locally Linear Embedding，ONLLE），并针对ONLLE优化问题提出两个高效优化算法。本文主要工作包括：
　　（1）正交非负局部线性嵌入——ONLLE。ONLLE假设每个样本嵌入在它的若干最近邻中，并且在子空间保持这种近邻关系，使得数据的局部几何结构保持不变。为了学习到基于局部的稀疏表示，ONLLE约束基矩阵是正交的，突出其空间局部特性。为了评估ONLLE的性能，本文在若干人脸数据集上测试了它的人脸识别和图像聚类性能，并与其它典型的NMF模型进行比较。实验结果表明，ONLLE的人脸识别性能和图像聚类性能优于传统的NMF、NPNMF和GNMF算法。
　　（2）Stiefel流形上的快速梯度下降法。乘法法则（MUR）是一种流行的NMF优化算法，但是由于MUR每次更新时沿着调整后的负梯度方向的搜索步长固定为1，导致MUR的收敛速度慢。为了加快ONLLE的收敛速度，本文在Stiefel流形上搜索基矩阵的解，提出ONLLE的Stiefel流形上的MUR算法。为了克服MUR固有的缺陷，本文设计了一种比 MUR更高效的Stiefel流形上的快速梯度下降法（FGD）。实验结果表明，Stiefel流形上的FGD的收敛速度快于Stiefel流形上MUR。
　　（3）有限记忆快速梯度下降法。FGD存在退化为MUR的风险，研究人员提出多步长快速梯度下降法（MFGD），它沿着调整后的负梯度方向使用多变量牛顿法搜索最优步长向量。MFGD存在以下两个缺点：1）高维的稠密Hessian矩阵的存储开销过大，2）算法过程中 Hessian矩阵的求逆运算及其与梯度的乘积运算的时间开销过大。为了克服MFGD的缺陷，本文提出有限记忆FGD算法（L-FGD）。特别地，在MFGD搜索最优步长向量的过程中，本文采取有限记忆BFGS（L-BFGS）算法直接近似Hessian逆矩阵和梯度的乘积。为了评估L-FGD的性能，本文在两个人脸库ORL和PIE、两个文本库Reuters和TDT2测试算法效率和聚类效果。实验结果表明，在聚类效果相当的情况下，L-FGD的收敛速度显著快于MFGD和MUR，且所用存储空间少于MFGD。

目录

封面

声明

目录

中文摘要

英文摘要

主要数学符号列表

英文缩写词对照表

第一章 绪论

1.1 课题研究的背景和意义

1.2 国内外研究现状

1.3 论文主要工作

第二章 非负矩阵分解及其算法

2.1 非负矩阵分解的提出

2.2 非负矩阵分解的乘法法则

2.3 本章小结

第三章 正交非负局部线性嵌入

3.1 几个典型的非负矩阵分解模型

3.2 正交非负局部线性嵌入

3.3 数值实验

3.4 本章小结

第四章 正交非负局部线性嵌入的快速梯度下降法

4.1 快速梯度下降法

4.2 Stiefel流形上的快速梯度下降法

4.3 数值实验

4.4 本章小结

第五章 图正则非负矩阵分解的有限记忆快速梯度下降法

5.1 图正则非负矩阵分解及其乘法法则

5.2 多步长快速梯度下降法

5.3 有限记忆快速梯度下降法

5.4 数值实验

5.5 本章小结

结 束 语

6.1 工作总结

6.2 不足与展望

致谢

参考文献

作者在学期间取得的学术成果