数事载本与度用
基于增量的ISOMAP算法研究
林强董平林嘉宇
(国防科技大学湖南长沙410073)
算法分析
摘要：本文针对日前的流形学习算法进行分新研究介绍了流形学习算法的主要算法,特别是对其中的SOMAP算法进行详期的分析,并针对其存在的缺点进行算法改进，最后通过Swiss Roll和Swis hole两种数据集实验比较MDS、PCA、ISOMAP、LLE、Hessian LLE、Laplaclan、InLLE和本文提出InISOMAP算法的优券。
关键词流形学习PCA增量算法
中图分类号：TP18] 1引言
文献标识码:A
随着科技的发展进步，存储技术的发展，信息数据呈爆炸式增长，维度带来的灾难使得很多传统的方法都难以在有效的时间内处理这些大数据。因此.降维算法得到了很多研究人员的关注。经典的降维算法有主成分分析(PrincipalComponentAnalysis,PCA) 多维尺度映射(MultidimensionalScaling，MDS)和Fisher判别分析(FDA)等只能处理具有线性结构的数据。非线性降维算法就引起研究学者的关注。
Tenebaum等人从保持高维数据的全局角度出发，在同期的科学>期刊上提出了ISOMAP算法，而Roweis从局部几何结构人手，提出了LLE算法这两种不同的算法开创了两类不同的流形方法
全局保持算法和局部保持算法，推动了流形学习成为数据分析、机器学习和人工智能等领域的热点研究课题。近年来，流形学得到了定的发展，涌现了一些方法，如拉普拉斯特征映射(LE)算法，局部切空闻排列(LTSA)算法)最大方差展开(MVU)Hessian特征映射7) 局部样条嵌入(LSE等，这些方法通过使用谱方法求解矩阵的最大（或最小的特征值所对应的特征向量，再将高维数据映射到特征向量空间上。这些方法有两个重要的特点：一是它们都是全局最优解，由
文章编号:1007-9416(2015)05-0125-03
于它们可以转换成凸优化问题求解，因面不会陷人局部最优解，二是都能在多项式时间内求解出来，就算最复杂的MDS算法也只需要O(n)的时间，因此这对于流形学习的实时性有一定的意义，不过，流形学习存在一些问题，比如流形学习算法都是根据已知数据的结构来求得它在低维空间上的最优解的。此外，流形学习的算法都要求得到每一点的邻接点，近邻参数的选择直接影响了低维空闻中的数据结构，如果近邻选取过多，会造成“短路线性，选取过少，会导致出现大量的非连通的区域等等一些问题。不管在理论上还是应用上，这些问
题都值得进一步研究。 2流形学习算法介绍
以下按照发展的时间顺序简要介绍一些重要的流形学习算法。主成分曲线(principalcurves)和流形给出了一个自然简洁的
非线性降维的框架，它通过标准的几何映射将PCA算法推广到构建高维数据的嵌入流形。通常情况下，主成分流形被视为一个优化问题的最优解，评价函数则要考患数据结构的近似度以及要对使流形变形的情况进行惩罚.最初的估测数据算法主要是线性PCA，SOM 或自动编码机。更具弹性的算法有期望最大值算法。
高斯过程潜在变量模型(研家n)，GPLVM)9是一种随机降
PCA:QO1371
LLE: 0.09187s
hN
图1八种算法对Swissroll数据的降维结果
收稿日期：2015-05-10
作者简介：林强(1982一),男，福建永泰人,颈士，研究方向：流形学习，图像处理。