维数灾难

数学术语

维数灾难(Curse of Dimensionality)：通常是指在涉及到向量的计算的问题中，随着维数的增加，计算量呈指数倍增长的一种现象。维数灾难涉及数字分析、抽样、组合、机器学习、数据挖掘和数据库等诸多领域。

背景

维数灾难最早是由理查德·贝尔曼（Richard E. Bellman）在考虑优化问题时提出来的，它用来描述当(数学)空间维度增加时，分析和组织高维空间(通常有成百上千维)中的数据，因体积指数增加而遇到各种问题场景。

该名词涉及数字分析、抽样、组合、机器学习、数据挖掘和数据库等诸多领域。在这些领域中，该名词代表的共同特点是：当维度增加时，空间的体积增加得很快，使得可用的数据变得稀疏。稀疏性对于任何要求有统计学意义的方法而言都是一个问题，为了获得在统计学上正确并且有可靠的结果，用来支撑这一结果所需要的数据量通常随着维数的提高而呈指数级增长。而且，在组织和搜索数据时也有赖于检测对象区域，这些区域中的对象通过相似度属性而形成分组。然而在高维空间中，所有的数据都很稀疏，从很多角度看都不相似，因而平常使用的数据组织策略变得极其低效。

“维数灾难”通常是用来作为不要处理高维数据的无力借口。然而，学术界一直都对其有兴趣，而且在继续研究。另一方面，也由于本征维度的存在，其概念是指任意低维数据空间可简单地通过增加空余或随机维将其转换至更高维空间中，相反地，许多高维空间中的数据集也可降维至低维空间数据，而不必丢失重要信息。当前的研究也表明除非其中存在太多不相关的维度，带有维数灾难特色的数据集依然可以处理，因为相关维度实际上可使得许多问题(如聚类分析)变得更加容易。

涉及领域

组合学

在一些问题中，每个变量都可取一系列离散值中的一个，或者可能值的范围被划分为有限个可能性。把这些变量放在一起，则必须考虑很多种值的组合方式，这后果就是常说的组合爆炸。即使在最简单的二元变量例子中，可能产生的组合总数就已经是在维数上呈现指数级的。一般而言，每个额外的维度都需要成倍地增加尝试所有组合方式的影响。

采样

当在数学空间上额外增加一个维度时，其体积会呈指数级的增长。如，点间距离不超过，个均匀间距的样本点足够采样到一个单元区间（“一个维度的立方体”）；一个10维单元超立方体的等价采样，其相邻两点间的距离为，则需要个样本点。一般而言，点距为的10维超立方体所需要的样本点数量，是1维超立方体这样的单元区间的倍。

在上面的n=2的例子中：当样本距离为0.01时，10维超立方体所需要的样本点数量会比单元区间多倍。这一影响就是上面所述组合学问题中的组合结果。

机器学习

在机器学习问题中，需要在高维特征空间(每个特征都能够取一系列可能值)的有限数据样本中学习一种“自然状态”（可能是无穷分布），要求有相当数量的训练数据含有一些样本组合。给定固定数量的训练样本，其预测能力随着维度的增加而减小。

贝叶斯统计

在贝叶斯统计中维数灾难通常是一个难点，因为其后验分布通常都包含着许多参数。

然而，这一问题在基于模拟的贝叶斯推理（尤其是适应于很多实践问题的马尔科夫蒙特卡洛方法）出现后得到极大地克服。当然，基于模拟的方法收敛很慢，因此这也并不是解决高维问题的灵丹妙药。

距离函数

一种用来描述高维欧几里德空间的巨型性的方法是将超球体中半径和维数的比例，和超立方体中边长和等值维数的比例相比较。这样一个球体的体积计算如下：

立方体的体积计算如下：

随着空间维度的增加，相对于超立方体的体积来说，超球体的体积就变得微不足道了。这一点可以从当趋于无穷时比较前面的比例清楚地看出

在某种意义上，几乎所有的高维空间都远离其中心。给定一个单一分布，由于其最小值和最大值与最小值相比收敛于0，即。因此，其最小值和最大值的距离变得不可辨别。

这通常被引证为距离函数在高维环境下失去其意义的例子。