具有最小大小约束的聚类算法

Question

我有一组数据聚类到k组,每个聚类的最小大小约束为m

我做了一些重新复制的数据.所以现在我得到了这一组点,每个点都有一个或多个更好的簇,但不能单独切换,因为它会违反大小约束.

目标:最小化从每个点到其中心的距离之和.

受制于:最小簇大小m

我想找到一种算法来重新分配所有点而不违反约束,同时保证减少目标.

我想过使用Graph来表示点之间的成对关系.但我不确定如何进行重新分配,因为它存在大密集循环的可能性,而且我在多个集群之间交换多个点时迷失了方向.

我还创建了一个具有可能的交换候选者的聚类对列表,但仍然无法找到最佳目标的方法.

我希望我解释了我的情况.我是算法新手,不熟悉行话和规则.如果需要任何其他信息,请告诉我.

我已经做了很多研究,我已经在本文中尝试了算法,但没有成功,因为会员度的总和不一定与簇大小相关. 使用大小约束进行聚类

我还在SO上阅读了其他类似的帖子,但没有找到我可以实现的详细算法.

我试图构建一个加权有向图,顶点表示簇,A到B的边表示簇A中的点,它们愿意重新定位到簇B.并且权重是点的总和

但是根据我的数据,结果表明所有节点都处于一个边缘非常密集的巨大周期中.由于我的经验有限,我仍然无法弄清楚如何在如此多的集群中重新分配.任何建议表示赞赏!

像这样的东西.

Answer 1

要获得最小（不幸的是不是最小）解决方案：

1. 首先，在不违反最小尺寸约束的情况下，贪婪地重新聚集任何点。
2. 接下来，构建一个有向多重图，如下所示：
   1. 每个集群都成为一个节点。
   2. 为 A 中更靠近 B 中心的每个点添加一条边 (A,B) （以便同一对节点之间可能存在多条边）；它的重量应该与移动它所获得的收益成正比。
3. 在此图中查找循环将允许您找到移动（其中移动包括移动循环中的每个顶点）。
4. 选择总权重最高的环，并对边对应的节点进行重新聚类。
5. 重复步骤 1-4，直到不再有循环。

创建图形的复杂度为 O(kn)，其中总共有 k 和 n 个点，并且可以创建相同数量的多重边。Tarjan 的算法的复杂度为 O(k ² )，假设您将多重边跳过到 DFS 中的同一目的地。每次消除一个环路时，都会将全局距离减小一定量，并从图中删除至少一条边，因此算法的总时间不能超过 O(k ⁴ m ² )。这实在是太奢侈了；我确信可以通过启发式方法（可能还有更详细的分析）来提高下限。