Ранжирование запросов - одна из фундаментальных проблем информационного поиска [1] (IR), научной / инженерной дисциплины, лежащей в основе поисковых систем . Учитывая запрос q и набор документов D , соответствующих запросу, проблема состоит в том, чтобы ранжировать, то есть отсортировать документы в D по некоторому критерию, чтобы «лучшие» результаты появлялись раньше в списке результатов, отображаемом для Пользователь. Ранжирование с точки зрения поиска информации является важным понятием в информатике и используется во многих различных приложениях, таких как запросы поисковых систем и рекомендательные системы.. Большинство поисковых систем используют алгоритмы ранжирования, чтобы предоставлять пользователям точные и релевантные результаты.
История [ править ]
Понятие рейтинга страниц восходит к 1940-м годам, а идея возникла в области экономики. В 1941 году Василий Леонтьев разработал итерационный метод оценки сектора страны, основанный на важности других секторов, которые поставляли ему ресурсы. В 1965 году Чарльз Хаббелл из Калифорнийского университета в Санта-Барбаре опубликовал методику определения важности людей на основе важности людей, которые их поддерживают.
Габриэль Пински и Фрэнсис Нарин предложили подход к ранжированию журналов. Их правило заключалось в том, что журнал важен, если на него ссылаются другие важные журналы. Джон Клейнберг , специалист по информатике из Корнельского университета , разработал почти идентичный подход к PageRank, который получил название поиск по темам, вызванный гипертекстом, или HITS, и рассматривал веб-страницы как «центры» и «авторитеты».
Алгоритм Google PageRank был разработан в 1998 году основателями Google Сергеем Брином и Ларри Пейджем и является ключевой частью метода Google для ранжирования веб-страниц в результатах поиска. Все вышеперечисленные методы в чем-то похожи, поскольку все они используют структуру ссылок и требуют итеративного подхода. [2]
Модели ранжирования [ править ]
Функции ранжирования оцениваются различными способами; один из самых простых - это определение точности первых k результатов с наивысшим рейтингом для некоторого фиксированного k ; например, доля 10 лучших результатов, релевантных в среднем по многим запросам.
IR-модели можно условно разделить на три типа: булевы модели или BIR, модели векторного пространства и вероятностные модели. [3]
Логические модели [ править ]
Логическая модель или ЗБИ - это простая базовая модель запроса, в которой каждый запрос следует основополагающим принципам реляционной алгебры с алгебраическими выражениями и где документы не выбираются, если они полностью не совпадают друг с другом. Поскольку запрос либо извлекает документ (1), либо не извлекает документ (0), нет методологии для их ранжирования.
Модель векторного пространства [ править ]
Поскольку логическая модель выбирает только полные совпадения, она не решает проблему частичного совпадения документов. Модель векторного пространства решает эту проблему путем введения векторов элементов индекса, каждому из которых присвоены веса. Веса варьируются от положительного (если совпадают полностью или в некоторой степени) до отрицательных (если не совпадают или полностью противоположно сопоставлены), если документы присутствуют. Частота термина - обратная частота документа ( tf-idf ) - один из самых популярных методов, где веса - это термины (например, слова, ключевые слова, фразы и т. Д.), А размеры - это количество слов в корпусе.
Оценка сходства между запросом и документом может быть найдена путем вычисления значения косинуса между вектором веса запроса и вектором веса документа с использованием подобия косинуса. Требуемые документы могут быть получены путем ранжирования их в соответствии с оценкой сходства и из k документов, которые имеют самые высокие оценки или наиболее релевантны вектору запроса.
Вероятностная модель [ править ]
В вероятностной модели теория вероятностей использовалась в качестве основного средства для моделирования процесса поиска в математических терминах. Вероятностная модель поиска информации была введена Мароном и Кунсом в 1960 году и в дальнейшем развита Роберстоном и другими исследователями. Согласно Спаку Джонсу и Уиллетту (1997): Основание для введения вероятностных концепций очевидно: системы IR работают с естественным языком, и это слишком неточно, чтобы позволить системе с уверенностью утверждать, какой документ будет иметь отношение к конкретному запросу.
Модель применяет теорию вероятности к поиску информации (вероятность возникновения события составляет от 0 до 100 процентов). т.е. в вероятностной модели релевантность выражается в терминах вероятности. Здесь документы ранжируются в порядке уменьшения вероятности релевантности. Он принимает во внимание элемент неопределенности в IR-процессе. т. е. неуверенность в том, соответствуют ли документы, полученные системой, заданному запросу.
Вероятностная модель предназначена для оценки и вычисления вероятности того, что документ будет соответствовать заданному запросу на основе некоторых методов. «Событие» в этом контексте поиска информации относится к вероятности соответствия между запросом и документом. В отличие от других моделей IR, вероятностная модель не рассматривает релевантность как точное измерение несовпадения или совпадения.
Модель использует различные методы для определения вероятности релевантности между запросами и документами. Релевантность в вероятностной модели оценивается по сходству между запросами и документами. Оценка подобия дополнительно зависит от частоты термина.
Таким образом, для запроса, состоящего только из одного термина (B), вероятность того, что конкретный документ (Dm) будет сочтена релевантным, представляет собой соотношение пользователей, которые отправляют термин запроса (B) и считают документ (Dm) релевантным в отношение к количеству пользователей, представивших термин (B). Как представлено в модели Марона и Куна, это может быть представлено как вероятность того, что пользователи, отправившие конкретный термин запроса (B), сочтут отдельный документ (Dm) релевантным.
По словам Солтона и МакГилла, суть этой модели заключается в том, что если можно рассчитать оценки вероятности появления различных терминов в соответствующих документах, то вероятность того, что документ будет извлечен, при условии, что он релевантен или что он нет, можно оценить.
Несколько экспериментов показали, что вероятностная модель может давать хорошие результаты. Однако такие результаты не были значительно лучше, чем результаты, полученные с использованием модели булевого или векторного пространства.[4] [5]
Меры оценки [ править ]
Наиболее распространенными критериями оценки являются точность, отзывчивость и f-балл. Они вычисляются с использованием неупорядоченных наборов документов. Эти меры должны быть расширены или должны быть определены новые меры для оценки результатов ранжированного поиска, которые являются стандартными для современных поисковых систем. В контексте ранжированного поиска подходящие наборы извлеченных документов, естественно, задаются первыми k извлеченными документами. Для каждого такого набора значения точности и отзыва могут быть нанесены на график, чтобы получить кривую точности-отзыва. [6]
Точность [ править ]
Точность измеряет точность процесса поиска. Если фактический набор соответствующих документов обозначен I, а полученный набор документов обозначен O, то точность определяется следующим образом:
Напомним [ править ]
Отзыв - это мера полноты IR-процесса. Если фактический набор соответствующих документов обозначен I, а извлеченный набор документов обозначен O, то отзыв определяется следующим образом:
F1 Score [ править ]
F1 Score пытается совместить точность и отзывчивость. Это гармоническое среднее из двух. Если P - точность, а R - отзыв, тогда оценка F определяется по формуле:
Алгоритм ранжирования страницы [ править ]
PageRank алгоритм выводит распределение вероятностей , используемое для представления вероятности того , что человек , случайно перейдя по ссылкам , будет поступать в какой - либо конкретной странице. PageRank можно рассчитать для коллекций документов любого размера. В нескольких исследовательских работах предполагается, что распределение равномерно распределяется между всеми документами в коллекции в начале вычислительного процесса. Для вычисления PageRank требуется несколько проходов через коллекцию, чтобы скорректировать приблизительные значения PageRank, чтобы они более точно отражали теоретическое истинное значение. Формулы приведены ниже:
т.е. значение PageRank для страницы u зависит от значений PageRank для каждой страницы v, содержащейся в наборе B u (набор, содержащий все страницы, ссылающиеся на страницу u ), деленных на количество L ( v ) ссылок со страницы v .
Алгоритм HITS [ править ]
Подобно PageRank, HITS использует анализ ссылок для анализа релевантности страниц, но работает только с небольшими наборами подграфов (а не с целым веб-графом) и зависит от запроса. Подграфы ранжируются в соответствии с весами в хабах и центрах, где выбираются и отображаются страницы с наивысшим рейтингом. [7]
См. Также [ править ]
- Учимся ранжировать : применение машинного обучения к проблеме ранжирования
Ссылки [ править ]
- ^ Пикколи, Габриэле; Пиньи, Федерико (июль 2018 г.). Информационные системы для менеджеров: с делами (Ред. 4.0). Проспект Пресс. п. 28. ISBN 978-1-943153-50-3. Проверено 25 ноября 2018 года .
- ↑ Franceschet, Massimo (17 февраля 2010 г.). «Ученый находит алгоритм типа PageRank 1940-х годов» . www.technologyreview.com.
- ^ Датта, Joydip (16 апреля 2010). «Рейтинг в поиске информации» (PDF) . Департамент компьютерных наук и инженерии Индийского технологического института. п. 7 . Проверено 25 апреля 2019 года .
- ^ Чу, Х. Представление информации и поиск в цифровую эпоху. Нью-Дели: Публикация Ess Ess.
- ^ GGChoudhary. Введение в современный поиск информации. Facet Publishing.
- ^ Мэннинг, Кристофер; Рагхаван, Прабхакар; Schutze, Hinrich. Оценка результатов ранжированного поиска . Издательство Кембриджского университета.
- ^ Тэнасе, Ракула; Раду, Ремус (16 апреля 2010 г.). «Лекция №4: Алгоритм HITS - хабы и авторитеты в Интернете» .
