numpy 在Python中矢量化半正矢距离计算

monwx1rj  于 12个月前  发布在  Python
关注(0)|答案(4)|浏览(112)

我试图使用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(docs)),但不知道如何在这种情况下应用它。

xghobddn

xghobddn1#

haversine's function definition来看,它看起来非常 * 可并行化 *。因此,使用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 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
wpx232ag

wpx232ag2#

您可以将函数作为参数提供给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
xtupzzrd

xtupzzrd3#

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

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

说我不确定它会有多快,这看起来像是Python: speeding up geographic comparison的复制品

but5z9lq

but5z9lq4#

查看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 library's page on PyPI

相关问题