关于维度的诅咒

Question

我的问题是关于这个话题，我一直在阅读一些。基本上我的理解是，在更高的维度上，所有的点最终都会非常接近对方。

我的疑问是，这是否意味着用通常的方式计算距离（例如欧几里得）是有效的。如果仍然有效，这意味着在高维度上比较向量时，两个最相似的向量与第三个向量相差不大，即使这第三个向量可能完全不相关。

这样说对吗？那么在这种情况下，你如何判断是否匹配呢？

Answer 1

基本上距离测量还是正确的，然而，当你拥有 "真实世界 "的数据时，它就变得毫无意义，因为数据是有噪声的。

我们这里说的效果是，在一个维度上两点之间的高距离很快就会被其他所有维度上的小距离所掩盖。这就是为什么到最后，所有的点某种程度上最后的距离都是一样的。这一点存在一个很好的例证。

假设我们想根据数据在每个维度上的价值来进行分类。我们只是说把每个维度划分一次（其范围为0...1）。在[0，0.5）中的值为正值，在[0.5，1]中的值为负值。根据这个规则，在3维空间中，有12.5%的空间被覆盖。在5个维度中，只有3.1%。在10个维度中，它小于0.1%。

因此，在每个维度上，我们仍然允许整体数值范围的一半！这已经相当多了。这是相当多的。但所有的最终都只占总空间的0.1%--这些数据点之间的差异在每个维度上都是巨大的，但在整个空间上可以忽略不计。

你可以更进一步说，在每个维度上你只削减了10%的范围。所以你允许在[0，0.9)中取值。你最终的结果仍然是在10个维度中覆盖了不到35%的整个空间。在50个维度中，它是0.5%。所以你看，每个维度中的宽范围数据都被塞进了你的搜索空间中很小的一部分。

这就是为什么你需要降维，你基本上不考虑信息量较小的轴上的差异。

Answer 2

这里用通俗的语言做一个简单的解释。

我试图用下图所示的一个简单的例子来说明这个问题。

假设你有一些数据特征x1和x2（你可以假设它们是血压和血糖水平），你想进行K-最近邻分类。如果我们将数据绘制成2D，我们可以很容易地看到数据很好地分组，每个点都有一些近邻，我们可以用来进行计算。

现在让我们决定考虑一个新的第三个特征x3（比如年龄）来进行分析。案例(b)显示了一种情况，即我们之前的所有数据都来自相同年龄的人。你可以看到，他们都位于年龄(x3)轴线的同一水平上.现在我们可以很快看到，如果我们想考虑年龄来进行分类，年龄(x3)轴线上有很多空位。

我们目前所拥有的数据只超过了年龄的一个层次。如果我们想对一个具有不同年龄的人（红点）进行预测，会发生什么？正如你所看到的，没有足够的数据点靠近这个点，无法计算距离和找到一些邻居。所以，如果我们想用这个新的第三个特征有很好的预测，我们必须去收集更多不同年龄的人的数据来填补年龄轴上的空白。

(C)它本质上显示的是同一个概念。这里假设我们的初始数据，是从不同年龄的人身上收集的。(即我们在之前的2个特征分类任务中，并没有在意年龄，可能认为这个特征对我们的分类没有影响)。

在这种情况下，假设我们的2D数据来自不同年龄的人（第三个特征）。现在，如果我们将相对较近的二维数据绘制成三维数据，会发生什么？如果我们把它们绘制成3D，我们可以看到，现在它们在新的高维空间（3D）中彼此之间的距离更远了，（更稀疏了）。因此，寻找邻域变得更加困难，因为我们没有足够的数据来处理新的第三个特征的不同值。

你可以想象，随着我们增加更多的维度，数据变得越来越分散。(换句话说，如果你想避免我们的数据有稀疏性，我们需要越来越多的数据)