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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова Факультет Вычислительной Математики и Кибернетики

На правах рукописи

Козлов Дмитрий Дмитриевич

РЕШЕНИЕ ЗАДАЧИ ТЕМАТИЧЕСКОГО ИНФОРМАЦИОННОГО ПОИСКА В РУНЕТ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

МОСКВА 2004

Работа выполнена на кафедре Автоматизации систем вычислительных комплексов факультета Вычислительной Математики и Кибернетики Московского государственного университета им. М.В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор, академик РАЕН Смелянский Руслан Леонидович.

Официальные оппоненты:

доктор физико-математических наук, Васенин Валерий Александрович; кандидат технических наук, Когаловский Михаил Рувимович.

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

Институт системного программирования Российской академии наук

Защита диссертации состоится "_15_"_октября 2004 г. в и

часов

на заседании специализированного совета Д.501.001.44 при Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Воробьевы горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан "_

_2004г.

Ученый секретарь специализированного совета п р о ф е с с

Трифонов

Обшдя характеристика работы

Актуальность темы

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

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

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

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

• отсутствует централизованное хранилище метаинформации об

объектах поиска;

• невозможно построить единую базу данных объектов поиска;

• отсутствует регламент создания объектов поиска;

• объекты поиска не содержат описания ихсодержимОШ!_„

I РОС НАЦИОНАЛА 3 I ВИЯЛИОТС!:/,

| С.Пгк; (

{ оз гсач**

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

• в начале поиска пользователь не знает четко свою информационную потребность, а имеет о ней лишь общее представление - тему. Поэтому он не может сформулировать запрос к информационно-поисковой системе (ИПС), в ответ на который будут выданы интересующие его объекты;

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

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

Для информационного поиска в Интернет в настоящее время наиболее широко используются системы поиска по ключевым словам (СПКС). Однако, как показано в работах М. Bates, N. Belkin и др.1, применение СПКС для тематического ИП в Интернет неэффективно в силу

1 Bates M., The design of browsing and berrypicking techniques for the online search interface. Online Review 13,5,1989.

Belkin N., Cool C., Stein A., Thiel U. Cases, Scripts, and Information-Seeking Strategies: On the Desingn of Interactive Information Retrieval Systems, Expert Systems and Applications, 9(3): 379-395 1994

того, что они построены на основе традиционной модели ИП, не учитывающей особенностей тематического ИП.

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

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

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

2 Davison B. Topical locality in the Web. Proceedings of the ACM SIGIR'2000 Conference, 2000.

Chakrabarti S., Dom B., Kumar S., Raghavan P., Tomkins A., Gibson D., Kleinberg J. Mining the Web's link structure. IEEE Computer, 32(8) pp 60-67,1999.

Цель работы

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

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

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

2. Разработать алгоритм тематического ИП в Интернет, который реализует эту модель.

3. Провести экспериментальное исследование эффективности предложенного алгоритма по сравнению с существующими методами тематического ИП в Интернет.

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

Основные результаты работы

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

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

- направленной организации итерационного процесса поиска;

- новой интерпретации механизма обратной связи;

- расширения алгоритма анализа структуры гиперссылок (алгоритма SALSA) средствами анализа текстов страниц.

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

Научная новизна

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

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

Практическая ценность

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

Результаты данной работы могут быть применены в следующих областях:

1. Для расширения функциональности систем поиска по ключевым словам с целью предоставления пользователям средств тематического ИП в Интернет.

2. Для. автоматизации построения вторичных, тематических информационных ресурсов - тематических каталогов (portholes3).

Методы исследования

При. разработке метода тематического ИП в Интернет использовались методы анализа социальных сетей, методы линейной алгебры, методы статистического анализа текстов.

Апробация работы и публикации

По теме диссертации опубликовано 5 печатных работ. Результаты работы докладывались на объединенном научно-исследовательском семинаре кафедр Автоматизации систем вычислительных. комплексов, Алгоритмических языков и Системного программирования факультета ВМиК МГУ, на научных семинарах лаборатории Вычислительных комплексов кафедры Автоматизации систем вычислительных комплексов факультета ВМиК МГУ, а также на следующих конференциях:

• Международная научная конференция «Научный сервис в сети Интернет» (Новороссийск, 2000);

• Международная научная конференция «Интеллектуализация обработки информации» (Алушта, 2000);

3 Chakrabarti S., Van Den Berg M., Dom B. Focused crawling: A new approach to topic-specific Web resource discovery. Eights World Wide Web Conference, Toronto, May 1999.

• Международная научная конференция «Интеллектуализация обработки информации» (Алушта, 2002);

• Научная конференция «Ломоносовские чтения» (Москва, 2004).

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения и библиографии. Общий объем диссертации 76 страниц. Библиография включает 70 наименований.

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

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

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

• когда автор ставит на своей странице А гиперссылку на другую страницу В, он рекомендует читателю А прочитать еще и В;

• если две страницы соединены гиперссылкой, то вероятность того, что они относятся к одной теме выше, чем в случае отсутствия гиперссылки.

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

Во второй главе проводится анализ особенностей рассматриваемой задачи и предлагается формальная модель тематического ИП в Интернет.

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

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

Пространство поиска определяется как ориентированный граф объектов G = <0, L>, где О - множество объектов поиска, a L - множество ориентированных ссылок между объектами. Каждый объект о, 6 О обладает вектором атрибутов: О = {о, = <а,1(..., а^, k=k(j)}. Для разных объектов наборы атрибутов могут различаться.

Пространство поиска в каждый момент времени представляет собой лишь некоторое приближение всего графа Web. Это приближение может изменяться в процессе поиска: Gt= <0Ь Lj> = G(t), t=0,l,2,...

В начале поиска пользователь формулирует свою информационную потребность в виде начального запроса: который задает

множество требуемых атрибутов объектов поиска. Запрос пользователя изменяется в процессе поиска:

Функция поиска осуществляет информационный поиск в пространстве Gt по запросу bt: Afb^G,) = J с Ог Результатом поиска является множество 0 объектов поиска из пространства поиска Ot.

Пользователь оценивает результаты поиска на соответствие своей информационной потребности

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

Q(6',bt) = <bt+I,dt+1>,dt+1c01.

Новое направление поиска задается в виде множества страниц, ссылки на которые (и с которых) надо раскрыть при расширении пространства поиска. На основании выбранного направления поиска производится расширение пространства поиска:

G^W^cWbO-

Для решения задачи тематического ИП в Интернет необходимо построить:

• функцию поискаА(ЬьО,),

• функцию уточнения запроса(3(0', Ь,),

• функцию расширения пространства поискаW(GP d(+1, b,). Точность поиска определяется в соответствии с традиционным

определением точности:

На основе введенной модели формулируется постановка задачи тематического ИП в Интернет:

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

таким образом, чтобы максимизировать точность

поиска.

2. Необходимо исследовать вопрос о возможности автоматизации функции уточнения запроса

Третья глава посвящена разработке алгоритма тематического ИП в Интернет на основе предложенной в главе 2 модели. Предложенная модель конкретизируется в части объектов поиска, их атрибутов, средств расширения пространства поиска, способа накопления результатов поиска, способов взаимодействия с пользователем.

Объектами поиска являются web-страницы, атрибутами которых являются слова, встречающиеся в текстах страниц. Для расширения пространства поиска используются следующие операции:

• получение страницы, заданной URL;

• получение ссылок на страницу, заданную URL, путем обращения к СПКС;

• получение от СПКС списка страниц по запросу из набора ключевых

слов.

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

• граф страницСР= < Р = {р}, НР = { <рьр2> | Pi, рг еР } >;

• граф ресурсовСя= (R^Hr), R= { г | г С Р };

• оценки релевантности и значимости;

• TFIDF-модель темыТ С Р (обучающая выборка для алгоритма

TFIDF4 анализа текста).

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

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

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

4 Saltón G., Buckley С., Term Weighting Approaches in Automatic Text Retrieval, Cornell University Technical Report 87-881,1987

запроса и выбор направления поиска на следующую итерацию:

<bt+I,dl+1> = Q(0,,bt).

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

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

5 Davison В. Topical locality in the Web. Proceedings of the ACM SIGIR^OOO Conference, 2000.

6 Kleinberg J. Authoritative sources in a hyperlinked environment Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.

7 Гиперссылки делятся на внешние (на страницу другого сайта) и локальные (на страпицу того же сайта).

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

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

Релевантность текстов страниц оценивается относительно TFDDF-модели, заданной пользователем на предыдущей итерации. На первой итерации обучающая выборка строится на основе набора ключевых слов а. Для оценки релевантности используется широко распространенный алгоритм TTTDF8.

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

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

8 Salton G., Buckley C., Term Weighting Approaches in Automatic Text Retrieval, Cornell University Technical Report 87-881,1987.

9 Science Citation Index. Institute for Scientific Information http://www.isinet.com, 1987.

алгоритма SALSA10 и анализ текста. Ключевыми особенностями предлагаемого метода являются:

• использование ресурсов, а не страниц для вычисления оценок значимости, что позволяет избежать влияния гиперссылок, не удовлетворяющих предположениям о семантике11, без использования специальных эвристик, сократить размерность задачи, оценивать группы страниц как единые объекты;

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

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

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

10 Lempel R., Moran S. The Stochastic Approach for Link-Structure analysis (SALSA) and the TKS Effect Ninth World Wide Web Conference, 2000.

" Имеются в виду описанные выше предположения о семантике гиперссылок, на которых основываются методы поиска тематических сообществ.

ресурсов путем выбора ресурсов с максимальной комбинированной (релевантность + значимость) оценкой, еще не включенных в модель темы.

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

Выбор направления поиска разбит на два независимых этапа:

• выбор направления поиска в терминах ресурсов,

• построение двух очередей: очереди страниц, ссылки на которые надо

скачать, и очереди страниц, которые надо скачать.

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

12 Сэлтон. Г., Автоматическая обработка, хранение и поиск информации, М., «Советское радио», 1973.

тематическому сообществу и, таким образом, с высокой вероятностью относящиеся к теме.

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

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

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

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

Для проведения исследования использовался метод экспертной оценки. Оценка производилась на реальных данных Рунет. Проводилось две группы экспериментов: в первом случае темы были взяты из классификатора yaca.yandex.ru, а эталонные результаты построены путем объединения информации из каталогов list.ru, yaca.yandex.ru, aport.ru; во втором случае, темы и эталонные результаты были предоставлены экспертами.

13 TREC-2002 Web Track Guidelines, Text Retrieval Conference, 2002.

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

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

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

1. Смелянский Р.Л., Козлов Д.Д. Использование интеллектуальных агентов для поиска информации в Интернет. // Искусственный интеллект - Донецк: 2000, № 2, с.378-382

2. Козлов Д.Д. Агент для поиска информации в Интернет. Архитектура и планирование работы // Тезисы конференции Научный сервис в сети Интернет. 2000, с.92-93

3. Козлов Д.Д. Информационный поиск в Рунет // Тезисы конференции Научный сервис в сети Интернет, 2001.

4. Козлов Д.Д. Реализация свойства проактивности агента для тематического информационного поиска в Интернет // Искусственный интеллект - Донецк: 2002.

5. Козлов Д.Д. Проблемы применения методов поиска тематических сообществ к задаче тематического информационного поиска в Интернет // Труды Всероссийской научной конференции Методы и средства обработки информации. - Москва: 2003, с. 211-215.

;И68

Издательство ООО "МАКС Пресс". Лицензия ИД №00510 от 01.12.99 г. Подписано к печати 03.09.2004 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 926. Тел. 939-3890,939-3891,928-1042. Тел ./Факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В Ломоносова.

i* Введение.

Задача тематического информационного поиска в Интернет.

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

Метод решения.7

Структура работы.7

1. Существующие средства и методы ИП в Интернет.9

1.1 Промышленные ИПС в Интернет.9

1.1.1 Системы поиска по ключевым словам.9

1.1.2 Алгоритм PageRank.13

1.1.3 Классификаторы.14

1.1.4 Метапоисковые системы.14

1.2 Методы тематического ИП в Интернет.17

Ъ 1.2.1 Тематические роботы.18

1.2.2 Поиск тематических сообществ в Web.21

1.2.2.1 Поиск тематических сообществ на основе двудольных графов.22

1.2.2.2 Поиск тематических сообществ на основе построения NK-клан графа.24

1.2.2.3 Поиск тематических сообществ на основе максимального потока.25

1.2.2.4 Алгоритмы семейства HITS.27

1.2.2.5 Алгоритм SALSA.32

1.3 Выводы.34

2. Модель тематического информационного поиска в Интернет.36

2.1 Традиционная модель информационного поиска.36

2.2 Анализ задачи тематического ИП в Интернет.37

2.2.1 Особенности задачи тематического ИП.37

2.2.2 Особенности Интернет как хранилища информации.38 л 2.2.3 Выводы.41

2.3 Модель тематического ИП в Интернет.42

14 2.4 Формальная постановка задачи тематического ИП в Интернет.43

3. Решение задачи тематического информационного поиска в Интернет.44

3.1 Общая схема работы системы для тематического ИП в Интернет.44

3.2 Общий подход к построению пространства поиска.47

3.3 Фаза построения пространства поиска.48

3.3.1 Типы гиперссылок.48

3.3.2 Типы страниц.48

3.3.3 Эвристики отбора ссылок.49

3.3.4 Построение пространства поиска.50

3.3.5 Построение графа ресурсов.52

3.4 Фаза анализа.53

3.4.1 Оценка релевантности страниц.54

3.4.2 Оценка значимости ресурсов.55

3.4.3 Выбор направления поиска.56

3.4.4 Предварительный отбор ресурсов для включения в модель темы.57

3.4.5 Фильтрация ресурсов по языку и по оценке релевантности.57

3.5 Обратная связь.58

3.6 Выводы.59

4 Экспериментальное исследование подхода.60

Л 4.1 Цели и методы экспериментального исследования.60

4.2 Экспериментальная реализация предложенного алгоритма.62

4.3 Результаты экспериментального исследования.64

4.3.1 Общие результаты экспериментов.64

4.4 Оценка вычислительной сложности.67

4.5 Выводы.69

Заключение.71

Литература.72 Л Л

Введение

Задача тематического информационного поиска в Интернет

С конца 50-х годов [36] применительно к библиотечным системам активно разрабатывались методы решения так называемой традиционной задачи информационного поиска (ИП) [8].

Задача ИП в общем виде1 состоит в том, чтобы в заданном пространстве поиска найти документы, релевантные информационной потребности пользователя, заданной в виде запроса. Частные варианты задачи информационного поиска определяются свойствами пространства поиска и свойствами информационной потребности пользователя.

Традиционная задача ИП основывалась на следующих предположениях об информационной потребности пользователя:

• пользователь четко знает, что он ищет, и может сформулировать это в виде запроса к информационно-поисковой системе;

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

• в процессе поиска информационная потребность пользователя не изменяется. Результат поиска определяется одним запросом.

В случае, когда эти предположения не выполнялись и пользователь не мог найти нужную информацию с помощью информационно-поисковой системы2 (ИПС), ему на

1 В литературе понятие информационного поиска трактуется широко, однако наиболее распространено определение информационного поиска как "родового понятия для поиска данных, поиска фактов и поиска документов" [4]. По виду объектов поиска задачу ИП делят на фактографический и документальный ИП. В рамках данной работы под информационным поиском подразумевается документальный информационный поиск, то есть поиск документов в заданном массиве в соответствии с критериями, предложенными пользователем.

Информационно-поисковой системой, согласно [3], называется программная система для хранения, поиска и выдачи интересующей пользователя информации (в рассматриваемом случае - документов). помощь всегда был готов прийти библиограф, который занимался созданием подборок документов по интересующей пользователя теме. Такой вариант задачи информационного поиска получил специальное название - тематический ИП.

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

• статичность (новые документы появляются относительно редко);

• локальность (документы собраны в базу данных);

• существует определенный регламент появления документов.

Интернет как пространство поиска не обладает этими свойствами, что существенно меняет задачу ИП в Интернет по сравнению с традиционной задачей ИП.

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

Свойства пространства поиска:

• отсутствует централизованное хранилище метаинформации об объектах поиска;

• невозможно построить единую базу данных объектов поиска;

• объекты поиска не содержат описания их содержимого;

• отсутствует регламент создания объектов поиска;

• большинство объектов поиска представляют собой гипертекстовые страницы, которые могут содержать гиперссылки на другие страницы. Страницы, связанные гиперссылками, образуют граф Web.

Свойства информационной потребности пользователя:

• в начале поиска пользователь не знает четко свою информационную потребность, а имеет о ней лишь общее представление — тему. Поэтому он не может сформулировать запрос к ИПС, в ответ на который будут выданы интересующие его объекты;

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

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

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

Актуальность темы

Широкое распространение Интернет привело к тому, что с задачей тематического ИП приходится сталкиваться не только профессионалам-библиографам, но и рядовым пользователям. Так, согласно [13], около половины запросов пользователей к информационно-поисковым системам в Интернет относятся к тематическому ИП.

Для информационного поиска в Интернет в настоящее время наиболее широко используются системы поиска по ключевым словам (СПКС), например, Google [64] или Yandex [65]. В работах [15],[18] была обоснована неэффективность применения таких систем для тематического ИП в силу того, что они построены на основе традиционной модели ИП (см. раздел 2.1), не учитывающей особенностей тематического ИП.

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

В последние годы исследования тематической структуры Интернет [16], [45], [46] продемонстрировали принципиальную возможность решать некоторые частные случаи задачи тематического ИП в Интернет без предварительной обработки данных (построения базы данных объектов поиска) и без наличия информации об организации предметной области (например, онтологии). Однако методы, предложенные в [45],[55], не учитывают важных особенностей задачи тематического ИП: они не позволяют пользователю осуществлять поиск итерационно, уточняя информационную потребность в процессе поиска.

Цель работы

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

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

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

2. Разработать алгоритм тематического ИП в Интернет, который реализует эту модель.

3. Провести экспериментальное исследование эффективности предложенного алгоритма по сравнению с существующими методами тематического ИП в Интернет.

Метод решения

В данной работе предлагается метод решения задачи тематического ИП в Интернет, который обобщает широко применяемые в этой области методы поиска тематических сообществ в части направленной организации итерационного процесса поиска, новой интерпретации механизма обратной связи, расширения алгоритма анализа структуры гиперссылок (алгоритма SALSA [55]) средствами анализа текста.

При разработке метода тематического ИП в Интернет использовались методы анализа социальных сетей, методы линейной алгебры, методы статистического анализа текстов.

Структура работы

Основные результаты работы заключаются в следующем:

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

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

- направленной организации итерационного процесса поиска;

- новой интерпретации механизма обратной связи;

- расширения алгоритма анализа структуры гиперссылок (алгоритма SALSA) средствами анализа текстов страниц.

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

Результаты данной работы могут быть применены в следующих областях:

1. Для расширения функциональности систем поиска по ключевым словам с целью предоставления пользователям средств тематического ИП в Интернет.

2. Для автоматизации построения вторичных тематических информационных ресурсов — тематических каталогов (portholes [48]).

Наиболее перспективным представляется развитие предложенных в работе методов по следующим направлениям:

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

2. Внедрение в алгоритм более развитых средств анализа текста, в частности, средств автоматической классификации.

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

Заключение

1. Ахо А., Ульман Д., Теория синтаксического анализа, перевода и компиляции, М., Мир, 1978.

2. Крюков Д.В. Поисковая система "Turtle". Физиология и анатомия. http://www.turtle.ru/db/architecture/

3. Мальковский М. Г., Грацианова Т. Ю., Полякова И. Н., Прикладное программное обеспечение: системы автоматической обработки текстов, Учебное пособие для студентов факультета ВМиК МГУ, Москва, МГУ, 2000

4. Мидоу Ч., Анализ информационно-поисковых систем, М., Мир, 1970

5. Некрестьянов И. Тематико-ориентированные методы информационного поиска. Диссертация. Санкт-Петербург, 2000

6. Райдингс К. Растолкованный PageRank. http://digits.ru/articles/promotion/pagerank.html. (пер. Садовский А.)

7. Россеева О., Загорулько Ю. Организация эффективного поиска на основе онтологий. Труды Международного семинара Диалог'2001.

8. Солтон Дж., Динамические библиотечно-информационные системы, М., Мир, 1979.

9. Сэлтон Г., Автоматическая обработка, хранение и поиск информации, М., «Советское радио», 1973

10. Черный А. И., Введение в теорию информационного поиска, М., Наука, 1975

11. Хензингер М. Анализ гиперссылок в Web. Открытые системы, 2001, N10, http://www.osp.ru/2001/10/050.htm.

12. Bates М., The design of browsing and berrypicking techniques for the online search interface. Online Review 13,5,1989

13. Belkin N., Cool C., Stein A., Thiel U. Cases, Scripts, and Information-Seeking Strategies: On the Desingn of Interactive Information Retrieval Systems, Expert Systems and Applications, 9(3): 379-395 1994

14. Bergman K., The Deep Web: Surfacing Hidden Value, BrightPlanet.com LLC, http://www.completeplanet.com/Tutorials/DeepWeb/index.asp

15. Brahat K. SearchPad: explicit Capture of Search Context to Support Web Search, Proceedings of the WWW9 Conference.

16. Davison В. Topical locality in the Web. Proceedings of the ACM SIGIR'2000 Conference, 2000.

17. Etzioni 0., The World Wide Web: quagmire or gold mine?, Communications of the ACM, November 1996.

18. O'Day V., Jeffries R. Orienteering in an Information Landscape: How Information Seekers Get From here to There. Proceedings of INTERCHI '93, 1993.

19. Seberg E., Etzioni O., The MetaCrawler Architecture for Resource Aggregation on the Web, http://www.cs.washington.edu/research/metacrawler. 1998

20. Inktomi Corp., Web Surpasses One Billion Documents, press release issued January 18, 2000, http://www.inktomi.com/new/press/billion.html

21. Mladenic D. Turning Yahoo Into an Automatic Web-Page Classifier. European Conference on Artificial Intelligence, 1998

22. Gruber T. Towards Principles for the Design of Ontologies Used for Knowledge Sharing. International Workshop on Formal Ontology, 1993.

23. Koenemann J. Supporting Interactive Information Retrieval Through Relevance Feedback, Proceedings of ACM CHI'96 Conference.

24. Pirolli P., Pitkow J., Rao R., Silk from a Sow's Ear: extracting Usable Structures from the Web, Proc. ACM Conf. Human Factors in Computing Systems, CHI'96, 1996

25. Flake G., Lawrence S., Giles C., Coetzee F. Self-Organization of the Web and Identification of Communities. IEEE Computer, 35(3), pp 66-71,2002.

26. Lawrence S., Bollacker K., Giles C., Digital Libraries and Autonomous Citation Indexing, IEEE Computer, pp. 67-71, June 1999

27. Lawrence S., Bollacker K., Giles C., Indexing and Retrieval of Scientific Literature, Proceedings of CIKM 1999 Conference, pp. 139-146

28. Lawrence S., Giles C., Accessibility of Information on the Web, Nature, vol.400, pp. 107-109,1999

29. Lawrence S., Giles C., Context and page analysis for improved web search, IEEE Internet Computing, July 1998, pp.3 8-46

30. Lawrence S., Giles C., Inquirus: The NECI Search Software, http://www.neci .nj .nec.com/homepages/lawrence/inquirus.html

31. Lawrence S., Giles C., Searching the Web: General and Scientific Information Access, IEEE Communications Magazine, January 1999, pp 116-122

32. Bollacker К., Lawrence S., Giles C., CiteSeer: An Autonomous {Web} Agent for Automatic Retrieval and Identification of Interesting Publications, Proceedings of the Second International Conference on Autonomous Agents, ACM Press, 1998, pp. 116— 123

33. Glover E., Lawrence S., Birmingham W., Giles C., Architecture of a Metasearch Engine that Supports User Information needs, Proceedings of CIKM-99 Conference, pp. 210216, ACM, 1999

34. Research Index Computer Science Directory http://citeseer.ni.nec.com/directory.html

35. Rijsbergen C., Information Retrieval, London, Butterworths, 1979

36. Salton G., Historical Note: The Past Thirty Years in Information Retrieval, Cornell University Technical Report 87-827

37. Salton G., Mathematics and information retrieval Cornell University Technical Report 78-332

38. Salton G., Buckley C., Term Weighting Approaches in Automatic Text Retrieval, Cornell University Technical Report 87-881

39. Salton G., Fox E., Wu H., Extended Boolean Information Retrieval, Cornell University Technical Report 82-511

40. Salton G., Buckley C. Improving retrieval performance by relevance feedback. Journal of the American Society for Information Science 41:288—297, 1990

41. Brin S., Page L. The anatomy of a large-scale hypertextual Web search engine. Proceedings of the WWW7 Conference, 1998.

42. Brin S., Page L., Motwani R., Winograd T. The PageRank citation ranking: Bringing order to the Web. Stanford Digital Library Technologies, Working Paper 1999-0120, 1998.

43. Bharat K., Henzinger M. Improved Algorithms for Topic Distillation in a Hyperlinked Environment. ACM SIGIR conference on Research and Development in IR, 1998.

44. Henzinger M. Link Analysis in Web Information Retrieval. IEEE Bulletin on Data Engineering, Vol. 23, N3,2000.

45. Chakrabarti S., Dom В., Kumar S., Raghavan P., Tomkins A., Gibson D., Kleinberg J. Mining the Web's link structure. IEEE Computer, 32(8) pp 60-67,1999

46. Chakrabarti S., В. Dom, D. Gibson, J. Kleinberg, P. Raghavan, S. Rajagopalan, Automatic resource list compilation by analyzing hyperlink structure and associated text. Proc. 7th International World Wide Web Conference, 1998.

47. Chakrabarti S. Integrating the Document Object Model with Hyperlinks for Enhanced Topic Distillation and Information Extraction. Proceedings of WWW 10 Conference, 2001

48. Chakrabarti S., Van Den Berg M., Dom B. Focused crawling: A new approach to topic-specific Web resource discovery. Eights World Wide Web Conference, Toronto, May 1999.

49. Kleinberg J. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.

50. Gibson D., Kleinberg J., Raghavan P. Inferring Web communities from link topology. Proc. 9th ACM Conference on Hypertext and Hypermedia, 1998.

51. Kleinberg J., Kumar S., Raghavan P., Rajagopalan S., Tomkins A. The Web as a graph: Measurements, models and methods. Invited survey at the International Conference on Combinatorics and Computing, 1999.

52. Kumar S., Raghavan P., Rajagopalan S., Tomkins A. Trawling the Web for emerging cyber-communities. Eighth World Wide Web Conference, Toronto, Canada, May 1999.

53. Terveen L., Hill W., Amento B. Constructing, Organizing, and Visualizing Collections of Topically Related Web Resourses. ACM Transactions on Computer-Human Interaction, Vol 6, No 1, March 1999, Pages 67-94

54. Amento В., Terveen L., Hill W. Does "Authority" Mean Quality? Predicting Expert Quality Ratings of Web Documents. ACM SIGIR conference on Research and Development in IR, 2000.

55. Lempel R., Moran S. The Stochastic Approach for Link-Structure analysis (SALSA) and the TKS Effect. Ninth World Wide Web Conference, 2000

56. Borodin A., Roberts G., Rosenthal J., Tsaparas P. Finding Authorities and Hubs From Link Structures on the World Wide Web. Tenth World Wide Web Conference, Hong Kong, 2001

57. Shivakumar N., Garcia-Molina H. Finding Near-Replies of documents on the Web. Porceedings inWebDB'99,1999.

58. Broder A. Z., Kumar S. R., Maghoul F., Raghavan P., Rajagopalan S., Stata R., Tomkins A., Wiener J. L. Graph structure in the web. In Proc. of the WWW9, pp. 309-320,2000.

59. Hermans В., Intelligent Software Agents on the Internet: an inventory of currently offered functionality in the information society and a prediction of future developments, http://www.hermans.org/agents, 1996

60. Cavnar W., Trenkle J., N-gram-based text categorization, in Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval, pp.161-175, 1994.

61. TREC-2002 Web Track Guidelines, TREC, 2002.

62. Сегалович И.В. Как работают поисковые системы, www.yandex.ru/papers/

63. Open Directory Project http://www.dmoz.org проект по созданию некоммерческого каталога.64. Google www.googIe.com65. Yandex www.vandex.ru

64. Стеммер Snowball http://snowball.tartarus.org

65. Davison В., Recognizing nepotistic links on the Web. AAAI-2000 Workshop on Artificial Intelligence for Web Seasrch, 2000.

66. Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962

67. СУБД Informix http://www.informix.com

68. Проект Jakarta, http://iakarta.apache.org