【摘要】随着如今社会的发展和信息时代的到来，人工智能、模式识别等领域中的模式维数越来越高。对流形进行处理时经常会出现的“维数灾难”成为一个令人头疼的问题。解决“维数灾难”一种行而有效的方法是进行数据降维。而由麻省理工学院计算机科学与人工智能实验室的Josh Tenenbaum教授于2000在《Science》杂志上提出等距离映射（Isomap）算法就是一种具有代表性的可以将数据降维的算法。这里主要讲述Isomap算法的一些基础知识以及对Josh Tenenbaum教授的论文《A global geometric framework for nonlinear dimensionality reduction》的一些学习与分析。
【关键词】Isomap;等距离映射;降维;分析
1.降维的基本概念及相关算法简介
如何快速有效的对物体进行识别是当今社会的一个重要研究课题。一种行而有效的方法是进行数据降维。如今数据降维在许多领域起着越来越重要的作用。在处理高维数据前人们都会对维数提前进行降维处理。通过数据降维的方法可以减轻流形研究中出现的维数灾难并且消除高维空间中其他的不相关属性，从而提高维数据的归类效率和可读性。一般上数据降维是指通过线性或非线性映射将样本从高维空间映射到低维空间，从而获得高维数据的一个代表性低维表示的过程。
流形学习方法是模式识别中的基本方法，分为两种：线性和非线性。比如Fisher判别分析（FDA）、主成分分析（PCA）、多维尺度分析（MDS）、独立分量分析（ICA）之类，都属于线性的流形学习方法。线性方法相对于非线性流形方法计算相对简单，但对于那些非线性结构的数据就无法得到有效的答案。非线性流形方法则可以对非线性结构进行分析计算，产生较可靠的结果。比如，LLE[6]和Isomap是两种具有象征性的非线性降维方法。
Isomap主要是通过分析现有的高维流形，得到高维流形所对应的低维嵌入，从而让高维流形上数据点间的近邻结构在低维嵌入中得到较完整的重现。以MDS（Multidimensional Scaling）算法为分析工具，不同点在于计算高维流形上数据点间的距离时，弃用了传统的Euclidean距离，而是使用了微分几何中的测地线距离代替Euclidean距离，用实际的输入数据估算其测地线距离的一种算法[4]。
2.Isomap算法的研究内容及背景
2000年在《Science》杂志上提出来的Isomap是流形里一种具有代表性的非线性降维方法。Isomap是流形学习方法的一种。关于流形，流形的概念很早以前就被提出，直到2000年后，流形学习被确认为属于非线性降维的一个分支;直至今日，流形学习已成为信息科学领域的热门研究区域。无论在纯理论还是实际应用中，流形学习方法都表现出重要的研究意义。
等距离映射（Isomap）算法是一种可以将数据降维的方法。Isomap算法可以高效且有效地进行高维数据的低维嵌入以及利用数据降维的方法避免“维数灾难”的发生。数年来利用等距离映射（Isomap）算法将数据降维并将其应用到各领域对科技的发展和社会的管理带来了极大的便利。
假设数据是均匀采样于一个高维Euclidean空间中的低维流形，流形学习的目的就是找到高维空间中的低维流形，即从高维采样数据中重现低维流形结构，并求出相对应的低维嵌入映射，以实现维数的降低或者数据的易读化，它是从看到的表面中去寻找事物的特质，找到数据形成的内在规则。
等距特征映射算法（Isometric Feature apping，Isomap[2]）和局部线性嵌入算法（LLE）是流形学习算法的代表，发表于2000年的《Science》杂志。Isomap算法是一种全局的非线性降维方法;它是从古典线性降维方法MDS中发展而来，将MDS中的原始距离换成了流形上的测地线距离，再用MDS完成其他的工作。
虽然，Isomap这种流形学习算法在处理稀疏数据时碰到了障碍，降维能力快速失衡甚至消失。但是近几年又有人提出了各种改进的Isomap算法，比如P-Isomap、CN-Isomap等。短短十年左右的时间，Isomap算法得到了长足的发展。
3.定义
流形：是局部具有欧几里得空间性质的空间，是欧几里得空间中的曲线、曲面等概念的推广。欧几里得空间就是最简单的流形的实例。地球表面这样的球面则是一个稍微复杂的例子。一般的流形可以通过把许多平直的片折弯并粘连而成。
降维：在机器学习和统计领域中，降维是指减少所需考虑的随机变量个数。
多维标度分析：（multidimensional sca-ling，MDS[3]）是一组通过直观的空间图（spa-tial map），表示研究对象的感知和偏好的分析方法。
欧氏距离：（Euclidean distance）也称欧几里得距离，它是一个通常采用的距离定义，它是在m维空间中两个点之间的真实距离。
线性：指量与量之间按比例、成直线的关系，在空间和时间上代表规则和光滑的运动。
非线性：指不按比例、不成直线的关系，代表不规则的运动和突变。
維数灾难：（英语：curse of dimensi-onality，又名维度的诅咒）一个最早由理查德·贝尔曼（Richard E.Bellman）在考虑动态优化问题时首次提出来的术语，用来描述当（数学）空间维度增加时，分析和组织高维空间（通常有成百上千维），因体积指数增加而遇到各种问题场景。这样的难题在低维空间中不会遇到，如物理空间通常只用三维来建模。
swiss_roll_data数据集：一种用于流形学习的常用人工数据集。
4.Isomap算法思想及实现
Isomap算法属于非线性方法。主要思想是先计算流形上的测地线距离，然后利用计算出来的测地线来代替欧氏距离，应用MDS算法，从而发现嵌入在高维空间里的低维坐标，这样Isomap就通过数据间的测地线距离，保留了数据固有的几何分布结构。Isomap中的测地线距离则使用的是最近邻接图中的最短路径[5]。
Isomap算法的优点是利用了流形上的测地线距离来代替欧氏距离，可以较好的保留数据的空间结构;缺点是Isomap算法具有拓扑不稳定性;若产生短环路则会严重影响其执行;并且对流形具有一定的限制要求。若流形不是凸的，则会发生变形;另外，若有空洞出现在流形上，Isomap算法也不能解决这个问题[8]。
算法思想如下：
（1）确定流形M上哪些点是邻近的，两点（i，j）之间距离用Dx（i，j）表示;i，j点皆属于空间X;Dx（i，j）距离定义为Euclidean距离[5]，邻接关系可以设为固定的半径e或K最近邻。
（2）通过计算图G上两点间的最短路径DG（i，j）估计流形M上测地线距离DM（i，j）。
（3）应用经典MDS构建一个在d维欧氏空间Y中保留最为完整的内在嵌入流形几何。
算法实现：
在Josh Tenenbaum教授的论文[2]中，使用的是Swiss_roll数据集，该论文中使用的数据集采样N固定为1000，进行降维后，得到了比较理想的答案。理解学习了Josh Tenenbaum教授的论文后，这里考虑将数据集采样N作为变量，来观察不同的N对Isomap算法产生的影响。
本次实验使用软件版本为MATLAB7.0，运行环境win XP，数据集为swiss_roll_data。
步骤：
输入：输入样本X，近邻数K，邻接矩阵D，嵌入维数n。
输出：降维后维数与方差的关系图。
当Swiss_roll数据集采样N=1000时的原始图形如图1所示：
图1
当数据集采样N不同时，利用MATLAB进行降维处理，得到的维数与剩余方差的关系图如图2所示：
图2
由图2所示可以看出：
当数据集采样N为1500、1000时，当维数大于2时，随着维数的增加，剩余方差并没有太大变化。
当数据集采样N为700、600、500、400时，当维数大于4时，随着维数的增加，剩余方差并没有太大变化。
当数据集采样N为300、200、100时，当维数大于3时，随着维数的增加，剩余方差并没有太大变化。
综合实验的结果，Isomap方法的确在数据降维方面有重要的意义。无论数据集采样N的大小，剩余方差在一定的维数限制下，总是能保持在一个很小的幅度内波动。
在一定范围内，Isomap算法可以将流形维数约简的同时保证其应有的特性不被破坏。Isomap算法的出现，为数据降维又提供了一种行而有效的方法。
参考文献
[1]Sebastian HS，Lee DD.The manifold ways of perception.Science，2000，290（12）：2268−2269.
[2]Tenenbaum JB，de Silva V，Langford JC.A global geometric framework for nonlinear dimensionality reduction.Science，2000，290（12）：2319−2323.
[3]Borg I，Groenen P.Modern multidimensional sealing：theory and application[M].New York，USA：Springer-Verlag，1997.
[4]流形学习.百度百科.[2014-03-25].[2014-08-19]
[5]赵连伟，罗四维，赵艳敞等.高维数据流形的低维嵌入及嵌入维数研究[J].软件学报，2005，16（8）：1423-1430.
[6]Roweis ST，Saul LK.Nonlinear dimensionality analysis by locally linear embedding.Science，2000，290（12）：2323−2326.
[7]J.B.Tenenbaum，V.de Silva and J.C.Langford，A Global Geometric Framework for Nonlinear Dimensionality Reduction.Science，2000，290（5500）：2319-2323.
[8]吳晓婷，闫德勤.数据降维方法分析与研究[J].计算机应用研究，2009，08（008）：2833-3835.
本项目受大连民族学院2014大学生创新创业训练计划项目资助（项目编号：2014120260143）;受2014年辽宁省大学生创新创业训练计划项目资助（项目编号：201412026000018）。
作者简介：周金龙，现就读于大连民族学院理学院，研究方向：信息与计算科学。