我有一个如下的数据集
Id Latitude longitude
1 25.42 55.47
2 25.39 55.47
3 24.48 54.38
4 24.51 54.54
我想为数据集的每个点找到最近的距离。我在互联网上发现了以下距离函数
from math import radians, cos, sin, asin, sqrt
def distance(lon1, lat1, lon2, lat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
"""
# convert decimal degrees to radians
lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])
# haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
c = 2 * asin(sqrt(a))
km = 6367 * c
return km
我正在使用以下函数
shortest_distance = []
for i in range(1,len(data)):
distance1 = []
for j in range(1,len(data)):
distance1.append(distance(data['Longitude'][i], data['Latitude'][i], data['Longitude'][j], data['Latitude'][j]))
shortest_distance.append(min(distance1))
但这段代码对每个条目循环两次,并返回n^2次迭代,因此速度非常慢。我的数据集包含近100万条记录,每次在所有元素中循环两次都会变得非常昂贵
我想找到更好的方法来找出每行最近的点。有谁能帮我找到用python解决这个问题的方法吗
谢谢
你可以使用字典来散列一些计算。代码多次计算A到B的距离(A和B是数据集中的两个任意点)
实现您自己的缓存:
或使用lru_cache:
你可以通过调用一个实现智能算法的库来实现very efficiently,一个例子是sklearn,它有一个^{} 方法来实现这一点
为此修改的代码示例:
给
找到离给定点最近的
N
点的蛮力方法是O(N)
,您必须检查每个点。 相反,如果N
点存储在KD-tree中,则查找最近点平均是O(log(N))
。 构建KD树还需要额外的一次性成本,这需要O(N)
时间如果需要重复此过程
N
次,则蛮力方法为O(N**2)
,kd树方法为O(N*log(N))
。 因此,对于足够大的N
,KD树将击败蛮力方法有关最近邻算法(包括KD树)的更多信息,请参见here
下面(在函数} 计算最近邻的大圆弧长的方法
using_kdtree
中)是一种使用^{scipy.spatial.kdtree
使用点之间的欧几里德距离,但有一个formula用于将球体上点之间的欧几里德弦距离转换为大圆弧长(给定球体半径)。 因此,我们的想法是将纬度/经度数据转换为笛卡尔坐标,使用KDTree
查找最近的邻居,然后应用great circle distance formula获得所需的结果以下是一些基准。使用
N = 100
,using_kdtree
比orig
(蛮力)方法快39倍对于
N = 10000
:由于
using_kdtree
是O(N log(N))
,而orig
是O(N**2)
,因此 哪一个using_kdtree
比orig
快,将随着N
的增长而增长data
,生长相关问题 更多 >
编程相关推荐