Forma pitónica para seleccionar elementos de lista con diferente probabilidad

Question

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

Este código me da "A", "B" o "C" con la misma probabilidad. ¿Hay una buena manera de expresarlo cuando quiere "A" con 30%, "B" con 40% y "C" con 30% de probabilidad?

Answer 1

Los pesos definen una función de distribución de probabilidad (pdf). Los números aleatorios a partir de cualquiera de tales pdf pueden ser generados por applying its associated inverse cumulative distribution function a números aleatorios uniformes entre 0 y 1.

Ver también este SO explanation, o, como se explica por 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 

La función choice anteriormente usa bisect.bisect, por lo que la selección de una variable aleatoria ponderada se realiza en O(log n) donde n es la longitud de weights.

---

Nota que a partir de la versión 1.7.0, NumPy tiene una Cythonized np.random.choice function. Por ejemplo, esto genera 1000 muestras de la población [0,1,2,3] con pesos [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 también tiene un parámetro replace para el muestreo con o sin sustitución.

---

Un teóricamente mejor algoritmo es el Alias Method. Construye una tabla que requiere O(n) tiempo, pero después de eso, las muestras se pueden dibujar en O(1) vez. Entonces, si necesita dibujar muchas muestras, en teoría, el Método Alias ​​puede ser más rápido. Hay una implementación de Python del Método Walker Alias ​​here y un numpy version here.

Answer 2

No ... tanto ...

pos = ['A'] * 3 + ['B'] * 4 + ['C'] * 3 
print random.choice(pos) 

o

pos = {'A': 3, 'B': 4, 'C': 3} 
print random.choice([x for x in pos for y in range(pos[x])]) 

Answer 3

Aquí es una clase para exponer un montón de elementos con probabilidades relativas, sin tener que ampliar la lista:

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 

Ahora, acaba de decir:

data = WeightedTuple({'A': 30, 'B': 40, 'C': 30}) 
random.choice(data) 

Answer 4

Prueba esto:

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

También puede hacer uso de este formulario, que no crea una lista arbitrariamente grande (y puede trabajar con cualquiera de las probabilidades integrales o decimales):

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

Hay Aquí se ofrecen algunas buenas soluciones, pero le sugiero que consulte Eli Bendersky's thorough discussion de esta edición, que compara varios algoritmos para lograr esto (con implementaciones en Python) antes de elegir uno.