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

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

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

Простой и популярный, но медленный алгоритм, алгоритм R , был создан Джеффри Виттером. ^[1]

Инициализируем массив, индексированный от до , содержащий первые k элементов ввода . Это резервуар . ${\displaystyle R}$${\displaystyle 1}$${\displaystyle к}$${\displaystyle x_{1},...,x_{k}}$

Для каждого нового ввода сгенерировать случайное число j равномерно по . Если , то установить , в противном случае отбросить . ${\displaystyle x_{i}}$${\displaystyle \{1,...,я\}}$${\displaystyle j\in \{1,...,k\}}$${\displaystyle R[j]:=x_{i}.}$${\displaystyle x_{i}}$

Возврат после обработки всех входных данных.${\displaystyle R}$

Этот алгоритм работает по индукции .${\displaystyle i\geq k}$

Хотя концептуально он прост и понятен, этот алгоритм должен генерировать случайное число для каждого элемента входных данных, включая отброшенные элементы. Асимптотическое время работы алгоритма , таким образом, составляет . Генерация такого количества случайности и линейного времени работы приводит к тому, что алгоритм становится неоправданно медленным, если входная популяция велика.${\displaystyle O(n)}$

Это алгоритм R, реализованный следующим образом:

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

Если мы генерируем случайные числа независимо, то индексы наименьшего из них представляют собой равномерную выборку k-подмножеств . ${\displaystyle n}$${\displaystyle u_{1},...,u_{n}\sim U[0,1]}$${\displaystyle k}$${\displaystyle \{1,...,n\}}$

Этот процесс можно осуществить, не зная :${\displaystyle n}$

Сохраните наименьшее из того, что было замечено до сих пор, а также , индекс наибольшего среди них. Для каждого нового сравните его с . Если , то отбросьте , сохраните и установите в качестве индекса наибольшего среди них. В противном случае отбросьте , и установите .${\displaystyle k}$${\displaystyle u_{1},...,u_{i}}$${\displaystyle w_{i}}$${\displaystyle u_{i+1}}$${\displaystyle u_{w_{i}}}$${\displaystyle u_{i+1}<u_{w_{i}}}$${\displaystyle u_{w_{i}}}$${\displaystyle u_{i+1}}$${\displaystyle w_{i+1}}$${\displaystyle u_{i+1}}$${\displaystyle w_{i+1}=w_{i}}$

Теперь соедините это с потоком входных данных . Каждый раз, когда что-то принимается, сохраняйте соответствующее . Каждый раз, когда что-то отбрасывается, отбрасывайте соответствующее .${\displaystyle x_{1},...,x_{n}}$${\displaystyle u_{i}}$${\displaystyle x_{i}}$${\displaystyle u_{i}}$${\displaystyle x_{i}}$

Этот алгоритм все еще нуждается в случайных числах, поэтому требует времени. Но его можно упростить.${\displaystyle O(n)}$${\displaystyle O(n)}$

Первое упрощение: нет необходимости проверять новые данные по одному, поскольку вероятность того, что следующее принятие произойдет в , то есть интервал принятия следует геометрическому распределению .${\displaystyle u_{i+1},u_{i+2},...}$${\displaystyle u_{i+l}}$${\displaystyle (1-u_{w_{i}})^{l-1}\,u_{w_{i}}=(1-u_{w_{i}})^{l-1}-(1-u_{w_{i}})^{l}}$${\displaystyle l}$

Второе упрощение: нет необходимости помнить весь массив самых маленьких из тех, что были замечены до сих пор, а просто самые большие из них. Это основано на трех наблюдениях:${\displaystyle k}$${\displaystyle u_{1},...,u_{i}}$${\displaystyle w}$

• Каждый раз, когда выбирается новый элемент для ввода в хранилище, равномерно случайная запись в хранилище отбрасывается.${\displaystyle x_{i+1}}$
• ${\displaystyle u_{i+1}\sim U[0,w]}$
• ${\displaystyle w_{i+1}}$имеет такое же распределение , как , где все независимо. Это может быть выбрано путем первого отбора проб , а затем взятия .${\displaystyle \max\{u_{1},...,u_{k}\}}$${\displaystyle u_{1},...,u_{k}\sim U[0,w]}$${\displaystyle u\sim U[0,1]}$${\displaystyle w\cdot u^{\frac {1}{k}}}$

Это алгоритм L , ^[2], который реализован следующим образом:

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

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

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

(*  S — поток элементов для выборки  S.Current возвращает текущий элемент в потоке  S.Next перемещает поток на следующую позицию  min-priority-queue поддерживает:  Count -> количество элементов в очереди с приоритетом  Minimum -> возвращает минимальное значение ключа всех элементов  Extract-Min() -> Удаляет элемент с минимальным ключом  Insert(key, Item) -> Добавляет элемент с указанным ключом *) ReservoirSample ( S [ 1 .. ? ]) H := new min - priority - queue пока S имеет данные r := random () // равномерно случайно между 0 и 1, исключая , если H . Count < k H . Insert ( r , S . Current ) else // сохраняет k элементов с наибольшими связанными ключами, если r > H . Minimum H . Extract - Min () H . Insert ( r , S . Current ) end S . Next end return items in H end                                  

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

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

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

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

(*  S — поток элементов для выборки  S.Current возвращает текущий элемент в потоке  S.Weight возвращает вес текущего элемента в потоке  S.Next перемещает поток на следующую позицию  Оператор возведения в степень представлен как ^  min-priority-queue поддерживает:  Count -> количество элементов в очереди с приоритетом  Minimum() -> возвращает минимальное значение ключа всех элементов  Extract-Min() -> удаляет элемент с минимальным ключом  Insert(key, Item) -> добавляет элемент с указанным ключом *) ReservoirSample ( S [ 1 .. ? ]) H := new min - priority - queue пока S имеет данные r := random () ^ ( 1 / S . Weight ) // random() создает равномерно случайное число в диапазоне (0,1) if H . Count < k H . Insert ( r , S . Current ) else // сохраняет k элементов с наибольшими связанными ключами if r > H . Minimum H . Extract - Min () H . Insert ( r , S . Current ) end end S . Следующий конец возврата элементов в H конец                                     

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

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

(*  S — поток элементов для выборки  S.Current возвращает текущий элемент в потоке  S.Weight возвращает вес текущего элемента в потоке  S.Next перемещает поток на следующую позицию  Оператор возведения в степень представлен как ^  min-priority-queue поддерживает:  Count -> количество элементов в приоритетной очереди  Minimum -> минимальный ключ любого элемента в приоритетной очереди  Extract-Min() -> удаление элемента с минимальным ключом  Insert(Key, Item) -> добавление элемента с указанным ключом *) ReservoirSampleWithJumps ( S [ 1 .. ? ]) H := new min - priority - queue, пока S имеет данные и H . Count < k r := random () ^ ( 1 / S . Weight ) // random() создает равномерно случайное число в диапазоне (0,1) H . Insert ( r , S . Current ) S . Следующий конец X := log ( random ()) / log ( H.Minimum ) // это величина веса, через которую нужно перепрыгнуть, пока S имеет данные X : = X - S.Weight если X < = 0 t := H.Minimum ^ S.Weight r : = random ( t , 1 ) ^ ( 1 / S.Weight ) // random ( x , y ) выдает равномерно случайное число в ( x , y ) H.Extract - Min ( ) H.Insert ( r , S.Current )                                                          X : = log ( random ( ) ) / log ( H.Minimum ) end S.Next end return items in H end​           

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

Предупреждение: следующее описание неверно, см. оригинальную статью Чао и обсуждение здесь.

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

(*  S содержит элементы для выборки, R будет содержать результат  S[i].Weight содержит вес для каждого элемента *) WeightedReservoir - Chao ( S [ 1 .. n ] , R [ 1 .. k ]) WSum := 0 // заполнить массив резервуара for i := 1 to k R [ i ] := S [ i ] WSum := WSum + S [ i ] . Вес end for i := k + 1 to n WSum := WSum + S [ i ] . Вес p := S [ i ] . Вес / WSum // вероятность для этого элемента j := random () ; // равномерно случайно между 0 и 1, если j <= p // выбрать элемент в соответствии с вероятностью R [ randomInteger ( 1 , k )] := S [ i ] // равномерный выбор в резервуаре для замены end end end                                                    

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

Обратите внимание, что Чао не указывает, как выбирать первые k элементов. Он просто предполагает, что у нас есть какой-то другой способ выбирать их пропорционально их весу. Чао: "Предположим, что у нас есть план выборки фиксированного размера относительно S_k в момент времени A ; такой, что его вероятность включения первого порядка X_t равна π(k; i) ".

Подобно другим алгоритмам, можно вычислить случайный вес jи вычесть значения вероятностной массы элементов, пропуская их, пока j > 0, уменьшая количество случайных чисел, которые необходимо сгенерировать. ^[4]

(*  S имеет элементы для выборки, R будет содержать результат  S[i].Weight содержит вес для каждого элемента *) WeightedReservoir - Chao ( S [ 1 .. n ] , R [ 1 .. k ]) WSum := 0 // заполнить массив резервуара для i := 1 до k R [ i ] := S [ i ] WSum := WSum + S [ i ] . Weight end j := random () // равномерно случайно между 0 и 1 pNone := 1 // вероятность того, что ни один элемент не был выбран до сих пор (в этом прыжке) для i := k + 1 до n WSum := WSum + S [ i ] . Weight p := S [ i ] . Вес / WSum // вероятность для этого элемента j -= p * pNone pNone := pNone * ( 1 - p ) если j <= 0 R [ randomInteger ( 1 , k )] := S [ i ] // равномерный выбор в резервуаре для замены j = random () pNone := 1 end end end                                                                         

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

(* S содержит входные данные, R будет содержать выходную перестановку *) Shuffle ( S [ 1 .. n ] , R [ 1 .. n ]) R [ 1 ] := S [ 1 ] for i from 2 to n do j := randomInteger ( 1 , i ) // включающий диапазон R [ i ] := R [ j ] R [ j ] := S [ i ] end end                       

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

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

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

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