开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2020.07.30
系列九我们从算法组合的角度一起实战学习了一下组合算法方面的知识，详情戳下链接：
在这一期中，我们将主要讨论一下几方面内容：
一.维度灾难
许多机器学习问题涉及特征多达数千乃至数百万个。正如我们将看到的，这不仅让训练变得非常缓慢，而且还会使得找到一个好的解决方案变得更加困难。这个问题通常被称为维度灾难。
除了加速训练之外，降维对于数据可视化（或DataViz）也非常有用。将维度数量减少到两个（或三个）使得可以在图表上绘制高维训练集，并且通常通过视觉上检测诸如集群的图案来获得一些重要的见解。
我们习惯于三维生活，当我们试图想象一个高维空间时，我们的直觉失败了。即使是一个基本的4D超立方体，在我们的脑海中也难以想象，如下图，更不用说在1000维空间弯曲的200维椭球。
事实证明，许多事物在高维空间中表现得非常不同。例如，如果你选择一个单位平方（1×1平方）的随机点，它将只有大约0.4％的机会位于小于0.001的边界（换句话说，随机点将沿任何维度“极端”这是非常不可能的）。但是在一个10000维单位超立方体（1×1×1立方体，有1万个1）中，这个概率大于99.999999％。高维超立方体中的大部分点都非常靠近边界。
这更难区分：如果你在一个单位平方中随机抽取两个点，这两个点之间的距离平均约为0.52。如果在单位三维立方体中选取两个随机点，则平均距离将大致为0.66。但是在一个100万维的超立方体中随机抽取两点呢？那么平均距离将是大约408.25（大约1,000,000/6）！
这非常违反直觉：当两个点位于相同的单位超立方体内时，两点如何分离？这个事实意味着高维数据集有可能非常稀疏：大多数训练实例可能彼此远离。当然，这也意味着一个新实例可能离任何训练实例都很远，这使得预测的可信度表现得比在低维度数据中要来的差。简而言之，训练集的维度越多，过度拟合的风险就越大。
理论上讲，维度灾难的一个解决方案可能是增加训练集的大小以达到足够密度的训练实例。不幸的是，在实践中，达到给定密度所需的训练实例的数量随着维度的数量呈指数增长。如果只有100个特征（比MNIST问题少得多），那么为了使训练实例的平均值在0.1以内，需要比可观察宇宙中的原子更多的训练实例，假设它们在所有维度上均匀分布。
二.降维的主要途径
在深入研究具体的降维算法之前，我们来看看降维的两种主要途径：投影和流形学习。
2.1投影
请注意，所有训练实例都靠近一个平面：这是高维（3D）空间的较低维（2D）子空间。现在，如果我们将每个训练实例垂直投影到这个子空间上（如连接实例到平面的短线所表示的那样），我们就得到如下图所示的新的2D数据集。当当！我们刚刚将数据集的维度从3D减少到了2D。请注意，轴对应于新的特征z1和z2（平面上投影的坐标）。
然而，投影并不总是降维的最佳方法。在许多情况下，子空间可能会扭曲和转动，如下图所示的著名的瑞士滚动玩具数据集。
简单地投射到一个平面上（例如，通过丢弃特征x3）将会把瑞士卷的不同层挤压在一起，如下图的左边所示。但是，您真正需要的是展开瑞士卷，以获得下图右侧的2D数据集。
2.2流形学习
瑞士卷是二维流形的一个例子。简而言之，二维流形是一种二维形状，可以在更高维空间中弯曲和扭曲。更一般地，d维流形是局部类似于d维超平面的n维空间（其中d 许多降维算法通过对训练实例所在的流形进行建模来工作;这叫做流形学习。它依赖于流形假设，也被称为流形假设，它认为大多数现实世界的高维数据集靠近一个低得多的低维流形。这种假设通常是经验性观察到的。 再次考虑MNIST数据集：所有的手写数字图像都有一些相似之处。它们由连线组成，边界是白色的，或多或少居中，等等。如果你随机生成图像，只有一小部分看起来像手写数字。换句话说，如果您尝试创建数字图像，可用的自由度远远低于您可以生成任何想要的图像的自由度。这些约束倾向于将数据集压缩到较低的维度。 流形假设通常伴随另一个隐含的假设：如果在流形的较低维空间中表示，手头的任务（例如分类或回归）将更简单。例如，在下图的第一行中，瑞士卷被分成两类：在三维空间（在左边），决策边界相当复杂，但是在2D展开的流形空间（在右边），决策边界是一条简单的直线。 但是，这个假设并不总是成立。例如，在上图右侧，判定边界位于x1=5。这个判定边界在原始三维空间（一个垂直平面）看起来非常简单，但是在展开的流形中它看起来更复杂四个独立的线段的集合）。 简而言之，如果在训练模型之前降低训练集的维数，那么肯定会加快训练速度，但并不总是会导致更好或更简单的解决方案。这一切都取决于数据集。 到这里我们基本能够很好地理解维度灾难是什么，以及维度减少算法如何与之抗衡，特别是当多种假设成立的时候。那么接下来我们将一起学习一下常见的降维算法。 三.PCA(主成分分析 主成分分析（PCA）是目前最流行的降维算法。主要是通过识别与数据最接近的超平面，然后将数据投影到其上。 3.1保持差异 在将训练集投影到较低维超平面之前，您首先需要选择正确的超平面。例如，简单的2D数据集连同三个不同的轴（即一维超平面）一起在下图的左侧表示。右边是将数据集投影到这些轴上的结果。正如你所看到的，在c2方向上的投影保留了最大的方差，而在c1上的投影保留了非常小的方差。 选择保留最大变化量的轴似乎是合理的，因为它最有可能损失比其他投影更少的信息。证明这一选择的另一种方法是，使原始数据集与其在该轴上的投影之间的均方距离最小化的轴。这是PCA背后的一个相当简单的想法。 3.2PCA中的PC 主成分分析（PCA）识别训练集中变化量最大的轴。在上图中，它是实线。它还发现第二个轴，与第一个轴正交，占了剩余方差的最大量。如果它是一个更高维的数据集，PCA也可以找到与前两个轴正交的第三个轴，以及与数据集中维数相同的第四个，第五个等。 定义第i个轴的单位矢量称为第i个主成分（PC）。在上图中，第一个PC是c1，第二个PC是c2。在2.1节的图中，前两个PC用平面中的正交箭头表示，第三个PC与平面正交（指向上或下）。 主成分的方向不稳定：如果稍微扰动训练集并再次运行PCA，一些新的PC可能指向与原始PC相反的方向。但是，他们通常仍然位于同一轴线上。在某些情况下，一部分的PC甚至可能旋转或交换，但他们确定的平面通常保持不变。 那么怎样才能找到训练集的主要组成部分呢？幸运的是，有一种称为奇异值分解（SVD）的标准矩阵分解方法，可以将训练集矩阵X分解成三个矩阵U·Σ·VT的点积，其中VT包含我们正在寻找的所有主成分，如下公式所示。 下面的Python代码使用NumPy的svd()函数来获取训练集的所有主成分，然后提取前两个PC： 3.3投影到d维度 一旦确定了所有主要组成部分，就可以将数据集的维数降至d维，方法是将其投影到由第一个主要组件定义的超平面上。选择这个超平面确保投影将保留尽可能多的方差。例如，在2.1节中的数据集中，3D数据集向下投影到由前两个主成分定义的2D平面，从而保留了大部分数据集的方差。因此，二维投影看起来非常像原始的三维数据集。 为了将训练集投影到超平面上，可以简单地通过矩阵Wd计算训练集矩阵X的点积，该矩阵定义为包含前d个主分量的矩阵（即，由VT的前d列组成的矩阵），如下公式所示。 以下Python代码将训练集投影到由前两个主要组件定义的平面上： 现在我们已经知道如何将任何数据集的维度降低到任意维数，同时尽可能保留最多的差异。 3.4使用Scikit-Learn Scikit-Learn的PCA类使用SVD分解来实现PCA，就像我们之前做的那样。以下代码应用PCA将数据集的维度降至两维： 在将PCA变换器拟合到数据集之后，可以使用components_变量访问主成分（注意，它包含水平向量的PC，例如，第一个主成分等于pca.components_.T[:,0]）。 3.5解释方差比率 另一个非常有用的信息是解释每个主成分的方差比率，可通过explained_variance_ratio_变量得到。它指明了位于每个主成分轴上的数据集方差的比例。例如，让我们看看图8-2中表示的3D数据集的前两个分量的解释方差比率： 它告诉我们，84.2％数据集的方差位于第一轴，14.6％位于第二轴。第三轴的这一比例不到1.2％，所以可以认为它可能没有什么信息。 3.6选择正确的维度数量 不是任意选择要减少的维度的数量，通常优选选择加起来到方差的足够大部分（例如95％）的维度的数量。当然，除非我们正在降低数据可视化的维度（在这种情况下，您通常会将维度降低到2或3）。 下面的代码在不降低维数的情况下计算PCA，然后计算保留训练集方差的95％所需的最小维数： 然后可以设置n_components=d并再次运行PCA。但是，还有一个更好的选择：不要指定要保留的主要组件的数量，您可以将n_components设置为0.0到1.0之间的浮点数，表示您希望保留的方差比率： 3.7PCA压缩 降维后显然，训练集占用的空间少得多。例如，尝试将PCA应用于MNIST数据集，同时保留其95％的方差。你会发现每个实例只有150多个特征，而不是原来的784个特征。所以，虽然大部分方差都被保留下来，但数据集现在还不到原始大小的20％！这是一个合理的压缩比，你可以看到这是如何加速分类算法（如SVM分类器）。 也可以通过应用PCA投影的逆变换将缩小的数据集解压缩回到784维。当然这不会给你原来的数据，因为投影丢失了一点信息（在5％的差异内），但它可能会非常接近原始数据。原始数据与重构数据（压缩然后解压缩）之间的均方距离称为重建误差。例如，以下代码将MNIST数据集(公众号回复“mnist”)压缩到154维，然后使用inverse_transform（）方法将其解压缩到784维。下图显示了原始训练集（左侧）的几个数字，以及压缩和解压缩后的相应数字。你可以看到有一个轻微的图像质量损失，但数字仍然大部分完好无损。 如下等式，显示了逆变换的等式。 3.8增量PCA 先于PCA实现的一个问题是，为了使SVD算法运行，需要整个训练集合在内存中。幸运的是，已经开发了增量式PCA（IPCA）算法：您可以将训练集分成小批量，并一次只提供一个小批量IPCA算法。这对于大型训练集是有用的，并且也可以在线应用PCA（即在新实例到达时即时运行）。 下面的代码将MNIST数据集分成100个小批量（使用NumPy的array_split()函数），并将它们提供给Scikit-Learn的IncrementalPCAclass5，以将MNIST数据集的维度降低到154维（就像以前一样）。请注意，您必须调用partial_fit()方法，而不是使用整个训练集的fit（）方法。 3.9随机PCA Scikit-Learn提供了另一种执行PCA的选项，称为随机PCA。这是一个随机算法，可以快速找到前d个主成分的近似值，它比以前的算法快得多。 四.KernelPCA 在前面的系列中，我们讨论了内核技巧，一种将实例隐式映射到非常高维的空间（称为特征空间）的数学技术，支持向量机的非线性分类和回归。回想一下，高维特征空间中的线性决策边界对应于原始空间中的复杂非线性决策边界。 事实证明，同样的技巧可以应用于PCA，使得有可能执行复杂的非线性投影降维。这被称为内核PCA(KPCA)。在投影之后保留实例簇通常是好的，有时甚至可以展开靠近扭曲流形的数据集。 下图显示了使用线性内核（等同于简单使用PCA类），RBF内核和S形内核（Logistic）减少到二维的瑞士卷。 五.LLE(局部线性嵌入) 例如，下面的代码使用Scikit-Learn的LocallyLinearEmbedding类来展开瑞士卷。得到的二维数据集如下图所示。正如你所看到的，瑞士卷是完全展开的，实例之间的距离在本地保存得很好。但是，展开的瑞士卷的左侧被挤压，而右侧的部分被拉长。尽管如此，LLE在对多样性进行建模方面做得相当不错。