我需要写一个加权版的random。选择(列表中的每个元素有不同的被选择的概率)。这是我想到的:

def weightedChoice(choices):
    """Like random.choice, but each element can have a different chance of
    being selected.

    choices can be any iterable containing iterables with two items each.
    Technically, they can have more than two items, the rest will just be
    ignored.  The first item is the thing being chosen, the second item is
    its weight.  The weights can be any numeric values, what matters is the
    relative differences between them.
    """
    space = {}
    current = 0
    for choice, weight in choices:
        if weight > 0:
            space[current] = choice
            current += weight
    rand = random.uniform(0, current)
    for key in sorted(space.keys() + [current]):
        if rand < key:
            return choice
        choice = space[key]
    return None

这个函数对我来说太复杂了,而且很丑。我希望这里的每个人都能提供一些改进的建议或其他方法。对我来说,效率没有代码的整洁和可读性重要。


当前回答

从Python v3.6开始,是随机的。选项可用于从给定的填充中返回具有可选权重的指定大小的元素列表。

随机的。select (population, weights=None, *, cum_weights=None, k=1)

总体:包含独特观测值的列表。(如果为空,则引发IndexError) 权重:进行选择所需的更精确的相对权重。 Cum_weights:进行选择所需的累积权重。 K:要输出列表的大小(len)。(默认len () = 1)


一些注意事项:

1)利用加权抽样与替换,使绘制的项目以后可以被替换。权重序列中的值本身并不重要,但它们的相对比例却很重要。

np.random.choice只能将概率作为权重,也必须确保个人概率的总和达到1个标准,但这里没有这样的规定。只要它们属于数值类型(int/float/fraction, Decimal类型除外),就仍然可以执行。

>>> import random
# weights being integers
>>> random.choices(["white", "green", "red"], [12, 12, 4], k=10)
['green', 'red', 'green', 'white', 'white', 'white', 'green', 'white', 'red', 'white']
# weights being floats
>>> random.choices(["white", "green", "red"], [.12, .12, .04], k=10)
['white', 'white', 'green', 'green', 'red', 'red', 'white', 'green', 'white', 'green']
# weights being fractions
>>> random.choices(["white", "green", "red"], [12/100, 12/100, 4/100], k=10)
['green', 'green', 'white', 'red', 'green', 'red', 'white', 'green', 'green', 'green']

2)如果既没有指定weights,也没有指定cum_weights,则以等概率进行选择。如果提供了权重序列,则它必须与填充序列的长度相同。

同时指定weights和cum_weights将引发TypeError。

>>> random.choices(["white", "green", "red"], k=10)
['white', 'white', 'green', 'red', 'red', 'red', 'white', 'white', 'white', 'green']

3) cum_weights通常是itertools的结果。累加函数在这种情况下非常方便。

从文档链接: 在内部,相对权重被转换为累积权重 在进行选择之前,提供累计权重可以节省 工作。

因此,无论是提供weights=[12,12,4]还是cum_weights=[12,24,28],对于我们所设计的情况都会产生相同的结果,并且后者似乎更快/更有效。

其他回答

另一种方法是,假设我们的权重与元素数组中的元素的下标相同。

import numpy as np
weights = [0.1, 0.3, 0.5] #weights for the item at index 0,1,2
# sum of weights should be <=1, you can also divide each weight by sum of all weights to standardise it to <=1 constraint.
trials = 1 #number of trials
num_item = 1 #number of items that can be picked in each trial
selected_item_arr = np.random.multinomial(num_item, weights, trials)
# gives number of times an item was selected at a particular index
# this assumes selection with replacement
# one possible output
# selected_item_arr
# array([[0, 0, 1]])
# say if trials = 5, the the possible output could be 
# selected_item_arr
# array([[1, 0, 0],
#   [0, 0, 1],
#   [0, 0, 1],
#   [0, 1, 0],
#   [0, 0, 1]])

现在我们假设,我们要在一次试验中抽取3个项目。你可以假设有三个球R、G、B大量存在,它们的权重由权重数组给定,可能的结果如下:

num_item = 3
trials = 1
selected_item_arr = np.random.multinomial(num_item, weights, trials)
# selected_item_arr can give output like :
# array([[1, 0, 2]])

您还可以将要选择的项目数量视为一组中二项/多项试验的数量。所以,上面的例子仍然可以作为工作

num_binomial_trial = 5
weights = [0.1,0.9] #say an unfair coin weights for H/T
num_experiment_set = 1
selected_item_arr = np.random.multinomial(num_binomial_trial, weights, num_experiment_set)
# possible output
# selected_item_arr
# array([[1, 4]])
# i.e H came 1 time and T came 4 times in 5 binomial trials. And one set contains 5 binomial trails.

步骤1:生成您感兴趣的CDF F

步骤2:生成u.r.v. u

步骤3:求z=F^{-1}(u)

这种建模在概率论或随机过程课程中有描述。这是适用的,因为您有简单的CDF。

如果你有一个加权字典而不是一个列表,你可以这样写

items = { "a": 10, "b": 5, "c": 1 } 
random.choice([k for k in items for dummy in range(items[k])])

注意(k, k范围的虚拟物品(物品[k])]产生这个列表(' a ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' c ', ' b ', ' b ', ' b ', ' b ', ' b ']

如果你碰巧有Python 3,并且害怕安装numpy或编写自己的循环,你可以这样做:

import itertools, bisect, random

def weighted_choice(choices):
   weights = list(zip(*choices))[1]
   return choices[bisect.bisect(list(itertools.accumulate(weights)),
                                random.uniform(0, sum(weights)))][0]

因为你可以用一袋管道适配器做任何东西!尽管……我必须承认,尼德的回答虽然稍长一些,但比较容易理解。

如果您的加权选项列表是相对静态的,并且您希望频繁采样,则可以执行一个O(N)预处理步骤,然后使用相关答案中的函数在O(1)中进行选择。

# run only when `choices` changes.
preprocessed_data = prep(weight for _,weight in choices)

# O(1) selection
value = choices[sample(preprocessed_data)][0]