在Python中向量化Haversine距离计算

Question

我正在尝试使用Haversine公式计算由纬度和经度标识的位置列表的距离矩阵，该公式需要两个坐标对的元组来生成距离：

def haversine(point1, point2, miles=False):
    """ Calculate the great-circle distance bewteen two points on the Earth surface.

    :input: two 2-tuples, containing the latitude and longitude of each point
    in decimal degrees.

    Example: haversine((45.7597, 4.8422), (48.8567, 2.3508))

    :output: Returns the distance bewteen the two points.
    The default unit is kilometers. Miles can be returned
    if the ``miles`` parameter is set to True.

    """

我可以使用嵌套的for循环来计算所有点之间的距离，如下所示：

data.head()

   id                      coordinates
0   1   (16.3457688674, 6.30354512503)
1   2    (12.494749307, 28.6263955635)
2   3    (27.794615136, 60.0324947881)
3   4   (44.4269923769, 110.114216113)
4   5  (-69.8540884125, 87.9468778773)

使用简单的函数：

distance = {}
def haver_loop(df):
    for i, point1 in df.iterrows():
        distance[i] = []
        for j, point2 in df.iterrows():
            distance[i].append(haversine(point1.coordinates, point2.coordinates))

    return pd.DataFrame.from_dict(distance, orient='index')

但是，考虑到时间复杂度，对于500个数据点，这需要相当长的时间，大约需要20秒，而我的列表要长得多。因此我开始考虑矢量化，并且我发现了numpy.vectorize(文档)，但是我无法弄清如何在这种情况下使用它。

- user3393657

---

可能是重复问题 https://dev59.com/omw15IYBdhLWcg3wYKmo - Joran Beasley

谢谢，我错过了那个！ - user3393657

Answer 1

从haversine函数定义中可以看出，它非常适合进行并行化。因此，使用NumPy的最佳向量化工具之一——broadcasting，并将数学函数替换为NumPy等效函数ufuncs，这里提供了一种向量化解决方案 -

# Get data as a Nx2 shaped NumPy array
data = np.array(df['coordinates'].tolist())

# Convert to radians
data = np.deg2rad(data)                     

# Extract col-1 and 2 as latitudes and longitudes
lat = data[:,0]                     
lng = data[:,1]         

# Elementwise differentiations for lattitudes & longitudes
diff_lat = lat[:,None] - lat
diff_lng = lng[:,None] - lng

# Finally Calculate haversine
d = np.sin(diff_lat/2)**2 + np.cos(lat[:,None])*np.cos(lat) * np.sin(diff_lng/2)**2
return 2 * 6371 * np.arcsin(np.sqrt(d))

运行时测试 -

另一个基于np.vectorize的解决方案已经展现出比原始代码更好的性能表现，因此本节将把发布的广播方法与该方法进行比较。

函数定义 -

def vectotized_based(df):
    haver_vec = np.vectorize(haversine, otypes=[np.int16])
    return df.groupby('id').apply(lambda x: pd.Series(haver_vec(df.coordinates, x.coordinates)))

def broadcasting_based(df):
    data = np.array(df['coordinates'].tolist())
    data = np.deg2rad(data)                     
    lat = data[:,0]                     
    lng = data[:,1]         
    diff_lat = lat[:,None] - lat
    diff_lng = lng[:,None] - lng
    d = np.sin(diff_lat/2)**2 + np.cos(lat[:,None])*np.cos(lat) * np.sin(diff_lng/2)**2
    return 2 * 6371 * np.arcsin(np.sqrt(d))

时间 -

In [123]: # Input
     ...: length = 500
     ...: d1 = np.random.uniform(-90, 90, length)
     ...: d2 = np.random.uniform(-180, 180, length)
     ...: coords = tuple(zip(d1, d2))
     ...: df = pd.DataFrame({'id':np.arange(length), 'coordinates':coords})
     ...: 

In [124]: %timeit vectotized_based(df)
1 loops, best of 3: 1.12 s per loop

In [125]: %timeit broadcasting_based(df)
10 loops, best of 3: 68.7 ms per loop

- Divakar

Answer 2

您可以将您的函数作为参数提供给np.vectorize()，然后可以将其作为参数传递给pandas.groupby.apply，如下所示：

haver_vec = np.vectorize(haversine, otypes=[np.int16])
distance = df.groupby('id').apply(lambda x: pd.Series(haver_vec(df.coordinates, x.coordinates)))

例如，以下是样例数据：

length = 500
df = pd.DataFrame({'id':np.arange(length), 'coordinates':tuple(zip(np.random.uniform(-90, 90, length), np.random.uniform(-180, 180, length)))})

比较500个点：

def haver_vect(data):
    distance = data.groupby('id').apply(lambda x: pd.Series(haver_vec(data.coordinates, x.coordinates)))
    return distance

%timeit haver_loop(df): 1 loops, best of 3: 35.5 s per loop

%timeit haver_vect(df): 1 loops, best of 3: 593 ms per loop

- Stefan

---

据我所知，“向量化”仅仅是为了方便，通常并不会提供任何加速（至少没有任何有意义的加速）。 - Joran Beasley

谢谢，我需要看到一个实现样例，对这一切还很新，无法从文档中弄清楚... - user3393657

Answer 3

首先使用 itertools.product 获取所有组合。

 results= [(p1,p2,haversine(p1,p2))for p1,p2 in itertools.product(points,repeat=2)]

话虽如此，我不确定它会有多快，这看起来可能是Python：加速地理比较的重复。

- Joran Beasley

Answer 4

请查看haversine python library，该库提供了一个方便的haversine_vector函数，用于计算向量化输入的距离。这个功能对于快速计算地理坐标列表之间的距离特别有用。

以下是该库文档中的一个实际示例：

from haversine import haversine_vector, Unit

lyon = (45.7597, 4.8422)  # Coordinates for Lyon (lat, lon)
paris = (48.8567, 2.3508)  # Coordinates for Paris
new_york = (40.7033962, -74.2351462)  # Coordinates for New York

distances = haversine_vector([lyon, lyon], [paris, new_york], Unit.KILOMETERS)

# Resulting array of distances:
# [392.21725956, 6163.43638211]

如果你正在使用包含坐标信息的pandas数据框，并且需要计算多个数据点之间的距离，你可以通过将坐标转换为列表，并使用haversine_vector来轻松实现，如下面的示例所示：

import pandas as pd
from haversine import haversine_vector, Unit

# Assuming you have a pandas dataframe named 'df' with columns 'coord' and 'compared_coord'
df['distance'] = haversine_vector(df['coord'].to_list(), df['compared_coord'].to_list(), unit=Unit.METERS)

这段代码片段可以高效地计算数据框中对应坐标对之间的距离，并将结果存储在一个新的“distance”列中。

要了解更多详细信息和安装说明，请访问haversine库在PyPI上的页面。

- Memin