关于流形学习若干基础问题与核心算法研究

论文摘要

数据特征提取,或数据降维,是数据建模与数据挖掘的基本问题,而流形学习是近年来所兴起的数据特征提取（特别是低维特征表示）最引人注目的热点方法之一。尽管已提出Isomap, LLE,Laplacian eigenmap等有效的流形学习方法,但其有效性机理、模型选择、对复杂数据的可应用性等基本理论与算法问题仍尚未解决。本学位论文针对流形学习方法的上述基础理论与算法问题进行系统研究,取得了一系列创新成果：（1）针对流形学习方法的模型选择问题,提出了有效的邻域尺寸与本质维自动选择策略。通过构造指数加权的k近邻距离均值表达,提出了近似描述流形数据局部本质维分布的刻画函数；通过定义刻画函数的稳定性度量,导出了流形学习算法邻域尺寸的最优选择策略；进而通过选取本质维分布的稳定值,实现了对数据本质维数的自动设定。所提出的理论与方法简洁、有效,可广泛实用于流形学习算法的参数自动设定。（2）针对流形学习方法的有效性机理与环结构问题,以Isomap方法为切入点证明了“数据流形不存在环结构是流形学习方法有效的充分必要条件”这一重要结论。该结论首次严格阐释了Isomap方法不能有效应用于具环结构复杂数据的本质原因。针对环流形数据降维问题,我们进而发展了有效的流形学习算法。所提出的新算法能够：（a）基于给定数据集判定其中是否存在结构；（b）针对环结构流形数据集生成一系列环形路径以对其环结构进行近似描述；（c）生成数据集的一个近似最大无环子集；（d）基于所生成的近似最大无环子集实现环流形数据集的降维。实验表明：所提出的有关流形学习方法其有效性机理与应用事实完全相符,而且算法能够成功地应用于具有环形结构的数据集降维。（3）针对流形学习的非连通性问题,提出了两类可用于非连通流形数据集非线性降维的高效流形学习算法：通道算法与分解-整合算法。通道算法利用图论工具与微分几何知识,通过搭建非连通流形数据类间的光滑连接通道（由光滑的邻域片组成）,且在连接通道上保持与流形类内一致的本质维结构,形成分布在全数据集上的光滑连通流形形态。相应的流形数据集（包括原数据集与通道数据集）使流形学习方法的有效性得以保证,从而有效地避免了非连通流形学习可能出现的短路、非连通与粗糙连接等问题。分解-整合算法将整个数据集首先按其流形类分解，并对每一子类形数据分别降维,然后利用类间关系对所得降维类分别进行定向与定位,并对其进行整合,从而获得原数据集的降维表示。所提出的新算法均能有效应用于非连通流形数据的降维,其性能均明显优于已有非连通流形学习算法。（4）针对流形学习方法中的数据邻域图构造与测地距离估训问题,提出了一种新的修正邻域图构造思想,并基于此思想发展了测地距离估计的一种更为精确的计算方法。在通常的局部线性假设下（即假设由数据与其近邻凸组合构成的局部邻域片位于本质流形面上）,通过将传统的“点线”邻域图扩充为“点与邻域片”邻域图,从而实现了对流形形态的更精细刻画。基于修正的邻域图,进而提出了在相邻邻域片间优化计算两点间测地距离的思想,并由此建立起了一个更为精确的数据测地距离改进估计方法。实验表明：所提出的新方法计算精度更高,且并未本质增加算法的计算复杂性,可广泛应用于流形学习算法的实际应用中。（5）综合上述研究成果并集成已有流形学习算法,研发了一套流形学习应用系统。该系统具有模型自动选择、数据流形类型检测、不变量特征（主要针对测地距离）精确估计和针对不同类型数据自动选择降维方法等综合功能。系统不仅可直接应用于广泛数据的低维特征提取,也可方便地用作流形学习算法研究和比较的平台。所研发系统的突出特征是功能模块齐全和对用户的弱依赖性,从而方便应用。作为例子,我们对所研发的系统在各种类型的图像数据集上进行了测试,取得了令人满意的效果。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 数据的特征提取与流形学习
• 1.2 典型流形学习方法概述
• 1.2.1 Isomap方法
• 1.2.2 LLE方法
• 1.2.3 Laplacian eigenmap方法
• 1.3 本文主要工作
• 2 关于流形学习模型选择的自动化策略与方法研究
• 2.1 引言:模型选择问题
• 2.2 预备知识
• 2.3 一种新的流形学习模型选择方法
• 2.3.1 流形数据具有一致局部本质维的情形
• 2.3.2 指数加权系数为1或0的情形
• 2.3.3 指数加权系数趋于无穷的情形
• 2.4 数值实验
• 2.4.1 应用到无噪声流形数据集
• 2.4.2 应用到带噪声流形数据集
• 2.5 小结
• 3 关于流形学习算法有效性机理与环流形问题研究
• 3.1 引言:环流形问题
• 3.2 Isomap的有效性问题
• 3.3 环流形数据的数学刻画与Isomap有效性基本定理
• 3.4 流形数据的环结构检测
• 3.5 适用于环流形数据的流形学习算法
• 3.6 数值实验
• 3.6.1 应用到无环流形数据集
• 3.6.2 应用到环流形数据集
• 3.7 小结
• 4 关于流形学习数据集非连通性问题研究（Ⅰ）:通道算法
• 4.1 引言:非连通性问题
• 4.2 解决非连通性问题的策略之一:通道算法
• 4.2.1 Step Ⅰ:寻找流形类边缘
• 4.2.2 Step Ⅱ:建立数据类间过渡通道
• 4.2.3 Step Ⅲ:基于通道的数据降维
• 4.3 数值实验
• 4.3.1 应用到两类流形数据集
• 4.3.2 应用到多类流形数据集
• 4.4 小结
• 5 关于流形学习数据集非连通性问题研究（Ⅱ）:分解-整合算法
• 5.1 引言
• 5.2 解决非连通性问题的又一策略:分解-整合算法
• 5.2.1 分解
• 5.2.2 整合
• 5.2.3 分解-整合算法
• 5.2.4 算法计算复杂度分析
• 5.3 数值实验
• 5.3.1 应用到5类非连通流形数据集
• 5.3.2 应用到具有不同分布密度的多类非连通流形数据集
• 5.3.3 计算效率测试
• 5.4 小结
• 6 关于流形数据邻域图构造与测地距离计算方法研究
• 6.1 引言:数据邻域图构造与数据间测地距离估值问题
• 6.2 基于局部线性假设的修正邻域图构造与新的测地距离计算方法
• 6.3 数值实验
• 6.4 推广到多链情形
• 6.5 小结
• 7 流形学习应用系统
• 7.1 引言
• 7.2 系统主要功能、操作方法及其在图像数据集上的应用
• 7.2.1 针对无环连通流形数据集的系统功能与操作
• 7.2.2 针对环状连通流形数据集的系统功能与操作
• 7.2.3 针对非连通流形数据集的系统功能与操作
• 7.3 小结
• 8 结论与展望
• 8.1 结论
• 8.2 展望
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果