如何根据加权概率从python字典中选择键？

Question

我有一个Python字典,其中键表示一些项目,值表示所述项目的一些(标准化)加权.例如:

d = {'a': 0.0625, 'c': 0.625, 'b': 0.3125}
# Note that sum([v for k,v in d.iteritems()]) == 1 for all `d`

鉴于项目与权重的这种相关性,我如何选择一个关键字,d结果为'a'的时间为6.25%,结果为'b'的时间为32.25%,结果的62.5%为'c' "？

Answer 1

def weighted_random_by_dct(dct):
    rand_val = random.random()
    total = 0
    for k, v in dct.items():
        total += v
        if rand_val <= total:
            return k
    assert False, 'unreachable'

应该做的伎俩.遍历每个键并保持运行总和,如果随机值(介于0和1之间)落入插槽,则返回该键

Answer 2

如果您打算经常这样做，您可以numpy使用np.random.choice(). 下面的示例将使用加权概率选择您的密钥 10,000 次。

import numpy as np

probs = [0.0625, 0.625, 0.3125]
keys = ['a', 'c', 'b']

choice_list = np.random.choice(keys, 10000, replace=True, p=probs)

Answer 3

从 Python 3.6 开始，您可以使用内置函数random.choices()而不必使用 Numpy。

那么，如果我们想从你的字典中采样（替换）25 个键，其中值是被采样的权重/概率，我们可以简单地写：

import random
random.choices(list(my_dict.keys()), weights=my_dict.values(), k=25)

这将输出采样键的列表：

['c', 'b', 'c', 'b', 'b', 'c', 'c', 'c', 'b', 'c', 'b', 'c', 'b', 'c', 'c', 'c', 'c', 'c', 'a', 'b']

如果您只需要一个键，请设置k为 1 并从random.choices返回的列表中提取单个元素：

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

（如果你不转换my_dict.keys()为列表，你会得到一个关于它是如何不可下标的类型错误。）

这是文档中的相关片段：

random.choices（人口，权重=无，*，cum_weights=无，k=1）

返回从具有替换的总体中选择的 ak 大小的元素列表。如果人口为空，则引发 IndexError。

如果指定了权重序列，则根据相对权重进行选择。或者，如果给出了 cum_weights 序列，则根据累积权重进行选择（可能使用 itertools.accumulate() 计算）。例如，相对权重 [10, 5, 30, 5] 等价于累积权重 [10, 15, 45, 50]。在内部，相对权重在进行选择之前转换为累积权重，因此提供累积权重可以节省工作。

如果权重和 cum_weights 均未指定，则以相同的概率进行选择。如果提供了权重序列，则它必须与总体序列长度相同。指定权重和 cum_weights 是一个类型错误。

weights 或 cum_weights 可以使用与 random() 返回的浮点值互操作的任何数字类型（包括整数、浮点数和分数，但不包括小数）。权重被假定为非负数。

对于给定的种子，具有相同权重的choices() 函数通常会产生与重复调用choice() 不同的序列。Choices() 使用的算法使用浮点算法来实现内部一致性和速度。choice() 使用的算法默认为具有重复选择的整数算术，以避免舍入误差造成的小偏差。

据当时的评论/sf/answers/2798387371/，random.choices是更快小数组，并numpy.random.choice为大数组更快。numpy.random.choice还提供了一个无需替换的采样选项，而没有内置的 Python 标准库函数。