在一个分组中检查坐标与另一个分组的接近程度。

Question

我有两组坐标：

1. {(x1,y1),..(xn,yn)}
2. {(w1,z1),..(wn,zn)}

我想要将每个第二组中的坐标对应到与其最接近的第一组坐标。由于我的数据很大，所以搜索需要很高效。

如果我的两组分别是 Group 1 = {(x1,y1,z1),..(xn,yn,zn)} 和 Group 2 = {(u1,v1, w1),..(un,vn,wn)}，那么我的答案会有何不同？另外，考虑到我的数据太大而无法存储在计算机上，你有什么建议来解决这个问题吗？

- user2468702

---

我认为你不可能有更好的方法，除了计算每个组合的距离并检查最小值。这需要你为n个对象分别计算n次距离，因此仅获取距离就需要n^2次计算。如果你的数据集真的像你说的那样巨大，那么你基本上可以忘记在未来几千年内完成这些计算了。 - Zinki

你已经了解这些点的范围和分布情况了吗？ - Prune

@Prune 你好-- 关于坐标的范围和分布目前还没有信息。高效搜索算法应该适用于任何用户指定的n值。另外如何处理极大的数据集，如果有工作示例会非常感激。谢谢。 - user2468702

Answer 1

你可以使用 KDTree：这个算法可以有效地找到最近的邻居，从而显著减少比较次数。 "KD"代表"k-dimensional"，意味着它可以处理任意维度的数据（回答您上一个问题）。

您可以使用其中一个列表构建树，然后对于另一个列表的每个元素查询最近的元素。Scipy提供了 ktrees的实现。

- Cavaz

---

谢谢您的回复。您能否提供一个小的最小工作示例，可以推广到任何大小为n的坐标？还有关于我的后续问题的任何建议吗？ - user2468702

看起来你想让我们为你编写一些代码。虽然很多用户愿意为有困难的程序员编写代码，但他们通常只会在发帖者已经尝试过自己解决问题时才提供帮助。展示这种努力的好方法是包括一个最小、完整、可验证的示例。查看入门指南，特别是如何提问。 - Prune