第九章 降维 9.1k近邻学习 k近邻（ k-Nearest Neighbor，简称KNN）学习是一种常用的监督学习方法，其工作机制非

常简单：给定测试样本，基于某种距离度量找出训练集中与其靠近的k个训练样本，然后基于k个“邻居”的信息来进行预测。在分类任务中一般使用“投票法”，在回归任务中使用“简单平均法”。还可以基于距离使用加权平均或加权投票。 9.2 低维嵌入 最近邻学习的一个重要建设：任意测试样本附近任意小的距离范围内总能找到一个训练样本，即训练样本的采样密度足够大。然而，这个假设在现实任务中通常很难满足。在低维数空间进行采样还比较容易满足一定条件，而在维数很高时，距离计算有时都面临困难。在高维情况下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习共同面临的障碍， 被称为“维数灾难”。 缓解维数灾难的一个重要途径是降维（dimension reduction），亦称“维数简约”，即通过 某种数学变换将原始高维属性空间转变为一个低维“子空间”，在这个子空间中样本的密度大幅增高，距离计算也变得容易。为什么能降维？这是因为在很多时候，人们观测或收集到的数据样本虽是高维的，但与学习任务密切相关的也许是某个低维分布，即高维空间中的一个低维嵌入。 若要求原始空间中样本之间的距离在低维空间中得以保持，即得到“多维缩放”（Multiple Dimensional Scaling，简称MDS）[Cox，2001]这样一种经典的降维方法。

假定m个样本在原始空间的距离矩阵为mmRD，其元素ijd表示样本ix与jx之间的

距离，原始空间的维数为d。目标是获得样本在d维空间的表示ddRZmd,，且任意两个样本在d维空间中的欧式距离等于原始空间中的距离，即ijjidzz。 令mmTRZZB，其中B为降维后样本的内积矩阵，jTiijzzb，有

jTijiijzzzzd2222

ijjjiibbb2 （1）

为了便于讨论，令降维后的样本Z被中心化，即01miiz。显然矩阵B的行与列之和均为零，即mjmiijbijb110。易知

jjmiijmbBtrd)(12

（2）

iimjijmbBtrd)(12

（3） )(2112Bmtrdmimjij （4）

其中，21)(miizBtr。令 mjijidmd122

.

1

（5）

miijjdmd122

.

1

（6）

mimjijdmd11222

..

1

（7）

于是由（1）和式（2）-（7）可得 )(212..2.2.2ddddbjiijij， （8）

由此即可通过降维前后保持不变的距离矩阵D求取内积矩阵B。 对矩阵B做特征值分解，TVVB，其中),,,(21ddiag为特征值构成的对

角矩阵，d21，V为特征向量矩阵。假定其中有d个非零特征值，它们构成对角矩阵),,,(21ddiag，令V表示相应的特征向量矩阵，则Z可表示为 mdZRVT2

1

。

在现实应用中为了有效降维，往往仅需要降维后的距离与原始空间中的距离尽可能接近，而不必严格等待。此时可取dd个最大特征值构成的对角矩阵来表示Z。 一般来说，欲获得低维子空间，最简单的办法是对原始高维空间进行线性变换。给定d

维空间中的样本mdmRxxxX),,,(

21

，变换后得到dd维空间中的样本

XWZT，

其中ddRW是变换矩阵，mdRZ是样本在低维空间中的表示。基于线性变化的降维方法称为线性降维方法，对W施加不同的约束形成不同的降维方法。 9.3 流形学习 流形学习（manifold learning）是一类借鉴了拓扑流形概念的降维方法，“流形”是在局部与欧式空间同胚的空间，换言之，它在局部具有欧式空间的性质，能用欧式距离来进行距离计算。这给降维方法带来了很大的启发：若低维流形嵌入到高维空间，则数据样本在高维空间的分布虽然看上去非常复杂，但在局部上仍然具有欧式空间的性质，因此，很容易地在局部建立降维映射关系，然后再设法将局部映射关系推广到全局。当维数被降至二维或三维时，能对数据进行可视化展示，因此流形学习也可被用于可视化。 9.3.1 等度量映射 等度量映射（Isometric Mapping，简称Isomap）[Tenembaum et al.2000]的基本出发点，是认为低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性。比如， S曲面上的两点的测地线距离是两点之间的本真距离，显然在高维空间中计算直线距离是不

恰当的。测地线距离不能用高维空间的直线距离计算，但能用近邻距离来近似。这时利用流形在局部上与欧式空间同胚这个性质，对每个点基于欧式距离找出其临近点，然后就能建立一个近邻连接图，图中近邻点之间存在连接，而非近邻点之间不存在连接，于是，计算两点之间测地线距离的问题，就转变为计算近邻连接图上两点之间的最短路径问题。在得到任意亮点的距离后，就可以利用MDS方法来获得样本点在低维空间中的坐标。 需要注意的是，Isomap仅得到了训练样本在低维空间的坐标，对于新样本，如何将其映射到低维空间呢？这个问题的常用解决方案，是将训练样本的高维空间坐标作为输入、低维空间坐标作为输出，训练一个回归学习器来对新样本低维空间坐标进行预测。这显然是一个权宜之计，但目前似乎并没有更好的办法。 对近邻图的构建通常有两种方法，一种是指定近邻点个数，这样得到的近邻图称为k近邻图；另一种方法是指定距离小于事先给定的阈值的点为近邻点，这样得到的近邻图称为近邻图。两种方法均有不足，例如若近邻范围指定的较大，则距离很远的点可能被误认为

是近邻，这样就出现“短路”问题；近邻范围指定的较小，则可能出现“断路”问题。 9.3.2 局部线性嵌入 与Isomap试图保持近邻样本之间的距离不同，局部线性嵌入（Locally Linear Embedding，

简称LLE）[Roweis and Saul,2000]试图保持邻域内样本之间的线性关系。假定样本点ix的坐

标能通过它的邻域样本lkjxxx,,的坐标通过线性组合而重构出来，即 lilkikjijixwxwxwx LLE算法：

给定N个输入向量DiNRxxxxO,,,,21，输出DdNiRydi,,,2,1,。 （1）寻找每个样本点的k个近邻点； （2）计算出样本点的局部重建全脂矩阵，定义误差函数

Nikjijijixwxw11)(min

其中，),,2,1(kjxij为ix的k个近邻点，11kjijw。 令iiiijkjijxwNxw~1，其中),,,(21ikiiixxxN是一个kD阶矩阵， Tikiiiwwww),,,(

21，是一个1k的矩阵。令



iiixxxX,,,是kD维矩阵。

记221)(iiikjijijiiwNxxwxw iiTiiiiiiiwNXNXwwNXwNXwT)()((22

iiSwwT

其中，)()(iTiNXNXS。 引入Lagrange乘子，)11()(TTiiiiwSwwwL

112012)(cSwSwwwLiiii

，

只要求出矩阵S的逆矩阵即可。具体解法如下： 构造一个局部协方差矩阵iQS，其值为 )()(imiTijiijmxxxxQ 于是

1)()()()()()()()()(1112111212212111112111121kkikikikiiikiiiikiiiQQQQQQQQQSwwww

考虑到11kjijw，于是得 

kpkqpqikmjmiijQQw11111

)()(

kkIrrIQQQiii是是正则化参数，此时必须正则化，可能是一个奇异矩阵，实际中,单位矩阵 （3）将所有样本点映射到低维空间中，映射条件满足 2

11)(minNikjijijiywyY

和避免数据集个近邻点，为了固定的是的输出向量是其中Ykykjyxyiijii),,2,1(,

在低维坍塌到坐标原点，满足两个限制条件：单位矩阵）。ddIyyNyNiTiiNii(1,011