通过每两点之间的距离对集群中的点进行分组的高效算法

Question

我正在为以下问题寻找一种有效的算法：

给定 2D 空间中的一组点，其中每个点由其 X 和 Y 坐标定义。需要将这组点拆分为一组簇，以便如果两个任意点之间的距离小于某个阈值，则这些点必须属于同一簇：

换句话说，这样的集群是一组彼此“足够接近”的点。

朴素算法可能如下所示：

1. 令R是一个结果簇列表，最初为空
2. 设P是一个点列表，最初包含所有点
3. 从P 中随机选取一个点并创建一个仅包含该点的集群C。从P 中删除该点
4. 对于来自P 4a 的每个点Pi。对于来自C 4aa 的每个点Pc。如果distance(Pi, Pc) < 阈值，则将Pi添加到C并将其从P 中删除
5. 如果在步骤 4中至少有一个点被添加到集群C，则转到步骤 4
6. 将集群C添加到列表R。如果P不为空，则转到步骤 3

然而，天真的方法是非常低效的。我想知道这个问题是否有更好的算法？

PS我不知道先验的簇数

Answer 1

这里有一些经典算法：

• 层次凝聚聚类
• DBSCAN

你应该阅读和理解。

Answer 2

1. 将点的空间分割成网格。该网格的单位长度等于threshhold / sqrt(8)。

2. 迭代点列表P，将每个点添加到它所占据的正方形和一个新簇中。如果将一个点添加到已包含一个点的正方形中，则将其添加到其他点的簇中。我将把所有占用的正方形的列表称为S。

3. 现在从S及其簇c中取出任何正方形。对于每个相邻或对角方格，将该方格的簇与c组合并从S中删除该方格。对刚刚添加的所有方块重复该过程。

4. 一旦找不到更多相邻的正方形，簇就完成并可以添加到C中。对S中剩余的方格重复步骤 3 。当S为空时，你就完成了。