流形学习中样本点稀疏问题的研究

论文摘要

随着科技的进步和时代的发展,现代社会已经进入了一个崭新的信息时代,大量的高维数据层出不穷,如图像分类检索、文本聚类和基因序列的建模等,人类必须借助于工具才能有效地识别高维数据的内在特征,其中数据降维技术是解决这种问题的主要方法。对数据进行降维处理的目的是要找出隐藏在高维数据中的低维结构,通常分为线性降维和非线性降维这两类方法。线性降维的方法是,将样本点从高维数据空间通过线性变换投射到一个低维空间,目的是获得一个关于原数据集的内在数据特征的低维表示。线性降维方法有着坚实的理论基础,优点是实现简单、适应性强。但现实中各种有用的数据其特征往往不是简单线性组合。因此,非线性降维方法,即流形学习越来越受到人们的广泛关注。流形学习可以分为两大类:一类是全局方法,是从全局角度出发,让降维时流形上临近的点映射到低维空间时保持临近;另一类是以局部方法,只保证在一个局部范围内将临近点间的关系映射到低维空间。因为局部方法它们只需要考虑流形临近点间的相互关系,不要求流形所对应的低维空间为凸,且计算复杂度较低,因此局部方法有着更广泛的适用对象。局部保持的流形学习算法具有一个共同的特征:找出每个数据点周围的局部性质,并将这些局部性质信息映射到一个低维空间中。显然,局部几何结构信息的保持和恢复程度决定了流形学习算法的优劣。在获取流形的局部信息时,流形学习算法假定流形在一个很小的范围内,局部同胚于一个欧氏空间的一个连通开集,这就决定了流形学习算法在选择邻域时,要尽可能保证邻域内的点满足局部同胚条件。而当样本点较为稀疏时,邻域内的样本点很难保持局部同胚条件,从而导致上述流形学习算法在处理稀疏数据集时会造成较大的误差,甚至失效。本文在流形学习方法的基本概念和理论基础上,针对流形学习无法有效处理稀疏样本集的问题展开了分析和研究。文章总结了流形学习的基本框架和基本步骤,分析了流形学习算法在处理稀疏数据集时的算法效果变差乃至失效现象的原因,并用图示展示了样本点稀疏不同时的邻域块结构。解决稀疏样本集问题的有效方法之一,是增加插值点使得样本点集变得稠密。为此,本文分别提出了线性插值方法和非线性插值方法。我们首先提出找三角形的重心线性插值方法。该方法从样本点和邻域点形成的三角形中找出重心作为插值点,从全局角度来看,插值点的加入使得样本集的稠密程度有了一定的改善,样本点局部邻域的表示更加精确,也使得邻域间有更多的交叠从而使得全局排列的误差更小,因此算法一定程度上改善了样本集稀疏问题,但仍未能改善局部线性逼近的误差,而且新的插值点并没有反应出流形的本质结构和特征。为此,我们提出了基于Matlab四格点样条的非线性的插值方法。即对于稀疏样本点集,我们根据其内部特点,结合流形本身的结构和性质,在利用Matlab四格点样条插值进行曲面重构的基础上非线性的选取一定数目的样本点作为插值点。文章最后通过实验,分别比较和分析了线性插值和非线性插值前后流形学习算法降维效果的变化,并指出与线性插值算法相比,非线性插值方法选取的插值点能有效的减少逼近误差,并能更好的保持和反映流形的本质结构和特征。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 当前国内外研究现状
• 1.3 本文研究的内容
• 1.4 本文的结构
• 第二章 流形学习方法概述
• 2.1 流形和流形学习的概念
• 2.2 线性流形学习算法
• 2.2.1 主成分分析（PCA）
• 2.2.2 线性辨别分析（LDA）
• 2.2.3 多维尺度变换（MDS）
• 2.3 非线性流形学习算法
• 2.3.1 等距映射（ISOMAP）
• 2.3.2 局部线性嵌入算法（LLE）
• 2.3.3 拉普拉斯特征映射算法（LE）
• 2.3.4 海赛局部线性嵌入算法（HLLE）
• 2.3.5 局部切空间排列算法（LTSA）
• 2.4 本章小结
• 第三章 流形学习中样本点稀疏问题的研究
• 3.1 流形学习的基本框架
• 3.1.1 计算邻域
• 3.1.2 求取局部坐标
• 3.1.3 局部坐标的全局排列
• 3.2 流形学习中样本点的稀疏问题
• 3.3 线性插值方法
• 3.3.1 线性插值算法
• 3.4 非线性插值方法
• 3.4.1 流形曲面拟合
• 3.4.2 插值点的选取
• 3.4.3 我们的算法
• 3.4.4 实验效果及分析
• 3.5 本章小结
• 第四章 总结与展望
• 参考文献
• 致谢