Pythonic方式选择具有不同概率的列表元素

Question

import random
pos = ["A", "B", "C"]
x = random.choice["A", "B", "C"]

这段代码给了我"A","B"或"C"的概率相等.当你想要30%的"A",40%的"B"和30%概率的"C"时,是否有一种很好的表达方式？

Answer 1

权重定义概率分布函数(pdf).来自任何这种pdf的随机数可以通过将其相关的逆累积分布函数应用于0和1之间的均匀随机数来生成.

另请参阅此SO解释,或者,如维基百科所解释的:

如果Y具有U [0,1]分布,则F？1(Y)被分配为F.这用于使用逆变换采样方法的随机数生成.

import random
import bisect
import collections

def cdf(weights):
    total = sum(weights)
    result = []
    cumsum = 0
    for w in weights:
        cumsum += w
        result.append(cumsum / total)
    return result

def choice(population, weights):
    assert len(population) == len(weights)
    cdf_vals = cdf(weights)
    x = random.random()
    idx = bisect.bisect(cdf_vals, x)
    return population[idx]

weights=[0.3, 0.4, 0.3]
population = 'ABC'
counts = collections.defaultdict(int)
for i in range(10000):
    counts[choice(population, weights)] += 1
print(counts)

# % test.py
# defaultdict(<type 'int'>, {'A': 3066, 'C': 2964, 'B': 3970})

choice上面的函数使用bisect.bisect,因此加权随机变量的选择在O(log n)其中n的长度为weights.

请注意,从版本1.7.0开始,NumPy具有Cythonized np.random.choice函数.例如,这会从人口中生成1000个样本,其[0,1,2,3]权重为[0.1, 0.2, 0.3, 0.4]:

import numpy as np
np.random.choice(4, 1000, p=[0.1, 0.2, 0.3, 0.4])

np.random.choice还有一个replace带或不带替换的采样参数.

理论上更好的算法是Alias方法.它构建了一个需要O(n)时间的表格,但在此之后,可以及时绘制样本O(1).因此,如果您需要绘制许多样本,理论上Alias方法可能会更快.这里有一个Walker Alias方法的Python实现,这里有一个numpy版本.

Answer 2

没那么多...

pos = ['A'] * 3 + ['B'] * 4 + ['C'] * 3
print random.choice(pos)

要么

pos = {'A': 3, 'B': 4, 'C': 3}
print random.choice([x for x in pos for y in range(pos[x])])

Answer 3

这是一个暴露一堆具有相对概率的项目的类,而不实际扩展列表:

import bisect
class WeightedTuple(object):
    """
    >>> p = WeightedTuple({'A': 2, 'B': 1, 'C': 3})
    >>> len(p)
    6
    >>> p[0], p[1], p[2], p[3], p[4], p[5]
    ('A', 'A', 'B', 'C', 'C', 'C')
    >>> p[-1], p[-2], p[-3], p[-4], p[-5], p[-6]
    ('C', 'C', 'C', 'B', 'A', 'A')
    >>> p[6]
    Traceback (most recent call last):
    ...
    IndexError
    >>> p[-7]
    Traceback (most recent call last):
    ...
    IndexError
    """
    def __init__(self, items):
        self.indexes = []
        self.items = []
        next_index = 0
        for key in sorted(items.keys()):
            val = items[key]
            self.indexes.append(next_index)
            self.items.append(key)
            next_index += val

        self.len = next_index

    def __getitem__(self, n):
        if n < 0:
            n = self.len + n
        if n < 0 or n >= self.len:
            raise IndexError

        idx = bisect.bisect_right(self.indexes, n)
        return self.items[idx-1]

    def __len__(self):
        return self.len

现在,只说:

data = WeightedTuple({'A': 30, 'B': 40, 'C': 30})
random.choice(data)

Answer 4

您也可以使用此表单,它不会创建任意大的列表(并且可以使用整数或十进制概率):

pos = [("A", 30), ("B", 40), ("C", 30)]


from random import uniform
def w_choice(seq):
    total_prob = sum(item[1] for item in seq)
    chosen = random.uniform(0, total_prob)
    cumulative = 0
    for item, probality in seq:
        cumulative += probality
        if cumulative > chosen:
            return item

Answer 5

这里提供了一些很好的解决方案,但我建议你看一下Eli Bendersky对这个问题的深入讨论,它在选择之前比较了各种算法(用Python实现).