我的任务是找到包含某个数据集的最多点的 N 个集群，因为这些集群受到一定大小的限制。目前，我正试图通过将我的数据插入到 kd 树中，迭代数据并找到其最近的邻居，然后在它们创建的集群不超过限制时合并这些点。我不确定这种方法会给我一个全球性的解决方案，所以我正在寻找调整它的方法。如果你能告诉我这会遇到什么类型的问题，那就太好了。
问问题
1417 次
3 回答
7
首先查看scipy.clustering。然后，关键字搜索可以提供有关那里使用的不同算法的大量信息。集群是一个很大的领域，有大量的研究和实际应用，并且有一些简单的方法已经被发现效果很好，所以你可能不想自己动手。
这就是说，聚类算法通常相当容易编程，如果您确实想自己编程，k-means 和凝聚聚类是一些快速完成的最爱。
最后，我不确定您关于以特定大小为界的确切 N 个集群的想法是自洽的，但这取决于您所说的“大小”和“集群”的确切含义（单点是集群吗？） .
更新：
根据下面 OP 的评论，我认为标准聚类方法不会为这个问题提供最佳解决方案，因为没有可以优化的点之间的“距离”的连续度量。尽管在某些情况下它们可能会给出一个很好的解决方案或近似值。对于聚类方法，我会尝试 k-means，因为这种方法的前提是具有固定的 N。
但不是聚类，这似乎更像是一个覆盖问题（即，你有 N 个固定大小的矩形，你试图用它们覆盖所有点），但我对这些不太了解，所以我会把它留给别人。
于 2010-10-08T15:05:36.957 回答
0
如果您的集群数量是固定的，并且您只想最大化这些集群中的点数，那么我认为贪婪的解决方案会很好：
- 找到可以包含最大点数的矩形，
- 删除这些点，
- 找到下一个矩形
- ...
那么如何找到包含最大点数的最大面积A的矩形（实际上每个矩形都会有这个面积）？
矩形对于欧几里得距离来说并不常见，在尝试解决这个问题之前，如果你真的需要矩形或者只是集群大小的一些限制，你能精确吗？圆形/椭圆会起作用吗？
编辑：贪婪将不起作用（见下面的评论），它真的需要是矩形......
于 2010-10-08T18:52:20.500 回答
0
链接文本实际上，我认为这很容易，有两个关键假设。
1）假设“一定大小”，我们可以说“任何簇必须完全包含在半径为r的圆内”。
2）您的所有点都是集群中心的候选“种子”点。
首先计算所有点之间所有小于r的距离。现在仅使用小于 r 的可行边来解决集合覆盖问题。如果任何点的最近邻距离大于 r 距离，则它会形成自己的集群。
于 2010-10-08T20:41:28.187 回答