本文我们将讨论机器学习中一个经常被提及的概念— “维度灾难”，也有译作“维度诅咒”，以及其在分类问题中的重要性。接下来我们通过一个直观的例子来解释维度灾难z，例子来源于The Curse of Dimensionality in classification。
假设我们有一个仅有猫(🐱)和狗(🐶)图片集合，然后想建立一个分类器，用来区分出猫和狗。首先，我们需要构造一个数字描述来表示每个类别，比如可以用数学表达式来区分物体类别，也就是一个分类器。比如，我们认为猫和狗通常有着不同的颜色，那么我们可以使用图片中的红色均值，绿色均值，蓝色均值这三个值区分这两类。一个简单的线性分类器可以来辨别图片所属类别：
然而仅使用这三种颜色树枝，也就是特征，很显然不足以得到一个完美的分类器。因此，我们决定添加一些描述图片纹理的特征，如x和y方向的平均边缘亮度。结合之前，现在有了5个特征，或许可以用来构建一个区分猫和狗的分类器了。
为了得到一个更准确的分类器，可增加更多的特征，如基于颜色或者纹理直方图统计矩。那我们是否可以获得一个拥有上百维特征的完美分类算法呢？答案听起来有点反直觉：不能得到。实际上，达到一个零界点后，试图通过增加新特征来增加问题的维度将会降低分类器的准确度。如下图所示，一开始，随着维度增加，分类器的性能也随之变好，直到最优特征数量；在没有继续增加训练样本的情况下，继续增加维度，分类器反而效果变差，这也是我们常说的“维度灾难”。如图1所示：
那么为什么会出现这样的现象呢？
在上面的例子中，假设我们有无限的猫狗生活在我们地球上，由于有限的时间和处理能力，我们仅能获取10张猫和狗的图片。但终极目标仍是星辰大海：仅通过这10个训练样本训练出一个分类器，识别出所有的猫和狗。
先尝试一个简单的线性分类器。仅使用1个特征，如图片的红色均值。
图2发现，仅通过单个特征无法得到一个良好的分类器。因此，再增加一个特征，如图片的绿色均值。发现：增加第二个特征仍无法找到一个线性可分的分类器：
最后再添加第三个特征，如图片的蓝色均值，构成一个三维特征空间：
在三维特征空间中，可以找到一个平面完美地分隔开猫和狗。这意味着，在这10个训练图片中，三个特征的线性组合可以得到一个完美的分类器.
以上过程似乎在说明在取得良好分类效果之前，增加特征数量带来的效果在训练过程中是“立竿见影”的，然而并不是这么回事。需要注意的是，随着维度的增加，训练样本密度是呈指数级变少的。
假设特征空间都分为5个空间单元（1维为等长线段，2维为正方形，3维为立方体）。图2中，10个训练数据覆盖1维特征空间，那么在1维空间中，样本密度维10/5=2 （样本/空间单元）。在2维空间（图3）中，10个训练样本仍覆盖拥有5*5=25个单位正方形，其样本密度是10/25=0.4（样本/空间单元）。同理，三维空间例子中，样本密度为10/125=0.08（样本/空间单元）。
如果继续增加特征，那么特征空间不断增长，也就是越来越稀疏，最终结果是会越来越容易找到一个可分离的超平面。因为当特征向量趋向于无穷大时，一个样本被分到超平面分错的可能性会变得无限小。
既然这样，那么维度越高越好吗？
当把一个高维分类器投影到低维空间时，一个严重的问题也将随之而来。图6展示了把三维空间分类器投影到二维空间。可以看到，在三维空间线性可分，并不意味着二维空间也是线性可分。实际上，增加一维特征获得一个简单的线性分类器，和在低维空间使用复杂的非线性分类器是相当的。复杂的非线性分类器会学到训练集合中的特例或者异类。最终，训练得到的分类器在实际预测中对那些“未曾谋面”的数据会表现得糟糕。
这就是过拟合，是维度灾难的直接产物。图7展示由两个特征训练得到的线性分类器。
尽管线性分类器（图7）看起来比非线性分类器（图6），但是在未知数据上简单线性分类器泛化更好。因为线性分类器没有学习仅训练集中有的特例。换而言之，使用更好的特征，可避免过拟合，即分类器也不会在训练集上过拟合。
从另一方式来看：假设所有特征都被归一化到[0, 1]，且特征是每只猫和狗独有的。如果想让训练数据覆盖该维特征的20%，那么训练数据将需要20%所有猫狗样本。如果增加一个特征，为了覆盖二维空间的20%，那么每维上需要45%所有猫狗样本（0.45^2=0.2）。三维场景下，这个数字更甚，每维上需要58%所有猫狗样本才能覆盖三维空间的20%（0.58^3=0.2）。
换句话，如果训练样本的数量是固定的，那么在不断增加特征的情况下维度灾难必然发生。另一方面，如果继续增加特征，训练样本数量需要指数随之增长才能保持一定的覆盖比例来防止过拟合。
在上面例子中，可以看到维度灾难引入了训练数据的稀疏性。特征越多，数据越稀疏，导致分类算法参数的准确估计更加困难。维度灾难的另一个影响是数据稀疏性在搜索空间分布并不均匀。实际上，离超立方体中心近的地方数据稀疏性比超立方体边角更加严重。举个栗子：
想象一个单位正方形代表着一个二维空间。特征空间的均值位于单位正方形的中心，所有离中心单位距离的数据都包含在一个内切单位圆内。而那些落在单位圆外的训练数据离搜索空间边角更近。由于这些样本的特征值变化很大，会很难对其进行正确分类。（譬如分布在对面角落的样本。）因此，如果大部分训练数据分布在单位圆内，分类会更加容易，如图9所示。
一个有意思的问题：当增加特征空间的维度时，内切圆（超球体）的体积如何随着正方形（超立方体）的面积变化而变化呢。假设n维超立方体的体积总是1，半径为0.5的n维超球体的体积有如下公式可以计算得到：
\begin{equation} \label{1}
V(d) = \frac{\pi ^{\frac{d}{2}}}{\Gamma (\frac{d}{2}+1)}0.5^{d}
\end{equation}
图10展示了超球体体积随着维度变化情况。
意味着随着维度趋向于无穷，超球体体积将趋向于0，超球体外体积将保持不变。这个奇怪且反直觉的结论部分解释了在分类中伴随维度灾难而来的问题：在高维空间中，大部分的训练数据位于超立方体（特征空间）的角落。加上前面提到的，角落的样本比靠近中心的样本更难以分类。如图11所示，二维单位正方形，三维单位立方体，以及八维超立方体（$2^{8}=256$个角落）
对于8维超立方体，约98%的样本分布在它的256个角落。当特征空间趋向于无穷大时，样本离中心点的最大最小欧式距离的差值和最小距离的比值趋向于0。
\begin{equation} \label{2}
\lim_{d\rightarrow \infty }\frac{dist_{max}-dist_{min}}{dist_{min}} \rightarrow 0
\end{equation}
因此，距离在高维空间将无法度量相似性。由于分类器依赖于距离度量（如欧拉距离、、马氏距离、曼哈顿距离），分类器在低维空间（使用更少特征描述物体属性）通常更容易。类似地，高维空间中高斯分布更平坦，分布更加长尾。最大最小似然差值和最小似然的比值趋向于0。
参考资料：