Орлова М. М., Дзицюк Є. В. Модифікація алгоритму Шеплі для обчислення невідповідності онтологій // Міжнародний науковий журнал "Інтернаука". — 2018. — №3.
Технічні науки
УДК 004.62
Орлова Марія Миколаївна
кандидат технічних наук, доцент
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
Орлова Мария Николаевна
кандидат технических наук, доцент
Национальный технический университет Украины
«Киевский политехнический институт имени Игоря Сикорского»
Orlova Mariia
Candidate of Technical Sciences, Associate Professor
National Technical University of Ukraine
“Igor Sikorsky Kyiv Polytechnic Institute”
Дзицюк Євгенія Володимирівна
студент
Національного технічного університету України
«Київський політехнічний інститут імені Ігоря Сікорського»
Дзыцюк Евгения Владимировна
студент
Национального технического университета Украины
«Киевский политехнический институт имени Игоря Сикорского»
Dzytsiuk Yevheniia
Student of the
National Technical University of Ukraine
“Igor Sikorsky Kyiv Polytechnic Institute”
МОДИФІКАЦІЯ АЛГОРИТМУ ШЕПЛІ ДЛЯ ОБЧИСЛЕННЯ НЕВІДПОВІДНОСТІ ОНТОЛОГІЙ
МОДИФИКАЦИЯ АЛГОРИТМА ШЕПЛИ ДЛЯ ВЫЧИСЛЕНИЯ НЕСООТВЕТСТВИЯ ОНТОЛОГИЙ
MODIFICTION OF SHAPLEY ALGORITHMS FOR THE CALCULATION OF ONTOLOGIES INCONSISTENCY
Анотація. В даній роботі описані існуючі підходи до обчислення міри неконсистентності онтологій. Запропоновано поєднання алгоритмів MIV та Шеплі та визначені переваги такого підходу.
Ключові слова: онтологія, консистентність, алгоритм Шеплі.
Аннотация. В данной работе описаны существующие подходы вычисления меры неконсистентности онтологий. Предложено объединение алгоритмов MIV и Шепли и определены преимущества такого подхода
Ключевые слова: онтология, консистентность, алгоритм Шепли.
Summary. This paper describes a study of existing approaches to the technology of measuring inconsistencies in ontology. Combining MI and Shapley algorithms was proposed and the advantages of this method were highlighted.
Key words: ontology, consistency, Shapley algorithm.
Вступ. Необхідність розробки надійних, але принципових логічних методів для аналізу інформації все частіше визнається невід`ємною частиною науки про обробку даних. Онтології відіграють важливу роль в даній сфері. Онтології використовуються в різноманітних додатках, які розширюються кожного дня. Відповідно збільшується і розмір онтологій, що веде до появи неконсистентностей. На сьогодні існує декілька методів обробки неконсистентних онтологій, які засновані на наступних сценаріях
Припустимо, K' і K'' - дві несумісні підмножини онтології O. Якщо O має неперетинаючі джерела невідповідностей, це означає, що K' ∩ K'' =ø. Невідповідність може мати місце на різних рівнях: на рівні однієї аксіоми і на рівні множин аксіом. Наприклад, нехай
K' = {C ⋃ ¬C ϵ C ∩ ¬ C} та К'' = {T ϵ ƎR.B , T ϵ R.¬B }. Аксіома в K' є неконсистентною, тоді як обидві з двох аксіоми в K'' несуть є причиною цього протиріччя.
Онтологія О, що має перекриваючі джерела неконсистентностей, означає, що К' ∩ К'' ≠ ø. Якщо два набори несумісних аксіом перетинаються, це означає, що певні аксіоми роблять більший внесок у неконсистентність. Найімовірніше, що видалення таких аксіом з O призведе до вирішення інших невідповідностей.
У даній роботі пропонується кількісна міра неконсистентностей у онтологіях, на основі алгоритмів Шеплі та MIV.
Мета даної роботи - використання раніше відомих стратегій теорії ігор в контексті онтологій в поєднанні з алгоритмом мінімальних підмножин і представлення міри систематичної оцінки неконсистентності в онтологіях. Цей підхід є незалежним від конкретного виду мови онтології або конкретної системою обробки онтології.
2. Основні поняття
У цьому розділі спочатку розглянемо деякі основні поняття та терміни, пов'язані з мовами онтології в семантичному Web та їх зв'язок з описовими логіками (DL). Також визначимо поняття неконсистентності в онтології.
2.1 Онтології в семантичному Web
Мова веб-онтології (OWL) рекомендована як стандарт мови web-онтологій Консорціумом Всесвітнього Інтернету [6]. Це мова для обміну та обґрунтування інформації в мережі Інтернеті.
OWL - це розширення структури опису ресурсів (RDF) і перегляд web-онтологічної мови DAML + OIL.
OWL являє собою представлення домену предметної області і визначає ієрархії класів та властивостей. Онтологія OWL складається з аксіом і фактів. Аксіоми визначають інтенсифікацію знання шляхом побудови зв'язків між класами та властивостями. Факти описують розширення знань про індивіди (вирази).
2.2 Описові логіки
Описова логіка - це сімейство концепцій формального представлення знань. Вона представляє собою знання про домен насамперед визначаючи відповідні поняття області. Ці поняття використовуються для визначення властивостей об'єктів у домені. Як правило, мова DL має дві частини: термінологію (TBox) і твердження (ABox). TBox включає в себе інтенсифікаційні знання у формі аксіом, тоді як ABox містить розширення знань, яке є специфічним для елементів у домені, індивідів.
TBox разом з ABox називається базою знань в DL. В TBox, основні описи - атомарні поняття, позначені універсальними предикатами, і атомарні ролі, позначені бінарними предикатами для вираження зв'язків між індивідами. Поняття можуть бути побудовані на атомарних концепціях за допомогою перетину, об'єднання, заперечення, обмеження. Аксіоми виражають як поняття так і ролі пов'язані один з одним. Як правило, це твердження форми C ϵ D : “Концепція C підпадає під поняття D”; або C ≡ D, що означає C ϵ D та D ϵ С. де C та D є концентами описів. ABox - це набір тверджень C(a) та R(a, b), де R - роль, а а, b - індивіди.
Інтерпретація І визначає формальну семантику понять, ролей та індивідів. Вона складається з непустої множини ∆І, яку називають доменом. Функція інтерпретації І ставить у відповідність кожен концепт А підмножині АІ з множини ∆І та кожну атомарну роль R до бінарного відношення RI ϵ ∆І х ∆І . До того ж І переводить кожне ім'я індивіда а в елемент аІ ϵ ∆І. В інтерпретації І C ϵ D, якщо CІ ϵ DІ ; C ≡ D, якщо CІ ≡ DІ ; С(а), якщо аІ ϵ СІ; R(a,b), якщо (aІ,bІ) ϵ RІ .
Основні властивості концептів в Tbox: здійсненність, категоризація, еквівалентність і диз'юнкція. Концепція С в Tbox Т називається здійсненною по відношенню до Т, якщо існує непуста модель Т (інтерпретація І, яка відповідає аксіомам Т) СІ. Інші три властивості можуть бути зведені до (не)здійсненності. Ще одним важливим фактором обробки Tbox є перевірка його консистентності, тобто перевірка існування моделі Т. Обробка Abox включає перевірку екземплярів, реалізацію, і вибірку даних. Перевірка екземпляра перевіряє, чи конкретний індивід є екземпляром визначеної концепції. Реалізація знаходить найбільш конкретну концепцію, екземпляром якої є індивід. Вирка даних знаходить індивіди у базі знань, які є екземплярами даної концепції. ABox A є консистентним відносно до TBox T, якщо існує інтерпретація, яка є моделлю як A, так і T (тобто інтерпретація I, яка одночасно задовольняє аксіомам Т і твердженням А). Подібно до властивостей TBox, властивості ABox також можна звести до проблеми узгодженості ABox. В даній роботі термін "консистентність" використовується для послання на проблеми узгодженості і в Tbox, і в Abox.
Таким чином, концепт в DL називається класом в OWL. Роль в DL - це властивість у OWL. Терміни “аксіома” та “індивід” мають однакове значення в DL і OWL. OWL DL частково заснований на DL SHOIN (D), який включає в себе спеціальні конструктори, такі як транзитивні властивості, зворотні властивості та властивості типу даних, а також його підмножину OWL Lite, яка базується на менш виразному DL SHIF (D). Враховуючи те, що зв'язок між OWL і DL є тісним, в даній роботі будемо вважати їх синонімами, приклади будуть наведені в синтаксисі DL.
Вільна формула бази знань K - це формула K, що не належить до жодної мінімальної неконсистентної підмножини К. Це означає, що для ця формули не має конфліктів з базою.
У цьому розділі вивчаються методи вимірювання невідповідностей у базах знань DL. Ідея полягає в тому, щоб спочатку визначити значення невідповідності, а потім прийняти його як характеристичну функцію для обчислення значення Шеплі.
Наступний приклад будемо використовувати як робочий. У прикладі A, B, C, D, A1 - A6 позначають концепти, а та b — індивіди.
Повна DL-обробка, така як FaCT ++ [8], RACER [9], повідомляє, що ця база знань є непослідовною. Однак вони не дають інформацію про те, що, наприклад, існує чотири несумісні підмножини (3, 4, 5 та 8; 1, 2 і 7; 1, 3, 4, 5 і 7; 6) в цій базі знань і , що одна аксіома (аксіома 6) є по суті неконсистентною.
Визначення 1. Враховуючи набір аксіом і тверджень в базі знань K, характеристична функція v: 2К → R присвоює значення кожній підмножині K', де К' ⊑ К.
Прикладом характеристичної функції є значення невідповідності, яке присвоює 1 до набору аксіом, якщо він неконсистентний, а 0 - до набору, якщо він є послідовним.
Визначення 2. Для набору аксіом і тверджень К' належить К, неконсистентне значення К' визначається як:
Id (К') = { 0, якщо К' консистентне або пусте; 1 — в іншому випадку}.
Приклад 1. Деякі значення невідповідності робочого прикладу є наступними. Зображуються лише деякі них, з коефіцієнтом невідповідності 1, і деякі послідовні (коефіцієнт невідповідності 0).
Id ({1}) = 0 Id ({1, 2}) = 0
Id ({3,4,5,8}) = 1 Id ({1,3,4,5,7}) = 1
Id ({2}) = 0 Id ({3,4,5}) = 0
Id ({3,4,5,6}) = 1 Id ({3}) = 0
Id ({1,2,6}) = 1
Як показано вище, підмножина {1, 2, 6} має коефіцієнт невідповідності 1. Аксіома 6 часто має велике значення для об'єднання підмножини. Наприклад, додавання аксіоми 6 змінює коефіцієнт невідповідності на 1 для підмножини {2, 6}. Це справедливо і для підмножини {3, 4, 5}.
Аналогічно, можемо визначити іншу характеристичну функцію, яка призначає набору аксіом 0, якщо поняття A є здійсненним і 1 в іншому випадку.
Визначення 3. Значення несумісності набору аксіом K' у відповідності до концепції A (A зустрічається у K) визначається як:
ІА(К) = {0, якщо А є здійсненною у відповідності до К', 1 — в іншому випадку}.
Приклад 2. Деякі пов'язані з концепцією значення невідповідності робочого прикладу:
IA1({1, 2}) = 1 IA1({1, 3, 4, 5}) = 1
IA3({3,4,5}) = 1 IA3({3,4,9}) = 0
Мірою неконсистентності є кількісне визначення вкладу кожної аксіоми або твердження в базі знань в загальну невідповідність. Чим більше це значення, тим більше аксіома сприяє неконсистентності.
Шеплі [10] запропонував підхід, відомий як значення Шеплі, в контексті теорії ігор в 1953 році, який описує справедливий розподіл одержаних прибутків співробітництвом між кількома агентами.
Значення Шеплі визначається для гри, яка має n агентів. У грі агенти можуть утворювати коаліції, які є підмножиною n агентів. Коаліція виграє, коли всі його члени працюють разом як команда. Питання, яке може виникнути "який агент найбільше сприяє виграшу в різних коаліціях?"
Рішення цієї проблеми може допомогти визначити, який агент має більше значення для гри, ніж інші. Значення Шеплі пропонується для вирішення цієї проблеми. Основна ідея полягає в наступному. Припустимо, що агенти приєднуються до певної коаліції за певним порядком і виграш агента в цій коаліції - його граничний внесок у виграш коаліції. Значення Шеплі бере всі можливі порядки формування коаліції та вираховує граничний внесок агента.
Оскільки перевірка невідповідності може розглядатися як гра, кожна аксіома (або твердження) в базі знань можна вважати агентом. Аналогічно, внесок кожної аксіоми (або твердження) до неконсистентності може бути виміряний використовуючи значення Шеплі.
Нехай К — база знань, σК — набір всіх перестановок К, n = |K| - потужність К (кількість неповторюваних елементів). Існує порядок σ ⊑ σК , позначаємо pασ для позначення набору всіх аксіом та тверджень в σ, які передують аксіомі (або твердженню) α.
Визначення 4. Значення Шеплі для аксіоми (або твердження) α в базі знань К визначається як:
Значення Шеплі можна безпосередньо обчислити з можливих коаліцій без урахування перестановок за наступним виразом:
де C - будь-яка коаліція аксіом та тверджень K, n = | K |, і c = | C |.
3.1 Міра неконсистентності на основі значення Шеплі
Приймаємо міру неконсистентності, визначену в Визначенні 2 (те ж саме обчислення може бути застосоване до поняття пов'язаної міри, визначеної в Визначенні 3) як характеристичну функцію, а потім використовуємо значення Шеплі для обчислення в якій мірі аксіома або твердження стосується невідповідності.
Наприклад, нехай, K - база знань, а α - аксіома (або твердження) в К, тоді значення Шеплі для α, виходячи з значення невідповідності Id визначається як:
де n = | K | і c = | C |.
Значення Шеплі бази знань K - це вектор, де кожен елемент позначає значення Шеплі кожної аксіоми (або твердження) в К.
Приклад 3. Значення Шеплі бази знань К {C ⊔ ¬C ⊑ C ⊓ ¬C, T ⊑ ∃R.B, T ⊑ ∀R.¬B, A⊑D} = ().
Приклад 4.Значення Шеплі для робочого прикладу: ()
Це показує, що аксіома 6 є такою, що викликає більшість проблем. 3, 4, 5 і 8 однаково відповідальні за неконсистентності, як і 1 і 7. Аксіома 9 має значення 0, що означає, що вона не сприяє неконсистентності. Аксіома 2 має більше значення, ніж 3, 4 або 5, що показує, що неконсистентність однаково розподілена між 3, 4 і 5.
3.2 Властивості міри неконсистентності
В даному підрозділі представлені декілька спостережень відносно властивостей міри неконсистентності.
Визначення 5. Характеристична функція v зростає, якщо Х належить Y, v(X) <= v(Y).
Зростаюча функція вказує на те, що додавання агентів до коаліції ніколи не призведе до зменшення значення Шеплі. Завдяки монотонності DL обробки, це можна довести наступним прикладом.
Пропозиція 1. Різке (пов'язане з поняттям) значення невідповідності (див. Визначення 2 та 3) зростає. Набір аксіом і тверджень називається конвергентним, якщо його значення невідповідності є конвергентним, тобто воно відповідає значенню неконсистентності супер наборів, і додавання будь-яких інших аксіом або тверджень не змінює значення невідповідності.
Визначення 6. Конвергентна підмножина K' бази знань K визначається як набір аксіом і тверджень, що задовольняє двом наступним властивостям:
1. Id(K' ) = 1 (або IA(K' ) = 1), та
2. Id(K'') = 0 (або IA(K'' ) = 1) для всіх К'' ∈ К
Інтуїтивно, K' є збіжною точкою, в якій значення невідповідності зміщується від 0 до 1. Існує пряме відношення між конвергентними підмножинами і мінімально неконсистентними підмножини бази знань, визначені наступним чином.
Визначення 7. Говорять, що Т' є мінімально неконсистентною підмножиною бази знань Т, якщо виконуються наступні твердження:
1. Т' є неконсистентною
2. Т'' є неконсистентною для кожного Т'', яке належить Т'.
Пропозиція 1. Нехай K' (визначення 6) є мінімально неконсистентною підмножиною. Міра невідповідності коаліції K' може бути визначена за кількістю мінімально непослідовних підмножин, які будуть видалені, якщо видалити K' з бази знань. Іншими словами, вимірюється вплив K' на базу знань, формалізований наступним чином.
Визначення 8. Міра невідповідності підмножини K' в базі знань K може бути визначена наступним чином:
Ii(K' ) = |MIS(K)| − |MIS(K − K')|
де |MIS (K')| позначає кількість мінімально неконсистентних підмножин K'.
Приклад 4. У робочому прикладі зазначено чотири конвергентних підмножини, тобто чотири MIS. Приклад
MIS1 = {1, 2, 7}, MIS2 = {3, 4, 5, 8}, MIS3 = {1, 3, 4, 5, 7}, MIS4 = {6}
Ii({1}) = Ii({7}) = Ii({3}) = Ii({4}) = Ii({5}) = 2
Ii({2}) = Ii({6}) = Ii({8}) = 1
Ii({9}) = 0
Очевидно, що видалення 1, 7, 3, 4 або 5 призведе до видалення найбільшої кількості невідповідностей. Видалення аксіоми 9 взагалі не вплине на неконсистентність.
3.3 Застосовувати міри невідповідності до виразів
Розглянуті в даній роботі невідповідності до цих пір застосовувалися до аксіом в онтологіях. Це виключає можливість перевірки компонентів аксіом. Зокрема, якщо невідповідність рівня одиничної аксіоми, то можна отримати лише два значення: консистентне або неконсистентне.
Вирази є складовою частиною аксіоми DL, тому можна визначити підхід, що виявляє частини аксіом, що відповідальні за неконсистентність. Отже, міра невідповідності може також застосовуватися до виразів, і це дозволяє нам це “подивитися всередину” аксіоми і визначите, яка частина аксіоми сприяє невідповідності.
4. Обчислювальна складність задачі
Найважливіше джерело обчислювальної складності при розрахунку значення Шеплі - це труднощі отримання міри неконсистентності аксіоми. Це безпосередньо залежить від складності перевірки послідовності в DL обробці. Крім того, складність також пов'язана з самим процесом обчислення. Обчислення значення Шеплі розглядає всі підмножини аксіом / тверджень в базі знань, і, отже, це призводить до складності EXP-time. Однак насправді не потрібно обчислювати значення невідповідності всіх підмножин.
У DL, аксіоми можуть бути пов'язані одна з одною через відповідність структури. Наприклад, аксіома A ⊑ B структурно пов'язана з ¬B ⊑ Т, але не пов'язана з ¬C ⊑ D. Додавання структурно непов'язаної аксіоми до коаліції не буде змінювати значення невідповідності. Структурна відповідність — еквівалентність відношення, отже, його можна використовувати для розбиття аксіом, як показано нижче. Такий підхід можна використовувати як оптимізацію, щоб прискорити обчислення невідповідності Шеплі.
Визначення 9. Аксіома структурно пов'язана з іншою аксіомою, якщо їх перетин (сукупність всіх (відхилених) назв концептів і імена ролей, що зустрічаються в аксіомі) не порожній. Структурна релевантність є транзитивним закриттям прямого структурного зв'язку.
Розбиття аксіом на групи на основі структурного зв'язку зберігає порядок значень Шеплі аксіом (і тверджень) всередині однієї групи. Іншими словами, якщо аксіома має більш високе значення Шеплі, ніж інша аксіома в групі, то в базі знань також буде вище значення Шеплі.
4.1 Оптимізація на основі властивостей міри невідповідності
Розбиття бази знань відповідно до структурної релевантності має сенс, коли розміри |Ki| невеликі, особливо коли розмір |Кі| обмежений константою. Однак це значною мірою залежить від конкретної бази знань. В даній роботі пропонується алгоритм розрахунку значення Шеплі, що базується на властивостях міри невідповідності, особливо властивості конвергентності. Цей метод спрямований на зменшення кількості перевірок послідовностей.
Основна ідея: згідно з визначенням 6 у розділі 3.2, конвергентна підмножина бази знань - це максимальна підмножина, значення невідповідності якої повинно бути розраховане. Будь-яка множина ковергентної бази знань може мати значення невідповідності 1 за рахунок монотонності DL. Отже, якщо підмножина є конвергентною, немає необхідності обчислювати її множину. Детальний алгоритм зазначений нижче.
Input: axiom α in K
Output: Shapley value of α
For all subsets K` ⊆ K
While I(K` ∪α) = 0
Go to next unvisited K`
For all supersets K`` of K`
I(K``) = 1
K`` → visited
Go to next K`
Compute Shapley value of α
Приклад 5. Щоб побачити, як цей алгоритм працює, застосуємо оптимізацію до одного з розділів робочого прикладу:
{A1 ⊑ A2 ⊓ ¬A ⊓A3, A2 ⊑ A ⊓ A4, A3 ⊑ A5 ⊓ A4, A4 ⊑ C ⊓ ∀S.¬B, A5 ⊑ ∃S.¬B, A1(a), A3(b)}.
Алгоритм спочатку обчислює значення неконсистентності A1(a), коаліцію A1(a) та будь-яку іншу аксіому, а потім коаліцію A1(a) та будь-які дві інші аксіоми, оскільки коаліція A1 належить A2 ⊓ ¬A ⊓ A3, A2 ⊑ A ⊓ А4 і A1(a) має значення невідповідності 1, обчислення значення невідповідність множин пропускається.
Такий підхід застосовується і для множини
A1 ⊑ A2 ⊓ ¬A ⊓ A3, A3 ⊑ A5 ⊓ A4, A4 ⊑ C ⊓ ∀S.¬B, A5 ⊑ ∃S.¬B та A1(a).
Оскільки можна розглянути мінімальні непослідовні підмножини як фундаментальні ознаки, що характеризують невідповідність, ми використовуємо аксіому тут як основну міру невідповідності.
Визначення 10
Значення MIVC визначається як
Це дозволяє нам визначити більш точне значення невідповідності, як це показано у наступному прикладі.
Приклад 6
Нехай K1 = {a, ¬a, ¬a ⊓ c, a ∨ d, ¬d, b ⊓ ¬b, e} ,
значення MIVC :
Визначення 11 Метод невідповідності МІ визначається як кількість мінімальних непослідовних множин К, тобто:
IMI (K) = |MI(K)|
Приклад
K = {a, ¬a, ¬a ∧ c, a ∨ d, ¬d, b ∧ ¬b, e}
Таким чином ми отримуємо наступне
IMI (K) = 4 IMI ({a, ¬a, ¬a ∧ c}) = 2 IMI ({b ∧ ¬b, e}) = 1 IMI ({¬a, ¬a ∧ c}) = 0
Пропозиція 3 Міри невідповідності МІ ІМІ є базовою мірою невідповідності, тобто вона задовольняє властивостям послідовності, монотонності, незалежності вільної формули. Наступний результат показує, що дане МІ Шеплі значення є таким самим як і MIVC
Припущення 2.
Розглянемо спочатку наступну лему, яка буде використана в доведенні.
Лемма 1. Якщо проста гра у множинній формі з безліччю гравців N = {1, . . . , n} визначається єдиною множиною, яка перемагає С' ⊑ N, наприклад:
Тоді значення Шеплі :
Доведення припущення 1.
1. Нехай α — вільна формула К, тоді Simiα = 0, MIVC (K, α) = 0. Відповідно Simiα = MIVC (K, α)
2. Нехай α не є вільною формулою К.
ІМІ можна предстаити як ІМІ (С)= ΣМ є МІ (К)Ḿ(С), де Ḿ — характеристична функція
Позначимо Ḿ(К) гру, визначену множинною формою від K і характеристичною функцією Ḿ. Тоді;
За лемою 1:
Відповідно:
Таким чином поєднання алгоритмів МІ та Шеплі для визначення міри неконсистентності потенційно може бути більш ефективним з точки зору обчислювальної складності та часу виконання ніж алгоритми МІ та Шеплі окремо.
На основі зазначеного вище припущення можемо визначити алгоритм для обчислення МІ Шаплі міри неконсистентності.
В запропонованому алгоритмі для обчислення міри неконсистентності спочатку розраховуються мінімально неконсистентні підмножини. Потім для отриманих підмножин обчислюється значення Шеплі. Таким чином значення Шеплі розраховується не для всіх аксіом бази знань, а лише для її мінімально неконсистентних підмножин, що скорочує кількість обчислень.
Щоб оцінити, описаний метод, був реалізований запропонований в попередньому розділі алгоритм і виконані експерименти. Алгоритм був запущений для онтології Коала з 14 твердженнями та 19 аксіомами. Тести були виконані на системі Windows 10, процесор Intel Core i5 2.30 Гц, 8GB пам’ті. Реалізація розроблена за допомогою мови програмування в Java (JDK 1.5.0). Оригінальна онтологія Коала є консистентною і має 3 невиконувані концепції відповідно. В нашому експерименті, ми додали нових індивідів у невиконувані концепти для того, щоб зробити онтологію неконсистентною. В онтології Коали існували три джерела невідповідності, і для розрахунку міри невідповідності за допомогою алгоритму Шеплі, МІ та МІ-Шеплі необхідно 467 мс, 546 мс та 350 мс відповідно.
Також була проведена серія експериментів для різних онтологій. Результат показав, що швидкість обробки неконсистентності онтології збільшилася в середньому в 1,5 рази.
Висновки. На сьогодні існує декілька методів обчислення неконсистентностей онтологій. В даній роботі був запропонований підхід на основі поєднання алгоритмів MIV та Шеплі. Також була визначена еквівалентність між значеннями невідповідності Шеплі і мінімальним неконсистентним значенням, що дозволяє модифікувати алгоритм Шеплі за допомогою мінімально неконсистентних підмножин. Запропонований алгоритм був протестований на різних за розміром та кількістю джерел неконсистентностей онтологіях. В середньому швидкість обробки неконсистентностей зменшилася в 1,5 рази.
Література
