假设一个正方形代表二维特征空间，特征空间的平均值是这个正方形的中心，到这个中心距离为一个单位距离的样本分布在一个单位圆中。不在这个单位圆的样本相对于中心更接近正方形的边角。这些样本因为特征值差距很大（如对角的样本）而很难分类。由图9可以看出，如果样本都落在内切圆中，分类将会简单很多：
有意思的是如果我们一直增加维度，那正方形（超立方体）中的圆（超球面）的体积是如何变化的呢？超立方体的体积始终保持1^d = 1，这个d维超立方体内切超球面的体积（半径为0.5）可以用如下公式计算：
图10展示了超球面的体积是如何随着维度增加而变化的：
可以看出随着维度趋于无穷，超球面的体积趋于0，然而超立方体体积没有变化。这解释了分类问题中的维度灾难：在高纬空间中，大多数训练样本处于超立方体的边角处。上面也提到过，边角处的样本相对于位于超球面内的样本更难分类。可以从下图中看出来，下图展示了二维正方形、三维立方体、和有着2^8 = 256个角的八维的超立方体：
对于一个8维的超立方体，大约98%的数据分布在它的256个角处。因此，当特征空间维度趋于无穷大，样本到中点的最大和最小欧几里得距离的差，比上样本到中点的最小欧几里得距离趋于0：
因此，在高纬度空间，距离度量逐渐失去了度量差异性的能力。由于分类是基于这些距离度量（如欧几里得距离、马氏距离、曼哈顿距离），分类算法在低维度空间更容易实现。类似的，高斯 likelihoods（不知道肿么翻译）变得平滑，重尾。因此最大likhood和最小likhood差值与最小likehood的壁纸也趋于0。
怎么避免维度灾难？
图1显示当维度很大时候，分类器的分类能力会下降。问题是“很大”是指什么，过拟合怎么避免？遗憾的是没有一个固定的法则定义在一个分类问题中应该用多少个特征。事实上，这取决于可提供的训练集大小、决策边界的复杂度、以及用的分类方法。
如果训练集可以达到理论上的无限个，那么久不存在维度灾难，我们可以用无限个维度去得到一个完美的分类器。训练集样本越少，越应该用少量的特征，如果N个训练样本足够覆盖一个一维的特征空间（区间大小为一个单位），那么 需要N^2个样本去覆盖一个同样密度的二维的特征空间，需要N^3个样本去覆盖三维的特征空间。换句话说，就是训练样本多少需要随着维度指数增长。
另外，那些精确计算非线性决策边界的分类器（如神经网络、KNN分类器、决策树）不会泛化的很好，而且容易发生过拟合。因此在用这些分类器的时候应该少用一些纬度。如果一个分类器泛化能力很好（如朴素贝叶斯，线性分类器），由于分类器本身表现能力差一些，那么纬度可以高一些。图6显示在高纬度空间用一个简单的分类器，就相当于在低纬度空间用一个复杂的分类器。
因此，过拟合在高纬度空间相对少量参数以、低纬度多参数的情况下都会发生过拟合。例如，考虑高斯密度函数，参数是它的平均值和协方差矩阵。在3D空间中，协方差矩阵是由6个不同元素（对角线上的三个方差和非对角线上的三个协方差）组成的3×3的对称矩阵，加上三个维度分布的的平均值，意味着我们需要估计9个参数，然而在2D情况中我们需要估计5个参数（两个平均值，两个方差和一个协方差）。我们可以看到随着维度增加，需要估计的参数随着维度二次增加。（原文grows quadratic with the number of dimensions.为什么是grows quadratic?）
在之前一篇文章我们看到随着需要估计的参数数量增加，参数的估计值的方差也会增加（并且如果估计偏差和训练集保持不变）。这意味着如果维度增加，随之方差增加，我们参数估计质量会下降。分类器的方差增加意味着过拟合。
另外一个有趣的问题是应该选择哪些特征。给定N个特征，我们如果选择最优的M个特征的子集满足M<N?一个方法是寻找图1中的最值。由于所有的特征组合，训练和测试分类是很棘手的，有很多方法来寻找这个最值。这些方法称为feature selection algorithms点击打开链接，经常用试探发（贪心算法，最好优先搜索法等）来确定特征的最优个数和组合。
另外一个方法是用M个特征替代N个特征，这M个特征中，每个都是原来特征的组合。为降低维度，尝试找到原始特征线性或者非线性最优组合的方法称为feature extraction methods点击打开链接。有名的产生正交的、原始特征线性组合的降维方法是PCA，PCA尝试找到一个低纬度的线性子空间，保持原始维度上大量数据的方差。然而，需要注意的是数据的大量方差不一定代表最有识别力的信息。
最后，一个非常重要的探测和避免分类训练过程中过拟合的方法是交叉验证。交叉验证方法将原始训练数据分成一个或多个训练数据子集。在分类训练中，一个子集用来测试分类结果的准确性，剩下的子集用来进行参数估计。如果分类结果在训练集合和测试集合上相差很多，那么就是产生了过拟合。很多类型的交叉验证如k折交叉验证和留一交叉验证可以用于可提供的训练数据很少的情况。
结论：
在这片文章中，我们讨论了feature selection和feature extraction的重要性，以及交叉验证，以防止维度灾难带来的过拟合。通过一个简单的栗子，我们探讨了维度灾难严重结果：过拟合。