Питоновский способ выбора элементов списка с разной вероятностью

Ответ 1

Массы определяют функцию распределения вероятности (pdf). Случайные числа из любого такого pdf могут быть сгенерированы с помощью применения его связанной функции обратного кумулятивного распределения к равномерным случайным числам между 0 и 1.

См. также описание fooobar.com/questions/198180/... или, как объяснено Wikipedia:

Если Y имеет распределение U [0,1], тогда F⁻¹ (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})
enter code here

В приведенной выше функции 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 ​​Method. Он создает таблицу, которая требует времени O(n), но после этого образцы могут быть нарисованы в O(1) времени. Итак, если вам нужно нарисовать много образцов, теоретически метод псевдонимов может быть быстрее. Существует реализация Python метода псевдонима Walker здесь и здесь здесь.

Ответ 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])])

Ответ 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)

Ответ 4

Есть несколько хороших решений, предлагаемых здесь, но я бы посоветовал вам взглянуть на подробное обсуждение Эли Бендерски этого вопроса, в котором сравниваются различные алгоритмы для достижения этого (с реализацией на Python), прежде чем выбрать его.

Ответ 5

Вы также можете использовать эту форму, которая не создает список сколь угодно большой (и может работать как с интегральной, так и с десятичной вероятностью):

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

Ответ 6

Попробуйте следующее:

import random
from decimal import Decimal

pos = {'A': Decimal("0.3"), 'B': Decimal("0.4"), 'C': Decimal("0.3")}
choice = random.random()
F_x = 0
for k, p in pos.iteritems():
    F_x += p
    if choice <= F_x:
        x = k
        break