降维是机器学习中很有意思的一部分，很多时候它是无监督的，能够更好地刻画数据，对模型效果提升也有帮助，同时在数据可视化中也有着举足轻重的作用。

一说到降维，大家第一反应总是PCA，基本上每一本讲机器学习的书都会提到PCA，而除此之外其实还有很多很有意思的降维算法，其中就包括isomap，以及isomap中用到的MDS。

ISOMAP是‘流形学习’中的一个经典算法，流形学习贡献了很多降维算法，其中一些与很多机器学习算法也有结合，但上学的时候还看了蛮多的机器学习的书，从来没听说过流形学习的概念，还是在最新的周志华版的《机器学习》里才看到,很有意思，记录分享一下。

流形学习

流形学习应该算是个大课题了，它的基本思想就是在高维空间中发现低维结构。比如这个图：
这些点都处于一个三维空间里，但我们人一看就知道它像一块卷起来的布，图中圈出来的两个点更合理的距离是A中蓝色实线标注的距离，而不是两个点之间的欧式距离（A中蓝色虚线）。

此时如果你要用PCA降维的话，它根本无法发现这样卷曲的结构（因为PCA是典型的线性降维，而图示的结构显然是非线性的），最后的降维结果就会一团乱麻，没法很好的反映点之间的关系。而流形学习在这样的场景就会有很好的效果。

我对流形学习本身也不太熟悉，还是直接说算法吧。

ISOMAP

在降维算法中，一种方式是提供点的坐标进行降维，如PCA；另一种方式是提供点之间的距离矩阵，ISOMAP中用到的MDS(Multidimensional Scaling)就是这样。
在计算距离的时候，最简单的方式自然是计算坐标之间的欧氏距离，但ISOMAP对此进行了改进，就像上面图示一样：

**1.**通过kNN(k-Nearest Neighbor)找到点的k个最近邻，将它们连接起来构造一张图。
**2.**通过计算同中各点之间的最短路径，作为点之间的距离$dijd_{ij}dij​$dijdij​dij​放入距离矩阵$DDD$DDD
**3.**将$DDD$DDD传给经典的MDS算法，得到降维后的结果。

ISOMAP本身的核心就在构造点之间的距离，初看时不由得为其拍案叫绝，类似的思想在很多降维算法中都能看到，比如能将超高维数据进行降维可视化的t-SNE。
ISOMAP效果，可以看到选取的最短路径比较好地还原了期望的蓝色实线，用这个数据进行降维会使流形得以保持：

ISOMAP算法步骤可谓清晰明了，所以本文主要着重讲它中间用到的MDS算法，也是很有意思的。

经典MDS（Multidimensional Scaling）

如上文所述，MDS接收的输入是一个距离矩阵$DDD$DDD,我们把一些点画在坐标系里：

如果只告诉一个人这些点之间的距离（假设是欧氏距离），他会丢失那些信息呢？
**a.**我们对点做平移，点之间的距离是不变的。
**b.**我们对点做旋转、翻转，点之间的距离是不变的。

所以想要从$DDD$DDD还原到原始数据$XXX$XXX是不可能的，因为只给了距离信息之后本身就丢掉了很多东西，不过不必担心，即使这样我们也可以对数据进行降维。

我们不妨假设：$XXX$XXX是一个$n×qn \times qn×q$n×qn×qn×q的矩阵，n为样本数，q是原始的维度
计算一个很重要的矩阵$BBB$BBB：
$B=XXT    (n×n)=(XM)(XM)T    (M是一组正交基)=XMMTX=XXT\begin{aligned} B &= XX^T  \space\space\space\space(n\times n) \\   &= (XM)(XM)^T \space\space\space\space(M是一组正交基)\\   &= XMM^TX \\   &= XX^T\end{aligned}B​=XXT    (n×n)=(XM)(XM)T    (M是一组正交基)=XMMTX=XXT​$B=XXT    (n×n)=(XM)(XM)T    (M是一组正交基)=XMMTX=XXT B      ​amp;=XXT     (n×n)amp;=(XM)(XM)T     (M是一组正交基)amp;=XMMTX amp;=XXT​B​=XXT    (n×n)=(XM)(XM)T    (M是一组正交基)=XMMTX=XXT​
可以看到我们通过$MMM$MMM对$XXX$XXX做正交变换并不会影响$BBB$BBB的值，而正交变换刚好就是对数据做旋转、翻转操作的。
所以如果我们想通过$BBB$BBB反算出$XXX$XXX，肯定是没法得到真正的$XXX$XXX,而是它的任意一种正交变换后的结果。

B中每个元素的值为：
$bij=∑k=1qxikxjk\begin{aligned} b_{ij} &= \sum_{k=1}^{q}x_{ik}x_{jk}\end{aligned}bij​​=k=1∑q​xik​xjk​​$bij=∑k=1qxikxjk bij​​amp;=k=1∑q​xik​xjk​​bij​​=k=1∑q​xik​xjk​​
计算距离矩阵$DDD$DDD，其中每个元素值为:
$dij2=(xi−xj)2=∑k=1q(xik−xjk)2=∑k=1qxik2+xjk2−2xikxjk=bii+bjj−2bij\begin{aligned} d_{ij}^2 &= (x_i-x_j)^2 \\     &= \sum_{k=1}^{q}(x_{ik}-x_{jk})^2\\     &= \sum_{k=1}^{q}x_{ik}^2+x_{jk}^2-2x_{ik}x_{jk}\\     &=b_{ii}+b_{jj}-2b_{ij}\end{aligned}dij2​​=(xi​−xj​)2=k=1∑q​(xik​−xjk​)2=k=1∑q​xik2​+xjk2​−2xik​xjk​=bii​+bjj​−2bij​​$dij2=(xi−xj)2=∑k=1q(xik−xjk)2=∑k=1qxik2+xjk2−2xikxjk=bii+bjj−2bij dij2​            ​amp;=(xi​−xj​)2amp;=k=1∑q​(xik​−xjk​)2amp;=k=1∑q​xik2​+xjk2​−2xik​xjk​amp;=bii​+bjj​−2bij​​dij2​​=(xi​−xj​)2=k=1∑q​(xik​−xjk​)2=k=1∑q​xik2​+xjk2​−2xik​xjk​=bii​+bjj​−2bij​​\tag{dij_square}\label{dij_square}
这时候我们有的只有$DDD$DDD，如果能通过$DDD$DDD计算出$BBB$BBB，再由$BBB$BBB计算出$XXX$XXX，不就达到效果了吗。

所以思路是：从D->B->X
此时我们要对X加一些限制，前面说过我们平移所有点是不会对距离矩阵造成影响的，所以我们就把数据的中心点平移到原点，对X做如下限制（去中心化）：
$∑i=1nxik=0,for all k=1..q\begin{aligned} \sum_{i=1}^nx_{ik} = 0, for \space all \space k =1..q\end{aligned}i=1∑n​xik​=0,for all k=1..q​$∑i=1nxik=0,for all k=1..q i=1∑n​xik​=0,for all k=1..q​i=1∑n​xik​=0,for all k=1..q​
所以有
$∑j=1nbij=∑j=1n∑k=1qxikxjk=∑k=1qxik(∑j=1nxjk)=0\begin{aligned} \sum_{j=1}^nb_{ij} &= \sum_{j=1}^n\sum_{k=1}^{q}x_{ik}x_{jk}\\    &=\sum_{k=1}^{q}x_{ik}\left(\sum_{j=1}^nx_{jk}\right)\\    &=0\end{aligned}j=1∑n​bij​​=j=1∑n​k=1∑q​xik​xjk​=k=1∑q​xik​(j=1∑n​xjk​)=0​$∑j=1nbij=∑j=1n∑k=1qxikxjk=∑k=1qxik(∑j=1nxjk)=0 j=1∑n​bij​        ​amp;=j=1∑n​k=1∑q​xik​xjk​amp;=k=1∑q​xik​(j=1∑n​xjk​)amp;=0​j=1∑n​bij​​=j=1∑n​k=1∑q​xik​xjk​=k=1∑q​xik​(j=1∑n​xjk​)=0​
类似的
$∑i=1nbij=∑i=1n∑k=1qxikxjk=∑k=1qxjk(∑i=1nxik)=0\begin{aligned} \sum_{i=1}^nb_{ij} &= \sum_{i=1}^n\sum_{k=1}^{q}x_{ik}x_{jk}\\    &=\sum_{k=1}^{q}x_{jk}\left(\sum_{i=1}^nx_{ik}\right)\\    &=0\end{aligned}i=1∑n​bij​​=i=1∑n​k=1∑q​xik​xjk​=k=1∑q​xjk​(i=1∑n​xik​)=0​$∑i=1nbij=∑i=1n∑k=1qxikxjk=∑k=1qxjk(∑i=1nxik)=0 i=1∑n​bij​        ​amp;=i=1∑n​k=1∑q​xik​xjk​amp;=k=1∑q​xjk​(i=1∑n​xik​)amp;=0​i=1∑n​bij​​=i=1∑n​k=1∑q​xik​xjk​=k=1∑q​xjk​(i=1∑n​xik​)=0​
可以看到即$BBB$BBB的任意行(row)之和以及任意列(column)之和都为0了。

设T为$BBB$BBB的trace，则有：
$∑i=1ndij2=∑i=1nbii+bjj−2bij=T+nbjj+0\begin{aligned} \sum_{i=1}^nd_{ij}^2 &= \sum_{i=1}^n b_{ii}+b_{jj}-2b_{ij}\\   &= T + nb_{jj} + 0\end{aligned}i=1∑n​dij2​​=i=1∑n​bii​+bjj​−2bij​=T+nbjj​+0​$∑i=1ndij2=∑i=1nbii+bjj−2bij=T+nbjj+0 i=1∑n​dij2​   ​amp;=i=1∑n​bii​+bjj​−2bij​amp;=T+nbjj​+0​i=1∑n​dij2​​=i=1∑n​bii​+bjj​−2bij​=T+nbjj​+0​
$∑j=1ndij2=∑j=1nbii+bjj−2bij=nbii+T+0\begin{aligned} \sum_{j=1}^nd_{ij}^2 &= \sum_{j=1}^n b_{ii}+b_{jj}-2b_{ij}\\   &= nb_{ii} + T + 0\end{aligned}j=1∑n​dij2​​=j=1∑n​bii​+bjj​−2bij​=nbii​+T+0​$∑j=1ndij2=∑j=1nbii+bjj−2bij=nbii+T+0 j=1∑n​dij2​   ​amp;=j=1∑n​bii​+bjj​−2bij​amp;=nbii​+T+0​j=1∑n​dij2​​=j=1∑n​bii​+bjj​−2bij​=nbii​+T+0​
$∑i=1n∑j=1ndij2=2nT\begin{aligned} \sum_{i=1}^n\sum_{j=1}^nd_{ij}^2 &= 2nT\end{aligned}i=1∑n​j=1∑n​dij2​​=2nT​$∑i=1n∑j=1ndij2=2nT i=1∑n​j=1∑n​dij2​​amp;=2nT​i=1∑n​j=1∑n​dij2​​=2nT​
得到B：根据公式 \eqref{dij_square}我们有：
$bij=−12(dij2−bii−bjj)\begin{aligned} b_{ij} &= -\frac12(d_{ij}^2-b_{ii}-b_{jj})\end{aligned}bij​​=−21​(dij2​−bii​−bjj​$bij=−12(dij2−bii−bjj) bij​​amp;=−21​(dij2​−bii​−bjj​)​bij​​=−21​(dij2​−bii​−bjj​