Информационно-поисковые системы. Сычев А.В г.1 Контекстно- сфокусированный поиск Воронежский государственный университет Факультет компьютерных наук Кафедра информационных систем

Информационно-поисковые системы. Сычев А.В г.2 Степень охвата сети поисковыми системами В период становления сети Веб сбор документов выполнялся пауками малого и среднего масштаба. С 1996 г. по 1999 г. происходило уменьшение степени охвата поисковыми системами: 1997 г. - 35% 1999 г. - 18%. После 1999 г. рост Веб замедлился, функциональность сети улучшилась, как результат – степень охвата увеличилась до 45% - 55% (2000 г. - Google)

Информационно-поисковые системы. Сычев А.В г.3 Предварительные идеи При выдаче ответа на запрос релевантными оказывается лишь небольшая доля из всех выданных и следовательно ещё меньшая доля из скачанных пауком из Веб. Естественный вопрос: возможно ли организовать приоритетный сбор ресурсов из Веб? При этом следует руководствоваться следующими целями: Предпочтение должно отдаваться наиболее релевантным ресурсам Часто изменяемые документы могут быть предпочтительными для некоторых приложений, например новостных порталов Для вертикальных порталов, обслуживающие запросы относящиеся к одной или нескольким обширным темам, требуется строить индексы из документов, относящихся только к этим темам.

Информационно-поисковые системы. Сычев А.В г.4 Тематическая локализация Эксперимент Случайным образом выбираются два документа, вычисляется косинусная метрика подобия TF-IDF. Случайным образом выбираются два документа, связанных гиперссылкой с общим для них документом, выбранным случайным образом из коллекции; также оценивается их подобие. Для случайной страницы u выбираются документы, связанные с ней гиперссылками, но имеющие общий хост. Для случайной страницы u выбираются документы, связанные с ней гиперссылками, но принадлежащие различным хостам.

Информационно-поисковые системы. Сычев А.В г.5 Тематическая локализация В эксперименте использовалась выборка размером в документов из хранилища исследовательской ИПС Disco Web.

Информационно-поисковые системы. Сычев А.В г.6 Интерпретация результатов эксперимента: Экспериментально подтверждается тематическая кластеризация в сети Веб. Локальность типа Разные домены может быть использована для формирования стратегии расширения веб-графа для сетевого робота. Однако, проявление данного типа локальности быстро убывает с расстоянием в графе. По этой причине агрессивное расширение графа соседства исключено. В тоже время в графе существуют относительно длинные пути, сохраняющие тематическую релевантность Тематическая локализация

Информационно-поисковые системы. Сычев А.В г.7 Стандартный vs. сфокусированный сетевой робот Стандартный сетевой робот, использующий стратегиюприоритет в ширину будет последовательно уровень за уровнем скачивать страницы независимо от их релевантности, прежде чем достигнет целевого документа. Сфокусированный робот игнорирует нерелевантные документы. И таким образом, скачает лишь небольшое подмножество документов по пути к целевому документу.

Информационно-поисковые системы. Сычев А.В г.8 Сфокусированный поиск Радиус-1 гипотеза: Если страница u соответствует тематике, и с ней связана гиперссылкой страница v, тогда вероятность того, что v соответствует тематике выше чем соответствующая вероятность у случайно выбранной из страницы.

Информационно-поисковые системы. Сычев А.В г.9 Идея: Обучаемому классификатору предъявляется каждый вновь закачанный роботом документ u. Если классификатор по нему принимает положительное решение, то исходящие из него ссылки добавляются в очередь сетевого робота, иначе – игнорируются. Сфокусированный поиск

Информационно-поисковые системы. Сычев А.В г.10 Сфокусированный робот

Информационно-поисковые системы. Сычев А.В г.11 Сфокусированный поиск Операционное представление сфокусированного поиска

Информационно-поисковые системы. Сычев А.В г.12 Варианты реализации: Жесткий: Байесовский классификатор выносит бинарное пороговое решение по документу u (и соответственно по документам, на которые ссылается u). Мягкий: Оценка вероятности определяет приоритет документов в очереди, ссылки на которые, извлекаются из документа u. Сфокусированный поиск

Информационно-поисковые системы. Сычев А.В г.13 Откуда брать стартовую обучающую выборку? Решение: иерархический тематический каталог (Yahoo!, Open Directory и т.п.) Сфокусированный поиск

Информационно-поисковые системы. Сычев А.В г.14 Формализация задачи сфокусированного поиска Имеются: ориентированный гипертекстовый граф G иерархический тематический каталог C каждому узлу соответствуют некоторые документы из G, т.е. D(c) потребность пользователя задается подмножеством байесовский классификатор на основе TF-IDF-косинусной метрики для каждого поступающего документа q формирует оценку релевантности стартовое множество документов задается как D(С*) Целью является поиск на графе множества вершин достижимых из D(С*), таких, что максимизируется величина:

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

Информационно-поисковые системы. Сычев А.В г.16 Поиск авторитетов и концентраторов сфокусированным роботом Хорошие авторитеты находятся сфокусированным роботом на расстоянии гиперссылок от стартовых узлов. Концентраторы плохо выявляютсярадиус-1 сфокусированным роботом, поскольку содержат относительно мало описательной текстовой информации, а также имеют ссылки по нескольким темам.

Информационно-поисковые системы. Сычев А.В г.17 Сфокусированный поиск Радиус-2 гипотеза: Если страница u ссылается на много страниц v имеющих высокий показатель R(v), тогда u является хорошим концентратором; соседние по графу страницы w, на которые ссылается u, вероятнее всего имеют более высокую релевантность нежели страницы случайно выбранные из веб.

Информационно-поисковые системы. Сычев А.В г.18 Когда показатель результативности сфокусированного робота радиус-1 резко сокращается можно: Переключиться на документы, на которые указывают качественные концентраторы (используя один из вариантов HITS) – сетевой робот радиус-2 Использовать обратные ссылки Сфокусированный поиск

Информационно-поисковые системы. Сычев А.В г.19 Пример: если необходимо найти статьи по определенной ИТ-тематике, то можно начать поиск с веб-страниц факультетов ИТ профиля, содержащих ссылки на домашние страницы преподавателей и сотрудников, некоторые из которых могут содержать в свою очередь ссылки на статьи по интересующей тематике. Контекстно-сфокусированный поиск

Информационно-поисковые системы. Сычев А.В г.20 Необходимо построить обучающую структуру для нахождения путей в веб-графе, приводящих к релевантным документам: объектами, подлежащими классификации, являются документы (узлы графа); в качестве атрибутов документов рассматриваются термины, содержащиеся в них; по тексту документа на входе необходимо предсказать - сколько переходов по ссылкам необходимо выполнить до достижения релевантного документа; оценка указанного расстояния используется для отнесения документа к определенному уровню, определяющего порядок очередности обработки документов. Контекстно-сфокусированный поиск

Информационно-поисковые системы. Сычев А.В г.21 Таким образом, строится следующий контекстный граф: Стартовый документ образует 0-й уровень. Документы, ссылающиеся на документ 0-го уровня попадают на 1-й уровень и т.д. Контекстный граф

Информационно-поисковые системы. Сычев А.В г.22 Контекстный граф

Информационно-поисковые системы. Сычев А.В г.23 Построенный контекстный граф показывает: темы, прямо или косвенно связанные с целевой темой; пути связывающие документы в графе с целевыми документами. Далее, контекстные графы для всех стартовых документов объединяются, образуя объединенный контекстный граф. Контекстный граф

Информационно-поисковые системы. Сычев А.В г.24 Объединенный контекстный граф используется байесовскими классификаторами для распределения вновь поступающих от сетевого робота документов по уровням контекстного графа и фактически для построения приоритетных очередей обработки документов. Наиболее приоритетными являются очереди документов, находящихся на нижележащих уровнях контекстного графа. Контекстно-сфокусированный поиск

Информационно-поисковые системы. Сычев А.В г.25 Структура контекстно-сфокусированного робота-паука

Информационно-поисковые системы. Сычев А.В г.26 Эксперимент

Информационно-поисковые системы. Сычев А.В г.27 Литература S. ChakrabartiMining the Web. Discovering Knowledge from Hypertext Data. Morgan Kaufmann Publishers, S. ChakrabartiMining the Web. Discovering Knowledge from Hypertext Data. Morgan Kaufmann Publishers, 2003 Brian D. Davison. Topical locality in the Web. In Proceedings of the 23rd Annual International Conference on Research and Development in Information Retrieval (SIGIR 2000), Athens, Greece, July Brian D. Davison. Topical locality in the Web. In Proceedings of the 23rd Annual International Conference on Research and Development in Information Retrieval (SIGIR 2000), Athens, Greece, July M.Diligenti, F.M.Coetzee, S.Lawrence, C.L. Giles, M.GoriFocused Crawling Using Context Graphs. Proceedings of the 26 th VLDB Conference, pp M.Diligenti, F.M.Coetzee, S.Lawrence, C.L. Giles, M.Gori Focused Crawling Using Context Graphs. Proceedings of the 26 th VLDB Conference, pp