aleatoria elección ponderada

Question

tengo datos de la siguiente manera:

d = (
    (701, 1, 0.2), 
    (701, 2, 0.3), 
    (701, 3, 0.5), 
    (702, 1, 0.2), 
    (702, 2, 0.3), 
    (703, 3, 0.5) 
) 

Dónde (701, 1, 0,2) = (ID1, ID2, prioridad)

¿Hay una manera bastante para elegir id2 si sé id1, ¿usando prioridad?

Func (701) debería devolver:
    1 - en 20% de los casos
    2 - 30%
    3 - 50%

ciento será áspera por supuesto

Answer 1

generar una función de distribución acumulativa para cada ID1 así:

cdfs = defaultdict() 
for id1,id2,val in d: 
    prevtotal = cdfs[id1][-1][0] 
    newtotal = prevtotal + val 
    cdfs[id1].append((newtotal,id2)) 

por lo que tendrá

cdfs = { 701 : [ (0.2,1), (0.5,2), (1.0,3) ], 
     702 : [ (0.2,1), (0.5,2) ], 
     703 : [ (0.5,3) ] } 

Luego genere un número aleatorio y búsqueda para ello en la lista.

def func(id1): 
    max = cdfs[id1][-1][0] 
    rand = random.random()*max 
    for upper,id2 in cdfs[id1]: 
     if upper>rand: 
      return id2 
    return None 

Answer 2

Utilice una distribución uniforme discreta del random module en un número suficiente de valores, luego divídalo:

Por ejemplo, para el caso de 701 utilizar una distribución de más de 10 valores, para 2 valores de retorno 1, para otro 3, volver 2, y para el otro 5, volver 3.

Usted puede construir cualquier distribución usando lo suficientemente uniforme distribuciones :)

Answer 3

Si los valores porcentuales no serán más precisos que los valores porcentuales enteros, utilice un generador de números aleatorios para generar un número 0-99.

Luego, en su función, use casos (programáticos) para elegir el número correcto. Por ejemplo (limpiar esto):

 
if 701 
    if random_num < 20 
    return 1 
    else if random number < 50 // (20 + 30) 
    return 2 
    else if random number < 100 // (20 + 30 + 50) 
    return 3 
    else 
    // error 

Answer 4

Un truco muy rápido:

import random 

d = { 
    701: [(1,0.2),(2,0.3),(3,0.5)], 
    702: [(1,0.2),(2,0.3),(3,0.5)] 
} 

def func(value): 
    possible_values=d[value] 
    total=sum(p[-1] for p in possible_values) 
    random_value=random.random() 
    prob=possible_values[0][-1]/total 
    index=1 
    while index<len(possible_values) and prob<random_value: 
     prob+=possible_values[index][-1]/total 
     index+=1 
    return possible_values[index-1][0] 

if __name__=='__main__': 
    testcases=1000 
    cnt=[0,0,0] 
    for case in xrange(testcases): 
     answer=func(701) 
     cnt[answer-1]+=1 
    for i in xrange(3): 
     print "Got %d %f%% of the time"%(i+1,float(cnt[i])/testcases*100) 

No es bonita, pero es el primero que me vino a la mente, y parece funcionar como se espera.

Lo que hace es obtener un valor aleatorio en el intervalo [0,1) (usando random.random()). Luego usa si el valor aleatorio cae en los intervalos [0,0.2), [0.2,0.5) o [0.5,1], para determinar qué valor devolver.

Answer 5

dos ideas (Permítanme ilustrar con opciones separadas y proporciones en aras de la claridad en los nombres de los argumentos, si están envasados ​​en una tupla puede guardar el "zip"):

a) Desnormalizar los pesos para obtener relaciones enteras, luego poner en una lista tantas copias como la proporción y usar random.choice.

def choice_with_ratios(options, ratios): 
    tmp = sum([[v]*n for v, n in zip(options, ratios)], []) 
    return random.choice(tmp) 

b) Utilizar los pesos normalizados y empezar sumando hasta llegar a un valor aleatorio uniforme generado

def choice_with_weights(options, weights): 
    s = 0 
    r = random.random() 
    for v, w in zip(options, weights): 
     s += w 
     if s >= r: break 
    return v 

Por cierto, si el primer campo se utiliza como una clave, que debe tenerlo en un diccionario, como:

d = { 
    701: ((1, 0.2), (2, 0.3), (3, 0.5), 
    702: ((1, 0.3), (2, 0.2), (3, 0.5) 
} 

Answer 6

Al darme cuenta de que mi primera respuesta fue bastante problemática en sus cálculos matemáticos, he producido una nueva idea. Creo que el algoritmo aquí es similar a la de varias de las otras respuestas, pero esta aplicación parece formar parte del "bastante" (si es que es igual sencilla) requisito de la cuestión:

def func(id): 
    rnd = random() 
    sum = 0 
    for row in d: 
     if row[0] == id: 
      sum = sum + row[2] 
      if rnd < sum: 
       return row[1] 

Con los datos del ejemplo de la OP va así:

• elegir un número aleatorio entre 0 y 1,0
• Si el número es < 0.2 de regreso al primer elemento
• Else si el número es < 0.5 devolver el segundo elemento
• demás (si el número es < 1.0) devuelven el tercer elemento

Answer 7

También puede crear una lista de 100 elementos para cada valor y, a continuación, dejar que random.choice hacer la selección de una lista cuyos miembros son cabeza de serie cargado en la ponderación que desea:

import random 
from collections import defaultdict 

d = ( 
    (701, 1, 0.2), 
    (701, 2, 0.3), 
    (701, 3, 0.5), 
    (702, 1, 0.2), 
    (702, 2, 0.3), 
    (702, 3, 0.5) 
) 

class WeightedLookup(object): 
    def __init__(self, valueTupleList): 
     self.valdict = defaultdict(list) 
     for key, val, prob in valueTupleList: 
      self.valdict[key] += [val]*(int)(prob*100) 

    def __getitem__(self,key): 
     return random.choice(self.valdict[key]) 


lookup = WeightedLookup(d) 

# test out our lookup distribution, sample it 100000 times 
res = { 1:0, 2:0, 3:0 } 
for i in range(100000): 
    res[lookup[701]] += 1 

# print how many times each value was returned 
for k in (1,2,3): 
    print k, res[k] 

Lienzo:

1 20059 
2 30084 
3 49857