- PVSM.RU - https://www.pvsm.ru -
В оригинале название звучит как «How Not To Sort By Average Rating». Я подумал, что дословный перевод «Как не сортировать по усреднённому рейтингу» будет малопонятен и хуже отражает содержание статьи.
Вы занимаетесь веб программированием. У вас есть пользователи, которые оценивают контент на вашем сайте. Вы хотите разместить высоко оцененный контент наверху, а низко оцененный — внизу. Для этого на основе пользовательских оценок вам нужно вычислить некий «рейтинг».
Рейтинг= (Число положительных оценок) - (Число отрицательных оценок)
Почему это неправильно. Предположим, у одного объекта есть 600 положительных оценок и 400 отрицательных, т.е. в итоге 60% положительных. Предположим далее, что у другого объекта 5500 положительных оценок и 4500 отрицательных, т.е. в итоге 55% положительных. Данный алгоритм разместит второй объект (с рейтингом 1000, но всего с 55% положительных оценок) выше первого объекта (с рейтингом 200 и с 60% положительных оценок). Неправильно.
Сайты, которые допускают подобную ошибку: Urban Dictionary [1]
Рейтинг = Средняя оценка = (Число положительных оценок) / (Число всех оценок)
Почему это неправильно. Средняя оценка хорошо работает, если у вас всегда куча оценок. Но предположим, что у одного объекта 2 положительные оценки и 0 отрицательных. Предположим далее, что у второго объекта 100 положительных оценок и 1 отрицательная. Данный алгоритм разместит второй объект (с кучей положительных оценок) ниже первого объекта (с очень малым числом положительных оценок). Это неправильно.
Сайты, которые допускают подобную ошибку: Amazon [2]
Рейтинг = Нижняя граница доверительного интервала Вильсона (Wilson) для парамерта Бернулли
Почему это правильно. Нам необходимо найти баланс между долей положительных оценок и неопределенностью малого числа наблюдений. К счатью, математический аппарат для решения этой проблемы был разработан в 1927 году Эдвином Вильсоном. Мы хотим знать следующее: «Обладая набором данных мне оценок, можно ли с вероятностью 95% сказать, какова будет „реальная“ доля положительных оценок?». Вильсон дает ответ. Учитывая только положительные и отрицательные оценки (т.е. не беря во внимание 5-бальную систему оценивания), нижняя граница доли положительных оценок вычисляется по следующей формуле:
Используйте минус там, где написано плюс/минус, чтобы вычислить нижнюю границу. Здесь p̂ — доля положитеьных оценок, zα/2 есть квантиль* (1-α/2) стандартного нормального распределения, и n есть общее число оценок. Аналогичнная формула, примененная на Ruby:
*Кванти́ль в математической статистике — значение, которое заданная случайная величина не превышает с фиксированной вероятностью. Wikipedia [3]
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 запроса на большой базе данных поговорите с вашим дружественным администратором о правильном индексировании таблиц. Изначально я разработал данный метод для генератора фактов о Чаке Норрисе [4] в честь одного из моих учителей, но затем этот метод опробовали в таких местах как Reddit [5], Yelp [6], и Digg [7].
Доверительный интервал Вильсона применим не только для сортировок. Его можно использовать везде, где вы хотите с уверенностью знать, какова пропорция людей, совершающих определенный поступок. Например, он может использоваться в следующих целях:
Этот метод может быть гораздо более полезным для формирования списков «самого лучшего» по отношению к числу просмотров, числу загрузок, или числу покупок, нежели вывод по числу положительных оценок по отношению к общему числу оценок. Многие люди, обнаруживающие что-то посредственное, не будут утруждать себя голосованием вообще. Сам по себе факт просмотра или покупки чего-либо без последующего голосования содержит полезную информацию о качестве объекта.
Сам перевод выполнял не я. Все благодарности karaboz [9].
Я не до конца уверен в точности перевода математических терминов, буду благодарен за уточнения!
Изначально обсуждение оригинала статьи [10] возникло в нашей FB-группе Лаборатория Социального Проектирования [11]. Там в комментах есть интересные вещи, которые я не стал вставлять в итак перегруженную статью.
Для того, чтобы лучше один раз увидеть, чем 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');
В приведённых ниже функциях дополнительно обрабатываются заминусованные объекты не получившие ни одного положительного голоса. В этом случае возвращается -число_минусов. В остальных случаях рейтинг будет находиться в диапазоне [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
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/sotsial-ny-e-seti/6729
Ссылки в тексте:
[1] Urban Dictionary: http://www.urbandictionary.com/
[2] Amazon: http://www.amazon.com//
[3] Wikipedia: http://ru.wikipedia.org/wiki/Квантиль
[4] фактов о Чаке Норрисе: http://ru.wikipedia.org/wiki/Факты_о_Чаке_Норрисе
[5] Reddit: http://blog.reddit.com/2009/10/reddits-new-comment-sorting-system.html
[6] Yelp: http://officialblog.yelp.com/2011/02/the-most-romantic-city-on-yelp-is.html
[7] Digg: http://about.digg.com/blog/algorithm-experiments-better-comments
[8] Binomial proportion confidence interval (Wikipedia): http://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval
[9] karaboz: http://habrahabr.ru/users/karaboz/
[10] обсуждение оригинала статьи: https://www.facebook.com/groups/260808967277517/permalink/399982970026782/
[11] Лаборатория Социального Проектирования: https://www.facebook.com/groups/260808967277517/
Нажмите здесь для печати.