Skip to content

14.9 非线性降维和局部多维缩放

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

最近有人提出了一些用于非线性降维的方法,类似主曲面的思想。想法是数据接近一个嵌在高维空间中的固有低维非线性流形(intrinsically low-dimensional nonlinear manifold)。这些方法可以看成是“压扁(flattening)”流形,因此将数据降低至表示流形中相对位置的低维坐标系统中。在信噪比非常高的问题中非常有用(比如,物理系统),而且对于有低信噪比的观测数据不是很有用。

基本的目标在图14.44的左图中进行了说明。数据落在有较大曲率的抛物线附近。经典的MDS不能保持沿着这条曲线的点的顺序,因为它会将处于曲线两端的点看成离得非常近。右图显示了局部多维缩放(local multi-dimensional scaling)的结果,我们将在下面讨论非线性多维缩放的三个方法中的其中一个。这些方法仅仅使用$p$维中点的坐标,不需要流形的其它信息。局部MDS能够很好地保持沿着曲线的点的顺序。

我们将简短地介绍用作非线性降维和流形映射的三个新方法。

等距特征映射算法(ISOMAP)(Tenenbaum et al. 20001)构造了一个图来近似沿着流形的点之间的测地线距离。具体地,对每个数据点,我们找到其邻居——距该点的某个欧式距离范围内的点。我们构造任意两个邻居点间用边相连的图。任意两点的测地线距离则用图中点的最短路径来近似。最终,对图的距离应用经典缩放,来得到低纬映射。

局部线性内嵌(LLE)(Roweis and Saul, 20002)采用完全不同的方式,它试图保持高维数据的局部仿射结构。每个数据点用邻居点的线性组合来近似。于是通过寻找保持局部近似的最优方式构造低维表示。细节非常有趣,所以在这里给出:

  1. 对每个$p$维中的数据点$x_i$,寻找欧式距离的K最近邻$\cal N(i)$
  2. 对每个点用邻居点的混合仿射来近似 其中权重$w_{ik}$满足$w_{ik}=0, k\not\in \cal N(i), \sum_{k=1}^Nw_{ik}=1$。$w_{ik}$是点$k$对$i$点的重构的贡献。注意到为了得到唯一解,我们必须要求$K < p$。
  3. 最后,固定$w_{ik}$,在$d < p$维空间中寻找点$y_i$来最小化

在第三步,我们最小化

其中$\W$是$N\times N$; $\Y$是$N\times d, d < p$。$\hat \Y$的解是$\M=(\I-\W)^T(\I-\W)$的trailing eigenvectors(Issue 59)。因为$\1$是特征值为0的平凡特征向量,所以我们舍弃它并且保留接下来的$d$个。这会产生额外的影响$\1^T\Y=0$,因此嵌入坐标(embedding coordinates)进行了中心化。

局部MDS(Chen and Buja, 20083) 采用最简单的、而且可以说是最直接的方式。定义$\cal N$为邻居点的对称集;具体地,如果点$i$在$i’$的$K$最近邻中,则点对$(i, i’)$在$\cal N$中,反过来也是如此。

weiya注

14.7节中的谱聚类的mutual K-nearest-neighbor graph也有用到$\cal N$。

于是我们构造压力函数

这里$D$是某个较大的常数,$w$是权重。想法是将不是邻居的点看成是距离非常远;这些点对被赋予小权重$w$使得它们不会主导整个压力函数。为了简化表达式,取$w\sim 1/D$,并令$D\rightarrow \infty$。展开式(14.105),得到

其中$\tau =2wD$。式(14.106)试图保持数据的局部性质,而第二项促使非邻居对$(i, i’)$的$z_i,z_{i’}$更远。局部MDS在固定邻居个数$K$以及调整参数$\tau$的情况下,在$z_i$上最小化压力函数(14.106)。

图14.44的右图显示了采用$k=2$个邻居和$\tau = 0.01$的局部MDS的结果。我们采用多个起始值的坐标下降来寻找(非凸)损失函数一个好的最小值。沿着曲线的点的顺序大部分都被保持了。

图14.45显示了LLE方法的一个有趣的应用。数据包含1965张图象,数字化为$20\times 28$的灰白图象。图中展示了LLE的前两个坐标结果,它们解释了摆放位置以及表情的一些变异。类似的图象可以通过局部MDS得到。

在Chen and Buja(2008)3报告的实验中,局部MDS与ISOMAP和LLE相比表现得更好。他们也演示了局部MDS在图象布局方面很有用的应用。有些方法与这里讨论的方法有着紧密的联系,如谱聚类(14.5.3节)和核PCA(14.5.4节)。


  1. Tenenbaum, J. B., de Silva, V. and Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction, Science 290: 2319–2323. 

  2. Roweis, S. T. and Saul, L. K. (2000). Locally linear embedding, Science 290: 2323–2326. 

  3. Chen, L. and Buja, A. (2008). Local multidimensional scaling for nonlinear dimension reduction, graph drawing and proximity analysis, Journal of the American Statistical Association. 

Comments