时间戳

首页 > 技术文章 > 简述降维方法MDS 与 Isomap

简述降维方法MDS 与 Isomap

poxiaoge 2017-06-24 23:57 原文

一、 多维缩放(Multidimensional Scaling)

1. 核心思想

使得原始空间中的样本距离在低维空间中得以保持

2. 问题描述

假定m个样本在原始空间中的距离矩阵为\(\bf {D} \in \mathbb R_{m\,x\,m}\),其第i行j列的元素\(dist_{ij}\)为样本\(\bf x_i\)到\(\bf x_j\)的距离.我们的目标是获得样本在 \(d^{'}\) 维空间的表示 \(\bf {Z} \in \mathbb {R}^{d^{'}\,\times\,m}\),\(d^{'} \le d\),
且任意两个样本在\(d^{'}\)维空间中的欧氏距离等于原始空间中的距离,即\(\parallel {\bf z_i-z_j} \parallel \,=\,dist_{ij}\).

3. 算法推导

MDS接收的输入是一个距离矩阵D.
如果只知道这些点的距离(假设是欧式距离),那么就会丢失一些信息:
a.我们对点做平移,点之间的距离是不变的
b.我们对点做旋转,翻转,点之间的距离是不变的.

所以想要从距离矩阵D精确还原到低维矩阵Z是不可能的,因为只给了距离信息之后本身就丢掉了很多东西.

设Z是高维矩阵X所对应的低维矩阵,矩阵\({\bf B}=Z^TZ\),M是一组正交基,则有

\[\begin{split}\bf B =&Z^TZ\\=&(ZM)^T(ZM)\\=&M^TZZM\\=&Z^TZ\end{split} \]

可以看到我们通过M对Z做正交变换并不会影响B的值,而正交变换就是对矩阵做旋转,翻转,平移等操作的.
所以,如果我们想通过B反退出Z,肯定是无法得到真正的Z,而是Z的任意一种正交变换后的结果.

令\({\bf B\,=\,Z^TZ}\,\in\,{\mathbb R}^{m\,\times\,m}\),B为降维后样本的内积矩阵,\(b_{ij}\,=\,{\bf z_i^Tz_j}\),则有

\[\begin{split}dist_{ij}^2=&\,{\parallel {\bf z_i} \parallel}^2+{\parallel {\bf z_j} \parallel}^2-2{\bf z_i^Tz_j}\\=&\,b_{ii}+b_{jj}-2b_{ij} \qquad (1) \end{split} \]

于是,我们发现,如果能通过D计算出B,那么再由B不就可以计算出Z了吗?
所以思路是:D->B->Z
现在我们要对Z加一些限制条件,由前面的讨论可知,品牌故意变换所有点不会对矩阵矩阵D造成影响,于是我们可以把数据的中心点平移到原点,对Z进行去中心化:

\[\begin{split}\sum_{i=1}^m{\bf z}_i=&\,{\bf 0} \\ \sum_{i=1}^m z_{ki}=&0\end{split}\]

其中\({\bf 0}\in{\mathbb R}^{d^{'}}\)为全零矩阵.
显然,矩阵B行与列的和均为0:

\[\begin{split}\sum_{j=1}^m b_{ij}\,&=\,\sum_{j=1}^m \sum_{k=1}^{d_{'}} z_{ki}z_{kj} \,=\,\sum_{k=1}^{d_{'}} z_{ki} \left (\sum_{j=1}^m z_{kj} \right) \,=\,0 \\ \sum_{i=1}^m b_{ij}\,&=\,\sum_{i=1}^m \sum_{k=1}^{d_{'}} z_{ki}z_{kj} \,=\,\sum_{k=1}^{d_{'}} z_{kj} \left (\sum_{i=1}^m z_{ki} \right) \,=\,0 \end{split}\]

矩阵B的迹$tr(B),=,\sum_{i=1}^m b_{ii} $,易知

\[\begin{split} &\sum_{i=1}^m dist_{ij}^2\,=\,tr(B)+mb_{jj}, \qquad (2)\\ &\sum_{j=1}^m dist_{ij}^2\,=\,tr(B)+mb_{ii} ,\qquad (3)\\ &\sum_{i=1}^m\sum_{j=1}^m dist_{ij}^2\,=\,2m\,tr(B) \qquad (4) \end{split} \]

我们令

\[\begin{split} dist_{i\cdot}^2\,&=\,{1\over m}\sum_{j=1}^m dist_{ij}^2 , \qquad (5)\\ dist_{\cdot j}^2\,&=\,{1\over m}\sum_{i=1}^m dist_{ij}^2 , \qquad (6)\\ dist_{\cdot \cdot}^2\,&=\,{1 \over {m^2}}\sum_{i=1}^m \sum_{j=1}^m dist_{ij}^2 \qquad (7) \end{split} \]

由式 (1)到 式(7) 可得

\[b_{ij}\,=\, -{ {1 \over 2} (dist_{ij}^2 - dist_{i \cdot}^2 - dist_{\cdot j}^2 + dist_{\cdot \cdot}^2 ) } \qquad (8) \]

由式(8)即可通过降维前后保持不变的距离矩阵D求取内积矩阵B.
对矩阵B作特征分解(eigenvalue decomposition),\(\bf B\,=\,V\Lambda V^T\),其中\({\bf \Lambda}\,=\,diag(\lambda_1,\lambda_2,\cdots,\lambda_d)\)为特征值构成的对角矩阵,\(\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_d\).
\(\Lambda\)为特征向量矩阵.假定其中有\(d^*\)个非零矩阵,它们构成对角矩阵\({\bf \Lambda}_*\,=\,diag(\lambda_1,\lambda_2,\cdots,\lambda_{d^*})\).令\(V_*\)表示相应的特征向量矩阵 ,则Z可表示为

\[{\bf Z\,=\, \Lambda_*^{1 \over 2} V_*^T} \,\in\,{\mathbb R}^{d^*\times m} \]

现实使用中,为了达到降维的目的,往往选择\(d^{'}\lt\lt d\)个最大的特征值构成的对角矩阵\(\Lambda\)和相应的特征向量矩阵\(V\)

4. 算法步骤

输入:距离矩阵\({\bf D}\,\in\,{\mathbb R}^{m\times m}\),其元素\(dist_{ij}\)为样本\(x_i\)到样本\(x_j\)的距离;低维空间维数\(d^{'}\).

过程:

  1. 根据式(5)~(7)计算\(dist_{i \cdot}^2,dist_{\cdot j}^2,dist_{\cdot \cdot}^2\);
  2. 根据式(8)计算矩阵B;
  3. 对矩阵B作特征值分解;
  4. 取\(\Lambda\)为\(d^{'}\)个最大特征值所构成的对角矩阵,\(V\)为相应的特征向量矩阵.

输出:
低维数据矩阵\({\bf Z\,=\,\Lambda^{1 \over 2}V^T} \,\in\,{\mathbb R}^{m\times d^{'}}\).每行是一个样本的低维坐标.

二、等度量映射(Isomap)

1. 算法思想

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

2. 算法步骤

输入:
样本集\(D=\{ x_1,x_2,\cdots,x_m\}\);近邻参数k;低维空间的维数\(d^{'}\).
过程:

  1. for i = 1,2,...,m do
    通过kNN算法确定\(x_i\)的k近邻;
    令\(x_i\)与k近邻点之间的距离设置为欧氏距离,与其它点的距离设置为无穷大.
    endfor
  2. 使用Floyd或Dijkstra算法计算任意两点之间的最短路径距离\(dist(x_i,x_j)\);
  3. 将\(dist(x_i,x_j)\)作为MDS算法的输入;
  4. 获取MDS算法的输出

输出:
样本集D在低维空间的投影\(Z=\{ z_1,z_2,\cdots ,z_m \}\)

3.算法讨论

ISOMAP本身的核心就在构造点之间的距离ISOMAP本身的核心就在构造点之间的距离.ISOMAP效果，可以看到选取的最短路径比较好地还原了期望的蓝色实线，用这个数据进行降维会使流形得以保持：

Reference

1.《机器学习》(周志华)

2. 维度打击，机器学习中的降维算法：ISOMAP & MDS

推荐阅读