线性特征降维——MDS

MDS

Multi-dimensional scaling，简称MDS，中文翻译成多维尺度分析。其原理是利用成对样本间的相似性，去构建合适的低维空间，使得样本在此空间的距离和在高维空间中的样本间的相似性尽可能的保持一致。MDS建立一个原始高维输入空间样本到低维特征空间样本的一一映射，建立的原则是在输入空间距离近的样本在低维特征空间的距离也要近。我们可以用这种方式来可视化数据分布。

MDS 基本原理

假设我们有$n * d$的样本集 $X=\left[ \begin{matrix} x_{11} & x_{12} &\cdots& x_{1n} \\ x_{21} & x_{22} &\cdots& x_{2n} \\ \vdots&\vdots& \ddots&\vdots\\ x_{n1} & x _{n2} &\cdots& x_{nn} \end{matrix} \right] \tag{1}$ 之后我们计算出每两个样本点的欧氏距离构成距离矩阵 $d(X)=\left[ \begin{matrix} \delta_{11} & \delta_{12} &\cdots &\delta_{1n} \\ \delta_{21} & \delta_{22} &\cdots&\delta_{2n} \\ \vdots &\vdots &\ddots&\vdots \\ \delta_{n1} & \delta_{n2} &\cdots &\delta_{nn} \end{matrix} \right] \tag{2}$ 其中, $d_{ij}(X)=\delta_{ij}$样本$i$和样本$j$之间的欧式距离，有 $\delta=\rVert x_i-x_j\rVert \\ =\sqrt{\sum\limits_{s=1}^{n}(x_{is}-x_{js})^2} \tag{3}$ MDS的基本原理是在一个低维的空间中，将$n$个物体嵌入到该空间中，使得彼此间的相似度尽可能地保留。如果这个低维的空间是2维或者3维，则可以画出该$n$个物体的可视化结果。假设将这$n$个样本映射到新的$p$维空间中，映射成的矩阵形式如下 $Y=\left[ \begin{matrix} y_{11}&y_{12}&\cdots&y_{1p}\\ y_{21}&y_{22}&\cdots&y_{2p}\\ \vdots&\vdots&\ddots&\vdots\\ y_{n1}&y_{n3}&\cdots&y_{np} \end{matrix} \right] \tag{4}$ 其中$p\ll d$。一般$p$取2或者3。通常，计量多元尺度法（Metric MDS）是最小化如下的目标函数 $\sigma(x)= \sum\limits_{i=1}^{n}{\sum\limits_{i=1}^{n}{(d_ij- \rVert \vec{y_i}-\vec{y_j}\rVert)^2}} \tag{5}$ 对于欧式距离，可以被任意旋转和变换，因为这些变换不会改变样本间的距离。所以，对于 $Y$，解是不唯一的。

• 基本的最优化理论

上述的MDS的目标函数可以用如下的优化理论来优化。其基本原理是如下描述。 首先，假设待优化的函数$f(x)$有最优的最小解，但是直接求解$f(x)$的解析解是非常困难的。因此，我们可以找一个简单的，更容易求解最优值的函数$g_y(x)$来代替求解$f(x)$。其中，$g_y(x)$满足如下条件 对于任意的 $x$，有 $g_y(x)\geqslant f(x) \tag{6}$ 其中, $y$ 是一个固定点，并且$g_y(x)$必须着陆于$f(x)$，即$f_y(x)$必须满足如下条件 $g_y(y)=f(y)$ 则，假设$x^*$是$g_y(x)$的最小值，则根据(6)，有$f(x^*)\leqslant g_y(x^*)$，又因为$g_y(x^*)$是函数$g_y(x)$的最小值，则有$g_y(x^*)\leqslant g_y(y)$。所以，我们可以得到如下的一个不等式链： $f(x^*)\leqslant g_y(x^*)\leqslant g_y(y) = f(y) \tag{7}$ 通过(7)我们发现，经过$g_y(x)$函数，$f(x)$朝着下降的方向走去$f(x^*)\leqslant f(y)$。 若我们反复迭代，则会找到函数$f(x)$的一个局部最小值，若$f(x)$是凸函数，则会找到$f(x)$的最小值。

该方法的迭代流程如下：

1. 选择一个初始值$y=y_0$，找到一个函数,使得$g_y(x)$满足公式(6)和公式(7)
2. 第$i+1$步，求解函数$g_y(x)$，得到最小值$y_{i+1}$。

3. 如果$f(y_i)-f(y_{i+1})< \epsilon$，则结束，$f(x)$的最优值是$f(y_{i+1})$；否则，令$y=y_{i+1}$，转到步骤2。

4. 柯西-施瓦茨不等式（Cauchy-Schwartx inequality）

在优化MDS的目标函数的时候，会用到第3节中的基本的最优化理论，而在寻找$g_y(x)$函数的时候，就会用到本小节的柯西-施瓦茨不等式。

首先，先给出柯西-施瓦茨不等式，然后证明其不等式成立。 $(\sum\limits_{i=1}^n x_iy_i)^2 \leqslant (\sum\limits_{i=1}^nx_i^2)(\sum\limits_{i=1}^ny_i^2) \tag{8}$ 不等式成立的条件是 $\frac{x_1}{y_1}=\frac{x_2}{y_2}=\cdots=\frac{x_n}{y_n} \tag{9}$ 证明:

考虑一个一元二次方程 $(x_1t+y_1)^2 +(x_2t+y_2)^2+\cdots+(x_nt+y_n)^2=0 \tag{10}$ 将(10)转化形式如下 $(\sum\limits_{i=1}^nx_i^2)t^2+(2\sum\limits_{i=1}^nx_iy_i)t+\sum\limits_{i=1}^ny_i^2=0 \tag{11}$ 很显然，该方程要不没有实数解，要不就是有重根，所以，其判别式$\Delta\leqslant0$，所以有 $\Delta=(2\sum\limits_{i=1}^nx_iy_i)^2-4(\sum\limits_{i=1}^nx_i^2)(\sum\limits_{i=1}^ny_i^2)\\ =4(\sum\limits_{i=1}^nx_iy_i)^2-4(\sum\limits_{i=1}^nx_i^2)(\sum\limits_{i=1}^ny_i^2)\leqslant0 \tag{12}$ 所以有公式(8)成立。当该方程是重根时，有$\Delta=0$，即$(x_1t+y_1)=(x_2t+y_2)=\cdots=(x_nt+y_n)=0$有公式(9)成立。

证明完毕。 其中，柯西-施瓦茨不等式可以化成如下的形式： $\sum\limits_{i=1}^nx_iy_i\leqslant \sqrt{(\sum\limits_{i=1}^nx_i^2)(\sum\limits_{i=1}^ny_i^2)} \tag{13}$ 我们在优化MDS目标函数的时候，会用到公式(13)。

MDS的python实现

在sklearn机器学习包中，有MDS的相关代码，示例如下：

import numpy as np
import pandas as pd
from sklearn.manifold import MDS
import matplotlib.pyplot as plt

data = np.array([(5,0,0,0,0,1,0,2,1,0),
                 (0,0,3,0,3,0,1,0,0,1),
                 (2,0,0,0,0,0,1,0,0,0),
                 (1,0,1,0,2,0,0,0,0,1),
                 (5,0,2,0,0,4,2,2,3,7),
                 (0,3,0,1,0,0,0,0,0,0),
                 (0,0,0,6,0,0,0,0,0,1),
                 (0,5,0,0,0,0,0,0,0,0),
                 (0,1,0,0,0,0,0,0,0,0),
                 (0,2,0,0,0,0,0,0,0,0)
                ]
               )
index = ['auto1','auto2','auto3','auto4','auto5','moto1','moto2','moto3','moto4','moto5']
columns = ['car','bike','cars','his','tires','she','ive','her','#k','are']
Word = pd.DataFrame(data,index,columns)

mds = MDS()
mds.fit(data)
a = mds.embedding_
plt.scatter(a[0:5,0],a[0:5,1],color='turquoise')
plt.scatter(a[5:10,0],a[5:10,1],color='red')

参考资料

1. 特征哈希(Feature Hashing)
2. Trevor Hastie et al. The Elements of Statistical Learning, 2001.
3. Kilian Weinberger et al. Feature Hashing for Large Scale Multitask Learning, 2010.
4. Joshua Attenberg et al. Collaborative Email-Spam Filtering with the Hashing-Trick, 2009.
5. https://www.zhihu.com/question/264165760/answer/277634591
6. sklearn.feature_extraction.FeatureHasher
7. sklearn学习笔记2 Feature_extraction库
8. 特征选择和稀疏学习
9. 《西瓜书》笔记11：特征选择与稀疏表示（三）
10. 特征选择与稀疏学习
11. https://www.zhihu.com/question/24124122/answer/50403932
12. https://blog.csdn.net/u014595019/article/details/52433754
13. PCA算法详解
14. 主成分分析（PCA）原理详解
15. 主成分分析PCA算法：为什么去均值以后的高维矩阵乘以其协方差矩阵的特征向量矩阵就是“投影”？
16. 用Python的sklearn库进行PCA(主成分分析)
17. 用scikit-learn学习主成分分析(PCA)
18. 独立成分分析（Independent Component Analysis）
19. 独立成分分析 ( ICA ) 与主成分分析 ( PCA ) 的区别在哪里？
20. 独立成分分析ICA系列4:ICA的最优估计方法综述
21. ICA-独立成分分析
22. 独立成分分析Independent component analysis(ICA)
23. 线性判别分析LDA原理总结
24. 一文读懂特征工程
25. 线性判别分析LDA详解
26. LinearDiscriminantAnalysis
27. 用scikit-learn进行LDA降维
28. https://blog.csdn.net/u010705209/article/details/53518772
29. https://blog.csdn.net/u012162613/article/details/42214205
30. https://blog.csdn.net/qianhen123/article/details/40077873
31. https://github.com/ceys/jdml/wiki/ALS
32. 美团点评技术团队之深入FFM原理与实践
33. [深度学习笔记（一）稀疏自编码器] (https://blog.csdn.net/u010278305/article/details/46881443)
34. Field-aware Factorization Machines for CTR Prediction ,Yuchin Juan et al.
35. Factorization Machines, Steffen Rendle et al.[2010]
36. http://deeplearning.stanford.edu/wiki/index.php/UFLDL_Tutorial
37. 局部线性嵌入(LLE)原理总结
38. Locally linear embedding(LLE)局部线性嵌入-降维
39. LocallyLinearEmbedding
40. 用scikit-learn研究局部线性嵌入(LLE)
41. 聚类和降维的区别与联系
42. 聚类算法
43. 受限玻尔兹曼机（RBM）学习笔记
44. 受限制玻尔兹曼机RBM原理简介
45. 从SNE到t-SNE
46. t-SNE完整笔记
47. SNE降维与可视化
48. 比PCA降维更高级 —— t-SNE聚类算法实现指南