互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

非线性降维算法Isomap与C-Isomap的研究


□ 袁利国 唐武雷

  摘要:文章对非线性降维算法Isomap的思想,优缺点进行了介绍。并通过使用聚类函数来对样本点进行聚类和引进核函数来优化Isomap算法邻域点的求解,使用此基于聚类的降维算法C-Isomap来提高Isomap算法的性能和应用范围。最后基于Swiss-Roll数据对Isomap与C-Isomap算法进行了实验与对比分析,C-Isomap算法有更好的降维效果。
  关健词:非线性降维;Isomap;C-Isomap
  中图分类号:TP391文献标识码:A文章编号:1009-3044(2007)04-11036-02
  
  1 引言
  在处理高维数据如全局气候模式,面部数据分析,人类基因分布等。这些数据都有大量的冗余和其相关性中隐藏着重要的关系,这样他们可能就会碰到降维的问题:找出隐藏在他们所观察到高维数据中有意义的低维结构。非线性降维算法有利于发现数据的内在结构和相关性,并且可以使高维数据在低维下而变得可视化。
  当前有许多降维方法,这些方法可以分成:线性方法与非线性方法。线性方法包括主要分量分析(PCA)和投影寻踪(PP)等。非线性降维算法主要有多维度MDS,线性局部嵌入(LLE),局部线性投影(LLP),Laplacian特征映射,Hessian特征映射和等距映射(Isomap)等[1-3]。
  
  2 Isomap算法
  Isomap算法是近年来用于非线性降维的一个重要算法。它来源于传统的降维算法MDS,算法的关键在于利用样本向量之间的欧氏距离dx(i,j)计算出样本之间的测地距离dG(i,j),从而真实再现高维数据内在的非线性几何结构。然后使用经典MDS算法构造一个新的d维欧氏空间Y(d是降维空间的维数),最大限度地保持样本之间的欧式距离dY(i,j)与dG(i,j)误差最小,从而达到降维的目的。如下图1(a)-图1(c)所示。图1(a)中样本分布数据Swiss-roll上。两点间的欧式距离(虚线)不能表征两点的实际距离。分布于流形面上的曲线是两点的测地线距离。流形未知时可以通过最短路径算法对邻域内的距离进行近似地重构两点间的测地线距离。图1(b)、图1(c)是Isomap降维后两点和两条路径(测地线和短程拼接)的投影结果[4]。
  2.1 Isomap算法的前提假设
  (1)高维数据所在的低维流形与欧氏空间的一个子集是整体等距的; (2)与数据所在的流形等距的欧氏空间的子集是一个凸集。
  2.2 Isomap算法的核心估计两点间的测地距离
  (1)离得很近的点间的测地距离用欧氏距离代替;(2)离得较远的点间的测地距离用最短路径来逼近。
  2.3 Isomap算法的主要步骤如下:(1)构造近邻图。首先计算任意两个样本向量xi与xj的欧氏距离dX(xi,xj),然后用全部的样本向量 xi(1≤i≤N)构造无向图G。对于样本向量xi,在图G中将它与离它最近的n个样本向量(n是可调参数)连接起来,设置连接线的长度分别为它们各自的距离。 ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《电脑知识与技术》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017