【机器学习】降维——MDS算法原理推导

MDS算法

我们日常观测或者收集到的数据来看，很多数据特征都是用不到的，而学习任务可能仅仅局限于某个低维分布（某些低维特征），这就是高维空间中的一个低维“嵌入”。数据降维，是解决数据“维数灾难”的有效手段，即通过某种数学变换将原始高维属性空间转变为一个低维的“子空间”。MDS算法（Multiple Dimensional Scaling,简称MDS）是一种行之有效的低维嵌入算法，即在保障原始空间与低维空间样本之间距离一致的前提下，将高维数据进行降维。

原理推导

假设有$m$个样本，其样本空间如下：
$T=\{x_1,x_2,\cdots,x_m\} \qquad x_i \in R^d$
令$D$表示样本间的距离，其中$D\in R^{m \times m}$,其中第$i$行$j$列的元素$dist_{ij}$为样本$x_i$到样本$x_j$之间的距离。很显然，矩阵$D$是一个对称矩阵。MDS算法的目的是在不改变样本间距离的前提下，实现数据降维，故我们最终要得到样本在$d'$（新样本空间）中的表示$Z \in R^{d' \times m},d'\leq d$,且任意两个样本在$d'$维空间中的欧氏距离等于原始空间中的距离，即$||z_i-z_j||=dist_{ij}$
令$B=Z^TZ \in R^{m \times m}$，其中$B$为降维后样本的内积矩阵，其中$b_{ij}=z_i^Tz_j$，则有
$\begin{aligned} dist_{ij}^2 &=||z_i||^2+||z_j||^2-2z_i^Tz_j \\&=b_{ii}+b{jj}-2b_{ij} \qquad \qquad \dots(1)\end{aligned}$
为了便于讨论，令降维后的样本$Z$被中心化，即$\sum_{i=1}^mz_i=0$,显然，矩阵$B$的行与列之和均为0，即$\sum_{i=1}^mb_{ij}=\sum_{j=1}^mb_{ij}=0$，可得如下一些变换：
$\sum_{i=1}^m dist_{ij}^2=tr(\textbf{B})+mb_{jj} \qquad \qquad \dots(2)$
$\sum_{j=1}^m dist_{ij}^2=tr(\textbf{B})+mb_{ii} \qquad \qquad \dots(3)$
$\sum_{i=1}^m \sum_{j=1}^m dist_{ij}^2=2m \ tr(\textbf{B}) \qquad \qquad \dots(4)$
其中$tr(\cdot)$表示矩阵的迹（trace）,$tr(\textbf{B})=\sum_{i=1}^m||z_i||^2$。令
$dist_{i\cdot}^2=\frac{1}{m}\sum_{j=1}^m dist_{ij}^2 \qquad \qquad \dots(5)$
$dist_{\cdot j}^2=\frac{1}{m}\sum_{i=1}^m dist_{ij}^2 \qquad \qquad \dots(6)$
$dist_{\cdot \cdot}^2=\frac{1}{m^2}\sum_{i=1}^m \sum_{j=1}^mdist_{ij}^2 \qquad \qquad \dots(7)$
结合以上（1）~（7）可得：
$b_{ij}=-\frac{1}{2}(dist_{ij}^2-dist_{i \cdot}^2-dist_{\cdot j}^2+dist_{\cdot \cdot}^2) \qquad \qquad \dots(8)$
由此即可通过降维前后保持不变的距离矩阵$D$求取内积矩阵$B$,又由于矩阵$B$是对阵矩阵，对其进行特征分解，即
$B=V\Lambda V^T$
其中，$\Lambda=diag(\lambda_1,\lambda_2,\cdots,\lambda_d)$为特征值构成的对角矩阵，$\lambda_1\geq \lambda_2 \geq \cdots \geq \lambda_d$,$V$为对应的特征向量矩阵。假定其中有$d^*$个非零特征值，它们构成对角矩阵$Lambda_*=diag(\lambda_1,\lambda_2,\cdots,\lambda_{d^*})$,令$V_*$表示相应的特征向量矩阵，则$Z$可表达为：
$Z=\Lambda_*^{\frac{1}{2}}V_*^T \in R^{d^* \times m}$
在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必言格相等。此时可取$d'<<d$个最大特征值构成对角矩阵$\hat{\Lambda}=diag(\lambda_1,\lambda_2,\cdots,\lambda_{d'})$，令$\hat{V}$表示相应的特征向量矩阵，则$Z$可表达为：
$Z=\hat{\Lambda}^{\frac{1}{2}}\hat{V}^T \ \in R^{d' \times m}$
故推导完毕。

参考文献

机器学习 周志华著