python - 为 500 万元素目录中的每个元素寻找 3D 欧几里德空间中的 10 个最近点

Question

假设我有一个包含 500 万个点的目录，以及它们在 3D 空间中的 x、y、z 位置。对于这 500 万个点中的每个点，我想找到最接近它的 10 个点(简单的 3D 欧氏距离公式)。

在 python 中，如果我对表中的每个元素执行一个简单的 for 循环，并在 for 循环中执行一个数组操作(不是第二个 for 循环!)以找到当前点与表中所有其他点之间的距离目录，这将需要数天/数周。我已经尝试了一些涉及排序和计算点之间的距离的东西，每个表元素周围只有 +/- 几千行，但这仍然需要几天时间。

在 python 中执行此操作的更快方法是什么？有没有办法将 for 循环变成某种矢量化操作？任何机器学习技术(例如，在 scikit-learn 中)会有帮助吗？或者以某种方式并行化代码有帮助吗？

Answer 1

我在 R 中使用了一个名为 RANN 的软件包，它可以找到“近似”最近的邻居。我用 2500 万个观测值和 8 个维度在几分钟内运行了它，结果对于我的用例来说已经足够好了。

我不确定我使用的包是否有 Python 版本，但我发现这个链接有很多替代品:Benchmark of ANN Libraries

Benchmark of ANN Libraries