Выборка по агрегированному набору данных

Question

Ввод - это набор данных, в котором каждая строка содержит событие, скажем, щелчок.Идентификатор участника является уникальным идентификатором.Пример данных: M1 100 M2 100 M3,50 M4,50 Цель состоит в том, чтобы отобрать 1% кликов, где общее количество кликов дается путем суммирования всех кликов по всем идентификаторам участников.Если я хочу выбрать 1% для выборочного набора данных, я хочу применить метод, который выбирает количество кликов случайным образом и производит 1% или 3 клика, что-то вроде: M1, 1 M2, 1 M4, 1 или некоторая другая комбинация, гдесумма кликов по членам составляет 1%.

Один из основных подходов состоит в том, чтобы разбить все записи во входных данных и использовать в качестве данных, а затем выбрать 1% из них.Это было бы очень медленно / неэффективно, если бы миллионы участников имели количество кликов в сотню раз.Ищете лучшее решение, где не требуется взрыв данных?

Answer 1

Кажется очевидным, что нужно сделать выборку от пользователей, с вероятностью каждого пользователя, пропорциональной количеству кликов для них, а затем выбрать клик равномерно случайным образом для данного пользователя.В приведенном вами примере это означает, что нужно выбрать пользователей с вероятностями 100/300, 100/300, 50/300 и 50/300, а затем выбрать щелчок для данного пользователя.

Вы можете произвести выборку пропорциональновесов (100/300, 100/300, 50/300, 50/300 здесь), генерируя случайное число p между 0 и 1, а затем находя наименьшее k (k = 1, 2, 3, ... # веса)так что сумма весов от 1 до k меньше или равна p.

Эффективный способ найти k - создать список частичных сумм весов (т. Е. 0, w1, w1 + w2, w1 + w2 + w3, ...), а затем выполнить бинарный поиск (не линейный) в этом списке.Бинарный поиск даст время на выборку, которое логарифмически увеличивается с количеством весов (пользователей в вашем случае), в то время как линейный поиск дает линейный рост.

РЕДАКТИРОВАТЬ: пример.Дано n = 10 пользователей с N = (100, 160, 200, 20, 500, 550, 400, 300, 120, 80) соответственно.Всего событий = 2430, а весовые коэффициенты w = (10/243, 16/243, 20/243, 2/243, 50/243, 55/243, 40/243, 10/81, 4/81, 8/243),Частичные суммы весов S = (0, 10/243, 26/243, 46/243, 16/81, 98/243, 17/27, 193/243, 223/243, 235/243, 1).(ПРИМЕЧАНИЕ: раньше я ошибался; последовательность должна быть (0, w1, w1 + w2, w1 + w2 + w3, ..., w1 + ... + w [n - 1], 1).)

Учитывая случайное число x между 0 и 1, найти (путем бинарного поиска) индекс частичной суммы, такой что S [i] <= x <S [i + 1].Затем выберите событие случайным образом из N [i] событий для пользователя i. </p>

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

EDIT2: исправлена ​​формула для списка частичных сумм.Список имеет n + 1 элементов;поиск i такой, что S [i] <= x <S [i + 1], следовательно, даст i = 1, 2, 3, ..., n.Последний элемент, 1, никогда не будет выбран, при условии, что случайное число всегда меньше 1. </p>