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

Резюме

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

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


algorithm popularity
person David Jones    schedule 20.06.2012    source источник
comment
Если вы позволяете людям различать элементы, это не требует только сохранения p в базе данных. Вы также должны хранить записи обо всех когда-либо сделанных лайках. В противном случае пользователь может «Мне нравится», затем «Не нравится», затем «Нравится», затем «Не нравится», снова и снова, чтобы увеличить свой голос. Как вы сказали, вы хотите изменить p элемента только тогда, когда он получит свой первый голос. Это означает, что вам нужно отслеживать все голоса.   -  person Al Sweigart    schedule 08.07.2017
comment
@AlSweigart - хороший аргумент. Этот алгоритм, вероятно, подходит только для систем однонаправленного голосования (например, просмотр страницы - это один голос в положительном направлении). Вероятно, он менее совместим с системами двунаправленного голосования.   -  person David Jones    schedule 11.07.2017

Ответы (5)


arrow_upward
4
arrow_downward

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

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

Способ настроить тот факт, что предлагаемое решение для альфа = 0,5 имеет тенденцию отдавать предпочтение недавним голосам (как отмечает daniloquio), состоит в том, чтобы выбрать более высокие значения для альфа (например, 0,9 или 0,99). Обратите внимание, что применение этого к тесту, предложенному daniloquio, не работает, однако, потому что, когда альфа увеличивается, алгоритму требуется больше «времени» для урегулирования (поэтому массивы должны быть длиннее, что часто верно в реальных приложениях. ).

Таким образом:

  • для альфа = 0,9 алгоритм усредняет примерно последние 10 значений
  • для альфа = 0,99 алгоритм усредняет примерно последние 100 значений
  • для альфа = 0,999 алгоритм усредняет примерно последние 1000 значений
  • и Т. Д.
person Ted Jaspers    schedule 03.08.2018
comment
Отличный ответ! Одно но: в статье говорится, что более высокое значение α приводит к более быстрому обесцениванию старых наблюдений, поэтому не должны ли значения альфа работать в противоположном направлении, как вы описали? - person David Jones; 10.09.2019

arrow_upward
10
arrow_downward

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

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

Представьте, что мы берем время и разбиваем его на дискретные значения временной метки в диапазоне от 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.

person daniloquio    schedule 20.06.2012
comment
Отличный анализ! Вы правы в том, что алгоритм действительно отдает предпочтение более свежим действиям, которые могут быть или нежелательны в зависимости от приложения. На мой взгляд, такое поведение подходит для большинства приложений. Тем не менее, это небольшая цена за простоту реализации. - person David Jones; 21.06.2012
comment
@danielfaraday: обратите внимание, что если вы используете 32-битные типы, вы можете переполниться, что приведет к временному снижению рейтинга при обновлении радикально. - person Mooing Duck; 21.06.2012
comment
@MooingDuck: Я не понимаю. Предполагается, что P будет округлено, поэтому размер всегда будет равен размеру метки времени (независимо от того, является ли степень детализации метки времени в секундах, миллисекундах или микросекундах). - person David Jones; 21.06.2012
comment
daniloquio: подумав, я не уверен, насколько полезен этот пример. Разница в общем количестве голосов слишком мала, чтобы сделать верный вывод. Я повторю комментарий, сделанный мной для btilly: предположим, что элемент A создан в 1912 году и получает один голос каждый год до 2012 года (всего 100 голосов). Чтобы элемент B превзошел элемент A в последнюю секунду с одним голосом, он должен был быть создан совсем недавно, в 2009 году! Это 97 лет спустя! Вот доказательство: jsfiddle.net/wBV2c. - person David Jones; 21.06.2012
comment
@danielfaraday, прежде всего, вам лучше не использовать свой алгоритм для голосов до 1970 года, иначе отрицательные временные метки доставят вам реальную боль. Вы ошибаетесь здесь, потому что дело не в том, чтобы один голос победил всех: дело в том, что новый горячий пункт быстро побьет исторических лидеров. Взгляните на мою правку в ответе. - person daniloquio; 21.06.2012
comment
@daniloquio: да, вы правы насчет того, что началось до 1970 года - не очень хорошая идея. Однако в вашем коде были ошибки. Я исправил ошибки, и результат такой, как и следовало ожидать - элемент A более популярен, чем элемент B: jsfiddle.net / wBV2c / 8. - person David Jones; 21.06.2012
comment
Фактически, даже если элемент B получает голосование каждый день с января 2012 г. по июль 2012 г., он все равно не побеждает элемент A: jsfiddle.net/wBV2c/9. - person David Jones; 21.06.2012
comment
@danielfaraday в своем коде вы вычисляете P, просто добавляя t вместо выполнения (p + t) / 2. Я изменил ваш код, чтобы вычислить P в соответствии с вашим алгоритмом, и добавил голосование за B с января по декабрь; угадайте, каков результат. jsfiddle.net/wBV2c/10 Если мой ответ даже не был вам полезен (мой ответ - единственный без +1), то я думаю, что мы закончили с этим обсуждением. Добрый день. - person daniloquio; 21.06.2012
comment
Ой! Ты прав. Вот исправленный код для примера месяца: jsfiddle.net/wBV2c/11. Пункт А в этом случае выигрывает. Вот исправленный код для дневного примера: jsfiddle.net/wBV2c/12. Пункт B в этом случае выигрывает. Это поведение, которое я ожидал бы от алгоритма популярности. Если один элемент внезапно перестанет получать голоса (элемент A в этом примере), а другой элемент начнет получать голоса с той же скоростью (элемент B в этом примере), я ожидаю, что второй (элемент B) будет самым популярным. Ваш ответ однозначно пригодится! +1 - person David Jones; 21.06.2012

arrow_upward
3
arrow_downward

Я вижу одну проблему, учитываются только последние ~ 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 голосов.

person Ishtar    schedule 21.06.2012
comment
Это неверно. Я доказываю, что вы ошибались здесь: jsfiddle.net/q2UCn. Это фактический расчет точного анализа, который вы описали выше (элемент A получил 217 голосов в тот же день, когда элемент B получил 17 голосов). Я также провел этот анализ по 25 голосам за 1 год (jsfiddle.net/tWU9y), который дал аналогичный результат. - person David Jones; 21.06.2012
comment
Ой, ты прав. Я неправильно интерпретировал результаты. Починил это. - person Ishtar; 21.06.2012
comment
Иштар: это правильно. Если два элемента получают по 32 голоса точно в одно и то же время, то при округлении значение их популярности будет одинаковым. Вот доказательство: jsfiddle.net/c4RVr. Однако вероятность того, что это произойдет, чрезвычайно мала, если голоса не поступают стабильно с субсекундными интервалами. В этом случае вы можете просто использовать микросекундную метку времени (например, функцию PHP microtime()). Это решает проблему. Вот доказательство: jsfiddle.net/k8HXu. Это просто зависит от того, сколько трафика вы ожидаете. - person David Jones; 21.06.2012
comment
@danielfaraday - Даже для одного пункта после 32 голосов вся история теряется. Вы отслеживаете только последние 32 голоса. Будет ли это проблемой, решать вам. Если вы используете microtime (или, скажем, 64-битный), вам нужно больше голосов, чтобы очистить историю, но все же голосование через несколько секунд имеет больший эффект, чем все голоса до 32-го последнего голосования. - person Ishtar; 21.06.2012
comment
Спасибо, Иштар. Очень полезные комментарии. - person David Jones; 21.06.2012
comment
@danielfaraday - Пожалуйста :). Вот тестовый jsfiddle.net/cyC7R с непопулярным и чрезвычайно популярным предметом, оба получают 32 случайных голосов в течение года. Разница исчезает, вы можете попробовать дать A 'toc' или B 0, это не имеет значения. Учитываются только последние! - person Ishtar; 21.06.2012

arrow_upward
1
arrow_downward

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

person btilly    schedule 20.06.2012
comment
Но отметка времени 1 недавнего голосования не будет принята за чистую монету. Вместо этого оно будет усреднено с более ранним голосованием. Это, вероятно, приведет к тому, что элемент будет оценен ниже, чем элемент с 100 голосами (если только все 100 голосов не произошли очень давным-давно). - person David Jones; 21.06.2012
comment
Кроме того, если 100 голосов действительно произошли очень давным-давно, определение популярности, зависящее от времени, потребовало бы, чтобы элемент, набравший 100 голосов, должен иметь рейтинг ниже, чем 1 недавнее голосование. - person David Jones; 21.06.2012
comment
+1 за последнее предложение, я согласен с вами в предположении, что некоторые странные, но редкие результаты приемлемы. - person daniloquio; 21.06.2012
comment
Допустим, элемент A создан в 1912 году и получает один голос каждый год до 2012 года (всего 100 голосов). Чтобы элемент B превзошел элемент A в последнюю секунду с одним голосом, он должен был быть создан совсем недавно, в 2009 году! Это 97 лет спустя! Вот доказательство: jsfiddle.net/wBV2c. Таким образом, ваш комментарий недействителен. Элемент с 100 голосами будет иметь более высокое значение популярности, даже если элемент с 1 голосом получил этот 1 голос очень недавно. Это на самом деле доказывает, насколько на самом деле надежен этот простой маленький алгоритм. - person David Jones; 21.06.2012

arrow_upward
0
arrow_downward

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

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

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

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

person RAJIV MITTAL    schedule 27.04.2018
comment
В вашем примере вы ожидаете, что популярность A и B будет равна t → ∞, что и происходит. Однако, учитывая исходное условие, что статья A новее, чем статья B, статья A всегда будет иметь небольшое преимущество над статьей B. Как уже говорилось, этот алгоритм отдает предпочтение новому контенту над старым контентом. Я думаю, что это на самом деле довольно хорошо отражает реальные жизненные ситуации - новые статьи, как правило, более актуальны по сравнению со старыми статьями, поэтому при прочих равных условиях более новая статья должна победить. Помните, что цель этого алгоритма - не быть лучшим, а, скорее, самым простым. - person David Jones; 30.04.2018