分区对象集

问题描述 投票:0回答:2

我试图将一组100个对象分成两个子集。每个对象都有一组数字属性。

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

注意,这个目标函数是使用过的几个中的一个(并且是最简单的);无论客观函数如何计算,我都需要一个通用的解决方案。

我提出的解决方案相当简陋:

  • 使用贪婪算法迭代地将新对象添加到其中一个子集
  • 与上面相同,但允许回溯以在每次新分配后重新平衡子集
  • 从完全种子集(基于随机分配)开始,然后进行贪婪搜索,以便在将对象降低目标函数时将对象从一个集移动到另一个集。

有没有比这些更准确的方法;即,这将导致更紧密匹配的集合,但不需要特别长的时间来评估?

algorithm optimization partitioning bin-packing
2个回答
0
投票

我不确定答案是否可以证明更好。您可以从k-means开始,这至少是您的第二种方法的系统版本,或遗传优化作为您的第三种方法的更系统化的版本。无论如何,请查看一些分类算法,看看哪种情况适合您的情况。

如果你想证明什么,那么最后,你的属性的维度可能是关键:

如果您只有一个数字属性,那么解决方案很简单。如果你有很多属性和足够均匀的分布,那么分区就不会“好”。尝试使用您的指标将超立方体分成两半以获得感觉。

在其他情况下,通过将点投影到一个维度上可能存在几何解决方案,尽可能保持距离。这样做的一种方法是多维缩放(MDS)。


0
投票

如果我正确理解你的目标函数,似乎你可以直接计算每个对象的成本。对数据进行一次传递以计算每个属性的平均值。 然后cost(obj) := sum( [ obj.attr[i]-mean[i] for i in len(obj.attr) ])

这减少了Partition Problem的问题,这是一个很好的研究。

您可能需要将每个值标准化为观察范围的百分比,以防止大范围属性支配决策。该范围可以在与平均值相同的过程中找到。

© www.soinside.com 2019 - 2024. All rights reserved.