我试图将一组100个对象分成两个子集。每个对象都有一组数字属性。
当前目标函数是最小化每组属性的平均值之间的差异的平均值。换句话说,我们首先计算每组中每个属性的平均值,然后取各组之间每个属性的差值,最后取这些差异的平均值。
注意,这个目标函数是使用过的几个中的一个(并且是最简单的);无论客观函数如何计算,我都需要一个通用的解决方案。
我提出的解决方案相当简陋:
有没有比这些更准确的方法;即,这将导致更紧密匹配的集合,但不需要特别长的时间来评估?
我不确定答案是否可以证明更好。您可以从k-means开始,这至少是您的第二种方法的系统版本,或遗传优化作为您的第三种方法的更系统化的版本。无论如何,请查看一些分类算法,看看哪种情况适合您的情况。
如果你想证明什么,那么最后,你的属性的维度可能是关键:
如果您只有一个数字属性,那么解决方案很简单。如果你有很多属性和足够均匀的分布,那么分区就不会“好”。尝试使用您的指标将超立方体分成两半以获得感觉。
在其他情况下,通过将点投影到一个维度上可能存在几何解决方案,尽可能保持距离。这样做的一种方法是多维缩放(MDS)。
如果我正确理解你的目标函数,似乎你可以直接计算每个对象的成本。对数据进行一次传递以计算每个属性的平均值。
然后cost(obj) := sum( [ obj.attr[i]-mean[i] for i in len(obj.attr) ])
这减少了Partition Problem的问题,这是一个很好的研究。
您可能需要将每个值标准化为观察范围的百分比,以防止大范围属性支配决策。该范围可以在与平均值相同的过程中找到。