Python最近邻——坐标

Question

我想检查我是否正确使用了 scipy 的 KD 树，因为它看起来比简单的暴力破解要慢。

关于这个我有三个问题:

Q1.

如果我创建以下测试数据:

nplen = 1000000
# WGS84 lat/long
point = [51.349,-0.19]
# This contains WGS84 lat/long
points = np.ndarray.tolist(np.column_stack(
        [np.round(np.random.randn(nplen)+51,5),
         np.round(np.random.randn(nplen),5)]))

并创建三个函数:

def kd_test(points,point):
    """ KD Tree"""
    return points[spatial.KDTree(points).query(point)[1]]

def ckd_test(points,point):
    """ C implementation of KD Tree"""
    return points[spatial.cKDTree(points).query(point)[1]]

def closest_math(points,point):
    """ Simple angle"""
    return (min((hypot(x2-point[1],y2-point[0]),y2,x2) for y2,x2 in points))[1:3]   

我希望 cKD 树是最快的，但是 - 运行这个:

print("Co-ordinate: ", f(points,point))
print("Index: ", points.index(list(f(points,point))))
%timeit f(points,point)

结果时间 - 简单的暴力破解方法更快:

closest_math: 1 loops, best of 3: 3.59 s per loop
ckd_test: 1 loops, best of 3: 13.5 s per loop
kd_test: 1 loops, best of 3: 30.9 s per loop

这是因为我用错了吗？

Q2.

我假设即使要获得最近点的排名(而不是距离)，仍然需要投影数据。但是，投影点和未投影点似乎给了我相同的最近邻居:

def proj_list(points,
              inproj = Proj(init='epsg:4326'),
              outproj = Proj(init='epsg:27700')):
    """ Projected geo coordinates"""
    return [list(transform(inproj,outproj,x,y)) for y,x in points]
proj_points = proj_list(points)
proj_point = proj_list([point])[0]

这仅仅是因为我的点分布不够大而导致失真吗？我重新运行了几次，仍然从返回的投影和未投影列表中得到了相同的索引。

Q3.

与在(未投影的)纬度/经度上计算 haversine 或 vincenty 距离相比，投影点(如上)和计算斜边距离通常更快吗？还有哪个选项会更准确？我进行了一个小测试:

from math import *
def haversine(origin,
              destination):
    """
    Find distance between a pair of lat/lng coordinates
    """
    lat1, lon1, lat2, lon2 = map(radians, [origin[0],origin[1],destination[0],destination[1]])
    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
    c = 2 * asin(sqrt(a))
    r = 6371000  # Metres
    return (c * r)

def closest_math_unproj(points,point):
    """ Haversine on unprojected """
    return (min((haversine(point,pt),pt[0],pt[1]) for pt in points))

def closest_math_proj(points,point):
    """ Simple angle since projected"""
    return (min((hypot(x2-point[1],y2-point[0]),y2,x2) for y2,x2 in points)) 

结果:

所以这似乎是说投影然后做​​距离比不做要快 - 但是，我不确定哪种方法会带来更准确的结果。

在 online vincenty calculation 上测试这个看起来投影坐标是要走的路:

Answer 1

Q1.

k-d 树明显效率低下的原因很简单:您同时测量了 k-d 树的构建和查询。这不是您将或应该使用 k-d 树的方式:您应该只构建一次。如果您仅测量查询，所花费的时间将减少到仅仅几十毫秒(与使用强力方法的几秒相比)。

Q2.

这将取决于所使用的实际数据和所使用的投影的空间分布。根据 k-d 树的实现在平衡构造树方面的效率，可能会有细微的差异。如果您只查询单个点，那么结果将是确定性的，并且无论如何都不受点分布的影响。

对于您正在使用的样本数据，它具有很强的中心对称性，并且对于您的 map 投影(横轴墨卡托)，差异应该可以忽略不计。

Q3.

从技术上讲，您的问题的答案很简单:使用 Haversine 公式进行地理距离测量既更准确又更慢。准确性和速度之间的权衡是否有必要在很大程度上取决于您的用例和数据的空间分布(显然主要取决于空间范围)。

如果您的点的空间范围位于较小的区域一侧，则使用合适的投影和简单的欧几里得距离度量对于您的用例可能足够准确，并且比使用半正弦公式更快。<​​/p>