最近邻搜索 kdTree

Question

对于 N 点列表 [(x_1,y_1), (x_2,y_2), ... ] 我试图根据距离找到每个点的最近邻居。我的数据集太大，无法使用蛮力方法，因此 KDtree 似乎是最好的。

我看到 sklearn.neighbors.KDTree 可以找到最近的邻居，而不是从头开始实施。这可以用来找到 每个 粒子的最近邻居，即返回一个 dim(N) 列表吗？

原文由 RedPen 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这个问题非常广泛，缺少细节。目前还不清楚你做了什么尝试，你的数据看起来如何以及最近的邻居是什么（身份？）。

假设您对身份不感兴趣（距离为 0），您可以查询两个最近的邻居并删除第一列。这可能是这里最简单的方法。

代码：

  import numpy as np
 from sklearn.neighbors import KDTree
 np.random.seed(0)
 X = np.random.random((5, 2))  # 5 points in 2 dimensions
 tree = KDTree(X)
 nearest_dist, nearest_ind = tree.query(X, k=2)  # k=2 nearest neighbors where k1 = identity
 print(X)
 print(nearest_dist[:, 1])    # drop id; assumes sorted -> see args!
 print(nearest_ind[:, 1])     # drop id

输出

 [[ 0.5488135   0.71518937]
  [ 0.60276338  0.54488318]
  [ 0.4236548   0.64589411]
  [ 0.43758721  0.891773  ]
  [ 0.96366276  0.38344152]]
 [ 0.14306129  0.1786471   0.14306129  0.20869372  0.39536284]
 [2 0 0 0 1]

原文由 sascha 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

您可以使用 sklearn.neighbors.KDTree 的 query_radius() 方法，它返回 某个半径内 最近邻居的 索引 列表（而不是返回 k 最近邻居）。

 from sklearn.neighbors import KDTree

points = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]

tree = KDTree(points, leaf_size=2)
all_nn_indices = tree.query_radius(points, r=1.5)  # NNs within distance of 1.5 of point
all_nns = [[points[idx] for idx in nn_indices] for nn_indices in all_nn_indices]
for nns in all_nns:
    print(nns)

输出：

 [(1, 1), (2, 2)]
[(1, 1), (2, 2), (3, 3)]
[(2, 2), (3, 3), (4, 4)]
[(3, 3), (4, 4), (5, 5)]
[(4, 4), (5, 5)]

请注意，每个点都将其自身包含在给定半径内的最近邻居列表中。如果要去除这些标识点，可以将线计算 all_nns 改为：

 all_nns = [
    [points[idx] for idx in nn_indices if idx != i]
    for i, nn_indices in enumerate(all_nn_indices)
]

导致：

 [(2, 2)]
[(1, 1), (3, 3)]
[(2, 2), (4, 4)]
[(3, 3), (5, 5)]
[(4, 4)]

原文由 scrpy 发布，翻译遵循 CC BY-SA 3.0 许可协议