database - 关于维度灾难

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 中绘制它们，我们相对靠近的 2d 数据会发生什么？如果我们在 3D 中绘制它们，我们可以看到现在它们在我们新的高维空间 (3D) 中彼此之间的距离更远（更稀疏）。结果，找到邻居变得更加困难，因为我们没有足够的数据来处理我们新的第三个特征中的不同值。

您可以想象，随着我们添加更多维度，数据变得越来越分开。（换句话说，如果你想避免我们的数据稀疏，我们需要越来越多的数据）