Взвешенный случайный выбор из массива - PullRequest
Новая
       6

Взвешенный случайный выбор из массива

67 голосов
/ 16 декабря 2010

Я бы хотел случайным образом выбрать один элемент из массива, но каждый элемент имеет известную вероятность выбора.

Все шансы вместе (в массиве) суммируются в 1.

Какой алгоритм вы бы предложили как самый быстрый и наиболее подходящий для огромных вычислений?

Пример: 

id => chance
array[
    0 => 0.8
    1 => 0.2
]

для этого псевдокода рассматриваемый алгоритм должен при нескольких вызовах статистически возвращать четыре элемента с идентификатором 0 для одного элемента с идентификатором 1.

Ответы [ 12 ]

67 голосов
/ 16 декабря 2010

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

13 голосов
/ 16 декабря 2010

Алгоритм прост 

rand_no = rand(0,1)
for each element in array 
     if(rand_num < element.probablity)
          select and break
     rand_num = rand_num - element.probability
8 голосов
/ 29 августа 2016

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

Я считаю, что оптимальным решением является использование Alias ​​Method (wikipedia) .Для инициализации требуется O (n) время, O (1) время для выбора и O (n) память.

Вот алгоритм для генерации результата броска взвешенного n -стороннего штампа (отсюда тривиально выбрать элемент из массива длины - n ) в виде взятия из эта статья .Автор предполагает, что у вас есть функции для бросания справедливого кубика (floor(random() * n)) и подбрасывания смещенной монеты (random() < p).

Алгоритм: метод псевдонима Vose

Инициализация:

  1. Создание массивов Псевдоним и Проб , каждый размером n .
  2. Создание двух рабочих списков, Малая и Большая .
  3. Умножьте каждую вероятность на n .
  4. Для каждой масштабированной вероятности p i :
    1. Если p i <1 </em>, добавьте i к Small .
    2. В противном случае ( p i ≥ 1 ), добавьте i к Large .
  5. Пока Маленький и Большой не пусты: ( Большой может быть сначала очищен)
    1. Удалить первый элемент из Маленький;назовите это l .
    2. Удалите первый элемент из Large ;Назовите его г .
    3. Набор Проб [л] = р л .
    4. Набор Псевдоним [l] = g .
    5. Set p g : = (p g + p l ) - 1 .(Это более числовой стабильный вариант.)
    6. Если p g <1 </em>, добавьте g к Small .
    7. В противном случае ( p g ≥ 1 ) добавьте g к Large .
  6. Пока Large не пусто:
    1. Удалить первый элемент из Large ;Назовите это г .
    2. Набор Проб [г] = 1 .
  7. В то время как Маленький не пусто: это возможно только из-за численной нестабильности.
    1. Удалить первый элемент из Small ;назовите это l .
    2. Set Prob [l] = 1 .

Поколение:

  1. Создайте справедливый бросок кубика из кубика n ;коллировать сторону i .
  2. перевернуть смещенную монету, которая появляется с вероятностью Prob [i] .
  3. если монета выпадет "головки "return i .
  4. В противном случае верните Alias ​​[i] .
6 голосов
/ 16 декабря 2010

Это можно сделать за O (1) ожидаемое время для образца следующим образом.

Вычислить CDF F (i) для каждого элемента i, чтобы получить сумму вероятностей, меньших или равных i.

Определить диапазон r (i) элемента i как интервал [F (i - 1), F (i)].

Для каждого интервала [(i - 1) / n, i / n] создайте сегмент, состоящий из списка элементов, диапазон которых перекрывает интервал. Это займет всего O (n) времени для всего массива, если вы достаточно осторожны.

Когда вы случайным образом выбираете массив, вы просто вычисляете, в каком сегменте находится случайное число, и сравниваете его с каждым элементом списка, пока не найдете интервал, который его содержит.

Стоимость выборки составляет O (ожидаемая длина случайно выбранного списка) <= 2. </p>

6 голосов
/ 16 декабря 2010

Пример в ruby ​​

#each element is associated with its probability
a = {1 => 0.25 ,2 => 0.5 ,3 => 0.2, 4 => 0.05}

#at some point, convert to ccumulative probability
acc = 0
a.each { |e,w| a[e] = acc+=w }

#to select an element, pick a random between 0 and 1 and find the first   
#cummulative probability that's greater than the random number
r = rand
selected = a.find{ |e,w| w>r }

p selected[0]
5 голосов
/ 22 апреля 2014

Другой пример Ruby: 

def weighted_rand(weights = {})
  raise 'Probabilities must sum up to 1' unless weights.values.inject(&:+) == 1.0
  raise 'Probabilities must not be negative' unless weights.values.all? { |p| p >= 0 }
  # Do more sanity checks depending on the amount of trust in the software component using this method
  # E.g. don't allow duplicates, don't allow non-numeric values, etc.

  # Ignore elements with probability 0
  weights = weights.reject { |k, v| v == 0.0 }   # e.g. => {"a"=>0.4, "b"=>0.4, "c"=>0.2}

  # Accumulate probabilities and map them to a value
  u = 0.0
  ranges = weights.map { |v, p| [u += p, v] }   # e.g. => [[0.4, "a"], [0.8, "b"], [1.0, "c"]]

  # Generate a (pseudo-)random floating point number between 0.0(included) and 1.0(excluded)
  u = rand   # e.g. => 0.4651073966724186

  # Find the first value that has an accumulated probability greater than the random number u
  ranges.find { |p, v| p > u }.last   # e.g. => "b"
end

Как использовать: 

weights = {'a' => 0.4, 'b' => 0.4, 'c' => 0.2, 'd' => 0.0}

weighted_rand weights

Чего ожидать: 

d = 1000.times.map{ weighted_rand weights }
d.count('a') # 396
d.count('b') # 406
d.count('c') # 198
3 голосов
/ 04 апреля 2015

Ruby решение с использованием пикапа gem : 

require 'pickup'

chances = {0=>80, 1=>20}
picker = Pickup.new(chances)

Пример: 

5.times.collect {
  picker.pick(5)
}

дал вывод: 

[[0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 1, 1], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 1]]
2 голосов
/ 19 мая 2017

Это код PHP, который я использовал в производстве: 

/**
 * @return \App\Models\CdnServer
*/
protected function selectWeightedServer(Collection $servers)
{
    if ($servers->count() == 1) {
        return $servers->first();
    }

    $totalWeight = 0;

    foreach ($servers as $server) {
        $totalWeight += $server->getWeight();
    }

    // Select a random server using weighted choice
    $randWeight = mt_rand(1, $totalWeight);
    $accWeight = 0;

    foreach ($servers as $server) {
        $accWeight += $server->getWeight();

        if ($accWeight >= $randWeight) {
            return $server;
        }
    }
}
2 голосов
/ 16 декабря 2010

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

array[
    0 => 0
    1 => 0
    2 => 0
    3 => 0
    4 => 1
]
1 голос
/ 27 февраля 2013

хитрость может заключаться в том, чтобы выбрать вспомогательный массив с повторениями элементов, которые отражают вероятность

Учитывая элементы, связанные с их вероятностью, в процентах: 

h = {1 => 0.5, 2 => 0.3, 3 => 0.05, 4 => 0.05 }

auxiliary_array = h.inject([]){|memo,(k,v)| memo += Array.new((100*v).to_i,k) }   

ruby-1.9.3-p194 > auxiliary_array 
 => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,                                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4] 

auxiliary_array.sample

если вы хотите использовать как можно более общее значение, вам нужно рассчитать множитель на основе максимального числа дробных цифр и использовать его вместо 100: 

m = 10**h.values.collect{|e| e.to_s.split(".").last.size }.max
Страница:
...