首页 文章

对具有最小尺寸的组中的项目进行最佳分组/聚类

提问于
浏览 次
0

我正在寻找一种解决以下问题的算法：

  • 给定：一组项目及其相似度矩阵 .

  • 目标：将这些项目分组为最小尺寸m的"clusters"

  • 条件：

  • 数据集中没有类似集群的结构，如Figure 1所示

  • 无论如何，组中的项目应该彼此相似 . 因此，全球相似性将很高 .

动机不是识别好的聚类，而是将数据集分成高相似性和最小尺寸的组 . 在medoids周围进行分区并不是开箱即用的，它会产生很多1项集群 . 分层方法（AGNES，DIANA）也没有帮助 .

这个问题在某种程度上类似于稳定的婚姻问题：一个人试图通过相似性对相邻的项目进行排名 . 但在这里，一组/一组婚姻中至少有m项 .

提前致谢！

Figure 1.

algorithm cluster-analysis stable-marriage

2 回答

  • 1

    这不是聚类 . 聚类算法应该告诉您那里没有聚类 . 您的任务听起来更像是bin pack，knapsack以及类似的优化问题 .

    没有任何进一步的限制，您的问题也未明确 .

    你为什么不尝试一种贪婪的启发式方法（这种问题通常用于背包） . 随机选择任意点，添加足够的点以满足最小尺寸约束 .

    然后从中选择最远点，再添加足够的点以满足最小尺寸 . 重复（使用距离总和进行排名），直到您不再能够满足最小尺寸 . 然后将每个剩余点添加到最近的簇中 . 最后，只要满足最小尺寸，优化是否将移动点移动到其他群集？

    回复于
  • 0

    虽然这不是典型的群集任务（请参阅@ Anony-Mousse），但您可以 modify a clustering algorithm 以满足您的需求 .

    你可以按照这个Tutorial for Same-Size K-Means，或者只是在ELKI的 tutorial 包/模块中使用这个算法（从GitHub构建最新版本，因为我刚修复了一个bug） .

    本质上，此算法执行k均值样式最小二乘优化，但所有群集必须具有相同的大小（如果N / k不是整数，则群集大小可能会变化1） .

    如果您转到上面的教程并滚动到底部，您可以看到示例结果 .

    回复于

相关问题