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

ШАБАЛИН Александр Георгиевич

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

РАЗРАБОТКА II ИССЛЕДОВАНИЕ ГРАММАТИЧЕСКОГО ПОДХОДА ДЛЯ РЕШЕНИЯ ЗАДАЧИ АВТОМАТИЧЕСКОГО ВЫРАВНИВАНИЯ И ОБЪЕДИНЕНИЯ ОНТОЛОГНЙ ПРЕДМЕТНЫХ ОБЛАСТЕЙ

Специальность: 05.13.17 — «Теоретические основы информатики»

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

Таганрог - 2013

- І.1ЮЛ 2013

005531249

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет».

Научный руководитель:

доктор технических наук, профессор Вишняков Юрий Муссович

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

Чернухин Юрий Викторович

доктор технических наук, профессор ФГАОУ ВПО «ЮФУ», профессор кафедры вычислительной техники, г. Таганрог

Логвинов Юрий Николаевич

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

г. Ростов-на-Дону

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

ФГБОУ ВПО «Ростовский государственный университет путей сообщения» (РГУПС), г. Ростов-на-Дону

Защита состоится « 2 » июля 2013г. на заседании диссертационного совета Д 212.208.21 при Южном федеральном университете по адресу: 347928 г.Таганрог, пер.Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке ЮФУ по адресу: г.Ростов-на-Дону, ул.Пушкинская, 148.

Автореферат разослан « 27 » мая 2013г.

Учёный секретарь

диссертационного совета Д 212.208.21 А.В.Боженюк

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

1. Провести анализ существующих методов и инструментальных средств соединения онтологий.

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

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

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

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

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

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

1. Предложен новый метод формального описания иерархических связей между различными сущностями предметной области, отличающийся от известных тем, что используется грамматика, которая порождает всё множество классификационных последовательностей для элементов иерархической системы. Каждая классификация рассматривается как допустимая терминальная цепочка, а совокупность всех правильных цепочек совпадает с семейством иерархий. (С. 38-59, 66-70).

2. Разработана формальная модель онтологии предметной области в качестве средства представления распределенных сетевых знаний, которая отличается от известных тем, что построена на основе механизма поровдающих грамматик. (С. 3135).

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

Основные положения, выносимые на защиту:

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

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

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

3. Разработан алгоритм решения задачи автоматического выравнивания и непосредственного объединения онтологий, которые имеют своё представление на базе грамматического подхода.

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

Использование результатов работы. Полученные в работе результаты использованы в рамках решения задач по исследованию и разработке средств представления и накопления знаний и внедрены в научно-исследовательский процесс лаборатории Е1ЛЭ1С.

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

- Всероссийской научной школе-семинаре молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки» (Таганрог, ТТИ ЮФУ, 25-28 мая 2010г.);

- II Международной научно-технической конференции «Технологии разработки информационных систем (ТРИС-2011)» (Геленджик, филиал ТТИ ЮФУ, 18-24 сентября 2011г.);

- IX Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системы анализ и управление» (Таганрог, ТТИ ЮФУ, 08-09 декабря 2011г.);

- Всероссийской научной школе-семинаре молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки» (Таганрог, ТТИ ЮФУ, 23-25 мая 2012г.);

- III Международной научно-технической конференции «Технологии разработки информационных систем (ТРИС-2012)» (Геленджик, филиал ТТИ ЮФУ, сентябрь 2012г.).

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

Структура и объем работы. Диссертация состоит из введения, трёх глав и заключения. Основной текст изложен на 124 страницах, содержит 8 рисунков, 13 таблиц, список литературы из 104 наименований, приложения изложены на 17 страницах, включают коды программ, реализующих программную модель.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Модель описания иерархии. Каждая иерархия представляет собой множество классификаций своих объектов, которые можно понимать как пути на дереве иерархии от корня к вершинам, принадлежащих кроне. Если выделить набор требований характерных для всякой классификации и сформулировать их в качестве системы порождающих правил-шаблонов Р для грамматики 5 = (V, U, I, Р), тогда можно заранее выводить синтаксис классификаций на основе специфицированных подстановок Р, а семантику вводить уже потом через интерпретацию терминалов V и нетерминалов П. Это делает возможным реализацию алгоритма представления всякой иерархии через грамматику 5, где конкретная интерпретация множеств Уи(/,а также спецификация для Р выступают в качестве входных данных.

Модель описания онтологии. Онтология состоит из формальных описаний иерархий для различных сущностей предметной области. Всякая иерархия описывается через представленную грамматику S. Формальное описание онтологии 0 = (Х,Я,Ф) можно сопоставить с грамматикой S = (V, U, 1,Р). Объединение множества терминалов и нетерминалов Vi) U грамматики 5 соответствует множеству различных сущностей X онтологии О. Система таксономий терминов R онтологии О может быть представлена семейством всех допустимых иерархических структур, которые выводятся грамматикой S. Следовательно, множество R полностью определяется через язык ¿(5), порождаемый грамматикой S. Множество функций интерпретации Ф онтологии О, заданных на различных сущностях, может быть поставлено в соответствие специфицированной схеме подстановок Р грамматики 5.

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

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

Схема грамматики. Рассмотрим порождающую грамматику S = (V,U,I,P). Отождествим терминальные символы V с множеством классифицируемых объектов иерархической системы, начальный символ I соответствует началу всякой

классификации. Отождествим множество нетерминалов С/ с множеством классификационных категорий.

Пусть множество терминалов V дополнено символом <5, который соответствует пустому элементу и служит индикатором начала и конца всех правильных терминальных цепочек, а множество нетерминалов I/ - символом Д, который соответствует пустой категории: Д= {5}.

Грамматика 5 порождает язык ¿(5), который можно понимать как лес деревьев: каждое дерево ориентировано от корня, вершины помечены терминалами из V или II, ребро - это применение продукции грамматики, а пути из корня в данную вершину -это выводы, которые соответствуют классификационным последовательностям. Таким образом, множество слов в языке ¿(5) - это множество всех путей во всех деревьях от корня к вершинам, принадлежащих кроне.

Грамматика для описания иерархии без учёта классификационных категорий. В этом случае можно считать, что множество нетерминалов Ц будет состоять из двух элементов, один из которых есть просто константа А, а другой - это пустой элемент, введенный по построению: I] = {А, Д}.

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

/ -» 5А = хА I ■ >х = 5

хА^хаРА = хА\х = хар;

хА^харА = хА\х=хар;

А -> 8,

где ар, 8 е V; х 6 V': А, А ВЦ. Запись хар означает конкатенацию (сцепление) терминальной цепочки х и терминала Ор. Запись вида хА _ ха означает

подстановку значения хар в формулу хА вместо х.

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

Для вычисления правых частей подстановок Р может быть использовано отображение вида Н: V' х {Л, Д} -> V, где V - алфавит терминальных символов; V' -множество всех слов в алфавите V; и = {А, Д} - алфавит нетерминальных символов. По своему смыслу отображение вычисляет множество следующих элементов классификационной последовательности или пустой терминал, если классификация заканчивается:

Н(х,Х) = {ар} Н(х,А)=8 ' где ар,<У 6 6 У',А,А 6 У.

Действие отображения Н для вычисления правых частей подстановок задаётся в табличном виде:

X Н(х,[А,А})

8 Ш

8ак {ад*

8акЬп... ст 8

' Грамматика для описания иерархии с учётом классификационных категорий. В данном случае основное уточнение для правил-шаблонов Р состоит в использовании множества нетерминалов Ак вместо одной константы А: и = {А1,..., Ат, Д}. Система порождающих правил-шаблонов Р определяется следующим образом:

/ -> 6Ак = хАк I : I* = 8

хАк -> ха£Лп = хАп |х = хак",

хАк -» ха%А = дгА |х _ хак ;

хАк -»х8;

А->8,

где Ак, Ап, А е У; а£ е Ак; 8 е V; х Е V'.

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

Переменные Ак, А", Д, которые присутствуют в правых частях подстановок Р, можно вычислить отображением вида: V' -» и, где V — алфавит терминальных символов; V' - множество всех слов в алфавите V; И — алфавит нетерминальных символов. Отображение ^ действует на терминальную цепочку х и вычисляет множество категорий {Ак} для следующего классифицируемого элемента или пустую категорию Д, если классификация завершена.

Терминалы ак, которые принадлежат соответствующим категориям Ак, могут быть вычислены отображением вида: Н:У X I! -* V. Отображение действует на терминальную цепочку х и в соответствии с категорией Ак, которое вычисляется отображением Р на предыдущем шаге, определяет множество следующих классифицируемых непустых терминалов {о£} или пустой терминал 8, если классификация завершается. Таким образом, для вычисления правых частей подстановок Р может быть использована система отображений следующего вида:

я*)=р;ь

I Н(х,А) = 5,

где Ак, Д£ У; ак е Ак, 8 Е V, х 6 V.

Действие системы отображений для вычисления правых частей подстановок Р задаётся в табличном виде:

X Н(х,Ак) Н(х,Ап) Н(х, Д)

5 Шб

{а?}|<5

S

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

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

Пространственная эффективность. Это случай грамматики для описания иерархии без учёта классификационных категорий. Рассмотрим иерархию объектов из N элементов. Через N(S) обозначим число ячеек памяти, которое требуется для хранения таблицы действия отображения Я: К* X {Л,Д} V, а через N(G) - число ячеек памяти для хранения соответствующего многосвязного списка. Существует точная оценка для хранения многосвязного списка из N узлов: N(G) = 2N — 1.

В случае представления одной иерархии таблицу для действия отображения Н можно оптимизировать таким образом, что оказывается достижима следующая оценка для хранения: N(S) = W(G) + 1 - М, где М - число висячих вершин в двусвязном списке.

В общем случае для представления семейства иерархий имеет место оценка: W(S) = ZW(G) + Кобщ - Мобщ = 2Ыо6щ - Мо6щ, где Y,N(G) - суммарные затраты на хранение всех списков, Ко6щ - число корневых вершин (число многосвязных списков), Мо6щ - общее число висячих вершин во всех иерархиях семейства, Л/общ - общее число вершин во всех иерархиях семейства.

Таким образом, для всякой древовидной структуры имеет место неравенство: W(S) < W(G). Чем более разветвленные структуры требуется описать, тем выше пространственная эффективность алгоритма с использованием грамматического подхода.

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

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

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

Рис. 1. Программная модель агента для формирования единой онтологии

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

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

Первый из поставленных экспериментов состоял в том, чтобы описать онтологию предметной области с использованием механизма порождающих грамматик, сформировать серию прямых и обратных вопросов к онтологии, которые могут быть обработаны машиной поиска. Схема эксперимента по созданию онтологии заключается в том, что на вход программному комплексу, построенному на основе предложенной модели агента, подаются глоссарий терминов и классификационные цепочки, которые описывают структурные характеристики моделируемой среды. На основе полного множества классификационных последовательностей ¿(5) программный комплекс автоматически восстанавливает таблицу действия отображений F и Н для вычисления правых частей подстановок Р грамматики S. Глоссарий терминов и множество классификационных цепочек для различных сущностей предметной области по определению являются распределенными ресурсами, в тоже время таблица действия системы отображений это уже объект, который локализован внутри программного агента.

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

В диссертационной работе экспериментальное моделирование процесса представления онтологий и процедуры их соединения проводилось на примере предметной области преподавания дисциплин информатики, которые отражены в отчётах Computing Curricula 2001 и Computing Curricula 2007, разработанных Институтом инженеров электротехники и электроники (IEEE-CS) и Ассоциацией по вычислительной техники (АСМ) по заказу образовательного сообщества стран Вашингтонского Соглашения. Результаты отчётов также использованы в российской высшей школе. В отчётах предметная область «Информатика» представлена с разных точек зрения и оформлена собственными разделами: «Совокупность знаний по информатики», «Задачи обучения», «Модели изложения материала», «Профессиональная практика и профессионализм», «Характеристики выпускников информатики».

Для целей экспериментального моделирования каждая точка зрения в выбранной предметной области была оформлена в виде отдельной онтологии, которая создавалась независимо от принятой системы понятий в других онтологиях. В качестве иллюстрирующих примеров в диссертационном исследовании подробно рассмотрены две онтологии^ = (V^U^I.P-J - «Задачи обучения» и 52 = (V2,U2,I,P2) - «Характеристики выпускников информатики». Фрагменты глоссариев для этих онтологий приведены на рис. 2.

А1 Задачи обучения

а Применять метода структурной декомпозиции программы

а Описать механизмы передачи параметров

а Указать свойства присущие хорошим алгоритмам

а Описать стратегии полезные при отладке

А2 Курсы, в рамках которых решаются задачи обучения

»? РР1. Основные конструкции программирования

al РР2. Алгоритмы решения задач

А3 Приобретаемые навыки

а? Высокоуровневое понимание систем в целом

а? Понимание влияния теории на практику

А1 Характеристики выпускников информатики

а\ Системный взгляд на дисциплину

Понимание связи теории и практики

А2 Требования к обладанию некоторым качеством

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

a¡ Высокоуровневое понимание систем в целом

al Понимание влияния теории на практику

Рис. 2. Фрагменты глоссариев для онтологий «Задачи обучения» и «Характеристики выпускников информатики»

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

5? - «Характеристики выпускников информатики»

а|а| 1

ala¡ "Wz а2а1

a\al 113 а1аЗа1 a\a\al

а1а1

Рис. 3. Классификационные цепочки для фрагментов глоссариев

Глоссарии терминов и множества классификационных цепочек - это описательные конструкции, которые могут размещаться где-либо в сети, в том числе фрагментарно. На основе собранных множеств классификационных цепочек программный агент автоматически восстанавливает табличный вид действия отображений Г и Я для вычисления правых частей подстановок Рг и Р2. Программный агент, посматривая сетевые ресурсы, строит внутри себя локализованное целостное представление каждой онтологии на основе табличного вида для отображений и Н. На рис.4 показаны полученные внутри программного агента табличные представления для действия отображений Рий.

xs A1 A2 A3 Л

S al,a,,a\,al

5а} a\ al

Sal al al

Sa\ aj

Sa\ a2

Sala\ al

Sala2 S

Sa\a\ a?

SaU f S

Sa\al S

Sa\a2 S

Sala\a? S

Sa)ala? S

A1 A2 Л

S al,a\

Sal al, al

Sai al

Salal S

Sala2 s

Sala2 s

Рис.4. Табличные представления для действия отображений F и Н

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

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

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

Если стоит задача обмена данными между разными онтологиями, то они должны использовать одинаковые обозначения для терминов, которые описывают. Представление онтологии О в виде грамматики 5 заставляет проектировщика сводить все рассматриваемые различные сущности предметной области к величинам или атомарным, которые имеют отдельные обозначения (это терминалы), или составным из атомарных, которые имеют отдельные обозначения (это нетерминалы), или составным из атомарных, которые не имеют отдельных обозначений (это терминальные цепочки). Из этого следует, что процедура сохранения исходных данных объединяемых онтологий с учётом установленных соответствий между их концептами сводится к переобозначению терминалов и нетерминалов с использованием единой системы обозначений в рамках общей онтологии.

Пусть 51 = (У\, Рг) и 52 = (У2, и2, /, Р2) - выравниваемые онтологии. Алгоритм процедуры выравнивания может быть представлен в следующем виде:

1. Внутри глоссария онтологии 5! все обозначения для сущностей А' е а} е У1г которые совпадают с обозначениями А' 6 I]2,а] 6 У2 из онтологии 52, заменяются на новые обозначения: А' -» Лк & V/ (а] -> а;к), если А1 Е 11г и ЗА1 е И2- Тем самым достигается сквозная нумерация обозначений для терминалов и нетерминалов из грамматик 5\ и 52.

2. После переобозначения элементов глоссария перестраиваются классификационные цепочки онтологии 54 с учётом новых обозначений: если а] -> а/, то а5 ... а] ... а™ а? ... а/ ... а™.

3. Внутри глоссария онтологии 5г все сущности, которые являются подобиями сущностей из онтологии 52, получают соответствующее дополнительное обозначение, заимствованные из онтологии 52. То же самое проделывается с глоссарием онтологии 52 в отношении подобных сущностей из Пусть А1 6

Ци а} € Уг, Ак еи2,а>| е Уг. Если А'~Ак (подобно), то 111 = и1и {Лк}, У2 = Щ и {Л;}. Если а]~о£, то У1 = У1и {а£} ,У2 = У2и (а)}. При необходимости естествешо потребовать, чтобы добавление терминала ак из онтологии 52 в глоссарий онтологии 5! означал и добавление категории Ак в глоссарий онтологии ^ (и наоборот).

4. Множество классификационных цепочек каждой онтологии 5г и 52 дополняется новыми классификациями с учётом добавленных в глоссарий подобий: если а]~а£, то для всех цепочек ... а] ... а{" е ¿(5Ч) имеем ¿(5,) = ¿(5,) и {а* ...а™}.

Результатом работы алгоритма выравнивания является то, что две онтологии и 52 используют единую систему обозначений своих сущностей. Для подобных сущностей введены соответствующие множественные обозначения, указывающие на их принадлежность разным онтологиям, перестроены классификационные цепочки и все эти изменения сохранены внутри онтологии. Программная модель автоматически восстановит таблицы действия отображений ?ий для вычисления правых частей подстановок Рг и Р2 выравниваемых онтологий ^ и 52 с учётом внесённых изменений.

В диссертационном исследовании для экспериментального моделирования процедуры выравнивания были рассмотрены две независимые онтологии: 5Х -«Задачи обучения» и 52 - «Характеристики выпускников информатики». Предложенный алгоритм выравнивания приводит к реализации следующих действий:

1. Обозначения для терминов из 5г, совпадающие с обозначениями для терминов из 52, заменяются на новые: Л1 на Л4, а! на а\, а\ на а\, а1 на а\, а\ на А2 на Л5, а? на а|, а2 на а2.

2. Используя заранее установленные соответствия между терминам разных онтологий, вводятся дополнительные обозначения для терминов из - это а 2 и а 3, а также а3! и а2 - для терминов из 52, которые связаны отношением подобия. На рис. 5

Л4 Задачи обучения

«Í Применять методы структурной декомпозиции программы

al Описать механизмы передачи параметров

«i Указать свойства присущие хорошим алгоритмам

А Описать стратегии полезные при отладке

л5 Курсы, в рамках которых решаются задачи обучения

а\ РИ. Основные конструкции программирования

«3 РЕ2. Алгоритмы решения задач

А3 Приобретаемые навыки

ala3 Высокоуровневое понимание систем в целом

а\,а\ Понимание влияния теории на практику

А1 Характеристики выпускников информатики

а! Системный взгляд на дисциплину

ai Понимание связи теории и практики

А2 Требования к обладанию некоторым качеством

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

al af Высокоуровневое понимание систем в целом

ala¡ Понимание влияния теории на практику

Рис. 5. Переобозначенные элементы глоссариев 3. С учётом новых обозначений перестраиваются классификационные цепочки. На рис. 6 показаны перестроенные классификационные цепочки, 5т - «Задачи обучения»

а*а1 а|а| ata! 4 5 а4а2

а?а£а1 а1аЗа2 а2а4а2 а2а4а3

а} al а1а2 а2а3

aWÍ a\al

Рис. 6. Перестроенные классификационные цепочки

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

— «Задачи обучения»

xs A2 Л3 A* As A

S 4 4 4 4

Sai al «?

Sai ai

Sal «?

Sai a?

SaUl a?

Safaf S

Sa$ai a?

Saja'í S

Sala| S

Saia¡ S

Safabaf S

Safala2 S

Salatal S

Sa\aia$ S

xs A1 A2 Л3 Д

S alai

Sal alaj «í

Sa\

Salal <5

5а|а| S

tfafa? S

Sal7a* S

¿aja3 <5

Рис. 7. Табличные представления для вьфовненных онтологий

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

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

В диссертационном исследовании проводилось экспериментальное моделирование процесса непосредственного объединения двух независимых онтологий: 5! - «Задачи обучения» и 52 - «Характеристики выпускников информатики». После процедуры выравнивания онтологий табличные представления могут быть сведены в единую таблицу. Такая таблица внутри проектируемого агента будет представлять собой программный образ для единой онтологии, составленной из и Б2.

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

ОНТОЛОГИИ, полученной ИЗ Si и S2.

X, A1 A2 A3 A1 A5

S a\,a\ aj, a|,a|,aj

Sa\ ai aî

fiaj a!

fia| al

8a% a|

fiajaj ai ai

Sa\a\ fi

Sajat al ai

S

fia|a| S

fiajal s

5a}a|a? s

fiaja|a| s

Saja^al s

fia|aja| s

fia} al al ai

Sa\ al al

Sa\a\ s

Sa{a 2 s

Sa\al s

Sa\al s

Sa\a\ s

Рис. 8. Табличное представление для единой онтологии

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

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

Рассмотрим вопрос: «Как решаемые задачи обучения сказываются на характеристиках выпускников информатики?».

По правилам грамматики инициализируется первый вывод всех терминальных цепочек, префикс которых описывает решаемые задачи обучения. Из префиксов («Применять методы структурной декомпозиции программы» и «Указать свойства присущие хорошим алгоритмам») и а^а* («Описать механизм передачи параметров»

и «Описать стратегии полезные при отладке») выводятся цепочки: а^а^а^, а*а*а1,

а2а4а2> а2а4а3-

По правилам грамматики инициализируется второй вывод всех терминальных цепочек, префикс которых описывает характеристики выпускников информатики. Из префиксов а\ (Системный взгляд на дисциплину) и (Понимание связи теории и практики) выводятся цепочки: я^я?, а}а|, а}аа^Яз, а\а1.

На основе совпадения целевых состояний (а|, а?, а|, а|) для разных наборов цепочек, которые получены в результате двух выводов, используя обратный вывод можно установить связь с их начальными состояниями:

- Задачи обучения а* и а* связаны с характеристикой выпускников а{.

- Задачи обучения я| и а* связаны с характеристикой выпускников а

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

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

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

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

2. Предложена схема грамматики для представления семейства иерархий объектов и категорий предметной области. Структурные особенности каждой отдельной иерархии проявляются в правилах вычисления правых частей подстановок грамматики, вычисляемых системой отображений, которая имеет табличное представление. (С. 38-66).

3. Разработан алгоритм автоматического выравнивания и непосредственного объединения онтологий, представленных с использованием грамматического подхода. Использование грамматики для представления иерархии позволяет отделить синтаксис иерархии от её семантики, вынести представление иерархии, то есть синтаксис, на более высокий уровень абстракции, а семантику определять в качестве входных данных. Такой подход к представлению иерархий позволяет совершить переход к проектированию простых алгоритмов автоматического выравнивания и непосредственного объединения онтологий. (С. 107-120).

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1. Шабалин А.Г. Использование порождающих грамматик для описания классификационных структур // Журнал «Информатизация и связь», № 3, 2011. - С. 20-22.

2. Шабалин А.Г. Формализованная модель предметной онтологии на основе порождающей грамматики. Создание и использование // Журнал «Информатизация и связь», № 5, 2012. - С. 64-66.

Публикации в других изданиях

3. Шабалин А.Г. Применение расширенной онтологии для комбинирования распределённых данных // Сборник трудов Всероссийской научной школы-семинара молодых учёных, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки». - Таганрог: изд-во ТТИ ЮФУ, 2010.-С. 115-120.

4. Шабалин А.Г. Использование порождающих грамматик для описания иерархических отношений // Сборник трудов IX Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление». - Таганрог: изд-во ТТИ ЮФУ, 2011. -С. 244-248.

5. Шабалин А.Г. Проблемы алгебраических методов представления иерархии объектов // Сборник трудов IX Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление». - Таганрог: изд-во ТТИ ЮФУ, 2011.-С. 257-261.

6. Шабалин А.Г. Об оптимизации машинного представления деревьев // Сборник трудов Всероссийской научной школы-семинара молодых учёных, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки». - Таганрог: изд-во ТТИ ЮФУ, 2012. - С. 65-71.

7. Шабалин А.Г. Формальный подход к представлению предметных онтологий с использованием порождающей грамматики // Сборник трудов Всероссийской научной школы-семинара молодых учёных, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки». - Таганрог: изд-во ТТИ ЮФУ, 2012. - С. 71-76.

ВГАОУ ВПО «Южный федеральный университет»

347928, Ростовская область г. Таганрог, пер. Некрасовский 44.

МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

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

Шабалин Александр Георгиевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ГРАММАТИЧЕСКОГО ПОДХОДА ДЛЯ РЕШЕНИЯ ЗАДАЧИ АВТОМАТИЧЕСКОГО ВЫРАВНИВАНИЯ И ОБЪЕДИНЕНИЯ ОНТОЛОГИЙ ПРЕДМЕТНЫХ ОБЛАСТЕЙ

Специальность: 05.13.17 — «Теоретические основы информатики»

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

Научный руководитель: д. т. н., проф. Вишняков Ю.М.

Таганрог 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.............................................................................................................5

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ СОЕДИНЕНИЯ ОНТОЛОГИЙ, ПОСТАНОВКА ЗАДАЧИ ПРЕДСТАВЛЕНИЯ СЕМЕЙСТВА ИЕРАРХИЙ С ИСПОЛЬЗОВАНИЕМ МЕХАНИЗМА ПОРОЖДАЮЩИХ ГРАММАТИК.................................................................14

1.1. Основные понятия и терминология...................................................14

1.2. Обзор основных методов выравнивания и объединения онтологий............................................................................................................18

1.2.1. Методология ONIONS.............................................................................21

1.2.2. Метод FCA-Merge....................................................................................22

1.2.2. Инструментальные средства PROMPT, OntoMerge, OntoMorph, Chimaera..............................................................................................................23

1.3. Использование формальной системы для представления иерархических структур...................................................................................25

1.4. Выбор математического инструментария для представления семейства иерархий..........................................................................................29

1.5. Создание онтологии предметной области с использованием

грамматического подхода..............................................................................31

1.6. Выводы.....................................................................................................35

ГЛАВА 2. ПРЕДСТАВЛЕНИЕ СЕМЕЙСТВА ИЕРАРХИЙ НА ОСНОВЕ МЕХАНИЗМА ПОРОЖДАЮЩИХ ГРАММАТИК....................................37

2.1. Общая модель порождающей грамматики и интерпретация её

элементов............................................................................................................38

2.2. Разработка схемы грамматики для вывода семейства иерархий40

2.2.1 Грамматика без учета классификационных категорий................40

2.2.2 Грамматика с учетом классификационных категорий.................47

2.2.3 Грамматика для представления семейства иерархических структур...............................................................................................................54

2.3. Табличное представление системы отображений для вычисления

правых частей подстановок............................................................................59

2.3.1 Система отображений для грамматики без учета

классификационных категорий.....................................................................59

2.3.2 Система отображений для грамматики с учетом

классификационных категорий.....................................................................62

2.3.3 Система отображений для представления семейства иерархий .64

2.4. Семантическая непротиворечивость, адекватность и разрешимость грамматики для представления семейства иерархий.....66

2.4.1. Непротиворечивость.........................................................................67

2.4.2. Адекватность......................................................................................68

2.4.3. Разрешимость.....................................................................................69

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

2.5.1 Оценка пространственной эффективности.........................................71

2.5.2 Оценка временной эффективности.......................................................79

2.3 Выводы...........................................................................................................83

ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МЕТОДОВ АВТОМАТИЧЕСКОГО ВЫРАВНИВАНИЯ И ОБЪЕДИНЕНИЯ ОНТОЛОГИЙ С ИСПОЛЬЗОВАНИЕМ ГРАММАТИЧЕСКОГО ПОДХОДА.............................................................................................................86

3.1. Структура экспериментальной модели.............................................86

3.2. Экспериментальное исследование....................................................92

3.2.1. Кодирование онтологии...................................................................92

3.2.2. Использование онтологии.............................................................101

3.2.3. Автоматическое выравнивание...................................................107

3.2.4. Автоматическое объединение......................................................117

3.3. Выводы...................................................................................................120

ЗАКЛЮЧЕНИЕ.................................................................................................122

ЛИТЕРАТУРА....................................................................................................125

ПРИЛОЖЕНИЯ.................................................................................................134

ПРИЛОЖЕНИЕ 1..............................................................................................135

ПРИЛОЖЕНИЕ 2..............................................................................................142

ВВЕДЕНИЕ

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

Термин «онтология», применительно к компьютерным наукам, впервые появился в контексте решения задач взаимодействия интеллектуальных систем между собой и с человеком [2]. Идея состояла в том, чтобы позволить интеллектуальным системам обмениваться между собой заложенными в них знаниями о решаемых задачах. Если внутри интеллектуальной системы знания могут быть закодированы как угодно, то для обмена этими знаниями с другой интеллектуальной системой необходимо предоставить описание этих знаний [60]. Онтологии отводится роль определения требуемых описаний для того, чтобы существовала возможность обмена информацией. Поэтому онтологии как системы представления знаний должны рассматриваться именно с точки зрения их сетевой специализации, что проявляется в форме взаимодействия разных онтологий друг с другом. После размещения в сети они должны быть повторно использованы для расширения, дополнения или верификации новых онтологий. Главные отличительные положительные свойства онтологий как систем хранения знаний в сравнении с другими аналогичными системами

проявляются при их совместном использовании, когда удаётся учесть взаимосвязи независимых онтологий [49].

На практике для совместного использования двух онтологий нужно уметь их объединять. Накопленный опыт онтологического инжиниринга в различных областях науки показывает, что если онтологии, которые нужно слить воедино, строились вне определённой базовой онтологии, трудоёмкость их объединения будет достаточно велика. Все известные методы и инструментальные средства объединения онтологий являются более или менее интеллектуальными помощниками человека-эксперта [44]. Поэтому на сегодняшний день слияние онтологий обычно проводится в ручном или полуавтоматическом режиме.

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

Онтологический инжиниринг имеет весьма большую историю исследований в работах зарубежных авторов Gruber, Berners-Lee, Noy, Gomez-Perez, Ushold, Gruninger, Guarino [1, 2, 6, 9, 10], среди русскоязычных

публикаций на эту тему необходимо выделить работы Гавриловой, Доброва, Овдей, Хорошевского, Гурьяновой, Ефименко, Кудрявцева, Попова, Лапшина [26, 35, 41, 44, 45, 56, 79]. На базе отечественных ВУЗов проводятся ежегодные конференций на тему онтологического моделирования и инженерии знаний: «Конференция по искусственному интеллекту» (КИИ), «ЗНАНИЯ-ОНТОЛОГИИ-ТЕОРИЯ» (ЗОНТ), «Управление знаниями и технологиями семантического веба» (КМЗ1^, «Научно-практическая конференция Инжиниринг предприятий и управление знаниями» (ИП&УЗ).

В разных областях информатики проводятся исследования на тему автоматического или инструментально поддерживаемого объединения онтологий (или иерархии классов, или объектно-ориентированных схем, или схем баз данных - определённая терминология изменяется в зависимости от области применения) [79]. Создание систем, основанных на онтологиях, требует методов и инструментов, как для построения онтологий, так и для целого ряда задач, связанных с их совместным использованием. Совместное использование онтологий достигается в процессе их слияния. Слияние онтологий может рассматриваться как состоящее из трёх последовательных этапов, каждое из которых использует результаты предыдущего - это отображение онтологий, т.е. установление подобных понятий, экземпляров, отношений; их выравнивание, т.е. сохранение в онтологиях информации о выявленных подобиях; и непосредственное объединение онтологий, т.е. соединение друг с другом компонентов двух онтологий.

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

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

При изучении вопросов представления онтологических знаний можно обратиться к хорошо известной теории формальных систем и порождающих грамматик [3, 4, 5, 31, 34, 53, 57, 77, 80, 97], которая имеет развитый математический аппарат. Применить грамматики для представления онтологических знаний имеет смысл по той причине, что это позволяет в дальнейшем получать полезные свойства при решении задачи их автоматического выравнивания и объединения. Суть такого подхода заключается в том, что использование формальной системы для представления абстрактной иерархии, позволяет отделить её предполагаемый синтаксис от возможной семантики. Это позволяет вывести алгоритм описания каждой отдельной иерархии на более абстрактный уровень, где конкретная семантика этой иерархии представлена в виде входных данных. Такой подход, в конечном счёте, приводит к созданию алгоритмов автоматического соединения онтологий, имеющих представление согласно описанной схеме.

Существуют подходы, которые позволяют представлять онтологию без разработки фреймовой структуры, которая основана на подробной детализации классов, слотов, доменов и т.д. [101, 102]. Такие подходы основаны на идее структуризации онтологических знаний в виде классификационных цепочек для понятий предметной области и применении грамматического подхода при их совместном использовании. Можно сделать вывод, что онтологию предметной области допустимо описывать без использования сложных языковых конструкций при определении диаграмм классификаций, композиционных схем для состава классов онтологии, схем взаимосвязей, диаграмм состояния объектов, таблиц логических аксиом, таблиц формул и т.д. Все эти конструкции обладают разными положительными свойствами для решения определённого круга задач, вместе

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

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

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

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

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

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

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

1. Провести анализ существующих методов и инструментальных средств слияния онтологий.

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

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

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

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

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

Научная новизна работы.

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