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

Question

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

Этот код дает мне «A», «B» или «C» с равной вероятностью. Есть ли хороший способ выразить это, когда вы хотите «A» с 30%, «B» с 40% и «C» с вероятностью 30%?

Answer 1

Веса определяют функцию распределения вероятности (pdf). Случайные числа из любого такого PDF могут быть получены путем applying its associated inverse cumulative distribution function единым случайных чисел между 0 и 1.

Смотрите также SO explanation этого, или, как объясняется Wikipedia:

If Y has a U[0,1] distribution then F⁻¹(Y) is distributed as F. This is used in random number generation using the inverse transform sampling-method.

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 

The choice функции выше использует bisect.bisect, поэтому выбор взвешенной случайной величины производится в O(log n), где n - это длина weights.

---

Обратите внимание, что в версии 1.7.0, NumPy имеет Cythonized np.random.choice function. Например, это порождает 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 here и numpy version here.

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

Попробуйте это:

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 

Answer 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 

Answer 6

Там некоторые полезные решения, предлагаемые здесь, но я бы предположил, что вы посмотрите на Eli Bendersky's thorough discussion этой проблемы, которая сравнивает различные алгоритмы для достижения этой цели (с реализацией на Python) перед ее выбором.