python - 具有指定范围的最近邻一维数据

Question

我有两个嵌套列表 A 和 B:

A = [[50,140],[51,180],[54,500],......]

B = [[50.1, 170], [51,200],[55,510].....]

每个内部列表中的第一个元素从 0 到大约 1e5，第 0 个元素从大约 50 到大约 700，这些元素是未排序的。我想做的是遍历 A[n][1] 中的每个元素并找到 B[n][1] 中最近的元素，但是在搜索最近的邻居时我只想在定义的区间内搜索A[n][0] 正负 0.5。

我一直在使用的功能:

def find_nearest_vector(array, value): 
   idx = np.array([np.linalg.norm(x+y) for (x,y) in array-value]).argmin()
   return array[idx]

例如，它会在坐标 A[0][:] 和 B[0][:] 之间找到最近的邻居。但是，我需要将搜索范围限制在围绕值 A[0][0] 的一些小偏移的矩形内。此外，我不想重用元素 - 我想要在 A[n][0] +/- 0.5 区间内的每个值 A[n][1] 到 B[n][1] 之间的唯一双射。

我一直在尝试使用 Scipy 的 KDTree，但是这个重用了元素，我不知道如何限制搜索范围。实际上，我想在沿特定轴的二维嵌套列表上进行一维 NNN 搜索，其中 NNN 搜索所在的邻域位于由每个内部列表中的第 0 个元素加上或减去一些小偏移定义的超矩形内.

Answer 1

我使用 numpy.argsort()、numpy.searchsorted()、numpy.argmin() 进行搜索。

%pylab inline
import numpy as np
np.random.seed(0)
A = np.random.rand(5, 2)
B = np.random.rand(100, 2)
xaxis_range = 0.02
order = np.argsort(B[:, 0])
bx = B[order, 0]
sidx = np.searchsorted(bx, A[:, 0] - xaxis_range, side="right")
eidx = np.searchsorted(bx, A[:, 0] + xaxis_range, side="left")
result = []
for s, e, ay in zip(sidx, eidx, A[:, 1]):
    section = order[s:e]
    by = B[section, 1]
    idx = np.argmin(np.abs(ay-by))
    result.append(B[section[idx]])
result = np.array(result)

我绘制的结果如下:

plot(A[:, 0], A[:, 1], "o")
plot(B[:, 0], B[:, 1], ".")
plot(result[:, 0], result[:, 1], "x")

输出: