生成位置与纬度和经度之间距离矩阵的最快方法是什么？

Question

感谢您阅读本文。目前我有很多地方的经纬度，我需要为 10 公里以内的位置创建一个距离矩阵。（远大于10km的位置之间用0距离填充矩阵即可）。

数据看起来像：

place_coordinates=[[lat1, lon1],[lat2,lat2],...]

在这种情况下，我使用下面的代码来计算它，但是需要很长时间。

place_correlation = pd.DataFrame(
   squareform(pdist(place_coordinates, metric=haversine)),
   index=place_coordinates,
   columns=place_coordinates
)

使用squareform时，不知道在10km以外不保存或不计算

最快的方法是什么？

提前致谢！

Answer 1

首先，距离计算需要使用haversine度量吗？你使用哪个实现？如果你会使用例如euclidean 指标你的计算会更快，但我想你有充分的理由选择这个指标。

在这种情况下，最好使用 haversine 的更优化实现（但我不知道您使用的是哪种实现）。检查例如this SO question.

我猜您正在使用 pdist 和 scipy.spatial.distance 中的 squareform。当您查看后面的实现时（here) you will find they are using for loop. In that case you could rather use some vectorized implementation (e.g. this one 来自上面的链接问题）。

import numpy as np
import itertools
from scipy.spatial.distance import pdist, squareform
from haversine import haversine  # pip install haversine

# original approach
place_coordinates = [(x, y) for x in range(10) for y in range(10)]
d = pdist(place_coordinates, metric=haversine)

# approach using combinations
place_coordinates_comb = itertools.combinations(place_coordinates, 2)
d2 = [haversine(x, y) for (x, y) in place_coordinates_comb]

# just ensure that using combinations give you the same results as using pdist
np.testing.assert_array_equal(d, d2)

# vectorized version (taken from the link above)
# 1) create combination (note that haversine implementation from the link above takes (lon1, lat1, lon2, lat2) as arguments, that's why we do flatten
place_coordinates_comb = itertools.combinations(place_coordinates, 2)
place_coordinates_comb_flatten = [(*x, *y) for (x, y) in place_coordinates_comb]
# 2) use format required by this impl
lon1, lat1, lon2, lat2 = np.array(place_coordinates_comb_flatten).T
# 3) vectorized comp
d_vect = haversine_np(lon1, lat1, lon2, lat2)

# it slightly differs from the original haversine package, but it's ok imo and vectorized implementation can be ofc improve to return exactly the same results
np.testing.assert_array_equal(d, d_vect)

比较时间时（绝对数字会因使用的机器而异）：

%timeit pdist(place_coordinates, metric=haversine)
# 15.7 ms ± 364 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit haversine_np(lon1, lat1, lon2, lat2)
# 241 µs ± 7.07 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

这是相当多的（快约 60 倍）。当你有很长的数组时（你使用了多少个坐标？）这可以帮助你很多。

最后，您可以使用您的代码组合它：

place_correlation = pd.DataFrame(squareform(d_vect), index=place_coordinates, columns=place_coordinates)

额外的改进可能是使用另一个指标（例如 euclidean 会更快）来快速说出哪些距离在 10 公里之外，然后计算其余的 haversine。

生成位置与纬度和经度之间距离矩阵的最快方法是什么？

What is the fastest way to generate a matrix for distances between location with lat and lon?

python

pandas

dataframe

scipy

pdist