Una versión ponderada de random.choice

Necesitaba escribir una versión ponderada de random.choice (cada elemento de 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 los que están aquí puedan ofrecer algunas sugerencias para mejorarlo o formas alternativas de hacerlo. La eficiencia no es tan importante para mí como la limpieza y legibilidad del código.

Desde la versión 1.7.0, NumPy tiene una función de choice 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 la probability_distribution es una secuencia en el mismo orden de list_of_candidates . También puede usar la palabra clave replace=False para cambiar el comportamiento para que los elementos dibujados no se reemplacen.

 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" 

Desde Python3.6 hay un método de selección de módulo random .

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

Y las personas también mencionaron que existe una numpy.random.choice que soporta ponderaciones, PERO no soporta matrices 2d , y así sucesivamente.

Así que, básicamente, puedes obtener lo que quieras (ver actualización ) con built . random si eliges 3.6.x Python .

ACTUALIZACIÓN : Como @roganjosh amablemente mencionó, random.choices no puede devolver valores sin reemplazo, como se menciona en la documentación :

Devuelva una lista de elementos de tamaño k elegida de la población con reemplazo .

Y la shiny respuesta de @ronan-paixão dice que numpy.choice tiene un argumento de replace , que controla tal comportamiento.

  1. Organizar los pesos en una distribución acumulativa.
  2. Use random.random () para elegir un float aleatorio 0.0 <= x < total .
  3. Busque la distribución utilizando 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 opción, divida esto en dos funciones, una para generar los pesos acumulativos y otra para dividir en un punto al azar.

Si no te importa usar numpy, puedes 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 por adelantado, puede hacerlo sin un bucle 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 agregar hasta 100, simplemente lo hice para facilitar la interpretación de los resultados de la prueba. (Si los pesos son números de punto 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 este

 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 , v3.6 podría usarse para devolver una list de elementos de tamaño específico de la población dada con ponderaciones opcionales.

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

  • población : list contiene observaciones únicas. (Si está vacío, eleva IndexError )

  • Pesos : pesos relativos más precisos requeridos para hacer selecciones.

  • cum_weights : pesos acumulativos necesarios para realizar selecciones.

  • k : tamaño ( len ) de la list a generar. (Predeterminado len()=1 )


Algunas advertencias:

1) Hace uso del muestreo ponderado con reemplazo para que los elementos dibujados se reemplacen más tarde. Los valores en la secuencia de pesos en sí mismos no importan, pero sí lo hace su relación relativa.

A diferencia de np.random.choice que solo puede tomar en cuenta las probabilidades como ponderaciones y también debe asegurar la sum de las probabilidades individuales hasta 1 criterio, no hay tales regulaciones aquí. Siempre y cuando pertenezcan a tipos numéricos ( int/float/fraction excepto el tipo Decimal ), 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 pesos ni cum_weights , las selecciones se realizan con la misma probabilidad. Si se suministra una secuencia de pesos , debe tener la misma longitud que la secuencia de población .

Especificar ambos pesos y cum_weights genera un TypeError .

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

3) los cum_weights suelen ser el resultado de la función itertools.accumulate que son realmente útiles en tales situaciones.

De la documentación vinculada:

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

Por lo tanto, ya sea que suministramos weights=[12, 12, 4] o cum_weights=[12, 24, 28] para nuestro caso idóneo se obtiene el mismo resultado y este último parece ser más rápido / eficiente.

Esta es la versión que se incluye en la biblioteca estándar de 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 ak 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

Requeriría que la sum de opciones sea 1, pero esto funciona de todos modos

 def weightedChoice(choices): # Safety check, you can remove it for c,w in choices: assert w >= 0 tmp = random.uniform(0, sum(c for c,w in choices)) for choice,weight in choices: if tmp < weight: return choice else: tmp -= weight raise ValueError('Negative values in input') 
 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 aportar 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 tienes pesos, simplemente agrega 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] 

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] 

Si su lista de opciones ponderadas es relativamente estática y desea un muestreo frecuente, puede hacer un paso de preprocesamiento O (N) y luego hacer la selección en O (1), utilizando las funciones de 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] 

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

Supongamos que desea muestrear la distribución K veces. Luego, la complejidad del tiempo que usa np.random.choice() cada vez es O(K(n + log(n))) cuando n es 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. Utilicé el siguiente código, que calcula la distribución acumulativa y la muestrea en O(log(n)) . La complejidad global 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] 

Busqué el otro hilo puntiagudo y se me ocurrió esta variación en mi estilo de encoding, esto devuelve el índice de elección para fines de conteo, pero es simple devolver la cadena (alternativa de retorno 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]) 

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 se eligió. Por defecto, el código solo hace un solo sorteo, pero puede pasar el número de sorteos que se realizarán y se devolverán los conteos por sorteo.

Si el vector de pesos no sum 1, se normalizará de modo 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]) 

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 aplicación cruda como un 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, realmente simple, desde la búsqueda de ideas finalmente construí esta plantilla. La idea es recibir los valores ponderados en forma de json de la api, que aquí se simula mediante 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 probé corriendo 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)