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

我有一组数据聚类为 k 组，每个集群的最小大小限制为 m

我已经对数据进行了一些重新整理。因此，现在我得到了这组要点，每个人都有一个或多个更好的集群，但是不能单独切换，因为它将违反大小约束。

目标:最小化每个点到其群集中心的距离之和。

符合:最小群集大小m

我想找到一种在不违反约束的前提下重新分配所有点的算法，同时保证降低目标。

我想到了使用Graph来表示点之间的成对关系。但是我不确定如何进行重新分配，因为它可能存在较大的密集周期，而且我在多个集群之间交换多个点时迷失了方向。

我还创建了一个群集对的列表，其中包含可能的交换候选对象，但仍然找不到优化目标的方法。

我希望我能解释我的情况。我是算法新手，对术语和规则不熟悉。如果需要其他任何信息，请告诉我。

我做了很多研究，
我已经在本文中尝试了该算法，但是没有成功，因为隶属度的总和不一定与集群大小相关。
Clustering with Size Constraints

我还阅读了SO上的其他类似文章，但没有找到我可以实现的详细算法。

我试图构造一个加权的有向图，其顶点表示聚类，并且从A到B的边缘表示聚类A中愿意重新定位到聚类B的点，而权重为点的总和

但是根据我的数据，结果证明所有节点都处于一个巨大的循环中，边缘非常密集。由于我的经验有限，我仍然不知道如何在这么多集群中重新分配。任何建议表示赞赏!

这样的事情。

最佳答案

要获得最小(不幸的是不是最小)解决方案:

首先，贪婪地重新组合您可以在不违背原则的情况下取得的所有要点
最小大小限制。

接下来，如下构建有向多重图:

每个群集都成为一个节点。

为A中靠近B中心的每个点添加一条边(A，B)(因此，在同一对节点之间可能存在多个边)。它的重量应与移动它所获得的 yield 成正比。

Looking for cycles in this graph将允许您找到招式
(移动包括移动循环中的每个顶点)。

选择总权重最高的循环并重新整理与边缘相对应的节点。

重复步骤1-4，直到没有更多循环为止。

创建图将具有O(kn)的复杂度，其中您总共有k和n个点，并且可以创建相同数量的多边。假设您将多边跳过到DFS中的相同目标，Tarjan的算法将具有O(k2)的复杂度。每次消除循环时，都会将整体距离减小一定程度，并从图形中删除至少一条边，因此算法的总时间不能超过O(k4m2)。那太奢侈了。我确信可能会有试探法(可能还有更详细的分析)来改善下限。