分类问题中的维度诅咒（下）

换句话说，如果可用训练数据的数量是固定的，我们继续添加维度的话，则会发生过拟合。另一方面，如果我们不断增加维度，训练数据的数量需要快速增长以保持相同的覆盖，并避免过拟合。在上面的例子中，我们表明维度的诅咒引入了训练数据的稀疏性。我们使用的特征越多，数据越稀疏，使得对分类器参数（即，其判定边界）的精确估计变得更加困难。维度的诅咒的另一个效果是，这种稀疏性在搜索空间上不是均匀分布的。事实上，围绕原点（在超立方体的中心）的数据比搜索空间的角落中的数据稀疏得多。这可以理解如下：

设想一个表示2D特征空间的单位正方形。特征空间的平均值是该单位正方形的中心，并且距离该中心的单位距离内的所有点都在内切单位正方形的单位圆内。不在此单位圆内的训练样本会更接近搜索空间的角落而不是其中心。这些样本难以分类，因为它们的特征值极大地不同（例如，在单位正方形的对角的样本）。因此，如果大多数样品落入内切单位圆内，则分类更容易，如图9所示：

Figure 9.Training samples that falloutside the unit circle are in the corners of the feature space and are moredifficult to classify than samples near the center of the feature space.

一个有趣的问题是，当我们增加特征空间的维度时，圆（超球面）的体积相对于正方形（超立方体）的体积如何变化。维度d的单位超立方体的体积总是1 ^ d = 1。维度d和半径0.5的刻入超球面的体积可以计算为：

(1)

图10显示了随着维度的增加，超立方体体积的改变：

Figure 10. The volume of the hyperspheretends to zero as the dimensionality increases.

这表明超球面的体积趋向于零，因为维度趋于无穷大，而周围超立方体的体积保持恒定。这种令人惊讶且违背直觉的观察部分地解释了与分类中的维度的诅咒相关联的问题：在高维空间中，大多数训练数据驻留在限定特征空间的超立方体的角落中。如前所述，特征空间的角落中的实例比围绕超球面的质心的实例更难以分类。这由图11示出，其示出了2D单位正方形，3D单位立方体以及具有2 ^ 8 = 256个角的8D超立方体的创造性可视化：

Figure 11. As the dimensionalityincreases, a larger percentage of the training data resides in the corners ofthe feature space.

这表明超球体的体积作为维度时趋于零。对于8维超立方体，约98％的数据集中在其256个角。结果，当特征空间的维度变为无穷大时，从采样点到质心的最小和最大欧几里德距离的差和最小距离本身的比率趋于为零：

(2)

因此，距离测量开始丧失其在高维空间中测量差异的有效性。由于分类器取决于这些距离度量（例如欧几里德距离，马哈拉诺比斯距离，曼哈顿距离），所以在较少维度空间中分类通常更容易，其中较少特征用于描述感兴趣对象。类似地，高斯似然在高维空间中变得平坦和长尾分布，使得最小和最大似然之间的差的比率和最小似然本身趋于零。

如何避免维度的诅咒

图1表明，当问题的维数变得太大时，分类器的性能会降低。那么“太大”这个意味着什么呢，以及如何避免过拟合。遗憾的是，没有固定的规则来定义在分类问题中应该使用多少个特征。事实上，这取决于可用的训练数据的量，决策边界的复杂性以及所使用的分类器的类型。

如果理论上有无限数量的训练样本可用，则维度的诅咒不适用，并且我们可以简单地使用无限数量的特征来获得完美分类。训练数据的大小越小，应使用的特征越少。如果N个训练样本足以覆盖单位间隔大小的1D特征空间，则需要N ^ 2个样本来覆盖具有相同密度的2D特征空间，并且在3D特征空间中需要N ^ 3个样本。换句话说，所需的训练实例的数量随着所使用的维度的数量呈指数增长。

此外，倾向于非常精确地建模非线性决策边界的分类器（例如神经网络，KNN分类器，决策树）不能很好地泛化，并且很容易过拟合。因此，当使用这些分类器时，维度应保持相对低。如果使用容易泛化的分类器（例如朴素贝叶斯分类器，线性分类器），则所使用的特征的数量可以更高，因为分类器本身不具有表现力。图6显示出了在高维空间中使用简单分类器模型对应于在较低维空间中使用复杂分类器模型。

因此，当在高维空间中使用相对较少的参数时以及当在较低维空间中使用许多参数时都会发生过拟合。作为示例，考虑由其平均和协方差矩阵参数化的高斯密度函数。假设我们在3D空间中操作，使得协方差矩阵是由6个唯一元素（对角线上的3个方差和非对角线上的3个协方差）组成的3×3对称矩阵。与分布的3D均值一起，这意味着我们需要基于我们的训练数据估计9个参数，以获得表示我们的数据的可能性的高斯密度。在1D情况下，仅需要估计2个参数（平均值和方差），而在2D情况下需要5个参数（2D平均值，两个方差和协方差）。再次，我们可以看到要估计的参数的数量与维数的二次方增长。

在前面的文章中，我们表明如果预估计参数的数量会增加（并且如果预估偏差和训练数据的量保持恒定），则参数预估方差增加。这意味着如果维度上升，由于方差的增加，我们的参数预估质量会降低。分类器方差的增加对应于过拟合。

另一个有趣的问题是应该使用哪些特征。给定一组N个特征;我们如何选择M个特征的最佳子集，使得M <N？一种方法是在图1所示的曲线中搜索最优。由于对所有特征的所有可能组合训练和测试分类器通常是难以处理的，因此存在尝试以不同方式找到该最优的若干方法。这些方法被称为特征选择算法，并且通常使用启发法（贪婪法，最佳优先方法等）来定位特征的最优数目和组合。

另一种方法是通过一组M个特征来替换N个特征的集合，每个特征是原始特征值的组合。试图找到原始特征的最佳线性或非线性组合以减少最终问题的维度的算法被称为特征提取方法。产生原始N个特征的不相关的线性组合的公知的维数降低技术是主成分分析（PCA）。 PCA试图找到较低维度的线性子空间，使得保持原始数据的最大方差。然而，请注意，数据的最大方差不一定代表最具辨别力的信息。

最后，用于在分类器训练期间检测和避免过拟合技术是交叉验证。交叉验证方法将原始训练数据分成一个或多个训练子集。在分类器训练期间，使用一个子集来测试所得分类器的准确性和精度，而其他子集用于参数估计。如果用于训练的子集上的分类结果与用于测试的子集的结果大不相同，则过拟合正在发挥作用。如果只有有限数量的训练数据可用，则可以使用几种类型的交叉验证，例如k折交叉验证和留一法。

结论

在本文中，我们讨论了特征选择，特征提取和交叉验证的重要性，以避免由于维度的诅咒而导致过拟合。