如何在Python中更快地计算多个点组合之间的最小地理距离？

Question

如何在Python中更快地计算多个点组合之间的最小地理距离？

3

我试图找出每个客户到店铺之间的最小距离。目前，我的数据中有约1500家商店和约670K名客户。我需要计算670K个客户与1500家商店之间的地理距离，并找到每个客户的最小距离。

我已经创建了下面的Haversine函数：

import numpy as np
def haversine_np(lon1, lat1, lon2, lat2):

    lon1, lat1, lon2, lat2 = map(np.radians, [lon1, lat1, lon2, lat2])

    dlon = lon2 - lon1
    dlat = lat2 - lat1

    a = np.sin(dlat/2.0)**2 + np.cos(lat1) * np.cos(lat2) * np.sin(dlon/2.0)**2

    c = 2 * np.arcsin(np.sqrt(a))
    miles = 6367 * c/1.609
    return miles

我的数据集如下所示，一个客户数据框（cst_geo）和一个店铺数据框（store_geo）。下面的数字是虚构的，因为我无法分享真实数据的片段：

客户ID	纬度	经度
A123	39.342	-40.800
B456	38.978	-41.759
C789	36.237	-77.348

店铺ID	纬度	经度
S1	59.342	-60.800
S2	28.978	-71.759
S3	56.237	-87.348

我写了一个for循环来尝试进行这个计算，但运行时间超过了8小时。我尝试使用deco，但无法进一步优化。

mindist = []
for i in cst_geo.index:
    dist = []
    for j in store_geo.index:
        dist.append(haversine_np(cst_geo.longitude[i], cst_geo.latitude[i],
                                 store_geo.longitude[j], store_geo.latitude[j]))    
    mindist.append(min(dist))

- Jennifer Wu

使用scipy.pdist()吗？ - Pranav Hosangadi

你可以使用k-d树。scipy.spatial中的cKDTree是该数据结构的快速实现。 - Rivers

2

看看这些是否有帮助 - https://stackoverflow.com/a/57696524/, https://dev59.com/b5Lea4cB1Zd3GeqP4Jel#34557996/, https://dev59.com/WqLia4cB1Zd3GeqPospR#44682708/, https://dev59.com/vFsW5IYBdhLWcg3w4aX7#34517218/. - Divakar

1

非常感谢您提供这些链接！此链接完美地运作：https://dev59.com/WqLia4cB1Zd3GeqPospR#44682708 - Jennifer Wu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AlexisG · Accepted Answer

这可以通过使用geopy来实现。

from geopy.distance import geodesic

customers = [
    (39.342, -40.800),
    (38.978, -41.759),
    (36.237, -77.348),
]
stores = [
    (59.342, -60.800),
    (28.978, -71.759),
    (56.237, -87.348),
]
matrix = [[None] * len(customers)] * len(stores)
for index, i in enumerate(customers):
    for j_index, j in enumerate(stores):
        matrix[j_index][index] = geodesic(i, j).meters

输出

[[3861568.3809260903, 3831526.290564832, 2347407.258650098, 2347407.258650098], 
[3861568.3809260903, 3831526.290564832, 2347407.258650098, 2347407.258650098],
 [3861568.3809260903, 3831526.290564832, 2347407.258650098, 2347407.258650098]]

您还可以使用kilometers、miles、feet等单位来表示距离...