Комп'ютерні науки та інформаційні технології 2009

I.Вступ

Замість того, щоб вирішувати кожну задачу, виходячи з первинних принципів, раціональний агент часто аналізує ситуацію в цілому і згадує, які рішення ухвалювалися раніше ним у подібних ситуаціях. Потім він або безпосередньо використовує ці рішення, або, при необхідності, адаптує їх до обставин, що змінилися для конкретної проблеми. Моделювання такого підходу до вирішення проблем, заснованого на досвіді минулих ситуацій, привело до появи технології логічного виведення, заснованого на прецедентах (Case-Based Reasoning), і надалі – до створення інтелектуальних систем, що реалізовують цю технологію [1]. Основною задачею моделювання таких систем – є визначення метрики для визначення відстані між прецедентом та поточною ситуацією. Пропонується для побудови такої метрики використовувати адаптивні онтології.

II. Процес прийняття рішень на основі прецедентів

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

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

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

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

Однак процес роботи таких систем добре вже відомий. Шукаються відстані між поточною ситуацією та наявними прецедентами. Вибирається той прецедент, для якого ця відстань є найменшою. Виконується чи пропонується до виконання те рішення, яке відповідає цьому вибраному прецедентові.

Введемо такі позначення: Pr={Pr₁, Pr₂,…, Pr_N} – множина прецедентів; R_i – рішення, яке приймається згідно до прецедента Pr_i; S – поточна ситуація; d_і(Pr_i,S) – відстань між і-им прецедентом та поточною ситуацією; о – оцінка прийнятого рішення. У більшості випадків методи пошуку прецедентів зводяться до індукції дерев рішень або до алгоритму "найближчого сусіда", доповненого, можливо, використанням знань про предметну область (ПО).

Інформація про ПО задається її онтологією. Тому пропонуєть-ся проектувати прецеденти та поточну ситуацію на онтологію ПО; ввести в межах онтології ПО метри-ку за допомогою якої шука-ти необхідну відстань (див. рисунок). Крім того сама онтологія буде адаптуватися до ПО за рахунок методів інтелектуального аналізу даних (ІАД). Щоб ці методи використовувались нам необхідно вести історію функціонування інтелектуальної системи, тобто набутий нею досвід розв’язування подібних задач, який буде зберігатися у архіві даних. Тобто ІАД: <О,АД>  О, де О=<X,R,F,W,L> (де X – скінченна множина концептів (понять, термінів) предметної області, яку задає онтологія О; R – скінченна множина відношення між концептами (поняттями, термінами) заданої предметної області; F – скінченна множина функцій інтерпретації (аксіоматизація), заданих на концептах або відношеннях онтології О; W – важливість понять Х, L – важливість відношень R.

Визначену таким чином онтологію будемо називати адаптивною, тобто такою що адаптується до ПО за рахунок модифікації концептів та коефіцієнтів важливості цих понять та зв’язків між ними [2].

Ефективність адаптації онтології бази знань до особливостей ПО визначають закладені в її структуру елементи та механізми її оптимізації (точніше, адаптації) шляхом самонавчання під час експлуатації. Одним з підходів до реалізації таких механізмів є автоматичне зважування понять бази знань (БЗ) та семантичних зв’язків між ними під час самонавчання. Цю роль беруть на себе коефіцієнти важливості понять та зв'язків. Їх розподіл у БЗ має відповідати таким основним вимогам:

• відображати семантичну вагу понять ПО, в якій ця інтелектуальна система реально застосовуватиметься;

• формуватися під час наповнення БЗ та коректуватися відповідно до визначених правил;

• забезпечувати контроль цілісності БЗ;

• відповідати вимогам метрики при їх використанні для порівняння семантичної близькості понять.

Стоїть завдання сформулювати відповідний набір правил присвоєння вагових коефіцієнтів (інформаційної ваги) поняттям та твердженням у моделі БЗ, що забезпечить оцінку актуальної цінності її інформаційного наповнення та досліджуваних поточних ситуацій (наприклад, віднесення текстових документів до класів згідно з УДК).

Покажемо можливість вирішення сформульованого завдання шляхом введення деяких спрощень і припущень. Подамо базу знань у вигляді іменованого графа, числові семантичні характеристики вершин і ребер якого визначаються за певними правилами. Він є орієнтованим зваженим мультиграфом з такими властивостями:

1) на кожний елемент (вершину) може бути довільна кількість посилань;

2) кожний елемент може мати зв'язок з будь-якою кількістю інших елемен­тів;

3) кожному зв’язку (ребру) у моделі відповідає певний напрям і коефіцієнт важливості зв’язку та достовірності відповідного твердження, кожному поняттю (вершині) – коефіцієнти важливості поняття.

Коефіцієнт важливості поняття (зв’язку) – це чисельна міра, котра характеризує значущість певного поняття (зв’язку) у конкретній предметній області, і динамічно змінюється за певними правилами у процесі експлуатації системи.

Наш підхід до подання знань у формі зваженої семантичної мережі (концептуальних графів) полягає у тому, що будь-яке можливе узагальнення, тобто комплексне, складене поняття завжди явним чином артикульоване, назване і як окремий концепт фігурує в базі знань. Тому, якщо деяке узагальнення має спільні властивості чи способи функціонування, вони фізично можуть бути реалізовані через властивості та опрацювання подій відповідного узагальнювального концепту [3,4].

III. Спосіб визначення метрики

Пропонується визначати відстань між прецедентом і ситуацією, як суму відстаней між найважливішими поняттями прецедента та поточною ситуацією. Таких важливих понять може бути одне, два; однак якщо їх є більше-рівне трьох, то нами пропонується вибирати перші три. Ця кількість визначена на основі опитувань експертів різних ПО і вважається ними оптимальною. У такому випадку ми маємо 3 центри ваг i-го прецедента і 3 центри ваг поточної ситуації . Тоді існує 9 різних відстаней , j=1,2,3; k=1,2,3. Вибираємо 3 найменші з них та їх сумуємо. Отримана таким чином сума й буде відстанню між прецедентом та поточною ситуацією. Очевидно, що визначена таким чином відстань залежатиме від того як ми визначимо відстань між двома суміжними вершинами. Для цього пропонується визначати відстані між вершинами, що з’єднані зв’язком як

де W_i та W_j – коефіцієнти важливості вершин С_іта С_jвідповідно; L_ij – коефіцієнт важливості зв’язку між вершинами; Q – константа, яка залежить від конкретної онтології. Приймемо, що L_iі = ∞, тоді d_iі = 0.

Далі знаходимо центри ваг концептуального графа. Це перші три вершини для яких середня відстань є найменшою:

Середня відстань для вершини С_і обчислюється згідно формули:

де n - кількість вершин графа, - найкоротший шлях між вершинами С_і та С_j, який обчислюється за допомогою відомих алгоритмів, наприклад Форда, Дейкстри, Флойда-Уоршалла [9].

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

Зазначимо, що пропонована таким чином відстань задовольняє трьом аксіомам метрики.

Дійсно, згідно визначення відстані, автоматично виконуються дві перші аксіоми:

;

.

Нехай - шлях між вершинами С_і та С_j, який відповідає відстані між ними. Тоді d_іj = d_іk + d_kj, якщо вершина С_k лежить на шляху і d_іj < d_іk + d_kj, якщо вершина С_k не лежить на шляху . А це означає, що виконується третя аксіома метрики.

Розглянемо методи задання початкових коефіцієнтів онтології ІА та їх модифікацію відповідно до рішень, отриманих методами ІАД, а саме методом побудови дерева рішень [8]. Нехай онтологія містить множину понять X={x₁,x₂,…x_n} та множину зв’язків R={r₁,r₂,…,r_m}. W={w₁,w₂,…,w_n} – коефіцієнти важливості відповідних понять, L={l₁,l₂,…,l_m} – коефіцієнти важливості відповідних зв’язків. Спочатку вважаємо, що всі значення w_i=1, i=1,2,…,n; l_j=1, j=1,2,…,m.

Нехай у результаті побудови дерева рішень ми отримали k різних правил Rule₁, Rule₂,…,Rule_k. Кожне правило Rule_s складається з підмножини понять, тобто Rule_s={x_s1, x_s2,…, x_st}. Додаємо до значення w_i одиницю, якщо поняття x_i входить у будь-яке правило Rule_s, s=1,…,k. Аналогічно, якщо між поняттями x_i та x_j існує зв'язок l_p, то значення l_p збільшуємо на одиницю, якщо обидва поняття x_iта x_j входять в одне правило. Тим самим ми збільшуємо важливість понять, які входять у правила, та відповідних зв’язків. Це відповідає уявленню, що поняття (ознаки), які присутні у правилах, є важливішими, ніж інші значення.

Розглянемо пропонований метод на прикладі класифікації текстового документу, тобто його віднесення до відповідного УДК. Набір УДК утворює дерево, ми будемо класифікувати документи за найнижчими рівнями УДК, тобто найнижчий рівень являє собою прецедент. Скільки різних прецедентів буде входити в ІА залежить від того як однаково є важливими поняття, тобто незмінним є коефіцієнт їх важливості та відповідних зв’язків.

Онтологію ІА в яку входять кілька УДК представлятимо у вигляді зважених концептуальних графів. Для кожного прецедента (найнижчого УДК) визначимо 3 центри їх інформаційної ваги, які використовуватимо для обчислення відстаней між прецедентом та поточним текстовим документом (ТД), який ми класифікуємо. Цей ТД ми теж задаємо у вигляді концептуального графа з відповідними коефіцієнтами важливості, які визначаємо як статистична кількість входжень понять та зв’язків у текст. Для цього ТД теж визначаємо 3 центри ваг. Знаходимо відстань між текстом та прецедентами як суму трьох найкоротших відстаней серед 9 можливих. Ідеальний варіант, коли центри ваг прецедента та поточного ТД співпадають. Тоді відстань дорівнюватиме нулю.

Зазначимо, що таким методом можна не тільки класифікувати текстові документи, а й знаходити відстань між будь-якими двома текстовими документами. Це у свою чергу дозволяє отримати деяку оцінку подібності двох електронних текстових документів, згідно до якої можна рангувати ці документи, якщо деякий вважати взірцевим. Тим самим будувати пошукові системи, функціонування яких базується на онтологіях ПО, що дозволяє здійснювати пошук не лише за ключовими словами, але й за контекстом. Приклад такого порівняння описано в [5].

Висновок

Запропонований метод логічного виведення, заснованого на прецедентах дозволяє розв’язувати задачу класифікації та прийняття відповідного до прецедента рішення. Метод ґрунтується на знаходженні відстані між поточною ситуацією та прецедентами та знаходженні мінімальною відстані. У свою чергу для знаходження відстані використовується онтологія предметної області, яка визначається як п’ятірка елементів, а не як трійка як прийнято згідно стандартного означення. Нами запропоновано враховувати важливість понять та зв’язків між ними, а таку онтологію називати адаптивною. Для правильного функціонування інтелектуальної системи коефіцієнти важливості понять та зв’язків модифікуються на основі досвіду набутого системою, використовуючи методи інтелектуального аналізу даних. Ці коефіцієнти використовуються для обчислення відстані між прецедентом та поточною ситуацією. Показано, що визначена таким чином відстань задовольняє трьом аксіомам метрики.

Даний метод можна використати до класифікації текстових документів згідно УДК або співставляти будь-які два текстові документи на їх подібність. Під час обчислення відстані між тестовими документами враховується контекст документів і відповідна до контексту семантика вжитих у них термінів та словосполучень. Це дає можливість здійснювати автоматичний пошук документів, котрі найбільше відповідають запиту-прототипу, і відкидати такі, що мають малу вагу і не відповідають предметній області. За допомогою розробленого методу можна здійснювати автоматичний пошук документів, котрі найбільше відповідають запиту-прототипу в мережі Інтернет, а також здійснювати його класифікацію та ранжування за релевантністю до заданого взірця.

Література

[1]  Каменнова М.С. Корпоративные информационные системы: технологии и решения / М.С.Каменнова // Системы Управления Базами Данных. – № 3. –1995. – С. 88-99.

[2]Даревич Р.Р. Mетод автоматичного визначення інформаційної ваги понять в онтології бази знань / Р.Р.Даревич, Д.Г.Досин, В.В.Литвин // Відбір та обробка інформації. – 2005. – Вип. 22(98). – С.105-111.

[3]Рассел С. Искусственный интеллект / С.Рассел, П.Норвиг. – М.,С.-П.,К.: Вильямс, 2006. – 1408с.

[4]Montes-y-Gómez M.Flexible Comparison of Conceptual Graphs / M.Montes-y-Gómez, A.Gelbukh, A.López-López, R.Baeza-Yates. // 12th International Conference on Database and Expert Systems Applications DEXA 2001. – Munich, Germany, September, 2001. – vol. 2113. –Springer-Verlag, 2001. ­– р.56-62.

[5] Даревич Р.Р. Оцінка подібності текстових документів на основі визначення інформаційної ваги елементів бази знань / Р.Р.Даревич, Д.Г.Досин, В.В.Литвин, З.Т.Назарчук – Исскуственный интеллект. – Донецк. – № 3. – 2006. – С. 500-509.

[6] Литвин В.В. Інтелектуальні системи підтримки прийняття рішень на основі адаптивних онтологій / В.В.Литвин, Р.О.Голощук // VI міжнародна науково-практична конференція Математичне та програмне забезпечення інтелектуальних систем. – Дніпропетровськ. – 2008. – С.208-209.