Модели и методы поиска информационных ресурсов с использованием семантических технологий

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

Нгуен Ба Нгок

Модели и методы поиска информационных ресурсов

с использованием семантических технологий

Специальность 05.13.11 – Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

автореферат

диссертации на соискание ученой степени

кандидата технических наук

Томск – 2012

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

Научный руководитель:	доктор технических наук, профессор Тузовский Анатолий Федорович
Официальные оппоненты:	Марчук Александр Гурьевич доктор физико-математических наук, профессор Федеральное государственное бюджетное учреждение науки Институт систем информатики им. А.П. Ершова Сибирского отделения РАН, директор Привезенцев Алексей Иванович кандидат технических наук Федеральное государственное бюджетное учреждение науки Институт оптики атмосферы им. В.Е. Зуева СО РАН, научный сотрудник
Ведущая организация:	Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский государственный технический университет»

Защита состоится «27» ноября 2012 года в 15:00 часов на заседании диссертационного совета Д 003.061.02 на базе Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск, пр. академика Лаврентьева, 6, тел. (383)330-71-59.

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

Автореферат разослан «18» октября 2012 г.

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

С.Б. Сорокин

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Получено два свидетельства Роспатента на программное обеспечение, разработанное в рамках выполнения диссертационной работы: «TST – инструментальное программное обеспечение для организации поиска по семантическим метаописаниям» [10] и «Triple – редактор семантических метаданных» [11].

На защиту выносятся следующие результаты:

1. Разработанная модель семантического поиска информации, основанная на метаописаниях, которые формируются с использованием онтологических моделей знаний.
2. Разработанные методы вычисления близости между метаописаниями, триплетами и компонентами триплетов.
3. Метод оптимизации хранения наборов триплетов с использованием числовых идентификаторов и алгоритм сжатия словарей URI-идентификаторов.
4. Алгоритм быстрого поиска меток элементов онтологии в документах.
5. Разработанная архитектура системы семантического поиска информационных ресурсов.

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

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

1. VI Международная научно-практическая конференция «Электронные средства и системы управления» (Томск, 2010);
2. IV университетская научно-практическая конференция иностранных студентов, магистрантов и аспирантов, обучающихся в ТПУ, «Коммуникация иностранных студентов, магистрантов и аспирантов, в учебно-профессиональной и научной сферах» (Томск, 2010);
3. Интеллектуальные информационно-телекоммуникационные системы для подвижных и труднодоступных объектов (Томск, 2010);
4. IX Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых с международным участием «Молодежь и современные информационные технологии» (Томск, 2011);
5. VIII Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (Томск, 2011);
6. IX Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (Томск, 2012).

Публикации. Основные результаты диссертационного исследования изложены в 11 печатных работах, в том числе в 4 статьях из списка рецензируемых журналов, рекомендованных ВАК РФ.

Структура и объем диссертации. Диссертация содержит введение, 5 глав, заключение, список использованной литературы, содержащей 157 наименования. Общий объем диссертации составляет 198 страниц машинописного текста, включающих 38 рисунков, 18 таблиц, и 3 приложения.

Основное содержание диссертации

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

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

Постановка задачи поиска информационных ресурсов:

Заданы множество документов , где n – количество документов коллекции, и описание информационной потребности q.

Требуется найти подмножество R множества документов D, которое состоит из релевантных документов для запроса q – результирующее множество.

Кроме текстовых документов также может выполняться поиск мультимедийных ресурсов (изображений, аудиозаписей, видеороликов и т.п.). Однако для этого требуется создавать текстовые описания, которые включаются во множество документов D в качестве входных ресурсов.

Описание процесса поиска информации представлено на рис. 1.

Рис. 1. Процесс поиска информации

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

В настоящее время существует большое количество поисковых систем. Однако все они имеют общую архитектуру, которая представлена на рис. 2.

Рис. 2. Общая архитектура систем информационного поиска

Как показано на рис. 2 любая система информационного поиска выполняет следующие три базовые функции:

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

2) Формирование запросов – описания информационных потребностей пользователя на языке, поддерживаемом поисковой системой.

3) Сравнение – вычисления оценок близости (релевантности) между запросами и документами. На основе оценок релевантности определяется множество результатов, которое затем возвращается пользователям.

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

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

Model = [D, Q, F, R(q, d)], (1)

где D – множество логических представлений документов (логические представления документов являются их упрощенными моделями в поисковых системах); Q – множество логических представлений информационных потребностей (запросов); F – платформа для моделирования документов, запросов и для реализации функции вычисления близости между документами и запросами – функции R(d, q).

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

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

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

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

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

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

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

O = , (2)

где C – множество элементов, называемых понятиями (классами); E – множество экземпляров понятий (классов); R –свойство (предикатов); T – множество отношений, которые включают: частичный порядок на C и R, задающий отношения «подкласс–суперкласс»; отношение типа «экземпляр–родительское понятие» – instanceOf; семантические отношения между экземплярами.

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

На основе такого языка и естественного языка предлагается составить фразы формата «субъект–предикат–объект» (триплеты) для описания информационных ресурсов. При этом субъект есть URI-идентификатор понятия или экземпляра понятия; предикат – URI-идентификатор свойства; объект – URI-идентификатор понятия или экземпляра, или литеральное значение, а триплеты обозначаются как или p(s, o), где s – субъект; p – предикат; o – объект.

На основе таких фраз создаются логические представления документов – их метаописаний. При этом метаописания m(d) документа d представляют собой набор триплетов с весовыми коэффициентами, выражающими степени значимости триплетов:

, (3)

где n – количество триплетов; ki –весовой коэффициент триплета .

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

, (4)

где m – количество триплетов запроса q.

Метаописания позволяют более точно описать семантики документов (и информационных потребностей) по сравнению с известными форматами набора слов (BOW – bag of words) и набора понятий (BOC – bag of concepts) за счет формального представления знаний с помощью онтологий и явного описания связи между сущностями.

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