在Python中高效地从多重集合（计数器）中抽样

Question

让人烦恼的是，下面的代码不起作用：

from collections import Counter
import random

c = Counter([1,1,1,1,0,0])
random.choice(c) # I expect this to return 1 with probability 2/3, 
                 # and 0 with probability 1/3.
                 # It actually returns 4 or 2, with probability 1/2

在Python中（任何版本），从一个多重集合中抽样的标准方法是什么？

编辑 是的，我确实需要使用多重集合。我的实际数据要大得多，单纯把它放在一个列表里是不现实的。

编辑 2 我需要以合理的效率来完成这个，因为我的代码会反复执行这个操作。Counter对象中会存储很多数据，任何涉及将所有这些数据复制到新数据结构中的方法都不是一个可行的解决方案。

Answer 1

在所有现代的Python版本中，你可以使用 random.choices() 这个功能，它可以从一个集合中随机选择一个或多个选项，并且这些选项可以有不同的权重。

这个例子直接来自于 Python文档中的示例：

>>> # Six roulette wheel spins (weighted sampling with replacement)
>>> choices(['red', 'black', 'green'], [18, 18, 2], k=6)
['red', 'green', 'black', 'black', 'red', 'black']

这里展示了一种方法，应用于一个计数器（多重集合），用来随机选择十个带权重的选项：

>>> from collections import Counter
>>> from random import choices
>>> c = Counter([1,1,1,1,0,0])
>>> choices(population=list(c), weights=c.values(), k=10)
[1, 0, 0, 1, 0, 1, 0, 1, 1, 1]

Answer 2

我也遇到了类似的问题，不过我用的计数器（Counter）是会不断变化的，而且计数器里的元素通常不多（最多100个）。

最后我找到了一种更有效的解决办法，使用了下面的代码：

c = Counter([1,1,1,1,0,0])
random.choice(list(c.elements()))

Answer 3

因为这个问题最近引起了一些关注，所以我想分享一下我的看法。在Python中高效地解决这个问题似乎需要自己写一些代码，不过我找到了一种算法，它在一个机器学习博客上有介绍，即使数据集的内容不断变化，这种算法也能高效运行，而且实现起来相对简单。这个博客文章里有一个基本的Python实现，同时还提供了一个快速的Cython实现的链接。

Answer 4

来自文档的内容：

一个常见的任务是使用加权概率来进行随机选择。

如果权重是小的整数比例，可以用一个简单的方法来创建一个包含重复项的样本集合：

>>> weighted_choices = [('Red', 3), ('Blue', 2), ('Yellow', 1), ('Green', 4)]
>>> population = [val for val, cnt in weighted_choices for i in range(cnt)]
>>> random.choice(population)
'Green'

另一种更通用的方法是使用itertools.accumulate()将权重整理成一个累积分布，然后用bisect.bisect()找到随机值：

>>> choices, weights = zip(*weighted_choices)
>>> cumdist = list(itertools.accumulate(weights))
>>> x = random.random() * cumdist[-1]
>>> choices[bisect.bisect(cumdist, x)]
'Blue'

对于你的应用，可能需要使用Counter来构建一个选择列表和一个累积概率列表，然后使用第二种方法进行抽样。

Answer 5

你可以使用 Python 3.6 及以上版本自带的 random.choices 来实现这个功能。

from collections import Counter
import random

c = Counter([1,1,1,1,0,0])
random.choices(list(c.keys()), weights=list(c.values()), k=1)

注意: 在 Python 3.7 及以上版本中，字典的键的顺序是有保证的，所以示例代码可以在 Python 3.7 及以上版本中运行。不过在 Python 3.6 中也可以找到类似的解决方案。