Python中不使用k-d树的最近邻搜索

Question

我刚开始学习Python，之前是用C++的。现在我想找一个简单的方法，来找出在一个二维的（numpy）数组中，某个多维查询点最近的邻居。这个二维数组里也存放着多维点（同样是numpy数组）。我知道scipy有一个k-d树，但我觉得这不是我想要的。首先，我会改变这个二维数组中多维点的值。其次，每个点在二维数组中的位置（坐标）也很重要，因为我还会改变它们的邻居。

我可以写一个函数，遍历这个二维数组，测量查询点和数组中每个点之间的距离，同时记录下最小的那个（可以用scipy的空间距离函数来测量距离）。但是有没有现成的函数可以做到这一点呢？我尽量想避免在Python中反复遍历数组，因为我还有很多查询点，这样就至少需要两个“for循环”——一个用来遍历查询点，另一个则是对每个查询点遍历二维数组，找出最小距离。

谢谢任何建议。

Answer 1

你可以通过 scipy.spatial.distance.cdist( X, Y ) 来计算所有的距离，或者使用 RTree 来处理动态数据：http://gispython.org/rtree/docs/class.html。

Answer 2

广播功能在这种情况下非常有用。我不确定这是否正是你需要的，但在这里我使用广播来计算点 p（在三维空间中的一个点）和 X（在三维空间中的一组10个点）之间的位移。

import numpy as np

def closest(X, p):
    disp = X - p
    return np.argmin((disp*disp).sum(1))

X = np.random.random((10, 3))
p = np.random.random(3)

print X
#array([[ 0.68395953,  0.97882991,  0.68826511],
#       [ 0.57938059,  0.24713904,  0.32822283],
#       [ 0.06070267,  0.06561339,  0.62241713],
#       [ 0.93734468,  0.73026772,  0.33755815],
#       [ 0.29370809,  0.76298588,  0.68728743],
#       [ 0.66248449,  0.6023311 ,  0.76704199],
#       [ 0.53490144,  0.96555923,  0.43994738],
#       [ 0.23780428,  0.75525843,  0.46067472],
#       [ 0.84240565,  0.82573202,  0.56029917],
#       [ 0.66751884,  0.31561133,  0.19244683]])
print p
#array([ 0.587416 ,  0.4181857,  0.2539029])
print closest(X, p)
#9

Answer 3

如果你想让代码简洁，可以用这一行代码：

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]