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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

ррб ст

Некрестьянов Игорь Сергеевич

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

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

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

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

профессор Б. А. Новиков

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

доктор технических наук, профессор С. Д. Кузнецов кандидат физико-математических наук, доцент В. А. Капустин

Ведущая организация: Институт проблем информатики

Российской Академии Наук

Защита диссертации состоится "2\ " 2000 года

в часов на заседании диссертационного совета К 063.57.54

по защите диссертаций на соискание ученой степени кандидата наук в Санкт-Петербургском государственном университете но адресу 198904, Санкт-Петербург, Старый Петергоф, Библиотечная пл., 2.

С диссертацией можно ознакомится в Научной библиотеке Санкт-Петербургского государственного университета но адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан " "__ 2000 года.

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

доктор физико-математических наук Б. К. Мартыпснко

ГУ

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

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

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

Центральная проблема информационного поиска формулируется просто — помочь пользователю найти ту информации, и которой он заинтересован [18]. Однако, описать информационные потребностей пользователя, а также определить меру релевантности (соответствия) информации этим потребностям, совсем не так просто [1].

Классическая задача информационного поиска — это поиск документов, удовлетворяющих запрос}' пользователя, в рамка.х некоторой статической (на момент выполнения поиска) коллекции документов. ■Запросом может быть задан как набор ключевых слов и словосочетаний, фрагмент текста на естественном языке или даже документ-образец. К области информационного поиска относится также и ряд других задач, например, задачи кластеризации [9, 16], классификации [23, 17], фильтрации [3, 15] и т.п.

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

Бурное развитие Интернет сделало наиболее популярной областью применения методов информационного поиска. Природа Интернет обуславливает ряд важных факторов, которые необходимо учитывать при рассмотрении задач поиска: огромный объем информации (по состоянию на июнь 2000 года в Интернет было опубликовано более миллиарда страниц), до 40% которой ежемесячно изменяется [10]; неконтролируемое качество информации; разнородность представлений информации (не только форматов, но языков и даже алфавитов). Важным отличием поисковых систем Интернет от классических систем информационного поиска является необходимость обслуживания всех запросов без реального доступа к ресурсам

на момент выполнения запроса, т. с. только на основе построенных индексов.

В целях повышения производительности и надежности, большинство современных многоцелевых систем имеют уже не централизованную, а параллельную архитектуру [1]. Активно исследуется возможность применения распределенных архитектур к поисковым системам [20, 4, 6].

В распределенных поисковых системах единый индекс разбивается но некоторому принципу на несколько отдельных частей (коллекций). Для повышения эффективности и надежности системы поиск производится не во всех коллекциях, а только в некотором их подмножестве. Этот процесс называется маршрутизацией запросов. Поскольку качество маршрутизации напрямую влияет на общее качество поиска, то методы маршрутизации запросов привлекают много внимания [33, 8, 21].

Одной из новых задач информационного поиска является задача сбора информации о доступных в Интернет информационных ресурсах [13, 5]. Собранная информация может быть использована, например, для создания индексов поисковых систем [12]. Огромный объем информации и высокая динамика Интернет делает невозможным посещение всех доступных ресурсов, что делает актуальным исследование стратегий обхода ресурсов Интернет.

Актуальной темой является также сравнительный анализ эффективности различных подходов к решению одной и той же задачи информационного поиска. При этом важно использовать стандартные наборы данных, такие, например, как созданные в рамках серии конференций TR.EC [25].

Понятие "тематика" давно используется в области информационного поиска, хотя оно и плохо формализуемо. В качестве примера можно привести задачи тематической классификации [23, 17, 2, 22] и фильтрации [7, 3, 11]. Перспективным направлением исследований является использование неявной информации о тематике в специализированных методах информационного поиска для повышения качества поиска [9, 19, 20, 24].

Цели работы

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

Общая методика

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

• "тематика" — понятие относительное, т.е. о "тематике" можно рассуждать только в рамках некоторого контекста,

• словарный запас и частоты использования слов зависят от тематики [22],

• типичный документ среднего размера затрагивает не единственную тематику [20. 19].

Эффективность предлагаемых подходов проверялась экспериментально по сравнению со стандартными методами. Для проверки использовались стандартные наборы тестовых данных — TREC-5 [25] и R.euters-21578.

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

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

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

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

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

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

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

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

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

8. Проведена обширная экспериментальная проверка предложенных методов на основе стандартных наборов тестовых данных.

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

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

Все основные научные результаты диссертации являются новыми.

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

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

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

Аппробация работы

Результаты диссертации докладывались на семинаре московской секции ACM SIGMOD, а также на конференциях по электронным библиотекам (DL'1999, Санкт-Петербург, Россия и DL'2000, Протвино, Россия), интеллектуальным сервисам (1S&N'99, Барселона, Испания) и распределенным информационным системам (SCI'99, Орландо, США).

Предложенные методы и полученные результаты были использованы при разработке распределенной поисковой системы OASIS, прототип которой доступен по адресу www.oasis-europe.org.

Публикации

Основные результаты диссертации изложены в восьми работах [27, 28, 29, 30, 31, 32, 33, 34] , перечисленных в конце автореферата.

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

Диссертация состоит из 5 глав со сквозной нумерацией разделов, рисунков и таблиц. Текст диссертации изложен на 88 страницах. Список литературы содержит 83 наименований.

Содержание работы

В первой главе кратко охарактеризован общин контекст исследований. В частности, основные задачи информационного поиска, а также особенности задач поиска в Интернет. Кратко описываются основные модели информационного поиска, включая латентно-семантический анализ, и определяются базовые критерии оценки эффективности поиска. Также описываются используемые для проведения экспериментов стандартные наборы тестовых данных — Т11ЕС-5 и Пс:и1хгй-21578.

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

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

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

• организации вычислительно-эффективного отсева посещенных документов, которые; не относятся к искомой тематике. Показано, что относительно простые методы фильтрации способны отсеивать более 80% мусора, сохраняя при этом более 90% ис-

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

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

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

• Предложен тематико-ориентированный метод сокращения описаний коллекций, что позволяет значительно сократить объем централизованной информации, необходимой для маршрутизации запросов. Прямолинейные подходы к сокращению описаний, к сожалению, вызывают резкое падение качества маршрутизации. Результаты экспериментов на основе набора данных ТПЕС-5 показали, что предлагаемый подход делает возможным 40%-е сокращение описаний практически без потерь в качестве маршрутизации.

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

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

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

Формальная экспериментальные проверка, проведенная на основе стандартного тестового набора данных Яет^еть-21о78, продемонстрировала перспективность описываемого подхода. Отметим, что в неформальных экспериментах с коллекцией статей но комбинаторике, предлагаемый метод находил не только документы, посвященные решению той же самой комбинаторной задачи, но также и работы, посвященные другим задачам, но использующие похожие методы.

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

Для экспериментальной проверки использовался сложный набор тестовых данных (на основе Т11ЕС-5), в котором тематики, зачастую, были очень близки друг к другу и многие документы относились одновремено к нескольким тематикам. Несмотря на сложность тестовой базы, проведенные эксперименты показали хорошее качество классификации, что подтверждает перспективность предлагаемого подхода.

Список литературы

[1] Ricardo Baeza-Yates and Berthier Ribeiro-Neto. Modern Information Retrieval. ACM Press, 1999.

[2] Douglas L. Baker and Andrew Kaehites McCallum. Distributional clustering of words for text classification. Tn Proceedings of the SIGIR'98, pages 96-103, 1998.

[3] J. Callan. Learning while filtering documents. In Proc. of SIGIR '98, pages 224-231, Melbourne. Australia, 1998.

[4] James P. Callan, Zhihong Lu, and W. Bruce Croft. Searching distributed collections with inference networks. In Proceedings of the SIGIR '95, 1993.

[5] Sournen Chakrabarti, Martin van den Berg, and Byron Dom. Focused crawling: A new approach to topic-specific web resource discovery. In Proc. of the WWW-8, May 1999.

[6] Peter B. Danzig, Jongsuk Aim, John Noll, and Katia Obraozka. Distributed indexing: A scalable mechanism for distributed information retrieval. Tn Proc. of the SIGIR'91, 1991.

[7] P.W. Foltz. Using latent semantic indexing for information filtering. In ACM Conference on Office Information Systems (COIS), pages 40-47, 1990.

[8] Luis Gravano. Querying Multiple Document Collections Accross the Internet PhD thesis, Stanford University, August 1997.

[9] Vasileios Hatzivassiloglou, Luis Gravano, and Ankineedu Maganti. An investigation of linguistic features and clustering algorithms for topical document clustering. In Proc. of the SIGIR'2000, 2000.

[10] B. Kahle. Preserving the Internet. Scientific American, pages 8283, March 1997.

[11] Fredrik Kilander, Eva Fehraeus, and Jacob Palme. PEFNA: The private filtering news agent. Technical report, Department of

Computer and Systems Sciences, Stockholm University, February 1997.

[12] T. Koch, A. Ardo, A. Brernmer, and S. Lundberg. The building and maintenance of robot based internet search services: A review of current indexing and data collection methods. Technical report, Lund University Library, Sweden, 1996.

[13] M. Koster. Robots in the Web: threat or treat? Connexions, 4(9), 1995.

[14] Igor Kuralenok, Vladimir Dobrynin, Igor Nekrestyanov, Mikhail Bessonov, and Ahmed Patel. Distributed search in topic-oriented document collections. In Proc. of World Multiconfercnce on Systematics, Cybernetics and Informatics (SCI'99), volume 4, pages 377-383, Orlando, Florida, USA, August 1999.

[15] Qi Lu, Matthias Eichstaedt, and Daniel Ford. Efficient profile matching for large scale webcasting.

[16] Dietr Merkl. A Handbook of Natural Language Processing: Techniques and Applications for the Processing of Language as Text, chapter Text data mining. Marcel Dekker, New York, 1998.

[17] Ron Papka and James Allan. Document classification using multiword features. In Proc. of the CIKM'98, pages 124-131, New-York, November 1998.

[18] G. Salton and M. J. McGill. Introduction to modern Information Retrieval. McGraw-Hill Computer Science Series. McGraw-Hill, New York, 1983.

[19] Gerald Salton, James Allan, and Amit Singhal. Automatic text decomposition and structuring. Information Processing & Management, 32(2):127-138, 1996.

[20] Gerald Salton, Amit Singhal, Mandar Mitra, and Chris Buckley. Automatic text decomposition and summarization. Information Processing & Management, 33(2):193-208, 1997.

[21] Jacqucs Savoy and Justin Picard. Report on the TREC-8 Experiment: Searching on the Web and in Distributed Collections. In Proc. of the TREC'8, 1999.

[22] Amit Singhal, Mandar Mitra, and Chris Buckley. Learning routing queries in a query zone. In Proc. of the SIGIR'97, pages 25-32, July 1997.

[23] Rayrnie Stata, Krishna Bharat, and Farzin Maghoul. The term vector database: fast access to indexing terms for web pages. In Proc. of the WWW-9, May 2000.

[24] Atsushi Sugiura and Oren Etzioni. Query routing for web search engines: Architecture and experiments. In Proc. of the WWW-9, May 2000.

[25] Elen Voorhces and Donna Harman. Overview of the Sixth Text REtrieval Conference (TREC-6). In N 1ST Special Publication 500240: The Sixth Text REtrieval Conference (TREC-6), 1997.

[2G] Jinxi Xu and Jamie Callan. Effective retrieval with distributed collections. In Proc. of the SIGIR'98, 1998.

Работы автора по теме диссертации

[27] И.С. Некрестьяпов, В.Ю. Добрынин, В.В. Клюев. Оценка тематического подобия текстовых документов. Труды второй всероссийской научной конференции "Электронные библиотеки", стр. 204- 210, Протвино, России, сентябрь 2000.

[28] Е.В. Романова, М.В. Романов, И.С. Некрестьянов. Использование интелектуальных сетевых роботов для построения тематических коллекций. Программирование, 3:63-71, 2000.

[29] В.Ю. Добрынин, 11.С. Некрестьянов. Задача выбора тематических коллекций, релевантных запросу. Труды Всероссийской научно-методической конференции "Интернета и современное coo6uificmeo'\ Санкт-Петербург, декабрь 1998.

[30] И.Е. Кураленок, И.С. Некрестьянои. Автоматическая классификация документов с использованием семантического анализа. Программирование, 4:31-41, 2000.

[31] II. С. Некрестьянов. Маршрутизация запросов в системах распределенного поиска. Труды второй всероссийской научной конференции "Электронные библиотеки", pages 280-287, Протвино, Россия,сентябрь 2000.

[32] Mikhail Bessonov, Udo Heuser, and Igor Nekrestyanov. Open architecture for distributed search systems. In Proc. of Sixth International Conference on Intellegence in Services and Networks (IS&N'99), volume 1597 of Lecture Notes in Computer Science, Barcelona, Spain, April 1999. Springer.

[33] Igor Kuralenok, Vladimir Dobrynin, Igor Nekrestyanov, Mikhail Bessonov, and Ahmed Patel. Distributed search in topic-oriented document collections. In Proc. of World Multiconference on Systematics, Cybernetics and Informatics (SCI'99), volume 4, pages 377-383, Orlando, Florida, USA, August 1999.

[34] Tgor Nekrestyanov, Tadlig O'Meara, and Ekaterina Romanova. Building topic-specific collections with intelligent agents. In Proc. of Sixth International Conference on Intellegence in Services and Networks (IS&N'99), volume 1597 of Lecture Notes in Computer Science, Barcelona, Spain, April 1999. Springer.