认识达内从这里开始

【广州linux培训】讨论所谓的“维度灾难”，并解释在设计一个分类器时它为何如此重要。在下面几节中我将对这个概念进行直观的解释，并通过一个由于维度灾难导致的过拟合的例子来讲解。

考虑这样一个例子，我们有一些图片，每张图片描绘的是小猫或者小狗。我们试图构建一个分类器来自动识别图片中是猫还是狗。要做到这一点，我们首先需要考虑猫、狗的量化特征，这样分类器算法才能利用这些特征对图片进行分类。例如我们可以通过毛皮颜色特征对猫狗进行识别，即通过图片的红色程度、绿色程度、蓝色程度不同，设计一个简单的线性分类器。

红、绿、蓝三种颜色我们称之为特征Features，但仅仅利用这三个特征，还不能得到一个完美的分类器。因此，我们可以增加更多的特征来描述图片。例如计算图片X和Y方向的平均边缘或者梯度密度。现在总共有5个特征来构建我们的分类器了。

为了得到更好的分类效果，我们可以增加更多特征，例如颜色、纹理分布和统计信息等。也许我们能得到上百个特征，但是分类器的效果会变得更好吗?答案有些令人沮丧：并不能!事实上，特征数量超过一定值的时候，分类器的效果反而下降。

维度灾难与过拟合

在之前引入的猫和狗的例子中，我们假设有无穷多的猫和狗的图片，然而，由于时间和处理能力限制，我们只得到10张图片(猫的图片或者狗的图片)。我们的最终目标是基于这10张图片构建一个分类器，能够正确对10个样本之外的无限多的图片进行正确分类。

现在，让我们使用一个简单的线性分类器来尝试得到一个好的分类器。如果只使用一个特征，例如使用图片的平均红色程度red。

增加第二个特征仍然不能线性分割，即不存在一条直线能够将猫和狗完全分开。

最后，我们决定再增加第三个特征：图片的平均蓝色程度，得到了三维特征空间，增加第三个特征实现了线性可分，即存在一个平面完全将猫和狗分开来。

在三维特征空间，我们可以找到一个平面将猫和狗完全分开。这意味着三个特征的线性组合可以对10个训练样本进行最佳的分类。

以上的例子似乎证明了不断增加特征数量，直到获得最佳分类效果，是构建一个分类器的最好方法。但是，之前图1中，我们认为情况并非如此。我们需要注意一个问题：随着特征维度的增加，训练样本的在特征空间的密度是如何呈指数型下降的?

如果我们继续增加特征，整个特征空间维度增加，并变得越来越稀疏。由于稀疏性，我们更加容易找到一个超平面来实现分类。这是因为随着特征数量变得无限大，训练样本在最佳超平面的错误侧的可能性将会变得无限小。然而，如果我们将高维的分类结果投影到低维空间中，将会出现一个严重的问题，使用太多特征导致过拟合。分类器学习了过多样本数据的异常特征(噪声)，而对新数据的泛化能力不好。

换句话说，如果可用的训练样本数量是固定的，那么如果增加特征维度的话，过拟合就会发生。另一方面，如果增加特征维度，为了覆盖同样的特征值范围、防止过拟合，那么所需的训练样本数量就会成指数型增长。

想象一个单位正方形代表了2D的特征空间，特征空间的平均值位于这个单位正方形的中心处，距中心处单位距离的所有点构成了正方形的内接圆。没有落在单位圆的训练样本距离搜索空间的角落处更距离中心处更近，而这些样本由于特征值差异很大(样本分布在正方形角落处)，所有难以分类。因此，如果大部分样本落在单位内接圆里，就会更容易分类。

一个有趣的问题是当我们增加特征空间的维度时，随着正方形(超立方体)的体积变化，圆形(超球体)的体积是如何变化的?无论维度如何变化，超立方体的体积都是1，而半径为0.5的超球体的体积随着维度d的变化。

这表明了随着维度变得越来越大，超球体的体积趋于零，而超立方体的体积是不变的。这种令人惊讶的反直觉发现部分解释了在分类中维度灾难的问题：在高维空间中，大部分的训练数据分布在定义为特征空间的超立方体的角落处。就像之前提到的，特征空间角落处的样本比超球体内的样本更加难以进行正确分类。