Вычисление сходства между двумя списками

Question

РЕДАКТИРОВАТЬ: так как все запутались, я хочу упростить свой вопрос.У меня есть два упорядоченных списка.Теперь я просто хочу вычислить, насколько похож один список на другой.

Например,

1,7,4,5,8,9
1,7,5,4,9,6

Что является хорошим показателем сходства между этими двумя списками, так что порядок важен.Например, мы должны оштрафовать сходство, так как в двух списках поменялось 4,5?

У меня 2 системы.Одна современная система и одна система, которую я внедрил.По запросу обе системы возвращают ранжированный список документов.Теперь я хочу сравнить сходство между моей системой и «современной системой», чтобы измерить правильность моей системы.Обратите внимание, что порядок документов важен, поскольку речь идет о ранжированной системе.Кто-нибудь знает какие-либо меры, которые могут помочь мне найти сходство между этими двумя списками.

Answer 1

DCG [Discount Cumulative Gain] и nDCG [нормализованная DCG] обычно являются хорошей мерой для ранжированных списков.

Это дает полное усиление для соответствующего документа, если он занимает первое место, и усиление уменьшается с уменьшением ранга.

Использование DCG / nDCG для оценки системы по сравнению с базовой линией SOA:

Примечание. Если вы установите все результаты, возвращенные "современной системой", как соответствующие, то ваша система будет идентична уровню техники, если они получили одинаковый ранг с использованием DCG / nDCG.

Таким образом, возможная оценка может быть: DCG(your_system)/DCG(state_of_the_art_system)

Чтобы дополнительно улучшить его, вы можете дать оценку релевантности [ релевантность не будет двоичной ] - и будет определяться в зависимости от того, как каждый документ был ранжирован в соответствии с уровнем техники. Например, rel_i = 1/log(1+i) для каждого документа в современной системе.

Если значение, полученное с помощью этой функции оценки, близко к 1: ваша система очень похожа на базовую линию.

Пример:

mySystem = [1,2,5,4,6,7]
stateOfTheArt = [1,2,4,5,6,9]

Сначала вы даете оценку каждому документу в соответствии с современной системой [используя формулу сверху]:

doc1 = 1.0
doc2 = 0.6309297535714574
doc3 = 0.0
doc4 = 0.5
doc5 = 0.43067655807339306
doc6 = 0.38685280723454163
doc7 = 0
doc8 = 0
doc9 = 0.3562071871080222

Теперь вы вычисляете DCG(stateOfTheArt) и используете релевантность, как указано выше [примечание релевантность здесь не является двоичной, и вы получаете DCG(stateOfTheArt)= 2.1100933062283396
Далее рассчитайте его для вашей системы , используя те же веса отклика и получите: DCG(mySystem) = 1.9784040064803783

Таким образом, оценка составляет DCG(mySystem)/DCG(stateOfTheArt) = 1.9784040064803783 / 2.1100933062283396 = 0.9375907693942939

Answer 2

Kendalls tau - это та метрика, которую вы хотите. Он измеряет количество парных инверсий в списке. Правило стопы Спирмена делает то же самое, но измеряет расстояние, а не инверсию. Они оба предназначены для выполнения поставленной задачи, измеряя разницу в двух ранжированных списках.

Answer 3

В дополнение к тому, что уже было сказано, я хотел бы указать вам на следующую превосходную статью: W.Уэббер и др. Мера сходства для неопределенных рейтингов (2010) .Помимо содержания хорошего обзора существующих мер (таких как вышеупомянутые Kendall Tau и Footrule Спирмена), авторы предлагают интуитивно привлекательную вероятностную меру, которая применима для различной длины списков результатов и когда не все элементы встречаются в обоих списках.Грубо говоря, параметризуется вероятность «постоянства» p, что пользователь сканирует элемент k + 1 после проверки элемента k (а не отказа). Ранговое перекрытие (RBO) - ожидаемый коэффициент перекрытия результатов в момент, когда пользователь прекращает чтение.

Реализация RBO несколько более сложна;Вы можете взглянуть на реализацию в Apache Pig здесь .

Другая простая мера - косинусное сходство , косинус между двумя векторами с размерами, соответствующими элементам, иобратные звания как веса.Тем не менее, он не обрабатывает элементы изящно, которые встречаются только в одном из списков (см. Реализацию в ссылке выше).

1. Для каждого элемента i в списке 1, пусть h_1 (i) =1 / RANK_1 (я).Для каждого элемента i в списке 2, отсутствующего в списке 1, пусть h_1 (i) = 0. То же самое для h_2 относительно списка 2.
2. Вычислить v12 = sum_i h_1 (i) * h_2 (i);v11 = sum_i h_1 (i) * h_1 (i);v22 = sum_i h_2 (i) * h_2 (i)
3. Return v12 / sqrt (v11 * v22)

Для вашего примера это дает значение 0,7252747.

Пожалуйста, позвольте мне дать вам несколько практических советов, помимо вашего непосредственного вопроса.Если базовый уровень вашей «производственной системы» не совершенен (или мы имеем дело с набором золота), почти всегда лучше сравнивать показатель качества (такой как вышеупомянутая nDCG), а не сходство;новый рейтинг будет иногда лучше, иногда хуже базового уровня, и вы хотите знать, случается ли первый случай чаще, чем второй.Во-вторых, меры подобия нетривиальны для интерпретации в абсолютном масштабе.Например, если вы получаете оценку сходства, скажем, 0,72, означает ли это, что она действительно похожа или существенно отличается?Меры сходства более полезны, когда говорят, что, например, новый метод ранжирования 1 ближе к производству, чем другой новый метод ранжирования 2.

Answer 4

Как вы сказали, вы хотите вычислить, насколько похож один список на другой.Я думаю упрощенно, вы можете начать с подсчета количества инверсий.Существует O (NlogN) разделяй и властвуй подход к этому.Это очень простой подход для измерения «сходства» между двумя списками.

например, вы хотите сравнить, насколько «похожи» музыкальные вкусы для двух человек на музыкальном веб-сайте, вы берете их рейтинг набора песен и считаете «нет».инверсий в нем.Чем меньше количество, тем «схожее» их вкус.

, поскольку вы уже рассматриваете «современную систему» ​​как эталон правильности, подсчет Инверсии должен дать вам основную меру «сходства»вашего рейтинга.Конечно, это всего лишь стартовый подход, но вы можете основываться на нем, насколько строгим вы хотите быть с «пробелом инверсии» и т. Д.

    D1 D2 D3 D4 D5 D6
    -----------------
R1: 1, 7, 4, 5, 8, 9  [Rankings from 'state of the art' system]
R2: 1, 7, 5, 4, 9, 6  [ your Rankings]

Поскольку рейтинги расположены в порядке документов, вы можете написать свойсобственная функция компаратора на основе R1 (ранжирование «современной системы» и, следовательно, подсчет инверсий по сравнению с этим компаратором.

Вы можете «штрафовать» «сходство» за каждую найденную инверсию: i 'R2 [j]
(>' здесь вы используете свой собственный компаратор)

Ссылки, которые вы можете найти полезными:
Link1
Link2
Link3

Answer 5

Я на самом деле знаю четыре различных показателя для этой цели.

Три уже были упомянуты:

• NDCG
• Тау Кендалла
• Spearman's Rho

Но если у вас есть более двух рангов, которые нужно сравнить, используйте W Кендалла W .

Answer 6

Является ли список документов исчерпывающим?То есть каждый ранг документа, упорядоченный системой 1, также ранж, упорядоченный системой 2?Если так, то ро Спирмена может служить вашим целям.Когда они не используют одни и те же документы, возникает большой вопрос, как интерпретировать этот результат.Я не думаю, что есть измерение, которое отвечает на этот вопрос, хотя могут быть некоторые, которые реализуют неявный ответ на него.

Answer 7

Полагаю, вы говорите о сравнении двух информационно-поисковых систем, которые мне доверяют, не является чем-то тривиальным.Это сложная проблема информатики.

Для измерения релевантности или проведения А / Б-тестирования необходимо иметь несколько вещей:

1. Конкурент для измерения релевантности,Поскольку у вас есть две системы, то это предварительное условие выполнено.

2. Вам необходимо вручную оценить результаты.Вы можете попросить своих коллег оценить пары запрос / URL для популярных запросов, а затем для дыр (т. Е. Для пары запрос / URL без оценки можно использовать функцию динамического ранжирования с помощью алгоритма «Обучение ранжированию» http://en.wikipedia.org/wiki/Learning_to_rank. Dont beУдивлен этим, но это правда (пожалуйста, прочитайте ниже пример Google / Bing).

Google и Bing являются конкурентами на рынке горизонтального поиска. Эти поисковые системы используют ручных судей по всемуи вкладывать в них миллионы, чтобы оценить свои результаты для запросов. Таким образом, для каждой пары «запрос / URL» обычно оцениваются результаты топ-3 или топ-5. На основе этих рейтингов они могут использовать такой показатель, как NDCG (нормализованное дисконтированное совокупное усиление), которыйявляется одним из лучших показателей и одним из самых популярных.

Согласно википедии:

Дисконтированный совокупный доход (DCG) - это мера эффективности алгоритма поисковой системы в Интернете или связанных приложений,часто используется при поиске информации. Используется шкала релевантности документов.В наборе результатов поисковой системы DCG измеряет полезность или прибыль документа на основе его положения в списке результатов.Усиление накапливается от верха списка результатов к низу, причем усиление каждого результата обесценивается на более низких рангах.

Википедия объясняет NDCG очень хорошо.Это короткая статья, пожалуйста, прочитайте.