对象划分集

Question

我正在尝试将一组100个对象划分为两个子集。每个对象都有一组数字属性。

当前的目标函数是最小化每个集合属性之间的平均值的平均值。换句话说，我们首先计算每个集合中每个属性的平均值，然后取集合之间每个属性的差异，最后取这些差异的平均值。

注意，这个目标函数是使用过的几个函数之一(也是最简单的)；我需要一个通用的解决方案，不管目标函数是如何计算的。

我想出的解决方案非常基本：

• 使用贪婪算法迭代地向其中一个子集添加一个新对象
• 与上述相同，但允许在每次新分配后重新平衡子集。
• 从完全种子集开始(基于随机分配)，然后进行贪婪的搜索，将一个对象从一个集合移动到另一个集合，如果它降低了目标函数的话。

是否有比这些更精确的方法；也就是说，这将导致更紧密匹配的集合，但不需要特别长的时间来评估？

Answer 1

我不确定是否有更好的答案。你可以从k方法开始，这至少是你的第二种方法的系统版本，或者遗传优化是你的第三种方法的更系统的版本。在任何情况下，看看一些分类算法，看看什么适合你的情况。

如果您想证明什么，那么最终，属性的维度可能是关键：

如果您只有一个数字属性，则解决方案非常简单。如果您有许多属性和足够一致的分布，那么分区可能是“好的”。试着将超级立方体分成两半，使用你的度量来获得感觉。

在其他情况下，通过将点投影到一维上，可以得到一个几何解，尽可能地保持距离。其中一种方法是多维缩放(MDS)。

Answer 2

如果我正确理解你的目标函数，似乎你可以直接计算每个对象的成本。对数据进行一次传递，以计算每个属性的平均值。

然后是cost(obj) := sum( [ obj.attr[i]-mean[i] for i in len(obj.attr) ])

这减少了分割问题的问题，这是一个很好的研究。

您可能需要将每个值规范化为观察范围的百分之一，以防止大范围属性支配决策。该范围可以在相同的通径与平均值。