维数灾难 维数灾难英語Curse of dimensionality又名维度的詛咒是一个最早由美國應用數學家理查德贝尔曼在考虑优化问题时首次提出来的术语用来描述当数学空间维度增加时分析和组织高维空间通常有成百上千维因体积指数增加而遇到各种问题场景这样的难题在低维空间中不会遇到如物理空间通常只用三维来建模 举例来说个平均分布的点能把一个单位区间以每个点距离不超过采样而当维度增加到后如果以相邻点距离不超过小方格采样一单位超正方体则需要 个采样点所以这个维的超正方体也可以说是比单位区间大倍这个是理查德贝尔曼所举的例子 在很多领域中如采样组合数学机器学习和数据挖掘都有提及到这个名字的现象这些问题的共同特色是当维数提高时空间的体积提高太快因而可用数据变得很稀疏稀疏性对于任何要求有统计学意义的方法而言都是一个问题为了获得在统计学上正确并且有可靠的结果用来支撑这一结果所需要的数据量通常随着维数的提高而呈指数级增长而且在组织和搜索数据时也有赖于检测对象区域这些区域中的对象通过相似度属性而形成分组然而在高维空间中所有的数据都很稀疏从很多角度看都不相似因而平常使用的数据组织策略变得极其低效 维数灾难通常是用来作为不要处理高维数据的无力借口然而学术界一直都对其有兴趣而且在继续研究另一方面也由于本征维度英语intrinsic dimension的存在其概念是指任意低维数据空间可简单地通过增加空余如复制或随机维将其转换至更高维空间中相反地许多高维空间中的数据集也可削减至低维空间数据而不必丢失重要信息这一点也通过众多降维方法的有效性反映出来如应用广泛的主成分分析方法针对距离函数和最近邻搜索当前的研究也表明除非其中存在太多不相关的维度带有维数灾难特色的数据集依然可以处理因为相关维度实际上可使得许多问题如聚类分析变得更加容易另外一些如马尔科夫蒙特卡洛或共享最近邻搜索方法经常在其他方法因为维数过高而处理棘手的数据集上表现得很好