Определение вероятности наступления события, когда оно еще не произошло - PullRequest
Новая
       9

Определение вероятности наступления события, когда оно еще не произошло

1 голос
/ 03 мая 2010

Пользователь посещает мой веб-сайт в момент времени t , и он может или не может щелкнуть по конкретной ссылке, которая мне небезразлична, если он запишет тот факт, что он нажал ссылку, а также продолжительность так как t что они щелкнули по нему, назовите это d .

Мне нужен алгоритм, который позволил бы мне создать такой класс: 

class ClickProbabilityEstimate {
    public void reportImpression(long id);
    public void reportClick(long id);

    public double estimateClickProbability(long id);
}

Каждому показу присваивается уникальный идентификатор , который используется при сообщении о клике, чтобы указать, какому показу принадлежит этот клик.

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

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

Алгоритм должен быть эффективным с точки зрения пространства и времени и, как мы надеемся, делать как можно меньше предположений, при этом быть элегантным. Простота реализации также была бы хорошей. Есть идеи?

Ответы [ 3 ]

2 голосов
/ 03 мая 2010

Предполагая, что вы сохраняете данные о прошлых показах и кликах, все просто: допустим, у вас есть показ, и с тех пор прошло время d '. Вы можете разделить ваши данные на три группы:

  1. Показы, получившие клик менее чем за d '
  2. Показы, которые получили клик после более чем d '
  3. Показы, которые никогда не получали клик

Очевидно, что текущее впечатление не относится к группе (1), поэтому устраните это. Вы хотите, чтобы вероятность была в группе (2), которая тогда равна 

P = N2 / (N2 + N3)

где N2 - количество показов в группе 2, и аналогично для N3.

Что касается фактической реализации, моей первой мыслью было бы сохранить упорядоченный список времени d для прошлых показов, которые получили клики, наряду со счетчиком количества показов, которые никогда не получали щелкните и просто выполните двоичный поиск для d ' в этом списке. Позиция, которую вы найдете, даст вам N1, а затем N2 - длина списка минус N1.

Если вам не нужна идеальная гранулярность, вы можете вместо этого сохранить прошедшее время в виде гистограммы, то есть список, который содержит в каждом элементе list[n] количество показов, которые получили клик после как минимум n но менее n+1 минут. (Или секунды, или любой другой временной интервал, который вам нравится). В этом случае вы, вероятно, захотите сохранить общее количество кликов в качестве отдельной переменной, чтобы вы могли легко вычислить N2.

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

1 голос
/ 03 мая 2010
0 голосов
/ 05 мая 2010

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

Надеюсь, это поможет.

...