如何按接近度对集合中的对象进行分组?

你可以试试 k-means clustering 算法。

您需要矢量量化:

http://en.wikipedia.org/wiki/Vector_quantization

" 它的工作原理是将一组大的点(向量)划分为最接近它们的点数量大致相同的组。每个组由其质心点表示,如k-means和其他一些聚类算法。 "

这里的向量是每个地址的地理坐标,您可以根据您的约束条件(接近度、组大小、组数……)为算法提供其他参数。

你可以从k-means开始,但根据我的经验,基于Voronoi的算法更灵活。很好的介绍 here .

这在一定程度上取决于您想要聚类的数据的规模。暴力方法是将所有点组合之间的距离计算成距离数组。结果数组为N^2,由于A到B的距离与B到A的距离相同,因此只需要其中的一半,因此结果集为N^2/2。

对于相对接近的lat-lon坐标,您有时可以使用lat-long作为x,y网格并计算笛卡尔距离。由于现实世界不是平的,笛卡尔距离会有误差。如果您的地址位于全国各地,您应该使用更精确的计算方法,请参阅 this link from Mathforum.com .

如果你没有足够的规模来处理整个距离矩阵,你需要做一些算法编程来提高效率。

“N组”和“每组M个地址”约束是互斥的。一个意味着另一个。

1. 构建所有地址之间的距离矩阵。
2. 从随机地址开始,按到该地址的距离升序对矩阵进行排序
3. 在执行过程中从矩阵中删除地址,将最接近起始地址的地址放入一个新组中,直到达到您的标准(组大小或最大距离)。
4. 一旦一个组满了,选择另一个随机地址,并通过距离矩阵来访问该地址
5. 继续这样做,直到从矩阵中取出所有地址。

如果地址均匀分布,每个组在起始地址周围都会有一种圆形形状。当起始地址靠近现有组时,问题就出现了。当这种情况发生时,新组将围绕旧组,如果你的停止标准只是组大小,甚至可以完全环绕它。如果使用最大距离约束,则不会发生这种情况(假设没有其他约束)。

我真的不知道这是不是一个好方法,但这是我会尝试的。我确信需要进行大量的优化。尤其是边缘的地址。