Случайно перетасовывайте взвешенный массив

Question

Существует хэш с идентификаторами и весами этих идентификаторов.

y = { 1 => 0.7, 2 => 0.2, 3 => 0.1 } 

Я хотел бы перетасовать этот хеш в соответствии с весами.

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

y.sort_by {|v| -v[1]*rand()} 

Когда я запускаю это в десять тысяч раз и выбрать первые идентификаторы, я получаю следующие счетчики:

{1=>8444, 2=>1316, 3=>240} 

Я ожидал, что эти счетчики с учетом веса выше (например, 1 =>7000). Мне немного туманно, почему эта перетасовка не соответствует этим весам. Может кто-то очистить мою путаницу и рассказать, как это исправить?

Вот некоторые из полезных источников я нашел:

• Random item by weight
• Weighted Shuffle of an Array or Arrays?
• How to implement a Weighted shuffle
• One-line ruby weighted shuffle

Answer 1

Вот достаточно, скорее всего неэффективно, но мы надеемся, эффективное решение : (Хотя я не обещаю правильности! Плюс код не собирается делать слишком много рубистов счастливыми ...).

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

def shuffle some_hash 
    result = [] 

    numbers = some_hash.keys 
    weights = some_hash.values 
    total_weight = weights.reduce(:+) 

    # choose numbers one by one 
    until numbers.empty? 
     # weight from total range of weights 
     selection = rand() * total_weight 

     # find which element this corresponds with 
     i = 0 
     while selection > 0 
     selection -= weights[i] 
     i += 1 
     end 
     i -= 1 

     # add number to result and remove corresponding weight 
     result << numbers[i] 
     numbers.delete_at i 
     total_weight -= weights.delete_at(i) 
    end 

    result 
end 

Answer 2

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

y = { 1 => 7, 2 => 2, 3 => 1 } 

Тогда можно построить массив, где число вхождений каждого элемента в массиве на основе весов:

weighted_occurrences = y.flat_map { |id, weight| Array.new(weight, id) } 
# => [1, 1, 1, 1, 1, 1, 1, 2, 2, 3] 

Затем делают взвешенную перетасовать так просто, как:

weighted_occurrences.shuffle.uniq 

После 10000 перемешивает и выбирая первые идентификаторы, я получаю:

{ 
    1 => 6988, 
    2 => 1934, 
    3 => 1078 
} 

Answer 3

Вы дали функцию плотности вероятности (P для «proability):

P(1) = 0.7 
P(2) = 0.3 
P(3) = 0.1 

Вам нужно построить (кумулятивный) функция распределения, которая выглядит следующим образом:

Теперь мы можем генерировать случайные числа между нулем и одним, нанести их на ось Y, нарисовать линию справа, чтобы увидеть, где они пересекают функцию распределения, затем прочитать связанную координату X как случайную величину. Поэтому, если случайное число меньше 0,7, случайная величина равна 1; если между 0,7 и 0,9, случайная величина равна 2, а случайная величина равна 3, если вероятность превышает 0.9. (Обратите внимание, что вероятность того, что rand будет равна 0.7 (скажем) точно практически равна нулю, поэтому мы не должны Сожалеем о различении < 0.7 и <= 0.7.)

Чтобы осуществить это, сначала вычислить хэш df:

y = { 1 => 0.7, 2 => 0.2, 3 => 0.1 } 

last = 0.0 
df = y.each_with_object({}) { |(v,p),h| last += p; h[last.round(10)] = v } 
    #=> {0.7=>1, 0.9=>2, 1.0=>3} 

И теперь мы можем создать случайное варьировать следующим образом:

def rv(df) 
    rn = rand 
    df.find { |p,_| rn < p }.last 
end 

Давайте попробуем:

def count(df,n) 
    n.times.each_with_object(Hash.new(0)) { |_,count| 
    count[rv(df)] += 1 } 
end 

n = 10_000 
count(df,n) 
    #=> {1=>6993, 2=>1960, 3=>1047} 
count(df,n) 
    #=> {1=>6986, 2=>2042, 3=>972} 
count(df,n) 
    #=> {1=>6970, 2=>2039, 3=>991} 

Обратите внимание, что порядок пар ключ-значение count определяется по результатам первых нескольких случайных вариаций, поэтому ключи не обязательно будут находиться в том порядке, в котором они находятся.

Answer 4

Вот еще один способ выполнить взвешенную случайную выборку, используя Enumerable#max_by и этот удивительный результат от Efraimidis and Spirakis:

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

# hash of ids with their respective weights that sum to 1 
y = { 1 => 0.7, 2 => 0.2, 3 => 0.1 } 

# lambda that randomly returns a key from y in proportion to its weight 
wrs = -> { y.max_by { |_, weight| rand ** (1.0/weight) }.first } 

# test run to see if it works 
10_000.times.each_with_object(Hash.new(0)) { |_, freq| freq[wrs.call] += 1 } 

# => {1=>6963, 3=>979, 2=>2058} 

На боковой ноте было добавлено talk с добавлением взвешенной случайной выборки в Array#sample, но функция, похоже, затерялась в перетасовке.

Дальнейшее чтение:

1. Ruby-Doc для Enumerable#max_by - конкретно wsample пример
2. Weighted Random Sampling по Efraimidis и Spirakis (2005), который вводит алгоритм
3. New features for Array#sample, Array#choice, который упоминает о намерении добавления взвешенного случайной выборки для Array#sample