基于Isomap的流形结构重建方法.docVIP

基于Isomap的流形结构重建方法( 孟德宇 徐晨 徐宗本(( （西安交通大学信息与系统科学研究所，西安，710049） 摘要 流形学习研究是目前模式识别与数据挖掘领域的研究热点之一，然而，已有的流形学习方法仅能建立点对点的降维嵌入，而未建立高维数据流形空间与低维表示空间之间的相互映射。此缺陷已限制了流形学习方法在诸多数据挖掘问题中的进一步应用。针对这一问题，本文提出了两种新型高效的流形结构重建算法：快速算法与稳健算法。其均以经典的Isomap方法内在运行机理为出发点，进而推导出高维流形空间与低维表示空间之间双向的显式映射函数关系，基于此函数即可实现流形映射的有效重建。理论分析与实验结果证明，所提算法在计算速度、噪音敏感性、映射表现等方面相对已有方法具有明显优势。 关键词 数据降维 流形学习 等距特征映射 模式分类 特征描述 近年来，在数据挖掘、人工智能及信息获取等研究领域中，常常需要处理具有高维描述特征的数据。数据的高维特性往往给应用中的数据处理过程带来计算效率低下、维数灾难等问题。从本质上说，实际中高维数据的属性特征之间常存在一定的规律性和相关性，即实际数据经常存在外在（存储的高维数）与内在（本质的低维数）两个维数。若能获得高维数据的本质低维表示，则一方面由于后者的本质性，可对其进行等效处理从而高效挖掘出前者中蕴涵的信息，另一方面由于后者的简单性，可在一定程度上解决高维特征给数据带来的诸多问题(如维数灾难)。因此，寻找高维数据的本质低维结构，即数据降维问题，是极为重要的非监督学习问题之一。 传统的降维方法包括主成分分析(Principle Component Analysis, PCA[1])与高维尺度分析(Multidimensional Scaling, MDS[2])等方法。当数据位于高维空间中一个低维线性超平面上时，此类方法能够有效对其实行降维。然而，它们不能对具有低维非线性分布结构的高维数据进行有效降维处理，这大大限制了它们的应用范围。近年来，出现了一类新型的非线性降维方法，流形学习降维方法，典型的此类方法包括等距特征映射(Isometric Mapping，Isomap[3])，局部线性嵌入(Locally Linear Embedding，LLE[4])与拉普拉斯特征映射(Laplacian Eigenmap[5])等。此类方法的特点在于其均假设数据本身具有低维的流形形式(即数据空间呈现由少数独立特征共同作用所张成的低维流形形态)。相比其它降维方法，流形学习方法具有很多优势：首先，其计算性能对数据的非线性流形结构具有自适应性；其次，只涉及到较少的参数选择问题；另外，基于非常易于理解的模型构造方式，降维后的数据特征具有很好的可解释性。在人脸识别，手写数字辨识，文本归类、轨迹跟踪等方面的成功应用([3，4，5，6])也进一步验证了流形学习降维方法的有效性。然而，目前这些方法的有效应用主要体现在聚类与数据可视化等应用领域中，当面对模式分类、回归分析、时间序列分析等需要预测功能的数据挖掘问题时，这些方法便会失效。主要原因是其仅实现了位于高维流形上有限数据集的低维表示(点与点的嵌入)，但并未建立高维流形空间与对应低维表示空间之间的相互映射关系(集合与集合的映射)，这使其无法获得一个新输入高维(或低维)空间数据在对应低维表示空间(或高维流形空间)的映射表示。此问题已成为限制流形学习方法进一步扩展应用的主要瓶颈([7，8，9])。因此，如何实现流形空间与其对应低维表示空间之间的映射关系，或者说如何基于流形产生的数据完整准确地重建流形结构，是目前流形学习领域亟需解决的主要问题之一。 目前已提出了一些流形重建方法[10]。其中最具代表性的包括由Isomap方法原理延伸构造的Landmark Isomap方法(L-Isomap[11，12])，由LLE方法原理构建的Extending LLE方法(E-LLE[13])与利用Laplacian eigenmap类似原理而提出的Locality presearving projections方法(LPP[14])与其非线性核化方法，以及一些其它方法[15]。这些方法在应用中的表现各有优劣，如：L-Isomap方法具有鲁棒的流形映射表现，然而对于每个新输入数据此方法需利用图论技术估计其与所有现有数据间的测地距离，因而导致算法计算速度较慢；E-LLE方法对于无噪音数据表现良好，然而由于LLE方法的计算性能对于噪音干扰反应敏感，因此往往导致基于LLE方法的E-LLE流形映射结果鲁棒性较差；LPP方法本质为针对非线性问题设计的线性方法，计算速度极快，但由于其本质的线性特征，对于具有非线性结构的数据往往计算失效。 针对以上问题，本文提出了两种全新的高效流形结构重建方法。一种为