我有一个填充了 3817 个坐标（纬度、经度）的数据集。我想要做的是创建约 500 个坐标的组，以便可以使用较小的组来解决车辆路线问题。我想这样做的原因是因为原始数据集很大，解决 VRP 需要太长时间。
我尝试将地图拆分为网格，并根据它们所在的网格简单地对坐标进行分组。但这不是最有效的方法。我已经阅读了 OptaPlanner 的一篇博客文章，他们在其中写了关于附近选择的文章，并希望对我的数据集进行此操作。
关于如何做到这一点的任何想法？
如何使用附近选择之类的方法将一大组坐标拆分为更小的坐标组？
数据挖掘
Python
2022-02-25 10:54:06
2个回答
您最好的选择可能是集群。
层次聚类可以帮助您获得解决方案，因为它基于距离较近的其他人，您可以选择所需的组数。
K 表示聚类也可以帮助您实现这种解决方案，其中 k=500
看看KD-Trees。它们通过（等待它...）树将您的空间划分为离散块来工作。这是 3d 空间的维基百科示例：
每个长方体都由树中的叶子或节点表示。它通过二元拆分工作（通过您可以自己选择的标准将空间分成两部分）。这是算法的简短介绍。
Scikit-Learn 中有一个实现。您构建一棵树，然后您可以查询给定点和半径的数据，返回该半径/距离内的所有点。
这样做的好处是，您还可以通过查询一组坐标来在一组子集上测试您的算法——您只需要构建一次树。
小演示
我将在 2d 整数网格上生成一些随机点随机点，因此值介于 0 和 10 之间。因此，网格上的某些点可能为空。
我将它们放入 Pandas Dataframe 中只是为了让事情更容易管理和绘制：
In [1]: import numpy as np
In [2]: import pandas as pd
In [3]: from sklearn.neighbors import KDTree # could use cKDTree
In [4]: import matplotlib.pyplot as plt
In [5]: data = {"x": np.random.randint(0, 11, 200), "y": np.random.randint(0, 10, 200)} # 200 random coords
In [6]: df = pd.DataFrame(data)
In [7]: df.head()
Out[7]:
x y
0 1 7
1 9 8
2 6 1
3 3 2
4 4 3
现在我创建 KDTree 并查询(5, 5)中心的坐标 - 我希望所有位于半径距离 3 内的点返回：
In [8]: tree = KDTree(df.values)
In [9]: ix = tree.query_radius([(5, 5)], r=3)[0]
现在我使用返回的索引ix（
In [10]: ax = df.plot.scatter("x", "y", c="b", alpha=0.5); # blue base points
In [11]: df.iloc[ix].plot.scatter("x", "y", c="r", ax=ax); # query results
In [12]: plt.scatter(5, 5, c="g"); # query point
In [11]: plt.show()
- 查询点为绿色（5, 5）
- 原始点为蓝色
- 查询结果为红色
请快点！
还有一个cKDTree 类，它的工作方式非常相似，但是是用 C 实现的，因此在许多情况下应该更快。看看这里的一些差异。如果您想像我的示例中那样进行简单查询，cKDTree 是最佳选择！