Skip to content

14.8 多维缩放

原文 The Elements of Statistical Learning
翻译 szcf-weiya
时间 2017-09-04
更新 2018-01-22
状态 Done

自组织图和主曲线以及主曲面都是将 $\IR^p$ 中的数据点映射到低维流形中。多维缩放(MDS)的目标也是类似的,但是是以一种不同的方式来解决这个问题。

我们以观测值 $x_1, x_2,\ldots, x_N\in R^p$ 开始,令 $d_{ij}$ 为观测 $i$ 和 $j$ 之间的距离。通常我们选择欧式距离$d_{ij}=\Vert x_i-x_j\Vert$,但是也可能采用其它的距离。另外,在有些应用中,我们可能甚至没有数据点$x_i$,仅仅有不相似性的测量$d_{ij}$(见14.3.10节)。举个例子,在一项酒的口感的试验中,$d_{ij}$可能是某个体对酒$i$和$j$口感的不同的一个度量,并且该个体对所有酒$i$和$j$都采用这样的度量。MDS仅仅需要不相似性$d_{ij}$,这与需要数据点$x_i$的SOM和主曲线、主曲面不同。

多维缩放寻找值$z_1,z_2,\ldots,z_N\in R^k$来最小化压力函数(stress function)

这被称为最小二乘缩放(least squares scaling)或者Kruskal-Shephard缩放。思想是寻找尽可能保持成对距离的数据的低维近似。注意到近似是对距离而言,而不是平方距离(这会导致计算有点复杂)。可以采用梯度下降法来进行最小化$S_M$。

最小二乘缩放的一个变种被称为Sammon mapping,它是对下式进行最小化

这里更重视保留越小的成对距离。

在经典缩放(classical scaling)中,我们从相似性$s_{ii’}$开始:经常使用中心化后的内积$s_{ii’}=\langle x_i-\bar x,x_{i’}-\bar x\rangle$。问题则变成了在$z_1,z_2,\ldots,z_N\in R^k$上最小化下式

这是很吸引人的,因为有个用特征向量表示的显式解:见练习14.11。如果我们有距离数据,而不是内积数据,并且是欧式距离,则可以将它们转换为中心化的内积,参见18章中的式(18.31)。如果事实上相似性为中心化的内积,则经典缩放正好与主成分等价,主成分本质上是线性降维技术。经典缩放不等价于最小二乘缩放;它们的损失函数不同,并且映射可以是非线性的。

最小二乘缩放和经典缩放都被称作度量(metric)缩放方法,在某种意义下,实际的非相似性或者相似性是近似的。Shephard-Kruskal非度量缩放有效地仅仅使用了秩(排名)。非度量缩放在$z_i$和任意的递增函数$\theta$上最小化压力函数

当$\theta$固定,我们通过梯度下降在$z_i$上最小化。当$z_i$固定,采用保序回归(isotonic regression)来寻找对$\Vert z_i-z_{i’}\Vert$最好的单调近似$\theta(d_{ii’})$。一直迭代这些步骤直到解达到稳定。

和自组织图和主曲面一样,多维缩放也是在低维坐标系统中表示高维数据。主曲面和SOM则更进一步,采用低维的流形来近似原来的数据,在低维的坐标系统中进行参量化。在主曲面和SOM中,原特征空间中相离比较近的点在流形上也映射在一起,但是特征空间中距离远的点也可能映射到一起。这在多维缩放中不太可能发生,因为它明确地试图保持所有的成对距离。

图14.43显示了对半球例子的经典缩放的前两个MDS坐标。簇之间的分类是很明显的,并且红色簇紧的特性也是显然的。

Comments