de selección basado en la ponderación porcentaje

Question

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) basado en el porcentaje de posibilidades otorgadas.

¿cómo puedo abordar esto?

mi intento hasta ahora se ve así:

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

estoy atascado subir con un algoritmo para manejar esto. ¿Cómo debería abordar esto para que pueda manejar conjuntos de valores más grandes sin solo encadenar flujos if-else juntos?

(ninguna explicación o respuesta en pseudo-código son bien una implementación de Python o C# sería especialmente útil.)

Answer 1

Tome la lista de y encontrar 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 obtener el primer valor para el cual la suma 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, tal como se aplica, también debe ser capaz de manejar pesos fraccionarios y los pesos que se suman a cualquier número, siempre y cuando no sean negativos.

Answer 2

Creo que puede tener una serie de objetos pequeños (lo implementé en Java aunque sé un poco C# pero me temo que puedo escribir un código incorrecto), por lo que es posible que deba portarlo usted mismo. El código en C# será mucho más pequeño, con estructura, var, pero espero que la idea

class PercentString { 
    double percent; 
    String value; 
    // Constructor for 2 values 
} 

ArrayList<PercentString> list = new ArrayList<PercentString(); 
list.add(new PercentString(70, "a"); 
list.add(new PercentString(20, "b"); 
list.add(new PercentString(10, "c"); 

double percent = 0; 
for (int i = 0; i < list.size(); i++) { 
    PercentString p = list.get(i); 
    percent += p.percent; 
    if (random < percent) { 
    return p.value; 
    } 
} 

Answer 3

1. Sea T = la suma de todas las ponderaciones de los artículos
2. Sea R = un número aleatorio entre 0 y T
3. iterar la lista de elementos restando cada peso del artículo de R y devolver el artículo que hace que el resultado para convertirse < = 0.

Answer 4

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), 
... 
a c c b a a a a a a a a 
>>> for _ in range(12): print random.choice(picks), 
... 
a c a c a b b b a a a a 
>>> for _ in range(12): print random.choice(picks), 
... 
a a a a c c a c a a c a 
>>> 

Idea general: haga una lista en la que cada elemento se repite varias veces proporcionalmente a la probabilidad que debería tener; use random.choice para elegir uno al azar (uniformemente), esto coincidirá con la distribución de probabilidad requerida. Puede ser un 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 recuentos en la lista de probabilidades por su mayor factor común si cree que es probable que sea un gran problema en su escenario de aplicación específico.

Además 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 de ese número aleatorio, sin comparaciones & c. Si sus probabilidades probables son muy extrañas (por ejemplo, números de coma flotante que deben coincidir con muchos, muchos dígitos significativos), pueden preferirse otros enfoques ;-).

Answer 5

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

public class ProportionValue<T> 
{ 
    public double Proportion { get; set; } 
    public T Value { get; set; } 
} 

public static class ProportionValue 
{ 
    public static ProportionValue<T> Create<T>(double proportion, T value) 
    { 
     return new ProportionValue<T> { Proportion = proportion, Value = value }; 
    } 

    static Random random = new Random(); 
    public static T ChooseByRandom<T>(
     this IEnumerable<ProportionValue<T>> 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()); 

Answer 6

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 random.random siempre devolverá < 1.0, nunca debe ser alcanzado la final return .

Answer 7

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 igualmente bien para los pesos fraccionarios

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

Si usted tiene un mucho de pesos, se puede utilizar la bisectriz de reducir el número de iteraciones necesarias

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

Answer 8

Knuth hace referencia al método de alias de Walker. Buscando en esto, me parece http://code.activestate.com/recipes/576564-walkers-alias-method-for-random-objects-with-diffe/ y http://prxq.wordpress.com/2006/04/17/the-alias-method/. Esto proporciona 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 Knuth describe, que hace una clasificación preparatoria que puede evitar).

Answer 9

hoy, the update of python document dar un ejemplo para hacer una random.choice() con probabilidades ponderadas:

Si los pesos son relaciones de números enteros pequeños, una técnica sencilla es construir una población de la 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 el de organizar los pesos en una distribución acumulativa con itertools.accumulate(), y luego localizar 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() needs python 3.2 or define it with the Equivalent.

Answer 10

Si usted es realmente depende de la velocidad y desea generar los valores aleatorios de forma rápida, mcdowella algoritmo de Walker se menciona en https://stackoverflow.com/a/3655773/1212517 es más o menos el mejor camino a seguir (O ​​(1) tiempo para al azar (), y O (N) tiempo para preproceso()).

Para cualquiera que esté interesado, aquí es mi propia implementación en 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];   
} 

Answer 11

aquí está mi versión que puede aplicarse a cualquier IList y normalizar el peso.Se basa en la solución de Timwi: selection based on percentage weighting

/// <summary> 
/// return a random element of the list or default if list is empty 
/// </summary> 
/// <param name="e"></param> 
/// <param name="weightSelector"> 
/// 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. 
/// </param> 
/// <returns></returns> 
public static T AnyOrDefault<T>(this IList<T> e, Func<T, double> 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"); 
} 

Answer 12

tengo mi propia solución para esto:

public class Randomizator3000 
{  
public class Item<T> 
{ 
    public T value; 
    public float weight; 

    public static float GetTotalWeight<T>(Item<T>[] 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<T>(Item<T>[] p_itens) 
{ 
    if(p_itens == null || p_itens.Length == 0) 
    { 
     return default(T); 
    } 

    float __randomizedValue = (float)_random.NextDouble() * (Item<T>.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 su uso debe ser algo así (eso es en Unity3d)

using UnityEngine; 
using System.Collections; 

public class teste : MonoBehaviour 
{ 
Randomizator3000.Item<string>[] lista; 

void Start() 
{ 
    lista = new Randomizator3000.Item<string>[10]; 
    lista[0] = new Randomizator3000.Item<string>(); 
    lista[0].weight = 10; 
    lista[0].value = "a"; 

    lista[1] = new Randomizator3000.Item<string>(); 
    lista[1].weight = 10; 
    lista[1].value = "b"; 

    lista[2] = new Randomizator3000.Item<string>(); 
    lista[2].weight = 10; 
    lista[2].value = "c"; 

    lista[3] = new Randomizator3000.Item<string>(); 
    lista[3].weight = 10; 
    lista[3].value = "d"; 

    lista[4] = new Randomizator3000.Item<string>(); 
    lista[4].weight = 10; 
    lista[4].value = "e"; 

    lista[5] = new Randomizator3000.Item<string>(); 
    lista[5].weight = 10; 
    lista[5].value = "f"; 

    lista[6] = new Randomizator3000.Item<string>(); 
    lista[6].weight = 10; 
    lista[6].value = "g"; 

    lista[7] = new Randomizator3000.Item<string>(); 
    lista[7].weight = 10; 
    lista[7].value = "h"; 

    lista[8] = new Randomizator3000.Item<string>(); 
    lista[8].weight = 10; 
    lista[8].value = "i"; 

    lista[9] = new Randomizator3000.Item<string>(); 
    lista[9].weight = 10; 
    lista[9].value = "j"; 
} 


void Update() 
{ 
    Debug.Log(Randomizator3000.PickOne<string>(lista)); 
} 
} 

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

Answer 13

Aquí hay un Ruby versión del método, así Alias: https://github.com/cantino/walker_method