97

我有两个 2d numpy 数组： x_array 包含 x 方向的位置信息， y_array 包含 y 方向的位置。

然后，我有一长串 x,y 点。

对于列表中的每个点，我需要找到最接近该点的位置（在数组中指定）的数组索引。

基于这个问题，我天真地制作了一些有效的代码： Find nearest value in numpy array

IE

import time
import numpy

def find_index_of_nearest_xy(y_array, x_array, y_point, x_point):
    distance = (y_array-y_point)**2 + (x_array-x_point)**2
    idy,idx = numpy.where(distance==distance.min())
    return idy[0],idx[0]

def do_all(y_array, x_array, points):
    store = []
    for i in xrange(points.shape[1]):
        store.append(find_index_of_nearest_xy(y_array,x_array,points[0,i],points[1,i]))
    return store


# Create some dummy data
y_array = numpy.random.random(10000).reshape(100,100)
x_array = numpy.random.random(10000).reshape(100,100)

points = numpy.random.random(10000).reshape(2,5000)

# Time how long it takes to run
start = time.time()
results = do_all(y_array, x_array, points)
end = time.time()
print 'Completed in: ',end-start

我正在对一个大型数据集执行此操作，并且真的很想加快速度。任何人都可以优化这个吗？

谢谢。

更新：解决方案遵循@silvado 和@justin 的建议（下）

# Shoe-horn existing data for entry into KDTree routines
combined_x_y_arrays = numpy.dstack([y_array.ravel(),x_array.ravel()])[0]
points_list = list(points.transpose())


def do_kdtree(combined_x_y_arrays,points):
    mytree = scipy.spatial.cKDTree(combined_x_y_arrays)
    dist, indexes = mytree.query(points)
    return indexes

start = time.time()
results2 = do_kdtree(combined_x_y_arrays,points_list)
end = time.time()
print 'Completed in: ',end-start

上面的代码将我的代码（在 100x100 矩阵中搜索 5000 个点）加快了 100 倍。有趣的是，使用scipy.spatial.KDTree（而不是scipy.spatial.cKDTree）为我的幼稚解决方案提供了相当的时间，所以绝对值得使用 cKDTree 版本......

4

4 回答 4

94

这是一个scipy.spatial.KDTree例子

In [1]: from scipy import spatial

In [2]: import numpy as np

In [3]: A = np.random.random((10,2))*100

In [4]: A
Out[4]:
array([[ 68.83402637,  38.07632221],
       [ 76.84704074,  24.9395109 ],
       [ 16.26715795,  98.52763827],
       [ 70.99411985,  67.31740151],
       [ 71.72452181,  24.13516764],
       [ 17.22707611,  20.65425362],
       [ 43.85122458,  21.50624882],
       [ 76.71987125,  44.95031274],
       [ 63.77341073,  78.87417774],
       [  8.45828909,  30.18426696]])

In [5]: pt = [6, 30]  # <-- the point to find

In [6]: A[spatial.KDTree(A).query(pt)[1]] # <-- the nearest point 
Out[6]: array([  8.45828909,  30.18426696])

#how it works!
In [7]: distance,index = spatial.KDTree(A).query(pt)

In [8]: distance # <-- The distances to the nearest neighbors
Out[8]: 2.4651855048258393

In [9]: index # <-- The locations of the neighbors
Out[9]: 9

#then 
In [10]: A[index]
Out[10]: array([  8.45828909,  30.18426696])
于 2015-09-25T11:59:48.923 回答
56

scipy.spatial还有一个 kd 树实现：scipy.spatial.KDTree.

做法一般是先用点数据建立kd树。其计算复杂度约为 N log N，其中 N 是数据点的数量。然后可以使用 log N 复杂度来完成范围查询和最近邻搜索。这比简单地循环遍历所有点（复杂度 N）要有效得多。

因此，如果您有重复的范围或最近邻查询，强烈建议使用 kd 树。

于 2012-05-30T15:03:48.890 回答
5

如果您可以将数据转换为正确的格式，那么一种快速的方法是使用以下方法scipy.spatial.distance：

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

特别是pdist提供cdist计算成对距离的快速方法。

于 2012-05-30T14:51:48.320 回答
1

搜索方法有两个阶段：

  1. npt从数据点（您的x y）构建搜索结构，例如 KDTree
  2. 查找nq查询点。

不同的方法有不同的构建时间和不同的查询时间。您的选择在很大程度上取决于：scipy cdistnpt的 构建时间为 0，但查询时间为 ~ 。KDTree构建时间很复杂，查找速度非常快，~ 。nq
npt * nq
ln npt * nq

在常规（曼哈顿）网格上，您可以做得更好：请参阅 (ahem) find-nearest-value-in-numpy-array。

一个小 测试台: : 构建一个 5000 × 5000 2d 点的 KDTree 大约需要 30 秒，然后查询需要微秒； 在我的旧 iMac 上， scipy cdist 2500 万×20 点（所有对，4G）大约需要 5 秒。

于 2021-10-19T12:04:35.120 回答