查找3D欧氏空间中的10个最近点，对于500万个元素目录中的每个元素

假设我有一个500万个点的目录，其3D空间中的x，y，z位置。对于这500万个点中的每一个，我想找到最接近它的10个点（直接的3D欧几里得距离公式）。在Python中，如果我对表中的每个元素执行一个简单的for循环，并在for循环中执行一个数组操作（而不是循环的第二个操作）以查找当前点和所有其他点之间的距离在目录中，这将需要几天/周。我试过一些涉及排序和计算点之间距离的东西，每个表格元素周围只有+/-几千行，但这仍然需要几天时间。查找3D欧氏空间中的10个最近点，对于500万个元素目录中的每个元素

什么是在Python中做到这一点的更快的方法？有没有办法将for循环变成某种向量化的操作？任何机器学习技术（例如scikit-learn）会有帮助吗？或者以某种方式并行化代码有帮助？

来源

2017-09-12 quantumflash

鉴于你的数据，即维3d的欧几里德空间，试图找到最近的10个邻居，这听起来像[空间分区]（https://en.wikipedia.org/wiki/Nearest_neighbor_search#Space_partitioning）的一个很好的候选者，它涉及到将数据放入kd-树，它可以给你真正的好表现！ 'scikit-learn'已经有kd-tree实现。这种方法具有*精确*而不是近似的附加好处。 –

我在R中使用了一个名为RANN的包，它查找“近似”最近的邻居。我用几分钟的时间用25M观察值和8个维度运行它，结果足以满足我的用例。

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

Benchmark of ANN Libraries

来源

2017-09-12 18:27:29 Dustin

查找3D欧氏空间中的10个最近点，对于500万个元素目录中的每个元素

回答

相关问题