Seleccione k elementos aleatorios de una lista cuyos elementos tienen pesos

La selección sin pesos (probabilidades iguales) está bellamente descrita aquí .

Me preguntaba si hay una manera de convertir este enfoque en uno ponderado.

También estoy interesado en otros enfoques también.

Actualización: muestreo sin reemplazo

Sé que esta es una pregunta muy antigua, pero creo que hay un buen truco para hacerlo en O (n) tiempo si aplica un poco de matemáticas.

La distribución exponencial tiene dos propiedades muy útiles.

  1. Dadas n muestras de diferentes distribuciones exponenciales con diferentes parámetros de velocidad, la probabilidad de que una muestra dada sea el mínimo es igual a su parámetro de velocidad dividido por la sum de todos los parámetros de velocidad.

  2. Es “sin memoria”. Entonces, si ya conoce el mínimo, entonces la probabilidad de que cualquiera de los elementos restantes sea de 2 ° a min es la misma que la probabilidad de que si se eliminaba el min verdadero (y nunca se generaba), ese elemento sería el nuevo min. Esto parece obvio, pero creo que debido a algunos problemas de probabilidad condicional, podría no ser cierto para otras distribuciones.

Usando el hecho 1, sabemos que la elección de un solo elemento se puede hacer generando estas muestras de distribución exponencial con un parámetro de velocidad igual al peso, y luego eligiendo el que tenga un valor mínimo.

Usando el hecho 2, sabemos que no tenemos que volver a generar las muestras exponenciales. En su lugar, solo genere uno para cada elemento y tome los elementos k con las muestras más bajas.

Encontrar la k más baja se puede hacer en O (n). Use el algoritmo Quickselect para encontrar el elemento k-ésimo, luego simplemente tome otro pase a través de todos los elementos y dé como resultado un valor inferior al k-ésimo.

Una nota útil: si no tiene acceso inmediato a una biblioteca para generar muestras de distribución exponencial, puede hacerlo fácilmente: -ln(rand())/weight

Si el muestreo es con reemplazo, puede usar este algoritmo (implementado aquí en Python):

 import random items = [(10, "low"), (100, "mid"), (890, "large")] def weighted_sample(items, n): total = float(sum(w for w, v in items)) i = 0 w, v = items[0] while n: x = total * (1 - random.random() ** (1.0 / n)) total -= x while x > w: x -= w i += 1 w, v = items[i] w -= x yield v n -= 1 

Esto es O ( n + m ) donde m es el número de elementos.

¿Por qué funciona esto? Se basa en el siguiente algoritmo:

 def n_random_numbers_decreasing(v, n): """Like reversed(sorted(v * random() for i in range(n))), but faster because we avoid sorting.""" while n: v *= random.random() ** (1.0 / n) yield v n -= 1 

La función weighted_sample es solo este algoritmo fusionado con un recorrido de la lista de items para seleccionar los elementos seleccionados por esos números aleatorios.

Esto a su vez funciona porque la probabilidad de que n números aleatorios 0 .. v todos sean menores que z es P = ( z / v ) n . Resuelve para z , y obtienes z = vP 1 / n . Sustituyendo un número aleatorio para P elige el número más grande con la distribución correcta; y podemos simplemente repetir el proceso para seleccionar todos los otros números.

Si el muestreo no tiene reemplazo, puede colocar todos los elementos en un montón binario, donde cada nodo almacena en caché el total de los pesos de todos los elementos en ese subheap. La construcción del montón es O ( m ). Seleccionar un elemento aleatorio del montón, respetando los pesos, es O (log m ). La eliminación de ese elemento y la actualización de los totales en caché también es O (log m ). Entonces puede elegir n elementos en el tiempo O ( m + n log m ).

(Nota: “peso” significa que cada vez que se selecciona un elemento, las posibilidades restantes se eligen con una probabilidad proporcional a sus ponderaciones. No significa que los elementos aparecen en el resultado con una probabilidad proporcional a sus ponderaciones).

Aquí hay una implementación de eso, abundantemente comentada:

 import random class Node: # Each node in the heap has a weight, value, and total weight. # The total weight, self.tw, is self.w plus the weight of any children. __slots__ = ['w', 'v', 'tw'] def __init__(self, w, v, tw): self.w, self.v, self.tw = w, v, tw def rws_heap(items): # h is the heap. It's like a binary tree that lives in an array. # It has a Node for each pair in `items`. h[1] is the root. Each # other Node h[i] has a parent at h[i>>1]. Each node has up to 2 # children, h[i< <1] and h[(i<<1)+1]. To get this nice simple # arithmetic, we have to leave h[0] vacant. h = [None] # leave h[0] vacant for w, v in items: h.append(Node(w, v, w)) for i in range(len(h) - 1, 1, -1): # total up the tws h[i>>1].tw += h[i].tw # add h[i]'s total to its parent return h def rws_heap_pop(h): gas = h[1].tw * random.random() # start with a random amount of gas i = 1 # start driving at the root while gas >= h[i].w: # while we have enough gas to get past node i: gas -= h[i].w # drive past node i i < <= 1 # move to first child if gas >= h[i].tw: # if we have enough gas: gas -= h[i].tw # drive past first child and descendants i += 1 # move to second child w = h[i].w # out of gas! h[i] is the selected node. v = h[i].v h[i].w = 0 # make sure this node isn't chosen again while i: # fix up total weights h[i].tw -= w i >>= 1 return v def random_weighted_sample_no_replacement(items, n): heap = rws_heap(items) # just make a heap... for i in range(n): yield rws_heap_pop(heap) # and pop n items off it. 

Si el muestreo es con reemplazo, use la técnica de selección de rueda de ruleta (a menudo utilizada en algoritmos genéticos):

  1. ordenar los pesos
  2. calcular los pesos acumulados
  3. elige un número al azar en [0,1]*totalWeight
  4. encuentre el intervalo en el cual este número cae
  5. selecciona los elementos con el intervalo correspondiente
  6. repetir k veces

texto alternativo

Si el muestreo no tiene reemplazo, puede adaptar la técnica anterior eliminando el elemento seleccionado de la lista después de cada iteración, luego re-normalizando los pesos para que su sum sea 1 (función de distribución de probabilidad válida)

He hecho esto en Ruby

https://github.com/fl00r/pickup

 require 'pickup' pond = { "selmon" => 1, "carp" => 4, "crucian" => 3, "herring" => 6, "sturgeon" => 8, "gudgeon" => 10, "minnow" => 20 } pickup = Pickup.new(pond, uniq: true) pickup.pick(3) #=> [ "gudgeon", "herring", "minnow" ] pickup.pick #=> "herring" pickup.pick #=> "gudgeon" pickup.pick #=> "sturgeon" 

Si desea generar grandes matrices de enteros aleatorios con reemplazo , puede usar la interpolación lineal por partes. Por ejemplo, usando NumPy / SciPy:

 import numpy import scipy.interpolate def weighted_randint(weights, size=None): """Given an n-element vector of weights, randomly sample integers up to n with probabilities proportional to weights""" n = weights.size # normalize so that the weights sum to unity weights = weights / numpy.linalg.norm(weights, 1) # cumulative sum of weights cumulative_weights = weights.cumsum() # piecewise-linear interpolating function whose domain is # the unit interval and whose range is the integers up to n f = scipy.interpolate.interp1d( numpy.hstack((0.0, weights)), numpy.arange(n + 1), kind='linear') return f(numpy.random.random(size=size)).astype(int) 

Esto no es efectivo si quiere muestrear sin reemplazo.

Aquí hay una implementación de Go de geodns :

 package foo import ( "log" "math/rand" ) type server struct { Weight int data interface{} } func foo(servers []server) { // servers list is already sorted by the Weight attribute // number of items to pick max := 4 result := make([]server, max) sum := 0 for _, r := range servers { sum += r.Weight } for si := 0; si < max; si++ { n := rand.Intn(sum + 1) s := 0 for i := range servers { s += int(servers[i].Weight) if s >= n { log.Println("Picked record", i, servers[i]) sum -= servers[i].Weight result[si] = servers[i] // remove the server from the list servers = append(servers[:i], servers[i+1:]...) break } } } return result } 

Si desea elegir x elementos de un conjunto ponderado sin reemplazo, de modo que los elementos se elijan con una probabilidad proporcional a sus ponderaciones:

 import random def weighted_choose_subset(weighted_set, count): """Return a random sample of count elements from a weighted set. weighted_set should be a sequence of tuples of the form (item, weight), for example: [('a', 1), ('b', 2), ('c', 3)] Each element from weighted_set shows up at most once in the result, and the relative likelihood of two particular elements showing up is equal to the ratio of their weights. This works as follows: 1.) Line up the items along the number line from [0, the sum of all weights) such that each item occupies a segment of length equal to its weight. 2.) Randomly pick a number "start" in the range [0, total weight / count). 3.) Find all the points "start + n/count" (for all integers n such that the point is within our segments) and yield the set containing the items marked by those points. Note that this implementation may not return each possible subset. For example, with the input ([('a': 1), ('b': 1), ('c': 1), ('d': 1)], 2), it may only produce the sets ['a', 'c'] and ['b', 'd'], but it will do so such that the weights are respected. This implementation only works for nonnegative integral weights. The highest weight in the input set must be less than the total weight divided by the count; otherwise it would be impossible to respect the weights while never returning that element more than once per invocation. """ if count == 0: return [] total_weight = 0 max_weight = 0 borders = [] for item, weight in weighted_set: if weight < 0: raise RuntimeError("All weights must be positive integers") # Scale up weights so dividing total_weight / count doesn't truncate: weight *= count total_weight += weight borders.append(total_weight) max_weight = max(max_weight, weight) step = int(total_weight / count) if max_weight > step: raise RuntimeError( "Each weight must be less than total weight / count") next_stop = random.randint(0, step - 1) results = [] current = 0 for i in range(count): while borders[current] < = next_stop: current += 1 results.append(weighted_set[current][0]) next_stop += step return results 

En la pregunta a la que se vinculó, la solución de Kyle funcionaría con una generalización trivial. Escanee la lista y sume los pesos totales. Entonces la probabilidad de elegir un elemento debería ser:

1 – (1 – (# necesario / (peso a la izquierda))) / (peso en n). Después de visitar un nodo, reste su peso del total. Además, si necesita ny tiene n izquierda, debe detenerse explícitamente.

Puedes verificar que con todo teniendo peso 1, esto se simplifica a la solución de Kyle.

Editado: (tuvo que replantearse qué significaba el doble de posibilidades)

Esto hace exactamente eso con O (n) y sin uso de memoria en exceso. Creo que esta es una solución inteligente y eficiente fácil de transportar a cualquier idioma. Las primeras dos líneas son solo para completar los datos de muestra en Drupal.

 function getNrandomGuysWithWeight($numitems){ $q = db_query('SELECT id, weight FROM theTableWithTheData'); $q = $q->fetchAll(); $accum = 0; foreach($q as $r){ $accum += $r->weight; $r->weight = $accum; } $out = array(); while(count($out) < $numitems && count($q)){ $n = rand(0,$accum); $lessaccum = NULL; $prevaccum = 0; $idxrm = 0; foreach($q as $i=>$r){ if(($lessaccum == NULL) && ($n < = $r->weight)){ $out[] = $r->id; $lessaccum = $r->weight- $prevaccum; $accum -= $lessaccum; $idxrm = $i; }else if($lessaccum){ $r->weight -= $lessaccum; } $prevaccum = $r->weight; } unset($q[$idxrm]); } return $out; } 

Al presentar aquí una solución simple para escoger 1 artículo, puedes expandirlo fácilmente para k artículos (estilo Java):

 double random = Math.random(); double sum = 0; for (int i = 0; i < items.length; i++) { val = items[i]; sum += val.getValue(); if (sum > random) { selected = val; break; } } 

He implementado un algoritmo similar a la idea de Jason Orendorff en Rust aquí . Mi versión también admite operaciones masivas: inserte y elimine (cuando desee eliminar un grupo de elementos dados por sus identificadores, no a través de la ruta de selección ponderada) de la estructura de datos en O(m + log n) tiempo donde m es el número de elementos para eliminar yn la cantidad de elementos almacenados.

Muestreo sin reemplazo con recursión: solución elegante y muy corta en c #

// cuántas formas podemos elegir 4 de 60 estudiantes, para que cada vez que elijamos diferentes 4

 class Program { static void Main(string[] args) { int group = 60; int studentsToChoose = 4; Console.WriteLine(FindNumberOfStudents(studentsToChoose, group)); } private static int FindNumberOfStudents(int studentsToChoose, int group) { if (studentsToChoose == group || studentsToChoose == 0) return 1; return FindNumberOfStudents(studentsToChoose, group - 1) + FindNumberOfStudents(studentsToChoose - 1, group - 1); } } 

Usé un mapa asociativo (peso, objeto). por ejemplo:

 { (10,"low"), (100,"mid"), (10000,"large") } total=10110 

busque un número aleatorio entre 0 y ‘total’ e itere sobre las teclas hasta que este número encaje en un rango determinado.