数据降维问题

在很多应用中，数据的维数会很高。以图像数据为例，我们要识别32x32的手写数字图像，如果将像素按行或者列拼接起来形成向量，这个向量的维数是1024。高维的数据不仅给机器学习算法带来挑战，而且导致计算量大，此外还会面临维数灾难的问题（这一问题可以直观的理解成特征向量维数越高，机器学习算法的精度反而会降低）。人所能直观看到和理解的空间最多是3维的，为了数据的可视化，我们也需要将数据投影到低维空间中，因此就需要有数据降维这种算法来完成此任务。

例如，下图是将0-9这10个手写数字投影到3维空间中后的结果（来自SIGAI云端实验室）。从图中我们可以清晰的看到这些手写数字在3维空间中的分布，每一个类一般聚集在某一区域内。例如7位于空间的左上角，而6则位于右下角。

在机器学习算法中，数据降维算法是一个大家族，既有有监督学习的版本，也有无监督学习的版本；既有线性的降维算法，也有非线性的降维算法。

最经典的数据降维算法要数PCA（主成分分析），这是一种线性降维算法，而且是无监督的，它通过线性变换将样本投影到低维空间中：

y = Wx

其中，x是输入向量，为n为向量，W是m行n列的投影矩阵，将x左乘它，可以得到一个m维的结果向量y。一般情况下，m远小于n，这样就将一个向量变换成另外一个更低维的向量，从而完成数据降维。PCA的矩阵W是通过样本学习得到的，其依据是最小化重构误差。

PCA是一种线性降维技术，对于非线性数据具有局限性，而在实际应用中很多时候数据是非线性的。此时可以采用非线性降维技术，它们都通过一个非线性的映射函数将输入向量x映射成一个更低维的向量y：

问题的关键是这个非线性映射函数如何得到，一般来说，它要使得数据降维之后保持之前的某些结构信息。非线性降维算法的典型代表有核PCA（KPCA，核主成分分析），神经网络（如自动编码器），流形学习等。在本文中我们重点介绍流形学习算法。

什么是流形？

流形（manifold）是几何中的一个概念，它是高维空间中的几何结构，即空间中的点构成的集合。可以简单的将流形理解成二维空间的曲线，三维空间的曲面在更高维空间的推广。下图是三维空间中的一个流形，这是一个卷曲面：

2维空间中的曲线，3维空间中的曲线可以看做是2维和3维空间中的1维流形，因为曲线是1维的。而3维空间中的曲面可以看做是2维的流形，因为曲面是2维的。n维空间中的m维流形就是具有m维几何形状的一个子集，在这里，m小于n。

在一般的流形学习算法中，我们并没有过多的用到微分几何，拓扑等复杂的数学理论，因此在本文中我们不对流形的数学理论做过多的阐述。

什么是流形学习？

很多应用问题的数据在高维空间中的分布具有某种几何形状，即集中在某个低维的流形附近。对于前面所说的32x32的手写数字图像，数字7的图像在1024维空间中应该聚集在某一个形状的几何体周围（如带状区域，球面），其他的类别也是如此。

流形学习（manifold learning）假设数据在高维空间的分布位于某一更低维的流形上，基于这个假设来进行数据的分析。对于降维，要保证降维之后的数据同样满足与高维空间流形有关的几何约束关系。除此之外，流形学习还可以用实现聚类，分类以及回归算法。

假设有一个N维空间中的流形M，即M为N维欧氏空间的一个真子集：

流形学习降维算法要实现的是如下映射：

其中n<  组成，它们分布在D维空间中的一个流形附近。每个数据点和它的邻居位于或者接近于流形的一个局部线性片段（平面，体现了线性，类似于微积分中的以直代曲的思想）上，即可以用邻居点的线性组合来重构，组合系数刻画了局部面片的几何特性：

权重  为第j个数据点对第i个点的组合权重，这些点的线性组合被用来近似重构数据点i。权重系数通过最小化下面的重构误差确定：

在这里还加上了两个约束条件：每个点只由它的邻居来重构，如果  不在  的邻居集合里则权重值为0，这体现了局部性。另外限定权重矩阵的每一行元素之和为1，即：

这是一个带约束的优化问题，求解该问题可以得到权重系数。这一问题和主成分分析要求解的问题类似。可以证明，这个权重值对平移、旋转、缩放等几何变换具有不变性。

假设算法将向量从D维空间的x映射为d维空间的y。每个点在d维空间中的坐标由下面的最优化问题确定：

这里的权重和上一个优化问题的值相同，在前面已经得到。优化的目标是  ，这个优化问题等价于求解稀疏矩阵的特征值问题。得到y之后，即完成了从D维空间到d维空间的非线性降维。下面是整个过程的示意图：

下图为用LLE算法将手写数字图像投影到3维空间后的结果（来自SIGAI云端实验室）：

拉普拉斯特征映射

拉普拉斯特征映射[2]（简称LE）是基于图论的方法。它从样本点构造带权重的图，然后计算图的拉普拉斯矩，对该矩阵进行特征值分解得到投影变换矩阵。

图是离散数学和数据结构中的一个概念。一个图由节点（也称为顶点）和边构成，任意两个节点之间可能都有边进行连接。边可以带有值信息，称为权重，例如两点之间的距离。下图是一个简单的无向图：

上面这个图有5个顶点，5条边，每条边都有权重值，如顶点1和3之间的边的权重为3。图的边可以是有向的，也可以是无向的，前者称为有向图，后者称为无向图。我们可以将地图表示成一个图，每个地点是节点，如果两个地点之间有路连接，则有一条边。如果这条路是单行线，则边是有向的，否则是无向的。

一个图所有节点之间的边的权重构成的矩阵称为邻接矩阵。假设i和j为图的顶点，  为边(i, j)的权重，由它构成的矩阵W称为邻接矩阵。显然，无向图的邻接矩阵是一个对称矩阵。如果两个顶点之间没有边，则邻接矩阵的元素为0。下面是上图中这个图的邻接矩阵：

节点的度定义为包含一个顶点的边的数量，对于有向图它还分为出度和入度，出度是指从一个顶点射出的边的数量，入度是连入一个节点的边的数量。由于边可以带有权重，因此可以定义带权重的度。定义节点i的带权重的度为与该节点相关的所有边的权重之和：

定义矩阵D为一个对角矩阵，其主对角线元素为每个顶点带权重的度：

其中n为图的顶点数。图的拉普拉斯矩阵定义为：

L = D -W

无向图的拉普拉斯矩阵是对称矩阵，另外可以证明它是半正定矩阵，因此所有特征值为非负实数。降维变换通过对拉普拉斯矩阵进行特征值分解得到。下面给出矩阵半正定的证明。对于任意的非0向量f，有：

因此拉普拉矩阵半正定。下面介绍通过拉普拉斯矩阵进行数据降维的具体做法。

假设有一批样本点  ，它们是  空间的向量，降维的目标是将它们变换为更低维的  空间中的向量  ，其中m<  ，其中M为嵌入空间中的一个流形。

算法为样本点构造加权图，图的节点是每一个样本点，边为每个节点与它的邻居节点之间的相似度，每个节点只和它的邻居有连接关系。

算法的第一步是构造图的邻接关系。如果样本点  和样本点  的距离很近，则为图的节点i和节点j建立一条边。判断两个样本点是否解接近的方法有两种。第一种是计算二者的欧氏距离，如果距离小于某一值  则认为两个样本很接近：

其中是一个人工设定的阈值。第二种方法是使用近邻规则，如果节点i在节点j最近的n个邻居节点的集合中，或者节点j在节点i最近的n个邻居节点的集合中，则认为二者距离很近。

第二步是计算边的权重，在这里也有两种选择。第一种方法为如果节点i和节点j是联通的，则它们之间的边的权重为：

否则  _=_0。其中t是一个人工设定的大于0的实数。第二种方式是如果节点i和节点j是联通的则它们之间的边的权重为1，否则为0。

第三步是特征映射。假设构造的图是联通的，即任何两个节点之间都有路径可达，如果不联通，则算法分别作用于每个联通分量上。根据前面构造的图计算它的拉普拉斯矩阵，然后求解如下广义特征值和特征向量问题：

由于是实对称矩阵半正定矩阵，因此特征值非负。假设  是这个广义特征值问题的解，它们按照特征值的大小升序排列，即：

去掉值为0的特征值  ，用剩下部分特征向量为行来构造投影矩阵，将向量投影到以它们为基的空间中。下图是拉普拉斯特征映射对三维数据进行降维的一个例子：

上图中左侧为三维空间中的样本分布，右图为降维后的结果。这种变换起到的效果大致上相当于把三维空间中的曲面拉平之后铺到二维平面上。

局部保持投影

局部保持投影（简称LPP）[3]思路和拉普拉斯特征映射类似，也是一种基于图论的方法。

假设有样本集  ，它们是  空间中的向量。这里的目标是寻找一个变换矩阵A，将这些样本点映射到更低维的  空间，得到向量，使得  能够代表  ，其中l<

假设  其中M是空间中的一个流形。

算法的第一步是根据样本构造图，这和拉普拉斯特征映射的做法相同，在这里不再重复介绍。

第二步是特征映射，计算如下广义特征向量问题：

矩阵L和D的定义与计算方式和上一节相同，矩阵X是将样本按列排列形成的。假设上面广义特征向量问题的解为  ，它们对应的特征值满足：

要寻找的降维变换矩阵为：

这样  是一个l维的向量，A是一个nxl的矩阵。对向量左乘矩阵A的转置即可完成数据的降维。

等距映射

等距映射（Isomap）[4]使用了微分几何中测地线的思想，它希望数据在向低维空间映射之后能够保持流形上的测地线距离。直观来看，就是将数据投影到低维空间之前，保持数据点之间的相对远近关系。

测地线是微分几何中的一个概念，源自于大地测量学，是地球上任意两点之间在球面上的最短路径。在三维空间中两点之间的最短距离是它们之间线段的长度，但如果要沿着地球表面走，最短距离就是测地线的长度，因为我们不能从地球内部穿过去。这里的测地线就是球面上两点之间大圆上劣弧的长度，高中的立体几何中我们就知道了这一结论。坐过长途国际航班的同学可能都知道，我们要从中国去美国，飞机飞的并不是一条直线，而是一条弧线，这大致上就是测地线（事实上不是严格的测地线，因为还要考虑出故障时有备降点等复杂因素）：

等距映射算法计算任意两个样本之间的测地距离，然后根据这个距离构造距离矩阵。最后通过距离矩阵求解优化问题完成数据的降维，降维之后的数据保留了原始数据点之间的距离信息。

在这里测地线距离通过图构造，是图的两个节点之间的最短距离。算法的第一步构造样本集的邻居图，这和前面介绍的两种方法相同。如果两个数据点之间的距离小于指定阈值或者其中一个节点在另外一个节点的邻居集合中，则两个节点是联通的。假设有N个样本，则邻居图有N个节点。邻居图的节点i和j之间边的权重为它们之间的距离_wij_，距离的计算公式可以有多种选择。

第二步计算图中任意两点之间的最短路径长度，可以通过经典的Dijkstra算法实现。假设最短路径长度为  ，由它构造如下矩阵：

其元素是所有节点对之间的最短路径长度。算法的第三步根据矩阵D_G_构造d维投影，这通过求解如下最优化问题实现：

优化的目标是，降维之前任意两点间的最短距离，与降维之后这两点间的最短距离，要尽可能接近。这个问题的解  即为降维之后的向量。这个目标函数的意义是向量降维之后任意两点之间的距离要尽量的接近在原始空间中这两点之间的最短路径长度，因此可以认为降维尽量保留了数据点之间的测地距离信息。我们可以形象的把这个过程理解成将3D的地球仪投影到2D的平面地图上：

投影之前，美国离中国的距离远，泰国离中国的距离近，投影之后要保持这种距离关系：

实际应用

从2000年之后，在很长一段时间内，流形学习是机器学习领域里的一个研究热点，它在理论上非常优美，也比较完善，但遗憾的是在实际应用中很少被使用。下面我们以它在人脸识别中的应用为例来说明[5]：

与使用PCA和LDA的算法类似，在这里将人脸图像按照像素拼接起来形成一个高维的向量，然后用拉普拉斯特征映射这样的流形降维算法将它们降到低维空间中，然后进行分类。关键的一步是这个降维过程。

参考文献

[1] Roweis, Sam T and Saul, Lawrence K. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500). 2000: 2323-2326.

[2] Belkin, Mikhail and Niyogi, Partha. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation. 15(6). 2003:1373-1396.

[3] He Xiaofei and Niyogi, Partha. Locality preserving projections. NIPS. 2003:234-241.

[4] Tenenbaum, Joshua B and De Silva, Vin and Langford, John C. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500). 2000: 2319-2323.

[5] He, Xiaofei, et al. Face recognition using Laplacianfaces. Pattern Analysis and Machine Intelligence, IEEE Transactions on 27.3 (2005): 328-340.

推荐阅读：
关注SIGAICN公众号，回复文章获取码，即可获得全文链接
[1] 机器学习-波澜壮阔40年 【获取码】SIGAI0413.
[2] 学好机器学习需要哪些数学知识？【获取码】SIGAI0417.
[3] 人脸识别算法演化史 【获取码】SIGAI0420.
[4] 基于深度学习的目标检测算法综述 【获取码】SIGAI0424.
[5] 卷积神经网络为什么能够称霸计算机视觉领域？【获取码】SIGAI0426.
[6] 用一张图理解SVM的脉络 【获取码】SIGAI0428.
[7] 人脸检测算法综述 【获取码】SIGAI0503.
[8] 理解神经网络的激活函数 【获取码】SIGAI0505.
[9] 深度卷积神经网络演化历史及结构改进脉络-40页长文全面解读 【获取码】SIGAI0508.
[10] 理解梯度下降法 【获取码】SIGAI0511.
[11] 循环神经网络综述—语音识别与自然语言处理的利器 【获取码】SIGAI0515.
[12] 理解凸优化 【获取码】SIGAI0518.
[13] 【实验】理解SVM的核函数和参数 【获取码】SIGAI0522.
[14] 【SIGAI综述】行人检测算法 【获取码】SIGAI0525.
[15] 机器学习在自动驾驶中的应用—以百度阿波罗平台为例(上)【获取码】SIGAI0529.
[16] 理解牛顿法 SIGAI 2018.5.31
[17] 【群话题精华】5月集锦—机器学习和深度学习中一些值得思考的问题 【获取码】SIGAI0601.
[18] 大话Adaboost算法 【获取码】SIGAI0602.
[19] FlowNet到FlowNet2.0：基于卷积神经网络的光流预测算法 【获取码】SIGAI0604.
[20] 理解主成分分析(PCA)【获取码】SIGAI0606.
[21] 人体骨骼关键点检测综述 【获取码】SIGAI0608.
[22] 理解决策树 【获取码】SIGAI0611.
[23] 用一句话总结常用的机器学习算法 【获取码】SIGAI0613.
[24] 目标检测算法之YOLO 【获取码】SIGAI0615.
[25] 理解过拟合 【获取码】SIGAI0618.
[26] 理解计算：从√2到AlphaGo ——第1季 从√2谈起 【获取码】SIGAI0620.
[27] 场景文本检测——CTPN算法介绍 【获取码】SIGAI0622.
[28] 卷积神经网络的压缩和加速 【获取码】SIGAI0625.
[29] k近邻算法 【获取码】SIGAI0627.
[30] 自然场景文本检测识别技术综述 【获取码】SIGAI0629.
[31] 理解计算：从√2到AlphaGo ——第2季 神经计算的历史背景 【获取码】SIGAI0702.
[32] 机器学习算法地图 【获取码】SIGAI0704.
[33] 反向传播算法推导-全连接神经网络 【获取码】SIGAI0706.
[34] 生成式对抗网络模型综述 【获取码】SIGAI0709.
[35] 怎样成为一名优秀的算法工程师【获取码】SIGAI0711.
[36] 理解计算：从√2到AlphaGo ——第3季 神经网络的数学模型【获取码】SIGAI0702.
[37] 人脸检测算法之S3FD 【获取码】SIGAI6
[38]基于深度负相关学习的人群计数方法 【获取码】SIGAI0718