距离计算问题的反问题

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

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

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

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

MDS

d_{ij}为样本x_ix_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^TXX的特征向量是相同的,而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
评论加载中...

发表评论