logo

MDS

距离计算问题的反问题

计算距离问题是小学时我们就会学习的，假设有一张地图，上面标示了数个城市，你需要求城市间的两两距离。这非常简单，尺子一量就知道了。如果是在多维坐标系下可以使用距离公式:

d_{ij} = ||x_i - x_j ||^2

现在把问题改一下假设你只知道n个城市两两之间的距离，那么这n个城市的位置关系应该是怎样的呢？

image

已知距离计算位置的算法称为MDS,它是距离计算问题的反问题.它的解可能有很多,因为平移和旋转是不影响点之间的距离的,比如下面这一组镜像点:

image

MDS

设 d_{ij} 为样本 x_i 到 x_j 之间的距离, 即 d_{ij} = ||x_i - x_j ||^2 ,设矩阵B为样本的协方差矩阵,即 b_{ij} = x_i^Tx_j

\begin{align} 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{align}

为了便于讨论我们对样本进行中心化,即 \sum_{i=1}^mx_i = 0 .可以推导出矩阵B的行与列之和均为零:

\sum_{i=1}^mb_{ij} = x_j\sum_{i=1}^mx_i^T = 0

\sum_{j=1}^mb_{ij} = x_i^T\sum_{j=1}^mx_j = 0

\sum_{i=1}^nd_{ij}^2 = \sum_{i=1}^n b_{ii}+b_{jj}-2b_{ij} = tr(B) + nb_{jj}

\sum_{j=1}^nd_{ij}^2 = \sum_{j=1}^n b_{ii}+b_{jj}-2b_{ij} = nb_{ii} + tr(B)

\sum_{i=1}^n\sum_{j=1}^nd_{ij}^2 = 2ntr(B)

可得:

\begin{align} b_{ij} &= -\frac12(d_{ij}^2-b_{ii}-b_{jj})\\ &= -\frac12(d_{ij}^2-\frac1n\sum_{j=1}^nd_{ij}^2-\frac1n\sum_{i=1}^nd_{ij}^2+\frac{2T}{n})\\ &= -\frac12(d_{ij}^2-\frac1n\sum_{j=1}^nd_{ij}^2-\frac1n\sum_{i=1}^nd_{ij}^2+\frac{1}{n^2}\sum_{i=1}^n\sum_{j=1}^nd_{ij}^2)\\ &= -\frac12(d_{ij}^2-d_{i\cdot}^2-d_{\cdot j}^2+d_{\cdot\cdot}^2) \end{align}

至此,我们根据距离求出了样本的协方差矩阵B.而协方差矩阵为样本的内积 B = X^TX .

如果你对特征值分解比较了解的话,你会知道 X^TX 与 X 的特征向量是相同的,而 X^TX 的特征值是 X 特征值的平方.所以我们可以对 X^TX 进行特征值分解:

X^TX = W\Sigma^2 W^T

所以

X = W\Sigma W^T

其中 W 是特征向量, \Sigma 为特征值矩阵.

另外需要提的是MDS也被用作降维,因为MDS会计算出 X 的特征向量 W ,只需要取前几个重要的特征向量就达到了降维的目的.

编程实现:
https://www.kaggle.com/swimmingwhale/multiple-dimensional-scaling

参考:
周志华<机器学习>
https://blog.csdn.net/Dark_Scope/article/details/53229427
http://www.datasciencelab.cn/dimensionreduction/mds

posted @ 2018-10-03 12:06:45
评论加载中...
发表评论