Selección basada en porcentaje de ponderación.

Tengo un conjunto de valores, y un porcentaje asociado para cada uno:

a: 70% de probabilidad
b: 20% de probabilidad
c: 10% de probabilidad

Quiero seleccionar un valor (a, b, c) en función del porcentaje de oportunidad dado.

¿Cómo me acerco a esto?

mi bash hasta ahora se parece a esto:

r = random.random() if r <= .7: return a elif r <= .9: return b else: return c 

Estoy atascado con un algoritmo para manejar esto. ¿Cómo debo abordar esto para que pueda manejar grandes conjuntos de valores sin solo encadenar flujos if-else?

(cualquier explicación o respuesta en pseudocódigo está bien. una implementación en Python o C # sería especialmente útil)

Aquí hay una solución completa en C #:

 public class ProportionValue { public double Proportion { get; set; } public T Value { get; set; } } public static class ProportionValue { public static ProportionValue Create(double proportion, T value) { return new ProportionValue { Proportion = proportion, Value = value }; } static Random random = new Random(); public static T ChooseByRandom( this IEnumerable> collection) { var rnd = random.NextDouble(); foreach (var item in collection) { if (rnd < item.Proportion) return item.Value; rnd -= item.Proportion; } throw new InvalidOperationException( "The proportions in the collection do not add up to 1."); } } 

Uso:

 var list = new[] { ProportionValue.Create(0.7, "a"), ProportionValue.Create(0.2, "b"), ProportionValue.Create(0.1, "c") }; // Outputs "a" with probability 0.7, etc. Console.WriteLine(list.ChooseByRandom()); 

Para Python:

 >>> import random >>> dst = 70, 20, 10 >>> vls = 'a', 'b', 'c' >>> picks = [v for v, d in zip(vls, dst) for _ in range(d)] >>> for _ in range(12): print random.choice(picks), ... accbaaaaaaaa >>> for _ in range(12): print random.choice(picks), ... acacabbbaaaa >>> for _ in range(12): print random.choice(picks), ... aaaaccacaaca >>> 

Idea general: haga una lista en la que cada elemento se repita una cantidad de veces proporcional a la probabilidad que debería tener; use random.choice para elegir uno al azar (uniformemente), esto coincidirá con su distribución de probabilidad requerida. Puede ser un poco desperdicio de memoria si sus probabilidades se expresan de maneras peculiares (por ejemplo, 70, 20, 10 hace una lista de 100 elementos donde 7, 2, 1 haría una lista de solo 10 elementos con exactamente el mismo comportamiento), pero podría dividir todos los conteos en la lista de probabilidades por su mayor factor común si cree que es probable que sea un gran problema en el escenario de su aplicación específica.

Aparte de los problemas de consumo de memoria, esta debería ser la solución más rápida: solo una generación de números aleatorios por resultado de salida requerido, y la búsqueda más rápida posible desde ese número aleatorio, sin comparaciones & c. Si sus probabilidades probables son muy extrañas (por ejemplo, los números de punto flotante que deben coincidir con muchos, muchos dígitos significativos), pueden ser preferibles otros enfoques ;-).

Knuth hace referencia al método de alias de Walker. Buscando en esto, encuentro http://code.activestate.com/recipes/576564-walkers-alias-method-for-random-objects-with-diffe/ y http://prxq.wordpress.com/2006/04 / 17 / el-alias-método / . Esto da las probabilidades exactas requeridas en tiempo constante por número generado con tiempo lineal para la configuración (curiosamente, n log n tiempo para la configuración si usa exactamente el método que describe Knuth, que hace una clasificación preparatoria que puede evitar).

Tome la lista de y encuentre el total acumulado de los pesos: 70, 70 + 20, 70 + 20 + 10. Elija un número aleatorio mayor o igual a cero y menor que el total. Iterar sobre los elementos y devolver el primer valor para el cual la sum acumulada de los pesos es mayor que este número aleatorio:

 def select( values ): variate = random.random() * sum( values.values() ) cumulative = 0.0 for item, weight in values.items(): cumulative += weight if variate < cumulative: return item return item # Shouldn't get here, but just in case of rounding... print select( { "a": 70, "b": 20, "c": 10 } ) 

Esta solución, como se implementó, también debería ser capaz de manejar pesos fraccionados y pesos que se sumn a cualquier número, siempre y cuando no sean negativos.

  1. Sea T = la sum de todos los pesos de los artículos
  2. Sea R = un número aleatorio entre 0 y T
  3. Iterar la lista de elementos restando cada peso de artículo de R y devolver el elemento que hace que el resultado se convierta en <= 0.
 def weighted_choice(probabilities): random_position = random.random() * sum(probabilities) current_position = 0.0 for i, p in enumerate(probabilities): current_position += p if random_position < current_position: return i return None 

Debido a que random.random siempre devolverá <1.0, nunca se debe alcanzar la return final.

 import random def selector(weights): i=random.random()*sum(x for x,y in weights) for w,v in weights: if w>=i: break i-=w return v weights = ((70,'a'),(20,'b'),(10,'c')) print [selector(weights) for x in range(10)] 

Funciona igual de bien para pesos fraccionarios

 weights = ((0.7,'a'),(0.2,'b'),(0.1,'c')) print [selector(weights) for x in range(10)] 

Si tiene muchos pesos, puede usar bisect para reducir el número de iteraciones requeridas

 import random import bisect def make_acc_weights(weights): acc=0 acc_weights = [] for w,v in weights: acc+=w acc_weights.append((acc,v)) return acc_weights def selector(acc_weights): i=random.random()*sum(x for x,y in weights) return weights[bisect.bisect(acc_weights, (i,))][1] weights = ((70,'a'),(20,'b'),(10,'c')) acc_weights = make_acc_weights(weights) print [selector(acc_weights) for x in range(100)] 

También funciona bien para pesos fraccionarios.

 weights = ((0.7,'a'),(0.2,'b'),(0.1,'c')) acc_weights = make_acc_weights(weights) print [selector(acc_weights) for x in range(100)] 

hoy, la actualización del documento de Python da un ejemplo para hacer un random.choice () con probabilidades ponderadas:

Si los pesos son proporciones de enteros pequeños, una técnica simple es construir una población de muestra con repeticiones:

 >>> weighted_choices = [('Red', 3), ('Blue', 2), ('Yellow', 1), ('Green', 4)] >>> population = [val for val, cnt in weighted_choices for i in range(cnt)] >>> random.choice(population) 'Green' 

Un enfoque más general es organizar los pesos en una distribución acumulativa con itertools.accumulate (), y luego ubicar el valor aleatorio con bisect.bisect ():

 >>> choices, weights = zip(*weighted_choices) >>> cumdist = list(itertools.accumulate(weights)) >>> x = random.random() * cumdist[-1] >>> choices[bisect.bisect(cumdist, x)] 'Blue' 

una nota: itertools.accumulate () necesita python 3.2 o lo define con el Equivalente.

Creo que puedes tener una gran variedad de objetos pequeños (implementé en Java aunque sé un poco de C #, pero me temo que puede escribir código incorrecto), por lo que es posible que debas portarlo tú mismo. El código en C # será mucho más pequeño con struct, var, pero espero que tengas la idea

 class PercentString { double percent; String value; // Constructor for 2 values } ArrayList list = new ArrayList 

Tengo mi propia solución para esto:

 public class Randomizator3000 { public class Item { public T value; public float weight; public static float GetTotalWeight(Item[] p_itens) { float __toReturn = 0; foreach(var item in p_itens) { __toReturn += item.weight; } return __toReturn; } } private static System.Random _randHolder; private static System.Random _random { get { if(_randHolder == null) _randHolder = new System.Random(); return _randHolder; } } public static T PickOne(Item[] p_itens) { if(p_itens == null || p_itens.Length == 0) { return default(T); } float __randomizedValue = (float)_random.NextDouble() * (Item.GetTotalWeight(p_itens)); float __adding = 0; for(int i = 0; i < p_itens.Length; i ++) { float __cacheValue = p_itens[i].weight + __adding; if(__randomizedValue <= __cacheValue) { return p_itens[i].value; } __adding = __cacheValue; } return p_itens[p_itens.Length - 1].value; } } 

Y usarlo debería ser algo así (eso es en Unity3d)

 using UnityEngine; using System.Collections; public class teste : MonoBehaviour { Randomizator3000.Item[] lista; void Start() { lista = new Randomizator3000.Item[10]; lista[0] = new Randomizator3000.Item(); lista[0].weight = 10; lista[0].value = "a"; lista[1] = new Randomizator3000.Item(); lista[1].weight = 10; lista[1].value = "b"; lista[2] = new Randomizator3000.Item(); lista[2].weight = 10; lista[2].value = "c"; lista[3] = new Randomizator3000.Item(); lista[3].weight = 10; lista[3].value = "d"; lista[4] = new Randomizator3000.Item(); lista[4].weight = 10; lista[4].value = "e"; lista[5] = new Randomizator3000.Item(); lista[5].weight = 10; lista[5].value = "f"; lista[6] = new Randomizator3000.Item(); lista[6].weight = 10; lista[6].value = "g"; lista[7] = new Randomizator3000.Item(); lista[7].weight = 10; lista[7].value = "h"; lista[8] = new Randomizator3000.Item(); lista[8].weight = 10; lista[8].value = "i"; lista[9] = new Randomizator3000.Item(); lista[9].weight = 10; lista[9].value = "j"; } void Update () { Debug.Log(Randomizator3000.PickOne(lista)); } } 

En este ejemplo, cada valor tiene un 10% de probabilidad de mostrarse como una depuración = 3

Si está realmente preparado y desea generar los valores aleatorios rápidamente, el algoritmo de Walker mcdowella mencionado en https://stackoverflow.com/a/3655773/1212517 es prácticamente la mejor manera de hacerlo (O (1) tiempo para tiempo aleatorio () y O (N) para preprocess ()).

Para cualquiera que esté interesado, aquí está mi propia implementación de PHP del algoritmo:

 /** * Pre-process the samples (Walker's alias method). * @param array key represents the sample, value is the weight */ protected function preprocess($weights){ $N = count($weights); $sum = array_sum($weights); $avg = $sum / (double)$N; //divide the array of weights to values smaller and geq than sum/N $smaller = array_filter($weights, function($itm) use ($avg){ return $avg > $itm;}); $sN = count($smaller); $greater_eq = array_filter($weights, function($itm) use ($avg){ return $avg <= $itm;}); $gN = count($greater_eq); $bin = array(); //bins //we want to fill N bins for($i = 0;$i<$N;$i++){ //At first, decide for a first value in this bin //if there are small intervals left, we choose one if($sN > 0){ $choice1 = each($smaller); unset($smaller[$choice1['key']]); $sN--; } else{ //otherwise, we split a large interval $choice1 = each($greater_eq); unset($greater_eq[$choice1['key']]); } //splitting happens here - the unused part of interval is thrown back to the array if($choice1['value'] >= $avg){ if($choice1['value'] - $avg >= $avg){ $greater_eq[$choice1['key']] = $choice1['value'] - $avg; }else if($choice1['value'] - $avg > 0){ $smaller[$choice1['key']] = $choice1['value'] - $avg; $sN++; } //this bin comprises of only one value $bin[] = array(1=>$choice1['key'], 2=>null, 'p1'=>1, 'p2'=>0); }else{ //make the second choice for the current bin $choice2 = each($greater_eq); unset($greater_eq[$choice2['key']]); //splitting on the second interval if($choice2['value'] - $avg + $choice1['value'] >= $avg){ $greater_eq[$choice2['key']] = $choice2['value'] - $avg + $choice1['value']; }else{ $smaller[$choice2['key']] = $choice2['value'] - $avg + $choice1['value']; $sN++; } //this bin comprises of two values $choice2['value'] = $avg - $choice1['value']; $bin[] = array(1=>$choice1['key'], 2=>$choice2['key'], 'p1'=>$choice1['value'] / $avg, 'p2'=>$choice2['value'] / $avg); } } $this->bins = $bin; } /** * Choose a random sample according to the weights. */ public function random(){ $bin = $this->bins[array_rand($this->bins)]; $randValue = (lcg_value() < $bin['p1'])?$bin[1]:$bin[2]; } 

Aquí está mi versión que puede aplicarse a cualquier IList y normalizar el peso. Se basa en la solución de Timwi: selección basada en el porcentaje de ponderación

 ///  /// return a random element of the list or default if list is empty ///  ///  ///  /// return chances to be picked for the element. A weigh of 0 or less means 0 chance to be picked. /// If all elements have weight of 0 or less they all have equal chances to be picked. ///  ///  public static T AnyOrDefault(this IList e, Func weightSelector) { if (e.Count < 1) return default(T); if (e.Count == 1) return e[0]; var weights = e.Select(o => Math.Max(weightSelector(o), 0)).ToArray(); var sum = weights.Sum(d => d); var rnd = new Random().NextDouble(); for (int i = 0; i < weights.Length; i++) { //Normalize weight var w = sum == 0 ? 1 / (double)e.Count : weights[i] / sum; if (rnd < w) return e[i]; rnd -= w; } throw new Exception("Should not happen"); }