数据降维(四)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)