对对象进行分组以实现各组的相似均值属性

5 投票

3 回答

1745 浏览

数据工程师

提问于 2025-04-16 08:38

我有一堆物品，每个物品都有一个数字的“重量”。我想把这些物品分成几个组，让每个组的物品重量平均值大致相同。

这些组的成员数量不一定要相同，但每组的大小差不多，最多相差一个。具体来说，我大约有50到100个物品，而每组最多大约有5个物品。

这个问题算不算一个常见的问题呢？感觉有点像背包问题或者分区问题。有没有什么有效的算法可以解决这个问题呢？

作为第一步，我写了一个python脚本，简单地通过按重量排序物品，然后把这些物品分成小组，再把每个小组的一个成员分配到最终的组里，从而实现了重量平均值的粗略相等。

我对python编程比较熟悉，所以如果有现成的包或者模块可以实现部分功能，我很希望能听到相关信息。

谢谢你的帮助和建议。

3 个回答

你也可以试试一种基于中心点的连接算法，它能达到同样的效果。

可以查看这个链接获取代码，以及这个链接来帮助理解。

UPGMA（也叫基于中心点的算法）可能就是你想要使用的。

回答于 2025-04-16 由 Python大师

分享举报

下面这个程序是一种低成本的启发式方法。它的工作原理是把数值分配到“桶”里，把大数值和小数值放在一起。具体做法是每轮从一个排序好的列表的一端选择数值，下一轮再从另一端选择。这样轮流分配可以确保每个桶里的元素数量符合规定。这是一种启发式方法，而不是算法，因为它通常能产生不错的结果，但并不能保证一定没有更好的结果。

理论上，如果有足够多的数值，并且这些数值分布得比较均匀，那么随机把这些数值放进桶里，可能会让每个桶的平均值相似。假设数据集比较小，这种启发式方法能提高找到好结果的机会。如果能更多地了解数据集的大小和统计分布，就能设计出更好的启发式方法或算法。

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))。

回答于 2025-04-16 由 Python大师

分享举报

你可以试试使用 k均值聚类：

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 个相互靠近的数字组。如果组与组之间的差异超过了某个设定的值，就会增加 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均值聚类算法最开始是随机选择 k 个组的中心点。这意味着每次运行同样的代码，可能会得到不同的结果，尤其是当权重没有明显分成几个不同的组时。

你还需要调整阈值参数，以便得到你想要的组数。

回答于 2025-04-16 由 Python大师

分享举报

对对象进行分组以实现各组的相似均值属性

相关问题：

3 个回答

撰写回答