聚类问题

Question

我被要求在一个特定的数据集中找到包含最多点的N个聚类，并且这些聚类的大小是有限制的。目前，我的做法是把数据放进一个kd树里，遍历数据，找出每个点最近的邻居，然后如果这些点组成的聚类没有超过限制，就把它们合并在一起。不过，我不太确定这种方法能否找到全局最优解，所以我在寻找一些调整的方法。如果你能告诉我这属于什么类型的问题，那就太好了。

Answer 1

如果你的聚类数量是固定的，并且你只想让尽可能多的点在这些聚类里，那么我觉得可以用一种贪心的方法来解决这个问题：

• 找到一个可以包含最多点的矩形，
• 把这些点去掉，
• 再找下一个矩形，
• ……

那么，怎么找到一个最大面积A的矩形（实际上每个矩形都会有这个面积），并且这个矩形能包含最多的点呢？

矩形在欧几里得距离中并不常见，在你尝试解决这个问题之前，能不能先确认一下你真的需要矩形，还是只是想对聚类的大小设个限制？用圆形或椭圆形可以吗？

补充说明：贪心方法是行不通的（见下面的评论），而且确实需要用矩形……

Answer 2

链接文本其实，我觉得这个问题很简单，只要有两个关键的假设。

1) 假设我们说的“某个大小”是指“任何聚类必须完全包含在一个半径为r的圆圈内”。

2) 所有的点都是候选的“种子”点，位于聚类的中心。

首先，计算所有点之间的距离，找出那些小于r的距离。然后，利用这些小于r的可行边来解决一个集合覆盖的问题。如果有任何一个点的最近邻居距离超过r，那么它就会形成自己的聚类。

Answer 3

可以先看看 scipy.clustering 这个网站。你可以通过关键词搜索，找到很多关于那里的不同算法的信息。聚类是一个很大的领域，有很多研究和实际应用，还有一些简单的方法效果不错，所以你可能不需要一开始就自己从头开始编写代码。

不过，聚类算法一般来说比较容易编程。如果你想自己写的话，k-means（K均值聚类）和聚合聚类是一些比较受欢迎的，且实现起来比较快的方法。

最后，我不太确定你提到的“恰好N个聚类，且每个聚类有一定大小”的想法是否合理，这要看你具体怎么定义“大小”和“聚类”（单个点算不算一个聚类呢？）。

更新：

根据楼主下面的评论，我觉得标准的聚类方法可能无法给出这个问题的最佳解决方案，因为没有一个可以优化的“距离”度量来衡量点与点之间的关系。虽然在某些情况下，它们可能会给出一个不错的解决方案或近似值。对于聚类方法，我会尝试k-means，因为这个方法的前提是有固定的N。

不过，这个问题看起来更像是一个 覆盖问题（也就是说，你有N个固定大小的矩形，想用它们覆盖所有的点），但我对这些了解不多，所以就不多说了。