前言
您的问题与最近邻搜索(NNS) 有关。解决它的一种方法是像在空间数据库中那样构建空间索引。
一个简单的解决方案是KD-Tree，它在sklearn.
问题
在这一点上，必须知道我们要回答什么问题：
Q1.a）atol在给定阈值（半径）内找到数据集 B 中与 A 的（距离）点一样近的所有点。
或者：
Q2.a)找到k数据集 B 中相对于我的数据集 A 的每个点的最近点。
这两个问题都可以使用 KD-Tree 来回答，我们必须意识到的是：
- 问题 Q1 和 Q2 不同，它们的答案也不同；
- Q1可以将0个或多个点映射在一起，不保证一对一映射；
- Q2 将精确地映射 1
k到点，保证参考数据集中的所有点都映射到k搜索数据集中的点（前提是有足够的点）；
- Q2.a 通常不等同于其倒数问题 Q2.b（当数据集 A 和 B 被置换时）。
MCVE
让我们构建一个 MCVE 来解决这两个问题：
# Parameters
N = 50
atol = 50
keys = ['x', 'y']
# Trials Datasets (with different sizes, we keep it general):
df1 = pd.DataFrame(np.random.randint(0, 500, size=(N-5, 2)), columns=keys).reset_index()
df2 = pd.DataFrame(np.random.randint(0, 500, size=(N+5, 2)), columns=keys).reset_index()
# Spatial Index for Datasets:
kdt1 = KDTree(df1[keys].values, leaf_size=5, metric='euclidean')
kdt2 = KDTree(df2[keys].values, leaf_size=5, metric='euclidean')
# Answer Q2.a and Q2.b (searching for a single neighbour):
df1['kNN'] = kdt2.query(df1[keys].values, k=1, return_distance=False)[:,0]
df2['kNN'] = kdt1.query(df2[keys].values, k=1, return_distance=False)[:,0]
# Answer Q1.a and Q1.b (searching within a radius):
df1['radius'] = kdt2.query_radius(df1[keys].values, atol)
df2['radius'] = kdt1.query_radius(df2[keys].values, atol)
将数据集 A 的结果作为参考：
index x y kNN radius
0 0 65 234 39 [39]
1 1 498 49 11 [11]
2 2 56 171 19 [29, 19]
3 3 239 43 20 [20]
4 4 347 32 50 [50]
[...]
至此，我们拥有了空间连接数据所需的一切。
最近的邻居(k=1)
我们可以使用 kNN 索引加入我们的数据集：
kNN1 = df1.merge(df2[['index'] + keys], left_on='kNN', right_on='index', suffixes=('_a', '_b'))
它返回：
index_a x_a y_a kNN radius index_b x_b y_b
0 0 65 234 39 [39] 39 49 260
1 1 498 49 11 [11] 11 487 4
2 2 56 171 19 [29, 19] 19 39 186
3 3 239 43 20 [20] 20 195 33
4 4 347 32 50 [50] 50 382 32
[...]
从图形上看，它导致：
互惠问题是关于：
我们看到映射完全是1参考数据k=1集中的所有点都映射到搜索数据集中的另一个点。但是当我们交换参考时答案会有所不同。
半径atol
我们还可以使用半径索引加入我们的数据集：
rad1 = df1.explode('radius')\
.merge(df2[['index'] + keys], left_on='radius', right_on='index',
suffixes=('_a', '_b'))
它返回：
index_a x_a y_a kNN radius index_b x_b y_b
0 0 65 234 39 39 39 49 260
2 1 498 49 11 11 11 487 4
3 2 56 171 19 29 29 86 167
4 2 56 171 19 19 19 39 186
7 3 239 43 20 20 20 195 33
[...]
图形化：
倒数答案是等价的：
我们看到答案是相同的，但不能保证一对一的映射。有些点没有映射（孤点），有些映射到许多点（密集邻域）。此外，它需要一个额外的参数atol，必须针对给定的上下文进行调整。
奖金
下面是渲染图形的函数：
def plot(A, B, join, title=''):
X = join.loc[:,['x_a','x_b']].values
Y = join.loc[:,['y_a','y_b']].values
fig, axe = plt.subplots()
axe.plot(A['x'], A['y'], 'x', label='Dataset A')
axe.plot(B['x'], B['y'], 'x', label='Dataset B')
for k in range(X.shape[0]):
axe.plot(X[k,:], Y[k,:], linewidth=0.75, color='black')
axe.set_title(title)
axe.set_xlabel(r'$x$')
axe.set_ylabel(r'$y$')
axe.grid()
axe.legend(bbox_to_anchor=(1,1), loc='upper left')
return axe
参考
一些有用的参考：
