Простой алгоритм популярности

Резюме

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

Это единственное значение популярности представляет все прошлые события (в пределах используемого типа данных), но более старые события начинают иметь значение в геометрической прогрессии, поскольку новые события учитываются. Этот алгоритм будет адаптироваться к различным масштабам времени и будет реагировать на различные объемы трафика., Каждый раз, когда происходит событие, новое значение популярности можно рассчитать по следующей формуле:

(a * t) + ((1 - a) * p)

a - коэффициент от 0 до 1 (более высокие значения быстрее сбрасывают со счетов старые события)
t - текущая метка времени
p - текущее значение популярности (например, хранится в базе данных)

Разумные значения для a будут зависеть от вашего приложения. Хорошей отправной точкой является a=2/(N+1), где N - это количество событий, которые должны существенно повлиять на результат. Например, на веб-сайте с низким трафиком, где событие представляет собой просмотр страницы, можно ожидать сотен просмотров страниц в течение нескольких дней. Выбор N=100 (a≈0.02) был бы разумным выбором. Для сайта с большим трафиком вы можете ожидать миллионы просмотров страниц в течение нескольких дней, и в этом случае N=1000000 (a≈0.000002) будет более разумным. Значение для a, вероятно, будет постепенно корректироваться со временем.

Чтобы проиллюстрировать, насколько прост этот алгоритм популярности, вот пример того, как его можно реализовать в Craft CMS в 2 строки разметки Twig:

{% set popularity = (0.02 * date().timestamp) + (0.98 * entry.popularity) %}
{% do entry.setFieldValue("popularity", popularity) %}

Обратите внимание, что нет необходимости создавать новые таблицы базы данных или хранить бесконечные записи событий, чтобы рассчитать популярность.

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

Оригинальное предложение

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

p = (p + t) / 2

Здесь p - это значение популярности, хранящееся в базе данных, а t - текущая временная метка. Когда элемент создается впервые, p необходимо инициализировать. Существует два возможных метода инициализации:

Инициализируйте p текущей меткой времени t
Инициализируйте p средним значением всех p значений в базе данных

Обратите внимание, что метод инициализации (1) дает недавно добавленным элементам явное преимущество перед историческими элементами, таким образом добавляя элемент релевантности. С другой стороны, метод инициализации (2) рассматривает новые элементы как равные по сравнению с историческими элементами.

Допустим, вы используете метод инициализации (1) и инициализируете p с текущей отметкой времени. Когда элемент получает свой первый голос, p становится средним значением времени создания и времени голосования. Таким образом, значение популярности p по-прежнему представляет действительную временную метку (при условии округления до ближайшего целого числа), но фактическое время, которое оно представляет, абстрагировано.

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

Пример работы алгоритма в течение 1 дня: http://jsfiddle.net/q2UCn/
Пример работы алгоритма в течение 1 года: http://jsfiddle.net/tWU9y/

Если вы ожидаете, что голоса будут непрерывно передаваться с интервалом менее секунды, вам потребуется использовать метку времени микросекунды, такую как функция PHP microtime(). В противном случае будет работать стандартная метка времени UNIX, например функция PHP time().

Теперь на мой вопрос: видите ли вы какие-либо серьезные недостатки этого подхода?

Ответ 1

Предложенный алгоритм является хорошим подходом и является частным случаем экспоненциальной скользящей средней, где альфа = 0,5:

p = alpha*p + (1-alpha)*t = 0.5*p + 0.5*t = (p+t)/2    //(for alpha = 0.5)

Ответ 2

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

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

Представьте, что мы берем время и разбиваем его на дискретные значения временной метки от 100 до 1000. Предположим, что при t = 100 оба A и B (два элемента) имеют одинаковые P = 100.

    A gets voted 7 times on 200, 300, 400, 500, 600, 700 and 800
resulting on a final Pa(800) = 700 (aprox).

    B gets voted 4 times on 300, 500, 700 and 900 
resulting on a final Pb(900) = 712 (aprox).

Когда t = 1000, оба A и B получают голоса, поэтому:

Pa(1000) = 850 with 8 votes
Pb(1000) = 856 with 5 votes

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

РЕДАКТИРОВАТЬ ВКЛЮЧЕНИЕ МОДЕЛИРОВАНИЯ

OP создал приятную скрипту, которую я изменил, чтобы получить следующие результаты:

http://jsfiddle.net/wBV2c/6/

Item A receives one vote each day from 1970 till 2012 (15339 votes)
Item B receives one vote each month from Jan to Jul 2012 (7 votes)

The result: B is more popular than A.

Ответ 3

Я вижу одну проблему, только подсчет последних 24 голосов.

p_i+1 = (p + t) / 2

За два голоса мы имеем

p2 = (p1 + t2) / 2 = ((p0 + t1) /2 + t2 ) / 2 = p0/4 + t1/4 + t2/2

Расширяя это за 32 голоса, вы получите:

p32 = t*2^-32 + t0*2^-32 + t1*2^-31 + t2*2^-30 + ... + t31*2^-1

Итак, для подписанных 32-битных значений t0 не влияет на результат. Поскольку t0 делится на 2 ^ 32, это ничего не даст p32.

Если у нас есть два элемента A и B (независимо от того, насколько велики различия), если они оба получат одинаковые 32 голоса, они будут иметь такую же популярность. Итак, вы вернулись к истории всего за 32 голоса. Нет разницы в 2032 и 32 голосах, если последние 32 голоса одинаковы.

Если разница меньше одного дня, они будут равны после 17 голосов.

Ответ 4

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

Ответ 5

Я не думаю, что рассмотренная выше логика сработает. p_i + 1 = (p_i + t)/2

Статью A просматривают на отметках времени: 70, 80, 90 популярности (Статья A): 82,5

Статью B просматривают на временных отметках: 50, 60, 70, 80, 90 популярности (Статья B): 80,625

В этом случае популярность Статьи B должна была быть больше. Во-первых, статья B рассматривалась совсем недавно, как статья A, а во-вторых, она также рассматривалась чаще, чем статья A.