python - 成对的 haversine 距离计算

Question

我有两个包含纬度和经度的数组。我想计算数组中每一对纬度和经度与其他每一对纬度和经度之间的距离。 这是我的两个数组。

lat_array

array([ 0.33356456,  0.33355585,  0.33355585,  0.33401788,  0.33370132,
        0.33370132,  0.33370132,  0.33371075,  0.33371075,  0.33370132,
        0.33370132,  0.33370132,  0.33356488,  0.33356488,  0.33370132,
        0.33370132,  0.33370132,  0.33401788,  0.33362632,  0.33362632,
        0.33364007,  0.33370132,  0.33401788,  0.33401788,  0.33358399,
        0.33358399,  0.33358399,  0.33370132,  0.33370132,  0.33362632,
        0.33370132,  0.33370132,  0.33370132,  0.33370132,  0.33370132,
        0.33356488,  0.33356456,  0.33391071,  0.33370132,  0.33356488,
        0.33356488,  0.33356456,  0.33356456,  0.33356456,  0.33362632,
        0.33364804,  0.3336314 ,  0.33370132,  0.33370132,  0.33370132,
        0.33364034,  0.33359921,  0.33370132,  0.33360397,  0.33348863,
        0.33370132])
long_array

array([ 1.27253229,  1.27249141,  1.27249141,  1.27259085,  1.2724337 ,
        1.2724337 ,  1.2724337 ,  1.27246931,  1.27246931,  1.2724337 ,
        1.2724337 ,  1.2724337 ,  1.27254305,  1.27254305,  1.2724337 ,
        1.2724337 ,  1.2724337 ,  1.27259085,  1.27250461,  1.27250461,
        1.27251211,  1.2724337 ,  1.27259085,  1.27259085,  1.27252134,
        1.27252134,  1.27252134,  1.2724337 ,  1.2724337 ,  1.27250461,
        1.2724337 ,  1.2724337 ,  1.2724337 ,  1.2724337 ,  1.2724337 ,
        1.27254305,  1.27253229,  1.27266808,  1.2724337 ,  1.27254305,
        1.27254305,  1.27253229,  1.27253229,  1.27253229,  1.27250461,
        1.27250534,  1.27250184,  1.2724337 ,  1.2724337 ,  1.2724337 ,
        1.27251339,  1.27223739,  1.2724337 ,  1.2722575 ,  1.27237575,
        1.2724337 ])

转换成弧度后。现在我想要第一对纬度和经度与剩余的纬度和经度对之间的距离等等。并想打印对和相应的距离。

这就是我在 python 中所做的。

distance = []
R = 6371.0

for i in range(len(lat_array)):
   for j in (i+1,len(lat_array)):
      dlon = long_array[j]-long_array[i]
      dlat = lat_array[j]-lat_array[i]
      a = sin(dlat / 2)**2 + cos(lat_array[i]) * cos(lat_array[j]) *     
          sin(dlon / 2)**2
      c = 2 * atan2(sqrt(a), sqrt(1 - a))

      distance.append(R * c)

它给我一个错误 IndexError: index 56 is out of bounds for axis 0 with size 56 我哪里做错了？如果数组很大，如何使计算更快？请帮忙。

Answer 1

由于这是目前 Google 在“成对 haversine 距离”方面的最高结果，我要补充两分钱:如果您可以访问 scikit-learn，这个问题可以很快得到解决。查看 sklearn.metrics.pairwise_distances 时，您会注意到不支持“haversine”指标，但它在 sklearn.neighbors.DistanceMetric 中实现。

这意味着您可以执行以下操作:

from sklearn.neighbors import DistanceMetric

def sklearn_haversine(lat, lon):
    haversine = DistanceMetric.get_metric('haversine')
    latlon = np.hstack((lat[:, np.newaxis], lon[:, np.newaxis]))
    dists = haversine.pairwise(latlon)
    return 6371 * dists

请注意，lat 和 lon 的串联是必需的，因为它们是单独的数组。如果您将它们作为 (n_samples, 2) 形状的组合数组传递，您可以直接在它们上调用 haversine.pairwise。此外，仅当您需要以公里为单位的距离时，才需要乘以 6371。例如。如果您只想找到最近的一对点，则不需要此步骤。

验证:

In [87]: lat = np.array([ 0.33356456,  0.33355585,  0.33355585,  0.33401788,  0.33370132])

In [88]: lng = np.array([ 1.27253229,  1.27249141,  1.27249141,  1.27259085,  1.2724337 ])

In [89]: sklearn_haversine(lat, lng)
Out[89]:
array([[ 0.        ,  0.25227021,  0.25227021,  2.90953323,  1.05422047],
       [ 0.25227021,  0.        ,  0.        ,  3.00383463,  0.98975923],
       [ 0.25227021,  0.        ,  0.        ,  3.00383463,  0.98975923],
       [ 2.90953323,  3.00383463,  3.00383463,  0.        ,  2.2276139 ],
       [ 1.05422047,  0.98975923,  0.98975923,  2.2276139 ,  0.        ]])

性能:

In [91]: lat = np.random.randn(1000)

In [92]: lng = np.random.randn(1000)

In [93]: %timeit original_app(lat,lng)
1 loops, best of 3: 1.46 s per loop

In [94]: %timeit vectorized_app1(lat,lng)
10 loops, best of 3: 86.7 ms per loop

In [95]: %timeit vectorized_app2(lat,lng)
10 loops, best of 3: 75.7 ms per loop

In [96]: %timeit sklearn_haversine(lat,lng)
10 loops, best of 3: 76 ms per loop

总而言之，您可以用更短更简单的代码以 vectorized_app2 的速度获得 Divakar 的 vectorized_app1 的输出。