python中的加权随机样本 [英] Weighted random sample in python
问题描述
我正在寻找函数 weighted_sample
的合理定义,该函数不只返回给定权重列表的一个随机索引(类似于
I'm looking for a reasonable definition of a function weighted_sample
that does not return just one random index for a list of given weights (which would be something like
def weighted_choice(weights, random=random):
""" Given a list of weights [w_0, w_1, ..., w_n-1],
return an index i in range(n) with probability proportional to w_i. """
rnd = random.random() * sum(weights)
for i, w in enumerate(weights):
if w<0:
raise ValueError("Negative weight encountered.")
rnd -= w
if rnd < 0:
return i
raise ValueError("Sum of weights is not positive")
给出一个具有恒定权重的分类分布)但是一个 k
的随机样本,无替换,就像 random.sample
与 random.choice
相比的行为.
to give a categorical distribution with constant weights) but a random sample of k
of those, without replacement, just as random.sample
behaves compared to random.choice
.
正如 weighted_choice
可以写成
lambda weights: random.choice([val for val, cnt in enumerate(weights)
for i in range(cnt)])
weighted_sample
可以写成
lambda weights, k: random.sample([val for val, cnt in enumerate(weights)
for i in range(cnt)], k)
但我想要一个不需要我将权重分解为(可能很大)列表的解决方案.
but I would like a solution that does not require me to unravel the weights into a (possibly huge) list.
如果有任何不错的算法可以给我一个直方图/频率列表(与参数 weights
格式相同)而不是一个索引序列,那也非常好有用.
If there are any nice algorithms that give me back a histogram/list of frequencies (in the same format as the argument weights
) instead of a sequence of indices, that would also be very useful.
推荐答案
来自您的代码:..
weight_sample_indexes = lambda weights, k: random.sample([val
for val, cnt in enumerate(weights) for i in range(cnt)], k)
.. 我假设权重是正整数,没有替换"是指没有替换解开的序列.
.. I assume that weights are positive integers and by "without replacement" you mean without replacement for the unraveled sequence.
这是一个基于 random.sample 和 O(log n) __getitem__
的解决方案:
Here's a solution based on random.sample and O(log n) __getitem__
:
import bisect
import random
from collections import Counter, Sequence
def weighted_sample(population, weights, k):
return random.sample(WeightedPopulation(population, weights), k)
class WeightedPopulation(Sequence):
def __init__(self, population, weights):
assert len(population) == len(weights) > 0
self.population = population
self.cumweights = []
cumsum = 0 # compute cumulative weight
for w in weights:
cumsum += w
self.cumweights.append(cumsum)
def __len__(self):
return self.cumweights[-1]
def __getitem__(self, i):
if not 0 <= i < len(self):
raise IndexError(i)
return self.population[bisect.bisect(self.cumweights, i)]
示例
total = Counter()
for _ in range(1000):
sample = weighted_sample("abc", [1,10,2], 5)
total.update(sample)
print(sample)
print("Frequences %s" % (dict(Counter(sample)),))
# Check that values are sane
print("Total " + ', '.join("%s: %.0f" % (val, count * 1.0 / min(total.values()))
for val, count in total.most_common()))
输出
['b', 'b', 'b', 'c', 'c']
Frequences {'c': 2, 'b': 3}
Total b: 10, c: 2, a: 1
这篇关于python中的加权随机样本的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!