《数据科学与分析：Python语言实现》 —3.9　注意“维度的诅咒”

3.9　注意“维度的诅咒”

我们一直将数据特征称为将与机器学习算法一起使用的成分中的一部分。一旦确定要包含在模型中的要素，即可将它们视为可以放置数据实例的不同维度：对于单个要素，我们用一维空间表示，两个要素可以用二维表示，等等。

因此，随着我们增加特征数量，模型包含的维数也会增加。不仅如此，我们还将增加描述数据实例所需的信息量，从而增加模型。

随着维度数量的增加，我们需要考虑增加更多数据实例，特别是在要避免过度拟合时。认识到采样空间所需的数据点数量随着空间的维数呈指数增长通常称为“维度的诅咒”，这是理查德·贝尔曼在动态规划环境中使用的术语，也是描述这个问题的好方法！

当我们拥有的数据集的数量远远大于数据点的数量时，维度的诅咒变得更加明显。这就是为什么当维数增加时，计算空间中数据点之间的距离会使问题变得明显。

让我们在不失一般性的前提下加以考虑：有一组属于3个不同类的数据实例，M=10。我们感兴趣的是找到每个数据点的最近邻居，在这种情况下，评估它们是否属于同一个类。这是一个非常简单的分类任务。我们可以通过考虑使用单位长度测量并计算其中的数据点数来简化讨论。图3.2中描述了这种情况，其中显示了10个数据实例，用三角形、空心圆和加号分别表示一维、二维和三维。

图3.2　维数的诅咒（10个数据实例放置在维度从一维到三维增加的空间中，稀疏度随着维数的增加而增加）

在一维空间中，单位测量由线给出。在图3.2所示的示例中，我们可以看到一个具有3个单位间隔的空间，因此样本密度为10/3。换句话说，每个区间有大约3.333……个数据点，因此找到一个邻近点并且评估它所属的类别肯定是可能的。

在二维情况下，我们必须搜索3×3=9个单位正方形的区域，在这种情况下，样本密度为10/9，或平均每平方1.111……个数据点。在这种情况下，不太可能在感兴趣的数据点所在的单位平方内找到给定数据实例的邻近点。最后，在三维情况下，我们的特征空间为3×3×3=27个单位立方体，样本平均密度为10/27=0.111……在这种情况下，我们在立方体内搜索邻近点变得更加困难，因为大多数特征空间实际上是空的。此时我们说这个空间很稀疏。

很容易看出，当不断添加特征（维度）时，空间会变得更加稀疏。正是由于这种稀疏性，在处理更高维度时需要越来越多的数据实例。例如，如果我们有兴趣使用一个介于0和1之间的值的特征来执行分类任务，同时希望数据集覆盖此范围的25%，那么我们将需要总体样本的25%。通过添加另一个特征，我们需要总体样本的50%（0.52=0.25），有3个特征时，我们需要总体样本的63%（0.633≈0.25）。

我们可能认为简单地添加更多数据是消除维度诅咒的合适的解决方案。但是，正如上面所介绍的，重要的是要记住所需的数据实例数量随着维度的数量呈指数级增长。在实践中我们很少访问无限量的数据。此外，使用太多特征实际上会导致过度拟合。

按照上面的分类示例，有3个类别（三角形、空心圆和加号），在考虑更多数量的特征时，更容易找到将数据实例分类为单独类的各种方法。这是一个很好的开始，但我们必须小心避免过度拟合，或者甚至被错误的模式带偏了方向。此外，较高维空间中的稀疏性不均匀，并且原点周围的空间比超空间的角落更稀疏。

为了理解这个问题，让我们考虑一下二维空间。特征空间的平均值位于单位正方形的中心。如果想要在距离中心一个单位距离内搜索空间，我们将在由单位半径圆（由正方形限定）给出的区域内搜索。落在该区域之外的任何数据实例都变得更接近正方形的边缘并且变得更难以分类，因为它们的特征值与在中心的那些（平均值）相距更远。现在让我们考虑N维的情况：

远离单位圆中心的数据实例更难以分类。这种情况在更高的维度上更加严重。

N维单位超立方体的体积为1N=1。

N维的单位超球的体积是：

其中半径r=1表示单位超球，Γ(·)是伽马函数。

在图3.3中，我们展示了随着维数N的增加，超球的体积趋于零。尽管如此，超立方体的体积仍然是固定的。这意味着在高维空间中，大多数数据实际上位于定义的超立方体的角落特征空间，使分类任务更难实现。

图3.3　超球的体积与维度的函数关系（随着维数的增加，超球的体积趋于零）

维度的诅咒真实存在，并没有太多可以完全消除它的方法，但是可以将其最小化，例如仔细检查低维方法在更高维度上是否有效。避免维度诅咒可以通过增加数据量来完成，但即便考虑用这种方法，还是要考虑所使用的特征数据是否确实是合适的数据集合。

在这方面，除了仔细地选择特征外，还可以通过将数据从较高维空间转换为较低维度的空间来减少问题的维数，如主成分分析（PCA）的情况。我们将在第8章讨论这种技术。至于避免过度拟合，在3.12节我们将讨论交叉验证背后的想法。但首先我们需要停下来谈谈Scikit-learn。