Distribución de probabilidad en Python

Tengo un montón de claves que cada una tiene una variable diferente. Quiero elegir aleatoriamente una de estas claves, pero quiero que sea más improbable que se elija un improbable (clave, valores) que un objeto menos improbable (más probable). Me pregunto si tendrías alguna sugerencia, preferiblemente un módulo Python existente que pueda usar, de lo contrario, necesitaré hacerlo yo mismo.

He revisado el módulo aleatorio; No parece proporcionar esto.

Tengo que tomar esas decisiones muchos millones de veces para 1000 conjuntos diferentes de objetos, cada uno con 2.455 objetos. Cada conjunto intercambiará objetos entre sí, por lo que el selector aleatorio debe ser dynamic. Con 1000 juegos de 2,433 objetos, eso es 2,433 millones de objetos; El bajo consumo de memoria es crucial. Y como estas opciones no son la mayor parte del algoritmo, necesito que este proceso sea bastante rápido; El tiempo de CPU es limitado.

Gracias

Actualizar:

Ok, traté de considerar sus sugerencias sabiamente, pero el tiempo es muy limitado …

Miré el enfoque del árbol de búsqueda binario y parece demasiado arriesgado (complejo y complicado). Las otras sugerencias se parecen a la receta de ActiveState. Lo tomé y lo modifiqué un poco con la esperanza de hacerlo más eficiente:

def windex(dict, sum, max): '''an attempt to make a random.choose() function that makes weighted choices accepts a dictionary with the item_key and certainty_value as a pair like: >>> x = [('one', 20), ('two', 2), ('three', 50)], the maximum certainty value (max) and the sum of all certainties.''' n = random.uniform(0, 1) sum = max*len(list)-sum for key, certainty in dict.iteritems(): weight = float(max-certainty)/sum if n < weight: break n = n - weight return key 

Espero obtener una ganancia en eficiencia al mantener dinámicamente la sum de certezas y la máxima certeza. Cualquier otra sugerencia son bienvenidas. Chicos, me ahorran tanto tiempo y esfuerzo, mientras aumentan mi efectividad, es una locura. ¡Gracias! ¡Gracias! ¡Gracias!

Actualización2:

Decidí hacerlo más eficiente al permitirle elegir más opciones a la vez. Esto dará lugar a una pérdida aceptable de precisión en mi algoritmo, ya que es de naturaleza dinámica. De todos modos, esto es lo que tengo ahora:

 def weightedChoices(dict, sum, max, choices=10): '''an attempt to make a random.choose() function that makes weighted choices accepts a dictionary with the item_key and certainty_value as a pair like: >>> x = [('one', 20), ('two', 2), ('three', 50)], the maximum certainty value (max) and the sum of all certainties.''' list = [random.uniform(0, 1) for i in range(choices)] (n, list) = relavate(list.sort()) keys = [] sum = max*len(list)-sum for key, certainty in dict.iteritems(): weight = float(max-certainty)/sum if n < weight: keys.append(key) if list: (n, list) = relavate(list) else: break n = n - weight return keys def relavate(list): min = list[0] new = [l - min for l in list[1:]] return (min, new) 

No lo he probado todavía. Si tiene algún comentario / sugerencia, por favor no dude. ¡Gracias!

Update3:

He estado trabajando todo el día en una versión adaptada a las tareas de la respuesta de Rex Logan. En lugar de 2 matrices de objetos y pesos, en realidad es una clase de diccionario especial; lo que hace que las cosas sean bastante complejas, ya que el código de Rex genera un índice aleatorio … También codifiqué un caso de prueba que se parece a lo que sucederá en mis algoritmos (¡pero no puedo saberlo hasta que lo intente!). El principio básico es: cuanto más se genere una clave aleatoriamente, más improbable que se vuelva a generar:

 import random, time import psyco psyco.full() class ProbDict(): """ Modified version of Rex Logans RandomObject class. The more a key is randomly chosen, the more unlikely it will further be randomly chosen. """ def __init__(self,keys_weights_values={}): self._kw=keys_weights_values self._keys=self._kw.keys() self._len=len(self._keys) self._findSeniors() self._effort = 0.15 self._fails = 0 def __iter__(self): return self.next() def __getitem__(self, key): return self._kw[key] def __setitem__(self, key, value): self.append(key, value) def __len__(self): return self._len def next(self): key=self._key() while key: yield key key = self._key() def __contains__(self, key): return key in self._kw def items(self): return self._kw.items() def pop(self, key): try: (w, value) = self._kw.pop(key) self._len -=1 if w == self._seniorW: self._seniors -= 1 if not self._seniors: #costly but unlikely: self._findSeniors() return [w, value] except KeyError: return None def popitem(self): return self.pop(self._key()) def values(self): values = [] for key in self._keys: try: values.append(self._kw[key][1]) except KeyError: pass return values def weights(self): weights = [] for key in self._keys: try: weights.append(self._kw[key][0]) except KeyError: pass return weights def keys(self, imperfect=False): if imperfect: return self._keys return self._kw.keys() def append(self, key, value=None): if key not in self._kw: self._len +=1 self._kw[key] = [0, value] self._keys.append(key) else: self._kw[key][1]=value def _key(self): for i in range(int(self._effort*self._len)): ri=random.randint(0,self._len-1) #choose a random object rx=random.uniform(0,self._seniorW) rkey = self._keys[ri] try: w = self._kw[rkey][0] if rx >= w: # test to see if that is the value we want w += 1 self._warnSeniors(w) self._kw[rkey][0] = w return rkey except KeyError: self._keys.pop(ri) # if you do not find one after 100 tries then just get a random one self._fails += 1 #for confirming effectiveness only for key in self._keys: if key in self._kw: w = self._kw[key][0] + 1 self._warnSeniors(w) self._kw[key][0] = w return key return None def _findSeniors(self): '''this function finds the seniors, counts them and assess their age. It is costly but unlikely.''' seniorW = 0 seniors = 0 for w in self._kw.itervalues(): if w >= seniorW: if w == seniorW: seniors += 1 else: seniorsW = w seniors = 1 self._seniors = seniors self._seniorW = seniorW def _warnSeniors(self, w): #a weight can only be incremented...good if w >= self._seniorW: if w == self._seniorW: self._seniors+=1 else: self._seniors = 1 self._seniorW = w def test(): #test code iterations = 200000 size = 2500 nextkey = size pd = ProbDict(dict([(i,[0,i]) for i in xrange(size)])) start = time.clock() for i in xrange(iterations): key=pd._key() w=pd[key][0] if random.randint(0,1+pd._seniorW-w): #the heavier the object, the more unlikely it will be removed pd.pop(key) probAppend = float(500+(size-len(pd)))/1000 if random.uniform(0,1) < probAppend: nextkey+=1 pd.append(nextkey) print (time.clock()-start)*1000/iterations, "msecs / iteration with", pd._fails, "failures /", iterations, "iterations" weights = pd.weights() weights.sort() print "avg weight:", float(sum(weights))/pd._len, max(weights), pd._seniorW, pd._seniors, len(pd), len(weights) print weights test() 

Cualquier comentario aún es bienvenido. @Darius: tus árboles binarios son demasiado complejos y complicados para mí; y no creo que sus hojas puedan ser removidas eficientemente … Thx todo

Esta receta de estado activo ofrece un enfoque fácil de seguir, específicamente la versión en los comentarios que no requiere que preas normalice sus pesos:

 import random def weighted_choice(items): """items is a list of tuples in the form (item, weight)""" weight_total = sum((item[1] for item in items)) n = random.uniform(0, weight_total) for item, weight in items: if n < weight: return item n = n - weight return item 

Esto será lento si tiene una gran lista de artículos. Una búsqueda binaria probablemente sería mejor en ese caso ... pero también sería más complicada de escribir, con poca ganancia si tiene un tamaño de muestra pequeño. Este es un ejemplo del enfoque de búsqueda binaria en Python si desea seguir esa ruta.

(Recomendaría realizar algunas pruebas de rendimiento rápidas de ambos métodos en su conjunto de datos. El rendimiento de diferentes enfoques para este tipo de algoritmo es a menudo un poco intuitivo).


Edit: tomé mi propio consejo, ya que tenía curiosidad, e hice algunas pruebas.

Comparé cuatro enfoques:

La función weighted_choice arriba.

Una función de selección de búsqueda binaria así:

 def weighted_choice_bisect(items): added_weights = [] last_sum = 0 for item, weight in items: last_sum += weight added_weights.append(last_sum) return items[bisect.bisect(added_weights, random.random() * last_sum)][0] 

Una versión de comstackción de 1:

 def weighted_choice_compile(items): """returns a function that fetches a random item from items items is a list of tuples in the form (item, weight)""" weight_total = sum((item[1] for item in items)) def choice(uniform = random.uniform): n = uniform(0, weight_total) for item, weight in items: if n < weight: return item n = n - weight return item return choice 

Una versión de comstackción de 2:

 def weighted_choice_bisect_compile(items): """Returns a function that makes a weighted random choice from items.""" added_weights = [] last_sum = 0 for item, weight in items: last_sum += weight added_weights.append(last_sum) def choice(rnd=random.random, bis=bisect.bisect): return items[bis(added_weights, rnd() * last_sum)][0] return choice 

Entonces construí una gran lista de opciones así:

 choices = [(random.choice("abcdefg"), random.uniform(0,50)) for i in xrange(2500)] 

Y una función de perfilado excesivamente simple:

 def profiler(f, n, *args, **kwargs): start = time.time() for i in xrange(n): f(*args, **kwargs) return time.time() - start 

Los resultados:

(Segundos tomados para 1,000 llamadas a la función).

  • Simple sin comstackr: 0.918624162674
  • Binario sin comstackr: 1.01497793198
  • Simple comstackdo: 0.287325024605
  • Binario comstackdo: 0.00327413797379

Los resultados "comstackdos" incluyen el tiempo promedio empleado para comstackr la función de selección una vez. (Programé 1,000 comstackciones, luego dividí ese tiempo por 1,000 y agregué el resultado al tiempo de la función de elección).

Entonces: si tiene una lista de elementos + pesos que cambian muy raramente, el método binario comstackdo es, con mucho, el más rápido.

En comentarios sobre la publicación original, Nicholas Leonard sugiere que tanto el intercambio como el muestreo deben ser rápidos. Aquí hay una idea para ese caso; No lo he probado.

Si solo el muestreo tuviera que ser rápido, podríamos usar una matriz de los valores junto con la sum de sus probabilidades, y hacer una búsqueda binaria sobre la sum de ejecución (siendo la clave un número aleatorio uniforme) – una O (log ( n)) funcionamiento. Pero un intercambio requeriría actualizar todos los valores de la sum stream que aparecen después de las entradas intercambiadas, una operación O (n). (¿Podría elegir intercambiar solo artículos cerca del final de sus listas? Asumiré que no.)

Así que vamos a apuntar a O (log (n)) en ambas operaciones. En lugar de una matriz, mantenga un árbol binario para cada conjunto de muestra. Una hoja contiene el valor de la muestra y su probabilidad (no normalizada). Un nodo de twig tiene la probabilidad total de sus hijos.

Para muestrear, genere un número aleatorio uniforme x entre 0 y la probabilidad total de la raíz, y descienda el árbol. En cada twig, elija el niño izquierdo si el niño izquierdo tiene una probabilidad total <= x . De lo contrario, reste la probabilidad del niño izquierdo de x y vaya a la derecha. Devuelve el valor de la hoja que scopes.

Para intercambiar, retire la hoja de su árbol y ajuste las twigs que conducen a ella (disminuyendo su probabilidad total, y eliminando los nodos de twig de un solo hijo). Inserte la hoja en el árbol de destino: puede elegir dónde colocarla, así que manténgala en equilibrio. Elegir a un niño al azar en cada nivel es probablemente lo suficientemente bueno, ahí es donde empezaría. Aumente la probabilidad de cada nodo padre, retroceda a la raíz.

Ahora tanto el muestreo como el intercambio son O (log (n)) en promedio. (Si necesita un equilibrio garantizado, una forma sencilla es agregar otro campo a los nodos de la twig que tienen el recuento de hojas en todo el subárbol. Al agregar una hoja, en cada nivel, seleccione al niño con menos hojas. Esto deja la posibilidad de un el árbol se desequilibra únicamente por las eliminaciones; esto no puede ser un problema si hay un tráfico razonablemente uniforme entre los conjuntos, pero si lo está, seleccione rotaciones durante la eliminación utilizando la información de recuento de hojas en cada nodo en su recorrido.)

Actualización: A petición, aquí hay una implementación básica. No lo he sintonizado en absoluto. Uso:

 >>> t1 = build_tree([('one', 20), ('two', 2), ('three', 50)]) >>> t1 Branch(Leaf(20, 'one'), Branch(Leaf(2, 'two'), Leaf(50, 'three'))) >>> t1.sample() Leaf(50, 'three') >>> t1.sample() Leaf(20, 'one') >>> t2 = build_tree([('four', 10), ('five', 30)]) >>> t1a, t2a = transfer(t1, t2) >>> t1a Branch(Leaf(20, 'one'), Leaf(2, 'two')) >>> t2a Branch(Leaf(10, 'four'), Branch(Leaf(30, 'five'), Leaf(50, 'three'))) 

Código:

 import random def build_tree(pairs): tree = Empty() for value, weight in pairs: tree = tree.add(Leaf(weight, value)) return tree def transfer(from_tree, to_tree): """Given a nonempty tree and a target, move a leaf from the former to the latter. Return the two updated trees.""" leaf, from_tree1 = from_tree.extract() return from_tree1, to_tree.add(leaf) class Tree: def add(self, leaf): "Return a new tree holding my leaves plus the given leaf." abstract def sample(self): "Pick one of my leaves at random in proportion to its weight." return self.sampling(random.uniform(0, self.weight)) def extract(self): """Pick one of my leaves and return it along with a new tree holding my leaves minus that one leaf.""" return self.extracting(random.uniform(0, self.weight)) class Empty(Tree): weight = 0 def __repr__(self): return 'Empty()' def add(self, leaf): return leaf def sampling(self, weight): raise Exception("You can't sample an empty tree") def extracting(self, weight): raise Exception("You can't extract from an empty tree") class Leaf(Tree): def __init__(self, weight, value): self.weight = weight self.value = value def __repr__(self): return 'Leaf(%r, %r)' % (self.weight, self.value) def add(self, leaf): return Branch(self, leaf) def sampling(self, weight): return self def extracting(self, weight): return self, Empty() def combine(left, right): if isinstance(left, Empty): return right if isinstance(right, Empty): return left return Branch(left, right) class Branch(Tree): def __init__(self, left, right): self.weight = left.weight + right.weight self.left = left self.right = right def __repr__(self): return 'Branch(%r, %r)' % (self.left, self.right) def add(self, leaf): # Adding to a random branch as a clumsy way to keep an # approximately balanced tree. if random.random() < 0.5: return combine(self.left.add(leaf), self.right) return combine(self.left, self.right.add(leaf)) def sampling(self, weight): if weight < self.left.weight: return self.left.sampling(weight) return self.right.sampling(weight - self.left.weight) def extracting(self, weight): if weight < self.left.weight: leaf, left1 = self.left.extracting(weight) return leaf, combine(left1, self.right) leaf, right1 = self.right.extracting(weight - self.left.weight) return leaf, combine(self.left, right1) 

Actualización 2: Al responder a otro problema , Jason Orendorff señala que los árboles binarios se pueden mantener perfectamente equilibrados representándolos en una matriz, al igual que la estructura de stack clásica. (Esto también ahorra el espacio dedicado a los punteros). Vea mis comentarios a esa respuesta sobre cómo adaptar su código a este problema.

Le sugiero que transfiera esta implementación de PHP ponderada aleatoriamente a Python. En particular, el segundo algoritmo basado en la búsqueda binaria ayuda a resolver sus problemas de velocidad.

Yo usaría esta receta . Deberá agregar un peso a sus objetos, pero eso es solo una proporción simple y colocarlos en una lista de tuplas (objeto, convicción / (sum de convicciones)). Esto debería ser fácil de hacer usando una lista de comprensión.

Aquí hay una forma clásica de hacerlo, en pseudocódigo, donde random.random () le da un flotante aleatorio de 0 a 1.

 let z = sum of all the convictions let choice = random.random() * z iterate through your objects: choice = choice - the current object's conviction if choice <= 0, return this object return the last object 

Por ejemplo, imagina que tienes dos objetos, uno con peso 2 y otro con peso 4. Generas un número de 0 a 6. Si la choice está entre 0 y 2, lo que ocurrirá con 2/6 = 1/3 de probabilidad, luego se restará por 2 y se elegirá el primer objeto. Si la elección es entre 2 y 6, lo que sucederá con 4/6 = 2/3 de probabilidad, entonces la primera resta seguirá teniendo la opción siendo> 0, y la segunda resta hará que el segundo objeto sea elegido.

Quieres darle un peso a cada objeto. Cuanto mayor sea el peso, más probable será que suceda. Más precisamente probx = weight / sum_all_weights.

Luego genere un número aleatorio en el rango de 0 para sum_all_weights y asigne a cada objeto.

Este código le permite generar un índice aleatorio y se asigna cuando el objeto se crea para la velocidad. Si todos sus conjuntos de objetos tienen la misma distribución, entonces puede sobrevivir con solo un objeto RandomIndex.

 import random class RandomIndex: def __init__(self, wlist): self._wi=[] self._rsize=sum(wlist)-1 self._m={} i=0 s=wlist[i] for n in range(self._rsize+1): if n == s: i+=1 s+=wlist[i] self._m[n]=i def i(self): rn=random.randint(0,self._rsize) return self._m[rn] sx=[1,2,3,4] wx=[1,10,100,1000] #weight list ri=RandomIndex(wx) cnt=[0,0,0,0] for i in range(1000): cnt[ri.i()] +=1 #keep track of number of times each index was generated print(cnt) 

Unos 3 años después …

Si usa numpy, quizás la opción más simple es usar np.random.choice , que toma una lista de valores posibles, y una secuencia opcional de probabilidades asociadas con cada valor:

 import numpy as np values = ('A', 'B', 'C', 'D') weights = (0.5, 0.1, 0.2, 0.2) print ''.join(np.random.choice(values, size=60, replace=True, p=weights)) # ACCADAACCDACDBACCADCAAAAAAADACCDCAADDDADAAACCAAACBAAADCADABA 

Lo más sencillo es usar random.choice (que usa una distribución uniforme) y variar la frecuencia de ocurrencia en el objeto en la colección de origen.

 >>> random.choice([1, 2, 3, 4]) 4 

… vs

 >>> random.choice([1, 1, 1, 1, 2, 2, 2, 3, 3, 4]) 2 

Por lo tanto, sus objetos podrían tener una tasa de ocurrencia básica (n) y entre 1 y n objetos se agregarán a la colección de origen en función de la tasa de convicción. Este método es realmente simple; sin embargo, puede tener una sobrecarga significativa si el número de objetos distintos es grande o la tasa de convicción debe ser muy detallada.

Alternativamente, si genera más de un número aleatorio utilizando una distribución uniforme y los sum, los números que se producen cerca de la media son más probables que los que ocurren cerca de los extremos (piense en tirar dos dados y la probabilidad de obtener 7 en lugar de 12 o 2). Luego, puede ordenar los objetos por tasa de convicción y generar un número utilizando múltiples tiradas de troqueles que utiliza para calcular e indexar en los objetos. Use números cerca de la media para indexar objetos de baja convicción y números cerca de los extremos para indexar artículos de alta convicción. Puede variar la probabilidad precisa de que se seleccione un objeto dado cambiando el “número de lados” y el número de sus “dados” (puede ser más sencillo colocar los objetos en cubos y usar dados con un número pequeño de lados en lugar de tratando de asociar cada objeto con un resultado específico):

 >>> die = lambda sides : random.randint(1, sides) >>> die(6) 3 >>> die(6) + die(6) + die(6) 10 

Una forma muy fácil y sencilla de hacer esto es establecer ponderaciones para cada uno de los valores, y no requeriría mucha memoria.

Probablemente podrías usar un hash / diccionario para hacer esto.

Lo que querrás hacer es tener el número aleatorio, x , multiplicado y sumdo en todo el conjunto de cosas que deseas seleccionar, y dividir ese resultado entre la cantidad de objetos en tu conjunto.

Pseudo-código:

 objectSet = [(object1, weight1), ..., (objectN, weightN)] sum = 0 rand = random() for obj, weight in objectSet sum = sum+weight*rand choice = objectSet[floor(sum/objectSet.size())] 

EDITAR : acabo de pensar en lo lento que sería mi código con conjuntos muy grandes (es O (n)). El siguiente pseudocódigo es O (log (n)), y básicamente utiliza una búsqueda binaria.

 objectSet = [(object1, weight1), ..., (objectN, weightN)] sort objectSet from less to greater according to weights choice = random() * N # where N is the number of objects in objectSet do a binary search until you have just one answer 

Hay implementaciones de búsqueda binaria en Python en toda la red, por lo que no es necesario repetirlas aquí.

Aquí hay una mejor respuesta para una distribución de probabilidad especial, la respuesta de Rex Logan parece estar orientada. La distribución es así: cada objeto tiene un peso entero entre 0 y 100, y su probabilidad es proporcional a su peso. Ya que esa es la respuesta actualmente aceptada, creo que vale la pena pensarlo.

Así que mantén un conjunto de 101 contenedores. Cada bandeja contiene una lista de todos los objetos con su peso particular. Cada contenedor también conoce el peso total de todos sus objetos.

Para muestrear: elija un recipiente al azar en proporción a su peso total. (Utilice una de las recetas estándar para esto: búsqueda lineal o binaria). Luego, elija un objeto del contenedor de manera uniforme y al azar.

Para transferir un objeto: retírelo de su bandeja, colóquelo en su bandeja en el objective y actualice los pesos de ambas bandejas. (Si está utilizando la búsqueda binaria para el muestreo, también debe actualizar las sums streams que utiliza. Esto sigue siendo razonablemente rápido ya que no hay muchos contenedores).

(Un año después) El método de alias de Walker para objetos aleatorios con diferentes probabilidades es muy rápido y muy simple

Me necesitaban en funciones más rápidas, para números no muy grandes. Así que aquí está, en Visual C ++:

 #undef _DEBUG // disable linking with python25_d.dll #include  #include  #include  static PyObject* dieroll(PyObject *, PyObject *args) { PyObject *list; if (!PyArg_ParseTuple(args, "O:decompress", &list)) return NULL; if (!PyList_Check(list)) return PyErr_Format(PyExc_TypeError, "list of numbers expected ('%s' given)", list->ob_type->tp_name), NULL; int size = PyList_Size(list); if (size < 1) return PyErr_Format(PyExc_TypeError, "got empty list"), NULL; long *array = (long*)alloca(size*sizeof(long)); long sum = 0; for (int i = 0; i < size; i++) { PyObject *o = PyList_GetItem(list, i); if (!PyInt_Check(o)) return PyErr_Format(PyExc_TypeError, "list of ints expected ('%s' found)", o->ob_type->tp_name), NULL; long n = PyInt_AsLong(o); if (n == -1 && PyErr_Occurred()) return NULL; if (n < 0) return PyErr_Format(PyExc_TypeError, "list of positive ints expected (negative found)"), NULL; sum += n; //NOTE: integer overflow array[i] = sum; } if (sum <= 0) return PyErr_Format(PyExc_TypeError, "sum of numbers is not positive"), NULL; int r = rand() * (sum-1) / RAND_MAX; //NOTE: rand() may be too small (0x7fff). rand() * sum may result in integer overlow. assert(array[size-1] == sum); assert(r < sum && r < array[size-1]); for (int i = 0; i < size; ++i) { if (r < array[i]) return PyInt_FromLong(i); } return PyErr_Format(PyExc_TypeError, "internal error."), NULL; } static PyMethodDef module_methods[] = { {"dieroll", (PyCFunction)dieroll, METH_VARARGS, "random index, beased on weights" }, {NULL} /* Sentinel */ }; PyMODINIT_FUNC initdieroll(void) { PyObject *module = Py_InitModule3("dieroll", module_methods, "dieroll"); if (module == NULL) return; }