一些维度灾难的知识点

雨点打透心脏的1/2处 2023-07-07 05:42 14阅读 0赞

**sampling采样**

如果数据是低维的，所需的采样点相对就比较少；如果数据是高维的，所需的采样点就会指数级增加，而实现中面对高维问题时往往无法获得如此多的样本点（即使获得了也无法处理这么庞大数据量），样本少不具有代表性自然不能获得正确的结果。

**combinatorics组合数学**

由于每个维度上候选集合是固定的，维度增加后所有组合的总数就会指数级增加。

**machine learning机器学习**

在机器学习中要求有相当数量的训练数据含有一些样本组合。给定固定数量的训练样本，其预测能力随着维度的增加而减小，这就是所谓的*Hughes影响*或*Hughes现象。*

**data mining数据挖掘**

在组织和搜索数据时有赖于检测对象区域，这些区域中的对象通过相似度属性而形成分组。然而在高维空间中，所有的数据都很稀疏，从很多角度看都不相似，因而平常使用的数据组织策略变得极其低效。

**距离在高维环境下失去意义**

在某种意义上，几乎所有的高维空间都远离其中心，或者从另一个角度来看，高维单元空间可以说是几乎完全由超立方体的“边角”所组成的，没有“中部”。一维正态分布有68%的值落于正负标准差之间，而在十维空间上只有0.02%。这对于理解卡方分布是很重要的直觉理解。

卡方分布：若N个随机变量服从标准正态分布，那么它们的平方和（注意在计算欧氏距离时就要用到各个变量的平方和）构成的新的变量服从卡方分布，N是自由度。下面是其概率密度图：

![format_png][]

自由度越大（维度越高）时，图形越”平阔“。

然而，也由于[本征维度][Link 1]的存在，其概念是指任意低维数据空间可简单地通过增加空余（如复制）或随机维将其转换至更高维空间中，相反地，许多高维空间中的数据集也可削减至低维空间数据，而不必丢失重要信息。这一点也通过众多[降维][Link 2]方法的有效性反映出来，如应用广泛的[主成分分析][Link 3]方法。针对距离函数和最近邻搜索，当前的研究也表明除非其中存在太多不相关的维度，带有维数灾难特色的数据集依然可以处理，因为相关维度实际上可使得许多问题（如聚类分析）变得更加容易。另外，一些如[马尔可夫蒙特卡罗][Link 4]或共享最近邻搜索方法[\[3\]][3]经常在其他方法因为维数过高而处理棘手的数据集上表现得很好。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMwMDIuY25ibG9ncy5jb20vaW1hZ2VzLzIwMTIvMTAzNDk2LzIwMTIxMjExMTYwMzA3OTAuanBn?x-oss-process=image/format,png
[Link 1]: http://en.wikipedia.org/wiki/intrinsic_dimension
[Link 2]: http://en.wikipedia.org/wiki/dimension_reduction
[Link 3]: http://zh.wikipedia.org/wiki/%E4%B8%BB%E6%88%90%E5%88%86%E5%88%86%E6%9E%90
[Link 4]: http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo
[3]: http://zh.wikipedia.org/wiki/%E7%BB%B4%E6%95%B0%E7%81%BE%E9%9A%BE#cite_note-houle-ssdbm10-3