图像降维之MDS特征抽取方法

   作者：龚赛          

编辑：龚赛          

前  言

MDS，中文名叫“多维缩放”，是一种经典的降维方法，同时也是数据可视化的一种手段。最早起源于当我们仅能获得物体之间的相似性矩阵时，如何由此来重构它们的欧几里得坐标，如对一个国家的许多城市而言，假如我们不知道它们的经纬度信息，却知道所有城市两两之间的距离，就可以通过MDS方法重现它们的空间信息。MDS的基本思想很简单，要求原始空间中样本之间的距离在低维空间中得到保持。下面我们将对MDS的原理进行学习。

章节目录

• 准备知识

• 算法推导

• 算法步骤

• 实验

• 总结

01

准备知识

实对称矩阵的特征分解性质

任意的对称矩阵都有N个线性无关的特征向量，并且可以正交单位化。实对称矩阵A可被分解成：

其中Q为正交矩阵，为实对角矩阵。

02

算法推导

给定m个样本的距离矩阵，其中第i行第j列的元素为样本到的距离。目标是获得低维表示，其中，且保持任意两个样本在维空间的欧氏距离不变。

从已知的条件中，我们唯一能够得到降维后的样本与未降维前的样本之间的关系如下(1)式：

为了更清晰地观察、与的关系，将(1)式左边平方，得(2)式：

从(2)式可以看出，与、各自的模以及内积有关，为了能够统一表示这种关系，这里引入内积矩阵，其中，(2)式变换成(3)式：

显然，我们接下来的目标是得到B中任一元素的解析解。在不影响结果正确性的前提下，为了方便后续计算，令降维后的样本Z被中心化，即，可以得到，同理。则由(3)式可以得到式(4)(5)(6)：

同理，

其中表示矩阵的迹(trace)。

由(4)(5)(6)式得，，，。

为了表述清晰，令

联合(3)和(4)(9)式，得(10)式：

至此，已得到B和D的全部关系。接下来便是由B得到最终目标Z。

首先，我们可以判断出B是实对称矩阵，由实对称矩阵性质可知，，其中为特征值构成的对角矩阵，，V是特征向量矩阵。

一般降维任务总是取作为目标维度，所以取d'个最大特征值构成对角矩阵，对应的特征向量矩阵为，则

03

算法步骤

输入：距离矩阵，其元素为样本到的距离；低维空间维数。

过程：

1: 根据(7)(9)式计算，，；

2: 根据(10)式计算内积矩阵B；

3: 对B做特征值分解；

4: 取为个最大特征值所构成的对角矩阵，为相应的特征向量矩阵。

输出：

04

实验

实验代码

"""
MDS : Multi-dimensional Scaling
Refercences :
[1]周志华.机器学习[M].清华大学出版社,2016:425.
[2]http://scikit-learn.sourceforge.net/dev/modules/generated/sklearn.manifold.MDS.html

Author : Ggmatch
Date : 2019/4/7
"""
from time import time

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from matplotlib.ticker import NullFormatter

from sklearn import manifold, datasets

# 制造样本
n_points = 1000
X, color = datasets.samples_generator.make_s_curve(n_points, random_state=0)
n_neighbors = 10

fig = plt.figure(figsize=(5, 5))  #画板
gs = fig.add_gridspec(1,2)  #共2副子图
ax1 = fig.add_subplot(gs[0,0], projection='3d')  #第一幅子图表示原始样本分布
ax1.scatter(X[:, 0], X[:, 1], X[:, 2], c=color, cmap=plt.cm.Spectral)

# MDS降维
n_components = 2

t0 = time()  #计时开始
mds = manifold.MDS(n_components, max_iter=100, n_init=1)  #建立MDS模型
Y = mds.fit_transform(X)
t1 = time()  #计时结束
ax2 = fig.add_subplot(gs[0,1])
ax2.scatter(Y[:, 0], Y[:, 1], c=color, cmap=plt.cm.Spectral)  #第2副子图表示降维后样本分布
ax2.set_title("MDS (%.2g sec)" % (t1 - t0))
ax2.xaxis.set_major_formatter(NullFormatter())
ax2.yaxis.set_major_formatter(NullFormatter())

plt.show()

实验效果

05

总结

1）高维空间中对两个样本用欧式距离求直线距离，很多时候并不可取（如实验案例取得是流形空间），两点之间应该用“测地线”距离。改进算法为Isomap(Isomatric Mapping)。

2）MDS其实分为Metric MDS与Non-Metric MDS，本文讲述的是Metric MDS，通过样本之间的欧氏距离来近似代表相似度的思路，而Non-Metric MDS是通过点与点之间距离的单调映射来近似原有的距离。实际应用中，样本之间的距离越近，相似度越大，反之亦然。

References:

[1]https://baike.baidu.com/item/%E7%89%B9%E5%BE%81%E5%88%86%E8%A7%A3/12522621?fr=aladdin

[2]周志华.机器学习[M].清华大学出版社,2016:425.

[3]http://scikit-learn.sourceforge.net/dev/modules/generated/sklearn.manifold.MDS.html

[4]Cox, T.F., Cox, M.A.A. (2001). Multidimensional Scaling. Chapman and Hall.

[5]http://blog.sina.com.cn/s/blog_501162be0102v37l.html

END

机器学习算法工程师

---

                            一个用心的公众号

长按，识别，加关注

进群，学习，得帮助

你的关注，我们的热度，

我们一定给你学习最大的帮助