流形学习——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中所有点对的最短路径
- 构建低维嵌入
瓶颈
- 最短路径的计算
- Floyd算法:O(N3)O(N^3)O(N3)
- Dijkstra算法(Fibonacci堆实现):O(KN2logN)O(KN^2\log N)O(KN2logN),K是最近邻的个数
- 特征分解:O(N3)O(N^3)O(N3)