在Python中矢量化Haversine距离计算

我正在尝试使用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')

但考虑到时间的复杂性,这需要相当长的一段时间,在20分钟左右运行500分,而且我有更长的清单.这让我看到了矢量化,我遇到过numpy.vectorize((docs),但无法弄清楚如何在这种情况下应用它.

从haversine's function definition,它看起来很可并行化.因此,使用NumPy aka矢量化的最佳工具之一,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 based solution对原始代码的性能改进表现出一些积极的承诺,因此本节将比较基于广播的发布方法与该方法.

功能定义 -

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