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

Резюме

Как мудро заметил Тед Джасперс, методология, которую я описал в первоначальном предложении еще в 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 в двух строках разметки Twig:

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

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

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

---

Исходное предложение

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

p = (p + t) / 2

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

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

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

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

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

Пример работы алгоритма за 1 день: http://jsfiddle.net/q2UCn/
Пример работы алгоритма за период 1 год: http://jsfiddle.net/tWU9y/

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

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