Математическая модель семантического поиска с использованием онтологического подхода тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Захарова, Ирина Викторовна

• Захарова, Ирина Викторовна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Захарова, Ирина Викторовна

1 ИНФОРМАЦИОННЫЙ поиск.ю

1 1 ИНФОРМАЦИОННЫЙ поиск

1.1.1 Модели информационного поиска

1.12 Булевское семейство моделей.

1.13 Векторные модели.

1 1.4 Вероятностные модели.

12 Релевантность

1 3 онтологии как интеллектуальные средств а представления знаний

1 3.1 Онтологии — определения и возникновение

13 2 Типы онтологии.

13 3 Разработка онтологии.

13 4 Применение онтологий

1.4 Поиск по контексту или семантический поиск.

2 ФОРМАЛЬНАЯ МОДЕЛЬ СЕМАНТИЧЕСКОГО ПОИСКА.

21 Формальные модели онтологий

2 2 Модель онтологии, специализированной для задач полнотекстового поиска

2 3 Функция интерпретации терминов

2 4 Функция интерпретации концепгдий

2 5 Математическая модель поисковой системы

2 6 Пример работы алгоритма.

3 ГЛАВА. МЕТОД ПОСТРОЕНИЯ ОНТОЛОГИИ НА ОСНОВЕ ББД.

3 1 Логическое представление библиографических баз данных

3.1.1 Система классификации УДК.

3 1.2 Описание библиографической записи.

3 2 Математическая модель библиографических баз данных

3 3 Метод построения онтологии

3 4 Структура библиографических баз данных и распределенный поиск по ним.

341 Физическая структура ББД.

3 4 2 Управление доступо и к информационным ресурсам • протокол Z39.50.

3 4 3 Особенности существующих систем распределенного поиска.

3.4.4 Техническая реализация поддержки протокола.

3 5 Архитектура предлагаемого решьния.

3.5.1 Общая логика работы системы.

3.5.2 Структуры данных и алгоритм работы клиентской программы.

3.4.3. Проблемы распределенного поиска.

3.6 Описание полученной онтологии.

4 ГЛАВА 4. АРХИТЕКТУРА, РЕАЛИЗАЦИЯ И ТЕСТИРОВАНИЕ ЭКСПЕРИМЕНТАЛЬНОЙ СИСТЕМЫ СЕМАНТИЧЕСКОГО ПОИСКА.

4.1 Описание ИПС, участвующих в тестирова! ши.

4.2 Архитектура и реализация системы.

4.2.1 Архитектура системы.

4.2.2 Реализация алгоритма семантического поиска с использованием онтологии.

4.3 Оценка эффективности модели.

4.3.1 Метод оценки.

4.3.2 Описание тестов.

4.3.3 Сравнительная характеристика эффективности модели.

Введение диссертации (часть автореферата) на тему «Математическая модель семантического поиска с использованием онтологического подхода»

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

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

Первые информационно-поисковые системы (ИПС) появились более тридцати лет назад [0,2], и с тех произошли существенные изменения, как в поисковых алгоритмах, так и в техническом оснащении. Современные поисковые системы [85, 86, 87, 54] автоматически собирают информацию в Интернете, учитывают морфологические особенности и производят оценку значимости найденных документов. В настоящее время в поисковых системах используется релевантная модель оценки соответствия исследуемого документа поисковому запросу [67]. Основная проблема заключается в сложности точной формулировки запроса - подбора ключевых слов, которые предстоит искать в телах документов. Это может быть связано с рядом причин, как недостаточным знанием пользователем терминологии предметной области, наличием в языке многозначных и синонимичных слов, и даже орфографическими ошибками в написании искомых слов, которые могут встречаться как в текстах, так и в самом запросе.

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

Одно из перспективных направлений развития информационно-поисковых систем - построение моделей «семантического», т.е. «смыслового» поиска - поиска ресурсов, наиболее релевантных запросу, а не просто содержащие слова из запроса [27].

Попытки реализации семантического поиска начались в конце 20 века, как зарубежными, так российскими учеными В 2000 году был предложен способ поиска схожих по семантике документов на основе сопоставления их лексических векторов [14]. В 1999-2002 годах как зарубежными так и российскими учеными было предложено использовать в модели семантического поиска онтологии предметных областей [29,82,88].

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

В России информационно-поисковая система с использованием онтологии была впервые реализована в информационно-поисковой системе УИС «Россия» [6]. Смирнов И.В., Соченков И.В.Муравьев В. В., Тихомиров И. А. предложили собственную модель семантического поиска, в которой объединены онтологические, статистические и лингвистические методы поиска, реализовав ее в информационно-поисковой системе «Exactus» [7]. Основная проблема при реализации данного подхода - отсутствие достаточно больших и качественных онтологии предметных областей, особенно на русском языке.

Последние несколько лет в работах [37, 62 ,63, 61, 65] рассматриваются различные методы для автоматического формирования онтологии, для чего используется лексический и синтаксический анализ документов. Но релевантность полученных онтологий достаточно низкая, и вопрос автоматического построения онтологий остается актуальным.

Основные задачи диссертационного исследования.

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

Для достижения этой цели необходимо решить следующие задачи:

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

2. разработать модель онтологии, способной отражать понятия и структуры, свойственные текстам естественного языка;

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

4. разработать математическую модель семантического поиска, использующую созданную онтологию;

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

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

Научная новизна и практическая ценность диссертационного исследования:

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

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

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

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

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

1. Разработана технология построения онтологии на основе распределенных библиографических баз данных с использованием протокола z39.50.

2. Разработаны, реализованы и внедрены в рамках библиотечной информационной системы ЧелГУ алгоритмы семантического поиска на основе полученной онтологии.

На защиту выносятся:

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

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

3. Новый метод автоматизированного построения обобщенной онтологии на основе библиографических баз данных, распределенных в сети Интернет.

4. Практическое применение предложенного метода для создания обобщенной онтологии с использованием возможностей протокола Z39.50

5. Предложен ряд алгоритмов на основе модели семантического поиска для практической реализации в информационно-поисковой системе.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Захарова, Ирина Викторовна

Заключение

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

Windows lis Яндекс Google SemanticSearch

Личность----

-•л.

А А |

Полнота

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

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

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

4. Реализованы алгоритмы формирования обобщенной онтологии на основе протокола Z39.50, в том числе:

5. алгоритм формирования автоматизированных запросов к протоколу Z39.50;

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Захарова, Ирина Викторовна, 2010 год

1. LUHN, Н.Р. A statistical approach to mechanised encoding and searching of library information// IBM Journal of Research and Development, 1, 1957, P. 309-317.

2. Stephen E. Robertson, C. J. van Rijsbergen, Martin F. Porter: Probabilistic Models of Indexing and Searching. SIGIR, 1980. P.35-56

3. O.J1. Голицына, H.B. Максимов. Технология и средства доступа к распределенным ресурсам электронных библиотек и баз данных.//Электронные библиотеки, 2000, Т 3, вып. 1.

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

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

6. И.В. Смирнов, И.В.Соченков, В.В. Муравьев, И.А. Тихомиров. Результаты и перспективы поискового алгоритма

7. Exactus. // Российский семинар по Оценке Методов Информационного Поиска. Труды РОМИП 2007-2008: Семинар в рамках Всероссийской науч. конф. RCDL'2008. 9 окт. 2008 г., Дубна изд-во Санкт-Петербург: НУ ЦСИ, 2008. С.66-76.

8. Modern Information Retrieval. Baezo-Yates R. and Ribeiro-Neto B. ACM Press Addison Wesley, 1999.

9. Information retrieval using a Singular Value Decomposition Model of Latent Semantic Structure. G. W. Furnas, S. Deerwester, S. T. Dumais, Т. K. Landauer, R. A. Harshman, L.A. Streeter, and K.E. Lochbaum. ACM SIGIR, 1988.

10. Greisdorf H. Relevance: An Interdisciplinary and Information Science Perspective. Informing Science, 3(2):67-72, 2000.

11. Mizzaro S. Relevance: The Whole History. Journal of the American Society of Information Science, 48(9):810-832, 1997.

12. Gabrielli S., Mizzaro S. Negotiating a multidimensional framework for relevance space. In Proc. of the MIRA'99, pp. 1-15, 1999.

13. Draper S. Mizzaro's framework for relevance. Available from http://staff.psy.gla.ac.Uk/~ steve/stefano.html.

14. Vakkari P. Cognition and Changes of Search Terms and Tactics during Task Performance: A Longitudinal Study. In Proc. of the RIAO'2000, pp. 894-907, 2000.

15. Saracevic T. Relevance reconsidered 1996. In Proc. of the CoLlS2, pp. 201-218, 1996.

16. Vakkari P. Relevance and contributory information types of searcheddocuments in task performance. In Proc. of the SIGIR'OO, 2000.

17. Studer R., Benjamins V.R., Fensel D. Knowledge Engineering: Principles and Methods. In Data & Knowledge Engineering, 25, 1998, pp. 161 -197.

18. Patil R.S. Causal Representation of Patient Illness for Electrolyte and Acid-Base Diagnosis. PhD Thesis, Laboratory for Computer Science, MT, 1981.

19. Weiss S.M., Kulikovski C.A., Amarel S. & Safir A. A Model-Based Method for Computer-Aided Medical Decision Making. In Clancey W.J. & Shortliffe E.H. Editors, Reading in Medical Artificial Intelligence, the First Decade. Addison Wesley, 1984.

20. Черняховская М.Ю. Представление знаний для диагностических экспертных систем в медицине. Владивосток: ДВО РАН СССР, 1983.

21. Проблемно-ориентированные представления. Препр. Владивосток: ИАПУ ДВНЦ АН СССР, 1985.

22. Genesereth, M.R., Fikes R.E. et al. Knowledge Interchange Format (version 3.0) Reference Manual. Interlingua Working Group of the DARPA Knowledge Sharing Effort. Computer Science Department, Stanford University. Report Logic-92-1.

23. Gruber T.R. Ontolingua: A Mechanism to Support Portable Ontologies. Technical Report KSL-91-66, Stanford University, Knowledge Systems Laboratory, 1992.

24. G ruber T.R. A Translation Approach to Portable Ontology

25. Specifications. In Knowledge Acquisition, 1993, 5: 199-220.

26. Wielinga, В., Schreiber A.T., Jansweijer W., Anjewierden A. and van Harmelen F. Framework and Formalism for Expressing Ontologies (Version 1). ESPRIT Project 8145 KACTUS, Free University of Amsterdam Deliverable, D01b.1, 1994.

27. Mike Ushold, Michael Gruninger (1996) Ontologies: Principles, Methods and Applications, Knowledge Engineering Review, Volume 11,Number 2.

28. Mike Ushold, Martin King (1995) Towards a Methodology for Building Ontologies, Workshop on Basic Ontologica Issues in Knowledge Sharing.

29. Jeff Heflin. James A. Hendler. Sean Luke: Applying Ontology to the Web: A Case Study. IWANN (2) 1999. P. 715-724

30. Richard Fikes, Adam Farquhar (1997) Large-Scale Repositories of Highly Expressive Reusable Knowledge.

31. Nicola Guarino (1999) OntoSeek: Content-Based Access to the Web, IEEE Intelligent Systems, May/June , pp. 70-80.

32. H. Takeda, M. Takaai, and T. Nishida (1998) Collaborative developmentand Use of Ontologies for Design, Proceedings of the Tenth International IFIP WG 5.2/5.3 Conference PROLAMAT 98, September 9-10-11,12,Trento, Italy.

33. V.F. Khoroshevsky. (1998) Knowledge v. s. data spaces: how an applied semiotics to work on web. //Proceedings of САГ98, Pushchino, Russia, C. 7-16.

34. Ю.А. Загорулько, И.Г. Попов (1997) Описание сложных предметных областей на основе интеграции средств представления знаний. // Труды международного семинара Диалог'97 по компьютерной лингвистике и ее приложениям, Москва, -С. 110-115.

35. Н. В. Майкевич.(1998) От информационного пространства к пространству знаний. Онтологии в Интернет. //Труды конференции КИИХ98, Пущино, Россия. С.152-158.

36. Andreas Hotho, Alexander Maedche, Steffen Staab. Ontology-based Text Clustering. In Proc. of IJCAI 2001. 2001.

37. A Statistical Interpretation of Term Specificity and Its Application in Retrieval. Karen Sparck Jones. Journal of Documentation, 1972.

38. Relevance Weighting of Search Terms. S.E. Robertson and Sparck Jones K. JASIS, 1976.

39. On relevance, probabilistic indexing and information retrieval. M. E. Maron and J. L. Kuhns. Journal of the ACM, 1960.

40. Information retrieval using a Singular Value Decomposition Model of Latent Semantic Structure. G. W. Furnas, S. Deerwester, S. T. Dumais, Т. K. Landauer, R. A. Harshman, L.A. Streeter, and K.E. Lochbaum.1. ACM SIGIR, 1988.

41. The approximation of one matrix by another of lower rank. C. Eckart, G. Young, Psychometrika, 1936.

42. Семантические поисковые системы. http://asknet.ru/Analytics/semantics.htm.

43. Смирнов А.В., Пашкин М.П., Шилов Н.Г., Т.В. Левашова. Онтологии в системах искусственного интеллекта: способы построения и организации (часть 1) // "Новости искусственного интеллекта" № 1 (49) 2002 г.

44. Alexander S. Kleshchev, Irene L. Artemjeva. Mathematical Models Of Domain Ontologies. //Technical Report, Vladivostok2000

45. Hinkelmann K. and Kieninger Th., 1997 Task-oriented web-search refinement and information filtering.

46. T. Joyce and R.M. Needham// The Thesaurus Approach to Information Retrieval American Documentation, 1958

47. Karen Sparck Jones.A Statistical Interpretation of Term Specificity and Its Application in Retrieval.Journal of Documentation, 1972

48. W. Furnas, S. Deerwester, S.T. Dumais, Т.К. Landauer, R. A. Harshman, L.A. Streeter, and K.E. Lochbaum.Information retrieval usinga Singular Value Decomposition Model of Latent Semantic Structure. GACM SIGIR, 1988

49. The approximation of one matrix by another of lower rank C. Eckart, G. Young. Psychometrika, 1936

50. S.E. Robertson and Sparck Jones K.Relevance Weighting of Search Terms//JASIS, 1976

51. E. А. Гребеников Метод усреднения в прикладных задачах. М.-.Наука, 1986 г.

52. Borlund P., Ingwersen P. Measures of relative relevance and ranked half-life: Performance indicators for interactive IR. In Proc of the SIGIR'98, pp. 324-331, 1998.

53. Baeza-Yates R., Ribeiro-Neto B. Modern Information Retrieval. ACM Press, 1999.

54. Большая Российская энциклопедия, 1969-1978

55. RUSMARC в примерах : учебное пособие для каталогизаторов / Национальный информационно-библиотечный центр «ЛИБНЕТ». — М. : ФАИР-ПРЕСС : Центр «ЛИБНЕТ», 2003.

56. Боровков, А. А. «Теория вероятностей», М.: Наука, 1986.

57. Максимов Н.В., Сысойкина М.А. О реализации электронной библиотеки с использованием протоколов HTTP и Z39.50// Электронные библиотеки, 2002, Т 5, вып. 1.

58. Жижимов О.Л. Введение в Z39.50. Новосибирск: Изд-во НГОНБ, 2000.

59. Indexing by Latent Semantic Analysis. S. Deerwester, S.T.116

60. Dumais, G.W. Furnas, Т.К. Landauer, R. Harshman. JASIS, 1990.

61. Браславский П.И., Соколов Е.А. Сравнение пяти методов извлечения терминов произвольной длины//Материалы международной конференции «Диалог 2008», Москва. С.67-75

62. Ермаков А.Е. Автоматизация онтологического инжиниринга в системах извлечения знаний из текста//Материалы международной конференции «Диалог 2008», Москва. С. 154-159

63. Лукашевич Н.В., Добров Б.В., Чуйко Д.С. Отбор словосочетаний для словаря системы автоматической обработки текстов. //Материалы международной конференции «Диалог 2008», Москва. С.339-345

64. Рубашкин В.Ш., Пивоварова Л.М Онторедактор как комплексный инструмент онтологической инженерии. //Материалы международной конференции «Диалог 2008», Москва. С. 453-460

65. Сидорова Е. А., Кононенко И. С. Подход к извлечению фактов из текста на основе онтологии. //Материалы международной конференции «Диалог 2009», Москва. С.451-458

66. М. Овдей, Г.Ю. Проскудина. Обзор инструментов инженерии онтологий. Электронные библиотеки, 2004, Том 7, Выпуск 4.

67. Guido Zuccon, Leif Azzopardi, Keith van Rijsbergen: The Quantum Probability Ranking Principle for Information Retrieval. ICTIR 2009.P. 232-240.

68. Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — M.: «Вильяме», 2007. — С. 824

69. Когаловский М. Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002. - 800 с.

70. Когаловский М. Р. Электронные библиотеки развитие продолжается//Программирование, МАИК,"Наука"/ Интерпериодика. - 2002. -№ 4.

71. Когаловский М. Р. Интеграция данных в информационных системах./Яруды третьей Всероссийской конференции "Стандарты в проектах современных информационных систем", Москва, 23-24 апреля 2003 г.

72. Snow R., Jurafsky D., Ng A.Y. Semantic taxonomy induction from heterogenous evidence // Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL. Sydney, Australia. - 2006. pp.801-808.

73. Nedellec C.,Nazarenko C. Ontology and Information Extraction: A Necessary Symbiosis II Ontology Learning from Text: Methods, Evaluation and Applications. BuitelaarP., Cimiano P. and Magnini B.(eds .), lOS Press Publication:2005.

74. Nicola Guarino. The Ontological Level: Revisiting 30 Years of Knowledge Representation. Conceptual Modeling: Foundations and Applications, 2009. P. 52-67

75. Гаврилова T.A. Извлечение знаний: лингвистический аспект // Корпоративные системы (Enterprise Partner), 2001. № 10 (25). - с. 24-285.

76. Страуструп, Бьерн. Язык программирования С++/ Б. Страуструп ; пер. с англ. С. Анисимова, М. Кононова ; под ред. Ф.

77. Андреева, А. Ушакова .— спец. изд. — М.: Бином-Пресс, 2007

78. Роман Гадиатулин, Светлана Чуприна. Rule-Mining: подход к автоматизированному извлечению онтологий //Xlll-th International Conference,Knowledge-Dialogue-Solution, june 18-24, 2007, Varna (Bulgaria). C.445-451.

79. Mike Taylor. Zthes: A Z39.50 Profile for Thesaurus Navigation. Version 0.3b.

80. ANSI/NISO Z39.50-1995. Information Retrieval (Z39.50): Application Service Definition and Protocol Specification. Z39.50 Maintenance Agency Offical Text for Z39.50-1995, July 1995.

81. Жижимов О.Л., Мазов H.A., Болванов А.Ю. Опыт построения распределенной информационной системы на базе протокола Z39.50. Матер. 6 Междунар. Конф. "Крым-99", т.1, стр. 249-252.

82. Воскресенский А.Л., Хахалин Г.К. Средства семантического поиска. //Материалы международной конференции «Диалог 2006», Москва. С.100-105.

83. Лукашевич Н.В., Добров Б.В. Тезаурус русского языка для автоматической обработки больших текстовых коллекций.// Компьютерная лингвистика и интеллектуальные технологии: Тр. Междунар. семинара Диалог'2002. М.: Наука, 2002. Т.2, С. 338-346.

84. Осипов Г. С., Куршев Е. П., Кормалев Д. А., Трофимов И. В., Рябков О. В., Тихомиров И. А.// Семантический поиск в среде интернет. ИПС РАН, 2003.

85. Ермаков А. Е. Эксплицирование элементовсмысла текста средствами синтаксического анализа-синтеза // Компьютерная лингвистика и интеллектуальные технологии: труды Международной конференции Диалог'2003. — М.: Наука, 2003.

86. Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. — 1998 r.

87. Sergey Brin, Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. — 1998 r.

88. Гусев Владимир Сергеевич. Яндекс: эффективный поиск информации в Интернет. Краткое руководство. — М.: «Диалектика», 2007. — 224 с.

89. Гаврилова Т. А., Хорошевский В. Ф. Базы знаний интеллектуальных систем. Учебник. -СПб.: Питер, 2000.