python中的加权随机样本
我正在寻找函数weighted_sample的合理定义，它不会只为给定的权重列表返回一个随机索引(可能是这样的
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相比一样。
就像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)但我想要一个不需要我将权重分解成一个(可能很大的)列表的解决方案。
编辑:如果有任何很好的算法可以给我返回一个直方图/频率列表(格式与参数weights相同)，而不是一系列索引，那也是非常有用的。
回答 6
Stack Overflow用户
发布于 2012-10-24 23:11:13
从你的代码中：..
weight_sample_indexes = lambda weights, k: random.sample([val
for val, cnt in enumerate(weights) for i in range(cnt)], k)。。我假设权重是正整数，您所说的“无替换”是指未分解序列的无替换。
这是一个基于random.sample和O(log ) __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: 1Stack Overflow用户
发布于 2012-10-25 23:29:54
您想要创建的是一个非均匀随机分布。这样做的一个不好的方法是创建一个巨大的数组，其中包含与权重成比例的输出符号。因此，如果a的概率是b的5倍，那么你创建的数组就是a比b的5倍，这对于权重甚至是彼此的倍数的简单分布很有效。如果你想要99.99%a和.01% b，你必须创建10000个插槽。
有一个更好的方法。所有具有N个符号的非均匀分布都可以分解为一系列n-1个二进制分布，每个分布的概率相等。
因此，如果你有这样的分解，你首先要随机选择一个二进制分布，从1- N-1生成一个均匀的随机数
u32 dist = randInRange( 1, N-1 ); // generate a random number from 1 to N;然后假设选择的分布是具有两个符号a和b的二进制分布，a的概率为0-alpha，b的概率为α-1：
float f = randomFloat();
return ( f > alpha ) ? b : a;如何分解任何不均匀的随机分布要稍微复杂一些。本质上，您创建了N-1个“存储桶”。选择概率最低和概率最高的符号，并将它们的权重按比例分配到第一二进制分布中。然后删除最小的符号，并删除用于创建此二进制分布的较大的符号的权重量。重复这个过程，直到你没有剩下的符号。
如果你想使用这个解决方案，我可以发布c++代码。
Stack Overflow用户
发布于 2012-10-24 21:37:57
如果为random.sample()操作构造了正确的数据结构，则根本不需要定义新函数。只需使用random.sample()即可。
这里，__getitem__()是O(n)，其中n是具有权重的不同项目的数量。但是它在内存中是紧凑的，只需要存储(weight, value)对。我在实践中使用了一个类似的类，它对于我的目的来说已经足够快了。请注意，此实现采用整数权重。
class SparseDistribution(object):
_cached_length = None
def __init__(self, weighted_items):
# weighted items are (weight, value) pairs
self._weighted_items = []
for item in weighted_items:
self.append(item)
def append(self, weighted_item):
self._weighted_items.append(weighted_item)
self.__dict__.pop("_cached_length", None)
def __len__(self):
if self._cached_length is None:
length = 0
for w, v in self._weighted_items:
length += w
self._cached_length = length
return self._cached_length
def __getitem__(self, index):
if index < 0 or index >= len(self):
raise IndexError(index)
for w, v in self._weighted_items:
if index < w:
return v
raise Exception("Shouldn't have happened")
def __iter__(self):
for w, v in self._weighted_items:
for _ in xrange(w):
yield v然后，我们可以使用它：
import random
d = SparseDistribution([(5, "a"), (2, "b")])
d.append((3, "c"))
for num in (3, 5, 10, 11):
try:
print random.sample(d, num)
except Exception as e:
print "{}({!r})".format(type(e).__name__, str(e))结果是：
['a', 'a', 'b']
['b', 'a', 'c', 'a', 'b']
['a', 'c', 'a', 'c', 'a', 'b', 'a', 'a', 'b', 'c']
ValueError('sample larger than population')https://stackoverflow.com/questions/13047806
复制相似问题