多维缩放（Multiple Dimensional Scaling，MDS）

1 绪论

假设在任何测试样本附近的任何小距离内总能找到训练样本，即训练样本的收集密度足够大，或称为密集采样（dense sample）。

然而，这种假设在实际任务中通常很难满足，例如?=0.001，如果只考虑单个属性，则归一化后的属性取值范围内只平均分布1000个样本点，使任何测试样本接近0.在001距离内总能找到训练样本，此时最近的邻近分类器(1NN）贝叶斯最优分类器的错误率不超过贝叶斯的两倍。然而，这只是属性维数为1的情况，如果有更多的属性，情况就会发生显著变化。例如，假设属性维数为20，如果样本符合密采样条件，则至少需要 ( 1 0 3 ) 20 = 1 0 60 (10^3)^{20}=10^{60} (103)20=1060样本。在实际应用中，属性维度通常是成千上万的，为了满足密集采样条件所需的样本数量是无法实现的天文数字。此外，许多学习方法都涉及到距离计算，而高维空间会给距离计算带来很大的麻烦。例如，当维度很高时，甚至不再容易计算内积。

数据样本稀疏、距离计算困难等问题是所有机器学习方法面临的严重障碍，被称为维数灾难（curse of dimensionality）。

以一个简单的例子，我们考虑设计一个分类器来区分猫和狗的照片，我们提取头发和形状作为特征，但只有两个特征似乎不能很好地区分猫和狗，所以最好考虑增加更多的特征吗？

如图所示，我们可以在三维空间中使用超平面对猫和狗进行很好的分类。如果超平面映射到二维平面，如第三图所示。

这样，增加更多特征的效果似乎越来越好。

事实上，从下图可以看出，分类器的性能随着特征数量的变化而增加，但在一定值之后，性能不会上升而是下降。这种情况被称为过拟合，即在训练集中拟合良好，但缺乏足够的泛化能力。过拟合通常是维度灾难的直接体现。

那么，有没有办法将高维空间中的数据映射到低维子空间？（subspace）而且数据还能保持高维空间的特性，能线性区分吗？

“降维”（dimension reduction），它是缓解维数灾难的重要途径，也被称为维数简单。它通常通过某种数学转换将原始的高维属性空间转化为低维的子空间 ，样本密度在这个子空间中大大提高，距离计算变得更容易。

2 多维缩放

多维缩放（Multiple Dimensional Scaling，MDS）许多最初的理论都是由数学心理学家发展起来的，他们在《心理测量学》杂志上发表了许多发现。尽管MDS它起源于行为科学，但现在越来越流行，并广泛应用于各种应用领域。这种流行反映在许多基于计算机的统计数据包中。

多维缩放，即MDS是一组对象之间的距离或差异的视觉表达。 对象可以是颜色、面孔、地图坐标和各种真实的东西。除了将差异解释为图中的距离外，MDS也可作为高维数据的降维技术。简而言之，MDS保持这些差异的主要目的是降维。 MDS算法很简单，一句话就是保持样本在原空间和低维空间之间的距离不变。

3 MDS算法解析

假设样本在原始空间中的距离矩阵是 ?? = ( ?? ?? ?? ) ?? × ?? ??=(??_{???} )_{??×??} D=(dij​)N×N​: 𝐷 = [ d 1 , 1 d 1 , 2 ⋯ d 1 , n d 2 , 1 d 2 , 2 ⋯ d 2 , n ⋮ ⋮ ⋱ ⋮ d n , 1 d n , 2 ⋯ d n , n ] 𝐷=\begin{bmatrix} {d_{1,1}}&{d_{1,2}}&{\cdots}&{d_{1,n}}\\ {d_{2,1}}&{d_{2,2}}&{\cdots}&{d_{2,n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {d_{n,1}}&{d_{n,2}}&{\cdots}&{d_{n,n}}\\ \end{bmatrix} D=⎣⎢⎢⎢⎡​d1,1​d2,1​⋮dn,1​​d1,2​d2,2​⋮dn,2​​⋯⋯⋱⋯​d1,n​d2,n​⋮dn,n​​⎦⎥⎥⎥⎤​ 其中 𝑑 𝑖 𝑗 = ‖ x ⃗ 𝑖 − 𝑥 ⃗ 𝑗 ‖ 𝑑_{𝑖𝑗}=‖\vec x_𝑖 − \vec 𝑥_𝑗 ‖ dij​=‖x i​−x j​‖为样本 𝑥 ⃗ 𝑖 \vec 𝑥_𝑖 x i​到样本$𝑥_𝑗 的 距 离 。 我 们 的 目 标 是 获 得 样 本 在 的距离。 我们的目标是获得样本在 的距离。我们的目标是获得样本在𝑛^{′$维空间的表示$𝑍∈ℝ}{𝑁×𝑛^′}$， 𝑛 ′ ≤ 𝑛 𝑛^′≤𝑛 n′≤n，且任意两个样本在 𝑛 ′ 𝑛^′ n′维空间中的欧式距离等于原始空间中的距离，即 ‖ 𝑧 𝑖 − 𝑧 𝑗 ‖ = 𝑑 𝑖 𝑗 ‖𝑧_𝑖−𝑧_𝑗 ‖=𝑑_{𝑖𝑗} ‖zi​−zj​‖=dij​。

令 𝐵 = 𝑍 𝑍 𝑇 ∈ R 𝑁 × 𝑁 𝐵=𝑍𝑍^𝑇∈ℝ^{𝑁×𝑁} B=ZZT∈RN×N，即： B = [ b 1 , 1 b 1 , 2 ⋯ b 1 , N b 2 , 1 b 2 , 2 ⋯ b 2 , N ⋮ ⋮ ⋱ ⋮ b N , 1 b N , 2 ⋯ b N , N ] B=\begin{bmatrix} {b_{1,1}}&{b_{1,2}}&{\cdots}&{b_{1,N}}\\ {b_{2,1}}&{b_{2,2}}&{\cdots}&{b_{2,N}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {b_{N,1}}&{b_{N,2}}&{\cdots}&{b_{N,N}}\\ \end{bmatrix} B=⎣⎢⎢⎢⎡​b1,1​b2,1​⋮bN,1​​b1,2​b2,2​⋮bN,2​​⋯⋯⋱⋯​b1,N​b2,N​⋮bN,N​​⎦⎥⎥⎥⎤​ 其中 𝑏 𝑖 𝑗 = 𝑧 𝑖 ⋅ 𝑧 𝑗 𝑏_{𝑖𝑗}=𝑧_𝑖·𝑧_𝑗 bij​=zi​⋅zj​为降维后样本的内积。 则根据降维后样本的欧氏距离保持不变有： 𝑑 𝑖 𝑗 2 = ‖ 𝑧 𝑖 − 𝑧 𝑗 ‖ 2 = ‖ 𝑧 𝑖 ‖ 2 + ‖ 𝑧 𝑖 ‖ 2 − 2 𝑧 𝑖 𝑇 𝑧 𝑗 = 𝑏 𝑖 𝑖 + 𝑏 𝑗 𝑗 − 2 𝑏 𝑖 𝑗 𝑑_{𝑖𝑗}^2=‖𝑧_𝑖−𝑧_𝑗 ‖^2=‖𝑧_𝑖 ‖^2+‖𝑧_𝑖 ‖^2−2𝑧_𝑖^𝑇 𝑧_𝑗=𝑏_{𝑖𝑖}+𝑏_{𝑗𝑗}−2𝑏_{𝑖𝑗} dij2​=‖zi​−zj​‖2=‖zi​‖2+‖zi​‖2−2ziT​zj​=bii​+bjj​−2bij​

假设降维后的样本集𝑍被中心化，即 ∑ 𝑖 = 1 𝑁 𝑧 𝑖 = 0 \sum_{𝑖=1}^𝑁{𝑧_𝑖} =0 ∑i=1N​<