2D点聚类

Question

2D点聚类

algorithmgeometry

20

给定：在二维平面上有一组N个点（x和y坐标），以及与每个点对应的N个半径。我们将称一个点的圆盘为以该点为中心并具有其半径的圆盘。

问题：聚类这些点。点的聚类是指每个点要么落在集群中至少一个其他点的圆盘内，要么至少一个其他点在该点的圆盘内。单个点不算做聚类。

我需要一种高效的算法来计算这个问题（最好不使用复杂的空间哈希技术，例如kd树）。我可以接受O（N^2）运行时间，但绝对不能超过O（N^3）。我觉得这应该很简单，但我卡在了聚类条件的非对称性上。

实质上，我正在寻找填充C函数原型的方法：

int cluster_points(
    size_t n,
    point_t *pt, // length n list of points
    double *radius, // length n list of radii for each point
    int *cluster, // length n list of cluster indexes; -1 if not clustered
    size_t *ncluster // number of clusters (number of distinct non -1 entries in cluster)
);

这不是作业。我需要它作为聚类复数矩阵算法的一部分。

- Victor Liu

5个回答

3

基于局部搜索和Lloyd算法的k-means聚类 http://www.cs.umd.edu/~mount/Projects/KMeans/
(该程序在GNU通用公共许可证下分发。)

k-means，k-medians，k-medoids，treecluster，自组织映射，clustercentroids，clusterdistance http://bonsai.hgc.jp/~mdehoon/software/cluster/cluster.pdf

- Stefan Steiger

k-means不是一个选项。我想要上面所描述的精确包含度量。 - Victor Liu

2

即使您事先知道聚类的数量，聚类仍然是一个NP-Hard问题，因此您可能需要放弃获得多项式运行时间。有许多技术可以解决这个问题，文献主要在机器学习社区中发现，k-means可能是最容易理解和实现的算法。

- fairidox

我不认为我需要使用均值聚类。你可以想象，如果所有的半径都相同，那么你可以循环遍历所有的配对，并确定这些配对是否应该在一个簇中。这定义了图形聚类关系的关联矩阵。之后，您只需要找到图的连通分支（我不是在寻找团）。我相信所有这些都是多项式时间。 - Victor Liu

好的，这有点帮助，但我仍然不完全清楚您要寻找什么。我主要想知道您如何限制簇的大小或数量，即什么阻止我始终声明所有点都在同一个簇中（假设它是完全连接的）。 - fairidox

好的，就像几何图形一样。我在平面上有一堆点，每个点都有一个指定的半径，所以实际上我是在平面上放置一堆圆盘。我想找到所有接触的圆盘组；这些簇是指它们的圆盘重叠形成了平面上更大的非圆形区域（可能带有孔）。簇的大小或数量没有限制；如果半径都为零，则没有簇。如果半径都很大，则只有一个簇。 - Victor Liu

哦，我明白了，这是一个范围搜索。显然，可以通过简单地迭代每对点来使用O(n^2)算法。如果你想更快，就必须使用更复杂的数据结构（kd树）。 - fairidox

如果条件是碟片相互接触，则匹配标准不对称--test(A,B)始终等于test(B,A)。如果条件是一个圆盘的中心在另一个圆盘的半径内，则匹配标准可以是不对称的。我想这就是你上面所说的“非互惠性”。那么，你想要哪个标准？对称的还是不对称的标准？ - Jon Watte

2

听起来，明显的O(n^2)算法是创建一个以点为顶点的图，如果满足你给出的条件，连接两个点。然后读取图的连通分量，丢弃单独的点。此外，你提供的聚类条件对我来说是对称的。我有什么遗漏吗？

- brainjam

我本来希望能够在O(1)的空间内完成这个任务，但是显而易见的方法可能更加直接。集群条件是对称的，但是对于双重循环实现来说，情况并非如此。 - Victor Liu

2

你有一个集合U，其中包含一些点p和它们的半径R。

关系~在U上的定义为：(p,R) ~ (q,S) <=> p位于q的圆盘内或者q位于p的圆盘内 <=> |p-q| <= max(R,S)。

显然，这个关系是自反的、对称的。因此，它的传递闭包(~)是一个等价关系。在~下的等价类将是单例或聚类。
我相信有标准算法可以计算像上面这样关系的传递闭包的等价类。例如，在Numerical Recipes中的排序章节中讨论了这个问题，并且他们说他们的程序基于Knuth。
（抱歉没有提供链接，但简短的搜索并没有找到完全正确的东西）。

- dmuir

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tom10 · Accepted Answer

这个暴力解决方案的时间复杂度只有O(N²)，因此它应该适用于你的情况。

1) 从未分配组中的所有点开始。

2) 选择一个点，并查看未分配组中的所有其他点，看它们是否符合您所描述的半径标准。

2a) 如果是，请开始一个组，并继续处理所有其他点，以查看它们是否符合此组（基于当前点），如果它们符合，则将它们从未分配组移动到此新组中。
2ab) 完成当前点后，请转到添加到该组的每个点并检查未分配组中的所有点。
2b) 但是，如果没有点符合当前点的半径条件，请放弃它。

3) 最后，您将按照自己的标准对点进行分组，并且最多只进行了N *（N / 2）次检查。

顺便说一句，你所描述的不是通常所说的“聚类”，所以我认为这让人们感到困惑。聚类问题的难点在于判断两个相邻点是否属于同一类取决于数据集中的所有其他点。在您的情况下，它（基本上）只取决于两个点的属性，因此在您的情况下，您可以检查它们全部。