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

Question

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

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

Answer 1

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

Давайте рассмотрим пример пяти одинаково взвешенных вариантов: (a:1, b:1, c:1, d:1, e:1)

Чтобы создать поиск псевдонимов:

1. Нормализуйте веса так, чтобы они суммировались до 1.0. (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2) Это вероятность выбора каждого веса.

2. Найдите наименьшую степень 2, большую или равную количеству переменных, и создайте это число секций, |p|. Каждый раздел представляет массу вероятности 1/|p|. В этом случае мы создаем 8 разделов, каждый из которых может содержать 0.125.

3. Возьмите переменную с наименьшим оставшимся весом и поместите как можно большую часть ее массы в пустой раздел. В этом примере мы видим, что a заполняет первый раздел. (p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8) с (a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)

4. Если раздел не заполнен, возьмите переменную с наибольшим весом и заполните раздел этой переменной.

Повторяйте шаги 3 и 4 до тех пор, пока ни один из весов из исходного раздела не будет назначен списку.

Например, если мы выполним еще одну итерацию 3 и 4, мы увидим

(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8) с (a:0, b:0.15 c:0.2 d:0.2 e:0.2) осталось назначить

Во время выполнения:

1. Получите U(0,1) случайное число, скажем, двоичное 0.001100000

2. Сдвиг битов lg2(p), поиск индекса раздела. Таким образом, мы сдвигаем его на 3, получая 001.1, или позицию 1, и, таким образом, делим 2.

3. Если разделение разделено, используйте десятичную часть смещенного случайного числа, чтобы решить разделение. В этом случае значение равно 0.5 и 0.5 < 0.6, поэтому верните a.

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

Answer 2

Простой подход, который не был упомянут здесь, - это предложенный в Efraimidis и Spirakis . В Python вы можете выбрать m элементов из n> = m взвешенных элементов со строго положительными весами, сохраненными в весах, возвращая выбранные индексы с помощью:

import heapq
import math
import random

def WeightedSelectionWithoutReplacement(weights, m):
    elt = [(math.log(random.random()) / weights[i], i) for i in range(len(weights))]
    return [x[1] for x in heapq.nlargest(m, elt)]

Это очень похоже по структуре на первый подход, предложенный Ником Джонсоном. К сожалению, этот подход смещен в выборе элементов (см. Комментарии к методу). Эфраимидис и Спиракис доказали, что их подход эквивалентен случайной выборке без замены в связанной статье.

Answer 3

Вот то, что я придумал для взвешенного выбора без замены:

def WeightedSelectionWithoutReplacement(l, n):
  """Selects without replacement n random elements from a list of (weight, item) tuples."""
  l = sorted((random.random() * x[0], x[1]) for x in l)
  return l[-n:]

Это O (m log m) для количества элементов в списке, из которых нужно выбрать. Я вполне уверен, что это будет правильно взвешивать предметы, хотя я не проверял это ни в каком формальном смысле.

Вот что я придумал для взвешенного отбора с заменой:

def WeightedSelectionWithReplacement(l, n):
  """Selects with replacement n random elements from a list of (weight, item) tuples."""
  cuml = []
  total_weight = 0.0
  for weight, item in l:
    total_weight += weight
    cuml.append((total_weight, item))
  return [cuml[bisect.bisect(cuml, random.random()*total_weight)] for x in range(n)]

Это O (m + n log m), где m - количество элементов в списке ввода, а n - количество элементов, которые нужно выбрать.

Answer 4

Взвешенный случайный выбор можно выполнить с заменой за время O (1) после первого создания дополнительной структуры данных размера O (N) за время O (N). Алгоритм основан на методе Alias ​​, разработанном Уокером и Возе, который хорошо описан здесь .

Основная идея состоит в том, что каждый бин в гистограмме будет выбираться с вероятностью 1 / N однородным ГСЧ. Таким образом, мы пройдемся по нему, и для любого малонаселенного мусорного ведра, которое получило бы избыточные попадания, назначьте избыток перенаселенному мусорному ведру. Для каждого бина мы храним процент попаданий, которые ему принадлежат, и партнерское бин для превышения. Эта версия отслеживает маленькие и большие корзины на месте, устраняя необходимость в дополнительном стеке. Он использует индекс партнера (хранится в bucket[1]) в качестве индикатора того, что они уже обработаны.

Вот минимальная реализация на Python, основанная на реализации C здесь

def prep(weights):
    data_sz = len(weights)
    factor = data_sz/float(sum(weights))
    data = [[w*factor, i] for i,w in enumerate(weights)]
    big=0
    while big<data_sz and data[big][0]<=1.0: big+=1
    for small,bucket in enumerate(data):
        if bucket[1] is not small: continue
        excess = 1.0 - bucket[0]
        while excess > 0:
            if big==data_sz: break
            bucket[1] = big
            bucket = data[big]
            bucket[0] -= excess
            excess = 1.0 - bucket[0]
            if (excess >= 0):
                big+=1
                while big<data_sz and data[big][0]<=1: big+=1
    return data

def sample(data):
    r=random.random()*len(data)
    idx = int(r)
    return data[idx][1] if r-idx > data[idx][0] else idx

Пример использования:

TRIALS=1000
weights = [20,1.5,9.8,10,15,10,15.5,10,8,.2];
samples = [0]*len(weights)
data = prep(weights)

for _ in range(int(sum(weights)*TRIALS)):
    samples[sample(data)]+=1

result = [float(s)/TRIALS for s in samples]
err = [a-b for a,b in zip(result,weights)]
print(result)
print([round(e,5) for e in err])
print(sum([e*e for e in err]))

Answer 5

Ниже приведено описание случайного взвешенного выбора элемента set (или мультимножество, если повторы разрешены), как с заменой, так и без замены в пространстве O (n) и O (log n) время.

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

1. сам элемент ( элемент )
2. ненормализованный вес элемента ( elementweight ) и
3. сумма всех ненормализованных весов левого дочернего узла и всех его дети ( левосторонний ).
4. сумма всех ненормализованных весов правого дочернего узла и всех его дети ( правосторонний ).

Затем мы случайным образом выбираем элемент из BST, спускаясь по дереву. Грубое описание алгоритма приведено ниже. Алгоритм получает узел из дерево. Тогда значения левый ответный вес , правый ответный вес , и elementweight of node суммируется, и веса делятся на это сумма, в результате чего значения правостороннее правдоподобие , правосторонняя правдоподобие и правдоподобие элемента соответственно. Затем получается случайное число от 0 до 1 ( randomnumber ).

• , если число меньше элемент вероятности ,
  • удалить элемент из BST как обычно, обновив leftbranchweight и правосторонний вес всех необходимых узлов и вернуть элемент.
• иначе, если число меньше ( вероятность элемента + левый ответный вес )
  • recurse on leftchild (запустите алгоритм, используя leftchild как node )
• еще
  • рекурс на правшу

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

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Алгоритм является грубым, и трактат о правильной реализации BST здесь не предпринимается; скорее стоит надеяться, что этот ответ поможет те, кому действительно нужен быстрый взвешенный отбор без замены (как я).

Answer 6

Я бы порекомендовал вам начать с изучения раздела 3.4.2 Получисленных алгоритмов Дональда Кнута.

Если ваши массивы большие, в главе 3 Принципы генерации случайных вариаций Джона Дагпунара есть более эффективные алгоритмы. Если ваши массивы не слишком велики или вы не заинтересованы в том, чтобы выжать как можно больше эффективности, более простые алгоритмы в Кнуте, вероятно, подойдут.

Answer 7

Предположим, что вы хотите выбрать 3 элемента без замены из списка ['white', 'blue', 'black', 'yellow', 'green'] с пробой. распределение [0,1, 0,2, 0,4, 0,1, 0,2]. С помощью модуля numpy.random это так просто:

    import numpy.random as rnd

    sampling_size = 3
    domain = ['white','blue','black','yellow','green']
    probs = [.1, .2, .4, .1, .2]
    sample = rnd.choice(domain, size=sampling_size, replace=False, p=probs)
    # in short: rnd.choice(domain, sampling_size, False, probs)
    print(sample)
    # Possible output: ['white' 'black' 'blue']

Если установить флаг replace на True, у вас есть выборка с заменой.

Больше информации здесь: http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html#numpy.random.choice