在地图上找到靠近给定点的点

数据挖掘 算法 特征提取 特征工程
2022-02-03 09:36:44

我有一个L点（纬度，经度）。我想找到 N=10 个点（我们称它们为仓库），这样：

loss=∑l∈Lmaximumw∈W(distance(l,w))2

被最小化。

是否有解决此问题的文档化算法或方法？现在我在想 Excel 可能能够处理这个任务。但是我有太多的 Excel 数据，需要在 Python / Pandas 中实现。

2个回答

我可以告诉你我会怎么做，但几乎可以肯定会有更快的实现。

假设你开始，对于每个点L，到每个仓库的距离，w∈W. 这些距离应通过半正弦公式计算。

你可以找到距离N中的第一个最近点w通过使用快速选择算法。这与快速排序算法非常相似，但只对您关心的部分进行排序。快速选择的平均情况是O(N)但你需要为每个重复l∈L.

请注意，由于正方形对于正距离是单调的，因此您只需要最小化

∑l∈Lmaximumw∈W(distance(l,w))

我在KoderDojo上找到了一个方便的快速选择算法实现

Scipy 已经拥有大部分工具。

locations = train[['latitude', 'longitude']].values
center = locations.mean(axis=0)
warehouses = np.repeat(np.expand_dims(center, 0), 20, 0)
warehouses = warehouses.flatten()

def Distances(warehouses):
    warehouses = np.reshape(warehouses, [20, 2])
    distances = scipy.spatial.distance.cdist(locations, warehouses)
    closests = distances.min(axis=1)
    other_way = distances.min(axis=0)
    return np.append(closests, other_way)

x = scipy.optimize.least_squares(Distances, warehouses, verbose=2)
其它你可能感兴趣的问题
上一篇F beta 公式的解释 下一篇模糊聚类的数据集