维度灾难

过拟合一般发生在两种情况，高维空间的数据对少参数进行预测，低维空间的数据对多参数进行预测。高维灾难就是第一种情况的描述。
高维灾难讲的是，为了得到更好的分类效果，我们可以加更多特征，但当我们特征多到一定时候时，分类器的效果反而开始下降了。

5938f499e5e96.jpeg

如何理解这种现象呢？当整个特征空间维度增加，数据在空间里的分布会越来越稀疏。于是我们更容易找到一个超平面来实现分类。但是当把高维的分类结果投影到低维空间时，原本线性可分的情况就变形了，原来的线性分类效果变成了低维的非线性分类。于是，高维的分类器学习了训练数据的噪声和异常，而对样本外数据拟合效果不理想。这说明使用更少的特征，维度灾难就能避免，过拟合现象也会减小。换句话说，如果可用的训练样本数固定，增加特征会导致过拟合。

从另一个角度看高维灾难。1. 2如果我们只用一个特征来训练分类器，如果我们希望训练样本的特征值点总特征值范围的20%，我们只需要采样20%的数据做训练样本。2. 如果我们用两个特征来训练分类器，如果我们希望还是占总特征值范围的20%， 我们的训练样本需要达到总体样本的45%（因为0.45^2=0.2）。3. 进一步地，如果我们用三个特征来训练分类器，如果我们希望还是占总特征值范围的20%， 我们的训练样本需要达到总体样本的58%（0.58^3=0.2）。换句话说，增加特征的同时，为了覆盖同样的特征值范围防止过拟合，所需的训练样本数就会指数型增长。
这个角度还可以推及到对空间的数据分布的理解，随着维度增大，超立方体的体积不变，而相应的超球体的体积会趋于零。1.在超立方体的情况下，围绕原点（中心）的数据比在角落处的数据要稀疏很多。2.而在角落处的数据由于特征值很大，所以难以分类。所以，多维情况下，难分类的数据很多。

5938f7ec1b84d.jpeg

如何避免维度灾难呢？

1. 理论上说，训练样本无限多，维度灾难就不会发生。也就是说，随着维度增加，训练样本的数量要求随指数增加。
2. 非线性决策边界的分类器，如神经网络、KNN，决策树分类效果好但是泛化能力差。因此使用这些分类器时维度不能过高。而如果是泛化能力好的分类器如贝叶斯、线性分类器，可以使用更多的特征。