logo标签列表

如何通过接近度将对象分组到一个集合中？

algorithmcluster-analysismachine-learning
7

我有一个包含数千个地址的集合。如果我可以获取每个地址的经纬度，如何按照接近程度将该集合分成组？

此外，我可能希望根据不同规则重新尝试“聚类”：

  • N组
  • 每组M个地址
  • 组内任何地址之间的最大距离
5个回答
11
5

你想要向量量化：

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

"它的工作原理是将一组大点（向量）分成具有大致相同数量的最接近它们的点的组。每个组由其质心点表示，就像k-means和其他一些聚类算法一样。"
"

在这里，向量是每个地址的地理坐标，并且您可以根据约束条件（接近度、组大小、组数等）使用其他参数来提供算法。

"
"

您可以从k-means开始，但从我的经验来看，基于Voronoi的算法更加灵活。一个好的介绍在这里。

"
2
这取决于您想要聚类的数据规模。暴力方法是计算所有点之间的距离，并将其存储在一个距离数组中。由此得到的数组为N^2，由于从A到B的距离与从B到A的距离相同，因此您只需要一半，所以结果集为N^2/2。
对于相对接近的经纬度坐标，您有时可以使用经纬度作为x，y网格并计算笛卡尔距离。由于现实世界不是平面的，因此笛卡尔距离会产生误差。如果您的地址位于全国各地，则应使用更精确的计算方法，请参见this link from Mathforum.com。
如果您没有处理整个距离矩阵的规模，则需要进行一些算法编程以提高效率。
格里夫斯先生已经给出了与我相同的答案。这就是我在开始回答后去锻炼，然后回来完成回答的结果！ - JD Long
你已经描述了计算所有相关距离到一个N^2/2半矩阵的第一个技术阶段，但是考虑到这一点，你如何进行分组呢？ - Motti Shneor
1

"N组"和"每组M个地址"的限制是互斥的。一个暗示着另一个。

你可以有N个组，每个组中地址数量不同吗？ - carrier
但这不是一个限制条件。这将是算法的结果。 - srmark
哪个不是限制条件？ 无论如何，如果我说每组必须有M个地址，那么我可能最终会得到一个已知数量为N的组。但是如果我指定必须有N个组，则每组M个地址可能是一个结果，也可能不是。 - carrier
1
  1. 建立所有地址之间距离的矩阵。
  2. 从一个随机地址开始，按照到该地址的距离升序排序矩阵。
  3. 在沿途删除矩阵中的地址时，将最靠近起始地址的地址放入新组，直到达到您的标准（组大小或最大距离）。
  4. 一旦一个组已满，选择另一个随机地址并按距离重新排序矩阵。
  5. 继续这样做，直到所有地址都被从矩阵中取出。

如果地址分布均匀，则每个组围绕起始地址形成一种圆形。问题在于起始地址靠近现有组时。当发生这种情况时，新组将围绕旧组缠绕，并且甚至可能完全包围它，如果您的停止标准仅为组大小，则会发生这种情况。如果使用最大距离约束，则不会发生这种情况（假设没有其他约束）。

我不知道这是否是一个好方法，但这是我尝试的方法。我相信需要进行大量优化。特别是对于边缘地址。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接