维度灾难 维数灾难 暂记

距离度量问题

对于基于距离的模型KNN，K-means来说。需要有效的降维，或者大量数据的训练，发现数据的低维流形空间。

Theorem[Beyer et al.99]:Fix $ϵ$ >0 and N,If data is “truly high-dimensional”,the under fairly weak assumptions on the distrbution of the data:
$$\underset{D\to \infty }{\lim }Pr[d_{max}(N,D)\le (1+ϵ)d_{min}(N,D)]=1$$

$$随着维度D的增加，数据之间最大距离与最小距离之间的差距将无限小，使用距离将无法有效的区分数据$$

欧氏距离差别很不明显

随着维度d上升，最大与最小欧氏距离之间的相对差距就趋近于0，因此KNN收敛速度很慢:
$$\underset{d\to \infty }{\lim }E(\frac{dis{t}_{max}(d)-dis{t}_{min}(d)}{dis{t}_{min}(d)})\to 0$$

相关论文

即高斯分布。如果我们观察三维输入空间的高斯密度，它就像一个超球面，其中概率随着半径的平均值而减小，这通常适用于超过3个维度。 壳体在超球面占据的体积分数随着数据维数的增加而增加

high dimension, there is no such thing as interpolatioIn high dimension, everything isextrapolation

对数据量需求的问题

对于线性分类器，需要不断增加维度

需要更多的训练数据

空间大小问题

单位超球的体积

$$\begin{array}{c}{V}_n=\frac{{\pi }^{n/2}}{\Gamma \left(\frac{n}{2}+1\right)}\end{array}$$

       所以更多的体积在超球体外围的空间，随着维度n的增加，超球体所占的比重趋于0.

计算机视觉的傻瓜书:https://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/中文翻译版

参考与更多

知乎：怎样理解 Curse of Dimensionality（维数灾难）?
维数灾难
Curse_of_dimensionality
超球体体积计算

为什么会产生维度灾难？如何解决？

Concentration of spherical Gaussians
为什么高维空间的高斯分布像肥皂泡

如同低微正太和高维正太分布的关系，高维空间中心坍缩。
In high-dimensional space, with the increase of dimension, the ratio of the center of space will shrink to zero, or even the positive looks like a soap bubble (where it is less dense in the center and more dense at the edge) instead of a bold of mold where it is more dense in the center.
In high-dimensional space, with the increase of dimension, the ratio of Space Center will shrink to zero, and even the Gaussian distribution looks like a soap bubble (low center density, high edge density), rather than a model with high center density.

信息论

k -最近邻分类
高维对距离函数的另一个影响涉及使用距离函数从数据集构建的k最近邻 ( k -NN)图。随着维度的增加，k -NN有向图的入度分布变得偏斜，峰值出现在右侧，因为出现了不成比例的集线器数量，即出现在更多其他k -NN 列表中的数据点数据点高于平均值。这种现象会对各种分类技术（包括k-NN 分类器）、半监督学习和聚类，[19]，它也影响信息检索。[20]

异常检测
在 2012 年的一项调查中，Zimek 等人。在高维数据中搜索异常时发现了以下问题： [13]

分数和距离的集中：距离等派生值在数值上变得相似
不相关的属性：在高维数据中，大量的属性可能是不相关的
参考集的定义：对于局部方法，参考集通常是基于最近邻的
不同维度的不可比分数：不同的子空间产生不可比的分数
分数的可解释性：分数通常不再传达语义
指数搜索空间：搜索空间不能再被系统扫描
数据窥探偏差：给定大的搜索空间，对于每个期望的意义，都可以找到一个假设
Hubness：某些对象比其他对象更频繁地出现在邻居列表中。
许多分析的专门方法解决了这些问题中的一个或另一个，但仍有许多未解决的研究问题。

维度的祝福
令人惊讶的是，尽管存在预期的“维度诅咒”困难，但基于最直接方法的常识启发式对于高维问题“可以产生几乎肯定是最优的结果”。[21] 1990 年代后期引入了“维度的祝福”一词。[21] 多诺霍在他的“千年宣言”中清楚地解释了为什么“维度的祝福”将成为未来数据挖掘的基础。[22]在许多应用中都发现了维度祝福的影响，并在测量现象的集中找到了它们的基础。[23]维数现象的一个例子是一个随机点与一个大的有限随机集合的线性可分性，即使这个集合是指数级的，也很有可能：这个随机集合中的元素数量可以随着维度呈指数增长。此外，这个线性泛函可以选择为最简单的线性Fisher判别式。这种可分性定理已被证明适用于广泛的概率分布：一般均匀对数凹分布、立方体中的乘积分布和许多其他族（最近在[23]中进行了评论）。

“次元的祝福和次元的诅咒是同一枚硬币的两个方面。” [24]例如，高维空间中本质上高维概率分布的典型性质是：随机点到选定点的平方距离很可能接近平均（或中值）平方距离. 此属性显着简化了数据的预期几何形状和高维数据的索引（祝福），[25]，但同时，它使高维中的相似性搜索变得困难甚至无用（诅咒）。[26]

齐梅克等人。[13]指出，虽然维度诅咒的典型形式化会影响iid数据，但即使在高维度上，在每个属性中分离的数据也会变得更容易，并认为信噪比很重要：每个属性中的数据都变得更容易添加信号的属性，而仅向数据添加噪声（不相关错误）的属性则更难。特别是对于无监督数据分析，这种效应被称为沼泽化。