Работая над проблемами ранжирования (ранжирование каналов, ранжирование в поиске и т. Д.), Я часто сталкивался с ситуациями, когда мне приходилось сравнивать ранжированные списки, созданные отдельными системами - например, «Производство» против A / B-теста. Необходимость сравнения двух или более ранжированных списков встречается чаще, чем вы думаете. Рассмотрим простой пример: вы и пара друзей решаете перечислить каждую из 5 ваших любимых серий популярного телесериала «ДРУЗЬЯ». Каждый записывает 5 названий своих любимых эпизодов, причем первый элемент указывает на его самый любимый, а последний элемент - на наименее любимый эпизод. Теперь каждый из вас может задаться вопросом, насколько ваш список похож или отличается от списка двух других друзей в комнате.

Как нам сравнивать эти списки? Формально эти ранжированные списки называются неполными ранжированием, потому что они не ранжируют все серии из «ДРУЗЬЯ», а вместо этого выбирают только пять лучших. Мы обсудим несколько подходов, которые популярны и довольно распространены в решение этой конкретной проблемы.

Метод 1: Кендалл Тау

Метрика Кендалла Тау, также известная как корреляция Кендалла, - это распространенный метод, используемый для проверки соответствия двух ранжированных списков.

Корреляцию Кендалла (𝛕) можно вычислить, сначала подсчитав количество согласованных пар (C) и количество несогласованных пар (D). Пара называется согласованной, если они появляются в одном и том же порядке в своих списках ранжирования.

M = (C -D)

𝛕 = M / (C + D)

Максимальное количество различных пар между двумя объединенными списками ранжирования в нашем примере (рис. 2) = 5. Выберите 2 = ½ * (5 * (5–1)) = 10. Если все пары согласованы, то C = 10 и D = 0, что означает max (𝛕) = (10–0) / (10 + 0) = 1. Если все пары не согласуются, то C = 0 и D = 10, что означает min (𝛕) = (0–10 ) / (0 + 10) = -1.

Давайте посчитаем фактическое значение 𝛕

Согласные пары:

(S6E17, S2E10) (S6E17, S3E24) (S6E17, S3E25) (S6E17, S3E15) (S2E10, S3E24) (S2E10, S3E25) (S2E10, S3E15) (S3E24, S3E25)

Дискордантные пары:

(S3E24, S3E15) (S3E25, S3E15)

𝛕 = (8–2) / (8 + 2) = 0.6

Интерпретация Кендалл Тау

Обратите внимание, что максимальное и минимальное значение, которое может принимать, равно +1 и -1 соответственно. +1 означает полное согласие, а -1 означает полное несогласие. Значение 0 означает, что между рейтингами нет корреляции. Значение 0,6, которое мы вычислили для рисунка 2, показывает нам, что рейтинги имеют среднюю корреляцию.

Другой способ интерпретации 𝛕 состоит в том, что его статистика M - это количество смежных попарных свопов, необходимых для упорядочения одного ранжированного списка таким образом, чтобы он напоминал другой. Это напоминает вам популярный алгоритм сортировки? Конечно же, пузырьковая сортировка!

Вы также можете проверить статистическую значимость метрики Кендалла Тау [8].

Реализация

Модифицированный Кендалл Тау может применяться к рейтингам, которые содержат связи - например, если человеку настолько понравился эпизод, что он указал один и тот же эпизод во всех трех из трех лучших слотов своего списка. Ничья в рейтинге не редкость. Недавно я реализовал собственный алгоритм Кендалла Тау O (NLogN), который обрабатывает связи в Netflix. Вот несколько реализаций алгоритма с открытым исходным кодом:

Использование

Кендалл Тау - популярный метод, используемый в задачах поиска информации, таких как поисковые системы и системы рекомендаций. Такие компании, как Yahoo [1] и Microsoft [3], использовали этот метод для различных случаев использования.

Недостатки

Хотя Кендалл Тау является популярной метрикой ранговой корреляции, у нее есть недостатки:

  1. Это требует, чтобы два списка ранжирования были соединены (одинаковые элементы в обоих списках).
  2. Он невзвешенный, то есть в нем уделяется столько же внимания разногласиям как внизу списка, так и вверху (в популярных поисковых системах результаты в «голове» имеют гораздо большее значение, чем результаты в «хвосте»).
  3. Вклад одной несогласованной пары уменьшается с увеличением глубины ранжирования, т. Е. Значений неразрывно связаны с глубиной ранжирующего списка.

Чтобы продемонстрировать эти недостатки, рассмотрим рейтинговые списки «Человек 1 против человека 2» на рис. 1. Обратите внимание, что есть только два общих эпизода между двумя списками: S2E10 и S3E24. К этим спискам нельзя применить корреляцию Кендалла, потому что они не являются составными (не содержат одинаковых элементов). Одним из возможных способов применения корреляции Кендалла к этим двум спискам является замена элементов, которых нет в обоих списках, специальным символом «#». Затем рейтинг человека 1 становится «# S2E10 # S3E24 #», а рейтинг человека 2 становится «# S2E10 # # S3E24». Вычисление 𝛕 для этого преобразованного списка приведет к значению 1.0, даже если S3E24 находится в позиции 3 в списке Person 1 и в позиции 4 в списке Person 2 (индекс, отсчитываемый от нуля). Это значение 1.0 означает полное соответствие между двумя списками - здесь явно не так.

Метод 2: перекрытие со смещением рангов (RBO)

В отличие от меры расстояния Кендалла Тау, RBO является мерой сходства. RBO решает 3 недостатка, наблюдаемых в Кендалл Тау, используя веса для каждой позиции в рейтинге. Веса выводятся из сходящегося ряда. Уравнение ниже описывает RBO двух бесконечных ранжированных списков S и T:

Параметр p - это настраиваемый параметр в диапазоне (0, 1), который можно использовать для определения вклада верхних d рангов в окончательное значение подобия RBO. мера. Обратите внимание, что член суммирования СУММ (p ^ (d -1)) сходится, поскольку это геометрический ряд. Его сумма равна 1 / (1- p), а поскольку 0 ‹p‹ 1, сумма конечна.

Чтобы получить единый балл RBO, мы можем экстраполировать его на основе доступной информации, предполагая, что согласие, наблюдаемое до глубины k, сохраняется неопределенно долго между двумя списками. Единый балл RBO можно рассчитать с помощью:

Вот простая (не прошедшая тщательную проверку) реализация экстраполированного показателя RBO с единственной оценкой в ​​Python 3:

Как выбрать значение «р»?

В показателе RBO выбор значения p определяет степень максимальной взвешенности, которую демонстрирует результирующий показатель RBO. Из статьи по RBO можно использовать следующее уравнение для расчета общего веса, который верхние ранги d вносят в расчет RBO:

Вот простая (не полностью протестированная) реализация вышеизложенного:

Для значения p = 0,9 и d = 10 (изучаются 10 лучших рангов) WRBO [1: d] составляет 0,8556, то есть 10 лучших рангов вносят 85,56% в окончательный показатель RBO. Следовательно, в зависимости от суммы вклада, которую вы хотели бы получить из верхних результатов d, вы можете выбрать значение p соответственно, используя уравнение WRBO [1: d] выше.

Устный перевод RBO

Как упоминалось выше, RBO принимает значения в диапазоне [0, 1], где 0 означает непересекающиеся, а 1 означает идентичные ранжированные списки.

Вернемся к примеру, когда Кендалл Тау не смог распознать явно несходные ранжированные списки, созданные человеком 1 и человеком 2:

Рейтинг человека 1 был «# S2E10 # S3E24 #»

Рейтинг человека 2 был «# S2E10 # # S3E24»

Я собираюсь выбрать p = 0,6, так как я хочу, чтобы три верхние позиции несли наибольший вес. При p = 0,6 верхние 3 позиции имеют 91,26% веса в окончательном показателе RBO. Подставляя значения Person 1 и Person 2, мы получаем RBO (Person1, Person2, p, k) = 0,24144, то есть значение RBO указывает на то, что два списка в основном различаются с небольшим сходством в трех верхних позициях. Увеличение значения p до 0,9 приводит к более высокому значению RBO, равному 0,352655, но, тем не менее, это значение может показать, что эти два списка различаются.

В заключение, RBO является более надежной мерой для оценки сходства неопределенных списков ранжирования, которые не обязательно являются объединенными, и его можно настроить для обеспечения максимальной взвешенности. Для дальнейшего чтения по RBO и теории, лежащей в основе этого, обратитесь к статье RBO [2].

дальнейшее чтение

Мы рассмотрели несколько способов сравнения двух разных наборов рейтингов. Вот еще несколько способов для дальнейшего чтения:

  • Корреляция Пирсона [5]
  • Тест Колмогорова-Смирнова [6]
  • Сравнение списков топ-k [7]

Немного пищи для размышлений

Наконец, я хочу дать вам повод задуматься:

Представьте себе случай, когда сравнить любые два элемента в списке не так-то просто. Скажите, что вы оцениваете 5 своих любимых событий чемпионата мира по футболу, сфотографировав это событие. Например, на рис. 3 показаны два изображения одного и того же события, когда Марио Гётце забил решающий гол в дополнительное время, но это разные изображения, сделанные с интервалом в несколько секунд. Если мы хотим вычислить RBO или Kendall Tau в ранжированных списках изображений, важно иметь возможность отличить два разных изображения одинаковыми. Как мы можем сравнить два изображения и сказать, что они относятся к одному и тому же событию?

использованная литература

[1] Кумар, Рави и Сергей Васильвицкий. «Обобщенные расстояния между рейтингами». Материалы 19-й международной конференции во всемирной паутине. 2010 г.

[2] Уильям Уэббер, Алистер Моффат и Джастин Зобель . 2010 . «Мера сходства для неопределенного ранжирования». ACM Trans. Инф. Syst. 28, 4, статья 20 (ноябрь 2010 г.), 38 стр. DOI: https: //doi.org/10.1145/1852102.1852106

[3] Бахрах, Йорам, Ральф Хербрих и Эли Порат. «Алгоритмы построения эскизов для аппроксимации ранговых корреляций в системах совместной фильтрации». Международный симпозиум по обработке строк и поиску информации. Шпрингер, Берлин, Гейдельберг, 2009.

[4] Атрибуция изображений чемпионата мира по футболу:

[левое изображение] Данило Боржес / Portal da Copa copa2014.gov.br Licença Creative Commons Atribuição 3.0, CC BY 3.0 ‹ https://creativecommons.org/licenses/by/3.0 ›, через Wikimedia Commons;

[правое изображение] Данило Борхес / copa2014.gov.br Licença Creative Commons Atribuição 3.0 Brasil, CC BY 3.0 BR ‹ https://creativecommons.org/licenses/by/3.0/br/deed.en ›, через Wikimedia Commons

[5] Бенести, Джейкоб и др. «Коэффициент корреляции Пирсона». Подавление шума при обработке речи. Springer, Берлин, Гейдельберг, 2009. 1–4.

[6] Мэсси-младший, Фрэнк Дж. «Тест Колмогорова-Смирнова на соответствие». Журнал Американской статистической ассоциации 46.253 (1951): 68–78.

[7] Фэджин, Рональд, Рави Кумар и Дакшинамурти Сивакумар. «Сравнение топ-k списков». Журнал SIAM по дискретной математике 17.1 (2003): 134–160.

[8] Тест значимости Кендалла Тау https://en.wikipedia.org/wiki/Kendall_rank_correlation_coefficient#Significance_tests