如何按照邻近性对一组中的对象进行分组？

Question

我有一套包含数千个地址。如果我能得到每个地址的经度和纬度，我该如何按照邻近度将这个集合分组？

此外，我可能要重试根据不同的规则的“聚类”：

• N个组，每组
• M个地址的基团中的任意地址之间
• 最大距离

Answer 1

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

Answer 2

“N组”和“每个组的M个地址”限制是相互排斥的。一个暗示另一个。

Answer 3

你想矢量量化：

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

“它通过将一大组点（矢量）的成具有大约相同数目的最接近他们点的组，每组由下式表示它的质心点，如k-means和其他一些聚类算法“

这里的向量是每个地址的地理坐标，并且可以根据你的约束条件给你的算法提供其他参数（proximity，gr大小，组数......）。

您可以从k-means开始，但根据我的经验，基于Voronoi的算法更加灵活。一个很好的介绍here。

Answer 4

1. 构建所有地址之间的距离矩阵。
2. 从一个随机地址开始，按照该地址的上升距离对矩阵进行排序
3. 随着您的移动，从矩阵中删除地址，将距离起始地址最近的地址放入一个新组，直到达到您的标准组的大小或最大距离）。
4. 一旦一个组被填满，选择另一个随机地址，并通过距离到该地址
5. 继续这样做，直到所有地址都被取出矩阵。

如果地址是均匀分布的，每个组的起始地址周围都会有一种圆形的形状。当起始地址靠近现有组时，问题就出现了。发生这种情况时，如果停止标准仅为组大小，新组将围绕旧组进行排序，甚至可以将其圈起来。如果使用最大距离约束，那么这不会发生（假设没有其他约束）。

我不知道这是否是一种很好的做法，但这是我的尝试。我相信很多优化是必需的。特别是对于边缘地址。

Answer 5

这取决于你想要聚类的数据的规模。蛮力方法是计算距离数组中所有点组合的距离。得到的数组是N^2，并且由于A到B的距离与B到A的距离相同，所以只需要一半，所以得到的集合是N^2/2。

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

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