3.3 数据降维
3.3.1 基本思想与方法
当尝试使用机器学习解决实际问题时，遇到的最大问题往往不是算法上的问题，而是数据上的问题。有时会苦恼于没有数据，而有时又会因为数据太多而陷入“幸福”的困扰。
在前文学习算法时，可以看到许多算法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦。实际上，在高维空间中出现的数据样本稀疏、距离计算困难等问题是所有机器学习方法共同面临的问题，被称为“维度灾难”“维度诅咒”“维度危机”等。尤其是当高维空间数据计算过于复杂或拟合困难时，就需要考虑通过降维的方式降低计算难度，降低算法模型的拟合成本。
1.基本思想
在机器学习领域中的降维是指采用某种映射方法，将原高维空间中的数据映射到低维空间中。降维的本质是学习一个映射函数，如式（3-8）所示。
其中x是原始数据点的表达，y是数据点映射后的低维向量表达，通常y的维度小于x的维度。若y的维度大于x的维度，则称为升维。f可能是显式或隐式、线性或非线性的降维方式。
数据降维的目的从直观上是算法处理的维度降低了，便于计算和可视化，但更深层次的意义在于实现了有效信息的提取，减少了无用信息对算法的干扰。目前，大部分降维算法处理的数据都是向量，也有一些降维算法处理的是高阶张量。
2.降维方法
降维方法可以进一步细分为变量选择和特征提取两类方式。变量选择是指通过不同的方法选择合适的数据变量；特征提取则是通过线性方式或非线性方式完成特征的提取，如图3-6所示。
3.3.2 变量选择
变量选择的前提是数据中含有大量冗余或无关变量（或称特征、属性、指标等），旨在从原有变量中找出主要变量，这些方法包括丢失值比例、低方差过滤等。
1.丢失值比例（Missing Value Ratio）
前文曾介绍过多种补齐缺失值的方法，但是当缺失值在数据集中的占比过高时，则可以设置一个阈值，如果缺失值占比高于阈值，则删除它所在的列。
2.低方差过滤（Low Variance Filter）
如果数据中的某些数据值非常相近，则其对算法的价值可能并不是特别大。低方差过滤可以计算样本中每个特征值所对应的方差，如果低于阈值，则进行过滤。
图3-6
3.高相关过滤（High Correlation Filter）
如果两个变量之间具有相似的趋势并且可能携带类似的信息，则表明它们具有高相关性。这类变量的存在会降低某些算法的性能。例如，在线性模型或逻辑回归中计算独立数值变量之间的相关性，如果相关系数超过某个阈值，则删除其中一个变量，当然，应尽可能保留与目标变量相关的变量。
4.随机森林（Random Forest）
随机森林是一种使用非常广泛的变量选择方法，通过随机森林可自动计算出各个变量特征的重要性，筛选出较小的特征子集。随机森林具有较高的准确性，既能处理离散数据，也能处理连续数据。
5.反向特征消去（Backward Feature Elimination）
反向特征消去是从效果的角度反向消除特征。例如，对于含有K个特征变量的数据集，首先对K个特征变量进行模型生成，然后逐一移除其中一个特征，对剩余K-1个特征变量进行模型生成，接着对原始模型和移除其中一个特征变量的模型效果进行比对，最后把对模型性能影响较小的变量移除。
6.前向特征选择（Forward Feature Selection）
前向特征选择与反向特征消去的过程相反，前向特征选择是找到对模型性能影响最大的特征，然后逐步新增特征训练模型。首先对每一个特征变量进行模型训练，得到K个模型；然后选择K个模型中性能最好的特征变量作为初始变量，把其余变量作为与该变量的一对一组合，进行模型训练；接着选择效果最好的一组特征变量作为下一轮的初始变量，依次迭代上述过程，直到模型性能无法再提升。
前向特征选择和反向特征消去的计算量较大、耗时较久，因此只适用输入变量较少的数据集。
3.3.3 特征提取
特征提取可以看作变量选择方法的一般化。特征选择是去掉无关特征，保留相关特征的过程，或是从所有的特征中选择一个最好的特征子集的过程。
特征提取则是将机器学习算法不能识别的原始数据转换为算法可以识别的特征的过程。例如，组合不同的特征变量可以得到新的特征变量，改变原有的数据特征空间。典型的特征提取方式有线性和非线性两种，如图3-7所示。
图3-7
线性
1.主成分分析
主成分分析（Principal Component Analysis, PCA）是常用的线性降维方法，通过正交变换将原始的N维数据集映射到一个主成分数据中，即把高维空间中的数据映射到低维空间，并在投影维度上使数据的方差尽可能大，从而减少数据维度，同时尽可能保留原始数据的特性，如图3-8所示。
图3-8
在图3-8中，相关变量x1、x2、x3、x4映射到了两个无关的成分变量pc1和pc2上。下面用一个实例介绍主成分分析的步骤和方法，假设有10组二维特征数据，如表3-2所示。
表3-2
通过绘制二维坐标可知，10个样本数据基本处于比较杂乱的状态，很难通过简单的方式进行降维，如图3-9所示。
图3-9
（1）对样本数据求均值，并进行去均值处理。x的均值为2.199，y的均值为2.253，通过
及
，重新映射坐标位置得到的结果如图3-10所示。可以发现，均值处理并未改变相对大小和结构，只是中心位移了。
图3-10
（2）计算协方差矩阵。协方差公式为
，由于本例的特征为x和y，因此协方差矩阵是一个2×2的矩阵，即
计算得到的协方差矩阵为（（0.74261 0.28652556））（（0.28652556 0.42833444））。
（3）计算协方差矩阵的特征值和特征向量，将特征向量绘制到图中，如图3-11所示。
图3-11
特征向量之间是正交的，主成分分析正是利用特征向量这个特点构建了新的空间体系，将原始数据乘以特征向量，得到的空间体系如图3-12所示。其中，“+”是通过坐标变换之后得到的新点，即每一个原始数据点投影到特征向量的结果。
图3-12
（4）选择主成分。根据特征值的大小，从大到小选择K个特征值对应的特征向量，例如，本例排序后的特征值和特征向量如表3-3所示。
表3-3
由于选择的是K个特征向量，而本例中仅有两个特征，因此选择K=1，即选择其中最大的特征值及对应的特征向量。
（5）生成降维数据。将原始数据乘以上一步筛选出的特征向量组成特征矩阵之后，即可得到新的降维数据。例如，本例得到的结果如表3-4所示，z即为从x和y映射的新特征。
表3-4
如果把z可视化到二维坐标系中，固定其另外一维的值为1.0，则效果如图3-13所示，从二维的小圆点数据映射到一维的小菱形数据。
至此，主成分分析完成了利用少数几个综合变量来代替原始多个变量的过程，也可以看出主成分分析的数据不需要数据满足特定分布（例如正态分布）。
图3-13
2.因子分析
因子分析（Factor Analysis）可以理解为是主成分分析的一种改进。因子分析基于原始变量相关矩阵内部的依赖关系，把一些关系错综复杂的变量归结为少数几个综合因子，实质则是从多个变量中提取共性因子，并得到最优解的过程。
在因子分析过程中，将变量按照相关性进行分组，组内的相关性足够高，组间的相关性相对较低，每个组即为因子。由于根据相关性进行了分组，每个组又包含了多个变量，因此因子的数量小于原始变量的数量，从而达到降维的目的。例如，针对学生的各科学习成绩的因子分析，若单科成绩优异的学生，其他科目的成绩也不差，则抽取的共性因子为学习能力或学习方法。
相较于主成分分析，因子分析是把变量表示成各因子的线性组合，而在主成分分析中，则是把主成分表示成各个变量的线性组合。
与主成分分析、因子分析类似的特征提取方式有线性判别分析（Linear Discriminant Analysis）、独立成分分析（Independent Components Analysis, ICA）等，它们都是通过线性变换的方式完成对数据的降维的。
非线性
前面介绍的是线性降维处理方式，对于非线性降维处理方式，常用的是基于流形学习的方法。
流形是几何中的一个概念，表示在高维空间中的几何结构，它是由空间中的点构成的集合，可以将流形理解成二维空间的曲线。例如，三维空间中的一个流形如图3-14所示，它实际上是一个二维数据的卷曲面。
流形学习的关键是假设观察的数据实际上是由一个低维流形映射到高维空间上的，流行学习的基本方法有多维尺度缩放、等距特征映射、局部线性嵌入等。
图3-14
1.多维尺度缩放
多维尺度缩放（Multidimensional Scaling, MDS）是一种比较经典的降维方法，它的核心思想是，高维空间的距离状态在低维空间中保持不变。由于距离计算对于数据的维度并没有直接依赖关系，因此保持距离状态不变也就保持了在低维空间中的相对距离。
对图3-14所示的流形进行多维尺度缩放，由三维降到二维的效果如图3-15所示。
图3-15
多维尺度缩放不需要先验知识即可进行计算，整个过程相对比较简单，且保留了原始数据的相对关系，能够较好地可视化。但是，多维尺度缩放在计算过程中认为各个维度对于结果的影响是相同的，然而事实上可能存在部分维度贡献度不同的情况。
2.等距特征映射
等距特征映射（Isometric Feature Mapping, ISOMAP）是被广泛使用的低维嵌入方法之一，等距特征映射建立在多维尺度缩放的基础上，两者的原理基本相同。等距特征映射试图保留数据原有的几何形状，最大的差异在于它采用最短路径距离替代了多维尺度缩放中的欧氏距离，这种最短路径距离采用测地线距离（曲线距离）作为空间中的两点距离，可以更好地拟合流形中的数据。
等距特征映射的计算过程分为三步。
① 为每个样本点确定邻居，确定邻居的方法可以采用KNN的方式或将半径阈值以内的作为邻居，因此可以形成一个加权图，边上的权重即为两点的空间距离。
② 对于图中的任意两点，计算最短路径，可以采用Dijkstra算法计算最短路径；
③ 把计算出的最短路径作为多维尺度缩放的输入，进行降维。
等距特征映射变换得到的低维空间中较好地保留了数据的本质特征，能够较好地处理非线性数据，属于非迭代的全局优化算法。
3.局部线性嵌入
局部线性嵌入（Locally Linear Embedding, LLE）是比较重要的非线性降维方法之一，局部线性嵌入在降维时保持了局部线性特征，因此被称作局部线性特征。
局部线性嵌入表示数据在较小的范围内是保持线性关系的，某个变量可以由其附近的若干个样本线性表示。例如，变量x1附近的变量x2、x3、x4可以表示为式（3-9）所示的线性形式。
通过局部线性嵌入降维之后，每一个变量xi的投影为
，应尽可能保持w12、w13、w14在有限范围内变化的同时满足式（3-10）。
即在变量附近依然产生线性关系，距离观测样本x1较远的其他样本对局部线性嵌入不产生任何影响。
局部线性嵌入的步骤主要有三步：
① 对样本求K近邻样本，和KNN算法流程一致，样本数量K需要提前设定，表示用多少样本表示单个样本；
② 对每个样本求其K近邻样本的线性组合，计算线性关系的权重系数；
③ 利用线性关系的权重系数在低维空间中重构样本，完成降维。
局部线性嵌入与计算机图形中的局部视觉感知有一定相似之处，因此局部线性嵌入被广泛应用在图形图像领域。
局部线性嵌入可以学习任意维度的局部线性的低维流形，整个算法可以归纳为对稀疏矩阵进行特征分解。由于局部线性特征及KNN算法本身的缺陷限定了局部线性嵌入对数据的处理，因此在处理闭合的流形、稀疏的数据样本或分布不均的样本时效果相对较差。