algorithm - 如何在具有最大平均子集大小的等距子集上拆分集？

Question

我有一组 N 个对象，它们之间有 N * N 个距离。我想将这个集合聚类到子集上，这样在每个聚类中，所有对象都具有相同的距离，并且所有聚类上的均值(cluster_size)最大化。

我试图通过这样的算法来解决这个任务:

1. 让我们枚举对象之间的所有唯一距离。

2. 对于每个唯一的距离 X，让我们基于对象作为节点和邻接矩阵构建图，如果对象 A 和 B 之间的距离恰好为 X，则 A 和 B 之间存在边

3. 让我们在此图中找到最大团。如果此 clique 的大小大于当前最大值 - 更新最大值并将 clique 存储为结果

4. 从对象集合中删除存储在Result中的对象

5. 重复直到对象集不为空

有没有更有效的[近似]解决方案？

Answer 1

均值(簇大小)=总点数/簇数

最大化这一点的唯一方法是最小化集群的数量。作为优化目标，这似乎是一个相当糟糕的选择。您可能需要重新考虑这个目标。

除此之外，我认为您的算法相当明智。由于问题可能是 NP 难问题，因此您确实希望使用贪心近似。

我建议在重新计算时更加懒惰，并添加一些界限。

1. 为每个唯一距离构建子图。

2. 按大小降序对子图进行排序。

3. 除非您有前一次迭代的缓存值，否则在每个子图中找到最大的团。记住最大的集团。如果当前最大的大于其余子图，则停止。

4. 输出找到的最佳子图。

5. 从所有图中删除包含的节点，并忘记那些包含刚刚找到的任何节点的最佳派系。回到2。