автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы информационного поиска тематических сообществ в Веб-пространстве

г ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

4847325

БЛЕКАНОВ Иван Станиславович

МЕТОДЫ ИНФОРМАЦИОННОГО ПОИСКА ТЕМАТИЧЕСКИХ СООБЩЕСТВ / В ВЕБ-ПРОСТРАНСТВЕ

05.13.01 - системный анализ, управление и обработка информации (по прикладной математике и процессам управления)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 9 МАЙ 2011

Санкт-Петербург 2011

4847325

Диссертация выполнена на кафедре технологии программирования факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета.

Научный руководитель;

кандидат физико-математических наук, доцент Сергеев Сергей Львович (СПбГУ)

Официальные доктор технических наук, профессор

оппоненты: Марлей Владимир Евгеньевич (СПГУВК)

кандидат физико-математических наук, Пашкевич Василий Эрикович

(ЗАО "Капитал Программ")

Ведущая организация:

Институт прикладных математических исследований Карельского научного центра Российской академии наук (ИПМИ КарНЦ РАН, г. Петрозаводск)

Защита диссертации состоится «_8_» июня 2011 года в часов на заседании диссертационного совета Д.212.232.50 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу 199034, Санкт-Петербург, Университетская наб., 7/9, Менделеевский центр.

С диссертацией можно ознакомиться в Научной библиотеке им. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9. Автореферат размещен на сайте www.spbu.ru

Автореферат разослан « 7 8 » <у. ij-СлД 2011 года.

Ученый секретарь диссертационного совета Д.212.232.50

доктор физико-математических наук, профессор (СПбГУ) Курбатова Галина Ибрагимовна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Наиболее распространенные современные системы поиска информации в Веб-пространстве (Google, Яндекс, Рамблер) имеют ряд проблем. Во-первых, это недостаточная актуальность информации\ Она возникает из-за того, что эти системы выполняют два вида работ: модификация индекса и поиск информации по запросам пользователей в индексе. Модификация индекса занимает большое количество времени (от дней до нескольких месяцев), что существенным образом снижает актуальность источников информации в Веб-пространстве. Во-вторых, ранжирование результатов поиска, существующих систем, основано на авторитетности документов в индексе и формальной близости документов к запросу пользователя. Отсутствие поиска по ссылкам в глубину часто приводит к ошибкам ранжирования.

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

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

системный анализ архитектурных особенностей поисковых роботов и систематизация набора критериев эффективности, которые могут применяться для реализации любых типов поисковых роботов;

выявление и описание обгцего, универсального ядра Веб-краулера (тип поискового робота, основанного на классическом обходе Веб-пространства);

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

исследование классического алгоритма ранжирования Клейнберга HITS и реализация его модификации для информационного поиска тематических сообществ;

исследование алгоритма взвешивания текста документов TF-IDF и реализация его модификации для информационного поиска тематических сообществ;

построение и тестирование программного комплекса на основе поискового робота с универсальным ядром и модифицированного апгоритма Клейнберга HITS;

построение и тестирование программного комплекса на основе поискового робота с универсальным ядром и модифицированного алгоритма взвешивания текста TF-IDF;

создание нового алгоритма информационного поиска тематических сообществ, учитывающего информацию о тексте и гиперссылочной структуре;

построение и тестирование программного комплекса на основе поискового робота с универсальным ядром и совместного использования модифицированных алгоритмов TF-IDF и HITS; создание тестовых коллекций документов для исследования качества поиска тематических сообществ;

получение экспериментального подтверждения практической применимости разработанного программного комплекса; оценка качества метода поиска тематических сообществ, основанного на совместном использовании модифицированных алгоритмов TF-IDF и HITS, в сравнении с методами, использующие те же самые методы по отдельности;

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

Методы исследования. Для решения задач, рассматриваемых в диссертационной работе, использовались математические методы теории вероятности и высшей алгебры. А для создания программного комплекса также методы технологии программирования. Для эксперимента использовались известные показатели по оценки качества в информационном поиске, а также создавались тестовые коллекции документов по запросам.

Научная новизна. Научная новизна работы заключается в следующем: 1. Создан метод поиска - направленный поиск тематических сообществ в Веб-пространстве, основанный на модификации классического алгоритма Клейнберга HITS, использующего информацию о гиперссылочной структуре найденных документов.

2. Создан метод поиска - направленный поиск тематических сообществ в Веб-пространстве, основанный на совместном использовании модификаций алгоритмов IIIТ S и TF-IDF, учитывающем как информацию о тексте, так и информацию о гиперссылочной структуре документов.

3. Выдвинута идея универсального ядра поискового робота, на базе которой строится любая модель тематического робота, и разработана его структура.

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

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

Реализация и внедрение результатов работы. Отдельные элементы созданного программного комплекса, предложенные алгоритмы, а также полученные результаты использованы компанией ООО "Клауд Инструменте" в коммерческих продуктах.

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались

на Всероссийской Научной Конференции по электронным библиотекам RCDL - г. Суздаль (Россия), 2006 г.; на семинаре в компании IPM (Informed Portfolio Management) - г. Стокгольм (Швеция), ноябрь, 2010 г.;

на семинарах в компании ООО «Клауд Инструменте» - г. Санкт-Петербург (Россия), 2010,2011 г.;

неоднократно на заседаниях и семинарах кафедры технологии программирования (ПМ-ПУ, СПбГУ 2009-2011); на научном семинаре по информационному поиску IR workshop на факультете ПМ-ПУ СПбГУ (2010 г.);

на семинаре в Карельском Научном Центре Российской Академии Наук - г. Петрозаводск (Россия), 2011 г.

Личный вклад автора. Все результаты диссертационного исследования получены автором лично.

Публикации. По материалам диссертации опубликованы 3 работы, 2 из которых в изданиях, входящих в перечень ВАК рецензируемых научных журналов. Список работ приведен в конце автореферата.

Структура и объем диссертации. Диссертационная работа изложена на 122 страницах машинописного текста и состоит из введения, шести глав и списка литературы, включающего 65 наименований. Работа содержит 23 рисунка и 11 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе формализуется постановка задачи, описывается структура представления Веб-пространства в виде ориентированного Веб-графа 0(У, Е), в котором вершины уеУ соответствуют Веб-страницам, а направленные ребра е(и,у) - соединяющим страницы гиперссылкам, где

ее£и и,уеУ.

Проведенное в 1999 г. Кумаром и Бродером исследование (на примере более 200 миллионов Веб-страниц) выявило широкомасштабную структуру Веб-графа, которую визуально можно представить в виде «бабочки» (Рис.1). На Рис.1 стрелочками показано направление ссылок для каждой Вебстраницы соответствующего множества страниц.

Рис. 1. Структура Веб-графа в виде ДЭВИСОН В СВОИХ исследованиях ЭКСПе-

«бабочки». риментально обосновал так назы-

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

Понятие тематического сообщества не имеет обобщенного формализованного математического определения. Например, Гибсон в своих работах определял тематическое сообщество, как множество документов, в котором каждый документ имеет больше ссылок на другие документы сообщества, чем на документы вне него.

Во второй главе рассматриваются Веб-краулеры2 в информационном поиске (роль, оценки эффективности, архитектурные особенности и др.), выделяется и описывается универсальное ядро, на базе которого строится любая модель Веб-краулера.

Ядро Веб-краулера (поискового робота) является программой, написанной на языке высокого уровня, взаимодействующей с окружающей средой посредством сетевых протоколов, например, интернет-протокола

HTTP. Задачей ядра поисковых роботов является обход Веб-графа определенным образом с целью сбора информации, выявление структуры и вычисление полезности информационных ресурсов в Веб-пространстве, а также передача собранной информации для анализа другим приложениям поисковых систем. Большинство существующих Веб-краулсров (например, Open Web Spider, Heritrix или Methanol Web Crawler) использует жесткие архитектурные подходы, при которых функции ядра смешиваются с дополнительными функциями, связанными со специализацией данных роботов. Архитектура Веб-краулера с универсальным ядром (см. Рис. 2) разработана таким образом, чтобы процесс добавления в нее новых модулей протекал с максимальной простотой и минимальными издержками по времени. Другими словами, она обладает большей гибкостью и масштабируемостью по сравнению с архитектурой существующих Веб-краулеров. Условиями остановки работы поискового робота являются,

2Веб-краулер - поисковый робот (webcrawler, ееб-краулер) - специальная программа, входящая в состав каждой поисковой машины (например, Google, Яндекс, Рамблер и др.). Основная задача робота: сканирование веб-страниц, известных поисковой системе, с целью обновления данных об их содержимом в индексе системы, а также поиск новых страниц, еще не включенных в этог индекс.

Рис. 2. Архитектура Веб-краулера с универсальным ядром

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

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

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

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

модель документа, использующая информацию о тексте информационного источника;

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

В главе подробно описаны исследования различных авторов по методам информационного поиска и приведены соответствующие ссылки (около 30 источников).

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

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

3 Российский семинар по Оценке Методов Информационного Поиска (РОМИП) - открытый семинар, проводимый ежегодно с 2003 года группой российских исследователей и разработчиков, занимающихся информационным поиском.

Text REtrieval Conference (TREC) - серия конференций, сконцентрированных на исследовании различных областей информационного поиска и их задач.

для неупорядоченного множества документов основаны на бинарной классификации документов «релевантен/не релевантен» по отношению к заданному запросу.

Для измерения эффективности созданных в диссертации методов информационного поиска тематических сообществ использовался тестовый набор данных, на котором оценивалось качество этих методов. Данный набор включал:

1. Тестовую коллекцию документов (построение выполнялось с использованием собственных методик).

2. Тестовое множество информационных потребностей пользователя, выражаемых в виде запросов (запросы и их описания брались из тестовых коллекций РОМИП и TREC).

3. Набор бинарных оценок для каждого найденного документа, характеризующих релевантность или нерелевантность данных документов запросам (бинарная классификация выполнялась независимыми оценщиками).

В пятой главе рассмотрены среда разработки программного комплекса с универсальным ядром и инструменты для его создания. Описаны

особенности архитектуры и реализации трех тематических Веб-кра-улеров: первый - использует модель документа на множестве слов и алгоритм взвешивания TF-IDF5 и создается как базовая модель для сравнения; второй - модель документа на анализе гиперссылок, в качестве инструмента для системного анализа используя алгоритм Клейнберга HITS6; третий построен на модели, учитывающей как текстовую характеристику документа, так и гиперссылочную. Перечисленные тематические Веб-краулеры используются в экспериментальной части диссертационной работы для выявления наиболее эффективной модель

5 TF-IDF (от англ. TF - term frequency, IDF - inverse document frequency) - статистическая мера, используемая для оценки важности слова в контексте документа.

6Hyperlink-Induced Topic Search (HITS) - созданный Д. Клейнбергом алгоритм, который вычисляет ранг Веб-страниц, исходя из анализа их гиперссылочной структуры.

(Модель \ /Модуль морфологического4, раюкирования/ ^анализа и взвешивания J

Страницы с весом TF-IDF > О

/Добавление ссылок

коллекцию документе!

/Добавление ссыло! \ в очередь

Рис. 3. Архитектура тематического краулера на основе TF-IDF взвешивания.

поиска.

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

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

Относительно архитектуры тематического Веб-краулера на основе алгоритма TF-IDF можно отметить, что итерационный Краулер-процесс программного комплекса с универсальным ядром расширяется модулем морфологического анализа и взвешивания (Рис. 3), который отвечает за процедуру выделения слов и устоявшихся словосочетаний в тексте информационных источников и их взвешивания.

Данный модуль получает из универсального ядра Веб-страницы и разбивает их текст и текст запроса пользователя на слова. Все слова информационных источников и запроса нормализуются по морфологии (выделяются основы всех слов): для английского языка использовался алгоритм Портера стемминг, для русского - словарь словообразований. Затем модуль выделяет устоявшиеся словосочетания (без учета шумовых слов), используя алгоритм, предложенный М. Губином7. Учитывая все используемые слова и устоявшиеся словосочетания, определяются веса всех информационных источников, полученых из универсального ядра. Формула, по которой осуществляется расчет веса для каждой Веб-страницы, имеет следующий вид:

TF - IDF = TFfactor *IDFfactor* NormaluationFactor (1),

- число вхождений термина / в документе с1, суг - множество документов, содержащих термин

' Губин, М. В. Исследование качества информационного поиска с использованием пар слов / М. В. Губин // 1п Труды КСП1Х2003. - 2003. - С. 186-191.

IDFfactor = log

N + \ df, ,

NormalnationFactor = ■

0.8 + 0.2 •

количество слов в документе

среднее количество слов в документе

На каждой итерации Краулер-процесса тематический поисковый робот на основе алгоритма 'ГР-ШБ выбирает источники информации с положительными весами (ТГ-Ю17 > 0) и добавляет их в очередь и коллекцию результатов. Результатом его поиска является тематически связанный набор информационных источников.

Второй, созданный на основе универсального ядра, тематический поисковый робот определяет значимость Веб-страниц исходя из системного анализа их гиперссылочной структуре. Особенность реализации данного метода информационного поиска тематических сообществ заключается в том, что для любого источника информации из универсального ядра Веб-краулера (Рис. 4) ставится в соответствие пара весов: авторитетность и индексность. Для нахождения значений этих весов применяются операции (2) и (3) в итерационном процессе (где формула (2) определяет значение авторитетного веса, а (3) - значение индексного веса для Веб-страницы р).

О5

f V

Инициализация очереди с Л

¡ачальными Веб-страницашу

-

Т

<Р>

<Р>

■

<q>

(2),

(3).

f Цобавление ссылок коллекцию документов,

С Авторитетные Веб-страницы

Рис. 4. Архитектура тематического краулера на основе алгоритма HITS.

2 х

Модуль взвешивания по ШТБ и модуль группировки гиперссылок тематического робота на основе алгоритма Клейнберга отвечают за вычисление наилучших авторитетных и индексных весов и расширяют архитектуру программного комплекса с универсальным ядром (Рис. 4). Из рис. 4 видно, что найденные хорошие авторитетные информационные источники сразу же включаются в индекс, а индексные используются для расширения поиска новых авторитетных источников информации.

Третий, созданный на основе универсального ядра, тематический поисковый робот определяет значимость информационных источников исходя из их морфологического и гиперссылочного анализа (Рис. 5).

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

старт

±

[ Инициализация очереди с j [начальными Ве&страницамиI

Рис. 5. Архитектура тематического краулера на основе алгоритма HITS и взвешивания TF-IDF.

Разработанный программный комплекс и тематические Веб-краулеры были созданы на объектно-ориентированном языке программирования Microsoft С# на базе платформы .NET в одной из лучших существующих интеграционных сред разработки программного обеспечения Microsoft Visual Studio 2008, сосредоточенной на производительности разработчика и обеспечивающей специалиста всем набором необходимых устройств.

Помимо указанных составляющих в основу разработки программного комплекса были положены следующие: .NETFramework 3.5\

Majestic! 2(биб;пютска для синтаксического анализа html-разметки); WPF (высокоуровневый объектно-ориентированный

функциональный слой, позволяющий создавать графические интерфейсы);

.NETReactive Framework (Rx) (библиотека для асинхронной работы с событиями).

В конце данной главы приводится сравнение созданного программного комплекса на базе универсального ядра с существующими Веб-краулерами, такими, как Heritrix, Open Web Spider и Methanol Web Crawler.

Табл. 1 показывает, что созданный Беб-краулер с универсальным ядром, кэшируя только информацию о ссылках, показал лучшую производительность среди существующих реализаций. И уступил немного в производительности Heritrix, который не обрабатывает текстовую информацию найденных Веб-страниц.

Таблица 1.

Средняя производительность обработки информации для различных Веб-краулеров.

Кол-во обработанных Всб-страпиц Время Heritrix (мин.) Время Open WebSpider (Mini.) Время Methanol (MIUÍ.) Веб-краулер с уиивесалышш ядром

анализ ссылок (мин.) анализ контента (мин.) анализ ссылок и контента (мин.)

2000 1.6 2.5 2.4 1.7 2.0 2.0

300000 7.1 9.2 8.5 6.3 7.7 8.3

500000 10.5 13.2 12.6 9.5 11.5 12.1

В шестой главе представлены результаты экспериментов, выполненных с целью проверки эффективности методов информационного поиска тематических сообществ, и обсуждены его результаты. В эксперименте оценивались результаты поиска информации тематического Веб-краулера на основе совместного использования алгоритмов ШТ 8 и 1Т-ГОР, полученные после обхода Веб-графа. Производилось также сравнение с результатами поиска, которые получились в результате обхода того же графа тематическими Веб-краулерами на основе тех же алгоритмов по отдельности.

Эффективность информационного поиска тематических сообществ для трех созданных поисковых роботов проверялась в русскоязычной и англоязычной частях Веб-пространства. Были выбраны запросы и составлены соответствующие тестовые коллекции (Табл. 2). Способы составления этих коллекций подробно описаны в диссертации.

Таблица 2 также показывает, что тематический Веб-краулер на основе алгоритмов TF-IDF и HITS находит больше релевантных документов в составленных коллекциях, чем другие реализации тематических краулеров.

Таблица 2. Составленные коллекции но запросам и их описаниям из РОМИП и TREC.

Запрос Общее кол-во док. коллекции Количество рел. док. коллекции Кол-во рел. док. Веб-к )аулеров

на основе TD-IDF на основе HITS на основе TD-IDF и HITS

Армия России 85 10 3 5 10

Гимн Франции 93 20 6 13 20

История рентгенологии 77 14 4 6 14

Кельтская музыка 86 17 2 11 17

Нейтронная бомба 102 20 и 15 20

Art museums 97 19 5 13 19

Solar flares 95 18 10 13 18

International trade 75 16 7 10 16

Planet Mars 109 25 14 23 25

Space exploration 98 18 6 12 18

Для оценки качества методов информационного поиска использовались собственные методики, а также методики РОМИП и ТКЕС. Все результаты по метрикам качества представлены в диссертации.

В работе доказано, что качество информационного поиска тематических сообществ в Веб-пространстве для Веб-краулера, основанного на совместном использовании алгоритмов HITS и TF-IDF, лучше для обоих видов коллекций, чем две другие модели. На рисунках 6 и 7 полученные результаты демонстрируются в виде 11-точечного графика полноты/точности, построенного по методике TREC для собственных тестовых коллекций документов.

Веб-краулер на основе TF-IDF

Веб-краулер на основе HITS

«•»«•Веб-краулер на

основе алгоритма HITS и TF-IDF Взвешивания

Рис. б. 11-точечный график полноты/точности по запросам из РОМИП.

к °.4 шщ

0,2

.....И1 "Веб-краулер на

основе TF-roF

Веб-краулер на основе HITS

О

Полнота

'Веб-краулер на основе алгоритма HITS и TF-IDF Взвешивания

Рис. 7. 11-точечный график полноты/точности по запросам из TREC.

По графикам (Рис. 6, 7) видно, что для коллекций, составленных по запросам из РОМИП и TREC, наблюдается некоторое уменьшение точности, вызванное, скорей всего, флуктуацией (частотой появления релевантных источников информации, найденных поисковым роботом). По всем Веб-краулерам наблюдается наибольший прирост качества поиска при малых значениях полноты. Другими словами, увеличение количества релевантных источников информации наблюдается в начале выдачи результатов системы, что является полезным качеством с точки зрения пользователя.

В ходе эксперимента было выявлено, что все документы, найденные по запросам тематическим Веб-краулером на основе совместного использования алгоритмов HITS и TF-IDF, релевантны теме соответствующих запросов в зависимости от личных потребностей пользователей, использующих данную систему поиска.

ОСНОВНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ

1. Метод поиска - направленный поиск тематических сообществ в Веб-пространстве, основанный на модификации классического алгоритма Клеинберга HITS.

2. Метод поиска - направленный поиск тематических сообществ в Веб-пространстве, основанный на совместном использовании модификаций алгоритмов HITS и TF-IDF.

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

4. Структура универсального ядра поискового робота, на базе которой строится любая модель тематического робота.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендуемых ВАК РФ

1. Блеканов И. С., Бовдаренко Д. С. Тематический краулинг на основе алгоритма HITS //Научно-технические ведомости СПбГПУ. - 2010. -№3(101).-С. 111-118.

2. Блеканов И. С., Бондаренко Д. С. Оценка эффективности методов поиска тематических сообществ в Веб-пространстве // Научно-технические ведомости СПбГПУ. -2010. -№ 5(108). - С. 18-24.

Публикации в других изданиях

3. Кураленок И., Блеканов И., Дюгуров Д., Еремин JL, Михайлюк И., Писарь В. Эффективность расширения запросов поисковых систем с помощью специальных операторов языка запросов // Труды VIII Всероссийской научной конференции / Электронные библиотеки: перспективные методы и технологии, электронные коллекции / -Суздаль. - 2006. - С. 90-91.

Отпечатано копировально-множительным участком отдела обслуживания учебного процесса физического факультета СПбГУ. Приказ № 571/1 от 14.05.03. Подписано в печать 20.04.11 с оригинал-макета заказчика. Ф-т 30x42/4, Усл. печ. л. 1. Тираж 100 экз., Заказ №1173/с. 198504, СПб, Ст. Петергоф, ул. Ульяновская, д. 3, тел. 929-43-00.

ВВЕДЕНИЕ.

1. Технические задачи информационного поиска.

2. Поиск в Веб-пространстве.

3. Постановка задачи данной работы.

4. Цель работы.

5. Основные задачи работы.

6. Положения научной новизны.

7. Результаты.

ГЛАВА

ПРЕДСТАВЛЕНИЕ ВЕБ-ПРОСТРАНСТВА.

1.1. Структура Веб-графа.

1.2. Степенной закон распределения гиперссылок в Веб-графе.

1.3. Обход Веб-Графа.

1.4. Выводы.

ГЛАВА

ВЕБ-КРАУЛЕРЫ В ИНФОРМАЦИОННОМ ПОИСКЕ.

2.1. Критерии эффективной работы Веб-краулера.

2.2. Архитектурные особенности Веб-краулеров.

2.3. Архитектура Веб-краулера с универсальным ядром и ее реализация.

2.4. Поиск и обновление значимых Веб-страниц.

2.4.1. Метрики значимости Веб-страниц.

2.4.2. Типы Веб-краулеров.

2.4.3. Обновление Веб-страниц.

ГЛАВА

МЕТОДЫ И МОДЕЛИ ИНФОРМАЦИОННОГО ПОИСКА.

3.1. Модель документа.

3.2. Модель на множестве слов.

3.2.1. Проблемы выделения слов в документе.

3.2.2. Модель на стемминге документа.

3.2.3. Модель на взвешивании слов документа.

3.3. Модель с использованием пар слов.

3.4. Семантическая модель документа.

3.5. Модель на анализе гиперссылок.

3.5.1. Модель на алгоритме Клейнберга HITS.

3.5.1.1. Построение фокусированного Веб-графа в HITS алгоритме.

3.5.1.2. Вычисление индексных и авторитетных источников информации.

3.5.2. Модель на PageRank алгоритме.

3.5.2.1. Стандартный PageRank.

3.5.2.2. Модифицированный PageRank.

3.5.2.3. Итеративное вычисление PageRank.

ГЛАВА

ОЦЕНКА КАЧЕСТВА ИНОРМАЦИОННОГО ПОИСКА.

4.1. Базовые метрики оценки качества.

4.2. Дополнительные метрики оценки качества.

4.3. 11-точечный график полноты и точности.

4.4. Стандартные тестовые коллекции.

4.5. Выводы.

ГЛАВА

РЕАЛИЗАЦИЯ.

5.1. Реализация тематического Веб-краулера.

5.1.1. Тематический Веб-краулер на основе TF-IDF взвешивания.

5.1.2. Тематический Веб-краулер на основе алгоритма HITS.

5.1.3. Тематический Веб-краулер на основе совместного использования алгоритма HITS и взвешивания TF-IDF.

5.2. Сравнение с аналогами.

5.3. Среда разработки.

5.4. Выводы.

ГЛАВА

ЭКСПЕРИМЕНТ.

6.1. Описание эксперимента.

6.2. Результаты эксперимента.

6.3. Выводы.

В течение последнего десятилетия наблюдается экспоненциальный рост числа Веб-документов в информационном Веб-пространстве. Только в открытой (индексированной) части Веб-пространства на сегодняшний день насчитывается более 20 миллиардов документов и более 200 миллионов Вебсайтов, не говоря уже о скрытой (неиндексированной) части, в которой эти показатели больше в несколько раз [60]. Для эффективной работы с таким объемом информации требуются современные инструменты и технологии, роль которых играют различные средства информационного поиска.

1. Технические задачи информационного поиска

Главной задачей информационного поиска является нахождение всей информации, соответствующей информационным потребностям пользователя, в некоторой коллекции документов [36]. Данную задачу можно условно разделить на несколько подзадач. Рассмотрим некоторые:

- сбор информации. Проблему обхода коллекции с целью нахождения документов, соответствующих заданной тематике, можно рассматривать как отдельную задачу. Для решения данной задачи применяются различные техники обхода, которые можно разбить на две группы. Первая — различные стратегии обхода, повышающие количество найденных тематически связанных документов среди общего объема найденных. Вторая - простая фильтрация, которая позволяет быстро отсеивать документы, не соответствующие тематике, уменьшая вычислительную стоимость нахождения очередного интересующего документа [20, 24, 33, 36]. Для решения задач сбора информации используются так называемые поисковые роботы (краулеры) [17, 18, 22, 45], которые получают из коллекции документы и извлекают из них гиперссылки, по которым осуществляется дальнейший сбор информации.

- построение индексной структуры. Необходимо найти оптимальную структуру хранения документов, позволяющую максимально эффективно хранить информацию, получать к ней доступ и выдавать результат поиска с минимальной задержкой по времени. В некоторых случаях, индексная структура должна обладать свойствами масштабируемости и надежности работы при отказе некоторых ее частей. При создании индексной структуры для размещения и работы с информацией большого объема используются распределенные параллельные архитектуры. Например, она разбивается на отдельные коллекции по некоторому принципу, причем внутри разных, коллекций могут использоваться разные методы выполнения поиска.

- ранжирование информации. Различные документы могут иметь различную ценность для конкретного пользователя, независимо от его конкретной информационной потребности [36]. Критериями такой ценности может быть размер и тематическая целостность документа, авторитетность его автора, время его создания. В процессе ранжирования должен оцениваться вес документа в коллекции. Оценка веса документа может зависеть от поискового запроса, либо от него не зависеть. В последнем случае она вычисляется на этапе индексации. При этом учитывается смысловое содержание текста или гиперссылочная структура документа.

- выбор модели документа. Для организации процедуры информационного поиска требуется формировать и сохранять упрощенные модели документов (модели с определенными наборами характеристик, по которым оцениваются документы) 5 коллекции. Моделью документа обычно называют набор характеристик документа, которые учитываются системой поиска при его обработке. Причем, для каждой из возможных задач подбирается индивидуальный набор характеристик, по которому оценивается документ или группы документов. - оценка качества поиска. На данный момент существует несколько моделей оценки качества информационного поиска. Используются как автоматические средства оценки качества, так и оценка путем опроса пользователей системы. Существуют общепринятые тестовые наборы, критерии и открытые результаты оценки качества различных информационных систем на этих наборах [36, 51, 56, 62, 64]. Проводятся различные конференции по проблемам оценки качества информационного поиска, как на международном (ТИЕС) [63], так и на российском (РОМИП) [57] уровне

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

6.3. Выводы

Целью данного эксперимента было оценить качество поиска тематического Веб-краулера на основе совместного использования алгоритмов ШТБ и ТР-ГОР, сравнив его с Веб-краулерами, построенных с использованием алгоритмов ШТБ и ТР-ГОР по отдельности.

Из поставленного эксперимента можно сделать следующие выводы:

- разработанный тематический поисковый робот с новым алгоритмом обхода Веб-пространства показал значительно лучшее качество поиска тематических сообществ, чем два других поисковых робота. А также для него наблюдается высокая стабильность полученных результатов, которая характеризуется высокими значениями различных оценок качества, так, например, значение оценки по всем запросам МАР(Р^ш+1р1С)1. =0.65, что, практически, в 2 раза больше значения МАР(0)Н1Т5 = 0.34.

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

- множество объединений релевантных документов, найденных тематическими Веб-краулерами на основе алгоритма HITS и на основе взвешивания TF-IDF, является подмножеством множества релевантных документов, найденных разработанным поисковым роботом с новым алгоритмом поиска. Данный факт говорит о хорошей полноте созданной системы поиска тематических сообществ в Веб-пространстве.

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

- как показал эксперимент, качество поиска тематических сообществ Веб-краулера на основе TF-IDF взвешивания самое худшее. Данный факт объясняется тем, что содержание большого количества слов запроса в документе не всегда влияет на его релевантность. К таким документам в тестовых коллекциях относились различные форумы, новостные порталы и рекламные Веб-страницы.

1. Берж, К. Теория графов и ее применения / К. Берж. М: Иностранная литература, 1962. —319 с.

2. Блеканов, И. С. Оценка эффективности методов поиска тематических сообществ в Веб-пространстве / И. С. Блеканов, Д. С. Бондаренко // Научно-технические ведомости СПбГПУ. 2010. -№5(102). -С. 109-119.

3. Блеканов, И. С. Тематический краулинг на основе алгоритма HITS / И. С. Блеканов, Д. С. Бондаренко // Научно-технические ведомости СПбГПУ.-2010.-№3(101).-С. 111-118.

4. Губин, М. В. Исследование качества информационного поиска с использованием пар слов / М. В. Губин // In Труды RCDL-2003. -2003.-С. 186-191.

5. Захарова, И. Математическая модель онтологии для задач анализа текстов / И.В.Захарова // Актуальные проблемы в науке и технике: тр. 4-й всероссийской школы сем. Уфа. - 2009. - Т. 1. - С. 210215.

6. Кобрицов, Б.П. Мофология и синтаксис в проекте «русский стандарт» (Создание корпуса грамматически размеченных русских текстов) / Б.П. Кобрицов // Статьи международной конференции Диалог.-2003.-6 с.

7. Некрестьянов, И.С. Тематико-ориентированные методы информационного поиска / Игорь Сергеевич Некрестьянов // канд. т. н.: 05.13.11 / Санкт-Петербургский государственный университет. СПб, 2000. - С. 88.

8. Рощин, И. Автоматическое определение кодировки текста / И. Рощин // Радиомир. Ваш компьютер. — 2002. — М. — С. 5-6.

9. Agrawal, R. Searching with numbers / R. Agrawal, R. Srikant // In Proceedings of the eleventh international conference on World Wide Web. ACM Press: NA, USA. - 2002. - P. 420-431.

10. Arampatzis, A. Linguistically motivated information retrieval. Marcel Dekker / A. Arampatzis, T. van der Weide, C. Koster, P. van Bommel. New York, USA: Encyclopedia of Library and Information Science, December 2000. - P. 69.

11. Arasu, A. Searching the web / A.Arasu, J. Cho, H. Garcia-Molina, A. Paepcke, S. Raghavan // ACM Transactions on Internet Technology. -Aug. 2001.- Volume 1, № 1. P. 2-43.

12. Bahle, D. Efficient phrase querying with an auxiliary index / D. Bahle, H. E. Williams, J. Zobel // Proceedings of the 25th annual international1.t

13. ACM SIGIR conference on Research and development in information retrieval. 2002. - ACM Press: NY, USA. - P. 215-221.

14. Barabasi, A. Emergence of scaling in random networks / A. Barabasi, R. Albert // Science, USA. 1999. - Volume 286, № 5439. - P. 509512.

15. Bharat, K. Mirror, mirror on the web: A study of host pairs with replicated content / K. Bharat, A. Broder // In Proceedings of the eighth international conference on World Wide Web. Elsevier North-Holland: NY, USA. - 1999. - P. 1579-1590.

16. Brewington, B. Keeping up with the changing Web / B. Brewington, G. Cybenko // IEEE Computer Society Press. Los Alamitos, CA, USA. -2000. - Volume 33, № 5. P. 52-58.

17. Brin, S. The anatomy of a large-scale hyper textual Web search engine / S. Brin, L. Page // Computer Networks and ISDN Systems. 1998. -Volume 30, № 1-7.-P. 107-117.

18. Broder, A. Graph structure in the Web: Experiments and models / A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener // In WWW9. May 2000. - Amsterdam. -Elsevier Science. - Volume 33, №1-6. - P. 309-320.

19. Cho, J. Estimating frequency of change / J. Cho, H. Garcia-Molina // ACM Transactions on Internet Technology. NY, USA. - 2003. -Volume 3, № 3. - P. 256-290.

20. Cho, J. The evolution of the web and implications for an incremental crawler / J. Cho, H. Garcia-Molina // In Proceedings of the 26th International Conference on Very Large Databases. CA, USA. -2000. - P. 200-209.

21. Coffman, E.G. Optimal robot scheduling for web search engines / E.G. Coffman, Z. Liu, R.R. Weber // INRIA: Technical report. № 3317. -1997.-P. 14-22.

22. Davison, B. Recognizing Nepotistic Links on the Web / B. Davison // AAAI Workshop on Artificial Intelligence for Web Search. Technical Report WS-00-01, AAAI Press. - 2000. - P. 23-28.

23. Flake, G. Self-Organization of the Web and Identification of Communities / G. Flake, S. Lawrence, C. Giles, F. Coetzee // IEEE Computer. 2002. - Volume 35, № 3. - P. 66-71.

24. Gibson, D. Inferring Web communities from link topology / D. Gibson, J. Kleinberg, P. Raghavan // Proc. 9th ACM Conference on Hypertext and Hypermedia. ACM Press. - New York. - 1998. - NY, USA. - P. 225-234.

25. Golub, G. Matrix Computations / G. Golub, C.F. Van Loan. Johns Hopkins University Press, 3rd edition. -1996. - P. 308.

26. Hull, D. A. Stemming algorithms: A case study for detailed evaluation / D. A. Hull // Journal of the American Society of Information Science. -1996. John Wiley & Sons, Inc. - Volume 47, № 1. - P. 70-84,

27. Kahle, B. Preserving the Internet / B. Kahle // Scientific American. -Mar. 1997.-P. 82-83.

28. Kleinberg, J. Authoritative sources in a hyperlinked environment / J. Kleinberg // Proc. 9th ACM-SIAM Symposium on Discrete Algorithms. 1998. - Extended version in Journal of the ACM 46(1999). - ACM Press. - New York. - Volume 46, № 5. - P. 604632.

29. Koster, M. Robots in the web: threat or treat? / Koster M. // Connexions. April 1995. - Volume 9, № 4. - P. 2-12.118

30. Lawrence, S. Accessibility of information on the web / S. Lawrence, C. Lee Giles // Intelligence. ACM: NY, USA. - 2000. - P. 32-39.

31. Lovins, J.B. Development of a stemming algorithm / J.B. Lovins // Mechanical Translation and Computation. 1968. - Massachusetts Institute of Technology. - Volume 11, № 1. - P. 22-31.

32. Manning, C. An Introduction to Information Retrieval / C. Manning, P. Raghavan, H. Schütze. Cambridge, England: Cambridge University Press. - April 2009. - P. 544 (84-133, 151-217, 443-481).

33. Mohr, G. Introduction to Heritrix: an open source archival quality web crawler / Mohr, G., Kimpton, M., Stack, M., Ranitovic, I. // Proceedings of the 4th International Web Archiving Workshop (IWAW'04). Bath, UK. - 2005. - P. 15.

34. Momoi, K. A composite approach to language/encoding detection / K. Momoi, S. Li // In 19th International Unicode Conference. 2002. - P. 12.

35. Najork, M. High-Performance Web Crawling / M. Najork, A. Heydon // Kluwer Academic Publishers. MA, USA. - 2002. pp. 25-45.

36. Page, L. The Pagerank Citation Ranking: Bringing Order to the Web / L. Page, S. Brin, R. Motwani, T. Winograd. Technical report. -Computer Science Department: Stanford University. - 1998. - P. 17.

37. Porter, M.F. An algorithm for suffix stripping / M.F. Porter // Program. 1980. - Volume 14, № 3. - P. 130-137.

38. Raghavan, S. Crawling the Hidden Web / S. Raghavan, H. GarciaMolina // Morgan Kaufmann Publishers Inc. San Francisco, CA, USA.-2001.-P. 129-138.

39. Rezgui, Y. Text-based domain ontology building using tf-idf and metric clusters techniques / Y. Rezgui // Cambridge University Press New York, NY, USA. Vol. 22 Issue 4. - 2007. - P. 379-403.

40. Salton, G. Automatic text processing: the transformation, analysis, and retrieval of information by computer / G. Salton. Boston, MA, USA: Addison-Wesley Longman Publishing Co. - 1989. - P. 530.

41. Sang Ho Lee. On URL normalization / Sang Ho Lee, Sung Jin Kim, Seok Hoo Hong // Proceedings of the International Conference on Computational Science and its Applications (ICCSA). 2005. -Volume 2.-P. 1076-1085.

42. Sidorov, G. Zipf and heaps laws' coefficients depend on language / G. Sidorov, A. Gelbukh. Mexico: In Proceeding of Conference on Intelligent Text Processing and Computational Linguistics, 2001. - P. 332-335.

43. Singhal, A. A case study in web search using tree algorithms / A. Singhal, M. Kaszkiel // Proceedings of the 10th international conference on World Wide Web. 2002. - ACM Press: Hong Kong. -P. 708-716.

44. Song, F. A general language model for information retrieval (poster abstract) / F. Song, W. B. Croft // In Research and Development in Information Retrieval. 1999. - ACM Press: USA. - P. 279-280.

45. Terveen L. Constructing, Organizing, and Visualizing Collections of Topically Related Web Resources / L. Terveen, W. Hill, B. Amento // ACM Transactions on Computer-Human Interaction. March 1999. -Volume 6, № 1. - P. 67-94.

46. Voorhes, E. The TREC-8 Question Answering Track Report / E. Voorhes // In Proc. of the TREC-8. 1999. - National Institute of Standards and Technology, Gaithersburg. - P. 77-82.

47. Williams, H. E. What's next? Index structures for efficient phrase querying / H. E. Williams, J. Zobel, P. Anderson // In M. Orlowska, editor, Proc. Australasian Database Conference. 1999. - Auckland, New Zealand. - P. 141-152.

48. Zakharova, I. An approach to automated ontology building in text analysis problems / I. V. Zakharova, A. V. Melnikov, J. A. Vokhmitsev // Workshop on Computer Science and Information Technologies. -2006.-P. 177-178.

49. Zobel, J. How reliable are the results of large-scale information retrieval experiments? / J. Zobel // Annual ACM Conference on

50. Research and Development in Information Retrieval. 1998. - NY, USA.-P. 307-314.

51. Российский семинар по Оценке Методов Информационного Поиска Электронный ресурс]. 2003. - Режим доступа: http://romip.ru/, свободный. - Загл. с экрана.

52. Heritrix Электронный ресурс]. 2004. - Режим доступа: http://crawler.archive.org/, свободный. - Загл. с экрана.

53. Methanol Web Crawling System Электронный ресурс]. Режим доступа: http://metha-sys.org/, свободный. — Загл. с экрана.

54. Most Reliable Hosting Company Sites Электронный ресурс]. -Режим доступа: http://news.netcraft.com/, свободный. Загл. с экрана.

55. OpenWebSpider Электронный ресурс]. Режим доступа: http://www.openwebspider.org, свободный. - Загл. с экрана.

56. Program to evaluate TREC results using SMART evaluation procedures Электронный ресурс]. Documentation. - Режим доступа: http://www-nlpir.nist.gov/projects/trecvid/trecvid.tools/treceval, свободный. -Загл. с экрана.

57. Text Retrieval Conference (TREC) Электронный ресурс]. 2000. -Режим доступа: http://trec.nist.gov/, свободный. - Загл. с экрана.