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

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

Shcherbak says: Это интересно и познавательно! Читаем ))

Еще чуть-чуть об экстенсивном развитии онтологических структур Читать ))

УДК 519.178, 519.711
Павлов Д.А.

Введение

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

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

Учитывая складывающиеся тенденции в применении онтологий, исследуемые онтологии по-умолчанию являются нечеткими.

Связанные задачи

Наиболее близкой задачей, к той, которая описывается в данной статье, является автоматическая локализация и устранение противоречивости статической онтологии (Prt_s).
Среди важных достижений в данном направлении необходимо отметить: обобщенные подходы к разрешению противоречивости [1], подходы анализа работы блоков логического вывода
(БЛВ) [2,3]. Первые решают комплексную задачу выявления причин возникновения противоречивости и поиска соответствующего шаблона решения, в то время как вторые демонстрируют цепочку фактов, приведших БЛВ к выводу о противоречивости. Наиболее полно достижения в направлении анализа БЛВ отражены в разработке SWOOP [4]. Не смотря на значительные достигнутые результаты этих работ, в них не уделяется должного внимания непосредственно процессу развития онтологии, являющегося корневым элементом появления противоречивости. Данная статья рассматривает вопросы статической противоречивости нечеткой онтологии Prt_sf, а также динамической противоречивость Prt_d.

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

В статье затрагиваются вопросы модульных онтологий, которые в значительной степени освещаются в [6,7], а также несколько более близкого понятия: экстенсивного развития онтологий [8].

Данная работа является логическим продолжением ряда работ посвященных интенсивному и экстенсивному развитию онтологических структур [8,9] и принимает все определения и соглашения принятые там.

Постановка задачи

Пусть существует некоторая онтология Ont наблюдаемая в условиях интенсивного развития

где Ont_i - онтология в момент времени t_i, характеризующий момент создания данной онтологии, I конечный неотрицательный номер версии Ont.

Известно, что развитие dev(Ont_i, Ont_i+1) является результатом совместной работы N различных, возможно не связанных между собой групп, занимающихся поддержкой данной онтологии.

Тогда, непосредственно переход Ont_i -> Ont_i+1 является простейшим элементом, на базе которого можно объективно оценить результирующий вклад всех N групп.

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

Необходимо:

- проанализировать процесс возникновения Prt_sf и Prt_d, оценить их влияние на общую семантику онтологии;

- разработать методы и алгоритмы автоматической локализации и устранения Prt_sf и Prt_d;

Ограничения и требования:

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

- выразительность онтологий ограничим дескриптивными логиками (ДЛ) с конечным логическим выводом.

Основные понятия:

(Четкая) онтология Ont есть конечный набор триплетов <s,p,o> , где s – субъект, p – предикат и o – объект.

Нечеткая онтология Ont_f есть конечный набор триплетов [<s,p,o>,m], для которых определена функция принадлежности m, характеризующая степень существования данного триплета. При m = 1, триплет считается всегда истинным, при m=0 – незаданным.

Таким образом, всякая Ont является частным случаем Ont_f.

Для ДЛ любого класса противоречивость есть существования объекта эквивалентного пустому множеству.

Для класса логик, в которых определено понятие отрицания предиката (ØP), можно утверждать следующее: для некоторых предикатов pÎP, где P полный набор
предикатов онтологии, существует ÎP такое, что <s,p,o>Ç<s, ,o>
= Æ для всех s и o, или другими словами предикат-отрицание. Например, равен – неравен, пересекается – не пересекается.

Противоречивость Prt_s – есть свойство онтологии, характеризующее онтологию, в которую одновременно входят по крайне мере два утверждения, <s,p,o> и <s, ,o>.

Противоречивость нечеткая Prt_sf – есть свойство онтологии, характеризующее онтологию, в которую одновременно входят по крайне мере два утверждения,
[<s,p,o>,m₁], [<s, ,o>,m₂], где m₁ , m₂ ³ g, где g – настраиваемый порог достоверности.

Отметим, что для четкого пространства состояний онтологии g равен 1.

Динамическая противоречивость Prt_d – есть свойство развития dev(Ont_x, Ont_y), описывающая состояние при котором существует хотя бы один такой набор [<s,p,o>,m₁] Î Ont_x,
[<s, ,o>,m₂] Î Ont_y и m₁ , m₂ ³ g, при чем Ont_x, Ont_y по-отдельности непротиворечивы.

Блок логического вывода (БЛВ, reasoner) – подсистема логического вывода, позволяющая проверить истинность, ложность либо неопределенность некоторой аксиомы в рамках заданной онтологии. Также БЛВ зачастую используются для построения полного набора аксиом на базе существующей онтологии.

Сложность логического вывода. Говорить о сложности логического вывода из онтологической базы знаний в общем виде не возможно, в виду того, что различная степень выразительности приводит к значительным различиям в сложности. Сложность может варьироваться от полиномиальной до невычисляемой. Учитывая принятые ограничения
на выразительность, а также существующие реализации БЛВ, а также мы рассматриваем сложность ДЛ SHIF_f [5], SHOIN [10] и sROIQ с простыми типами [11]. Важно
отметить, что выбранные ДЛ достаточно выразительны для создания противоречивых утверждений.

Семантика противоречивой онтологии

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

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

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

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

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

1. Вследствие устранения существовавшей ошибки.

2. Вследствие ошибки ввода.

3. Вследствие несоответствия понятий.

4. Вследствие ошибки в цепи логического вывода.

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

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

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

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

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

Избыточность и неполнота в условиях противоречивости

Всякое изменение онтологии сопровождается возникновением свойств неполноты Npl и избыточности Iz [12].

Рассмотрим простейший случай возникновения динамической противоречивости. Пусть существует следующий набор аксиом, формирующий онтологию Ont₁: заданы классы A и В, при чем A несовместен с B, и задан класс C, являющийся подклассом А. Исходя из правил логического вывода, B и C несовместны. Пусть произошло развитие онтологии до Ont₂, в которой класс С стал подклассом B, тогда C теперь несовместен с A. Имеем два набора придающие развитию dev(Ont₁, Ont₂)свойство динамической противоречивости Prt_d:

и;

и .

Очевидно, что элементы, образующие пары противоречивости, формируют также и попарное возникновение неполноты и избыточности.

С₁ = {,}

C₂ = {,}

или в нормализованном виде

С₁ = {,,,}

C₂ = {,,,}

Npl_С = 1, Iz_C = 1

Важно отметить, что динамическая противоречивость, в отличие от статической, сопровождается
одновременным присутствием свойств Npl и Iz.

Теорема 1. Всякое развитие dev(Ont_x, Ont_y), обладающее свойством динамической противоречивости, обладает свойствами неполноты и избыточности.

Доказательство теоремы 1. Пусть существует свойство Prt_d для развития dev(Ont₁,Ont₂), тогда по определению 3 будет некоторый набор [<s,p,o>,m₁] Î Ont₁, [<s, ,o>,m₂] Î Ont₂. Предположим что для данного развития dev Npl = 0, тогда в онтологии Ont₂ должно присутствовать утверждение [<s,p,o>,m₁] Î Ont₂ – но тогда Ont₂ обладает свойством статической противоречивости Prt_s, что противоречит определению 3. Следовательно, Npl ¹ 0. Аналогично доказывается присутствие Iz.

Отметим, что обратная связь свойств отсутствует.

Оценка присутствия динамической противоречивости Prt_d в условиях перехода dev(Ont_x, Ont_y) сопряжена с интеграцией версий Ont_x, Ont_y, что не всегда приемлемо.

Например, некоторая онтология Ont состоит из двух крупных подразделов Ont₁ и Ont₂, которые разрабатываются. Пусть Ont₁ подвергся сильным изменениям, в то время как Ont₂ изменился поверхностно. Важно оценить при заведомой конфликтности одного подраздела плавность перехода другого. При чем явно эти разделы не отделимы. Учитывая выбранный уровень выразительности онтологий, скорость работы БЛВ экспоненциально зависит от размеров входных данных [10,11].
В связи с этим эффективным решением является автоматическое разбиение онтологии на модули, аналогичные тем которые формируются при экстенсивном развитии. Для независимой оценки Ont₂ необходимо, чтобы выполнялось условие nezav(Ont₂, Ont₁), таким образом, необходимо привести онтологию к виду аддитивного экстенсивного развития [8].

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

Аксиома. Некоторый элемент A онтологии Ont принадлежит ядру Ont_core , тогда и только тогда, когда fun(Iz_A, Npl_A)<a, где Iz_A избыточность элемента при переходе dev, Npl_A - неполнота, a - настраиваемый порог.

Порог a может быть скорректирован в соответствии с набором отчетов {Rep}. Например, a = min(a_i) при необходимости выделения наименьшего и наиболее точного
ядра, либо a = (åa_i)/|Rep| при необходимости выявления наибольших всплесков противоречивости.

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

Также разрезание может привести к «выкалыванию» элементов подразделов. Например, в слабо измененном ядре некоторый элемент сильно изменился, но не повлек за собой изменений связанных с ним элементов. Для уменьшения такого влияния введем порог S на размер графа перемещаемого в Ont_env, где S минимальное число связных
элементов. Увеличивая S – оператор будет требовать большей независимости подразделов онтологии.

Кривая эффективности порога связности S (Рисунок 1) имеет 2 значимые точки S₁ и S₂, где S₁ – наиболее полное разделение, а S₂ – порог, после которого онтология остается единым целым.

Рисунок 1 - Кривая эффективности порога связности

Автоматическое устранение динамической противоречивости

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

Рисунок 2 - Алгоритм итеративного устранения динамической противоречивости

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

Для этого блок проверки адекватности включает следующие функции:

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

2. Механизм сравнения отчетов разработчиков с полученными значениями критериев неполноты и избыточности;

3. Блок нечеткого логического вывода о присутствии ошибки в развитии.

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

4. Механизм разрезания онтологии на Ont_core и Ont_env;

5. Оценка статической целостности Ont_core.

6. Приведение в состояние целостности Ont_core.

7. Механизм последовательного подбора несовместных аксиом из Ont_env;

8. Блок логического вывода, подтверждающий несовместность.

Далее после установления противоречивой аксиомы используется:

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

10. Фаззификационный блок, уменьшающий степень противоречивости.

Вся система тесно взаимодействует с интерфейсом управления оператора онтологии.

Рассмотрим подробнее каждый пункт.

Пункт 1 детально рассмотрен в [12], суть которого заключается в расчете двух числовых значений критериев адекватности Npl(A₁,A₂) и Iz(A₁,A₂) для каждого элемента A₁ входящего в версию онтологии Ont₁ и соответствующего элементу A₂ входящего в версию онтологии Ont₂, где dev(Ont₁, Ont₂) = true. Полученный набор значений позволяет перейти из пространства групп в метрическое пространство, что дает возможность использовать более мощный математический аппарат.

Пункт 2 сравнивает расчетные средние значения Npl и Iz с обобщенными значениями глубины изменения, предоставляемыми с новой версией онтологии.

k = max[max[avg(Iz), avg(Npl)] – ch(Rep), 0] (1)

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

k = max[max[avg(Iz), avg(Npl)] – def_ch, 0] (2)

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

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

Res = min[m(x_i)]|i=1,N, m(x_i) = 1- k_i. (3)

Результат Res является переменной функции решения об автоматическом запуске процессов локализации и устранения противоречивости (Рисунок 3)

, (4)

где a является настраиваемым порогом противоречивости.

3 - Функция принадлежности онтологии классу противоречивых

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

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

Также данный этап может выполняться в полностью автоматическом режиме.

Проверка статической целостности 5 в Ont_core осуществляется путем проверки всех аксиом онтологии на предмет равенства пустому множеству, при помощи существующих БЛВ.

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

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

1) аксиомы, входящие в Ont_env, которые составлены из предикатов имеющих отрицание, сортируются по значениям критериев Npl и Iz;

2) в отдельном списке они сортируются по близости к ядру по принципу, если для аксиомы A<s,p,o> s или o входят в ядро, то близость равна Near_core(А) = 1, если s или o входят в аксиому A₁ близость которой уже известна Near_core(А₁) = n, то Near_core(А) = n+1, в случаях конфликтов выбирается наименьшая близость; таким образом, чем меньше значение близости, тем меньше аксиом нужно добавить, чтобы необходимая аксиома стала связна с ядром;

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

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

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

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

Выбор аксиомы А, подлежащей «ослаблению» осуществляется с помощью следующей эвристики:

1) АÎOnt_Env

2) минимальное число объектов Obj должно описываться данной аксиомой A, N®min, A Î Obj_i | i=1,N,

3) если одна и та же аксиома входит в разные цепи противоречивости, то она является предпочтительной для «ослабления».

Ослабление аксиом производится по следующей формуле

, (5)

где m₀ и m₁ значения функции принадлежности существования ослабляемой аксиомы в версиях 0 и 1 соотвественно.

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

Прикладное решение задач

Рассмотрим процесс работы предложенных решений на прикладных объектах.

Исследование производилось на онтологии информационных потоков предприятия Ont_Inf, разработанной на языке OWL[14] с уровнем выразительности DL с использованием нечетких предикатов. Данная онтология являлась экстенсивным развитием онтологии SWEET[15], которая в свою очередь является экстенсивным расширением базовой онтологии OWL.

Используя синтаксис принятый в [9],

imp(Ont_Inf, {Ont_OwlDL, Ont_Sweet})=1 и Struct = <{ Ont_Inf, Ont_OwlDL, Ont_Sweet }, {imp(Ont_Inf, {Ont_OwlDL, Ont_Sweet})}>.

В ходе исследования изменению подлежали две составляющие онтологической структуры Ont_Sweet, а также Ont_Inf

D_Inf = {<Ont_Infi, t_i>_i}|i=0..3, D_Sweet = {<Ont_Sweetj, t_j>_j}|j=0..2

Отметим, что развитие D_Inf происходило в условиях зависящих от данного исследования, в то время как D_Sweet – полностью независимое развитие.

Данное развитие является гибридным интенсивно-экстенсивным при постоянной структуре импортов.

, MRI(t)=MRI=const,

Онтологии Ont_OwlDL и Ont_Sweet являются четкими, в то время как Ont_Inf – нечеткая.

4 - Обобщенная схема онтологической структуры Struct

Рассмотрим переход dev(Ont_Inf0, Ont_Inf1) который сопровождался значительным уточнением понятий бухгалтерии, а также незначительными коррективами в области кадровой информации. Это было отмечено в отчетах разработчиков как Rep_Skl = {ch = 0, imp = 0}, Rep_Buh = {ch = 0,5, imp = 0,8}, Rep_Kadr = {ch = 0,1, imp = 0,1}.

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

Одним из важнейших изменений в разделе Buh фактически было переопределение понятий «дебет» и «кредит». В версии 0 данные два понятия состояли в отношении «несовместности»,
в то время как в версии 1 данное отношение было удалено. Таким образом, появилась возможность одновременно у одного объекта указать, что он является «дебетом» для одного объекта хозяйственной деятельности и «кредитом» для другой. Это, во-первых, уменьшило количество фактически дублирующихся объектов, а во-вторых, увеличило семантическиесвязи между объектами хозяйственной деятельности. Таким образом, в Ont_Inf1 появились аксиомы, которые в Ont_Inf0 были бы заведомо противоречивыми.

Проследим работу системы проверки адекватности.

При расчете значений критериев Iz и Npl получены следующие данные:

Таблица 1 - Значения критериев неполноты и избыточности для развития Ont_Inf

Имя онтологии	Критерий	max	Avg
OntInf	Iz	1	0,2
	Npl	1	0,4
Buh	Iz	1	0,23
	Npl	1	0,6
Skl	Iz	0,3	0,03
	Npl	0,2	0,01
Kadr	Iz	1	0,19
	Npl	0,2	0,01

Сравним полученные значения с отчетами Rep по формуле (1):

k_Buh = 0.1, k_Skl = 0.03, k_Kadr = 0.09.

Тогда, блок логического вывода над результатами сравнения проверяет, принадлежит ли данное решение к классу непротиворечивых (3,4):

Prt (max[k_i]) => [0,1]

В данном развитии принадлежность к классу непротиворечивых решений 0.7 (при a =0.66).

В автоматическом режиме решение принимается, что версия онтологии применима.

Выберем из интерфейса оператора решение о дальнейшем анализе развития.

При разрезании онтологии получаем связное ядро Ont_core и набор аксиом образующий Ont_env. Ont_core целостна.

Переходим к подбору потенциально противоречивых аксиом. Первой аксиомой в очереди является аксиома A = <”дебет”, “disjointWith”, “кредит”>. Для простоты примера выберем значения переменной W = 0.

При проверке выявляем, что Ont_Core+A – противоречива.

Цепи противоречивости включают следующие аксиомы:

{А, <obj1, isA, “дебет”>, <obj2, isA, “кредит”>, <obj1, “equals”, obj2>},

{А, <obj3, isA, “дебет”>, <obj4, isA, “кредит”>, <obj3, “equals”, obj4>},

{А, <obj5, isA, “дебет”>, <obj6, isA, “кредит”>, <obj5, “equals”, obj6>}.

Исходя из эвристик блока 10 аксиома А подлежит ослаблению. [A`,0.5]

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

Рассмотрим переход dev(Ont_Sweet0, Ont_Sweet1) который сопровождался уточнениями и исправлениями в ряде модулей. Так как данная
онтология является внешней, то отчеты разработчиков не поставлялись при ее изменении.

Повторим операции анализа

Таблица 2 - Значения критериев неполноты и избыточности для развития Ont_Sweet

Имя онтологии	Критерий	max	Avg
OntSweet	Iz	1	0,14
	Npl	1	0,09
Units	Iz	1	0,16
	Npl	1	0,3
Human Activities	Iz	0	0
	Npl	0	0
Other	Iz	1	0,15
	Npl	1	0,04

Принимая значениями по умолчанию def_ch = 0 рассчитаем значения k. k_Units = 0.3, k_HA = 0, k_Other = 0,15.(

В данном развитии принадлежность к классу непротиворечивых решений 0 (при a =0.66). Таким образом, автоматически переходим к фазе выявления противоречивости.

Разрезаем онтологию на Ont_Core и Ont_Env. При первом разрезании в Ont_Env содержится ряд одиночных аксиом. Повышаем порог s до 1. После этого получаем Ont_Env, состоящую из 3 модулей: 1 – степени в единицах измерений, 2 – изменения в данных о биосфере, 3 – изменения данных об элементах Земли.

nAd(Ont_Core) = 1. Это происходит в связи с тем, что поменялся ряд функциональных значений свойств некоторых объектов. Например, поменялся ряд численных и строковых
значений. Разрешение этого конфликта выполняется на уровне интерфейса оператора, путем использования в качестве истинных значений второй версии.

Итак, имеем модифицированное целостное ядро Ont`_Core.

{TODO look SWEET}

Рассмотрим развитие Ont_Inf в аспекте развития dev(Ont_Sweet0, Ont_Sweet1), а также в аспекте скорректированного развития dev(Ont_Sweet0, Ont`_Sweet).

Наблюдается значительное снижение значений критериев неадекватности.

Выводы

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

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

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

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

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

1. Peter Haase, Frank van Harmelen, Zhisheng Huang, Heiner Stuckenschmidt, and York Sure A Framework for Handling Inconsistency in Changing Ontologies // Lecture Notes
in Computer Science, Springer-Verlag, Germany, 2005, pp. 353-367

2. Bijan Parsia and Evren Sirin and Aditya Kalyanpur, Debugging owl ontologies //The 14th international world wide web conference (www2005), Chiba, Japan, May
2005.

3. Wang, H. Harridge, M. Rector, A. Drummond, N. Seidenberg, J. Debugging OWL-DL Ontologies: A Heuristic Approach // Lecture Notes in Computer Science, Springer-Verlag,
Germany, 2005, pp. 745-757

4. Aditya Kalyanpur, Bijan Parsia, James Hendler A tool for working with web ontologies// In proceedings of the international journal on semantic web and information systems, vol. 1, no. 1, jan - march, 2005

5. Umberto Straccia, A Fuzzy Description Logic for the Semantic Web // Fuzzy Logic and the Semantic Web, Elsevier, 2006, pp. 73-90

6. Stuckenschmidt, H. Klein, M. Integrity and Change in Modular Ontologies // International Joint Conference on Artificial Intelligence, USA, 2003, Vol. 18,
pp. 900-908

7. Fikes, R. Farquhar, A. Rice, J. Tools for Assembling Modular Ontologies in Ontolingua // Proceedings Of The National Conference on Artificial
Intelligence, USA, 1997, N 14, pp. 436-441

8. Павлов Д. Экстенсивное развитие онтологических структур // «Бионика интеллекта», Харьков, №2(63), 2005 г. С 91-97.

9. Кучеренко Е., Павлов Д. Модель интенсивного развития онтологий // “АСУ и приборы автоматики”, Харьков, №135, 2006 г. С. 4-12

10. Stephan Tobies. Complexity results and practical algorithms for logics in Knowledge Representation. PhD Thesis, LuFG Theoretical Computer Science, RWTH-Aachen,
Germany, 2001, 173 p.

11. I Horrocks, O Kutz, U Sattler The even more irresistible SROIQ // Principles of Knowledge Representation and Reasoning (KR'2006). http://www.cs.man.ac.uk/~okutz/sroiq-TR.pdf

12. Кучеренко Е., Павлов Д. О проблемах выявления неполноты и избыточности информации в онтологическом пространстве // Прикладная радиоэлектроника, Т.4, №2,
Харьков, 2005 г., С. 175-179

13. SOFT COMPUTING

14. OWL (W3C)

15. SWEET

УДК 519.71

Кучеренко Е.И., Павлов Д.А.

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

About problems of displaying of incompleteness and superfluity of subject of inquiry in ontological spaces

Ye.I. Kucherenko, D.A. Pavlov

There has spotted problems of appearance of elements of incompleteness and superfluity of ontologies during changes or development of their versions. There were suggested criteria and algorithms for displaying and localization of these properties. There were determined mathematical and logical relations between incompleteness and superfluity. Listed recommendations how to use these theoretical results in practice.

Введение

В настоящее время получили широкое распространение распределенные системы обработки данных и управления. В связи с чем, начали значительно развиваться идеи унификации представления информации. Одной из самых важных и разрабатываемых идей является использование онтологий. Сегодня уже предложен ряд высоко специфицированных языков представления онтологической информации, такие как OWL, OIL и DAML [1]. В основе всех указанных языков заложены возможности распределения информации, то есть написание отдельных частей онтологии и синхронизация их на основе механизмов ссылок.

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

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

1. Постановка задачи

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

Необходимо:

- предложить и обосновать формальные критерии выявления неполноты () онтологической информации:

(1)

где - версия в момент времени , - пространство времени, в котором существует альтернативная версия онтологии;

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

(2)

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

Для снижения сложности решения принять ограничения на входящую информацию типа:

- поступающие данные предоставлены строго в онтологическом виде;

- в системе должны храниться все предыдущие версии онтологий;

- при изменении версии онтологии специалист должен иметь возможность определить степень подобия версий.

2. Формальное представление неполноты и избыточности

Существует множество случаев, когда в обрабатываемой информации присутствует свойство неполноты (1).

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

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

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

Тогда к избыточности относятся сведения, не имеющие отношения к существу вопроса, и сведения в объеме, превышающем возможности своевременной их обработки [7].

Утверждение 1. Избыточность (2) представим как обратное подобие неполноты (1).

Справедливость утверждения 1 следует из определений (1) и (2).

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

Уточним основное понятие, используемое в данной работе [8].

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

Основными элементами онтологии являются:

- классы – обобщенные категории вещей, используемые в предметной области;

- свойства – атрибуты, которые могут иметь представители классов.

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

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

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

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

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

Пусть заданы состояния некоторой онтологии или онтологии:

(3)

где – онтология в момент времени , – j-й класс онтологии,

(4)

где – онтология в момент времени ,– j-й класс онтологии, причем классы онтологии и подлежат сравнению на логическом уровне.

Утверждение 2. Онтология (4) является неполной относительно онтологии (3), если соответствующие в них классы обладают свойствами неполноты.

Утверждение 3. Онтология (4) является избыточной относительно онтологии (3), если соответствующие в них классы обладают свойствами избыточности.

Утверждения 2 и 3 справедливы в контексте решаемых задач, если принять истинность замечания 1.

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

Пусть:

(5)

где – объект, представитель класса , а  – объект, представитель класса .

Утверждение 4. Если , где и – рассмотрение объекта в контексте , то мы наблюдаем явление неполноты .

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

Пусть:

(6)

Утверждение 5. Если , то мы наблюдаем явление избыточности .

Действительно, утверждение 5 справедливо, если учесть что при справедливости

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

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

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

(7)

где – свойство класса, ,, .

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

(8)

где – свойство класса, ,, .

Для функций (7) и (8) характерна следующая взаимосвязь, которая проистекает из смыслового сравнения неполноты и избыточности:

(9)

Если учесть, что в ряде случаев указывает на , то есть свойство класса представлено классом, подлежащим дальнейшему анализу, то, очевидно, что (7) и (8) четко описывает рекурсивный поиск.

Эти функции оперируют с классами количество свойств которых (далее мощность) одинаково. Каждое из свойств одного класса имеет сравнимое с ним свойство в другом классе. Тогда перед их использованием будем использовать метод приведения классов:

(10)

где , , , , – структура выхода функции .

Таким образом, на выходе (10), имеем два класса, некоторые из свойств которых являются нулевыми и удовлетворяют следующему требованию:

(11)

где - функция критерия неполноты либо избыточности.

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

,если (12)

(13)

(14)

где обозначает в данном контексте нулевой класс или класс, не описанный в онтологии.

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

(15)

Также содержательная часть некоторых из (15) может быть представлена лингвистическими переменными [10, 11] при изменении их
мощностей:

|A|  (16)

В связи с этим возникает необходимость новых подходов к оценке состояния (15) на основе нечеткой логики [11].

Анализ показал, что степенью сравнения классов согласно определений (1) – (3) и предложенных критериев (7) – (8) в нечетком пространстве состояний [10] может быть значение индекса нечеткости на основе, например, обобщенного расстояния Хемминга [11]:

(17)

где – мощность нечеткого множества атрибутов класса , – четкое множество, ближайшее к нечеткому . Аналогично (17) определяется процедура для класса .

На основе нахождения нормы расстояния

(18)

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

Если

(19)

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

Следует отметить также, что выявление нечетких критериев неполноты и избыточности с учетом (16) – (19) требует дальнейших исследований.

3. Алгоритмическое обеспечение

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

Пусть а В дальнейшем, примем для определенности , a , что ни в коей мере не сужает общности рассуждений. Тогда класс , а класс . Пусть попарно сравнимы между собой свойства и, и, и.

Критерий неполноты. Алгоритм может быть представлен в виде:

Шаг 1. Выполним операцию нормализации (10).

где ,

теперь .

Шаг 2. Рассчитаем непосредственно количественное значение критерия по неполноте (7):

=(+ ++ + + )/6.

Используя (13) и (14), получим :

=(+ + + 1 + 0 + 0)/6.

Повторив рекурсивно расчет для функций

и , а также определив различия и c помощью (5) и (6), имеем четко определенное значение .

В следствие (11) имеем значение .

Шаг 3. Анализ полученных результатов.

Критерий избыточности.
Алгоритм может быть представлен в виде:

Шаг 1. Выполним операцию нормализации (10).

где ,

теперь .

Шаг 2. Рассчитаем непосредственно количественное значение критерия по избыточности (8):

=(+ ++ ++ >)/6.

Учтем взаимосвязь неполноты и избыточности (9). Тогда:

= (++ +++ )/6.

Что в свою очередь

= (++ + 0 + 1 + 1)/6.

Пройдя рекурсию до конца, имеем значение критерия избыточности.

Шаг 3. Анализ полученных результатов.

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

Утверждение 6. Верхняя оценка вычислительной сложности выполнения алгоритма по критерию временных затрат определяется согласно:

(20)

где – временные затраты на выполнение единичного такта алгоритма, – количество классов онтологии, – среднее число атрибутов в классе.

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

4. Практическая реализация

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

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

Существуют также методы устранения неполных данных [12]. Эти методы имеют ряд практических приложений, но они используются в применении к статистическим данным, что в условиях использования онтологий не применимо. Применение полученных результатов позволило осуществить предварительный анализ динамики развития и изменения
онтологии, которые определяют различия новых версий по отношению к предшествующим. Это дает возможность определения ограничений на использование новых версий онтологий.

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

Таким образом, требования к объему памяти при реализации предложенных алгоритмов соизмеримы с размерами описания онтологии, а время анализа значительно меньше, чем процесс непосредственной загрузки онтологии, что следует из сравнения верхней границы сложности вычисления и экспериментального замера времени загрузки. В связи с этим, к программным реализациям и техническим средствам нет необходимости предъявлять дополнительные требования, и реализация приложений может быть выполнена на персональных компьютерах, что чрезвычайно важно в практических реализациях. Минимальные требования к компьютерам для программной реализации: Intel Celeron 1000 MHz, 128 Mb Ram.

Анализ областей практического применения в значительной части определил перспективы работ. К ним, в первую очередь, следует отнести:

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

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

- создание механизмов динамической компоновки версий онтологии;

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

5. Выводы

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

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

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

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

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

Литература:

[1] Michael K. Smith, Chris Welty, Deborah McGuinness. OWL Web Ontology Language Guide, 2003 // http://www.w3.org/TR/owl-guide/.

[2] W. Liu, S. M. Easterbrook & J. Mylopoulos , Rule-Based Detection of Inconsistency in UML Model.
// Workshop on Consistency Problems in UML-Based Software Development, 2002. P. 106 – 123

[3] Paolo Liberatore Redundancy in Logic I: CNF Propositional Formulae // CoRR cs.AI/0211031: 2002

http://arxiv.org/abs/cs.AI/0211031

[4] Абрамов О.Ю. Избыточность в технических системах // Творчество во имя достойной жизни, Великий Новгород, 2001 http://www.natm.ru/triz/articles/abram/abram01.htm

Обработка нечеткой информации в системах принятия решений. / А.Н. Борисов, А.В. Алексеев, Г.В. Меркульева М.: Радиосвязь 1989. 304 с.

[7] Серый Е.С. Бизнес-словарь. Москва. 2003. http://www.businessvoc.ru/

[8] Jennifer Golbeck, Amy Alford, James HendlerOrganization and Structure of Information using Semantic Web Technologies. // Handbook of Human Factors in Web Design. Maryland, College Park 2003.

[9] Kenneth Baclawski, Mieczyslaw M. Kokar,Richard Waldinger, Paul A. Kogut Consistency Checking of Semantic Web Ontologies. // Lecture Notes in Computer Science, LNCS
2342, Springer, 2002. P. 454 - 459

[10] Кофман А. Введение в теорию нечетких множеств: Пер. с франц. М.: Радио и связь, 1982. 432 с.

[11] Tsokalas L.H. Uhrig R.E. Fuzzy and Neural Approaches in Engineering. New York: John Willer & Sons Enc., 1997. 587p.

[12] Warren Sarle. Handling missing or incomplete data. Information Technology Services at The University of Texas at Austin, 2004. http://www.utexas.edu/its/rc/answers/general/gen25.html