概述
我有一组对象,每个对象都有一个数字’权重’.我想创建这些对象的组,使得每个组具有与对象权重大致相同的算术平均值.
这些组不一定具有相同数量的成员,但组的大小将在彼此之内.在数字方面,将有50到100个对象,最大组大小约为5.
这是一个众所周知的问题吗？这看起来有点像背包或分区问题.是否已知有效的算法可以解决它？
作为第一步,我创建了一个python脚本,通过按权重对对象进行排序,对这些对象进行分组,然后将每个子组的成员分发到最终组之一,从而实现平均权重的粗略等价.
我很乐于在python中编程,所以如果存在现有的包或模块来实现这个功能的一部分,我会很感激听到它们.
感谢您的帮助和建议.
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均值聚类算法使用随机猜测来初始选择k个组的中心.这意味着重复运行相同的代码可以产生不同的结果,特别是如果权重不将它们分成明显不同的组.
总结
以上是编程之家为你收集整理的python – 对对象进行分组以实现所有组的类似平均属性全部内容，希望文章能够帮你解决python – 对对象进行分组以实现所有组的类似平均属性所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧
602392714
清零编程群