Сервис дарения вещей и услуг
55,95
рейтинг
2 мая 2012 в 17:38

Разработка → Как правильно сортировать контент на основе оценок пользователей перевод



В оригинале название звучит как «How Not To Sort By Average Rating». Я подумал, что дословный перевод «Как не сортировать по усреднённому рейтингу» будет малопонятен и хуже отражает содержание статьи.

Постановка проблемы


Вы занимаетесь веб программированием. У вас есть пользователи, которые оценивают контент на вашем сайте. Вы хотите разместить высоко оцененный контент наверху, а низко оцененный — внизу. Для этого на основе пользовательских оценок вам нужно вычислить некий «рейтинг».

Неправильное решение №1

Рейтинг= (Число положительных оценок) - (Число отрицательных оценок)


Почему это неправильно. Предположим, у одного объекта есть 600 положительных оценок и 400 отрицательных, т.е. в итоге 60% положительных. Предположим далее, что у другого объекта 5500 положительных оценок и 4500 отрицательных, т.е. в итоге 55% положительных. Данный алгоритм разместит второй объект (с рейтингом 1000, но всего с 55% положительных оценок) выше первого объекта (с рейтингом 200 и с 60% положительных оценок). Неправильно.

Сайты, которые допускают подобную ошибку: Urban Dictionary
Urban Dictionary rating

Неправильное решение №2

Рейтинг = Средняя оценка = (Число положительных оценок) / (Число всех оценок)

Почему это неправильно. Средняя оценка хорошо работает, если у вас всегда куча оценок. Но предположим, что у одного объекта 2 положительные оценки и 0 отрицательных. Предположим далее, что у второго объекта 100 положительных оценок и 1 отрицательная. Данный алгоритм разместит второй объект (с кучей положительных оценок) ниже первого объекта (с очень малым числом положительных оценок). Это неправильно.

Сайты, которые допускают подобную ошибку: Amazon
Amazon average rating

Правильное решение


Рейтинг = Нижняя граница доверительного интервала Вильсона (Wilson) для параметра Бернулли

Почему это правильно. Нам необходимо найти баланс между долей положительных оценок и неопределенностью малого числа наблюдений. К счатью, математический аппарат для решения этой проблемы был разработан в 1927 году Эдвином Вильсоном. Мы хотим знать следующее: «Обладая набором данных мне оценок, можно ли с вероятностью 95% сказать, какова будет „реальная“ доля положительных оценок?». Вильсон дает ответ. Учитывая только положительные и отрицательные оценки (т.е. не беря во внимание 5-бальную систему оценивания), нижняя граница доли положительных оценок вычисляется по следующей формуле:


Используйте минус там, где написано плюс/минус, чтобы вычислить нижнюю границу. Здесь — доля положительных оценок, zα/2 есть квантиль* (1-α/2) стандартного нормального распределения, и n есть общее число оценок. Аналогичнная формула, примененная на Ruby:
*Кванти́ль в математической статистике — значение, которое заданная случайная величина не превышает с фиксированной вероятностью. Wikipedia

require 'statistics2'

def ci_lower_bound(pos, n, confidence)
    if n == 0
        return 0
    end
    z = Statistics2.pnormaldist(1-(1-confidence)/2)
    phat = 1.0*pos/n
    (phat + z*z/(2*n) - z * Math.sqrt((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n)
end

Тут pos — число положитеьных оценок, n — общее число оценок, а confidence задаёт статистически доверительный уровень: установите его в 0.95, чтобы с 95% вероятностью рассчитывать на правильность нижней границы, в 0.975, чтобы иметь 97.5% вероятности. Число z в этой функции никогда не меняется. Если у вас нет удобного программного обеспечения для работы со статистическими данными или же для вас критична производительность, вы можете всегда жестко прописать значение для z. (Используйте 1.96 для доверительного уровня в 0.95).

Ниже в качестве иллюстрации приведём SQL запрос, делающий что нам нужно. Предполагаем, что у нас есть таблица объектов с положительными и отрицательными оценками по ним, и мы хотим отсортировать их по нижней границе 95% доверительного интервала:

SELECT 
	widget_id, 
	((positive + 1.9208) / (positive + negative) - 
		1.96 * SQRT((positive * negative) / (positive + negative) + 0.9604) / 
 		(positive + negative)) / (1 + 3.8416 / (positive + negative)) 
 	AS ci_lower_bound 
	FROM widgets WHERE positive + negative > 0 
	ORDER BY ci_lower_bound DESC;

Если кто-то не поверит, что такой сложный SQL запрос способен вернуть полезный результат, просто сравните этот результат с результатами двух других методов, обсуждаемых выше:

SELECT widget_id, (positive - negative) 
       AS net_positive_ratings FROM widgets ORDER BY net_positive_ratings DESC;

SELECT widget_id, positive / (positive + negative) 
       AS average_rating FROM widgets ORDER BY average_rating DESC;

Вы быстро убедитесь, что совсем немного дополнительной математики заставит хороший контент всплывать наверх. Однако перед запуском этого SQL запроса на большой базе данных поговорите с вашим дружественным администратором о правильном индексировании таблиц. Изначально я разработал данный метод для генератора фактов о Чаке Норрисе в честь одного из моих учителей, но затем этот метод опробовали в таких местах как Reddit, Yelp, и Digg.

Другие применения метода


Доверительный интервал Вильсона применим не только для сортировок. Его можно использовать везде, где вы хотите с уверенностью знать, какова пропорция людей, совершающих определенный поступок. Например, он может использоваться в следующих целях:

  • Выявление спама или злоупотреблений. Сколько людей, увидевших сообщение, пометят его как спам?
  • Создание списка «самого лучшего». Сколько людей, увидевших сообщение, пометят его как «самое лучшее»?
  • Создание списка «самого расшариваемого». Сколько людей, увидевших сообщение, нажмут на кнопку «расшарить»?

Этот метод может быть гораздо более полезным для формирования списков «самого лучшего» по отношению к числу просмотров, числу загрузок, или числу покупок, нежели вывод по числу положительных оценок по отношению к общему числу оценок. Многие люди, обнаруживающие что-то посредственное, не будут утруждать себя голосованием вообще. Сам по себе факт просмотра или покупки чего-либо без последующего голосования содержит полезную информацию о качестве объекта.

Ссылки


  • Binomial proportion confidence interval (Wikipedia)
  • Agresti, Alan and Brent A. Coull (1998), «Approximate is Better than 'Exact' for Interval Estimation of Binomial Proportions,» The American Statistician, 52, 119-126.
  • Wilson, E. B. (1927), «Probable Inference, the Law of Succession, and Statistical Inference,» Journal of the American Statistical Association, 22, 209-212.


P.S. От меня


Сам перевод выполнял не я. Все благодарности karaboz.
Я не до конца уверен в точности перевода математических терминов, буду благодарен за уточнения!

Изначально обсуждение оригинала статьи возникло Facebook. Там в комментах есть интересные вещи, которые я не стал вставлять в итак перегруженную статью.

Букмарклеты

Для того, чтобы лучше один раз увидеть, чем 10 раз прочитать на Хабре, я сделал пару букмарклетов сортирующих комментарии описанным методом для Хабра и блога на Дару~даре с 95% точностью. Делал по-быстрому, проверял только в Chrome/Safari:

javascript:jQuery.getScript('http://dl.dropbox.com/u/285016/code/habr_comment_by_rating.js');

javascript:jQuery.getScript('http://dl.dropbox.com/u/285016/code/dd_comment_by_rating.js');


Выглядит так (кликабельно):
image

Реализация рейтинга на JavaScript

В приведённых ниже функциях дополнительно обрабатываются заминусованные объекты не получившие ни одного положительного голоса. В этом случае возвращается -число_минусов. В остальных случаях рейтинг будет находиться в диапазоне [0;1). В качестве параметров передаётся число положительных и отрицательных голосов.

function wilson_score(up, down) {
	if (!up) return -down;
	var n = up + down;
	var z = 1.64485; //1.0 = 85%, 1.6 = 95%
	var phat = up / n;
	return (phat+z*z/(2*n)-z*Math.sqrt((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n);
}


P.P.S.


Адаптировал формулу под произвольную шкалу голосов. Код на Python:

def wilson_score(sum_rating, n, votes_range = [0, 1]):
    z = 1.64485
    v_min = min(votes_range)
    v_width = float(max(votes_range) - v_min)
    phat = (sum_rating - n * v_min) / v_width / float(n)
    rating = (phat+z*z/(2*n)-z*sqrt((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n)
    return rating * v_width + v_min

Тут sum_rating — сумма всех голосов, n — количество, votes_range — дапазон возможных оценок. Возвращаемое значение находится в указанном диапазоне votes_range.
Автор: @ur001 Evan Miller
Дарудар
рейтинг 55,95
Сервис дарения вещей и услуг

Комментарии (132)

  • +47
    Ах, отличная картинка, меня сразу привлекло. Спасибо за перевод.
    • +10
      Улыбнуло:
      Рейтинг = Нижняя граница доверительного интервала Вильсона (Wilson) для параметра Бернулли

      И тут я докрутил до формулы — и лег под стол. Посмеялся от души!

      Материал отличный! Буду вспоминать математику и тестировать.

      Спасибо.
      • +2
        Почему-то вспомнилось

        image

        The Engineer's Favorite Equation

        А в формуле из статьи a/2 рядом с Z придаёт монструозности. Если их отбросить, то вполне себе выражение, что видно по ниже приведенному коду.
    • +12
      Картинка хорошая, конечно, но меня не покидает ощущение, что сиськи сейчас слипнутся под действием противоположных зарядов…
    • –3
      Зашел, чтобы прочитать первый комментарий.
  • +26
    world-art.ru применяет алгоритм Томаса Байеса для оценки аниме и фильмов по 10-балльной шкале, и, как мне кажется, она очень хорошо подходит для фильмов:

    Для определения рейтинга применяется специальная статистическая техника, известная как байесовская оценка (по имени автора Томаса Байеса). Она призвана взять в расчёт не только среднее арифметическое оценок проголосовавших (средний балл), но и их количество.
    image
    30 — это необходимый минимум голосов, отданных за данное аниме. 7.2453 — некая усреднённая величина, принятая за основу метода. Суть заключается в том, что при небольшом количестве голосов расчётный балл будет близок к 7.2453. По мере увеличения отданных голосов роль среднего балла (среднего арифметического голосов) будет возрастать. Интересной особенностью является то, при одинаковой средней арифметической голосов больший расчётный балл имеют аниме с меньшим количеством голосовавших. Это искажение будет исправляться с поступлением новых голосов, хотя логика в нём есть — если при меньшем количестве голосовавших среднее арифметическое то же, то и низких баллов дано меньше.
    • +4
      Да, этот метод похож. Его применяет IMDB.

      При малом числе голосов такой рейтинг будет стремиться к заданному дефолтному значению. Насколько «малом» определяется константой (у вас 30). Я пробовал применить этот алгоритм к +/– голосованию, но тот что приведён в статье мне показался правильней. А только не на 100% понял почему так происходит и как он работает :)

      Я где-то видел сравнение этих 2-х методов в обсуждении, если мне не изменяет память, на Reddit-е. Если найду — скину ссылку.
      • 0
        Да, тоже видел, на реддите. А вы как пытались его применить к ±? Задавали + как 10 и — как 1? Или приводили алгоритм к [0,1]?
        • 0
          Второе. «Минус» = 0 баллов, «Плюс» = 1. Может это и не совсем верных подход. Средний брал, естественно 0.5.
      • +7
        • 0
          Ух-ты, я этой статьи не находил ещё. Спасибо!
        • +4
          DRY? Не, не слышали

          DRY? No
    • 0
      Ага, нашёл. Там обсуждение как раз начинается с Bayesian average.
    • +1
      Алгоритм преподобного Томаса Байеса. Как звучит :)
    • +1
      По-моему, этот алгоритм не так хорош, как кажется. Слишком легко и высоко поднимаются новые аниме.
    • 0
      На кинопоиске по такой же формуле рассчитывается ТОП-250 (http://www.kinopoisk.ru/level/20/#formula)
  • +4
    «Если бы вы знали, что искать, то увидели бы, что алгоритм находится на окне в моей спальне.» (с) Марк Цукерберг из «Социальная сеть».
    img-fotki.yandex.ru/get/6109/24951406.27/0_739ae_b9ed19d2_L
    • 0
      Пока писал, опеределили =)
    • +1
      Это же алгоритм рейтинга Ело (спасибо плейд цтф за то что я это узнал :)
      • 0
        Один я походу из WoW узнал про эту систему :)
  • +6
    Отличная статья, спасибо за перевод. Сразу вспомнил одногруппника, который всегда говорил: «Я не математик, я программист». Даже в такой, на первый взгляд, тривиальной задаче ему бы пригодились тервер и матстат, чтобы взглянуть на проблему глубже.
    • +5
      С тем же успехом можно сказать, что ему помогли бы знания в лингвистике при написании компилятора или автоматического перевода. На самом деле математика и программирование софта связаны лишь в определенных местах. Та же теория графов не менее полезна.
    • +4
      Он прав. Математика нужна только инженерам-программистам. Инженер-программист отличается от программиста так же как инженер-конструктор самолетов, и рабочего собирающего самолеты в цеху. В обоих случаях требуется высокая квалификация специалистов. Но в разница способе производства огромна. Инженер это творец, а программист это ремесленник. Инженер сам не может знать, что ему нужно знать для своего труда. А программист четко знает, что ему нужно для создания конкретного продукта. Потому, что за него об этом подумал инженер или архитектор.
      • +3
        Хех. Как пример разности мнений, приведу свое. Всегда считал наоборот, т.к. из тех, кого знаю я, инженеры-программисты работали исключительно по тех заданию и по указаниям начальства, тогда как программисты имели простор для творчества и не ограничены в фантазии нуждами производства.
        И да, в моем случае программист является и архитектором. Видимо вы про тех программистов, которые работают винтиками в каких то огромных компаниях.
        • +1
          Конечно я говорил о корпоративном секторе. В стартапах программист должен быть и инженером, и архитектором, и бизнесменом, и философом в одном лице ;)
      • –1
        И как знания математики помогут инженеру-программисту написать какую-то предметную задачу? Ну скажем симулятор космического корабля (чтобы отладить на модели новую деталь, а не пускать спутники в океан). Тут очень сильно знание физики важны в первую очередь, а не математики. Или симулятор эволюционного развития, для биологии. Тут без генетических знаний — никуда, а математика нужна в объеме чуть выше чем «сдачу посчитать». В данном случае просто проблема, которую надо решить — математическая. При этом знания математики, конечно же, сильно помогают.

        Хотя на самом деле, задача тут (которая формулой решается) вообще не программистская. Будто бы в ТЗ было прописано «вычислить оценку фильмам по оценкам пользователей, но так, чтобы лучшие фильмы имели более высокую оценку». Непонятно, что считать тут лучшими фильмами, и что если предложенный метод выглядит сложно, наукоемко (А раз так — то, значит, верен. Все сложное и непонятное всегда умнее простого и понятного), но при этом он не совсем хорош? Можно ведь и вообще по рандому выставлять оценки фильмам, товарам, итд, и тоже получим некий отсортированный список. Нужен какой-то четко прописанный принцип, какая оценка и сортировка нам кажутся правильными, и по каким критериям мы их оцениваем.

        Вот самый грамотный подход (на мой взгляд конечно же) был бы тут такой, который бы с этого начинался. Сначала описываем критерии, по которым будем определять, какой результат работы считаем лучшим (а это уже заставляет задуматься, ведь непонятно почему эта схема хороша — показаны только минусы других простых подходов, а у этого и свои минусы могут быть). И потом уже пробуем разные алгоритмы, прогоняем через них разные данные, сравниваем результаты, «дефекты» каждого алгоритма, и в итоге получаем статистическое доказательство что выбранный алгоритм лучше. Предложденный же алгоритм лучше лишь тем, что не показывает иногда «яркие» положительные или отрицательные оценки при малом количестве отзывов. Но так же можно найти примеры, на которых он ошибается. Скажем, если алгоритм вам даст оценку шедевра кинематографа в «средние» 6 баллов, при том что проходная романтическая комедия (но не худшая) оценивается в 7, вы же не будете считать такой алгоритм правильным? А в данном случае этот алгоритм именно так и поступает, усредняя результат при малом количестве оценок.
    • 0
      и все же, не каждый программист пишет игровой движок. В некоторых местах достаточно арифметики, логики и алгоритмов.
  • +4
    Спасибо за перевод.
    Тема показалась не до конца раскрытой. Не хватило четких критериев, которым должна удовлетворять формула, т.е. критериев, по которым автор отделяет «правильно» от «не правильно». Именно поэтому, мне, например, не очень понятно, почему эта формула — то, что надо.
    • +3
      Мы хотим знать следующее: «Обладая набором данных мне оценок, можно ли с вероятностью 95% сказать, какова будет „реальная“ доля положительных оценок?»

      То есть матстатовыми методами оценивается, каков был бы рейтинг, если бы проголосовало больше людей — а именно меньшее/большее количество проголосовавших создаёт проблемы для очевидных способов ранжирования.
      • +1
        Это не очень похоже на четкий критерий, который можно применить к любой формуле вычисления рейтинга и сказать «катит/не катит» :-)
    • +3
      Если я сам правильно понял смысл такой. Пока оценок мало — мы не можем сказать каким будет отношение положительных и отрицательных голосов когда проголосует больше. Точнее, можем, но с определённой ±погрешностью. В данном алгоритме берётся нижняя граница этого диапазона. Т.е. если средний рейтинг = 10±5, то мы берём 5. В итоге учитывается и отношение голосов, и их число. Число голосов играет роль подтверждения достоверности результата.

      Что мне не понятно, так это закон распределения. Тут используется именно нормальное распределение, и, по хорошему надо взять статистику голосов сайта и проверить как оно на самом деле. Берём объекты за которые проголосовало много людей. Вычисляем среднее значение голоса. И смотрим, по какому закону относительно числа голосов рейтинг приближался к своему среднему.

      Будет время проанализирую голоса на Дару~даре. Или brutto с buxley проанализируют голоса Хабра.
      • +1
        Спасибо. На сколько я могу судить, понял смысл так же, как вы, и это хорошо :-) Что делает формула — понятно, наверняка она, даже крутая по всем параметрам, но это субъективная оценка: «да, формула большая, толстая и много чего учитывает».
        Хотя, конечно, может автору и все равно на принятые в математике правила, и он просто хотел познакомить читателя с формулой, не вдаваясь в подробности. Я просто написал то, чего мне не хватило:
        в постановке задачи, кроме субъективизма, я ничего не нашел (а ведь, как известно, постановка задачи — пол дела). Соответственно, после озвучки правильной формулы, никак не проверить её соответствие поставленной задаче. :-)
        • 0
          Ну вы поробуйте, опять же, субъективную оценку. Поиграйтесь букмарклетом с комментами Хабра. В конце-концов основным критерием будет субъективная оценка создателей проекта. Если создателю/идеологу нравится результат — ок :) Хотя я конечно предпочёл бы встраивать в свой сайт не чёрный ящик, а что-то более прозрачное.
    • +9
      Тема подробно раскрыта в книге Building Web Reputation Systems. Написана разработчиками из Yahoo!
      • 0
        Спасибо. Любопытная книга. Только как я понял тут больше про пользовательскую репутацию и кармические механизмы. Там немного другая специфика.

        Никогда не заказывал книги с Амазона. Не в курсе — насколько это сложно/долго и насколько большая выходит переплата?
        • +1
          Название книги может сбивать с толку, но в ней описаны практически все возможные рейтинговые системы, подпадающие под классификацию «A source» -> «makes a claim» — > «about a target», а также различнве методики сбора и подсчета статистики.

          В Amazon я покупаю только электронные книги. Через Kindle эта процедура автоматизирована до одного клика, даже CVC-код карты никогда не запрашивается.
          • 0
            Вот уж действительно, где тема раскрыта! Целая книженция про рейтинги, для меня удивительно :-)
            • +5
              Область весьма нетривиальная, есть место для исследований. В книге, например, хорошо аргументируется, почему возможность прямого изменения рейтинга пользователя как на Хабре — простейшее и далеко не лучшее решение.

              (фрагмент из первых абзацев главы про пользовательскую карму)
              " — Rating a user directly should be avoided. Typical implementations require a user to click only once to rate another user and are therefore prone to abuse. When direct evaluation karma models are combined with the common practice of stream-lining user registration processes (on many sites opening a new account is an easier operation than changing the password on an existing account), they get out of hand quickly. See the example of Orkut in “Numbered levels” on page 186.

              — Asking people to evaluate others directly is socially awkward. Don’t put users in the position of lying about their friends.

              — Using multiple inputs presents a broader picture of the target user’s value.

              — Economics research into “revealed preference,” or what people actually do, as opposed to what they say, indicates that actions provide a more accurate picture of value than elicited ratings.
              "
              • +5
                Карма на Хабре — забавная штука. Вроде бы, есть какой-то сложный рейтинг, который учитывает множество параметров, и формула которого известна одному НЛО. Но почему-то все права и ограничения завязаны на старую систему кармы, и от рейтинга не зависит ровным счётом ничего, кроме исключительно фаллометрического «топа».

                Не понимаю.
          • 0
            А! Ну тогда я пошёл качать Kindle для iOS-а :) Спасибо.
      • +5
        Спасибо за наводку. Еще порекомендовал бы Programming Collective Intelligence (есть русское издание).
  • 0
    А еще в фильме «Социальная сеть» на стекле в общаге они написали формулу для составления рейтинга девушек. Это как дополнительный вариант.
    • 0
      Только формула, по-моему, пустышка, рыба, ничего не значащая.
  • +3
    Всегда приходилось самому изобретать велосипед от необразованности. И как правило в сети толковоразжёванных статей не сыщешь. Спасибо за информацию.
  • 0
    Кстати в рейтингах приходится учитывать немного большее количество параметров, нежели + и -.
    • +1
      Можете по подробнее? Очень интересная для меня сейчас тема.
      • +1
        Если у Вас по этой теме есть какой-то открытый проект, можно с вами связаться, например, через ЛС? Возможно, Вас заинтересуют наработки некоторой группы людей, а мы могли бы скоординировать усилия при появлении новой информации.
        • 0
          Да, давайте. Было бы интересно.
  • –17
    Открыл хабр после лепры и растерялся.
  • –4
    Readability — приводит текст веб-страницы к удобному для чтения виду.
    • 0
      Это вы про отображение в оверлее? Меня скорее плагин iReader для Хрома вдохновил :)
  • +23
    У всех рейтингов, какие бы формулы ни использовались, есть одна большая беда — «снежный ком» оценок. Есть 100500 объектов, у нескольких есть высокий рейтинг, и эти объекты, в общем-то, вполне удовлетворяют спрос. Все будут смотреть их, ставить плюсик и не обращать внимания на остальные. Однажды вырвавшиеся вперёд заплюсованные объекты застревают в Топе навечно, пока не случится какой-нибудь катаклизм.

    Посмотрим на Хабр: когда к статье 300 комментариев, как много народа читает их все и объективно выставляет оценки? Скорее всего, есть несколько комментариев с рейтингом 20+, которые сразу бросаются в глаза, которые большинство плюсует, и эти комментарии быстро уходят ввысь. И, скорее всего, есть несколько комментариев в минусе, которые тоже хорошо бросаются в глаза благодаря серому тексту, и которые, скорее всего, скоро улетят в глубокий минус.

    В результате возникает десяток комментариев с высокоми рейтингами по модулую, которые не обязательно самые выдающиеся и самые отвратительные, а большинство комментариев болтается в диапазоне ±1, иногда ±5.

    Вот если бы знать, как бороться с этим, было бы круто.
    • +2
      Да, такая проблема безусловно есть. Но стоит ли считать её проблемой? Вот с фильмами, к примеру. Не будем же мы смотреть всё подряд, боясь пропустить что-то и зная о подобном эффекте? Скорее всего мы обратим внимание на уже оценённые фильмы. Это банально экономит время. Потом, мне кажется, действительно стоящие комментарии в конце концов всплывут, так как найдутся несколько энтузиастов прочиющих всё. Я иногда читаю по 500 комментариев, если мне интересна статья (хотя и редко).

      Кстати, продолжая аналогию с фильмами, можно там же поискать решение. Помимо рейтинга IMDB, по которому вообще-то сложно понять насколько понравится фильм, существуют различные системы рекомендаций. Их можно взять на заметку, и, к примеру, делать колонку «комментарии которые могут вам понравится». В качестве алгоритма можно попробовать от Коллаборативной Фильтрации (предлагать высоко оцененные объекты от людей со схожими оценками), до Байесовской (выделяя в качестве независимых признаков объекта автора, ключевые слова и другие атрибуты). Как вам такая идея?
      • +10
        Я экспериментировал с коллаборативной фильтрацией и в целом остался очень доволен. На одном из тематических арт-сайтов я сграбил все связи «юзер следит за работами юзера» и построил по ним рекомендации — сразу нашёл множество интересных мне художников. Судя по отзывам, эксперимент можно считать успешным. Что любопытно, некоторым интереснее оказалась обратная связь — кому порекомендовали их. Говорят, интересный народ нашли. :)

        Для сравнения, другой программист сделал для того же сайта рейтинг с а-ля гугловским pagerank’ом — я прошёлся чуть ли не по тысяче из «топа», и толком ничего не нашёл.

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

        На том же Амазоне кроме его тупого рейтинга есть аналогичные «рекомендации» — можно сказать, что тебе нравится, и Амазон начнёт тебе советовать что-то похожее. Тытрубка — вообще ярчаший пример блестящей реализации рейтингов: есть и абсолютный топ, и результаты коллаборативной фильтрации, и «похожие» видео, и ещё чего только нет. Искать «хочу того, не знаю чего» становится весьма приятным занятием. :)

        Но у коллаборативной фильтрации есть и минусы: во-первых, ресурсоёмко; во-вторых, нужно знать что-то о пользователе.
        • 0
          > Но у коллаборативной фильтрации есть и минусы: во-первых, ресурсоёмко; во-вторых, нужно знать что-то о пользователе.

          Ресурсоёмкие — это по памяти или по времени?
          • 0
            В моём случае было и по времени (расчёт шёл несколько часов), и по памяти (все связи запихивались в оперативку). Есть какие-то специальные алгоритмы для очень больших наборов данных, но я в эту тему не влезал, да и давненько это уже было, деталей не помню. Уж в любом случае расчёт будет гораздо медленнее, чем подсчёт среднего.
    • 0
      Думал я об этом вопросе и пришёл к выводу, что это не что иное, как несовершенство механизма ранжирования. Весь фокус в том, что для сообщества будет выгоднее ранжировать не по высшему рейтингу, а по несколько другому алгоритму. Проблема высокооценённых — этому яркое подтверждение. От этого же — попса не есть лучшее из искусства, топ фильмов не покажет все лучшие фильмы и топ компаний (по объёму поставок) не даст лучшие для пользователя компании. Чувствую, это — тема для ещё одной интересной статьи и отдельный вопрос.
    • 0
      У меня в топе игры была такая проблема — сильнейшие игроки застряли наверху и все видят только их, хотя они уже давно не посещают игру. Ввёл простое правило: кто не играл неделю — пошел вон из топа. И топ сразу ожил.
      • 0
        А вам, возможно что-то типа такого подойдёт. Сделать этот рейтинг основным, с возможностью сложного переключиться на «вневременный». Чтобы и тем с другим угодить.
    • 0
      Можно делить рейтинг на время, прошедшее с момента публикации оцениваемого комментария/статьи. Тогда новое интересное будет наверху, но чтобы оставаться наверху, ему надо быть ОЧЕНЬ интересным, получая всё новые плюсы.
    • 0
      есть несколько комментариев с рейтингом 20+, которые сразу бросаются в глаза, которые большинство плюсует, и эти комментарии быстро уходят ввысь

      Это мне кажется вообще некошерным. Какая читателю разница какой рейтинг у комментария? Может быть разве что автору комментария стоит это показывать. А может быть даже и ему не показывать, а только для технической стороны дела использовать (удалять при -100 например).

      Если кто-то написал «вася дурак», то для выставления оценки, читатель должен оценить, насколько это верно сказано, насколько тактично, насколько прямо итд. Но если ему при этом еще добавить лишней информации, типа «Кстати, 60% оценивают этот комментарий позитивно. Возможно вам интересно, но при этом 80% выставивших плюс имеют возраст до 20 лет, 75% проплюсовавших не имеют высшего образования, 77% из них часто употребляют мат в разговорной речи. Не будь быдлом как они, поставь другую оценку!», тогда человек уже не оценку утверждению выставляет, а оценку СЕБЕ, причисляя ее к той группе, которая ему более симпатична. На dirty слишком много такой информации дается. На хабре поменьше, но она тоже лишняя. Комментарий хороший или плохой, вне зависимости от того, нулевая у него пока что еще оценка, или его уже бешено заплюсовали (заминусовали).
  • +4
    Тема рейтингов статей поднималась мной в недавней статье "Что у нас «Лучшего» на сегодня?". В ней приводится статистика оценивания 10-15 лучших статей на вечер пятницы на Хабре — 4 типа оценок: рейтинг, избранное, Гугл+ и число комментарии —
    и названия с тематикой статей, ссылки на них. Стоит посмотреть, чтобы увидеть, что действительно интересные статьи для разработчиков надо искать по иным показателям, чем наивысшие какие-либо оценки. В конце я сформулировал мысль (уже ночью, поэтому не все, кто читал, её увидели. Если интересно — прошу обсудить), что надо построить иные формальные оценки статей на Хабре, и тогда каждая группа читателей (ведь кого-то устроит и рейтинг популярности) получит свою Ленту.
    Появилась идея: из 5 показателей (включая число добавлений в избранное и число отрицательных ответов) пытаться угадать род статьи. Исходя ещё из заявленных хабов и иногда — автора, вполне можно классифицировать статьи гораздо точнее, чем сейчас. И ищущие серьёзных статей их будут получать.


    • 0
      Э… не надо пожалуйста про «свою ленту» :) Это больная тема. Я перед уходом из ТМ сделал тестовую версию Хаброленты 3.0, которая учитывала перечисленные вами и множество других признаков для персональной рекомендации статей. С тех пор я читал только её, т.к. для меня она работала великолепно. Но с миграцией на Хабы в её коде, видимо не разобрались, или сочли не порвостепенной задачей и выпилили. Хотя система Хабов, ИМХО, сама по себе замечательна. Но с ней я трачу горадо больше личного времени на прочтение неинтересных мне статей…
      • +1
        Так никто не предлагает уговаривать разработчиков Хабра поддержать придуманную систему. Есть более конструктивный путь.

        Приятно услышать мнение из самых первых рук — от человека, который сражался с реальным потоком рейтингов на Хабре. Спасибо!
        • 0
          Дело в том, что извне не вытащишь информацию о голосах пользователя. Только об избранном. Не уверен, что на одном избранном можно хорошо что-то порекомендовать.

          Я вообще пробовал 4 варианта: оценки постов, избранное, коллаборативную фильтрацию на основе оценок и на основе друзей. В итоге остановился на первых 2-х. Коллаборативная фильтрация вообще тут плохо подходит, т.к. в отличие от фильмов/музыки актуальность поста сильно зависит от времени. В итоге мы получаем сильно отстающую штуковину.
  • +33
    Суть статьи в трех предложениях:

    Плохо: R = P+ — P-

    Плохо: R = P+ / Pall

    Хорошо:
    • +6
      Короткий ответ на вопрос «Почему хорошо?»:
      «Потому что кванти́ль!».
      • +4
        Тогда уж «Потому что гладиолус» )
        • 0
          Кто-нибудь понял, о чем он?
          • +5
          • 0
            Это из уральских пельменей, вот из этой сценки.
    • 0
      ахахаха))) да, здорово)

      свои пять копеек:
      давно интересовался проблемой, правда применимок спорту. И разработал прсотую, но как мне кажется, действенную систему (модификация второго варианта).
      Берем две вещи с оценками (+/итого): 5/10 и 7/10. Получаем 50% и 70% положительных оценок. Вопросов не возникает — второе действительно лучше. Но что, если 50% получается из такого 100/200? Ведь навреное ценнее более расширенная выборка? Для этого нужно ввести дополнительный коэффициент — количество положительных оценок. (100 * 100) / 200 = 50 баллов, (7 * 7) / 10 = 4.9 балла похоже на истину?
      Еще пример: 5/10 (2.5 балла), 5/11 (2.27 балла). По-моему здравое зерно в такой методике есть, т.к. основывается на процентовке, а для правильной оценки применяется количественный коэффициент.
      Если я что-то неправильно думаю, поправьте. Мне это интересно.

      По поводу снежного кома в рейтнгах (голосуют за ТОПовые позиции) могу предложить делать выборку за опеределнный срок, напрмиер месяц. Это не избавит от проблемы, но несколько снизит вред.
      • 0
        Хм… А почему именно p^2/n? И как вы эти 2 формулы потом объединили?
        • 0
          какие две формулы? у меня одна формула, которую вы написали.
          нужен какой-то коэффициент. Если есть 5/10 и 10/20 (в обоих вариантах 50%), то более ценна оценка с большим количеством проголосовавших и соответственно положительных отзывов. Направшивается вывод: умножить на количество положительных.
          5/10 и 10/20 => 2.5 и 5 — вторая оценка в два раза ценнее, т.к. в два раза больше проголосовавших.
          • 0
            А, понял
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          не вижу тут неправильного ранжирования, раз мы договорились, что важна не процентовка, а неслучайность процентовки, которая выявляется количеством положительных отзывов. 1001 отзыв из миллиона зарабатывался год, а 10 из 100 — полчаса. К тому же 11 из 101 уже будет в пользу второго объекта.
    • 0
      А сиськи где?!!!
  • +4
    Я в своё время заморачивался, и обнаружил, что лучше всего работает вот такой тривиальный алгоритм: подбросить каждому элементу n-ое количество средних оценок.

    Т.е. было среднее арифметическое = (сумма всех оценок) / (количество оценок)
    Стало (для пятибальной системы) взвешенное среднее = (сумма всех оценок + 3n) / (число оценок + n)
    n выбирается небольшое (я выбрал 2).

    Просто для понимания, легко отсекает элементы с небольшим числом строго положительных/отрицательных оценок, почти не влияет на элементы с большим количеством оценок, очень легко вычисляется, в т.ч. SQL-запросом.
    • +2
      Угу. Это у вас упрощённая версия вот этого. Для многих случаев она действительно неплохо работает. Когда нужно просто пессимизировать результаты с небольшим кол-вом голосов.
      • 0
        Если считать, что 3 — это средний балл, то да.
        На самом деле смысл не в упрощении формулы, а в упрощении вычислительной сложности расчетов. В случае с Байесом приходится либо считать средние значения по всей базе «на лету», либо кэшировать их на какое-то время. А здесь всё просто и прозрачно.
        • 0
          Да нет, оно считается один раз по проекту и прописывается как константа. Ну можно раз в год пересчитать
          • 0
            Ну я и говорю — кэшировать на год :)
            Для проектов, которые быстро накапливают базу этот вариант неприемлем.
            • +2
              Но IMDB его использует. Они посчитали один раз, и уже много лет не меняют. На самом деле не очень важно каков средний рейтинг по 5-и бальной шкале 4.123 или 4.124. Вообще если средний рейтинг оценки фильмов увеличится на 10 долю об этом напишут в новостях.

              Между прочим при 0 голосов у вас выходит 3*2/2 = 3. Это и есть ваше среднее
            • 0
              А, блин, да у вас же 1:1 формула :)
              Разложите её на сумму
              • 0
                Дык я так и написал же :)
                Если считать, что 3 — это средний балл, то да.
  • +1
    Всегда задавался этой проблемой, но никак не мог найти подходящего решения. Спасибо!
  • +1
    C такой нагрузкой дропбокс вам паблик на сутки закрутит, перезалейте.
    • 0
      Ой-ой, правда? А что у них за ограничения?
      • 0
        выложил фотку в комменты — через три часа на почту «а-та-та и public is closed for a day»
        • 0
          Ну, for a day — это не страшно. Скажут — переложу
          • 0
            Ну кому как, я дропбокс использую очень активно :)
          • +1
            ну я продолжение фразы не написал, там про то, что при повторе будет больно!
            • +2
              Вот блин, какая-то пасмурная у них облачность :(
              • 0
                Так там честно написано: «шейр файлс», а не «мэйкл ред лайтс дистрикт фром ёур дропбокс».
  • +1
    Хорошая статья, возьму на заметку.
  • +5
    Я представил себе социальную сеть, где можно выбрать фотографии с 95% C.L. в ± 2σ вокруг оценённого пользователями балла 4.152.
  • +10
    Измерять вероятное количество положительных оценок — хорошо, но все равно не решает общую задачу. Нужно еще учитывать единодушие оценок, и, как здесь раньше написали в комментариях, предпочтения групп. Для чего мы строим систему рейтинга по объектам? Для того, чтобы потом тот или иной объект порекомендовать. Если оценки по объекту 98 положительных и 2 отрицательных, то порекомендовать его можно кому угодно. А если 1000 положительных и 1500 отрицательных? Да, рейтинг получается невысокий, но ведь 1000 человек это понравилось, значит, что-то в нем все-таки есть. Нужно пытаться сегментировать отрицательные и положительные оценки по объекту и выделять группы посетителей, которым он с большой вероятностью нравится и наоборот.

    Что в итоге хотел сказать: рейтинг — это всего лишь примитивная система рекомендаций, как бы хитроумно он ни рассчитывался. И чтобы рейтинг получался правильным, его нужно рассчитывать для каждого персонально свой.
    • 0
      Согласен. Насчёт предпочтения групп — правильная идея. Но она тем более актуальна, чем менее тематичен ресурс. Т.е. если оценивать любые фильмы или музыку, то польза общего рейтинга невелика, а если у нас узко специализированное сообщество — то вполне подходит.

      Я как раз привёл пример использования такого рейтинга для комментариев одной публикации, и тут он работает хорошо, т.к. публикация изначально сужает группу до тех, кому она интересна. В том числе на этой публикации букмарклет работает замечательно :)

      Да, ещё помимо рекомендательной функции рейтинг выполняет функцию обратной связи. Это тоже важно.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Не, я имел в виду обратную связь автору. Цифра рейтинга для него является показателем востребованности, одобрения его публикаций в сообществе.

          Насчёт уведомлений — правильный подход. На Дару~даре вместо уведомлений есть лента даров/комментариев получивших определённое число минусов доступная «смотрителям». С комментариями фокус не пройдёт, а с публикациями можно делать плавающий порог для отправки уведомлений, на основе числа просмотров по приведённой формуле:
          Выявление спама или злоупотреблений. Сколько людей, увидевших сообщение, пометят его как спам?
  • +3
    Есть еще один фактор, который хотелось бы учесть — вещи, которые в топе рейтинга часто плюсуют просто так (принцип стада) — вот вес этих плюсов нужно уменьшать.
    • 0
      Вы наверно об этом? Я там написал свой комментарий.
    • +1
      Вы, наверное, про сиськи в этом посте? :)))
  • 0
    как по-поему, так картинка неправильная.
    левая (с минусом которая) сиська должна быть нарисована большей, нежели правая (и дело тут вовсе не в том, что у реальных женщин левая грудь, обычно, немного больших размеров).
    • 0
      Нарисуйте — поменяем :)
      • 0
        только за большие сиськи деньги :)
    • +8
      Зато знаки правильные. Вот вход в мой бывший учебный корпус:

  • НЛО прилетело и опубликовало эту надпись здесь
    • +2
      Я знаю 2 варианта:

      1. Рейтинг «самые трендовые», типа такого
      2. И ещё один забавный алгоритм. Можно просто к рейтингу прибавлять дату публикации на что-нибудь поделённую. В итоге вверх будут всплывать и более новые, и более рейтинговые (только нужно нормальный рейтинг тоже хранить, а этот использовать для сортировки)
      • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Уже давали ссылку выше: amix.dk/blog/post/19588
      См. раздел Effects of submission time
  • 0
    ну как, как можно было на сиську "-" налепить? СИСЬКИ — это всегда "+"!
    Статья отличная! Спасибо!
  • 0
    Скажите, пожалуйста, чем плох следующий велосипед. Выбираем некий шаг, например, 5%. Выбираем элементы, где процент положительных оценок ⊂ (95—100]. Сортируем по количеству положительных оценок. То же — для диапазона (90—95]. И так далее.

    Чем меньше шаг, тем выше точность. Из плюсов вижу интуитивную понятность, какие минусы?
    • НЛО прилетело и опубликовало эту надпись здесь
  • –5
    Судя по рейтингу поста, вся статичтика — туфта. Сиськи рушат любые формулы и планы ))
    • 0
      А что я не так сказал? Метода выше не будет работать для соотвествующего контента.
  • 0
    Для получения объективных результатов нужно учитывать психологическую составляющую. Например то что отрицательные оценки люди склонны ставить гораздо чаще положительных.
    • 0
      Можно домножать количество отрицательных оценок на некий коэффициент (k>=1). На общий рейтинг это не влияет.
    • 0
      Может всё-таки реже? Давайте посмотрим на число людей с положительной кармой и число с отрицательной, первое явно выше. Про миллионы фотографий «я и ковёр», получающих на Однокласниках только 5 баллов (за 4 наверняка обижаются ещё) я уж молчу.

      Но стоит ли придавать отрицательным оценкам больший вес из-за того что они встречаются реже? Скорее стоит сегментировать аудитории, но это уже путь к рекомендательному сервису. В целом же, 10-бальная шкала выглядит более полезной, чем + и — (по сути — двубальная шкала без градаций, как сильно вам что-то нравится или не нравится).
  • 0
    Статья была бы ещё лучше, если бы было поменьше «воды», и побольше математики. Я понимаю, что перевод, но всё же.
  • +1
    Есть у нас 10 картинок, за которые голосовали 1 год. А потом добавилась еще одна картинка и стало их 11. В результате в нашей системе образовалось 2 эпохи, когда оценок X, а количество картинок N и N+1. И получается, что формулу используем с допущениями, на которые она не рассчитана…

    И может сохраниться вселенская несправедливость (мы же не исследовали наше допущение), когда отстойнейшая картинка, провисевшая год и набравшая по случайности K оценок, будет иметь лучший рейтинг, чем новая, провисевшая 10 дней и набравшая K/2 оценок.

    А как же быть с сезонностью? Когда 31 декабря популярна картинка со Снегуркой в полупрозрачном красном пеньюаре, а летом популярна та же Снегурка, но в купальнике?

    Вот и мыслится, что нужно в формулах учитывать ещё и возраст выставленной оценки: Чем древнее оценка, тем меньший коэффициент значимости ей присваивать. Таким образом оценки, выставленные недавно, будут больше влиять на рейтинг, чем оценки выставленные давно.

    • +1
      Тут можно сделать одну голосовалку «лайк», а рейтинг считать по формуле где вместо числа голосов — число увидивших картинку пользователей. Думаю будет работать превосходно
      • НЛО прилетело и опубликовало эту надпись здесь
  • +2
    Хорошая статья, я даже успел забыть про завлекающую картинку.
  • 0
    Очень полезная статья и вполне достойный перевод. Спасибо.
  • 0
    Есть мысль, что если сразу задвигать вниз элементы с низким (отрицательным) рейтингом, то они никогда и не поднимуться. Тоже самое касается и популярных элементов.

    Мне лично очень хотелось бы добавить в рассчет рейтинга нормирование всех элементов на общее кол-во оценок, или даже на количество оценок за последние Х дней. (Пример — рейтинги Ebay за год и месяц)
    Т.е. по сути — заменить рейтинг на скорость наростания рейтинга

    Тогда новые элементы, вообще не имеющие оценок тоже будут иметь шанс быть увиденными а топам придется «прилагать усилия» для поддержания позиции.
    Очень похоже на пример с выкидыванием из топа неигравших игроков.
    • 0
      Верная мысль, так и делал «заменить рейтинг на скорость наростания рейтинга…» но тут возникает большая проблема в подборе эмпирических коэффициентов и адекватных зависимостей, которые для каждого из сервиса могут быть свои. Например что будет выше в топе +1000 набранные год назад, или +10 набранные месяц назад, или +1 но сегодня.
  • 0
    По переводу названия — на мой взгляд, более подходящая форма для нас, русскоговорящих: Как НЕ нужно сортировать контент на основе оценок пользователей.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка