Случайная выборка из гистограммы / таблицы частотного хэша - PullRequest
Новая
       22

Случайная выборка из гистограммы / таблицы частотного хэша

0 голосов
/ 24 мая 2018

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

Данные в настоящее время содержатся в хеш-таблице, где каждый ключ являетсяitem, а значение ключа - это частота элемента в исходном распределении.

Если кто-то хотел бы выбрать из такой гистограммы, как бы он это сделал, если бы он хотел сохранить исходные вероятности элементов и передать ихв образец?

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

Существует ли общепринятый алгоритм для этого?Если это поможет, нам нужно реализовать его в Common Lisp.

1 Ответ

0 голосов
/ 24 мая 2018

Это часть ответа.Он использует списки вместо хеш-таблицы: 

(defun random-item-with-prob (prob-item-pairs) 
  "The argument PROB-ITEM-PAIRS is ((p_1 item_1) (p_2 item_2) ... 
   (p_n item_n)). The function returns one of the items according to the
   probabilities. "
 (loop with p = (random 1.0)
       with x = 0
       for pair in prob-item-pairs
       do
        (if (< p (+ (first pair) x)) 
            (return (second pair))
            (incf x (first pair)))))

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

...