什么是维数灾难？

SVM第一话（回复 SVM1 查看）里提到了“维数灾难”，什么是维数灾难呢？

维数灾难（英语：curseof dimensionality，又名维度的诅咒）是一个最早由理查德·贝尔曼(Richard E. Bellman)在考虑动态优化问题时首次提出来的术语，用来描述当（数学）空间维度增加时，分析和组织高维空间（通常有成百上千维），因体积指数增加而遇到各种问题场景。这样的难题在低维空间中不会遇到，如物理空间通常只用三维来建模。

数据的维数越高，会引发灾难，首先是计算量巨大，不用多说。其次，对于已知样本数目，存在一个特征数目的最大值，当实际使用的特征数目超过这个最大值时，分类器的性能不是得到改善，而是退化。因为在高维空间中，所有的数据都很稀疏，于是导致在相似度度量上，距离计算上都会出现很大的偏差，因为平时我们采用的算法也都会变得很低效。因此，多于多维数据，我们通常采用降维处理（比如主成分，你知道主成分吗？），而SVM机智的采用了核函数技术。

举例来说，100个平均分布的点能把一个单位区间以每个点距离不超过0.01采样；而当维度增加到10后，如果以相邻点距离不超过0.01小方格采样一单位超正方体，则需要1020 个采样点:所以，这个10维的超正方体也可以说是比单位区间大1018倍(这个是Richard Bellman所举的例子)。

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

“维数灾难”通常是用来作为不要处理高维数据的无力借口。然而，学术界一直都对其有兴趣，而且在继续研究。另一方面，也由于本征维度的存在，其概念是指任意低维数据空间可简单地通过增加空余（如复制）或随机维将其转换至更高维空间中，相反地，许多高维空间中的数据集也可削减至低维空间数据，而不必丢失重要信息。这一点也通过众多降维方法的有效性反映出来，如应用广泛的主成分分析方法。针对距离函数和最近邻搜索，当前的研究也表明除非其中存在太多不相关的维度，带有维数灾难特色的数据集依然可以处理，因为相关维度实际上可使得许多问题（如聚类分析）变得更加容易。