Una versión ponderada de random.choice

Necesitaba escribir una versión ponderada de random.choice (cada elemento en la lista tiene una probabilidad diferente de ser seleccionado). Esto es lo que se me ocurrió:

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

Esta función me parece demasiado compleja y fea. Espero que todos aquí puedan ofrecer algunas sugerencias para mejorarlo o formas alternativas de hacerlo. La eficiencia no es tan importante para mí como la limpieza y la legibilidad del código.

Desde la versión 1.7.0, NumPy tiene una choicefunción que admite distribuciones de probabilidad.

from numpy.random import choice
draw = choice(list_of_candidates, number_of_items_to_pick,
              p=probability_distribution)

Tenga en cuenta que probability_distributiones una secuencia en el mismo orden de list_of_candidates. También puede usar la palabra clave replace=Falsepara cambiar el comportamiento para que los elementos dibujados no se reemplacen.

Desde Python 3.6 hay un método choicesdesde el randommódulo.

Python 3.6.1 (v3.6.1:69c0db5050, Mar 21 2017, 01:21:04)
Type 'copyright', 'credits' or 'license' for more information
IPython 6.0.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import random

In [2]: random.choices(
...:     population=[['a','b'], ['b','a'], ['c','b']],
...:     weights=[0.2, 0.2, 0.6],
...:     k=10
...: )

Out[2]:
[['c', 'b'],
 ['c', 'b'],
 ['b', 'a'],
 ['c', 'b'],
 ['c', 'b'],
 ['b', 'a'],
 ['c', 'b'],
 ['b', 'a'],
 ['c', 'b'],
 ['c', 'b']]

Tenga en cuenta que random.choicesse muestra con reemplazo , según los documentos :

Devuelva una klista de tamaño de los elementos elegidos de la población con reemplazo.

Si necesita muestrear sin reemplazo, entonces, como dice la brillante respuesta de @ ronan-paixão , puede usar numpy.choice, cuyo replaceargumento controla dicho comportamiento.

def weighted_choice(choices):
   total = sum(w for c, w in choices)
   r = random.uniform(0, total)
   upto = 0
   for c, w in choices:
      if upto + w >= r:
         return c
      upto += w
   assert False, "Shouldn't get here"

1. Organice los pesos en una distribución acumulativa.
2. Use random.random () para elegir un flotante aleatorio 0.0 <= x < total.
3. Busque la distribución usando bisect.bisect como se muestra en el ejemplo en http://docs.python.org/dev/library/bisect.html#other-examples .

from random import random
from bisect import bisect

def weighted_choice(choices):
    values, weights = zip(*choices)
    total = 0
    cum_weights = []
    for w in weights:
        total += w
        cum_weights.append(total)
    x = random() * total
    i = bisect(cum_weights, x)
    return values[i]

>>> weighted_choice([("WHITE",90), ("RED",8), ("GREEN",2)])
'WHITE'

Si necesita hacer más de una elección, divídalo en dos funciones, una para construir los pesos acumulativos y otra para dividir en bisectos a un punto aleatorio.

Si no le importa usar numpy, puede usar numpy.random.choice .

Por ejemplo:

import numpy

items  = [["item1", 0.2], ["item2", 0.3], ["item3", 0.45], ["item4", 0.05]
elems = [i[0] for i in items]
probs = [i[1] for i in items]

trials = 1000
results = [0] * len(items)
for i in range(trials):
    res = numpy.random.choice(items, p=probs)  #This is where the item is selected!
    results[items.index(res)] += 1
results = [r / float(trials) for r in results]
print "item\texpected\tactual"
for i in range(len(probs)):
    print "%s\t%0.4f\t%0.4f" % (items[i], probs[i], results[i])

Si sabe cuántas selecciones necesita hacer de antemano, puede hacerlo sin un ciclo como este:

numpy.random.choice(items, trials, p=probs)

Crudo, pero puede ser suficiente:

import random
weighted_choice = lambda s : random.choice(sum(([v]*wt for v,wt in s),[]))

¿Funciona?

# define choices and relative weights
choices = [("WHITE",90), ("RED",8), ("GREEN",2)]

# initialize tally dict
tally = dict.fromkeys(choices, 0)

# tally up 1000 weighted choices
for i in xrange(1000):
    tally[weighted_choice(choices)] += 1

print tally.items()

Huellas dactilares:

[('WHITE', 904), ('GREEN', 22), ('RED', 74)]

Asume que todos los pesos son enteros. No tienen que sumar 100, solo hice eso para que los resultados de la prueba sean más fáciles de interpretar. (Si los pesos son números de coma flotante, multiplíquelos todos por 10 repetidamente hasta que todos los pesos> = 1.)

weights = [.6, .2, .001, .199]
while any(w < 1.0 for w in weights):
    weights = [w*10 for w in weights]
weights = map(int, weights)

Si tiene un diccionario ponderado en lugar de una lista, puede escribir esto

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

Tenga en cuenta que [k for k in items for dummy in range(items[k])]produce esta lista['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']

A partir de Python v3.6, random.choicespodría usarse para devolver un listelemento de tamaño específico de la población dada con pesos opcionales.

random.choices(population, weights=None, *, cum_weights=None, k=1)

• población : listcontiene observaciones únicas. (Si está vacío, sube IndexError)

• pesos : más precisamente, los pesos relativos necesarios para realizar selecciones.

• cum_weights : pesos acumulativos necesarios para realizar selecciones.

• k : tamaño ( len) de la listsalida. (Predeterminado len()=1)

Pocas advertencias:

1) Utiliza muestreo ponderado con reemplazo para que los artículos extraídos sean reemplazados más tarde. Los valores en la secuencia de pesos en sí mismos no importan, pero su relación relativa sí.

A diferencia de lo np.random.choiceque solo puede asumir las probabilidades como ponderaciones y también lo que debe garantizar la suma de las probabilidades individuales hasta 1 criterio, aquí no existen tales regulaciones. Mientras pertenezcan a tipos numéricos ( int/float/fractionexcepto el Decimaltipo), estos seguirían funcionando.

>>> 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) Si no se especifican ni pesos ni cum_weights , las selecciones se realizan con la misma probabilidad. Si se proporciona una secuencia de pesos , debe tener la misma longitud que la secuencia de población .

Especificar pesos y cum_weights plantea a TypeError.

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

3) cum_weights son típicamente el resultado de una itertools.accumulatefunción que es realmente útil en tales situaciones.

_{De la documentación vinculada:}

Internamente, los pesos relativos se convierten en pesos acumulativos antes de realizar selecciones, por lo que el suministro de los pesos acumulativos ahorra trabajo.

Por lo tanto, el suministro weights=[12, 12, 4]o cum_weights=[12, 24, 28]para nuestro caso artificial produce el mismo resultado y este último parece ser más rápido / eficiente.

Aquí está la versión que se incluye en la biblioteca estándar para Python 3.6:

import itertools as _itertools
import bisect as _bisect

class Random36(random.Random):
    "Show the code included in the Python 3.6 version of the Random class"

    def choices(self, population, weights=None, *, cum_weights=None, k=1):
        """Return a k sized list of population elements chosen with replacement.

        If the relative weights or cumulative weights are not specified,
        the selections are made with equal probability.

        """
        random = self.random
        if cum_weights is None:
            if weights is None:
                _int = int
                total = len(population)
                return [population[_int(random() * total)] for i in range(k)]
            cum_weights = list(_itertools.accumulate(weights))
        elif weights is not None:
            raise TypeError('Cannot specify both weights and cumulative weights')
        if len(cum_weights) != len(population):
            raise ValueError('The number of weights does not match the population')
        bisect = _bisect.bisect
        total = cum_weights[-1]
        return [population[bisect(cum_weights, random() * total)] for i in range(k)]

Fuente: https://hg.python.org/cpython/file/tip/Lib/random.py#l340

import numpy as np
w=np.array([ 0.4,  0.8,  1.6,  0.8,  0.4])
np.random.choice(w, p=w/sum(w))

Probablemente sea demasiado tarde para contribuir con algo útil, pero aquí hay un fragmento simple, breve y muy eficiente:

def choose_index(probabilies):
    cmf = probabilies[0]
    choice = random.random()
    for k in xrange(len(probabilies)):
        if choice <= cmf:
            return k
        else:
            cmf += probabilies[k+1]

No es necesario ordenar sus probabilidades o crear un vector con su cmf, y termina una vez que encuentra su elección. Memoria: O (1), tiempo: O (N), con tiempo de ejecución promedio ~ N / 2.

Si tiene pesas, simplemente agregue una línea:

def choose_index(weights):
    probabilities = weights / sum(weights)
    cmf = probabilies[0]
    choice = random.random()
    for k in xrange(len(probabilies)):
        if choice <= cmf:
            return k
        else:
            cmf += probabilies[k+1]

Si su lista de opciones ponderadas es relativamente estática y desea un muestreo frecuente, puede hacer un paso de preprocesamiento de O (N) y luego hacer la selección en O (1), utilizando las funciones en esta respuesta relacionada .

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

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

Miré el otro hilo puntiagudo y se me ocurrió esta variación en mi estilo de codificación, esto devuelve el índice de elección para el recuento, pero es simple devolver la cadena (alternativa de devolución comentada):

import random
import bisect

try:
    range = xrange
except:
    pass

def weighted_choice(choices):
    total, cumulative = 0, []
    for c,w in choices:
        total += w
        cumulative.append((total, c))
    r = random.uniform(0, total)
    # return index
    return bisect.bisect(cumulative, (r,))
    # return item string
    #return choices[bisect.bisect(cumulative, (r,))][0]

# define choices and relative weights
choices = [("WHITE",90), ("RED",8), ("GREEN",2)]

tally = [0 for item in choices]

n = 100000
# tally up n weighted choices
for i in range(n):
    tally[weighted_choice(choices)] += 1

print([t/sum(tally)*100 for t in tally])

Depende de cuántas veces desee muestrear la distribución.

Suponga que desea muestrear la distribución K veces. Entonces, la complejidad de tiempo que se usa np.random.choice()cada vez es O(K(n + log(n)))cuándo nes el número de elementos en la distribución.

En mi caso, necesitaba muestrear la misma distribución varias veces del orden de 10 ^ 3 donde n es del orden de 10 ^ 6. Usé el siguiente código, que calcula previamente la distribución acumulativa y la muestra O(log(n)). La complejidad general del tiempo es O(n+K*log(n)).

import numpy as np

n,k = 10**6,10**3

# Create dummy distribution
a = np.array([i+1 for i in range(n)])
p = np.array([1.0/n]*n)

cfd = p.cumsum()
for _ in range(k):
    x = np.random.uniform()
    idx = cfd.searchsorted(x, side='right')
    sampled_element = a[idx]

Si tiene Python 3 y tiene miedo de instalar numpyo escribir sus propios bucles, puede hacer lo siguiente:

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]

¡Porque puede construir cualquier cosa con una bolsa de adaptadores de plomería! Aunque ... debo admitir que la respuesta de Ned, aunque un poco más larga, es más fácil de entender.

Una solución general:

import random
def weighted_choice(choices, weights):
    total = sum(weights)
    treshold = random.uniform(0, total)
    for k, weight in enumerate(weights):
        total -= weight
        if total < treshold:
            return choices[k]

Aquí hay otra versión de weighted_choice que usa numpy. Pase el vector de pesos y devolverá una matriz de 0 que contiene un 1 que indica qué bin fue elegido. El código predeterminado es solo hacer un sorteo único, pero puede pasar el número de sorteos que se realizarán y se devolverán los recuentos por sorteo.

Si el vector de pesos no suma 1, se normalizará para que lo haga.

import numpy as np

def weighted_choice(weights, n=1):
    if np.sum(weights)!=1:
        weights = weights/np.sum(weights)

    draws = np.random.random_sample(size=n)

    weights = np.cumsum(weights)
    weights = np.insert(weights,0,0.0)

    counts = np.histogram(draws, bins=weights)
    return(counts[0])

Otra forma de hacerlo, suponiendo que tengamos pesos en el mismo índice que los elementos en la matriz de elementos.

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]])

Ahora supongamos que tenemos que probar 3 elementos en 1 prueba. Puede suponer que hay tres bolas R, G, B presentes en gran cantidad en relación con sus pesos dados por la matriz de peso, el siguiente resultado podría ser posible:

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]])

También puede pensar en el número de elementos que se seleccionarán como número de ensayos binomiales / multinomiales dentro de un conjunto. Entonces, el ejemplo anterior todavía puede funcionar como

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.

Sebastien Thurn da una conferencia sobre esto en el curso gratuito Udacity AI for Robotics. Básicamente, hace una matriz circular de los pesos indexados utilizando el operador mod% , establece una variable beta en 0, elige aleatoriamente un índice, para bucles a través de N donde N es el número de índices y en el bucle for en primer lugar incrementa beta por la fórmula:

beta = beta + muestra uniforme de {0 ... 2 * Weight_max}

y luego anidado en el ciclo for, un ciclo while por debajo:

while w[index] < beta:
    beta = beta - w[index]
    index = index + 1

select p[index]

Luego, al siguiente índice para volver a muestrear en función de las probabilidades (o probabilidad normalizada en el caso presentado en el curso).

El enlace de la conferencia: https://classroom.udacity.com/courses/cs373/lessons/48704330/concepts/487480820923

Estoy conectado a Udacity con la cuenta de mi escuela, por lo que si el enlace no funciona, es la Lección 8, video número 21 de Inteligencia Artificial para Robótica, donde está dando conferencias sobre filtros de partículas.

Una forma es aleatorizar el total de todos los pesos y luego usar los valores como puntos límite para cada var. Aquí hay una implementación cruda como generador.

def rand_weighted(weights):
    """
    Generator which uses the weights to generate a
    weighted random values
    """
    sum_weights = sum(weights.values())
    cum_weights = {}
    current_weight = 0
    for key, value in sorted(weights.iteritems()):
        current_weight += value
        cum_weights[key] = current_weight
    while True:
        sel = int(random.uniform(0, 1) * sum_weights)
        for key, value in sorted(cum_weights.iteritems()):
            if sel < value:
                break
        yield key

Usando numpy

def choice(items, weights):
    return items[np.argmin((np.cumsum(weights) / sum(weights)) < np.random.rand())]

Necesitaba hacer algo como esto realmente rápido, muy simple, desde la búsqueda de ideas finalmente construí esta plantilla. La idea es recibir los valores ponderados en forma de un json de la API, que aquí es simulada por el dict.

Luego, conviértalo en una lista en la que cada valor se repita proporcionalmente a su peso, y simplemente use random.choice para seleccionar un valor de la lista.

Lo intenté con 10, 100 y 1000 iteraciones. La distribución parece bastante sólida.

def weighted_choice(weighted_dict):
    """Input example: dict(apples=60, oranges=30, pineapples=10)"""
    weight_list = []
    for key in weighted_dict.keys():
        weight_list += [key] * weighted_dict[key]
    return random.choice(weight_list)

No me encantó la sintaxis de ninguno de esos. Realmente quería especificar cuáles eran los artículos y cuál era el peso de cada uno. Me doy cuenta de que podría haber usado, random.choicespero en su lugar, escribí rápidamente la clase a continuación.

import random, string
from numpy import cumsum

class randomChoiceWithProportions:
    '''
    Accepts a dictionary of choices as keys and weights as values. Example if you want a unfair dice:


    choiceWeightDic = {"1":0.16666666666666666, "2": 0.16666666666666666, "3": 0.16666666666666666
    , "4": 0.16666666666666666, "5": .06666666666666666, "6": 0.26666666666666666}
    dice = randomChoiceWithProportions(choiceWeightDic)

    samples = []
    for i in range(100000):
        samples.append(dice.sample())

    # Should be close to .26666
    samples.count("6")/len(samples)

    # Should be close to .16666
    samples.count("1")/len(samples)
    '''
    def __init__(self, choiceWeightDic):
        self.choiceWeightDic = choiceWeightDic
        weightSum = sum(self.choiceWeightDic.values())
        assert weightSum == 1, 'Weights sum to ' + str(weightSum) + ', not 1.'
        self.valWeightDict = self._compute_valWeights()

    def _compute_valWeights(self):
        valWeights = list(cumsum(list(self.choiceWeightDic.values())))
        valWeightDict = dict(zip(list(self.choiceWeightDic.keys()), valWeights))
        return valWeightDict

    def sample(self):
        num = random.uniform(0,1)
        for key, val in self.valWeightDict.items():
            if val >= num:
                return key

Proporcione random.choice () con una lista pre ponderada:

Solución y prueba:

import random

options = ['a', 'b', 'c', 'd']
weights = [1, 2, 5, 2]

weighted_options = [[opt]*wgt for opt, wgt in zip(options, weights)]
weighted_options = [opt for sublist in weighted_options for opt in sublist]
print(weighted_options)

# test

counts = {c: 0 for c in options}
for x in range(10000):
    counts[random.choice(weighted_options)] += 1

for opt, wgt in zip(options, weights):
    wgt_r = counts[opt] / 10000 * sum(weights)
    print(opt, counts[opt], wgt, wgt_r)

Salida:

['a', 'b', 'b', 'c', 'c', 'c', 'c', 'c', 'd', 'd']
a 1025 1 1.025
b 1948 2 1.948
c 5019 5 5.019
d 2008 2 2.008