WikiDer > Отбор проб из резервуара

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

Мотивация

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

Простой алгоритм

Простой и популярный, но медленный алгоритм, широко известный как Алгоритм R, принадлежит Алану Уотерману.^[1]

Алгоритм работает, поддерживая резервуар размера k, который изначально содержит первый k элементы ввода. Затем он перебирает оставшиеся элементы, пока ввод не будет исчерпан. Использование массива на основе единицы индексация, позволять ${ displaystyle i> k}$ быть индексом рассматриваемого элемента. Затем алгоритм генерирует случайное число j между (включительно) 1 и я. Если j самое большее k, то элемент выбирается и заменяет тот элемент, который в настоящее время занимает j-я позиция в резервуаре. В противном случае предмет выбрасывается. Фактически для всех я, то я^th элемент ввода выбирается для включения в пласт с вероятностью ${ displaystyle k / i}$. Аналогично на каждой итерации j^th элемент коллектора коллектора выбирается заменяемым с вероятностью ${ Displaystyle 1 / к раз к / я = 1 / я}$. Можно показать, что, когда алгоритм завершает выполнение, каждый элемент во входной совокупности имеет равную вероятность (т. Е. ${ displaystyle k / n}$) быть выбранным для резервуара: ${ Displaystyle 1 / я раз (1-1 / (я + 1)) раз (1-1 / (я + 2)) раз (1-1 / (я + 3) раз ... раз (1-1 / n) = k / n}$.

(* S имеет элементы для выборки, R будет содержать результат *)Резервуар(S[1..п], р[1..k])  // заполняем массив резервуара  за я := 1 к k      р[я] := S[я]  // заменяем элементы с постепенно уменьшающейся вероятностью  за я := k+1 к п    (* randomInteger (a, b) генерирует однородное целое число из включающего диапазона {a, ..., b} *)    j := randomInteger(1, я)    если j <= k        р[j] := S[я]

Хотя этот алгоритм концептуально прост и понятен, он должен генерировать случайное число для каждого элемента входных данных, включая элементы, которые отбрасываются. Его асимптотическое время работы таким образом ${ Displaystyle О (п)}$. Это приводит к излишне медленной работе алгоритма при большом количестве входных данных.

Оптимальный алгоритм

Алгоритм L^[2] улучшает этот алгоритм, вычисляя, сколько элементов выбрасывается до того, как следующий элемент попадет в резервуар. Ключевое наблюдение состоит в том, что это число следует за геометрическое распределение и поэтому может быть вычислен за постоянное время.

(* S имеет элементы для выборки, R будет содержать результат *)Резервуар(S[1..п], р[1..k])  // заполняем массив резервуара  за я = 1 к k      р[я] := S[я]  (* random () генерирует равномерное (0,1) случайное число *)  W := exp(бревно(случайный())/k)  пока я <= п      я := я + этаж(бревно(случайный())/бревно(1-W)) + 1      если я <= п          (* заменить случайный элемент резервуара на элемент i *)          р[randomInteger(1,k)] := S[я]  // случайный индекс от 1 до k включительно          W := W * exp(бревно(случайный())/k)

Этот алгоритм вычисляет три случайных числа для каждого предмета, который становится частью резервуара, и не тратит время на предметы, которые этого не делают. Таким образом, его ожидаемое время работы ${ Displaystyle О (к (1 + журнал (п / к)))}$,^[2] что оптимально.^[1] В то же время его легко реализовать и эффективно, и он не зависит от случайных отклонений от экзотических или трудно вычисляемых распределений.

Со случайной сортировкой

Если мы свяжем с каждым элементом ввода равномерно сгенерированное случайное число, k элементы с наибольшими (или, что то же самое, наименьшими) связанными значениями образуют простую случайную выборку.^[3] Таким образом, простой отбор проб из коллектора поддерживает k элементы с наибольшими в настоящее время связанными значениями в приоритетная очередь.

(*  S - это поток элементов для выборки  S.Current возвращает текущий элемент в потоке  S.Next переводит поток на следующую позицию  min-priority-queue поддерживает:    Счетчик -> количество элементов в приоритетной очереди    Минимум -> возвращает минимальное значение ключа для всех элементов    Extract-Min () -> Удалить элемент с минимальным ключом    Insert (key, Item) -> Добавляет элемент с указанным ключом *)Резервуар(S[1..?])  ЧАС := новый мин-приоритет-очередь  пока S имеет данные    р := случайный()   // равномерно случайный от 0 до 1, исключая    если ЧАС.Считать < k      ЧАС.Вставлять(р, S.Текущий)    еще      // сохраняем k элементов с наибольшими связанными ключами      если р > ЧАС.Минимум        ЧАС.Извлекать-Мин.()        ЧАС.Вставлять(р, S.Текущий)    S.Следующий  возвращаться Предметы в ЧАС

Ожидаемое время работы этого алгоритма ${ Displaystyle О (п + к журнал к журнал (п / к))}$ и это актуально в основном потому, что его можно легко распространить на предметы с весом.

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

Некоторые приложения требуют, чтобы вероятности выборки элементов соответствовали весам, связанным с каждым элементом. Например, может потребоваться выборка запросов в поисковой системе с весом, равным количеству их выполнений, чтобы выборка могла быть проанализирована на предмет общего воздействия на взаимодействие с пользователем. Пусть вес предмета я быть ${ displaystyle w_ {i}}$, а сумма всех весов будет W. Есть два способа интерпретировать веса, присвоенные каждому элементу в наборе:^[4]

1. В каждом раунде вероятность каждого невыделенный элемент, который будет выбран в этом раунде, пропорционален его весу относительно веса всех невыбранных элементов. Если Икс это текущая выборка, тогда вероятность элемента ${ Displaystyle я notin X}$ быть выбранным в текущем раунде ${ displaystyle textstyle w_ {i} / (W- sum _ {j in X} {w_ {j}})}$.
2. Вероятность включения каждого предмета в случайную выборку пропорциональна его относительному весу, т. Е. ${ displaystyle w_ {i} / W}$. Обратите внимание, что эта интерпретация может быть недостижимой в некоторых случаях, например, ${ Displaystyle к = п}$.

Алгоритм A-Res

Следующий алгоритм был предложен Эфраимидисом и Спиракисом, который использует интерпретацию 1:^[5]

(*  S - это поток элементов для выборки  S.Current возвращает текущий элемент в потоке  S.Weight возвращает вес текущего элемента в потоке  S.Next переводит поток на следующую позицию  Оператор мощности представлен как ^  min-priority-queue поддерживает:    Счетчик -> количество элементов в приоритетной очереди    Minimum () -> возвращает минимальное значение ключа для всех элементов    Extract-Min () -> Удалить элемент с минимальным ключом    Insert (key, Item) -> Добавляет элемент с указанным ключом *)Резервуар(S[1..?])  ЧАС := новый мин-приоритет-очередь  пока S имеет данные    р := случайный() ^ (1/S.Масса)   // random () производит равномерно случайное число в (0,1)    если ЧАС.Считать < k      ЧАС.Вставлять(р, S.Текущий)    еще      // сохраняем k элементов с наибольшими связанными ключами      если р > ЧАС.Минимум        ЧАС.Извлекать-Мин.()        ЧАС.Вставлять(р, S.Текущий)    S.Следующий  возвращаться Предметы в ЧАС

Этот алгоритм идентичен алгоритму, приведенному в Отбор проб из коллектора со случайной сортировкой кроме генерации ключей предметов. Алгоритм эквивалентен присвоению каждому элементу ключа ${ displaystyle r ^ {1 / w_ {i}}}$ куда р - случайное число, а затем выбирая k предметы с самыми большими ключами. Аналогично, более численно стабильный формулировка этого алгоритма вычисляет ключи как ${ displaystyle - ln (r) / w_ {i}}$ и выберите k предметы с самый маленький ключи.^[6]

Алгоритм A-ExpJ

Следующий алгоритм является более эффективной версией A-Res, также данные Эфраимидисом и Спиракисом:^[5]

(*  S - это поток элементов для выборки  S.Current возвращает текущий элемент в потоке  S.Weight возвращает вес текущего элемента в потоке  S.Next переводит поток на следующую позицию  Оператор мощности представлен как ^  min-priority-queue поддерживает:    Count -> количество элементов в очереди с приоритетом    Минимум -> минимальный ключ любого элемента в приоритетной очереди    Extract-Min () -> Удалить элемент с минимальным ключом    Insert (Key, Item) -> Добавляет элемент с указанным ключом *)РезервуарSampleWithJumps(S[1..?])  ЧАС := новый мин-приоритет-очередь  пока S имеет данные и ЧАС.Считать < k    р := случайный() ^ (1/S.Масса)   // random () производит равномерно случайное число в (0,1)    ЧАС.Вставлять(р, S.Текущий)    S.Следующий  Икс := бревно(случайный()) / бревно(ЧАС.Минимум) // это вес, который нужно перепрыгнуть  пока S имеет данные    Икс := Икс - S.Масса    если Икс <= 0      т := ЧАС.Минимум ^ S.Масса      р := случайный(т, 1) ^ (1/S.Масса) // random (x, y) производит равномерно случайное число в (x, y)          ЧАС.Извлекать-Мин.()      ЧАС.Вставлять(р, S.Текущий)      Икс := бревно(случайный()) / бревно(ЧАС.Минимум)    S.Следующий  возвращаться Предметы в ЧАС

Этот алгоритм следует тем же математическим свойствам, которые используются в A-Res, но вместо вычисления ключа для каждого элемента и проверки того, должен ли этот элемент быть вставлен, он вычисляет экспоненциальный переход к следующему элементу, который будет вставлен. Это позволяет избежать создания случайных значений для каждого элемента, что может быть дорогостоящим. Количество требуемых случайных значений сокращается с ${ Displaystyle О (п)}$ к ${ Displaystyle О (к журнал (п / к))}$ в ожидании, где ${ displaystyle k}$ - размер резервуара, а ${ displaystyle n}$ - количество элементов в потоке.^[5]

Алгоритм A-Chao

Следующий алгоритм, предложенный М. Т. Чао, использует интерпретацию 2:^[7]

(*  S имеет элементы для выборки, R будет содержать результат  S [i] .Weight содержит вес для каждой позиции. *)Взвешенный резервуар-Чао(S[1..п], р[1..k])  WSum := 0  // заполняем массив резервуара  за я := 1 к k      р[я] := S[я]      WSum := WSum + S[я].Масса  за я := k+1 к п    WSum := WSum + S[я].Масса    п := S[я].Масса / WSum // вероятность для этого элемента    j := случайный();          // равномерно случайным образом от 0 до 1    если j <= п               // выбираем элемент по вероятности        р[randomInteger(1,k)] := S[я]  // единый выбор в резервуаре для замены

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

Отношение к перемешиванию Фишера – Йетса

Предположим, кто-то хотел нарисовать k случайные карты из колоды карт. Естественным подходом было бы перетасовать колоду, а затем взять верхнюю k В общем случае тасование также должно работать, даже если количество карт в колоде не известно заранее, условие, которое удовлетворяется вывернутой наизнанку версией колоды. Перемешивание Фишера – Йетса:^[8]

(* S имеет вход, R будет содержать выходную перестановку *)Перемешать(S[1..п], р[1..п])  р[1] := S[1]  за я из 2 к п делать      j := randomInteger(1, я)  // включающий диапазон      р[я] := р[j]      р[j] := S[я]

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

(* S имеет элементы для выборки, R будет содержать результат *)Резервуар(S[1..п], р[1..k])  р[1] := S[1]  за я из 2 к k делать      j := randomInteger(1, я)  // включающий диапазон      р[я] := р[j]      р[j] := S[я]  за я из k + 1 к п делать      j := randomInteger(1, я)  // включающий диапазон      если (j <= k)          р[j] := S[я]

Поскольку порядок первого k карты несущественны, первую петлю можно удалить и р может быть инициализирован как первый k элементы ввода. Это дает Алгоритм R.

Статистические свойства

Вероятности выбора коллекторских методов обсуждаются в Chao (1982).^[7] и Тилле (2006).^[9] В то время как вероятности выбора первого порядка равны ${ displaystyle k / n}$ (или, в случае процедуры Чао, к произвольному набору неравных вероятностей), вероятности выбора второго порядка зависят от порядка, в котором записи сортируются в исходном резервуаре. Проблема преодолевается выборка куба метод Девиля и Тилле (2004).^[10]

Ограничения

При отборе проб из резервуара предполагается, что желаемая проба соответствует основная память, часто подразумевая, что k постоянная, не зависящая от п. В приложениях, где мы хотели бы выбрать большое подмножество списка ввода (скажем, третье, т.е. ${ Displaystyle к = п / 3}$), необходимо использовать другие методы. Предложены распределенные реализации этой проблемы.^[11]

Рекомендации