我有一个数据集如下
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解决这个问题的方法吗?
谢谢
您可以通过调用实现智能算法的库very efficiently来实现这一点,一个例子是sklearn,它有一个^{} 方法来实现这一点。
为此修改的代码示例:
它给予
你可以用字典来散列一些计算。代码多次计算A到B的距离(A和B是数据集中的两个任意点)。
实现自己的缓存:
或者使用lru_cache:
找到离给定点最近的
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
,生长。相关问题 更多 >
编程相关推荐