高效地计算测地线最近邻居

Question

从经纬度数据（用弧度表示）开始，我正在尝试以地理测量（WGS-84）距离为理想情况，高效地找到最近的n个邻居。

目前，我正在使用sklearn的BallTree和haversine距离（KD-Tres仅采用Minkowski距离），这很快（在7500个可能匹配的1200个位置中查找5个最近邻居需要3-4秒），但不如我所需的准确。 代码:

tree = BallTree(possible_matches[['x', 'y']], leaf_size=2, metric='haversine')
distances, indices = tree.query(locations[['x', 'y']], k=5)

当我用自定义函数替换度量(metric)时（例如：metric=lambda u, v: geopy.distance.geodesic(u, v).miles），运行时间变得“不合理”地长（在与上面相同情况下需要4分钟）。文档记录了自定义函数可能需要很长时间，但无法帮助我解决问题。

我考虑使用ECEF坐标和欧几里得距离的KD-Tree，但我不确定这是否更准确。

如何保持当前方法的速度，同时提高距离精度？

- ZaxR

Answer 1

你的度量指标运行缓慢的主要原因是它是用Python编写的，而sklearn中的其他度量指标是用Cython/C++/C编写的。

例如，对于随机森林，如此处所讨论的或此处所述的，您需要在Cython中实现自己的度量指标，分叉您自己版本的BallTree并在其中包括您的自定义指标。

- Marcus V.