5

我有一组对象，每个对象都有一个数字“权重”。我想创建这些对象的组，使每个组的对象权重的算术平均值大致相同。

这些组不一定有相同数量的成员，但组的大小将在彼此之内。就数量而言，将有 50 到 100 个对象，最大组大小约为 5。

这是一个众所周知的问题吗？这似乎有点像背包或分区问题。已知有效的算法可以解决它吗？

作为第一步，我创建了一个 Python 脚本，该脚本通过按重量对对象进行排序、对这些对象进行分组，然后将每个子组的成员分配到最终组中的一个，来实现非常粗略的平均重量等价。

我很喜欢用 python 编程，所以如果存在现有的包或模块来实现部分功能，我会很高兴听到它们。

感谢您的帮助和建议。

4

3 回答 3

2

下面的程序是一个低成本的启发式程序。它所做的是将值分布在“桶”中，通过在一轮中从排序列表的一端选择值，在下一轮从另一端选择值，将大值与小值一起放置。以循环方式进行分配可确保满足有关每个桶的元素数量的规则。它是一种启发式而不是算法，因为它往往会产生好的解决方案，但不能保证不存在更好的解决方案。

理论上，如果有足够的值，并且它们是均匀分布或正态分布的，那么将值随机放置在桶中可能会导致桶的均值相同。假设数据集很小，这种启发式方法提高了一个好的解决方案的机会。更多地了解数据集的大小和统计分布将有助于设计更好的启发式或算法。

from random import randint, seed
from itertools import cycle,chain

def chunks(q, n):
    q = list(q)
    for i in range(0, len(q), n):
       yield q[i:i+n]

def shuffle(q, n):
    q = list(q)
    m = len(q)//2
    left =  list(chunks(q[:m],n))
    right = list(chunks(reversed(q[m:]),n)) + [[]]
    return chain(*(a+b for a,b in zip(left, right)))

def listarray(n):
    return [list() for _ in range(n)]

def mean(q):
    return sum(q)/len(q)

def report(q):
    for x in q:
        print mean(x), len(x), x

SIZE = 5
COUNT= 37

#seed(SIZE)
data = [randint(1,1000) for _ in range(COUNT)]
data = sorted(data)
NBUCKETS = (COUNT+SIZE-1) // SIZE

order = shuffle(range(COUNT), NBUCKETS)
posts = cycle(range(NBUCKETS))
buckets = listarray(NBUCKETS)
for o in order:
    i = posts.next()
    buckets[i].append(data[o])
report(buckets)
print mean(data)

由于排序步骤，复杂性是对数的。这些是样本结果：

439 5 [15, 988, 238, 624, 332]
447 5 [58, 961, 269, 616, 335]
467 5 [60, 894, 276, 613, 495]
442 5 [83, 857, 278, 570, 425]
422 5 [95, 821, 287, 560, 347]
442 4 [133, 802, 294, 542]
440 4 [170, 766, 301, 524]
418 4 [184, 652, 326, 512]
440

请注意，对桶大小的要求占主导地位，这意味着如果原始数据中的方差很大，则均值不会接近。您可以尝试使用此数据集：

data = sorted(data) + [100000]

包含的桶100000将至少获得另外 3 个基准。

我想出了这个启发式的想法，如果一群孩子递给一包不同面额的钞票，并告诉他们按照这个游戏的规则分享它们，这就是他们会做的事情。它在统计上是合理的，并且 O(log(N))。

于 2010-12-30T15:50:26.973 回答
1

您可以尝试使用k-means 聚类：

import scipy.cluster.vq as vq
import collections
import numpy as np

def auto_cluster(data,threshold=0.1,k=1):
    # There are more sophisticated ways of determining k
    # See http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set
    data=np.asarray(data)
    distortion=1e20
    while distortion>threshold:
        codebook,distortion=vq.kmeans(data,k)
        k+=1   
    code,dist=vq.vq(data,codebook)    
    groups=collections.defaultdict(list)
    for index,datum in zip(code,data):
        groups[index].append(datum)
    return groups

np.random.seed(784789)
N=20
weights=100*np.random.random(N)
groups=auto_cluster(weights,threshold=1.5,k=N//5)
for index,data in enumerate(sorted(groups.values(),key=lambda d: np.mean(d))):
    print('{i}: {d}'.format(i=index,d=data))

上面的代码生成一个包含 N 个权重的随机序列。它使用scipy.cluster.vq.kmeans将序列划分k为靠近在一起的数字簇。如果失真高于阈值，则重新计算 kmeans 并k增加。重复此过程，直到失真低于给定阈值。

它产生这样的集群：

0: [4.9062151907551366]
1: [13.545565038022112, 12.283828883935065]
2: [17.395300245930066]
3: [28.982058040201832, 30.032607500871023, 31.484125759701588]
4: [35.449637591061979]
5: [43.239840915978043, 48.079844689518424, 40.216494950261506]
6: [52.123246083619755, 53.895726546070463]
7: [80.556052179748079, 80.925071671718413, 75.211470587171803]
8: [86.443868931310249, 82.474064251040375, 84.088655128258964]
9: [93.525705849369416]

请注意，k-means 聚类算法使用随机猜测来最初选择k组的中心。这意味着重复运行相同的代码会产生不同的结果，特别是如果权重没有将它们自己分成明显不同的组。

您还必须调整阈值参数以生成所需数量的组。

于 2010-12-16T16:53:09.093 回答
1

您也可以尝试基于质心的链接算法，它可以实现相同的效果。

有关代码，请参阅this ，并了解this。

UPGMA（又名基于质心）是您可能想要做的。

于 2010-12-16T16:59:55.270 回答