对无关对象进行分组的算法

Question

我有一组对象。每个物体都放在“空间”中，我知道每个物体之间的距离。我正在寻找一种算法，用于对彼此远离的对象进行分组。我选择组数。组应该是“平衡的”(每个组应该包含相同数量的项目)。

示例:

假设我有 4 个对象

{ A, B, C, D }

我在二维空间中表示它们:

我知道每个物体之间的距离所以

{
    AB = 1
    AC = 3.6
    AD = 5
    BC = 2.8
    BD = 4.2
    and so on...
}

我希望算法将对象分为两组，它应该输出

{[ A, C ][ B, D ]}

当然这对于 4 个对象来说很容易，但是对于更多的对象就很难了。

我搜索了很多，但我找不到这样的分组的任何内容。我已经阅读了很多关于 k 均值聚类和其他聚类方法的文章，但它们并不适用，因为它们将相似的对象分组。

什么是最好的解决方案？

编辑

问题的形式化可能是最大化每个组中元素之间的距离。所以这就是算法应该将 A 和 C、B 和 D 分组的原因。

A 和 D，B 和 C 这不是一个好的解决方案。

算法应该处理N个项目(N > 2)和K个组(K < N，我选择多少组)

Answer 1

您可能会在这里滥用聚类算法，在它们期望相似时给它们一个距离，或者反过来。

看看层次聚类，按照你想要的方式“打破”它应该很容易。

但更有可能的是，除了此类玩具场景之外，结果在任何情况下都不会很有说服力，因为“差异”不是传递性的。

通常，当A与B相似，B与C相似时，你会希望A、B、C在同一个簇中。

但是当A和B不相似，B和C不相似，那么A和C可能很相似；所以你不希望它们聚类……不过，“也许”完整的链式聚类(如上讨论的滥用时)对你有用。