python - 为第二个数据帧中的每个观察结果从一个 pandas 数据帧中查找最近的(纬度/经度)观察值
问题描述
问题总结:
我有两个数据框。第一个数据帧 (df1) 相对较小(几乎总是少于 100 个观测值,通常少于 50 个),具有一组点标识符及其纬度/经度坐标。第二个数据框(df2)非常大(数十万个观测值),它也有纬度/经度坐标。我希望在 df2 中创建两个新列:第一个具有离 df1 最近的点的标识符,第二个具有到该点的距离。我目前的方法非常笨拙,我认为可以显着优化。对于其他上下文,有一个 df1(小数据帧),但我将对多个 df2s(大数据帧)重复此过程。
设置/示例数据:
# imports:
import pandas as pd
import geopy.distance
from faker import Faker
# creating sample data:
Faker.seed(0)
fake=Faker()
id1=[]
lat1=[]
lon1=[]
id2=[]
lat2=[]
lon2=[]
length1=10 # length of df1
length2=100 # length of df2
for x in range(length1):
a=fake.local_latlng()
id1.append(x)
lat1.append(float(a[0]))
lon1.append(float(a[1]))
for x in range(length2):
a=fake.local_latlng()
id2.append(x)
lat2.append(float(a[0]))
lon2.append(float(a[1]))
dict1={
'loc_id' : id1,
'lat' : lat1,
'lon' : lon1,
}
dict2={
'point_id' : id2,
'lat' : lat2,
'lon' : lon2,
}
df1=pd.DataFrame(dict1)
df2=pd.DataFrame(dict2)
当前解决方案:
# calculating distances:
for x in range(len(df1)):
loc_id=df1.iloc[x]['loc_id']
pt1=(df1.iloc[x]['lat'],df1.iloc[x]['lon'])
for y in range(len(df2)):
pt2=(df2.iloc[y]['lat'],df2.iloc[y]['lon'])
dist=geopy.distance.distance(pt1,pt2).miles
df2.loc[y,x]=dist
# determining minimum distance and label:
temp_cols=list(range(len(df1)))
df2['min_dist']=df2[temp_cols].min(axis=1)
df2['min_loc']=df2[temp_cols].idxmin(axis=1)
# removing extra columns:
df2=df2.drop(temp_cols,axis=1)
print(df2.head())
可能的解决方案:
这段代码显然很慢,因为我计算了每对点的距离。从概念上讲,我认为这可以改进,但我在实施改进时遇到了麻烦。一些想法:
- 矢量化操作。这个公认的答案似乎表明对向量的操作更快,但我不知道如何在向量上实现 geopy.distance.distance() 函数(或者如果可能的话)。
- 通过比较可以说是“支配”的点来消除点。这样,例如,如果一个点在纬度/经度上都比另一个大,那么当与我必须检查的集合中的纬度/经度点中较小的点进行比较时,我可能能够消除它。我想这会增加前端的工作/处理,但最终会通过减少我为每个点检查的点数来获得回报。不过,弄清楚该算法对我来说并不明显。
- 我也许可以将某种点合并到彼此附近的组中,因此可以让较小的候选人集相互比较。也许有可能在计算距离之前找出最近的点。危险在于 df1 中的某些点也可能非常接近。
附加细节: 两个点具有相同距离的几率很小,如果应该出现的话,我很高兴随机选择任何最接近的点。
解决方案
基于使用Balltree的 k 最近邻
方法
- 为 df1 创建 lat/lon 的 k-最近邻树。使用 BallTree,因为它允许自定义距离函数,例如 geopy.distance.distance
- 对于 df2 中的每个纬度/经度,从 1 中找到它在树中的最近点
- 注意:如果我们使用内置距离函数(例如 Haversine),Balltree 会更快
代码
import pandas as pd
import numpy as np
from faker import Faker
from sklearn.neighbors import BallTree
from geopy import distance
import functools
import time
# Timing Decorator
def timer(func):
"""Print the runtime of the decorated function"""
@functools.wraps(func)
def wrapper_timer(*args, **kwargs):
start_time = time.perf_counter() # 1
value = func(*args, **kwargs)
end_time = time.perf_counter() # 2
run_time = end_time - start_time # 3
print(f"Finished {func.__name__!r} in {run_time:.4f} secs")
return value
return wrapper_timer
def generate_data(length):
'''
Genearte data frame with random lat/lon data
Data with same length is always identical since we use same initial seed
'''
Faker.seed(0)
fake = Faker()
id = list(range(length))
# First two fields of fake.local_latlng are lat & lon as string
# Generate vector of fake.local_latlng then unpack out lat/lon array
lat, lon = list(zip(*[fake.local_latlng() for _ in range(length)]))[:2]
# Convert strings to float
lat = [float(x) for x in lat]
lon = [float(x) for x in lon]
return pd.DataFrame({'point_id':id, 'lat':lat, 'lon':lon})
def generate_balltree(df):
'''
Generate Balltree using customize distance (i.e. Geodesic distance)
'''
return BallTree(df[['lat', 'lon']].values, metric=lambda u, v: distance.distance(u, v).miles)
@timer
def find_matches(tree, df):
'''
Find closest matches in df to items in tree
'''
distances, indices = tree.query(df[['lat', 'lon']].values, k = 1)
df['min_dist'] = distances
df['min_loc'] = indices
return df
@timer
def find_min_op(df1, df2):
' OP solution (to compare timing) '
for x in range(len(df1)):
#loc_id=df1.iloc[x]['loc_id'] # not used
pt1=(df1.iloc[x]['lat'],df1.iloc[x]['lon'])
for y in range(len(df2)):
pt2=(df2.iloc[y]['lat'],df2.iloc[y]['lon'])
dist=distance.distance(pt1,pt2).miles
df2.loc[y,x]=dist
# determining minimum distance and label:
temp_cols=list(range(len(df1)))
df2['min_dist']=df2[temp_cols].min(axis=1)
df2['min_loc']=df2[temp_cols].idxmin(axis=1)
# removing extra columns:
df2 = df2.drop(columns = temp_cols)
return df2
测试
df1 = 100 个元素,df2 = 1000 个元素
l1, l2 = 100, 1000
df1 = generate_data(l1)
df2 = generate_data(l2)
tree = generate_balltree(df1)
find_matches(tree, df2)
df2 = generate_data(l2) # Regenerate df2 for next test since find_matches modified it
find_min_op(df1, df2)
输出
Finished 'find_matches' in 32.1677 secs
Finished 'find_min_op' in 147.7042 secs
因此,这种方法在此测试中快了约 5 倍
推荐阅读
- python - Python从基础数组创建多个数组
- python - 如何在保留有效位数的同时在 Python 中将“0.00”读取为数字?
- reactjs - 从 GraphQL 查询数据后如何将数据存储为 React 状态?
- asp.net-core-2.0 - 如何禁用:授权属性自动登录用户
- html - 带布尔玛的固定柱
- java - 使用更新的 javac 编译为 Java 8 编译的 Java 源代码会更有效吗?
- r - 如何使用writeJPEG从R中嵌套数组中所有元素的平均值再现图像
- windows - 我得到“项目无法打开:访问路径被拒绝”
- java - 使用接口的客户端-服务器连接
- java - Java 11 Spring Boot java.lang.ClassNotFoundException:com.sun.xml.ws.api.server.SDDocumentSource$3