数据降维(四)ISOMAP

流形学习——ISOMAP算法

Isomap(Isometric Feature Mapping)是流行学习的一种,用于非线性数据降维,是一种无监督算法.

流形

流形是一个局部具有欧式空间性质的拓扑空间,流形能很好地近似任意高维的子空间.

测地线距离

测地距离(Geodesic Distance),在高维空间中度量距离不应当直接使用欧式距离,而应当使用测地距离.

测地线距离定义

  • 邻近的点:输入空间的欧式距离提供一个测地线距离的近似.
  • 最远的点:测地线距离通过一些列邻域点之间的欧式距离的累加近似得到.

举例: 在一个流形中,相距很远的两个点,有可能欧式距离很近.

ISOMAP算法

ISOMAP(Isometric Feature Mapping, 等距离特征映射),是一种非线性降维方法,其基于度量MDS,试图保留数据内在的由测地线距离蕴含的几何结构.

算法步骤

  • 构建邻接图
    • 通过连接距离小于ϵ\epsilonϵ的两个点iii和jjj在N个数据点上定义图GGG(ϵ−Isomap\epsilon-Isomapϵ−Isomap),或者点iii是点jjj的kkk近邻之一(K-Isomap).
    • 设置边的长度为d(i,j)d(i,j)d(i,j).
  • 计算最短路径
    • 初始化dG(i,j)=d(i,j)d_G(i,j) = d(i,j)dG​(i,j)=d(i,j),如果iii和jjj相连接,否则dG(i,j)=∞d_G(i,j) = \inftydG​(i,j)=∞
    • 对于每一个k=1,2,…,Nk=1,2,\dots, Nk=1,2,…,N,替换所有的dG(i,j)d_G(i,j)dG​(i,j)为min⁡(dG(i,j),dG(i,k)+dG(k,j)\min(d_G(i,j),d_G(i,k)+d_G(k,j)min(dG​(i,j),dG​(i,k)+dG​(k,j).那么DG=[dG(i,j)]D_G = [d_G(i,j)]DG​=[dG​(i,j)]包含G中所有点对的最短路径
  • 构建低维嵌入
    • 通过MDS构建低维的数据嵌入

瓶颈

  • 最短路径的计算
    • Floyd算法:O(N3)O(N^3)O(N3)
    • Dijkstra算法(Fibonacci堆实现):O(KN2log⁡N)O(KN^2\log N)O(KN2logN),K是最近邻的个数
  • 特征分解:O(N3)O(N^3)O(N3)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏耕耘实录

巧用OpenSSL完成md2、md4、md5、rmd160、sha、sha1等的验证

版权声明:本文为耕耘实录原创文章,各大自媒体平台同步更新。欢迎转载,转载请注明出处,谢谢

11030
来自专栏Debian社区

Debian升级内核开启TCP_BBR 实现网络单边加速

自从锐速发布以来,这款牛逼的单边加速神器的确为一些线路不太优秀的服务器带来了更优秀的体验。但是呢,过高的价格和不再低端售卖。导致了我们并无法实现一个免费好用的单...

45720
来自专栏做全栈攻城狮

React Native APP签名打包release版本APK

首先React Native开发的APP是无法通过Android Studio进行打包的,因为AS打包的APK,也是和debug版本一样,需要进行依托local...

27220
来自专栏耕耘实录

SSH免密远程登录的配置与实现

操作系统:CentOS Linux release 7.4.1708 (Core)

16620
来自专栏進无尽的文章

数据结构与算法 - 时间复杂度与空间复杂度

时间复杂度:时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的最大次数。 空间复杂度:类似于时间复杂度的讨论,一个算法的空间复杂度为该算法所耗费...

97420
来自专栏博客园

Core官方DI解析(3)-ServiceCallSite.md

上一篇说过在整个DI框架中IServiceProviderEngine是核心,但是如果直接看IServiceProviderEngine派生类其实看不出也没什么...

11410
来自专栏即时通讯技术

用JWT技术解决IM系统Socket长连接的身份认证痛点1、引言2、原作者3、系列文章5、完全搞懂什么是JWT技术6、我们是怎样使用JWT技术的?7、JWT技术的缺点8、点评附录:更多即时通讯方面的文

本文引用了封宇《JWT技术解决IM系统的认证痛点》一文的部分内容,即时通讯网重新整理、增补和修订,感谢原作者的无私分享。

13020
来自专栏Debian社区

多达 95% 的 HTTPS 链接能被黑客劫持

HSTS 是一个被当前大多数 Web 浏览器所支持的 Web 安全策略,它可以帮助 Web 管理员保护他们的服务器和用户避免遭到 HTTPS 降级、中间人攻击和...

20730
来自专栏做全栈攻城狮

电脑小白学习软件开发(9)-C#基础数组最大值,最小值及排序

上次说了枚举字符串以及数组的一部分知识点,其实这些东西枯燥的很。小编在以前学习的时候也是如此。虽然枯燥,但这是做所有项目的基础。今天主要讲解点数组的基础知识,这...

9910
来自专栏Debian社区

Google 宣布新拥堵控制算法 TCP BBR

Google 宣布了 新拥堵控制算法 TCP BBR。Google 官方博客称新算法将 google.com 和 YouTube 的全球网络吞吐量平均改进了 4...

25040

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励