维度的诅咒

维度的诅咒指的是在高维空间中分析和组织数据时出现的各种现象，这些现象在低维环境中不会出现，例如日常经验的三维物理空间。

这一表述是理查德-E-贝尔曼在考虑动态编程中的问题时创造的。在数值分析、抽样、组合学、机器学习、数据挖掘和数据库等领域都会出现维度诅咒的现象。

这些问题的共同主题是，当维度增加时，空间的体积迅速增加，以至于可用的数据变得稀少。为了获得一个可靠的结果，所需的数据量往往随着维度的增加而呈指数级增长。

另外，组织和搜索数据往往依赖于检测对象形成具有相似属性的群体的区域；然而，在高维数据中，所有的对象似乎都是稀疏的，而且在许多方面都不相似，这使得普通的数据组织策略无法有效地进行。

组合学在一些问题中，每个变量可以取几个离散的值之一，或者可能的值的范围被划分为有限数量的可能性。把这些变量放在一起，必须考虑大量的数值组合。

这种效应也被称为组合爆炸。即使在最简单的情况下{displaystyled}的最简单的情况下二元变量的最简单情况下，可能的组合数量已经是，在维度上是指数级的。

直观地说，每增加一个维度，尝试所有组合所需的努力就会增加一倍。

在一个数学空间中增加额外的维度，体积会呈指数级增长。例如，102=100个均匀分布的样本点足以对一个单位区间（一维立方体）进行采样，各点之间的距离不超过10-2=0.01；对一个10维单位超立方体进行等效采样，其格子的相邻点之间的间距为10-2=0.01，需要1020=[（102）10]样本点。

一般来说，在间隔距离为10-n的情况下，10维超立方体似乎比1维超立方体（即单位间隔）大10n（10-1）=[（10n）10/（10n）]倍。

在上面的例子中，n=2：当使用0.01的采样距离时，10维超立方体似乎比单位区间大1018。这种效果是上面的组合学问题和下面解释的距离函数问题的结合。

当通过数字后向归纳法解决动态优化问题时，必须对每个值的组合计算目标函数。当状态变量的维度很大时，这是一个很大的障碍。

在机器学习问题中，涉及到从高维特征空间的有限数量的数据样本中学习自然状态，每个特征都有一个可能的值范围，通常需要大量的训练数据以确保每个值的组合都有几个样本。

在抽象的意义上，随着特征或维度数量的增加，我们需要准确归纳的数据量也呈指数级增长。一个典型的经验法则是，每个维度的表征至少要有5个训练实例。

在机器学习中，就预测性能而言，维度的诅咒与峰值现象交替使用，后者也被称为休斯现象。

这种现象表明，在固定数量的训练样本中，分类器或回归器的平均（预期）预测能力首先会随着所用维度或特征数量的增加而增加，但超过一定维度后，预测能力就会开始恶化，而不是稳步提高。

然而，在一个简单的分类器的背景下（在共同的已知协方差矩阵假设下的多元高斯模型中的线性判别分析），Zollanvari等人通过分析和经验表明，只要一个额外的特征集（相对于已经成为分类器一部分的特征）的相对累积功效大于（或小于）这个额外特征集的大小，使用这些额外特征构建的分类器的预期误差将小于（或大于）没有这些特征的分类器的预期误差。

换句话说，在观察平均预测能力的下降或上升时，额外特征的大小和它们（相对）的累积判别效果都很重要。

在数据挖掘中，维度的诅咒指的是一个有太多特征的数据集。考虑xxx个表格，它描述了200个个体和2000个基因（特征），用1或0表示他们是否有基因突变。