论文摘要
随着各种数据采集设备的出现,大量高维的原始数据在预处理后才能被用于后续的各种操作,如聚类、分类、野值检测等。维数约简是数据预处理的步骤之一。其目的是在减少数据维数的同时,尽量减少或去除次要的冗余信息,并且保留或增强有意义的信息。因为现实世界中的数据多是非线性的,利用线性降维技术（如主成分分析,PCA）在映射到低维空间时,并不能保持高维空间的几何结构和关系。流形学习是一类新近出现的非线性维数约简算法,认为很多数据集是伪高维的,有时包含上千特征的数据点可以描述为几个潜在参数的函数。换句话说,数据点实际上采样于嵌入到高维空间里的低维流形。流形学习算法试图确定这些参数,并发现数据的低维表示。对流形学习问题的研究有着非常重要的实际意义,在模式分析、数据挖掘、图像处理等领域都有着广泛的应用。流形学习在分类和聚类方面的研究尚在初始阶段,有很多问题尚待解决。本论文研究几种代表性的流形学习算法,尤其是等距特征映射算法。分析了各种流形学习算法的优缺点,并对流形学习若干关键问题进入了深入分析和改进,侧重于流形学习中的距离度量、固有维数、核化等几个关键问题。本文的主要内容包括:（1）谱图理论是流形学习的基础,本文根据谱图理论,充分考虑数据的局部结构,提出了一种基于近邻自适应尺度的改进谱聚类算法。其基本思想是根据数据点的近邻分布,对每个点设置一个近邻自适应尺度,代替标准谱聚类算法中的全局统一尺度。近邻自适应尺度简化了参数的选取,使得新算法对密度的变化不敏感,对离群点有一定的鲁棒性,同时比标准谱聚类更适合任意形状的数据分布。然后,将改进的谱聚类算法成功地应用到颜色量化中。（2）如何自动确定高维数据的固有维数,是流形学习难点之一。极大似然估计（MLE）是一种新近出现的维数估计方法,实现简单,选择合适的近邻能取得不错的结果。但当近邻数过小或过大时,均有比较明显的偏差。其根本原因是没有考虑每个点对固有维数的贡献是不同的。本文充分考虑了数据集的分布信息,提出了一种自适应极大似然估计（AMLE）。实验证明,无论在模拟数据集还是真实数据集上,AMLE较MLE在估计准确度上均有很大的提高。对近邻数的变化也不甚敏感。（3）等距特征映射（Isomap）是一种有代表性的流形学习算法,该算法高效、简单,但计算复杂度较高。基于界标点的L-Isomap减少了计算复杂度,但对于界标点的选取,大都采用随机的方法,致使该算法不稳定。本文考虑到样本点和近邻点相对位置,将对嵌入流形影响较大的样本点赋予较高的权重。然后根据权重大小选择界标点,同时考虑界标点之间的相对位置,使得选出的界标点不会出现过度集中的现象,近似直线分布的概率也大大降低,从而保证了算法的稳定性。实验结果表明,该算法在界标点数量较少的情况下,比L-Isomap稳定,且对缺失数据的不完整流形,也能获取和Isomap相差不大的结果。（4）高维数据中最常见的是图像数据,如何度量图像数据之间的距离是一项有挑战性的工作。本文提出一种基于图像距离的等距特征映射:IMD-Isomap。因为图像距离考虑了图像的空间分布信息,实验结果表明IMD-Isomap比Isomap的可视化效果更好,尤其在添加噪声的情况下。然后,结合泛化回归神经网络,设计出一种分类器。结果表明,该分类器对噪声表现出一定的鲁棒性,均比KNN、Isomap或Eigenface的分类效果好。（5）Isomap是无监督的学习算法,本身不具备样本外测试能力,因而不能直接用于分类。核Isomap是Isomap的改进,利用核技巧获得了泛化特性。将类别标记信息集成到距离中,得到了加权距离。该距离使得同类点问的距离更近,不同类点间的距离更远,更利于分类任务。本文提出一种基于加权距离的核Isomap,称作WKIsomap。实验结果表明,无论用于数据的可视化还是分类,WKIsomap都比Isomap或KIsomap更鲁棒。