多维缩放MDS降维方法

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  多维缩放(Multiple Dimensional Scaling, MDS)是一种经典的降维方法,它可以使原始空间中样本之间的距离在低维空间中得以保持,本文做一个简单的记录。

  假设\(m\)个样木在原始空间的距离矩阵为\(\mathbf{D} \in \mathbb{R}^{m \times m}\),其中每个元素\(dist_{ij}\)为样本\(\boldsymbol{x}_i\)\(\boldsymbol{x}_j\)之间的距离,我们的目标是获得样本在\(d^{'}\)维空间的表示\(\mathbf{Z} \in \mathbb{R}^{d^{\prime} \times m}, d^{\prime} \leqslant d\),且任意两个样本在样本空间中的欧氏距离等于原始空间中的距离,即\(\left\|z_{i}-z_{j}\right\|=d i s t_{i j}\)
  令\(\mathbf{B}=\mathbf{Z}^{\mathrm{T}} \mathbf{Z} \in \mathbb{R}^{m \times m}\),其中\(B\)为降维后样本的内积矩阵,\(b_{i j}=\boldsymbol{z}_{i}^{\mathrm{T}} \boldsymbol{z}_{j}\),有: \[ \begin{aligned} d i s t_{i j}^{2} &=\left\|z_{i}\right\|^{2}+\left\|z_{j}\right\|^{2}-2 z_{i}^{\mathrm{T}} z_{j} \\ &=b_{i i}+b_{j j}-2 b_{i j} \end{aligned} \]   令降维后的样本\(\mathbf{Z}\)被中心化,即\(\sum_{i=1}^{m} \boldsymbol{z}_{i}=\mathbf{0}\)\(\mathbf{B}\)的行与列之和均为零,即\(\sum_{i=1}^{m} b_{i j}=\sum_{j=1}^{m} b_{i j}=0\),因此: \[ \begin{array}{l}{\sum_{i=1}^{m} \operatorname{dist}_{i j}^{2}=\operatorname{tr}(\mathbf{B})+m b_{j j}} \\ {\sum_{j=1}^{m} \operatorname{dist}_{i j}^{2}=\operatorname{tr}(\mathbf{B})+m b_{i i}} \\ {\sum_{i=1}^{m} \sum_{j=1}^{m} \operatorname{dist}_{i j}^{2}=2 m \operatorname{tr}(\mathbf{B})}\end{array} \]   其中\(\operatorname{tr}(\mathbf{B})=\sum_{i=1}^{m}\left\|\boldsymbol{z}_{i}\right\|^{2}\),令: \[ d i s t_{i .}^{2}=\frac{1}{m} \sum_{j=1}^{m} d i s t_{i j}^{2} \\ d i s t_{\cdot j}^{2}=\frac{1}{m} \sum_{i=1}^{m} d i s t_{i j}^{2} \\ d i s t_{ . .}^{2}=\frac{1}{m^{2}} \sum_{i=1}^{m} \sum_{j=1}^{m} d i s t_{i j}^{2} \]   代入可得: \[ b_{i j}=-\frac{1}{2}\left(d i s t_{i j}^{2}-d i s t_{i}^{2}-d i s t_{ : j}^{2}+d i s t_{ . .}^{2}\right) \]   由此即可通过降维前后保持不变的距离矩阵\(\mathbf{D}\)求取内积矩阵\(\mathbf{B}\)
  对矩阵B做特征值分解(eigenvalue decomposition),得\(\mathbf{B}=\mathbf{V} \mathbf{\Lambda} \mathbf{V}^{\mathrm{T}}\),其中\(\Lambda=\operatorname{diag}\left(\lambda_{1}, \lambda_{2}, \dots, \lambda_{d}\right)\)为特征值构成的对角矩阵,其中\(\lambda_{1} \geqslant \lambda_{2} \geqslant \ldots \geqslant \lambda_{d}\)\(\mathbf{V}\)为特征向量矩阵.假定其中有\(d^*\)个非零特征值,它们构成对角矩阵\(\Lambda=\operatorname{diag}\left(\lambda_{1}, \lambda_{2}, \dots, \lambda_{d}\right)\),令\(\mathbf{V}_*\)表示相应的特征向量矩阵,则\(\mathbf{Z}\)可表达为: \[ \mathbf{Z}=\mathbf{\Lambda}_{*}^{1 / 2} \mathbf{V}_{*}^{\mathrm{T}} \in \mathbb{R}^{d^{*} \times m} \]   在现实应用中为了有效降维,往往仅需降维后的距离与原始空间中的距离尽可能接近,而不必严格相等.此时可取\(d^{'} \le d\)个最大特征值构成对角矩阵\(\tilde{\boldsymbol{\Lambda}}=\operatorname{diag}\left(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{d^{\prime}}\right)\),令\(\tilde{\mathbf{V}}\)表示相应的特征向量矩阵,则\(\mathbf{Z}\)可表达为: \[ \mathbf{Z}=\tilde{\mathbf{\Lambda}}^{1 / 2} \tilde{\mathbf{V}}^{\mathrm{T}} \in \mathbb{R}^{d^{\prime} \times m} \]   下图给出了具体的算法流程图:

Refer


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. Refer
您是第 位小伙伴 | 本站总访问量 | 已经写了 609.8k 字啦

载入天数...载入时分秒...