我有一组 N 个对象，它们之间有 N * N 个距离。我想将这个集合聚类到子集上，这样在每个聚类中，所有对象都具有相同的距离，并且所有聚类上的均值(cluster_size)最大化。
我试图通过这样的算法来解决这个任务:
让我们枚举对象之间的所有唯一距离。
对于每个唯一的距离 X，让我们基于对象作为节点和邻接矩阵构建图，如果对象 A 和 B 之间的距离恰好为 X，则 A 和 B 之间存在边
让我们在此图中找到最大团。如果此 clique 的大小大于当前最大值 - 更新最大值并将 clique 存储为结果
从对象集合中删除存储在Result中的对象
重复直到对象集不为空
有没有更有效的[近似]解决方案？
最佳答案
均值(簇大小)=总点数/簇数
最大化这一点的唯一方法是最小化集群的数量。作为优化目标，这似乎是一个相当糟糕的选择。您可能需要重新考虑这个目标。
除此之外，我认为您的算法相当明智。由于问题可能是 NP 难问题，因此您确实希望使用贪心近似。
我建议在重新计算时更加懒惰，并添加一些界限。
为每个唯一距离构建子图。
按大小降序对子图进行排序。
除非您有前一次迭代的缓存值，否则在每个子图中找到最大的团。记住最大的集团。如果当前最大的大于其余子图，则停止。
输出找到的最佳子图。
从所有图中删除包含的节点，并忘记那些包含刚刚找到的任何节点的最佳派系。回到2。
关于algorithm - 如何在具有最大平均子集大小的等距子集上拆分集？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47947178/