Інститут кібернетики імені В.М. Глушкова

ВЕЛИЧКО Віталій Юрійович

УДК 681.3:16

РОЗВ’ЯЗАННЯ АНАЛІТИЧНИХ ЗАДАЧ
В ДИСКРЕТНИХ СЕРЕДОВИЩАХ
МЕТОДАМИ ВИВЕДЕННЯ ЗА АНАЛОГІЄЮ

05.13.06 – автоматизовані системи управління та прогресивні

інформаційні технології

Автореферат

дисертації на здобуття наукового ступеня
кандидата технічних наук

Київ 2004

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики ім. В.М. Глушкова НАН України.

Науковий керівник: доктор технічних наук, професор,
Гладун Віктор Полікарпович,
Інститут кібернетики ім. В.М. Глушкова НАН України,
провідний науковий співробітник.

Офіційні опоненти: доктор технічних наук, професор,
Зайченко Юрій Петрович,
Національний технічний університет України “Київський політехнічний інститут” МОН України,
декан факультету другої вищої та післядипломної освіти,

кандидат технічних наук, Рачковський Димитрій Андрійович,
Міжнародний науково-навчальний центр інформаційних технологій та систем НАН України і МОН України,
старший науковий співробітник.

Провідна установа: Інститут проблем математичних машин та систем НАН України, м.Київ.

Захист відбудеться  “13” жовтня   р. о 16 годині на засіданні спеціалізованої вченої ради Д .194.03 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою: 

03680, МСП, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науковій бібліотеці інституту.

Автореферат розісланий  “_1_”вересня_   р.

Учений секретар

спеціалізованої вченої ради |

РОМАНОВ В.О.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Останнім часом технічні можливості для збору та збереження великих масивів даних значно зросли. У світі накопичено бази даних, що охоплюють практично всі сфери людської діяльності. Тому необхідно створення методів інтелектуального аналізу даних, які б дозволяли обробляти великі обсяги інформації. Широке поширення систем інтелектуального аналізу знань свідчить про практичну значимість проведення досліджень у цьому напрямку. Людина в своїй життєдіяльності широко використовує методи правдоподібного виведення, перш за все індуктивне виведення та виведення за аналогією. Виведення за аналогією може виконуватись на підставі описів заданих об’єктів, яких немає у достатній кількості, або які лише частково задовольняють заданим вимогам. Тому розширюється діапазон вирішуваних задач, виникає принципова можливість виконувати діагностику або прогнозування навіть за умови відсутності відомих об’єктів, які повністю задовольняють заданим вимогам. Створення експертних систем, використання яких дозволило б спростити та прискорити процеси аналізу знань, є актуальною науковою задачею. Для інтелектуального аналізу даних на сьогодні пропонується використовувати широкий спектр методів, великий вклад у розробку та дослідження яких внесли вчені В.П. Гладун, М.Г. Загоруйко, А.Д. Закревський, Ю.І. Журавльов, А.Г. Івахненко, Г.С. Лбов, В.М. Коваль, В.К. Фінн, D. J.Quinlan та інші.

Зв’язок роботи з науковими програмами, планами, темами. Результати дисертаційної роботи використовувались при виконанні науково-дослідних тем Інституту кібернетики ім. В.М. Глушкова НАН України: ВФ 245.12 “Розробка теорії і методів інтелектуального аналізу даних для вирішення типових аналітичних задач у наукових дослідженнях” (номер держреєстрації 0100U0002656); ІП.245.15 “Розроб-ка інструментального комплексу інтелек-туаль-ної інформаційної підтримки наукових досліджень”; міжнародного наукового проекта УНТЦ № “Розробка високо-міцної ударостійкої кераміки на основі карбіду бору з використанням технології комп’ютерного моделювання”; міжнародного наукового проекта INTAS № “Data Mining Technologies And Image Processing: Theory And Applications”. При виконанні цих робіт автором розроблено: модель предметної області та методи виведення за аналогією; алго-ритм розв’язання задачі прогнозування властивостей для структурно-атрибу-тив-ної моделі знань; елементи програмного комплексу для вирішення задач класифікації, діагностики і прогнозування шляхом виведення за аналогією.

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

Мета дисертаційної роботи визначає необхідність розв’язання таких задач:

- удосконалення семантичної мережі для представлення структурно-атрибутивних моделей знань;

- розробка критеріїв існування подібності складених об’єктів для структурно-атрибутивних моделей знань;

- порівняльний аналіз розроблених методів виведення за аналогією;

- розробка методів вирішення задач прогнозування властивостей та проектування складу складених об’єктів на основі виведення за аналогією;

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

Об'єкт дослідження – методи виведення за аналогією на основі структурно-атрибутивної моделі знань.

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

Методи дослідження. Дослідження, які виконано під час роботи над дисертацією, ґрунтуються на застосуванні методів математичної логіки, системного аналізу, використанні апарату теорії мультимножин.

Наукова новизна роботи полягає в розробці елементів теорії та прикладних методів правдоподібного виведення на основі представлення структурно-атрибутивних моделей знань в семантичних мережах. Автором отримані такі нові результати:

- структурно-атрибутивну модель знань запропоновано доповнити обмеженнями на сумісність первинних об’єктів у складених об’єктах та використанням вторинних ознак складених об’єктів, у результаті чого з’явилась можливість розв’язувати задачу проектування складу та підвищувати точність отриманих результатів на 3%;

- розроблена методологія вирішення задач прогнозування властивостей та проектування складу методами виведення за аналогією;

- з метою спрощення опису методів виведення за аналогією використана теорія мультимножин;

- запропоновані нові критерії дослідження подібності двох складених об’єктів: критерій покомпонентної структурної аналогії та критерій структурної аналогії властивостей, які дають змогу покращити точність отриманих результатів на 5-10%;

- запропоновані нові способи визначення інтегральної оцінки подібності складеного об’єкта до сукупності складених об’єктів;

- запропонована ітераційна процедура уточнення сформованої гіпотези для моделей, що потрапили до області невизначеності та невпевнених відповідей;

- виконана адаптація розроблених методів до проблеми прогнозування нових хімічних сполук і створення нових керамічних матеріалів;

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

Практичне значення одержаних результатів. Механізми представлення структурно-атрибутивної моделі знань та алгоритми виведення за аналогією реалізовано в програмному комплексі розв’язання задач методами правдоподібного виведення. Комплекс було застосовано в Інституті металургії та матеріалознавства ім. А.А. Байкова РАН для вирішення таких задач: прогнозування температури плавлення окислів сполуки МО, прогнозування кристалічної структури хімічних сполук типу ABCF6 та конструювання нових хімічних сполук із визначеним типом кристалічної структури, прогнозування існування подвійних, потрійних неорганіч-них хімічних сполук. Комплекс розв’язання задач методами правдоподібного виведення був використаний в Інституті проблем матеріалознавства ім. І.М. Францевича НАН України при виконанні проекта створення нових високоміцних карбідоборових керамічних матеріалів.

Розроблені методи виведення за аналогією забезпечують ефективне розв’язання задач прогнозування властивостей та проектування складу об’єкта досліджень. Висока точність отриманих результатів (90  9%) підтверджує доцільність використання програмного комплексу для вирішення широкого кола аналітичних задач.

Особистий внесок здобувача. Всі наукові результати, подані в дисертації, одержані автором особисто. У друкованих працях, опублікованих у співавторстві, особистий внесок здобувача такий: [],],] – доповнення структурно-атрибутивної моделі знань обмеженнями на сумісність первинних об’єктів у складених об’єктах; [] – опис дослідження подібності складених об’єктів; [] – процедура розв’язання задачі проектування складу; [] – дослідження та оцінка відношення подібності між моделлю та прототипом; [] – критерій покомпонентної структурної аналогії, оцінка відношення подібності між моделлю та прототипом; [] – опис розв’язання задач прогнозування властивостей на основі виведення за аналогією; [] – опис блоку аналізу бази знань; [] – опис блоку керування процесами розв’язання задач; [] – опис процедури вирішення задачі прогнозування властивостей, розробка різних способів обчислення інтегральної оцінки подібності моделі до деякої множини прототипів, ітераційної процедури уточнення сформованої гіпотези для моделей, що потрапили до області невизначеності та невпевнених відповідей; [] – архітектура програмного комплексу розв’язання задач методами правдоподібного виведення, розробка схеми використання програм комплексу при розв’язанні аналітичних задач, використання коефіцієнтів значимості первинних властивостей, методи виведення за аналогією на основі структурно-атрибутивних моделей; [] – опис програми “Аналогія”.

Апробація результатів дисертації. Окремі положення та наукові результати дисертаційної роботи доповідались на семінарах та конференціях: VI Міжнародна конференція “Knowledge-Dialogue-Solution” KDS-97 (Ялта, 15-20 вересня, 1997); I Міжнародна науково-практична конференція з програмування УкрПРОГ'98 (Київ, 2-4 вересня, 1998); I Міжнародна науково-методична конференція “Інтернет-освіта-наука” (Вінниця, 17-19 листопада, 1998); VIII Міжнародна конференція “Knowledge-Dialogue-Solution” KDS-99 (Кацивелі, 13-19 вересня, 1999); III Міжнародна наукова конференція “Інтелектуалізація обробки інформації” ИОИ-2000 (Алушта, 12-16 червня, 2000); II Міжнародна науково-практична конференція з програмування УкрПРОГ'2000 (Київ, 23-26 травня, 2000); російсько-український науковий семінар Інтелектуальний аналіз інформації, ИАИ-2001 (Київ, 16-18 травня, 2001); X Міжна-род-на конференція “Knowledge-Dialogue-Solution” KDS-2001 (Санкт-Петербург, 19-22 червня, 2001); III Міжнародна науково-практична конференція з програмування УкрПРОГ'2002 (Київ, 21-23 травня, 2002); IV Міжнародна наукова конференція “Інтелектуалізація обробки інформації” ИОИ-2002 (Алушта, 17-21 червня, 2002);

Публікації. Автором опубліковано 14 статей у наукових журналах та збірниках наукових праць, із них 2 – одноосібні, 9 праць опубліковані у фахових виданнях ВАК України.

Структура та обсяг дисертації. Дисертаційна робота складається із вступу, п’яти розділів, висновків та трьох додатків. Загальний обсяг роботи – 116 сторінок, 12 рисунків, 35 таблиць, список вико-ристаних джерел містить 47 найменувань на 3 сторінках, 3 додатки мають обсяг 16 сторінок.

Зміст РОБОТИ

У вступі відображена актуальність теми дисертації, мета та задачі дослід-ження, наукова новизна та практичне значення роботи, стисло викладений зміст дисертаційної роботи.

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

Загальнопоширеною парадигмою в області автоматизації мислення та машинного навчання є виведення на основі фактів (Case-Based reasoning). При виведенні на основі фактів нова проблема вирішується за допомогою виявлення її подібності до вже вирішених проблем та адаптації відомого рішення до нової ситуації. Виведення на основі фактів складається з чотирьох основних етапів: 1) аналіз бази відомих фактів (retrieve); 2) формування гіпотези про властивості моделі (reuse); 3) перегляд сформованої гіпотези (revise); 4) внесення підтвердженої гіпотези до бази фактів (retain).

Формування гіпотез може бути здійснено за допомогою індуктивного узагальнення та виведення за аналогією. При використанні індуктивного виведення на першому етапі здійснюється виведення загальної закономірності на базі відомих фактів. Отримане правило на другому етапі використовується для формування гіпотези про модель. При використанні виведення за аналогією посилки виведення відносяться до одного об'єкту, а гіпотеза - до іншого, причому кожній гіпотезі надається деяка оцінка впевненості виведення. Перший з цих об’єктів будемо називати прототипом q, а другий – моделлю m. Наприклад, при розв’язанні задачі прогнозування властивостей об’єкта дослідження, на основі аналізу наявних знань про відомі властивості деякої сукупності об'єктів, опис яких представлено в базі фактів, може бути сформовано гіпотезу про властивості моделі.

Другий розділ присвячений розробці методів виведення за аналогією на основі структурно-атрибутивної моделі знань.

Для визначення структурно-атрибутивної моделі знань мають бути задані множини P, A, S, V. Елементи множини P будемо називати первинними властивостями, елементи множини А – первинними об’єктами, елементи множини S – складеними об’єктами, елементи множини V – властивостями складених об’єктів. На заданих множинах визначимо такі відношення. Відношення служить для опису властивостей складених об’єктів, відношення необхідно для представлення знань про склад заданих складених об’єктів. Відношення представляє первинні властивості первинних об’єктів.

Первинну властивість p будемо називати релевантною до множини складених об’єктів , якщо існує складений об’єкт та первинний об’єкт такий, що та . Первинний об’єкт будемо називати релевантним до властивості складених об’єктів v, якщо існує складений об’єкт такий, що та .

Серед складених об’єктів виділимо так звані припустимі складені об’єкти, тобто такі об’єкти, існування яких відповідає деяким формальним критеріям. Доповнимо структурно-атрибутивну модель, визначивши множину С класів первинних об’єктів та множину T – припустимих структур складених об’єктів. Введемо відношення R5 та R6, що використовуються для відображення умов формування множини припустимих складених об’єктів: , тоді, коли первинний об’єкт a належить до класу c; , тоді, коли первинні об’єкти класу c створюють припустиму структуру t.

Необхідною умовою існування подібності між двома первинними об’єктами a та b є наявність спільних первинних властивостей. Для двох складених об’єктів та виконується необхідна умова існування подібності, якщо вони мають спільні релевантні первинні властивості, тобто.Чисельну оцінку, яка характеризує наскільки первинна властивість релевантна до об’єктів множини прототипів будемо називати вагою первинної властивості. В результаті дослідження подібності моделі та прототипів мають бути сформовані чисельні оцінки, які відображають ступінь подібності моделі та прототипів. У виведенні за аналогією для структурно-атрибутивних моделей виділимо такі етапи, які відповідають ета-пам виведення на основі фактів: 1) аналіз заданих складених об’єктів – обчислення ваг первинних властивостей; 2) дослідження подібності складених об’єктів моделі та прототипу (або сукупності прототипів) – обчислення ваг первинних та складених об’єктів; 3) формування гіпотези про властивості складеного об’єкта, який виступає в якості моделі – склад моделі може бути заданий за умовою задачі (прогнозування властивостей), або спроектований у відповідності до заданих властивостей складе-них об’єктів (задача проектування складу); 4) уточнення сформованої гіпотези.

Для опису критеріїв та методів виведення за аналогією використаємо теорію мультимножин. Мультимножина на множині X – це множина X разом з функцією , яка визначає кратність елементів X. Нехай – довільна мультимножина. Визначимо операцію додавання мультимножини за елементами мультимножини . Будемо вважати, що ==. Аналогічно для операції об’єднання . Нехай – множина складених об’єктів, – деякий складений об’єкт. Позначимо – множина первинних об’єктів, які входять до складу складеного об’єкта s, тоді мультимножина . Позначимо – множина первинних властивостей, які має первинний об’єкт , тоді мультимножина . Позначимо . З того, що , випливає, що . Позначимо , при чому .

Критерії існування подібності складених об’єктів відрізняються способами визначення кратності релевантних первинних властивостей – .

1.

2.

3.

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

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

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

Для деякого складеного об’єкта s, склад якого задано, може бути визначена ступінь його подібності до іншого складеного об’єкта z або сукупності складених об’єктів Z згідно з вагами його складових відповідно за формулами та . При виведенні за аналогією першим складеним об’єктом s буде виступати модель m, а другим z – прототип q або сукупність прототипів Z, що є підмножиною Q.

Для складених об’єктів визначимо критерій покомпонентної структурної аналогії. У цьому випадку вага за множиною Z обчислюється наступним чином: якщо для довільного первинного об’єкта a існує довільний первинний об’єкт такий, що та , то . Для всіх інших первинних об’єктів вага за множиною Z дорівнює 0. Ступінь подібності складеного об’єкта s до множини складених об’єктів Z визначається згідно з вагами релевантних до множини Z первинних об’єктів, що входять до складу складеного об’єкта :.

Для того, щоб більш точно врахувати подібність саме структур двох складених об’єктів, розроблений критерій структурної аналогії властивостей, що використовується для встановлення подібності складеного об’єкта до складеного об’єкта .

Нехай , та . Тоді ступінь подібності складеного об’єкта до складеного об’єкта дорівнює .

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

Обчислювальна складність алгоритму методів загального аналізу росте пропорційно кубу загальної кількості об’єктів структурно-атрибутивної моделі. Порівняно з методом загального аналізу обчислювальна складність алгоритму методу попарного порівняння приблизно в 3 рази більша.

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

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

Задача прогнозування властивостей полягає у визначенні невідомих характеристик об’єкта дослідження. Нехай для довільного складеного об’єкта qQ задані Vq та Aq=, для довільного складеного об’єкта m M задано Am= та для всіх задано . Необхідно для довільного складеного об’єкта m M знайти Vm=. Нехай досліджується властивість , яку будемо називати цільовою властивістю. Якщо властивостей складених об’єктів більше ніж 1, то дослідження кожної з них буде проводитися незалежно. Здійснимо розбиття множини прототипів за множиною значень досліджуваної властивості ,.

Для висунення гіпотези про значення властивості моделі m M необхідно дослідити подібність моделі m до кожної підмножини прототипів . Будемо називати мірою моделі m за значенням властивості . Якщо міра моделі за деяким значенням властивості максимальна, то можна висунути гіпотезу про те, що модель має значенням властивості .

При використанні методу загального аналізу кожній моделі m M поставлена у відповідність сукупність мір . Ступінь подібності складеного об’єкта m може бути визначена як нормована по формулі відносно складеного об’єкта , де - прототип, для якого виконується =. Тоді .

При використанні методу попарного порівняння для кожної моделі m M обчислений кортеж оцінок , де – вага моделі m відносно складеного об’єкта qі. Міра моделі m за кожним зна-ченням властивості визначається за одним із способів: 1) – цей спосіб є ефективним тільки в тому випадку, коли кількість прототипів, що мають різні значення властивості, приблизно однакова; 2) – цей спосіб є ефективним тільки в тому випадку, коли модель не отримала однакові значення ваги відносно прототипів з різними значеннями властивості; 3) визначається як сума С найбільших значень ваг моделі m відносно тих прототипів, що входять до сукупності прототипів ; 4) дорівнює кількості прототипів з множини , а множина формується з прототипів, вага яких входить до С найбільших значень ваг моделі m; 5) , визначається як у четвертому способі.

Для більш обґрунтованого висунення гіпотези про значення властивості моделі m представляється доцільним виділити такі області: область невизначеності за значенням ; область невпевнених

відповідей за значенням ; область впевнених відповідей за значенням : .

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

При використанні методу попарного порівняння, якщо не було отримано однозначного висновку про властивість моделі m, потрібно збільшити кількість прототипів, на підставі яких було визначено міру моделі. Для цього необхідно, змінивши значення параметру С, повторити обчислення міри моделі, але лише для значень властивості з множини .

У загальному вигляді процедура обчислення міри моделі та встановлення порядку на множині моделей може бути представлена таким чином. Для кожної моделі здійснюється така послідовність обчислень. На кожній ітерації s:

·

причому , при обчисленні міри за 4-тим або 5-тим способом та , , при обчисленні міри за 3-тім способом;

·

·

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

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

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

1) міру подібності прототипу q за значенням властивості :

;

2) відносну кількість прототипів, які більш подібні до прототипів, що мають інші значення властивості:

;

3) середнє арифметичне значення мір прототипів для кожного значення властивості за формулою: і для значення властивості за формулою: , яку будемо називати мірою значення властивості vj;

4) мінімальне відносне значення різності мір значень властивостей за формулою:

.

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

Щоб використати ознаки, які характеризують складений об’єкт у цілому, доцільно ввести деяку властивість складеного об’єкта, яку будемо називати вторин-ною властивістю. Значення вторинної властивості складеного об’єкта до проведення дискретизації обчислюється за допомогою математичних операцій над одноймен-ними значеннями властивостей первинних об’єктів, які є релевантними складеному об’єкту. Отримані в результаті дискретизації номінальні вторинні властивості складених об’єктів використовуються у наведених методах дослідження подібності.

Методологія вирішення задачі прогнозування властивостей методами виведення за аналогією.

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

Відповідно до схеми виведення на основі фактів з метою підвищення достовірності виведення на першому етапі необхідно виконати аналіз бази фактів. Експерт предметної області згідно з своїми знаннями здійснює такі операції:

) відбір первинних властивостей та визначення коефіцієнтів значимості первинних властивостей, які будуть змінювати обчислену вагу релевантних первинних властивостей;

) обрання найкращого способу підрахунку ваг первинних властивостей та первинних об’єктів. Для кожної множини прототипів за допомогою різних методів та евристичних критеріїв виведення за аналогією виконується аналіз заданих складених об’єктів та дослідження подібності первинних об’єктів. Первинні об’єкти впорядковуються за зменшенням ваги до множини прототипів . Експерт обирає, який спосіб впорядкування первинних об’єктів, що є релевантними для досліджуваного значення властивості, є найкращим. На основі обраного порядку визначається відповідний найкращий спосіб підрахунку ваг;

) уточнення складу та властивостей об’єктів з множини прототипів. Для цього обчислюються характеристики множини прототипів : , , . На основі обчислених значень характеристик необхідно виконати наведені нижче дії. Переглянути перелік складених об’єктів з метою перевірки правильності даних та доціль-ності їх використання в множині прототипів. У першу чергу необхідно розглянути складені об’єкти, що мають значення властивості , для яких . Для значень властивості складених об’єктів та необхідно доповнити множину прототипів складеними об’єк-та-ми та розширити простір первинних властивостей такими властивостями, що дають змогу розрізнити складені об’єкти зі значеннями властивості та . Для значень властивості складених об’єктів та необхідно або доповнити множину прототипів, або не проводити етап формування гіпотези за цими властивостями, бо результат буде мати дуже низьку достовірність. Якщо у множину прототипів були внесені зміни, необхідно повторити операції аналізу за п. a);

) формування вторинних ознак складених об’єктів. Якщо ступінь подібності прототипів, які мають деяке значення властивості , визначена як низька, експерт вирішує доцільність застосування вторинних ознак складених об’єктів;

) вибір методу виведення та евристичних критеріїв виведення за аналогією. Для кожної множини прототипів розв’язуємо задачу мінімізації набору прецеден-тів. Найкращим вважаємо критерій та спосіб підрахунку ваг, при використанні якого отримуємо мінімальний набір прототипів. Експерт порівнює способи підрахунку ваг, що визначені при виконанні п. б) та цього пункту, та приймає остаточне рішення. На основі характеристик , , обираємо метод виведення за аналогією;

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

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

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

При використанні методу загального аналізу доцільно уточнити гіпотезу про значення властивості моделі за допомогою методу попарного порівняння для подібних значень властивості складених об’єктів.

На останньому етапі представимо результат виведення експерту. Якщо деякі гіпотези підтвердились, за ініціативою експерта можна додати відомості про складені об’єкти до бази фактів.

Сформулюємо задачу проектування складу. Нехай заданий деякий набір складених об’єктів Q  S. Для кожного складеного об’єкта q Q задані Vq=, Aq=, а для всіх задано , визначені множини та відношення R5, R6. Нехай задана F – множина властивостей складених об’єктів. Для кожної властивості задано множину її значень – . Нехай задані , та , , . Необхідно знайти множину складених об’єктів M (тобто для кожного m M знайти Am= таку, щоб кожний складений об’єкт  m M мав усі значення властивостей з множини та жодного значення з множини . Таким чином, множини , задають критерії відбору складених об’єктів, а задає обмеження, що накладаються на існування складених об’єктів.

Розглянемо порядок розв’язання задачі комплектації. Здійснимо розбиття множини прототипів за множиною значень досліджуваної властивості , – кількість значень властивості . Нехай до множини входить деяке значення властивості .

У розв’язанні задачі проектування складу можна виділити чотири етапи. На першому етапі розв’язання задачі проектування складу необхідно визначити склад множини об’єктів конструювання RelevantSet – множини первинних об’єктів для кожного з яких . Упорядкуємо множину первинних об’єктів за зменшенням їх ваги за множиною . Максимальне значення порогу повинно бути таким, щоб до множини RelevantSet були включені всі первинні об’єкти з множини , .

На другому етапі виконується конструювання складених об’єктів – моделей з первинних об’єктів, які ввійшли до множини RelevantSet. Для кожного aRelevantSet визначається сукупність структур Тх Т, таких, що та . Далі формуються всі можливі складені об’єкти структур Тх, що складаються з первинних об’єктів множини RelevantSet.

На третьому етапі виконується обчислення міри моделі m значенням властивості з множини V. Обчислення міри моделі m може проводитись як за допомогою методу загального аналізу, так і методу попарного порівняння з викорис-тан-ням різних критеріїв виведення за аналогією. Якщо задача має бути розв’язана методом загального аналізу, то обчислені на попередньому кроці ваги первинних об’єктів використовуються для визначення ваг складених об’єктів із множини М.

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

Четвертий розділ присвячений опису програмного комплексу, в якому реалізовані методи правдоподібного виведення на основі атрибутивних та структурно-атрибутивних моделей знань. У системі виведення та аналізу закономірностей КОНФОР реалізовані методи правдоподібного виведення для атрибутивних моделей знань на основі пірамідальних мереж. Семантичну мережу для представлення структурно-атрибутивних моделей знань та методи виведення за аналогією реалізовані в системі АНАЛОГІЯ. У системі ДИСКРЕТ реалізований алгоритм приведення числових змінних до номінального типу. Детально описана послідовність використання програм комплексу при розв’язанні задач для структурно-атрибутивних та атрибутивних моделей знань.

У п’ятому розділі наведені результати застосування програмного комплексу для вирішення задач прогнозування властивостей та проектування складу хімічних сполук. Розглянуті задачі прогнозування температури плавлення окислів складу МО, прогнозування кристалічної структури хімічних сполук типу ABCF6 та конструювання нових хімічних сполук із визначеним типом кристалічної структури; прогнозування існування подвійних, потрійних та четверних неорганічних хімічних сполук. Відсоток правильно висунутих гіпотез про властивості сполук у наведених задачах склав від 90,79 до 99,68. Експерименти довели, що запропоновані механізми виведення за аналогією в комбінації з ефективними засобами представлення знань забезпечують високий рівень достовірності гіпотез про властивості та склад об’єктів.

ВИСНОВКИ

У дисертаційній роботі наведене теоретичне узагальнення і нове вирішення наукового завдання розробки та використання методів виведення за аналогією для вирішення задач прогнозування властивостей та комплектації складених об’єктів на основі структурно-атрибутивних моделей знань. Розроблені методи реалізовані в про-грамній системі АНАЛОГІЯ, яку було використано для прогнозування власти-вос-тей та проектування складу хімічних сполук.

У ході дослідження отримані такі основні результати.

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

2. Уперше використана теорія мультимножин для опису виведення за анало-гією на основі структурно-атрибутивної моделі знань.

3. Запропоновано доповнення структурно-атрибутивної моделі знань додатко-вими характеристиками множини первинних та складених об’єктів:

3.1 обмеженнями на сумісність первинних об’єктів у складених об’єктах для представлення знань про типи первинних об’єктів, що входять до складу складених об’єктів;

3.2 коефіцієнтами значимості первинних властивостей, які задаються експертом предметної області згідно з своїми знаннями;

3.3 вторинними властивостями складених об’єктів.

4. Розроблені нові методи виведення за аналогією для структурно-атрибу-тив-ної моделі знань, а саме на основі:

4.1 критеріїв покомпонентної структурної аналогії та структурної анало-гії властивостей;

4.2 різних способів обчислення інтегральної оцінки подібності складе-но-го об’єкта до деякої множини прототипів;

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

5. Створені модулі програмного комплексу розв’язання задач методами правдо-подібного виведення та програмної системи АНАЛОГІЯ, які реалізують механізми представлення структурно-атрибутивних моделей знань, та алгоритми виведення за аналогією.

6. Програмний комплекс був використаний для розв’язання задач прогнозування нових хімічних сполук і створення нових керамічних матеріалів.

З наведених результатів випливають такі висновки:

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

· використання теорії мультимножин дозволяє спростити опис виведення за аналогією;

· запропоновані методи виведення за аналогією на основі структурно-атри-бу-тив-ної моделі знань дали змогу покращити точність отриманих результатів на 5-10%;

· як показують проведені експерименти, висока точність отриманих результатів (90  %) підтверджує доцільність використання створеного програмного комплексу для вирішення широкого кола аналітичних задач.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

АНОТАЦІЯ

Величко В.Ю. Розв’язання аналітичних задач в дискретних середовищах методами виведення за аналогією. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – автоматизовані системи управління та прогресивні інформаційні технології. – Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2004.

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