МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ХЕРСОНСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

УДК 681.32

ДІДИК ОЛЕКСІЙ ОЛЕКСАНДРОВИЧ

МЕТОДИ ТА АЛГОРИТМИ ПОБУДОВИ МОДЕЛЕЙ ПРОЦЕСІВ УПРАВЛІННЯ

НА ОСНОВІ РЕТРОСПЕКТИВНИХ ДАНИХ

05.13.06. — Автоматизовані системи управління

та прогресивні інформаційні технології

АВТОРЕФЕРАТ

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

кандидата технічних наук

ХЕРСОН 2001

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

Робота виконана в Херсонському державному технічному університеті Міністерства освіти і науки України.

Науковий керівник: Кандидат технічних наук, професор, Рогальський Франц Борисович, Херсонський державний технічний університет, проректор, завідувач кафедри інформатики та обчислювальної техніки

Офіційні опоненти: Доктор технічних наук, професор, Петров Едуард Георгійович, Харківський державний технічний університет радіоелектроніки, завідувач кафедри системотехніки Доктор технічних наук, професор, Кокошко Володимир Семенович, Одеський інститут сухопутних військ, кафедра військової кібернетики

Провідна установа Державний аерокосмічний університет ім. Н.Є. Жуковського “ХАІ”

Захист відбудеться 11.05.2001 p. о 14 годині на засіданні спеціалізованої вченої ради К67.052.01 при Херсонському державному технічному університеті за адресою: 73008, м. Херсон, Бериславське шосе, 24, корп. 1. ауд. 223

З дисертацією можна ознайомитися у бібліотеці Херсонського державного технічного університету за адресою: 73008, м. Херсон, Бериславське шосе, 24, корп. 1.

Автореферат розісланий 10.04.2001 р.

Вчений секретар спеціалізованої вченої ради Костін В.О.

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

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

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

У зв'язку з цим успішно розвивається науковий напрямок — системи підтримки прийняття рішень (СППР). Основною задачею цього напрямку є розробка програмно-апаратних засобів, що надають допомогу фахівцям у процесі підготовки і вибору раціональних рішень у конфліктних ситуаціях на основі емпіричних знань, накопичених експертами, а також отриманих самою системою в процесі функціонування.

З іншого боку, бурхливий розвиток систем керування базами даних (СУБД) привів до загальної комп'ютеризації буквально всіх областей людської діяльності. Бази даних (БД), фактично, стали величезним сховищем, у якому зберігається інформація про всі аспекти діяльності людини. Тому з кінця 80-х почала розвиватися нова область дослідження, що одержала назву добування знань з баз даних і переробка даних (Knowledge Discovery in Databases and Data Mining). Спочатку це була спроба перенести методи й алгоритми машинного навчання на великі бази даних, тобто БД розглядалися як великі навчальні вибірки. Але надалі, розвиваючись як окрема область знань, у рамках цієї технології були розроблені і продовжують розвиватися методи, що дозволяють використовувати бази даних зовсім по-новому. Іншими словами, бази даних являють собою великі вибірки ретроспективних даних, які можна використовувати як джерело знань для систем підтримки прийняття рішень з метою побудови моделей процесів управління.

За оцінками багатьох вітчизняних і закордонних фахівців створення СППР у найближчі 5—10 років стане основним напрямком розвитку проблемно-орієнтованих програмних засобів, що забезпечують ефективне застосування обчислювальної техніки в різних сферах людської діяльності, які пов'язані із ПР.

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

У процесі роботи над дисертаційним дослідженням автор спирався на праці фахівців, які спеціалізуються в цій проблематиці: В.М. Глушкова, О.Д. Поспєлова, О.О. Первозванського, В.І. Скуріхіна, Ю.Р. Валькмана, J.E.J.J.Z.wlak.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційне дослідження проводилося в Херсонському державному технічному університеті в рамках розробки системи інформаційного забезпечення підготовки і прийняття рішень органів адміністративного управління згідно “Програми реформування економіки і соціально-економічного розвитку області” (розпорядження глави Херсонської обласної державної адміністрації №312 від 28.05.1999). Автор взяв участь у даній роботі як виконавець.

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

1. Обґрунтувати вибір технології добування знань з баз даних (ДЗБД) для отримання й обробки знань про процеси управління.

2. Розробити методи й алгоритми побудови моделей процесів управління на основі ретроспективних даних з використанням технології ДЗБД.

3. Розробити елементи СППР із використанням нових методів і алгоритмів.

4. Впровадити розроблені елементи в СППР управління Міністерства з надзвичайних ситуацій у Херсонський області.

5. Оцінити ефективність застосування розроблених методів і алгоритмів та адекватність отриманих моделей.

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

1. Розроблено елементи проблемно-орієнтованого інструментарію СППР у вигляді методів, алгоритмів і програм, що реалізуються за допомогою прогресивних інформаційних технологій.

2. Розроблено новий метод кластеризації баз даних, заснований на використанні запропонованих мір розрідженості кластера, відстані і якості кластеризації баз даних.

3. Запропоновано нове визначення відношення нерозрізненості об'єктів через побудову відношення подібності елементів наближеної множини.

4. Отримано удосконалену графову модель процесів управління за рахунок введення додаткових вагових коефіцієнтів і функцій виведення умов виконання операцій процесу.

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

У процесі дисертаційного дослідження отримані наступні практичні результати:

1. Розроблено алгоритм ієрархічної агломеративної кластеризації баз даних з використанням показників якості кластеризації .

2. Розроблено алгоритм виявлення підмножини значимих атрибутів з використанням отриманої міри нерозрізненості об'єктів.

3. Розроблено алгоритм формування множини характеристичних правил кластеризації.

4. Розроблено алгоритм побудови графових моделей процесів управління на основі ретроспективних даних.

Практична цінність роботи полягає у тому, що розроблені методи і алгоритми реалізовано у вигляді прикладної програмної системи (ППС), яка впроваджена в управлінні Міністерства з надзвичайних ситуацій у Херсонській області. Це дозволило істотно зменшити навантаження на ОПР і підвищити ефективність прийнятих рішень за рахунок поліпшення процедур побудови набору альтернативних рішень.

Особистий внесок здобувача. Усі положення, що виносяться на захист, належать особисто автору і не містять результатів чи ідей, розробок, що належать співавторам, разом з якими опубліковані наукові праці. У роботі [2] автору належить підхід до побудови СППР із використанням системи добування знань із БД; в роботі [5] автором запропоновано підхід до використання асоціативних правил для переробки неструктурованої інформації; в роботі [8] автору належать методи добування знань з баз даних на основі теорії наближених множин; в працях [11, 13] автору належить метод побудови моделі процесів на основі ретроспективних даних; в роботі [10] автором запропоновано метод боротьби з шумами в даних з використанням апарату теорії наближених множин; в роботі [3] автором запропонована загальна структура системи добування знань з баз даних; в роботі [9] автору належить метод формування стислих представлень знань; у працях [7, 6, 4] автору належить алгоритм визначення ступенів релевантності та суперечливості даних в базах даних; в роботі [1] автором запропоновано підхід до використання теорії нечіткої подібності для представлення знань в інтелектуальних системах.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися на міжнародній конференції “Створення, інтеграція, використання інформаційних ресурсів інноваційного розвитку” (м. Київ, ); на ІІІ міжнародній науковій конференції “Теорія і техніка передачі, прийому й обробки інформації” (м. Харків, ); на семінарах наукової ради НАН України з проблем "Кібернетика", "Прикладні проблеми інформатики" (м. Херсон, ); науково-методичної конференції "Інформаційні технології в освіті і управлінні" (м. Н. Каховка, ); наукової конференції "Комп'ютерне моделювання й інформаційні технології в природничих науках" (м. Кривої Ріг, ); на II міжнародній науковій конференції “Інформаційна інфраструктура вищих навчальних закладів” (м. Херсон, ).

Публікації. Основні результати дослідження викладені в 13 друкованих роботах.

Структура й обсяг дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, списку використаних джерел з 135 найменувань, одного додатку, 30 малюнків, 7 таблиць. Загальний обсяг роботи складає 190 сторінок, у тому числі 150 сторінок основного тексту.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

Проведено аналіз традиційних систем та методів одержання експертних знань та визначено їх недоліки. Показано, що процес одержання знань є самим “вузьким” місцем при побудові СППР, тому що розроблювачам СППР доводиться постійно зіштовхуватися з такими проблемами як організаційні неузгодженості; невдалі методи одержання знань, що не збігаються зі структурою знань у даній галузі; неадекватні моделі (мови) для представлення знань; невміння інженера по знаннях налагодити контакт з експертом; відсутність цілісної системи знань у результаті витягу тільки “фрагментів” та ін.

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

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

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

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

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

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

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

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

З метою подолання зазначених недоліків запропоновано використовувати апарат теорії наближених множин.

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

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

Запропоновано загальний підхід до побудови відношення подібності об'єктів, що ґрунтується на виконанні двох умов:

· достатня кількість атрибутів об'єктів, які порівнюються, повинна бути подібна;

· жоден з атрибутів, який не є подібним, не повинен накладати обмежень на рівень подібності об'єктів.

Частковий ступінь подібності, що позначається як Cj(x,y), відбиває рівень подібності значень атрибута ai (i=1,…,n) об'єктів x і y. Це функція, яка повертає значення з множини {0,1} чи з інтервалу [0,1], де:

· Cj(x,y)=0, якщо і тільки якщо значення атрибута aj цілком не подібні;

· Cj(x,y)=1, якщо і тільки якщо значення атрибута aj еквівалентні для обох об'єктів.

Часткові ступені подібності виводяться з урахуванням різниць у природі атрибутів об'єктів, що порівнюються.

Частковий ступінь неузгодженості по подібності, що позначається як Dj(x,y), відображає рівень обмежень, що накладаються значеннями атрибута aj (j=1,…,n) на рівень подібності об'єктів x і y. Це функція, яка повертає значення з множини {0,1} чи з інтервалу [0,1], де:

· Dj(x,y)=0, якщо і тільки якщо значення атрибута aj не надають негативного впливу на рівень подібності об'єктів x і y;

· Dj(x,y)=1, якщо і тільки якщо взагалі неможливо говорити про подібність значень атрибута aj об'єктів x і y.

Загальний ступінь подібності, що позначається C(x,y), відбиває рівень подібності об'єктів x і y. Це функція, яка повертає значення з множини {0,1} чи з інтервалу [0,1], де:

· C(x,y)=0, якщо і тільки якщо об'єкти x і y цілком не подібні;

· C(x,y)=1, якщо і тільки об'єкти x і y ідентичні.

Загальний ступінь подібності об'єктів x і y утворюється в результаті агрегування n часткових ступенів подібності:

, (1)

де g є функція, що задовольняє наступним умовам:

· g(1,...,1)=1,

· g(0,...,0)=0.

Функція g може бути обрана з числа двох наступних сімейств операторів:

· оператори усереднення (компромісні), такі як сума ваг:

, (2)

де wj є відносна власна вага, пов'язана з aj.

· оператори кон'юнкції, такі як min чи добуток:

(3)

або

. (4)

Загальний ступінь неузгодженості, що позначається як D(x,y), відбиває рівень обмежень, які накладаються на подібність об'єктів x і y значеннями всіх атрибутів двох об'єктів. Це функція, якаповертає значення з множини {0,1} чи з інтервалу [0,1], де:

· D(x,y)=0, якщо і тільки якщо жоден з атрибутів не накладає обмежень на подібності об'єктів x і y;

· D(x,y)=1, якщо і тільки якщо взагалі неможливо говорити про подібність об'єктів x і y.

Загальний ступінь неузгодженості утворюється в результаті агрегування n часткових ступенів неузгодженості атрибутів:

, (5)

де h є функція, яка задовольняє наступним умовам:

· якщо і тільки якщо існує хоча б один такий, що Dj(x,y)=1;

· h(0,…,0)=0...

Функція h може бути обрана з числа наступних операторів:

(6)

або

(7)

або

. (8)

Ступінь подібності об'єктів x і y є результатом агрегування загальних ступенів подібності і неузгодженості C(x,y) і D(x,y):

, (9)

де f є функція, що задовольняє наступним умовам:

· ,

· ,

· ,

і може бути обрана з числа наступних операторів:

(10)

або

. (11)

Розглянуто питання використання апарату теорії наближених множин для розв'язання задачі визначення підмножини значимих атрибутів і класифікації в умовах неповноти та неточності даних.

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

Виділено основні етапи розв'язання поставленої задачі і визначена їхня послідовність:

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

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

3. Побудова набору характеристичних правил для кожної групи даних.

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

5. Обчислення вагових коефіцієнтів і функцій визначення умов виконання операцій процесу, які визначені на дугах моделі.

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

· необхідність апріорного визначення експертом граничного значення подібності;

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

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

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

· розрідженість кластеризації, що є функцією від розрідженості всіх кластерів у кластеризації;

· якість кластеризації, що є функцією від перших двох показників.

Відстань кластеризації визначено як

D(C), (12)

де d(ci,cj) – відстань між кластерами ci і cj у кластеризації C = .

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

Розрідженість кластеризації визначено як

R(C), (13)

де r(ci) - розрідженість кластера, яка визначена як

, (14)

де hmed є центр мас кластера c.

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

Q(C). (15)

На основі вищенаведених показників розроблено алгоритм ієрархічної агломеративної кластеризації. Алгоритм одержує в якості вхідного параметру множину О з n об'єктів і робить n кластеризацій об'єктів, починаючи з тривіальної кластеризації C0, яка складається з одноелементних кластерів. На виході алгоритм видає кластеризацію Cbest, що є кращою кластеризацією з погляду якості кластеризації. Використання показника якості звільняє від необхідності апріорного визначення граничного значення подібності, а також дозволяє використовувати кілька мір відстані між кластерами.

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

Розроблено алгоритм обчислення оптимальної підмножини значимих атрибутів B, в основу якого покладено ступінь релевантності атрибута. Ступінь релевантності визначено в такий спосіб:

, (16)

де B – підмножина умовних атрибутів,

D – множина атрибутів рішення.

Показник k(B,D) відбиває ступінь залежності між B и D і визначений в такий спосіб:

. (17)

Ступінь релевантності відображає зміну рівня залежності між B і D у результаті додавання до множини B атрибуту a.

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

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

Для вказаних цілей використовується поняття матриці рішення , яка визначена у такий спосіб:

, (18)

де є об'єкт, що належить кластеру ci кластеризації C бази даних, тобто та і=1,2,…,=r;і j=1,2,…,=f...

Множина DMij містить усі пари виду “атрибут=значення” для тих атрибутів, що не подібні з урахуванням граничного значення подібності для об'єктів і . Іншими словами, DMij містить усю необхідну інформацію для визначення різниці між об'єктами, що належать кластеру ci, та іншими об'єктами БД.

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

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

Процес управління розглядається як послідовність окремих операцій. Формально модель у вигляді графа представляється декартовим добутком , де E – множина взаємозв'язків операцій, зображених дугами, а M и T відповідно семантичні та часові оцінки вершин графа. Дуги графа представляють потенційні переходи управління від однієї операції до іншої. (рис.1).

Рис. 1. Модель процесу управління.

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

Виконання процесу – це список подій (P, A, E, T, O), упорядкований за часом, де P є ідентифікатором виконання процесу, А є ідентифікатором операції, є типом події, T є часом, коли подія відбулася, і O = o(A) є вихідні дані функції виведення умов виконання операції.

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

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

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

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

ППС реалізує розроблені алгоритми побудови моделей процесів управління на основі ретроспективних даних, що зберігаються в БД. Запропоновано конструктивні рішення по реалізації взаємодії програмних модулів у системі.

ППС реалізує наступні функції:

· кластеризацію БД, в якій зберігаються дані про гасіння пожеж природного походження у минулому, з метою виявлення груп пожеж, що виконувалися у подібних умовах;

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

· формування множини характеристичних правил, що описують окремі групи пожеж, які отримані в результаті проведення кластеризації БД;

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

· зберігання отриманих моделей у спеціальній БД для подальшого використання;

· графічне відображення даних і моделей, що отримані на кожному етапі роботи системи.

Запропоновано методику оцінки ефективності функціонування СППР на основі показників середнього часу розв'язання задачі, інформаційної наповненості та інтересності, а також адекватності отриманих моделей процесів управління. Зазначені показники є “нечіткими”, їх точна кількісна оцінка ускладнена і може бути визначена лише приблизно за умови узагальнення набору часткових показників.

За допомогою запропонованої методики проведено порівняльний аналіз СППР, побудованої з використання системи ретроспективного моделювання та без неї. Для проведення порівняльного аналізу були використані дані про ліквідацію пожеж природного походження у лісних масивах Херсонської області.

ВИСНОВКИ

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

1. Проведено аналіз існуючого рівня розвитку засобів підтримки прийняття рішень, що використовуються для розв'язання задач управління у складних системах. Обґрунтовано правильність і доцільність застосування технології добування знань з баз даних для побудови системи ретроспективного моделювання в СППР.

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

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

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

5. Розроблено прикладну програмну систему ретроспективного моделювання процесів управління, що програмно реалізує розроблені алгоритми.

6. Запропоновано методику оцінки ефективності функціонування СППР на основі показників середнього часу розв'язання задачі, інформаційної наповненості та інтересності, а також оцінки адекватності отриманих моделей. За допомогою зазначеної методики проведено порівняльний аналіз СППР, що побудовані з використанням системи ретроспективного моделювання та без неї. Аналіз показав, що запропонований підхід дозволив збільшити ефективність прийняття рішень, наочність та зручність виведення інформації тощо.

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Ходаков В.Е, Шерстюк В.Г., Дидык А.А., Степанский К.Г., Козуб Н.А. Приложение теории нечеткого подобия к представлению знаний в интеллектуальных системах // Вестник Херсон. гос. техн. ун-та. – Херсон, 1997. – №2(2) – с. 138-140.

2. Ходаков В.Е, Шерстюк В.Г., Дидык А.А., Степанский К.Г. Использование internet-технологий для построения информационно-аналитических систем органов регионального управления // Создание, интеграция, использование информационных ресурсов инновационного развития: Тез. докл. и сообщ. междунар. конф., Киев, 18-19 дек. 1997 г. – К., 1997 – с. 23-24.

3. Ходаков В.Е., Шерстюк В.Г., Дидык А.А., Степанский К.Г., Козуб Н.А. Моделирование индуктивных рассуждений в системах извлечения знаний корпоративных информационных систем // Вестник Херсон. гос. техн. ун-та. – Херсон, 1998. – №1(3) – с. 21-24.

4. Ходаков В.Е., Шерстюк В.Г., Дидык А.А., Степанский К.Г., Козуб Н.А. Механизмы возникновения и устранения диссонанса в процессе принятия решений // Вестник Херсон. гос. техн. ун-та. – Херсон, 1998. – №1(3) – с.117-122.

5. Шерстюк В.Г., Дидык А.А., Степанский К.Г. Технологии переработки неструктурированной информации в корпоративных интеллектуальных системах поддержки принятия решений // Теория и техника передачи, приема и обработки информации: Тез. докл. III междунар. науч. конф., Харьков, 1998 г.– Харьков, 1998 – с. 48-49.

6. Ходаков В.Е., Шерстюк В.Г., Дидык А.А., Степанский К.Г., Мартынов В.В. Методы оценки степени противоречивости знаний с помощью отношения диссонанса // Радиоэлектрон. и информат. – Харьков, 1998. – №1(1) – с.156-162.

7. Ходаков В.Е., Шерстюк В.Г., Дидык А.А., Степанский К.Г., Мартынов А.Н. Методы оценки релевантности информационных структур в базах знаний // Пробл. бионики. – Харьков, 1998. – Вып.49 – с. 186-195.

8. Ходаков В.Е., Шерстюк В.Г., Дидык А.А. Применение приближенных множеств для извлечения знаний в интеллектуальных системах поддержки принятия решений // Вестник Херсон. гос. техн. ун-та. – Херсон, 1999. – №1(5) – с. 17-18.

9. Ходаков В.Е., Шерстюк В.Г., Дидык А.А. Извлечение знаний и индуктивные базы данных // Вестник Херсон. гос. техн. ун-та. – Херсон, 1999. – №3(6) – с. 159-162.

10. Шерстюк В.Г., Тутушкин Ю.И., Дидык А.А., Иоанесян А.Н. Извлечение контекстных знаний в интеллектуальных системах поддержки принятия решений в условиях неполноты и зашумленности данных // Вестник Херсон. гос. техн. ун-та. – Херсон, 1999. – №3(6) – с. 168-174.

11. Рогальский Ф.Б., Шерстюк В.Г., Дидык А.А., Лубяный В.З. Использование извлечения знаний для построения моделей бизнес-процессов в системах управления проектами // Вестник Херсон. гос. техн. ун-та. – Херсон, 2000. – №1(7) – с. 149-151.

12. Дидык А.А. Об использовании концептуальной кластеризации для анализа процессов ликвидации чрезвычайных ситуаций // Вестник Херсон. гос. техн. ун-та. – Херсон, 2000. – №3(9) – с. 165-167.

13. Рогальский Ф.Б., Шерстюк В.Г., Дидык А.А. Использование технологии извлечения знаний из баз данных для построения моделей бизнес-процессов в корпоративных информационных системах // Сборник научных трудов II международной научной конференции “Информационная инфраструктура высших учебных заведений”. – Херсон, 2000. – т. 2 – с. 255-258.

АНОТАЦІЯ

Дідик О.О. Методи і алгоритми добування моделей процесів з баз даних. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – “Автоматизовані системи управління і прогресивні інформаційні технології”. – Херсонський державний технічний університет, Херсон, 2001.

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

Як механізм для класифікації даних в умовах неповноти і неточності використовується апарат теорії наближених множин. Визначено нову міру нерозрізненості об'єктів, в основі якої лежить відношення подібності елементів множини. Запропоновано нові визначення мір подібності окремих атрибутів і об'єктів у цілому.

Дано нові визначення показникам розрідженості, відстані і якості кластеризації. Розроблено алгоритм кластеризації бази даних, заснований на використанні зазначених показників.

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

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

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

ABSTRACT

Didyk A.A. Methods and algorithms of processes models discovery in databases. - Manuscript.

Thesis on competition of the candidate degree in technical science on a speciality 05.13.06 - Automated control systems and progressive information technologies. - Kherson state technical university, Kherson, 2001.

This thesis is devoted to questions of technique development of a processes models construction, being grounded on the retrospective data, which describe passing these processes in the past. The purpose of a technique development is the rise of decision support systems efficiency due to insertion of an additional subsystem of processes information simulation that use the retrospective data stored in databases.

As the data classification mechanism in conditions of the incompleteness and inaccuracy the theory of rough sets is used. New measure of objects indiscernibility is defined. New definitions of similarity measures of separate attributes and objects as a whole are offered.

The data grouping method based on a method of conceptual clustering is offered. New definitions of clustering measures are given: rarefaction measure, distance measure and quality measure of clustering.

New method and algorithm for processes models construction is developed which display a sequence of transitions in time from one state to another. The model represents a digraph, on which sites are displayed states, and on arcs - operations that have resulted in transition from one state to another. The weight coefficients indicating possibility of such transition are defined on arcs of the graph. Functions definition also is given which mirror dependence of those or other operations on states of an environment. It's shown, that the constructed model is causal.

The program implementation of a processes simulation subsystem is developed. Estimation of an overall performance of a processes simulation subsystem is given with the help of a special assessment technique of decision support systems works.

Keywords: decision support systems, simulation of processes, knowledge discovery in databases.

АННОТАЦИЯ

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 – “Автоматизированные системы управления и прогрессивные информационные технологии”. – Херсонский государственный технический университет, Херсон, 2001.

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

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

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

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

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

Ключевые слова: системы поддержки принятия решений, моделирование процессов, извлечение знаний из баз данных.

Відповідальний за випуск Костін В.О.

Підписано до друку 12.06.2000. Формат 60х90/16

Папір офсетний. Умовн.-друк. аркушів 1,00

Тираж 100 прим. Замовлення №234

Надруковано у видавництві ХДТУ,

73008, м. Херсон, Бериславське шосе, 24