java - 基于地理半径的推文聚类算法

Question

我想根据指定的地理半径（如（10 米））对推文进行聚类。例如，如果我指定 10 米半径，那么我希望 10 米内的所有推文都在一个集群中。

一个简单的算法可能是计算每条推文与其他推文之间的距离，但这在计算上会非常昂贵。有更好的算法来做到这一点吗？

Answer 1

您可以在四叉树中组织您的推文。这使得在不查看所有粗花呢及其位置的情况下很容易找到附近的推文。四叉树不直接传递距离（因为它基于曼哈顿距离，但它通过推文为您提供附近，之后您可以计算出精确的距离。

Answer 2

如果您的问题仅在于计算距离：

1. 请记住：如果您只需要比较距离，则永远不要计算距离。改用他们的方块。

   不要比较：

   sqrt((x1-x2)^2+(y1-y2)^2) 对 10

   改为比较

   (x1-x2)^2+(y1-y2)^2 对 100

   它需要的时间大大减少。

2. 如果您在比较距离的平方之前简单地比较坐标，则可以实现另一项改进。如果 abs(x1-x2)>1，你就不需要那对了。（这是史密斯先生所说的曼彻斯特距离）

3. 我不知道你如何处理你的点，但如果它们的集合是稳定的，你可以制作两个数组，并在每个数组中根据其中一个坐标对它们进行排序。之后，您只需要检查两个数组中靠近源点的这些点。