algorithm - 最小尺寸的组中项目的最佳分组/聚类

Question

我正在寻找解决以下问题的算法:

• 给定:一组项目及其相似度矩阵。
• 目标:将这些项目分组为最小大小 m
的“集群”
• 条件:
  • 数据集中没有类簇结构，如图 Figure 1
  • 无论如何，一组中的项目应该彼此相似。因此，全局相似度会很高。

这样做的动机不是识别好的集群，而是将数据集拆分为相似度高且大小最小的组。围绕中心点进行分区并不是开箱即用的，它会产生很多 1-item-clusters。分层方法(AGNES、DIANA)也无济于事。

这个问题在某种程度上类似于稳定婚姻问题:一个人试图根据相似性对相邻项目进行排名。但是在这里，一组/一段婚姻中至少有 m 项。

提前致谢!

Answer 1

这不是聚类。聚类算法应该告诉您那里没有聚类。你的任务听起来更像是装箱，knapsack以及对我来说类似的优化问题。

没有任何进一步的限制，您的问题也未指定。

您为什么不尝试贪心启发法(这通常用于解决类似背包的问题)。随机选择任意点，添加足够的点以满足最小尺寸限制。

然后选择距此最远的点，并再次添加足够的点以满足您的最小尺寸。重复(使用距离之和进行排名)，直到您不再满足最小尺寸。然后将每个剩余点添加到最近的每个簇中。最后，只要满足最小大小，优化是否将移动点传递给其他集群？