没有k-d树的Python中的最近邻居搜索 [英] Nearest Neighbor Search in Python without k-d tree

问题描述

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

I'm beginning to learn Python coming from a C++ background. What I am looking for is a quick and easy way to find the closest (nearest neighbor) of some multidimensional query point in an 2D (numpy) array of multidimensional points (also numpy arrays). I know that scipy has a k-d tree, but I don't think this is what I want. First of all, I will be changing the values of the multidimensional points in the 2D array. Secondly, the position (coordinates) of each point in the 2D array matters as I will also be changing their neighbors.

我可以编写一个函数，该函数遍历2D数组并测量查询点与数组中的点之间的距离，同时跟踪最小的点(使用科学的空间距离函数来测量距离).有内置的功能可以做到这一点吗?我试图避免尽可能多地遍历python中的数组.我还将有许多查询点，因此将至少有两个"for循环"-一个循环遍历查询点，对于每个查询，一个循环遍历2D数组并找到最小距离.

I could write a function that goes through the 2D array and measures the distance between the query point and the points in the array while keeping track of the smallest one (using a scipy spatial distance function to measure distance). Is there is a built in function that does this? I am trying to avoid iterating over arrays in python as much as possible. I will also have numerous query points so there would be at least two "for loops" - one to iterate through the query points and for each query, a loop to iterate through the 2D array and find the minimum distance.

谢谢您的建议.

推荐答案

如果您的目标是简明扼要，则可以单线执行:

If concise is your goal, you can do this one-liner:

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]

这篇关于没有k-d树的Python中的最近邻居搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！