聚类问题

Question

我的任务是找到N个簇,其中包含特定数据集的最多点,因为簇具有一定的大小.目前,我试图通过将我的数据插入到kd树中,迭代数据并找到它的最近邻居,然后在他们制作的集群不超过限制时合并这些点来尝试这样做.我不确定这种方法会给我一个全局解决方案,所以我正在寻找方法来调整它.如果你能告诉我这会遇到什么类型的问题,那也很棒.

Answer 1

查看scipy.clustering开始.关键词搜索可以提供有关在那里使用的不同算法的大量信息.聚类是一个很大的领域,有大量的研究和实际应用,并且已经发现许多简单的方法可以很好地工作,所以你可能不想从自己开始.

这就是说,聚类算法通常很容易编程,如果你想编写自己的编程算法,那么k-means和凝聚聚类是一些很容易做到的.

最后,我不确定你对一定大小限制的N个簇的想法是自洽的,但它取决于你的"大小"和"簇"的确切含义(群集是单点吗？) .

更新:

根据下面的OP评论,我认为标准聚类方法不会给出这个问题的最佳解决方案,因为对于可以优化的点之间的"距离"没有连续的度量.虽然在某些情况下它们可能会提供良好的解决方案或近似值.对于聚类方法,我尝试k-means,因为这种方法的前提是具有固定的N.

但是,而不是集群,这似乎更像是一个覆盖问题(即,你有固定的尺寸为N长方形和你试图覆盖所有与他们分),但我不知道很多关于这些,所以我留给别人.