机器学习降维算法六——ISOMAP(等距特征映射)
流形学习:传统的机器学习方法中，数据点和数据点之间的距离和映射函数都是定义在欧式空间中的，然而在实际情况中，这些数据点可能不是分布在欧式空间中的，因此传统欧式空间的度量难以用于真实世界的非线性数据，从而需要对数据的分布引入新的假设。流形学习假设所处理的数据点分布在嵌入于外维欧式空间的一个潜在的流形体上，或者说这些数据点可以构成这样一个潜在的流形体。
图1 一个嵌在三维空间的流行体
图1就是一个数据嵌入在流行体的例子，传统的例如PCA和MDS降维方法效果就不是十分理想。此流行体实际上是一个二维分布的平面，在三维空间中流行体上点与点之间的距离不能使用传统的欧式空间的距离来计算，而应该用测地线距离代表这两个点的实际距离。
图2 测地线和欧式距离
图2中蓝色虚线为两个点的欧式距离，蓝色实线为两个点的测地线距离。但是测地线距离也不好测量，因此我们采用另一种路径近似代表测地线距离。
图3 图中两点的最短路径
我们构建一个连通图，其中每个点只和距离这个点最近的k个点直接连接，和其他的点不直接连接。这样我们可以构建邻接矩阵，进而求出图中任意两个点的最短路径，代替测地线距离。
图4 测地线和图中两点的最短路径
在图四中，蓝色点代表两个点之间的测地线距离，红色线代表图中两点的最短路径，两者距离相近，因此我们使用后者替代前者。进而引出isomap算法。
1 基本思想
isomap算法是基于前面所讲的MDS算法，不同之处在于isomap用图中两点的最短路径距离替代了MDS中欧式空间的距离，这样能更好的拟合流行体数据。
2 原理推导
原理和MDS原理基本一致
唯一不同的地方如下:
MDS高维空间中两个点的距离:
而在isomap两个点的距离为图中两点的最短路径。
然后采用内积形式进行推导。
3 算法流程
(1)设置每个点最近邻点数k,构建连通图和邻接矩阵。
(2)通过图的最短路径构建原始空间中的距离矩阵。
(3)计算内积矩阵 。
(4)对矩阵B进行特征值分解，获得特征值矩阵 和特征向量矩阵
。
(5)取特征值矩阵最大的前 项及其对应的特征向量
。
4 举例
(1) 我们先举一个简单的例子，分别对图1利用isomap和MDS算法降维至2维空间。
图5(a)isomap
图5(b)MDS
当我们已知数据嵌在一个高维的流行体时候，使用isomap明显会有更好的效果。
但是大多数情况下，我们不知道高维流行体展开之后的维度，这个就需要我们通过主观来判断。下面是 A Global GEometric Framework for Nonlinear Dimensionality Reduction (提出isomap降维方法的文章)中的几个例子:
(2) 人脸照片
数据集是698个64x64的同一个人的脸部图像，那么每一个图像就相当于4096空间中的一个坐标点，实际上这些人脸照片也是嵌入在一个流行体内，根据主观判断，我们可以得出影响人脸的因素有三个:光照方向、是否上下抬头、是否左右偏头。使用isomap将数据降维到二维空间可得:
图6
图6横坐标指的是人左右偏头的程度、纵坐标是人上下偏头的程度、每一张图片下面的Lighting direction指的是光照的方向。我们可以看出数据点在低维的分布基本可以替代数据点在原始空间的分布，例如想要判断人脸的左右偏头的程度，完全可以在降维之后的点上训练分类器，也可以得到很好的效果。
图7
图7中纵轴是残差方差，其值越小表示和原始数据越相近。横轴表示降维之后的维度。
其中空心三角是PCA对人脸图片降维的残差方差，实心圆圈是isomap对人脸图片进行降维的残差方差。可以看出isomap效果要优于PCA。观察代表isomap的曲线，当维度等于3的时候，方差残差下降非常快，同时在维度高于3之后，残差方差值变化很小。我们可以断定流行体是三维的数据点嵌入到了高维空间。
(3) MINIST手写字体集中数字2
数据集一共有1000个数据项，每个数据项时28x28大小的图片。
图7
将数据降维至2维，我们通过观察低维空间数据点代表的图像，发现有两个明显的特征:
横坐标代表了数字2底部是否有一个环形；纵坐标表示数字2顶部的歪曲角度的大小。
图8
图8中纵轴是残差方差，其值越小表示和原始数据越相近。横轴表示降维之后的维度。
其中空心三角是PCA对数字2降维的残差方差，空心圆圈是MDS对数字2降维的残差方差实心圆圈是isomap对数字2降维进行降维的残差方差。观察代表isomap的曲线，并没有出现快速下降的趋势，因此数字2流行嵌入并不明显。
5 总结
总的来说，高维空间的数据大多数都具有相同的特点，因此会嵌入到一个流行体中，而不是随机分散在高维空间中，高维数据相同特征的数目也就是流行体的维度，也就是我们降维的目标空间维数，这个维度需要一定的人为主观判断。同时，如果数据在高维空间中没有嵌入到一个流行体中。例如高维数据点分为10类，每一类都和其它类分散开，自己成为一簇，此时isomap算法就不太适合。如果数据是分类的，数据基本不会嵌入在一个流行体，isomap降维算法效果就比较差，但是数据是连续的，数据就很有可能嵌入在一个流行空间内，此时isomap算法的效果就会比较好。