如何根据特定概率选择列表中的项目？

Question

假设我们得到了如下列表：

list = [[A,10,3],[B,5,2],[C,8,1]]

对于列表中的每个项目，都有一个被选中的概率，可以通过 softmax 计算。例如，对于第一个元素 (A)，我们有：

from math import exp

A_probability = exp(list[0][2]/list[0][1] /
                     (exp(list[0][2]/list[0][1]) +
                      exp(list[1][2]/list[1][1]) +
                      exp(list[2][2]/list[2][1])))

如何根据每个项目的计算概率随机选择列表中的项目？

Answer 1

我假设您有一个预先计算的概率列表（例如 probs），列表中的每个索引（例如 data）要从中选择。

此外，probs 和 data 显然必须具有相同的长度，并且 probs 的条目必须是总和为 1.[=29 的非负数=]

有一种巧妙而简单的技术可以根据 probs 中的分布随机选择 data 中的索引，这被称为 轮盘赌 .在 Python 中，我相信它应该看起来像这样

import random

data = ['A', 'B', 'C', 'D']

probs = [0.2, 0.4, 0.3, 0.1]

def roulette_wheel(probs):
    rand = random.random()
    for slot, prob in enumerate(probs):
        rand -= prob
        if rand < 0.0:
            return slot

请注意，通过将 rand 乘以项 sum(weights)，可以将其推广到非负权重列表（不必加起来等于 1） .我相信，很久以前我第一次在一本关于 Pascal 编程的书中看到这个可爱的想法。

编辑:

正如 MadPhysicist 在中建议的那样，如果需要从相同的数据中重复绘制，这可以提高效率。在这种情况下，可以预先计算累积分布函数，然后对索引进行二分搜索，使得 cumulative prob. <= rand ~ U(0, 1)。在 Python 中，这可能类似于以下内容

from random import random
from bisect import bisect_right


def cdf(probs):
    cdf = []
    total = 0.0
    for p in probs:
        total += p
        cdf.append(total)
    return cdf


def roulette_wheel_bisect(cdf):
    return bisect_right(cdf, random())

# compute cdf
cumsum = cdf(probs)

# randomly draw 10 indexes 
for i in range(0, 10):
    print(roulette_wheel_bisect(cumsum))

免责声明：我不是 Python 程序员，所以上面的代码应该只是说明了一般的想法。它在实际使用中可能不是很健壮。如果可以的话，您应该始终使用经过良好测试的标准库，例如 numpy。

编辑2:

我刚了解到 numpy 有 numpy.random.choice 可以满足您的需求。示例：

from numpy import random

data = ['A', 'B', 'C', 'D']
probs = [0.2, 0.4, 0.3, 0.1]

# randomly draw 10 list elements with replacement
for i in range(0, 10):
    print(random.choice(data, p=probs))

如何根据特定概率选择列表中的项目？

How to choose an item in a list according to a specific probability?

random

python-3.x

probability-density