Описание метода ранжирования

Что такое метод ранжирования

Ранжирование — это отношение между множеством элементов, часто записанных в виде списка, такое, что для любых двух элементов первый либо ранжирован «выше, чем», «ниже, чем», либо «равно» второму. В математике это известно как слабый порядок или полный предварительный порядок объектов. Это не обязательно полный порядок объектов, потому что два разных объекта могут иметь одинаковые ранги. Сами ранги являются абсолютно упорядоченными. Например, материалы полностью упорядочены по твердости, а степени твердости полностью упорядочены. Если два предмета имеют одинаковый ранг, это считается равенством.

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

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

Цель обучения — выучить функцию ранжирования, которая позволяет отсортировать элементы таким образом, чтобы максимизировать их релевантность запросу или предпочтениям пользователя. Это очень важно для таких поисковых систем, как Google или Bing, где порядок результатов поиска может существенно повлиять на удовлетворенность и вовлеченность пользователей.

При вычислении порядкового измерения две (или более) ранжируемые величины могут быть равны. В таких случаях может быть принята одна из приведенных ниже стратегий присвоения рангов.

1. Стандартный (1224) — предметы, которые сравниваются одинаково, получают одинаковые номера ранжирования, а в номерах ранжирования остается пробел. Количество ранговых номеров, оставшихся в этом промежутке, на один меньше, чем количество предметов, которые сравнивались на равных. Это распространенная стратегия ранжирования. Используется в соревнованиях, поскольку она означает, что если два (или более) участника сравняются в рейтинге, то это не повлияет на положение всех тех, кто занял место ниже них (т. е. участник займет второе место, если ровно один человек набрал больше очков, третье — если ровно два, четвертое — если ровно три и т. д.).
2. Модифицированный (1334) — иногда при соревновательном ранжировании пробелы в ранговых числах оставляют перед наборами предметов с равными рангами (а не после них, как при стандартном соревновательном ранжировании). Количество ранговых номеров, оставленных в этом промежутке, на один меньше, чем количество равных предметов. При таком ранжировании участник занимает второе место только в том случае, если он набрал больше баллов, чем все его соперники, кроме одного, третье — если он набрал больше, чем все соперники, кроме двух, и т. д.
3. Плотный (1223) — предметы, которые сравниваются на равных, получают одинаковый номер рейтинга, а следующий предмет (предметы) получает сразу следующий номер рейтинга. Эквивалентно, ранговый номер каждого предмета равен 1 плюс количество предметов, расположенных выше него, которые отличаются друг от друга по порядку ранжирования.
4. Процентный (0..1) — Проценты варьируются от 1 до 99 в целых числах. Округление всегда происходит в большую сторону, например, 10,1 перцентиль становится 11. В отличие от обычной математической практики, меньшее число означает лучший результат.
5. Порядковое ранжирование (1234) — все предметы получают отдельные порядковые номера, включая предметы, которые сравниваются между собой. Присвоение отдельных порядковых номеров равнозначным предметам может осуществляться случайным образом или произвольно, но в целом предпочтительнее использовать произвольную, но последовательную систему, так как она дает стабильные результаты при многократном ранжировании. Примером произвольной, но последовательной системы может быть включение в порядок ранжирования других атрибутов (например, алфавитного порядка имени конкурента), чтобы гарантировать, что ни один из двух пунктов не совпадает в точности. В компьютерной обработке данных порядковое ранжирование также называют нумерацией строк.

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

В информационном поиске

Функции ранжирования оцениваются различными способами; один из самых простых — определение точности первых k результатов, занимающих верхние строчки, для некоторого фиксированного k; например, доля 10 лучших результатов, которые являются релевантными, в среднем по многим запросам.

Модели информационном поиске можно разделить на три типа:

1. Булева модель поиска — это модель поиска информации, в которой запрос имеет форму булева выражения терминов в сочетании с операторами ДА, ИЛИ и НЕТ. Модель рассматривает каждый документ как просто набор слов. Простая модель, основанная на теории множеств и булевой алгебре. Булева модель, предсказывает, что каждый документ является релевантным или нерелевантным.

2. Модель векторного пространства — это математическая структура, используемая в информационном поиске и обработке естественного языка для представления и анализа текстовых данных. Она является основополагающей для интеллектуального анализа текстов, поиска документов и задач машинного обучения на основе текстов, таких как классификация документов, поиск информации и анализ сходства текстов. 

   Модель векторного пространства представляет документы и термины как векторы в многомерном пространстве. Каждое измерение соответствует уникальному термину во всем корпусе документов. Каждое измерение соответствует уникальному термину, а документы и запросы могут быть представлены в виде вектора в этом пространстве.

3. Вероятностная модель поиска основана на принципе вероятностного ранжирования, который гласит, что информационно-поисковая система должна ранжировать документы в зависимости от вероятности их соответствия запросу, учитывая все имеющиеся данные. Модель применяет теорию вероятности к информационному поиску (событие имеет вероятность наступления от 0 до 100 процентов). Т.е. в вероятностной модели релевантность выражается в терминах вероятности. Здесь документы ранжируются в порядке убывания вероятности релевантности. Она учитывает элемент неопределенности в процессе ИК, т. е. неопределенность в отношении того, являются ли документы, полученные системой, релевантными данному запросу. Релевантность в вероятностной модели оценивается по сходству между запросами и документами. Суждение о сходстве дополнительно зависит от частоты терминов.

Для чего применяется

Ранжирование с точки зрения информационного поиска является важной концепцией в информатике и используется во многих различных приложениях, таких как запросы в поисковых системах и рекомендательные системы. Большинство поисковых систем используют алгоритмы ранжирования для предоставления пользователям точных и релевантных результатов.

Преимущества и недостатки

Преимущества:

Преимуществом данного метода измерения является простота измерительных процессов, которые не требуют какой-либо тщательной подготовки специалистов.

Недостатки:

Недостатком ранжирования является непрактичное расположение большого количества объектов. Как показывает практика применения этого метода, при большом количестве объектов (15-20) специалистам сложно ранжировать их. Это связано с тем, что в ходе оценки эксперт должен установить взаимосвязи между всеми объектами и рассматривать их как единицу.

С увеличением числа объектов число связей между ними увеличивается пропорционально квадрату числа объектов. Способность запоминать и анализировать большой набор связей между объектами ограничивается умственными способностями человека. Поэтому при оценке загруженности объектов эксперты могут допускать серьезные ошибки.

Примеры

Шаг 1: Корпус документов и запрос
Начнем с небольшого корпуса из трех документов и запроса:

Документ 1: «Быстрая коричневая лиса перепрыгивает через ленивую собаку».
Документ 2: «Коричневая собака погналась за лисой».
Документ 3: «Собака ленивая».

Запрос: «коричневая собака»

Шаг 2: Создание матрицы документов и терминов (DTM)
Мы создаем матрицу DTM, в которой строки представляют документы, а столбцы — термины. Мы будем использовать значения TF-IDF (Частота терминов и обратная частота документов) для каждого термина в матрице:

| | коричневая | преследуемая | собака | лиса | прыгает | лениво | через | быструю | лисицу |
|--------|---|-------|--------|-----|-----|----|-------|------|-------|-----|
| Док 1 | 0 | 0,29 | 0 | 0,29 | 0,29 | 0 | 0,29 | 0,29 | 0,29 | 0,29 | 0,58 |
| Док 2 | 0,41 | 0,29 | 0,41 | 0,29 | 0,29 | 0 | 0 | 0 | 0 | 0 | 0,41 |
| Док 3 | 0 | 0 | 0 | 0.41 | 0 | 0.41 | 0 | 0.41 | 0 | 0.41 | 0 | 0 | 0.41 |
| Запрос | 0 | 0,71 | 0 | 0,71 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Здесь рассчитали значения TF-IDF для каждого термина в документах и запросе.

Шаг 3: Векторизация запроса
Запрос также представляется в виде вектора. В данном случае это простой двоичный вектор, где 1 означает наличие термина, а 0 — его отсутствие:

| | а | коричневая | преследуемая | собака | лиса | прыгает | лениво | через | быструю | лисицу |.
|--------|---|-------|--------|-----|-----|----|-------|------|-------|-----|
| Запрос | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

Шаг 4: Вычисление коэффициента Отиаи
Теперь рассчитаем коэффициент Отиаи между вектором запроса и каждым вектором документа. Формула выглядит следующим образом:

Коэффициента Отиаи = (вектор запроса * вектор документа) / ||вектор запроса|| * ||вектор документа||

Документ 1 ≈ 0,58
Документ 2 ≈ 0,29
Документ 3 ≈ 0,41

Шаг 5: Ранжирование документов по сходству
Документы ранжируются по значениям коэффициента Отиаи в порядке убывания:

Документ 1: Косинусное сходство ≈ 0.58
Документ 3: Косинусное сходство ≈ 0.41
Документ 2: косинусное сходство ≈ 0,29
Таким образом, на основе косинусного сходства документ 1 является наиболее релевантным запросу «коричневая собака», за ним следует документ 3, а затем документ 2. Это демонстрирует, как модель векторного пространства может быть использована для поиска информации и ранжирования документов на основе их сходства с запросом.