我有一个包含数千个地址的集合。如果我可以得到每个地址的经度和纬度，我如何按接近度将集合分成组？
此外，我可能想根据不同的规则重试“集群”：
- N组
- 每组 M 个地址
- 组中任何地址之间的最大距离
carrier
问问题
5839 次
5 回答
11
您可以尝试k-means 聚类算法。
于 2009-01-26T16:27:07.523 回答
5
你想要矢量量化：
http://en.wikipedia.org/wiki/Vector_quantization
“它的工作原理是将一大组点（向量）分成最接近它们的点数大致相同的组。每个组都由其质心点表示，如 k-means 和其他一些聚类算法。 “
这里的向量是每个地址的地理坐标，您可以根据您的约束（接近度、组大小、组数......）为您的算法提供其他参数。
您可以从 k-means 开始，但根据我的经验，基于 Voronoi 的算法更灵活。这里有一个很好的介绍。
于 2009-01-26T16:28:11.703 回答
2
这在一定程度上取决于您要集群的数据规模。蛮力方法是将所有点组合之间的距离计算成一个距离数组。结果数组为 N^2，由于 A 到 B 的距离与 B 到 A 的距离相同，因此您只需要其中一半，因此结果集为 N^2/2。
对于相对接近的 lat lon 坐标，您有时可以使用 lat long 作为 x,y 网格并计算笛卡尔距离。由于现实世界不是平坦的，笛卡尔距离会有误差。如果您的地址位于全国各地，则应使用更精确的计算方法，请参阅Mathforum.com 的此链接。
如果您没有处理整个距离矩阵的规模，则需要进行一些算法编程以提高效率。
于 2009-01-26T18:14:03.283 回答
1
“N 个组”和“每组 M 个地址”约束是互斥的。一个暗示另一个。
于 2009-01-26T16:14:02.697 回答
1
- 建立所有地址之间的距离矩阵。
- 从一个随机地址开始，按到该地址的距离升序对矩阵进行排序
- 随着您的进行，从矩阵中删除地址，将最接近起始地址的地址放入一个新组中，直到达到您的标准（组大小或最大距离）。
- 一旦一个组已满，选择另一个随机地址并按到该地址的距离使用矩阵
- 像这样继续，直到所有地址都从矩阵中取出。
如果地址分布均匀，每个组将在起始地址周围形成一种圆形。当起始地址靠近现有组时，问题就出现了。发生这种情况时，如果您的停止标准仅是组大小，新组将环绕旧组，甚至可以完全环绕它。如果您使用最大距离约束，那么这不会发生（假设没有其他约束）。
我真的不知道这是否是一个好方法，但这是我会尝试的。我确信需要进行大量优化。特别是对于边缘的地址。
于 2009-01-26T17:03:02.410 回答