Диссертация (1137159), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Поисковая система обычно осуществляет выборку τ в дваэтапа:1. Выбор множества претендентов ~τ ⊂ R , такого, что все элементы ~τ в той илииной степени релевантны поисковому запросу. Определение релевантностина данном этапе очень приближенное. Например, может быть использованлогический метод, рассматриваемый далее.2. Для каждого τ i ⊂ ~τ определяется его релевантность Rel (τ i ) , а затем ~τ сортируется в порядке уменьшения релевантности.

При сортировке некоторыеэлементы, имеющие релевантность ниже порогового значения, могут бытьисключены из выборки. Результирующей выборкой будет являться τ .1.1.2 Логический метод определения множества претендентовРассмотрим процесс определения множества претендентов ~τ , которыйобычно происходит с использованием логического метода.

Основная идеяданного метода заключается в том, что результирующее множество поисковогозапроса (например, «цепи Маркова») должно содержать только страницы,относящиеся ко всем уникальным термам запроса (в данном случае ими будутявляться «Маркова» и «цепи»). Затем ответ на поисковый запрос может бытьдан после просмотра всех документов, содержащих термы «Маркова» и «цепи»,используя пересечение множеств документов, содержащих любой из этих18термов (или оба терма), как результирующее множество претендентов. Этообъясняется тем, что основной задачей компонента индексации являетсяпостроение инвертированного индекса, являющегося структурой данных, вкоторой термам в соответствие ставятся документы (или же DOCID),содержащиеданныеслова.ВТаблице1.1представленпримеринвертированного индекса - одной из важных частей вышеупомянутоговнутреннего представления документов.

Запрос, таким образом, подвергаетсядекомпозиции в древовидную структуру с термами (т.е. атомарными словамиили фразами) в качестве листьев и логическими операторами в качестве узлов.Наиболее используемыми логическими операторами являются AND, OR иNOT,равнозначныеоперациям(пересечения),(объединения)и(дополнения) между множествами DOCID соответственно. В дальнейшем этисимволы будут использованы для того, чтобы различать операции надмножествами и логические операции. AND обычно используется в случаеотсутствияоператорамеждудвумятермами.Примерылогическихпредставлений поисковых запросов представлены в Таблице 1.2.Логическое сравнение – это простой путь получения ~τ потенциально релевантных документов, не представляющий их в порядке соответствия запро-су.Поэтому используются разные методы при сортировке ~τ и при получении τ .Таблица 1.1. Пример инвертированного индекса.ТермDOCID документов, содержащих данный термМаркова35, 678, 432,1839, 6456, …цепи7834, 889, 8912, 325, 91, …Таблица 1.2.

Примеры логических интерпретаций поисковых запросов.ЗапросЛогическая интерпретацияМаркова Цепи{Маркова} {Цепи}Маркова -Цепи{Маркова}Маркова (Цепь OR Процесс){Маркова} ({Цепь} {Процесс}){Цепи}191.1.3 Проблема ранжирования: переход от ~τ к τПосле определения ~τ происходит поиск зависимой от поискового запросафункции ранжирования или релевантностиRel ω : ~τ → [ 0, ∞ )такой, чтоRelω (τ i ) > Rel ω (τ j ) , если элемент τ i считается более релевантным запросу, чемτ j , и, таким образом, должен быть расположен в τ до него. Другими словамирезультирующее множество τ нужно отсортировать по убыванию значенияRelω .Функции классаRelωопределяют схему ранжирования, т.е. техарактеристики документа, которые были определены как значимые приформировании результатов для определенного поискового запроса.Логический метод в той или иной степени является применимым к любомунабору данных, однако проблема ранжирования в высшей степени зависит отокруженияU , из которого данные были извлечены.

Например, поисковыесистемы для веба постоянно сталкиваются с проблемой спама: веб-страницы,которыепытаются«перехитрить»поисковыесистемы,предоставляянеобычайно высокое значение Relω для конкурентоспособного ω : s , тем самымрассчитывая на увеличение количества появлений страницы в результатахпоиска. Данная проблема приводит к тому, что функция Relωдолжнаопределяться как можно тщательнее и скептически. Тем временем также нестоит отсеивать «честные» документы. Это приводит к тому, что решениепроблемы ранжирования результатов в неконтролируемой среде становитсяочень востребованным и перспективным.

Обычно спам не является проблемойв более контролируемых средах, таких как поисковые системы дляакадемических работ или внутренних сетей.Рассмотрим ранжирование в неконтролируемых средах, таких как Веб. Здесьфункция ранжирования принимает в расчет как внешние факторы (on-pagefactors): информационное содержимое и его размещение на странице, так ивнутренние факторы (inter-page factors): обычно, информация о том, какстраницы соотносятся с другими посредством гиперссылок и т.п. Основноевниманиеследуетуделитьвнутреннемуфакторугиперссылокмежду20страницами, однако сделаем небольшой обзор процесса ранжирования в целом.Мотивацией к изучению внутренних факторов является то, что все внешниефакторы находятся под полным контролем автора страницы. Изучениеразличных отношений внутри документа с гораздо большим числом страницпозволяет более эластично оценить качество исследуемой страницы.В общем случае, функция ранжирования поисковой системы для Вебавыбирается следующим образом:Rel ω (τ ) = Ρ(τ, ω)q(τ) ,(1.1)где Ρ(τ, ω) является показателем документа τ для запроса ω по внешнимфакторам, т.е.

насколько релевантна информация, расположенная на страницеτ , по отношению к запросу ω , а q (τ ) является качественной функцией от τ ,котораярассчитываетсянаоснованиифакторов,непредставленныхнепосредственно на самой странице. Качественная функция q может включатьв себя внутренние факторы страницы и признаки ручного вмешательства (т.е.страница была специально изменена для поднятия рейтинга и позиции врезультатах поиска).

Следует отметить, что q не является функцией, зависящейот запроса, а скорее присваивает обобщенный весовой коэффициент каждойстранице независимо от запроса. Функция q принимает значения в пределах[0;1], таким образом, умножение на q используется для дампинга ранговдокументов (т.е.

набранных ими «очков» по внешним факторам). Рассмотримдалее три возможных метода определения Ρ(τ, ω) .1.1.3.1 Логический метод ранжированияПредставим простейшую поисковую систему, принимающую Ρ(τ, ω) =1, врезультате имеющую Rel ω (τ ) = q(τ ) . Результирующее множествоτбудетсостоять исключительно из множества претендентов ~τ , отсортированного поубыванию значения q. Так функционирует чисто логическая поисковаясистема: все страницы, имеющие любое отношение к термам, которые ищетпользователь, одинаково релевантны поисковому запросу.211.1.3.2 Ранжирование на основе вектора документаРассмотрим подход к ранжированию с использованием вектора документа,который является достаточно популярной технологией.Первым предположением в данной модели является то, что документ τдолжен иметь высокий рейтинг по терму ωi , если данный терм частовстречается на этой странице. Предположим, что запрос ω2 состоит из Lтермов: ω1 ..ω L . Зададим частоту термов, TFω (τ ) , как отношение количестваiпоявлений терма ωi в документе к размеру ( S τ ) документа в некоторыхудобных единицах измерения (например, количество слов или байтов).Далее, предположим, что некоторые термы более значимы при поиске, чемдругие.

Стандартный метод определения значимости термов заключается внахождении обратной частоты документа (Inverse Document Frequency, IDF).Предположим, Rωi является подмножеством репозитория R и состоит издокументов, содержащих терм ωi . Вероятность того, что документ, выбранныйслучайно, будет содержать терм ωi , такова: p =|R | .ωi|R|В теории информацииШэннона [92] это соответствует собственной информации (self-information)log 2 (1) .

На основании этого определяется инверсивная частота документаpIDF(ωi ) = log(|R| ) ,|R |ωiт.е. логарифм отношения общего числа документов в репозитории к количествудокументов, содержащих терм ωi (обычно принято использовать логарифм пооснованию 10). Инверсивная частота документа представляет собой оценкуколичества информации, свойственной терму. Если терм часто встречается вдокументах, находящихся в репозитории, то вероятность того, что он весьмаобщий, высока, и поиск определенного ресурса при помощи поисковойсистемы не даст значительных результатов, поэтому ему присваивается низкоезначение IDF.

В Таблице 1.3 представлены примеры вычисленных значений22IDF для некоторых термов (в примере используются словосочетания),относящихся к хорошо известной теории множеств, но с возрастающейстепенью обобщения и, поэтому, с убывающим количеством содержащейся вдокументах полезной информации.TF и IDF будут использоваться для определения оценки документа.

Длякаждого τ ∈ ~τ определим вектор документа δτ , состоящий из L элементов (поодному для каждого терма), такой, что выполняется соотношение:[δ τ ]i = IDF(ωi ) ⋅ TFωi (τ ) .Элементы вектора документа, таким образом, являются относительнойединицей измерения отношения частоты вхождений терма в документ к частотепоявления терма в репозитории в целом и, по существу, данные элементыпринимают во внимание как значимость терма в документе, так и егопредполагаемую информационную значимость.Таблица 1.3.IDF ,вычисленные поисковой системой Yahoo, при|R|приблизительно равном 20 ⋅ 10 9ТермКоличество вхожденийIDFтеорема Перрона - Фробениуса82706.38цепь Маркова10500004.28Теория вероятностей109000003.26математика929000002.33наука8160000001.39Можно рассматривать поисковый запрос (ПЗ) как документ сортов, в котором каждый из термов запроса встречается только один раз.

Пусть υ - это Lвектор для каждого υ i = Sυ−1 IDF (ω i ) , где Sυ - это размер ПЗ, представленный втех же единицах измерения, что и размер упоминавшегося документа. Помимоэтого, можно рассматривать это как вектор документа для запроса. Посколькунеизвестно, как пользователь задает приоритеты термам в его запросе, весовыекоэффициенты термам будут присвоены в соответствии с их IDF.23Определим зависящую от запроса часть функции отношения, т.е. Ρ(τ, ω) в(1.1), чтобы установить соответствие между δτи υ , а определениемсоответствия, в данном случае, будет являться угол между векторами в Lпространстве:δτ ⋅ υΡ(τ, ω) = cos( ∠(δ τ ,υ)) =δτ2⋅υ(1.2)2Пример 1.

Продемонстрируем векторную модель на практике, рассмотревпроцесс поиска для запроса «связный граф».В хорошо известной поисковой системе для Веба можно обнаружитьпримерно 20 ⋅ 10 9 документов, в которых терм «связный» встречается в 7 ⋅10 9документах, а терм «граф» в 150 ⋅10 6 документах. Таким образом, значения IDFбудут следующими: IDF(связный) = 0.46 и IDF(граф) = 2.1.

Характеристики

Список файлов диссертации