没有kd树的Python中的最近邻搜索

Question

我开始学习来自C++背景的Python.我正在寻找的是一种快速简便的方法,可以在2D(numpy)多维点数组(也是numpy数组)中找到某个多维查询点的最近(最近邻居).我知道scipy有一棵kd树,但我认为这不是我想要的.首先,我将更改2D数组中多维点的值.其次,2D阵列中每个点的位置(坐标)很重要,因为我也将改变它们的邻居.

我可以编写一个通过2D数组的函数,测量查询点和数组中的点之间的距离,同时跟踪最小的一个(使用scipy空间距离函数来测量距离).是否有内置功能可以做到这一点？我试图尽可能避免在python中迭代数组.我还将有许多查询点,因此至少有两个"for循环" - 一个遍历查询点,每个查询循环迭代2D数组并找到最小距离.

谢谢你的建议.

Answer 1

如果简洁是你的目标,你可以做到这一点:

In [14]: X = scipy.randn(10,2)

In [15]: X
Out[15]: 
array([[ 0.85831163,  1.45039761],
       [ 0.91590236, -0.64937523],
       [-1.19610431, -1.07731673],
       [-0.48454195,  1.64276509],
       [ 0.90944798, -0.42998205],
       [-1.17765553,  0.20858178],
       [-0.29433563, -0.8737285 ],
       [ 0.5115424 , -0.50863231],
       [-0.73882547, -0.52016481],
       [-0.14366935, -0.96248649]])

In [16]: q = scipy.array([0.91, -0.43])

In [17]: scipy.argmin([scipy.inner(q-x,q-x) for x in X])
Out[17]: 4

如果您有多个查询点:

In [18]: Q = scipy.array([[0.91, -0.43], [-0.14, -0.96]])

In [19]: [scipy.argmin([scipy.inner(q-x,q-x) for x in X]) for q in Q]
Out[19]: [4, 9]

Answer 2

您可以计算所有距离scipy.spatial.distance.cdist( X, Y ) 或使用 RTree 获取动态数据：http://gispython.org/rtree/docs/class.html。