Исследование и разработка методов и моделей поиска адекватной информации в полнотекстовых базах данных тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Андриенко, Евгений Владимирович

• Андриенко, Евгений Владимирович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Андриенко, Евгений Владимирович

ВВЕДЕНИЕ.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ СИСТЕМ ПОИСКА ИНФОРМАЦИИ В ПОЛНОТЕКСТОВЫХ БД.

1.1. Общее описание, задачи и основные требования к поисковым системам.

1.2. Существующие модели информационного поиска.

1.3. Информационно-поисковый язык.

1.4. Обзор существующих поисковых систем.

1.5. Обобщенная архитектура и недостатки существующих поисковых систем.

1.6. Выводы.

2. РАЗРАБОТКА МОДЕЛЕЙ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ В ИНТЕЛЛЕКТУАЛЬНОЙ ПОИСКОВОЙ СИСТЕМЕ.

2.1. Модель полнотекстового документа.

2.2. Модель поискового образа документа.

2.3. Модель поискового запроса.

2.4. Модель базы знаний экспертов.

2.5. Выводы.

3. РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ПОИСКА АДЕКВАТНОЙ ИНФОРМАЦИИ В ПОЛНОТЕКСТОВЫХ БД.

3.1. Алгоритм построения поискового образа документа.

3.2. Формальная грамматика поискового языка.

3.3. Алгоритмы построения расширенного поискового запроса на основе предложенной грамматики.

3.4. Алгоритм сравнения поискового образа и запроса.

3.5. Алгоритм построения семантической сети предметной области.

3.6. Общий алгоритм поиска релевантной информации.

3.7. Выводы.

4. РАЗРАБОТКА АРХИТЕКТУРЫ ИНТЕЛЛЕКТУАЛЬНОЙ ПОИСКОВОЙ СИСТЕМЫ.

4.1. Особенности архитектуры полнотекстовой поисковой системы.

4.2. Оценка временной сложности используемых алгоритмов.

4.3. Архитектура поисковой системы.

4.4. Результаты имитационного моделирования работы ИПС на коллекции технических документов.

4.5. Выводы.

Введение диссертации (часть автореферата) на тему «Исследование и разработка методов и моделей поиска адекватной информации в полнотекстовых базах данных»

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

Становление современного информационного общества немыслимо без использования информационных ресурсов в электронном виде. Переведенные в электронную форму и собранные в общую систему, информационные ресурсы приобретают новый статус, в котором реализуется качественно иной уровень хранения и распространения самой разнообразной информации, обеспечивая им более широкое распространение и эффективное использование [1-2]. Однако возникающие при этом коллекции документов имеют большую неоднородность. Как показывает статистика, доля структурированных данных в подобных архивах составляет не более 20%, остальные же 80% приходятся на долю различных документов, сканированных текстов и другой разрозненной информации [3]. При этом возникает проблема эффективного поиска адекватной информации, решение которой позволяет превратить разрозненные данные в целостную систему знаний [4]. Существующие поисковые системы первого поколения не могут в полной мере решить задачу поиска релевантной информации в полнотекстовых коллекциях, во многом по причине ориентированности на реляционные модели поиска, слабо применимые к поиску информации в коллекциях документов на естественном языке.

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

Ряд авторитетных исследователей внесли своими научными трудами значительный вклад в развитие информационно-поисковых систем: И.С. Некрестьянов, Д.А. Поспелов, В.Ю. Добрынин, А.Г. Дубинский, И.Е. Кураленок, А.Е. Ермаков, М.Р. Когаловский, A.B. Сокирко, Ф.У. Ланкастер, G. Saltón, A. Singhai, М. Mitra, S. Lawrence, P. Foltz, E. Fox, J. Cho, R. Baeza-Yates, K. Tajima, C. Van Rijsbergen, L. Gravano, J. Kleinberg.

Кроме того, существуют коммерческие организации, занимающиеся не только вопросами исследований, но и вопросами внедрения информационных поисковых технологий, это такие известные организации как Яндекс, Рамблер, Апорт, НейрОК, Гарант-Парк-Интернет, Медиа Лингва, Галактика-Зум, ABBYY-FTR, Hummingbird, Convera и др.

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

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

Объект исследования

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

Цели и задачи работы

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

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

Заключение диссертации по теме «Теоретические основы информатики», Андриенко, Евгений Владимирович

4.5. Выводы

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

- использование расширенного запроса, составленного на основании объединения знаний экспертов, знаний пользователя и знаний ИПС, полученных при анализе уже проиндексированных документов, позволяет повысить полноту ответа (при сравнении с обычным запросом на 15-20%) и точность отдельных релевантных документов (в экспериментах релевантность документов повышалась на 10-15%);

- семантическая сеть, получаемая на основании объединения ПОДов проиндексированных документов, позволяет получить полезную информацию о предметной области, такую как семантическое окружение запроса, более точно характеризующие направление поиска, термы, имеющие схожие семантические окружения, которые могут оказаться синонимами (в экспериментах число таких термов, оцененных экспертом как синонимы было равно 5-10%), кластера сильно связанных термов, выделяющих темы внутри предметной области, позволяющие решать задачу классификации результатов поиска; предложенные в работе дальнейшие направления совершенствования интеллектуальных поисковых информационных систем в рамках семантико-ориентированной модели поиска позволяют говорить об актуальности развития данного направления, как для науки, так и для практического применения.

Список литературы диссертационного исследования кандидат технических наук Андриенко, Евгений Владимирович, 2004 год

1. Gudivada V.N., Raghavan V.V. 1.formation Retrieval on the World Wide Web

2. IEEE Internet Computing. — 1997. V.I. N. 5. P. 58-68.

3. Информационные ресурсы Сибирского отделения РАН. —http://www.sbras.nsc.ru/win/elbib/infor/infres.html

4. Карташева Е. Интеллектуальные поисковые системы Excalibur. Сети,06, 1997.

5. Лобачев С.Л., Попов А.Э., Семенихин И.Н. Интернет-технологии вдистанционном и открытом образовании. Educational Technology & Society 4(2) 2001 ISSN 1436-4522 pp. 194-204.

6. G. Salton and M. J. McGill. Introduction to modern Information Retrieval.

7. McGraw-Hill Computer Science Series. McGraw-Hill, New York, 1983.

8. Андриенко E.B. Концепции поиска адекватной информации вполнотекстовых базах данных. Перспективные информационные технологии и интеллектуальные системы. Таганрог. Изд-во ТРТУ, №3 2003 (15) стр. 68-72.

9. Тематико-ориентированные методы информационного поискаhttp ://meta.math.spbu.ru/~igor/thesis/node 1 .html

10. Кононенко Р.Н. Разработка методов и алгоритмов мультиагентногопоиска в информационных средах гипертекстовой организации. Дисс.

11. К.т.н., Таганрог, ТРТУ, 2000 г.

12. Ермаков А.Е., Плешко В.В. Семантическая сеть текста в задачаханалитика. Информатизация и информационная безопасность правоохранительных органов: XI Международная научная конференция. Сборник трудов Москва, 2002. - С. 343-347.

13. Интеллектуальная поисковая система «СЛЕДОПЫТ» http://www.sledopyt.ru

14. Колесов А. Технологии извлечения знаний Fulcrum. Byte Magazine Online, №4, 2003.

15. Андриенко Е.В. Методы хранения сложных структур при поиске релевантной информации. Новые информационные технологии. Разработка и аспекты применения. Труды VI Всероссийской научной конференции с международным участием. Таганрог, 2003. Стр. 75-78.

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

17. Аграновский А. В., Арутюнян P. Э. Индексация массивов документов Мир ПК, №06, 2003.

18. Zadeh L.A. Fuzzy Sets // Information and Control. — 1965. V. 8. P. 338-353.

19. Асаи К., Ватада Д., Иваи С.и др. Прикладные нечеткие системы / Пер. с япон.; Под. Ред. Т. Тэрано, К.Асаи, М.Сугэно. — М.:Мир, 1993.—368 с.

20. Мелихов А.Н., Берштейн JI.C. Конечные четкие и расплывчатые множества. 4.2 Расплывчатые множества. Таганрог, ТРТИ 1981.

21. Raghavan V., Wong S.K.M. A Critical Analysis of Vector Space Model for Information Retrieval // J. Am. Soc. Information Science. — 1986. V. 37. N.5. P. 279-287.

22. Salton G. Automatic Text Processing. — Reading (MA): Addison-Wesley, 1989.

23. Frakes W.B., Baeza-Yates R. Information Retrieval: Data Structures and Algorithms. — EngleWood Cliffs, N.J.: Prentice Hall, 1992.

24. Ежов A.A. Шумский C.A. Нейрокомпьютинг и его применение в экономике и бизнесе.— М.: МИФИ, 1998. — 224с.

25. Shannon С.Е. Prediction and Entropy in Printed English // Bell Systems J. — 1951. V. 30. N. l.P. 50-65.

26. Robertson S.E. Spark-Jones K. Relevance Weighting of Search Terms // J. Am. Soc. of Information Sciences. — 1976. — P. 129 -146.

27. AltaVista Digital Equipment Corporation http://www.altavista.digital.com

28. Информационно-поисковые системы Internet http://www.citforum.ru/internet/services/services0312.shtml

29. Промышленная информационно-поисковая система Convera RetrievalWare http://www.odeon-ast.ru/products/rware.asp

30. Ланкастер Ф.У. Информационно-поисковые системы: Пер. с англ. -М: "Мир", 1972.-308 с.

31. Дейт К. Дж. Введение в системы баз данных / Пер. с англ.— 6-е изд.— К.: Диалектика, 1998. — 784 е.: ил.

32. Лингвистическое обеспечение информационно-поисковой системы Excalibur RetrievalWare: Аналитический аспект http://www.citforum.ru/seminars/cis99/vest2.shtml

33. Мощевикин А. Google знает, как найти. Мир ПК, №01, 2003.

34. Нетоскоп: Три поисковика Рунета, не считая Google http://travin.msk.ru/arc/searchengine.html

35. Новости и тенденции поисковых технологий (функциональные возможности ПС) ricn.ru/neiron/material/489/

36. Robert С. Berwick. "Computational Linguistics". MIT Press, Cambridge, MA, 1989. ISBN 0262-02266-4.

37. Extensible Markup Language (XML) 1.0 (Second Edition). W3C Recommendation. 6 October 2000. http://www.w3.org/TR/2000/REC-xml-20001006.37