基础理论-维数灾难问题

• 维数灾难问题
  • 引言
  • 1. 维度再难会带来哪些问题？
  • 2. 如何解决维数灾难问题？

维数灾难问题

---

引言

先思考一个问题： 数据的维度越高越好吗？ 恐怕不是吧，不然为什么机器学习中特征工程如此的重要，简单来说， 当数据维度过高时，会为学习带来一些困难。

其实，任何的机器学习算法，其性能与特征数量的关系往往是这样的：

1. 维度再难会带来哪些问题？

• 数据稀疏： 这很好理解， 因为维数增多，样本密度必然减少， 举例而言：假设我们现在有10个样本， 而每一维的宽度为5个单位， 这样样本密度为 $\frac{10}{5} = 2$ ； 那么在二维空间下， 样本密度为： $\frac{10}{5*5} = 0.4$， 我们看到样本密度成倍数减少，最终造成了数据稀疏。

• 样本分布不均匀：准确的来说，处于中心位置的训练样本比边缘训练样本更加稀疏。

  这点可以通过数学定理来解释：N个点在p维单位球内随机分布，则随着p的增大，这些点会越来越远离单位球的中心，转而往外缘分散。而各点距单位球中心距离的计算公式为：

  $$d(p,N) = (1 - \frac{1}{2}^{\frac{1}{N}})^{\frac{1}{p}}$$

  从另一个角度来看，对于D维空间，位于半径 $r = 1- \epsilon$ 和半径 $r = 1$ 之间的部分占球总体积的百分比是多少？

  答案是，随着D的增加，这个比率接近为1 ， 这也就解释了为什么在高维空间中，球体的大部分体积都聚集在表面附近的薄球壳上。

  $$V_{外} = k * 1 ^ p = k \\ V_环 = V_外 - V_内 = K - K (1-\epsilon)^p \\ \frac{V_环}{V_外} = 1 - (1-\epsilon)^p$$

• 过拟合问题：可以肯定的一点是，样本在高维数据上更容易分类，但是，在高维中训练得到的分类器其实相当于低维空间上的一个复杂非线性分类器，而了解过拟合的同学都应该知道， 模型过于复杂往往是造成过拟合的直接原因。

2. 如何解决维数灾难问题？

• 对于数据稀疏与分布不均的问题，只有通过增加训练样本和降维的方式来解决。
• 对于过拟合问题，可以添加针对过拟合的一些操作来解决。