我有有限数量的点（云），并在它们上定义了一个度量。我想在这个云中找到最大数量的集群，这样：
1) 一个簇中任意两点之间的最大距离小于给定的 epsilon ( const )
2) 每个簇中恰好有 k ( const ) 个点
我查看了各种不同的聚类方法，并且限制内部最大距离的聚类不是问题（基于密度）。2）约束和找到“最大数量的集群 st”的要求似乎是有问题的。对于有效的解决方案有什么建议吗？
谢谢阿~
问问题
220 次
2 回答
1
实际上，我和@Anony-Mousse 的印象是一样的：你还没有理解你的问题和要求。
如果您希望您的集群大小为k，那么您将获得多少个集群是毫无疑问的：显然是n /k. 因此，您可以尝试使用产生与本教程中所述相同大小的集群的 k-means 变体：Tutorial on same-size k-means并将所需的集群数设置为n/k。
请注意，这不是一个特别明智或好的聚类算法。它可以满足约束条件，但从聚类分析的角度来看，聚类并没有真正的意义。这是约束满足，但不是聚类分析。
为了也满足您的 epsilon 约束，您可以从这个初始解决方案开始（这可能是@Anony-Mousse 所说的“显而易见的方法”）并尝试执行相同类型的优化交换元素为了满足 epsilon 条件。
您可能需要多次重新启动，因为可能没有解决方案。
也可以看看：
对于本质上多余的问题。
于 2013-02-16T23:13:29.600 回答
1
鉴于您的限制，可能没有解决方案。实际上，这可能经常发生……
最明显的情况是当您没有多个k点时。
但如果epsilon设置得太低，可能会有一些点不能再放入集群中。
我认为您需要重新考虑您的要求和问题，而不是寻找一种算法来解决可能无法满足的不合理的硬要求。
还要考虑您是否真的需要找到保证的最大值，或者只是一个好的解决方案。
有一些相当明显的方法至少可以快速找到一个好的近似值。
于 2013-02-15T22:37:49.970 回答