Подтвердить что ты не робот

Выбор на основе процентного взвешивания

У меня есть набор значений и связанный процент для каждого:

a: 70% шанс
б: вероятность 20%
c: вероятность 10%

Я хочу выбрать значение (a, b, c) на основе процентного шанса.

Как мне подойти к этому?


моя попытка до сих пор выглядит так:

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

Я застрял с алгоритмом, чтобы справиться с этим. Как мне подойти к этому, чтобы он мог обрабатывать более крупные наборы значений, не связывая друг с другом потоки if-else.


(любое объяснение или ответы в псевдокоде прекрасны: реализация python или С# будет особенно полезна)

4b9b3361

ОТВЕТЫ

Ответ 1

Вот полное решение в С#:

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.");
    }
}

Применение:

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());

Ответ 2

Для 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
>>>

Общая идея: составить список, в котором каждый элемент повторяется в несколько раз пропорционально вероятности, которую он должен иметь; используйте random.choice, чтобы выбрать один случайным образом (равномерно), это будет соответствовать вашему обязательному распределению вероятности. Может быть немного расточительно память, если ваши вероятности выражаются особыми способами (например, 70, 20, 10 составляет список из 100 элементов, где 7, 2, 1 будет составлять список из 10 элементов с точно таким же поведением), но вы можете разделить все подсчеты в списке вероятностей по их наибольшему общему коэффициенту, если вы считаете, что это может быть большой проблемой в вашем конкретном сценарии приложения.

Помимо проблем с потреблением памяти, это должно быть самое быстрое решение - только одно генерирование случайных чисел за каждый требуемый результат вывода и самый быстрый поиск из этого случайного числа, без сравнений и с. Если ваши вероятные вероятности очень странные (например, числа с плавающей запятой, которые должны соответствовать многим, многим значимым цифрам), могут быть предпочтительными другие подходы: -).

Ответ 3

Кнут ссылается на метод псевдонимов Уолкера. Поиск по этому вопросу я нахожу http://code.activestate.com/recipes/576564-walkers-alias-method-for-random-objects-with-diffe/ и http://prxq.wordpress.com/2006/04/17/the-alias-method/. Это дает точные вероятности, требуемые в постоянное время на число, генерируемое с линейным временем для установки (любопытно, n log n время для установки, если вы точно используете метод, описанный Knuth, который может быть подготовительным типом, который вы можете избежать).

Ответ 4

Возьмите список и найдите совокупное общее количество весов: 70, 70 + 20, 70 + 20 + 10. Выберите случайное число, большее или равное нулю и меньшее, чем общее. Перейдем к элементам и вернем первое значение, для которого суммарная сумма весов больше, чем это случайное число:

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

Это решение, как реализовано, должно также иметь возможность обрабатывать дробные веса и веса, которые суммируются до любого числа, если все они неотрицательны.

Ответ 5

  • Пусть T = сумма всех весов элементов
  • Пусть R = случайное число между 0 и T
  • Итерировать список элементов, вычитая каждый вес предмета из R и возвращать элемент, который заставляет результат становиться <= 0.

Ответ 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

Потому что random.random всегда будет возвращать < 1.0, окончательный return никогда не должен быть достигнут.

Ответ 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)]

он работает одинаково хорошо для дробных весов

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

Если у вас много весов, вы можете использовать bisect для уменьшения количества требуемых итераций

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

Также отлично работает для дробных весов

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

Ответ 8

Сегодня обновление документа python дает пример, чтобы сделать random.choice() со взвешенными вероятностями:

Если веса являются малыми целыми отношениями, простой метод заключается в построении выборочной совокупности с повторами:

>>> 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'

Более общий подход состоит в том, чтобы расположить веса в кумулятивном распределении с itertools.accumulate(), а затем найти случайное значение с помощью bisect.bisect():

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

одно примечание: itertools.accumulate() нуждается в python 3.2 или определить его с эквивалентом.

Ответ 9

Я думаю, что у вас может быть массив небольших объектов (я реализовал на Java, хотя знаю немного С#, но я боюсь, что могу написать неправильный код), поэтому вам может потребоваться его собственный порт. Код в С# будет намного меньше со структурой, var, но я надеюсь, что вы получите идею

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;
  }
}

Ответ 10

У меня есть собственное решение для этого:

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;

}
}

И использование этого должно быть что-то вроде этого (thats in 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));
}
}

В этом примере каждое значение имеет вероятность 10% быть отображено как debug = 3

Ответ 11

Если вы действительно ускоряетесь и хотите быстро генерировать случайные значения, алгоритм Walker mcdowella, упомянутый в fooobar.com/questions/198009/..., - это самый лучший способ пойти (O (1) время для случайного() и O (N) времени для препроцесса()).

Для всех, кто заинтересован, вот моя собственная реализация PHP алгоритма:

/**
 * Pre-process the samples (Walker 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];        
}

Ответ 12

Вот моя версия, которая может применяться к любому IList и нормализовать вес. Он основан на решении Timwi: выбор на основе процентного взвешивания

/// <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");
}

Ответ 14

Основан на numpy.random.choice(a=items, p=probs), который принимает массив и массив вероятностей одинакового размера.

    public T RandomChoice<T>(IEnumerable<T> a, IEnumerable<double> p)
    {
        IEnumerator<T> ae = a.GetEnumerator();
        Random random = new Random();
        double target = random.NextDouble();
        double accumulator = 0;
        foreach (var prob in p)
        {
            ae.MoveNext();
            accumulator += prob;
            if (accumulator > target)
            {
                break;
            }
        }
        return ae.Current;
    }

Массив вероятности p должен быть равен (приблизительно) 1. Это сделано для того, чтобы поддерживать его в соответствии с простым интерфейсом (и математикой), но вы можете легко изменить это, если хотите.