基于增量的ISOMAP算法研究

林强　董平　林嘉宇

摘要：本文针对目前的流形学习算法进行分析研究，介绍了流形学习算法的主要算法，特别是对其中的ISOMAP算法进行详细的分析，并针对其存在的缺点进行算法改进，最后通过Swiss Roll和Swiss hole两种数据集实验比较MDS、PCA、ISOMAP、LLE、Hessian LLE、Laplaclan、InLLE和本文提出InISOMAP算法的优劣。

关键词：流形学习 PCA 增量算法

中图分类号：TP181 文献标识码：A 文章编号：1007-9416（2015）05-0000-00

1 引言

随着科技的发展进步，存储技术的发展，信息数据呈爆炸式增长，维度带来的灾难使得很多传统的方法都难以在有效的时间内处理这些大数据。因此，降维算法得到了很多研究人员的关注。经典的降维算法有主成分分析（Principal Component Analysis， PCA）、多维尺度映射 （Multi-dimensional Scaling， MDS）和Fisher判别分析（FDA）等[1]只能处理具有线性结构的数据。非线性降维算法就引起研究学者的关注。

Tenebaum等人从保持高维数据的全局角度出发，在同期的《科学》期刊上提出了ISOMAP算法[2]；而Roweis从局部几何结构入手，提出了LLE算法[3]。这两种不同的算法开创了两类不同的流形方法——全局保持算法和局部保持算法，推动了流形学习成为数据分析、机器学习和人工智能等领域的热点研究课题。近年来，流形学习得到了一定的发展，涌现了一些方法，如拉普拉斯特征映射（LE）算法[4]、局部切空间排列（LTSA）算法[5]、最大方差展开（MVU）[6]、Hessian特征映射[7]、局部样条嵌入（LSE）[8]等，这些方法通过使用谱方法求解矩阵的最大（或最小）的特征值所对应的特征向量，再将高维数据映射到特征向量空间上。这些方法有两个重要的特点：一是它们都是全局最优解，由于它们可以转换成凸优化问题求解，因而不会陷入局部最优解；二是都能在多项式时间内求解出来，就算最复杂的MDS算法也只需要O（n3）的时间，因此这对于流形学习的实时性有一定的意义。不过，流形学习存在一些问题，比如流形学习算法都是根据已知数据的结构来求得它在低维空间上的最优解的。此外，流形学习的算法都要求得到每一点的邻接点，近邻参数的选择直接影响了低维空间中的数据结构，如果近邻选取过多，会造成“短路”线性，选取过少，会导致出现大量的非连通的区域等等一些问题。不管在理论上还是应用上，这些问题都值得进一步研究。

2 流形学习算法介绍

以下按照发展的时间顺序简要介绍一些重要的流形学习算法。

主成分曲线（principal curves）和流形给出了一个自然简洁的非线性降维的框架，它通过标准的几何映射将PCA算法推广到构建高维数据的嵌入流形。通常情况下，主成分流形被视为一个优化问题的最优解，评价函数则要考虑数据结构的近似度以及要对使流形变形的情况进行惩罚。最初的估测数据算法主要是线性PCA，SOM或自动编码机。更具弹性的算法有期望最大值算法。

高斯过程潜在变量模型（， GPLVM）[9]是一种随机降维方法，即使用高斯过程计算出高维数据的低维非线性嵌入坐标。它是PCA的统计模型的推广。如同KPCA（kernel PCA）算法，GPLVM也使用一个核函数来计算非线性映射。

曲线成分分析（ CCA）[10]的主要思想在输出空间寻找尽可能保持原有数据间距离的点，同时十分重视输出空间中比较小的距离的点。必须要注意的是，使用迭代算法实现CCA时，刚开始关注比较大的距离，然后逐步关注较小的距离，较小距离的信息会代替较大距离的信息。

等规度变换（ISOMAP）算法是Flyoed算法和经典的多维尺度化（MDS）算法的结合。经典的MDS算法以各个数据点之间的距离矩阵作为输入，然后计算各个点的坐标。ISOMAP假设仅仅知道相邻数据点的距离，使用Floyd算法计算不相邻点之间的距离。Floyd算法可以高效的计算出所有数据点之间的距离。最后ISOMAP算法使用MDS算法降维后的所有点的坐标。

局部线性嵌入（LLE）算法与ISOMAP算法是同时提出来的，它相对ISOMAP来说有一些优势，由于利用了稀疏矩阵算法的一些性质使得LLE算法比ISOMAP更快，此外，LLE算法解决许多问题时相比ISOMAP具有更好地结果。HLLE（Hessian LLE）与LLE相似，都是基于稀疏矩阵算法。它能产生比LLE精确得多的结果，但是代价是时间复杂度很高。因此，密集采样的数据很少采用这种方法降维。

3 ISOMAP算法

Isomap算法的主要思想是：局部使用欧式距离，而各个局部之间的连接信息通过测地线距离表示，测地线距离利用邻接图上的最短距离来近似，对测地线距离矩阵利用MDS算法在输入空间与低维空间建立等距离映射，保持测地线距离不变，从而获得数据对应的低维空间坐标。

标准Isomap算法的基本步骤如下：

（1）构建空间X中流形M上所有数据点 的邻接图G，距离定义为欧式距离 ，邻接关系定义为 球或k最近邻（k-NN）。

（2）利用Dijkstra算法（或Floyd算法）计算邻接图G上两点间的最短路径 近似流形M上的测地线距离 ，得到近似测地线距离矩阵 。

对测地线矩阵 采用MDS算法，获得d维内蕴流形上的坐标 。

但是，Isomap具有一定的缺陷，例如计算复杂度较高为O（n3）；还有，它对噪声很敏感，当近邻点选取较宽松时，会造成短路，即由于流形曲面的弯曲使得两个测地线距离较远的区域由于欧式距离较近而被误连在一起。可见，Isomap抗噪能力较弱，一个点的出错会改变整个输出结果的结构。

4 基于增量ISOMAP算法

ISOMAP的一个缺点是它不能将新的点嵌入到低维内蕴流形上，因为它对于输入数据来说的是固定的。在数据空间 中，采样点集 包含 个点，假设新增加一个采样点 不改变新的数据点集的低维内蕴流形空间。为了获得新采样点集 的嵌入坐标，最简单的方法就是对新的点集 运行一次ISOMAP算法，新的点集中每一点的 近邻点以及每一对点之间的测地线距离都要重新计算一遍。这个过程的时间复杂度为 。为了提高它的效率，我们从输入数据中选择一些“界标点”，当有新的数据加入时，不需要计算对所有的点重新使用一次ISOMAP算法，而是只要保持新的数据点与界标点之间的测地线距离就行。低维内蕴空间中的界标点个数 满足条件 。

获取一个新的输入数据在低维内蕴空间的坐标的算法如下：

（1）使用一种合适的方法从输入数据中选取 个界标点。

（2）搜取新数据点 在输入数据 中的 近邻点集，并且计算新数据点 与每个界标点的测地线距离。

（3）将界标点和新数据点 合并为点集 ， 包含 个点。对 运行ISOMAP算法，获取 嵌入低维内蕴流形上的坐标。

为了计算新加入数据点的对应嵌入坐标，首先要计算它与界标点之间的测地线距离。当有新的数据点输入时，假设所有输入数据的 近邻点都保持不变，这就意味着所有输入数据点之间的测地线距离未发生改变。设新的数据点 近邻点集为 。根据Dijkstra算法，新的数据点与界标点之间的测地线距离可有以下方程得到：

，

其中 和 分别表示两点组合 间的测地线距离和欧式距离。为了使得计算测地线距离更加高效，可以保存输入数据点集的 近邻图，即一个 的矩阵。

在以上的算法中，计算搜取新增点的 近邻点至多只需要 的时间，而计算它们的测地线距离需要 的时间。MDS算法对于估计 的矩阵特征值来说时间复杂度为 ，因此计算新增点的低维嵌入坐标的时间复杂度是 。

5几种流形算法性能对比

本节对比了经典的流形学习算法MDS、PCA、ISOMAP、LLE、Hessian LLE、Laplaclan、InLLE和本文提出InISOMAP算法。下面通过两种数据集对各种算法进行比较。

5.1 Swiss Roll

Swiss Roll是经典的流形结构，由于它具有“卷”的结构，所以可以用它采样的数据来测试各种算法对测地线距离的保持性能。如图1可知，MDS算法和ISOMAP算法非常缓慢，HLLE算法次之，PCA算法最快。PCA算法和MDS算法不能展开Swiss Roll，因为在流形上，黄点和蓝点是距离最远的，而MDS算法没有保持结构这种结构，PCA算法上出现了重叠。LE、LLE和InLLE算法都不能保持原有的几何结构，只有ISOMAP、HLLE和InISOMAP能够较好地在嵌入空间保持了流形的几何结构。综合速度来看，InISOMAP胜出。

5.2 Swiss hole

Swiss hole是在Swiss roll上挖一个“孔”，这就破坏了流形的部分局部结构，一次测试各种算法对数据是否均匀采样的依赖性。从图2中可以看到，只有HLLE、InISOMAP能够成功处理这种具有非凸结构的流形，ISOMAP、LLE发生了一定的变形，而其他算法都失败了。

6结语

流形学习作为一种新兴的非线性降维技术正在受到研究者们越来越多的关注，它并非一种全新的理论，本文对ISOMAP不适合动态的数据系统的缺陷做出改进，得到基于增量的算法InISOMAP。实验表明，这种方法在动态的数据系统中性能优于ISOMAP算法。

本文只对流形学习算法中的ISOMAP算法进行了研究，并提出了改进的算法，但没有深入研究流形学习算法的实用价值。当前，由于大数据的持续火热，对数据降维技术的需求在持续增加，将流形学习引入到模式识别是一个非常诱人的想法，而且也有研究人员对这方面进行了研究，但是目前还没有非常成功的案例。未来工作中，可以考虑将对流形学习和人脸识别进行深度融合。

参考文献

[1]王靖.流形学习的理论与方法研究[D].浙江大学，2006

[2]Tenenbaum J B， De Silva V， Langford J C. A global geometric framework for nonlinear dimensionality reduction [J]. Science， 2000， 290（5500）： 2319-2323.

[3]Roweis S T， Saul L K. Nonlinear dimensionality reduction by locally linear embedding [J]. Science， 2000， 290（5500）： 2323-2326.

[4]Belkin M， Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering [C]//NIPS. 2001， （14）： 585-591.

[5]Zhang Z， Zha H. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment [J]. Journal of Shanghai University （English Edition）， 2004， 8（4）： 406-424.

[6]Weinberger K Q， Saul L K. An introduction to nonlinear dimensionality reduction by maximum variance unfolding [C]//AAAI. 2006， （6）： 1683-1686.

[7]Donoho D L， Grimes C. Hessian eigenmaps： Locally linear embedding techniques for high-dimensional data [J]. Proceedings of the National Academy of Sciences， 2003， 100（10）： 5591-5596.

[8]Xiang S， Nie F， Zhang C， et al. Nonlinear dimensionality reduction with local spline embedding [J]. Knowledge and Data Engineering， IEEE Transactions on， 2009， 21（9）： 1285-1298.

[9]Lawrence N D. Gaussian process latent variable models for visualisation of high dimensional data [J]. Advances in neural information processing systems， 2004， 16（3）： 329-336.

[10]Demartines P， Hérault J. Curvilinear component analysis： A self-organizing neural network for nonlinear mapping of data sets [J]. Neural Networks， IEEE Transactions on， 1997，8（1）：148-154.