分类问题中维度诅咒(上)

导论：

在本文中，我们将讨论所谓的“维度的诅咒”，并解释为什么在设计分类器时很重要。在以下部分中，我将提供对这个概念的直观解释。

考虑一个例子，其中我们有一组图像，每个描绘了一只猫或狗。我们想创建一个能够自动区分狗和猫的分类器。为此，我们首先需要考虑通过数字表示的每个对象类的描述符，例如数学算法（即分类器），可以使用这些数字来识别对象。例如，我们可以认为猫和狗的颜色通常不同。鉴别这两个类的可能的描述符可以包括三个数字; 所考虑的图像的平均红色，平均绿色和平均蓝色。例如，一个简单的线性分类器可以线性组合这些特征来决定类标签：

If 0.5*red + 0.3*green + 0.2*blue > 0.6 : return cat; else return dog;

然而，这三个描述颜色的数字，所谓特征，显然不足以获得完美的分类。因此，我们可以决定添加一些描述图像纹理的特征，例如通过计算X和Y方向上的平均边缘或梯度强度。我们现在有5个特征了，组合在一起可能被分类算法用于区分猫和狗。

为了获得更准确的分类，我们可以基于颜色或纹理的直方图，统计矩等添加更多的特征。也许我们可以通过认真定义几百个这些特征来获得完美的分类？这个问题的答案听起来有点反直觉：不，我们不能！事实上，在某一点之后，通过添加新特征来增加问题的维度实际上会降低我们的分类器的性能。这由图1示出，并且通常被称为“维度的诅咒”。

Figure 1.随着维数的增加，分类器的性能随之增加，直到达到最佳数量的特征。进一步增加维度而不增加训练样本的数量导致分类器性能的降低。

维度的诅咒和过拟合

在前面介绍的猫和狗的例子中，让我们假设有无限数量的猫和狗住在我们的星球上。然而，由于我们有限的时间和处理能力，我们只能够获得10张猫和狗的图片。分类的最终目标是训练基于这10个训练实例的分类器，能够正确地分类无限数量的狗和猫，这些我们没有任何信息的实例。现在让我们使用一个简单的线性分类器，并尝试获得完美的分类。我们可以从一个特征开始，例如，图像中的平均“红色”：

Figure 2. A single feature does notresult in a perfect separation of our training data.

图2显示，如果只使用一个特征，我们不能获得完美的分类结果。因此，我们可能会决定添加其他特征，例如，图像中的平均“绿色”：

Figure 3.Adding a second feature stilldoes not result in a linearly separable classification problem: No single linecan separate all cats from all dogs in this example.

最后我们决定添加第三个特征，例如，平均“蓝色”因此构造了一个三维特征空间：

Figure 4. Adding a third featureresults in a linearly separable classification problem in our example. A planeexists that perfectly separates dogs from cats.

在三维特征空间中，我们现在可以找到一个将狗与猫完美分开的平面。这意味着三个特征的线性组合可以用于在我们的10个图像的训练数据上获得完美的分类结果：

Figure 5. The more features we use, thehigher the likelihood that we can successfully separate the classes perfectly.

这似乎暗示增加特征的数量直到获得完美的分类结果是训练分类器的最佳方式，而在图1所示的引言中，我们认为这种情况不行。但是，请注意，当我们增加问题的维数时，训练样本的密度是如何呈指数下降。

在1D情况下（图2），10个训练实例覆盖了完整的1D特征空间，其宽度为5个单位间隔。因此，在1D情况下，样品密度为10/5 = 2个样品/间隔。在2D情况下（图3），我们仍然有10个训练实例，我们现在覆盖了一个面积为5×5 = 25个单位正方形的2D特征。因此，在2D情况下，样品密度为10/25 = 0.4样品/间隔。最后，在3D情况下，10个样本必须覆盖5×5×5 = 125个单位立方体的特征空间。因此，在3D情况下，样品密度为10/125 = 0.08个样品/间隔。

如果我们继续添加特征，特征空间的维度随之增长，并且变得更稀疏。由于这种稀疏性，变得更容易找到可分离的超平面，因为当特征的数目变得无限大时，训练样本位于最佳超平面的错误方向的可能性变得无限小。然而，如果我们将高维分类结果投影回较低维的空间，则与该方法相关联的问题的严重性变得更明显：

Figure 7. Although the training data isnot classified perfectly, this classifier achieves better results on unseendata than the one from figure 5.

虽然图7所示的具有决策边界的简单线性分类器看起来比图5中的非线性分类器更差，但是这种简单分类器更好地泛化了不可见的数据，因为它没有学习仅在我们的训练数据中的特定异常。换句话说，通过使用较少的特征，避免了维度的诅咒，使得分类器没有过拟合训练数据。

图8以不同的方式示出了上述内容。假设我们想训练一个分类器，只使用一个单一的特征，其值的范围从0到1。让我们假设这个特征对于每个猫和狗是唯一的。如果我们希望我们的训练数据覆盖这个范围的20％，那么所需的训练数据量是猫和狗的完整数量的20％。现在，如果我们添加另一个特征，产生了2D特征空间，于是事情改变了；为了覆盖2D特征范围的20％，我们现在需要在每个维度上获得45％的猫和狗的完整群体（0.45 ^ 2 = 0.2）。在3D情况下，这变得更糟：为了覆盖3D特征范围的20％，我们需要在每个维度中获得58％的群体（0.58 ^ 3 = 0.2）。

Figure 8. The amount of training dataneeded to cover 20% of the feature range grows exponentially with the number ofdimensions.