如何在一个拥有500,000个点的100维空间中找到距离最近的两个点？

Question

17

我有一个包含500,000个点的100维空间数据库，我想找到最接近的2个点。如何做到呢？

更新：空间是欧几里得空间，抱歉。谢谢大家的回答。顺便说一句，这不是作业。

- Edwin Jose Palathinkal

2

你好，你是从哪里获取到一个100维空间的呢？ - Will A

2

这个问题不够清晰。这是一个数学问题吗？ - Sarmaad

18

@Sarmaad 这个问题可能缺乏很多细节，但它确实很清晰：读完一句话后我完全理解了问题。（尽管空间类型没有被提到，通常默认为欧几里得空间） - Nikita Rybak

1

@louzer：这里是使用KDTree和多进程的暴力方法，http://ideone.com/Z7uSc（你可以用它来测试小数量点的解决方案）。 - jfs

@Will，当我根据某些功能和结构参数绘制所有蛋白质时，我得到了一个104维空间。通过解决k-NN问题，我能够得出一个非常小的数据集，其中只包含最接近的进化亲属。我在这些亲属上运行分类器，以得出所有具有特定属性的蛋白质共同的高精度和高召回率签名。 - Edwin Jose Palathinkal

显示剩余6条评论

5个回答

7

使用kd树。您正在寻找最近邻问题，有高度优化的数据结构处理这种问题。 http://en.wikipedia.org/wiki/Kd-tree 附言：有趣的问题！

- Stefan Mai

6

你可以尝试使用ANN库，但只能可靠地处理20维以下的数据。

- dalle

谢谢。ANN正是我所需要的。希望它可以将所有内容保存在RAM中。 - Edwin Jose Palathinkal

ANN很容易使用，但需要注意的是它是一种近似最近邻实现，因此不能保证完全正确。 - chuck taylor

6

对你的数据运行PCA，将向量从100维转换为20维。然后创建一个K-最近邻树（KD-Tree），并基于欧几里得距离获取最接近的2个邻居。

通常，如果维数非常大，则必须采用蛮力方法（并行+分布式/映射缩减）或基于聚类的方法。

- Muhammad Hasan Khan

谢谢。我正在按照您的建议减少维度。 - Edwin Jose Palathinkal

1

如果您运行PCA 100 -> 20维度，请务必检查方差的分数，即sum(20个特征值) / sum(all)。 - denis

4

使用称为KD-TREE的数据结构。您需要分配大量内存，但是根据您的数据，您可能会发现一两个优化。 http://en.wikipedia.org/wiki/Kd-tree.

我的朋友几年前在他的博士论文上遇到了类似的问题。他的工作涉及10维度的100万个点。我们建立了一个kd-tree库来解决它。如果您想与我们联系，我们可能能够挖出代码。

- selbie

kdtrees 让在 O(log n) 时间内找到给定点的最近邻变得容易，就我所记。是否有一种优化方法可以在少于 O(n log n) 的时间内找到最接近的点对？ - rampion

2

根据维基百科，如果N >> 2^k（其中k是维度，N是点的数量），则kD树是高效的。在这种情况下，2^100 >> 5e5，答案完全是误导性的。-1 - Unreason

10d不等于100d。即使数据点大致位于100d中的一个10维平面上，kd树也无法工作（在我看来）：想象一下一个深度为100的kd树。 - denis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nikita Rybak · Accepted Answer

算法导论中有一章专门讲解如何在二维空间中以O(n*logn)的时间找到两个最近的点。你可以在Google图书上查看。事实上，我建议每个人都去看看，因为他们将分治技术应用于这个问题的方式非常简单、优雅和令人印象深刻。

虽然它不能直接扩展到您的问题（因为常数7将被替换为2^101 - 1），但对于大多数数据集来说，它应该是完全可以胜任的。所以，如果您的输入数据相当随机，它会给您提供O(n*logn*m)的时间复杂度，其中n是点的数量，m是维数。

编辑
这一切都是基于您有欧几里得空间的假设。即，向量v的长度是sqrt(v0^2 + v1^2 + v2^2 + ...)。然而，如果您可以选择度量标准，就可能有其他优化算法的选项。