Случайный образец набора данных

Question

я наткнулся на Q, который был задан в одном из интервью ..

Q - Представьте, вы получаете действительно большой поток элементов данных (запросы на Google поиск в мае, продукты покупали в Walmart в рождественский сезон, имена в телефонной книге, что угодно). Ваша цель - эффективно возвращать случайную выборку из 1000 элементов, равномерно распределенных из исходного потока. Как бы вы это сделали?

Ищу -

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

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

Answer 1

Двоичный образец/образец не может быть правильным ответом. Предположим, вы хотите пробовать 1000 строк, и вы делаете это с помощью броска монеты .. Это будет означать, что примерно после посещения 2000 строк .. вы сделаете .. Как насчет остальной струны?

Я прочитал этот пост - http://gregable.com/2007/10/reservoir-sampling.html

, который отвечает на этот Q вполне ясно ..

Позвольте мне резюме здесь -

SIMPLE РЕШЕНИЕ

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

ПЛАСТ ДОЗИРОВОЧНОГО

Сделать резервуар (массив) 1000 элементов и заполнить его первые 1000 элементов в потоке. Начните с i = 1,001. С какой вероятностью после 1001-го шага должен быть элемент 1 001 (или любой элемент в этом отношении) в наборе из 1000 элементов? Ответ прост: 1,000/1,001. Итак, сгенерируйте случайное число от 0 до 1, а если оно меньше 1000/1001, вы должны взять элемент 1,001. Если вы решите добавить его, замените любой элемент (например, элемент № 2) в резервуаре, выбранном случайным образом. Элемент №2 определенно находится в резервуаре на шаге 1000, и вероятность его удаления - это вероятность того, что элемент 1001 будет выбран, умноженный на вероятность того, что № 2 будет выбрана случайным образом в качестве замещающего кандидата. Эта вероятность составляет 1000/1,001 * 1/1000 = 1/1,001. Таким образом, вероятность того, что №2 сохранится в этом раунде, равна 1 - это или 1000/1,001.

Это может быть расширено для i-го раунда - сохраните i-й элемент с вероятностью 1000/i, и если вы решите сохранить его, замените случайный элемент из резервуара. Вероятность того, что любой элемент до этого шага находится в резервуаре, равна 1000/(i-1). Вероятность их удаления равна 1000/i * 1/1000 = 1/i. Вероятность того, что каждый элемент склеивается, учитывая, что они уже находятся в резервуаре, равна (i-1)/i, и, следовательно, общая вероятность существования элементов в резервуаре после i раундов составляет 1000/(i-1) * (i- 1)/i = 1000/i.

Answer 2

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

Выбор проб воды - это путь, хотя анализ с @abipc кажется в правильном направлении, но не совсем правильный.

Нам легче понять, что мы хотим. Представьте, что у вас есть N элементов (N неизвестно), и вам нужно выбрать 1000 элементов. Это означает, что нам нужно настроить схему выборки, где вероятность того, что любой элемент присутствует в выборке, составляет точно 1000/N, поэтому каждый элемент имеет такую ​​же вероятность быть в выборке (не предпочтение ни одному элементу, основанному на его позиции на оригинале список). Схема, упомянутая @abipc, отлично работает, вычисления вероятности идут следующим образом:

После первого шага у вас есть 1001 элемент, поэтому нам нужно выбрать каждый элемент с вероятностью 1000/1001. Мы выбираем 1001-й элемент с такой вероятностью, чтобы это было хорошо. Теперь нам также нужно показать, что каждый другой элемент также имеет ту же вероятность быть в выборке.

р (любой другой элемент, оставаясь в образце) = [1 - р (этот элемент удален из образца)]

= [ 1 - p(1001st element is selected) * p(the element is picked to be removed) 
    = [ 1 - (1000/1001) * (1/1000)] = 1000/1001 

Отлично, так что теперь мы доказали, каждый элемент имеет вероятность того, что 1000/1001 будет в выборке. Этот точный аргумент может быть расширен для i-го шага с использованием индукции.

Answer 3

Как я знаю, такой класс алгоритмов называется алгоритмом выборки коллектора.

Я знаю, что один его из Datamining, но не знаю его название:

1. Collect первые элементы S в вашей памяти с max.size равна S.
2. Пусть следующий элемент поток имеет номер N.
3. С вероятностью S/N улавливайте новый элемент, иначе отбросьте его
4. Если вы зацепили элемент N, замените один из элементов в одном комплекте S, подобрав его равномерно.
5. N = N + 1, получают следующий элемент, Гота 1

Это может быть теоретически доказано, что на любой шаге такого потока обработки вашего хранения с размером S содержит элементы с равной S/вероятности N_you_have_seen.

Так, например, S = 10;

N_you_have_seen = 10^6

S - это конечное число; N_you_have_seen - может быть бесконечным числом;