python - 对于数组中的每个点，在第二个数组中找到最接近它的点并输出该索引

Question

如果我有两个数组:

X = np.random.rand(10000,2)
Y = np.random.rand(10000,2)

对于 X 中的每个点，如何找出 Y 中最接近它的点？所以最后我有一个数组显示:

x1_index   y_index_of_closest
   1               7
   2               54
   3               3
  ...             ...

我想对 X 中的两列执行此操作，并将每个列与 Y 中的每一列和值进行比较

Answer 1

这个问题很受欢迎。由于类似的问题在这里不断被关闭和链接，我认为值得指出的是，即使现有的答案对于数千个数据点来说相当快，但在那之后它们开始崩溃。我的马铃薯在每个数组中有 10k 个项目时出现段错误。

其他答案的潜在问题是算法的复杂性。他们将 X 中的所有内容与 Y 中的所有内容进行比较。为了解决这个问题，至少平均而言，我们需要一个更好的策略来排除 Y 中的一些事情。

在一维中这很容易——只需对所有内容进行排序并开始弹出最近的邻居即可。在二维中，有多种策略，但 KD 树相当流行，并且已经在 scipy 堆栈中实现。在我的机器上，各种方法之间存在交叉点，其中每个 X 和 Y 都有 6k 个东西。

from scipy.spatial import KDTree

tree = KDTree(X)
neighbor_dists, neighbor_indices = tree.query(Y)

scipy 的 KDTree 实现的极差性能一段时间以来一直是我的痛处，尤其是在它之上构建了如此多的东西。可能有一些数据集表现良好，但我还没有看到。

如果您不介意额外的依赖项，只需切换 KDTree 库即可获得1000 倍的速度提升。 pykdtree 包可以通过 pip 安装，而且我几乎保证 conda 包也能正常工作。通过这种方法，我使用的廉价 chromebook 可以在不到 30 秒的时间内处理 X 和 Y，各处理 1000 万个点。这比在墙上时间的 10,000 个点上的段错误要好;)

from pykdtree.kdtree import KDTree

tree = KDTree(X)
neighbor_dists, neighbor_indices = tree.query(Y)