我正在寻找解决以下问题的算法:
- 给定:一组项目及其相似度矩阵。
- 目标:将这些项目分组为最小大小 m 的“集群”
- 条件:
- 数据集中没有类簇结构，如图 Figure 1
- 无论如何，一组中的项目应该彼此相似。因此，全局相似度会很高。
这样做的动机不是识别好的集群，而是将数据集拆分为相似度高且大小最小的组。围绕中心点进行分区并不是开箱即用的，它会产生很多 1-item-clusters。分层方法(AGNES、DIANA)也无济于事。
这个问题在某种程度上类似于稳定婚姻问题:一个人试图根据相似性对相邻项目进行排名。但是在这里，一组/一段婚姻中至少有 m 项。
提前致谢!
最佳答案
这不是聚类。聚类算法应该告诉您那里没有聚类。你的任务听起来更像是装箱，knapsack以及对我来说类似的优化问题。
没有任何进一步的限制，您的问题也未指定。
您为什么不尝试贪心启发法(这通常用于解决类似背包的问题)。随机选择任意点，添加足够的点以满足最小尺寸限制。
然后选择距此最远的点，并再次添加足够的点以满足您的最小尺寸。重复(使用距离之和进行排名)，直到您不再满足最小尺寸。然后将每个剩余点添加到最近的每个簇中。最后，只要满足最小大小，优化是否将移动点传递给其他集群？
关于algorithm - 最小尺寸的组中项目的最佳分组/聚类，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37589168/