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

в 13:38, , рубрики: digg, reddit, social interaction design, wilson score, yelp, Алгоритмы, Веб-разработка, голосовалка, голосование, рейтинги, сортировка, социальные сети, Социальные сети и сообщества

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

В оригинале название звучит как «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.
Я не до конца уверен в точности перевода математических терминов, буду благодарен за уточнения!

Изначально обсуждение оригинала статьи возникло в нашей FB-группе Как правильно сортировать контент на основе оценок пользователей Лаборатория Социального Проектирования. Там в комментах есть интересные вещи, которые я не стал вставлять в итак перегруженную статью.

Букмарклеты

Для того, чтобы лучше один раз увидеть, чем 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');

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

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

function wilson_score(up, down) {
	if (!up) return -down;
	var n = up + down;
	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);
}

Автор: ur001

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js