Підхід до обробки інформації на основі деревоподібних баз знань зі змішаною схемою виведення

Размещено на http://www.allbest.ru/

Національний технічний університет України

"Київський політехнічний інститут"

05.13.06 - "Автоматизовані системи управління та прогресивні інформаційні технології"

УДК 681.325

АВТОРЕФЕРАТ

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

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

підхід до обробки інформації на основі деревоподібних баз знань зі змішаною схемою виведення

Терновой Максим Юрійович

Київ 2007

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

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

Науковий керівник: доктор технічних наук, професор ГЛОБА Лариса Сергіївна, Національний технічний університет України "Київський політехнічний інститут", завідувач кафедри інформаційно-телекомунікаційних мереж.

Офіційні опоненти: доктор технічних наук, професор ТЕЛЕНИК Сергій Федорович, Національний технічний університет України "Київський політехнічний інститут", завідувач кафедри автоматики та управління в технічних системах.

доктор технічних наук, професор ЖОЛТКЕВИЧ Григорій Миколайович, Харківський національний університет ім. В.Н. Каразіна, завідувач кафедри теоретичної і прикладної інформатики.

Провідна установа: Національний аерокосмічний університет ім. М.Є. Жуковського "Харківський авіаційний інститут" Міністерства освіти і науки України.

Захист відбудеться "21" травня 2007 р. о 15 годині на засіданні спеціалізованої вченої ради Д 26.002.03 у Національному технічному університеті України "Київський політехнічний інститут" за адресою: 03056, м. Київ, пр. Перемоги, 37, навчальний корпус №35, аудиторія 006.

З дисертацією можна ознайомитись в науково-технічній бібліотеці Національного технічного університету України "Київський політехнічний інститут" за адресою: 03056, м. Київ, пр. Перемоги, 37.

Автореферат розісланий "17" квітня 2007 р.

Вчений секретар спеціалізованої ради Д 26.002.03, д.т.н, проф. Новіков О.М.

Загальна характеристика роботи

організаційний складний інформація

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась згідно з планами наукових досліджень кафедри інформаційно-телекомунікаційних мереж Інституту телекомунікаційних систем в рамках держбюджетних тем: 2435 (номер державної реєстрації 0100U000954), 2606 (номер державної реєстрації 0103U000285), 2567-П (номер державної реєстрації 0102U003833), 2606-П (номер державної реєстрації 0103U000285), 2819 (номер державної реєстрації 0105U001071) та госпдоговірних робіт: "Розробка АІПС Чергова Частина", (дог. № 28\В) (номер державної реєстрації 0103U000526), "Забезпечення функціонування й удосконалення Центрального та регіональних чорнобильських банків даних всіх категорій постраждалих громадян (ЧБД)" (дог. № 25-1/11нсі-02) (номер державної реєстрації 0104U010440), що виконувалася у відповідності до:

1. Постанова Верховної Ради України від 20.03.2000 р. №1681-ІІІ "Про парламентські слухання щодо чотирнадцятої річниці Чорнобильської катастрофи";

2. Доручення Кабінету Міністрів України від 6.05.2000 р. №36\707;

3. Постанова Кабінету Міністрів України від 4.02.1997 р. № 135 "Про перевірку правильності видачі посвідчень "Учасник ліквідації наслідків аварії на Чорнобильській АЕС";

4. Постанови Верховної Ради від 26.04.2001 р. № 2404-ІІІ "П'ятнадцята річниця Чорнобильської катастрофи. Досвід подолання.";

5. Доручення КМ від 16.05.2001 р. № 6406\3 .

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

Для досягнення мети дослідження було поставлено та вирішено такі основні задачі:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) структура та алгоритми функціонування інформаційно-аналітичної системи департаменту Державтоінспекції МВС України, а також математичні методи оцінки інформації, які можуть в ній використовуватися;

2) підходи до створення інформаційних ресурсів корпорації;

3) модель комплексної оцінки складного об'єкту в умовах невизначеності;

4) принцип побудови програмної компоненти обробки інформації на базі Intranet технологій, її структурна схема та програмна реалізація;

5) алгоритм динамічного формування SQL-запитів;

6) підхід до зведення нечіткої бази знань до деревоподібної структури та обчислення складності виведення на основі деревоподібної та невпорядкованої нечітких баз знань.

Апробація результатів дисертації. Основні положення і результати дисертаційної роботи були представлені, повідомлені й одержали схвалення на ІІІ Міжнародній науково-технічній конференції "Электронные ресурсы: проблемы формирования, обработки, распространения и использования- 2002" (Київ, 2002), IV-VII Міжнародних науково-практичних конференціях "Современные информационные и электронные технологии" (Одеса, 2003-2006), Міжнародній науково-технічній конференції "Проблемы физической и биомедицинской электроники -2003" (Київ, 2003), Міжнародній науково-технічній конференції "Сучасні проблеми радіоелектроніки, телекомунікацій та комп'ютерної інженерії - 2006" (Львів - Славсько, 2006), Міжнародній конференції "СВЧ-техника и телекоммуникационные технологии. Крымико'2006" (Севастополь, 2006).

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

Структура і обсяг дисертації. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел з 157 найменувань, 7 додатків. Загальний обсяг дисертації 180 сторінок, в тому числі 145 сторінок основного тексту та 14 сторінок використаних джерел. Робота містить 28 рисунків, 5 таблиць. Додатки займають 21 сторінку.

Основний зміст дисертації

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

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

Визначено, що для моделювання швидкоплинних локальних у часі процесів застосування математичних методів і моделей, які потребують навчання для виявлення закономірностей функціонування системи неможливо. У цьому випадку основним способом формування моделі в умовах притаманних САдС стає формалізація експертних знань і представлень у вигляді баз знань (БЗ), з використанням методів теорії нечітких множин та нечіткої логіки. Основна ідея полягає в тому, що при настроюванні нечіткої БЗ, можна ідентифікувати нелінійні залежності з необхідною точністю. Перевагою даного підходу є також можливість урахування недетермінованих впливів, структурних і якісних змін у складі системи в процесі моделювання. Також дуже корисною особливістю цього підходу є можливість представлення результатів моделювання у відносно простій і наочній формі, яка буде зрозумілою людині. До недоліків цього підходу можна віднести невпорядкованість та надлишковість початкової нечіткої БЗ, яка формується виходячи з експертних знань, та внаслідок цього важкість відповідей на питання “чому?” і “як?”, тобто неможливість визначення всієї ієрархії параметрів, що впливають на значення виходу системи. Це ускладнює процес прийняття рішень щодо необхідних напрямків управління для покращення ситуації.

При побудові моделей для проведення обробки інформації в САдС з відносно постійним складом учасників на середньо- і довгостроковому часовому інтервалі з'являється можливість застосовувати в якості вихідних даних більш об'єктивну інформацію, а саме інформацію про стан системи в періоди її стійкості. Тому додатково до сформованої за допомогою методів нечіткої логіки моделі можна використовувати методи теорії нечітких нейронних мереж та еволюційних обчислень для проведення формування структури та настроювання параметрів функцій належності (ФН). Такий підхід дає можливість значно зменшити суб'єктивність і суперечливість експертних оцінок і внаслідок цього поліпшити якість прогнозування.

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

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

Другий розділ присвячено розробці підходу до обробки інформації в САдС. Обробка інформації здійснюється за допомогою математичної моделі об'єкту, яка подається у вигляді нечіткої логічної моделі. В такій моделі виділяються три частини: мова, система аксіом та правила виведення. У випадку моделі сформованої засобами нечіткої логіки мова представляє собою лінгвістичні змінні (ЛЗ), їх терм-множини та структуру правил, до аксіом відноситься нечітка БЗ, яка в загальному випадку є невпорядкованою, а правила виведення задаються формулами за допомогою яких визначається значення ФН термів ЛЗ.

З метою покращення обробки інформації сформульовано задачу зведення нечіткої БЗ до деревоподібної структури.

Дано:

1) - невпорядкована нечітка БЗ, де

- -е правило для визначення -го терму ЛЗ з ідентифікатором ,

- ЛЗ, - ідентифікатор ЛЗ,

()- номер ЛЗ в лівій частині правила,

-терм ЛЗ з номером .

2) - множина з уведеною на ній ієрархією, що відповідає ієрархії оцінювання ситуації в САдС

3) Відповідність елементів ієрархії оцінювання ситуації в САдС лінгвістичним змінним ,

Отримати:

- деревоподібна нечітка БЗ, де

(1)

- ЛЗ, - номер ЛЗ на рівні ,

- терм ЛЗ з номером ,

- номер ЛЗ у рядку кон'юнкцій для визначення -го терму -тої ЛЗ -го рівня,

- кількість рядків кон'юнкцій,

- номер терму ЛЗ -го рівня.

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

Тоді для кожного набору правил, які відповідають одному терму ЛЗ проводиться композиція, яка полягає у знаходженні максимуму серед всіх отриманих значень ФН (2).

де - значення ФН терму .

Сформована таким чином БЗ буде мати деревоподібну структуру (рис. 2). В ній можна виділити дві частини: нижню і верхню. Зауважимо, що виходячи з особливостей ПО застосовувати автоматичні механізми формування та настроювання можливо лише для нижньої частини деревоподібної нечіткої БЗ. Це обумовлено тим, що адекватну вибірку значень вхідних та відповідних результуючих змінних можна забезпечити лише для частин нижнього рівня.

В роботі запропоновано розглядати нижню частину БЗ у вигляді нечіткої нейромережі аналогічної NEFCLASS, що дозволило використати розроблені для нечітких нейромереж механізми навчання.

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

Твердження 2.1 Алгоритм нечіткого виведення на основі невпорядкованої нечіткої БЗ має обчислювальну складність

,

де - загальна кількість ЛЗ на рівні,

- розмір терм-множин ЛЗ,

- кількість рівнів.

Твердження 2.2 Алгоритм нечіткого виведення на основі деревоподібної нечіткої БЗ має обчислювальну складність

,

де - загальна кількість ЛЗ на рівні,

- розмір терм-множин ЛЗ,

- кількість рівнів.

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

Дано:

Отримати:

де - множина вхідних змінних,

- результуюча змінна,

- вхідна змінна, що визначила значення результуючої змінної.

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

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

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

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

Твердження 2.4 Якщо вірні наступні умови:

1) деревоподібна нечітка БЗ побудована для вирішення задачі класифікації;

2) належність класу визначається шляхом нечіткого виведення Мамдані для задач класифікації;

3) часткові нечіткі БЗ, що визначають залежність ЛЗ вище другого рівня від ЛЗ попереднього рівня є повними;

4) значення ФН термів ЛЗ другого рівня, які визначають поточні значення цих ЛЗ, більші ніж значення ФН інших термів ЛЗ другого рівня

То:

1) верхню частину деревоподібної нечіткої БЗ можна розглядати як класичну логічну БЗ, тобто розв'язки задачі класифікації при виведенні на основі класичної логічної БЗ і на основі нечіткої БЗ будуть збігатися;

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

Твердження 2.5 Якщо вірні умови:

1) належність класу визначається шляхом нечіткого виведення Мамдані для задач класифікації;

2) для сусідніх термів всіх ЛЗ першого рівня ФН визначені таким чином, що вони перетинаються на однаковій висоті;

3) для кожної ЛЗ встановлено ранжування термів за важливістю;

4) у випадках, коли значення відповідної до входу ФН знаходиться на перетині функцій, то робиться зменшення значення ФН терму з меншою важливістю;

5) часткові нечіткі БЗ, що визначають залежність ЛЗ другого рівня від ЛЗ першого рівня, є повними

То:

виконується умова 4 Твердження 2.4.

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

Запропоновано метод обробки інформації на основі деревоподібних нечітких БЗ зі змішаною схемою виведення, який складається з підготовки нечіткої БЗ, сутність якої полягає в зведенні нечіткої БЗ до деревоподібної структури, її настроюванні та подальшому використанні для обробки інформації. Цей метод дозволяє зменшити обчислювальну складність виведення без втрати значення ФН результуючого терму модельованої ЛЗ за рахунок використання удосконаленої нечіткої логічної моделі з деревоподібною нечіткою БЗ, а, по-друге, використання змішаної, а саме чіткої і нечіткої, схеми виведення на основі деревоподібної нечіткої БЗ.

Сформульована задача обробки інформації на основі деревоподібних нечітких БЗ.

Дано:

I. Математична модель об'єкту:

1) - множина вхідних змінних,

2) - множина ЛЗ, що відповідають ,

3) , - терм-множини ЛЗ 1-го рівня,

4) - множина ФН, відповідних до термів ЛЗ 1-го рівня, за якими проводиться фаззіфікація ,

5) - множина ЛЗ -го рівня,

6) , - терм-множини ЛЗ -го рівня,

7) - множина ФН, відповідних до термів ЛЗ -го рівня (2),

8) - результуюча змінна,

9) - ЛЗ, що відповідає ,

10) - терм-множина ЛЗ ,

11) - нечітка деревоподібна БЗ,

12) - часткова БЗ (1)

II. Вектор фіксованих значень вхідних змінних об'єкта

Знайти:

Результуюче значення та вхідний параметр , який визначив таке значення.

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

1. Отримати вхідні данні.

2. Визначити значення ФН термів ЛЗ першого рівня, за допомогою функцій фаззіфікації, якщо дані подаються в чисельному вигляді, або експертно, якщо дані подаються в якісному вигляді.

3. Визначити значення ФН термів ЛЗ другого рівня за допомогою нечіткого виведення на основі нижньої частини деревоподібної нечіткої БЗ.

4. Якщо умова 4 твердження 2.4 вірна, а саме значення ФН термів ЛЗ другого рівня, які визначили поточні значення цих ЛЗ, більші ніж значення ФН інших термів ЛЗ другого рівня, то перехід на п. 5, в протилежному випадку п. 7.

5. Визначити значення модельованої ЛЗ за допомогою логічного виведення на основі верхньої частини деревоподібної БЗ.

6. Визначити результуюче значення ФН терму модельованої ЛЗ обчисленням мінімуму серед значень ФН термів ЛЗ другого рівня, які визначають належність до певного класу. Перехід на п. 8.

7. Визначити значення модельованої ЛЗ за допомогою нечіткого виведення на основі верхньої частини деревоподібної БЗ.

8. Вивести значення модельованої ЛЗ та значення результуючої ФН.

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

Дано:

1) - множина вхідних змінних,

2) - множина ЛЗ, що відповідають ,

3) , -терм-множини ЛЗ 1-го рівня,

4) - множина ФН, відповідних до термів ЛЗ 1-го рівня, за якими буде проводитись фаззіфікація,

5) - множина ЛЗ 2-го рівня,

6) - терм-множина ЛЗ ,

7) - вибірка для побудови та настроювання, де - -й набір значень вхідних змінних, - -й набір значень ЛЗ 2-го рівня ,

8) - вибірка для тестування

Знайти:

1) - нечітку базу знань, що визначає залежність ЛЗ 2-го рівня від ЛЗ 1-го рівня

2) Настроїти

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

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

Метод спрощення нечіткої БЗ за подібністю полягає в використанні міри подібності (3) для нечітких множин, відповідних термам ЛЗ, для визначення надлишковості в БЗ де - нечіткі множини, - потужність множини.

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

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

Під час ГП для кожної популяції застосовуються операції схрещування і мутації. Роль операції схрещування полягає в дослідженні простору пошуку в процесі обміну хромосом з популяції своїми частинами. Дві випадково обраних хромосоми "розрізаються" та "з'єднуються" для "вироблення" нової хромосоми. Метою використання операції мутації є внесення різноманітності в популяцію та сприяння знаходженню рішення в просторі пошуку. В роботі пропонується використовувати два види операції схрещування та мутації на рівні входів вузлів АБО і на рівні входів вузлів ТА.

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

Якщо після проходження заданої кількості епох не знайдена хромосома, що задовольняє умові закінчення, то змінюються параметри і алгоритм виконується знову. У протилежному випадку хромосома переписується у вигляді правила "ЯКЩО…, ТО…", яке є частиною часткової нечіткої БЗ для визначення залежності ЛЗ другого рівня від ЛЗ першого рівня. Кінцева БЗ буде отримана шляхом об'єднання сформованих частин БЗ, що визначають терми ЛЗ.

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

Четвертий розділ присвячено питанням розробки гнучкої технології створення програмних модулів обробки інформації (ПМОІ) та досвіду практичного використання розроблених моделей, методу, алгоритмів та відповідних програмних засобів. Запропонована технологія використовує метод, моделі, підходи і алгоритми, які були розроблені в роботі і функціонально реалізовані у вигляді інструментальних засобів гнучкої технології, в структурі яких можна виділити три великі частини (рис. 6), а саме систему підтримки, систему проектування та розвитку, інформаційні бази.

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

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

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

Схему БД можна представити у вигляді зваженого графу , де замість таблиць слід поставити вершини, а замість зв'язків між таблицями - ребра з одиничною вагою.

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

Досвід практичного використання розробленої гнучкої технології показав, що час розробки ПМОІ скорочується у 1,5-2 рази, а використання зручних засобів для проведення обробки інформації та формування звітної документації в термінах предметної області дозволило в 2-5 разів скоротити час на її підготовку, що значно підвищило ефективність роботи користувачів.

Практичне використання запропонованих методу, моделей, підходів та засобів розглянуто на прикладі ДАІ МВС України, для якої сформовано модель оцінки стану аварійності та злочинності на дорогах України та в рамках неї нечітку базу знань (рис. 7).

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

В якості вихідних зразків, на яких проводилось побудова, настроювання і тестування була взята інформація щодо аварійності та злочинності по дорогах України для трьох регіональних центрів за 2003-й рік. Так як в базі даних міститься інформація по тижням, то набір містив 156 зразків. Для навчання було обрано 117 зразків, а для тестування 39.

Приклад формування та настроювання БЗ для визначення залежності ЛЗ другого рівня “Ситуація по ДТП” від ЛЗ першого рівня наведено далі.

В результаті використання алгоритму побудови мережі NEFCLASS була сформована початкова БЗ , яка складалася з 30 правил. В результаті тестування на навчальній вибірці було вірно класифіковано 100 %, а на вибірці для тестування вірно класифіковано 95% (37 зразків).

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

Далі для визначення залежності кожного терму ЛЗ від термів ЛЗ попереднього рівня було проведено формування БЗ за допомогою методів та алгоритмів ГП. Розмір популяції дорівнював 15-20 для різних термів та складався з правил, що були сформовані на попередньому етапі та їх складових частин. Було проведено 200 ітерацій (епох). Поріг дорівнював 0,5, а =0,01. В результаті була отримана БЗ . Нижче розглянута побудова її частини для терму “Погано”.

Виходячи з частини початкової БЗ для визначення терму “Погано”, яка складалася з 5 правил з сумарною кількістю термів 20 було проведено етап формування структури.

Розмір початкової популяції складав 20 хромосом, кількість ітерацій була задана в розмірі 200. В результаті була отримана база знань, що складається з 3 правил з сумарною кількістю термів 4.

Після проведення етапу формування структури було проведено додаткове тестування на всій вибірці (156 зразків), яке дало 100% вірних результатів.

Відмітимо, що БЗ суттєво спростилась лише для випадку коли лінгвістична змінна приймає значення П (погано).

Етап настроювання параметрів ФН для даного випадку не проводився, так як БЗ давала вірне рішення для всієї навчальної вибірки.

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

За допомогою комплексу інструментальних засобів були розроблені програмні модулі обробки інформації, побудовані відповідні нечіткі бази знань, які були впроваджені в Державному науково-дослідному центрі безпеки дорожнього руху та діяльності дорожньо-патрульної служби місцевої міліції МВС України, Всеукраїнському науково-дослідному інституті цивільного захисту населення і територій від надзвичайних ситуацій техногенного та природного характеру МНС України, Департаменті подолання наслідків Чорнобильської катастрофи МНС України, використання яких дозволило оперативно отримувати об'єктивну картину стану справ та скоротити час обробки інформації на різних рівнях ієрархії предметних областей.

У додатках приведені види функцій належності, мовні засоби гнучкої технології побудови програмних модулів обробки інформації, загальний формат SQL-запиту на вибірку, блок-схеми алгоритму нумерації та алгоритму розмітки, структура бази даних АІПС “Чергова Частина”, акти впровадження.

Основні результати та висновки

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

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

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

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

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

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

6. Модифіковано підхід до настроювання нечіткої БЗ введенням етапу формування структури, який полягає у спрощенні нечіткої БЗ за подібністю та застосуванні ГП, для якого запропоновано підхід до формування початкового набору хромосом, що дозволило скоротити простір пошуку.

7. Розроблено гнучку технологію створення ПМОІ, яка дозволяє адаптуватись до складних організаційних систем та особливістю якої є наявність інструментальних засобів прив'язки, формування, упорядкування та навчання нечіткої БЗ, що дозволило скоротити час розробки ПМОІ у 1,5-2 рази.

8. Запропоновані інструментальні засоби гнучкої технології створення ПМОІ включають CASE-засоби обробки інформації в термінах ПО, що дозволило скоротити час підготовки звітної документації в 2-5 разів та значно підвищити ефективність роботи користувачів.

9. На базі гнучкої технології створено ПМОІ, які було впроваджено в Державному науково-дослідному центрі безпеки дорожнього руху та діяльності дорожньо-патрульної служби місцевої міліції МВС України, Всеукраїнському науково-дослідному інституті цивільного захисту населення і територій від надзвичайних ситуацій техногенного та природного характеру МНС України, Департаменті подолання наслідків Чорнобильської катастрофи МНС України, що дозволило підвищити прозорість проходження інформації, достовірність результатів обробки інформації, оперативно реагувати на негативний вплив певних факторів, зменшити час проведення обробки інформації, за рахунок зменшення кількості правил в БЗ нижнього рівня в 1,2-1,7 разів та сумарної кількості термів в 2-4 рази.

Список опублікованих праць за темою дисертації

1. Коломієць С.Г., Глоба Л.С., Прокопенко Ю.М., Христич М.Й., Терновой М.Ю. Програмні технології побудови розподіленої корпоративної системи департаменту Державтоінспекції МВС України. // Безпека дорожнього руху. - 2002. - № 2 (13). - С. 21-24.

Здобувачем розроблені структура інформаційно-аналітичної системи, алгоритми її функціонування, описані основні програмні технології створення корпоративної системи Державтоінспекції МВС України.

2. Глоба Л.С., Терновой М.Ю. Основні підходи до побудови інформаційно-аналітичної системи УДАІ УМВС України. //Электроника и связь. - 2002. - №17. - С. 97-104.

Здобувачем розглянуті та запропоновані математичні методи, які можуть використовуватись в інформаційно-аналітичній системі УДАІ УМВС України.

3. Глоба Л.С., Терновой М.Ю. Створення інформаційних ресурсів корпорації: архітектурні рішення та технології. // Науково-технічна інформація. - 2003. - №1. - С.19-22.

Здобувачем запропоновані основні архітектурні рішення щодо створення інформаційних ресурсів корпорації.

4. Глоба Л.С., Терновой М.Ю. Комплексная оценка сложного объекта в условиях неопределенности. // Электроника и связь. - 2003. - №18. - С 65-68.

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

5. Ільченко М.Ю., Терещенко П.І., Глоба Л.С., Терновой М.Ю., Лисенко А.М. Технології Intranet в задачах аналітичної обробки інформації та підтримки прийняття управлінських рішень щодо підвищення безпеки дорожнього руху. // Безпека дорожнього руху. - 2004. - № 1-2. - С.148-160.

Здобувачем запропоновано принцип побудови програмної компоненти обробки інформації на базі Intranet технологій.

6. Баканов А.А., Глоба Л.С., Терновой М.Ю Алгоритм динамического формирования SQL-запроса в системах аналитической обработки информации. // Электроника и связь. - 2005. - №27. - С. 65-68.

Здобувачем запропоновано алгоритм автоматичної побудови SQL-запиту на вибірку.

7. Глоба Л.С., Терновой М.Ю. Проблемы и технологии построения информационных ресурсов корпорации. // Материалы ІІІ международной научно-технической конференции "Электронные ресурсы: проблемы формирования, обработки, распространения и использования- 2002". - К.: УкрИНТЭИ .- 2002. -С. 34.

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

8. Терновой М.Ю. Використання апарату нечіткої логіки для аналізу інформації в розподілених корпоративних системах. // Труды 6-й международной научно-практической конференции "Современные информационные и электронные технологии" (СИЭТ 2005). - Одеса: ОНПУ. - 2005 .- С.163.

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

9. Ternovoy M. Modified Fuzzy Intelligence System. // Proceedings of the International Conference TCSET'2006. - Lviv-Slavsko. - pp. 420-422.

Здобувачем запропоновано модифікацію підсистеми нечіткого виведення.

10. Терновой М.Ю. Гибкая технология создания программных модулей интеллектуальной обработки информации. // Материалы 16-й Международной Крымской конференции "СВЧ-техника и телекоммуникационные технологии. Крымико' 2006". - Севастополь: Вебер.- 2006. - С. 400-401.

Здобувачем запропоновано гнучку технологію побудови програмних модулів обробки інформації.

11. Глоба Л.С., Терновой М.Ю. Интеллектуальная обработка информации в производственных системах. // Труды четвертой международной научно-практической конференции "Современные информационные и электронные технологии" (СИЭТ-2003).- Одеса: ОНПУ. - 2003.- С. 98.

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

12. Глоба Л.С., Терновой М.Ю. Разработка универсальной компоненты анализа информации в распределенной корпоративной системе. // Труды пятой международной научно-практической конференции "Современные информационные и электронные технологии" (СИЭТ-2004).- Одеса: ОНПУ. - 2004.- С. 150.

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

13. Глоба Л.С., Терновой М.Ю. Оптимизация использования базы знаний экспертной системы введением иерархии правил. // Труды седьмой международной научно-практической конференции "Современные информационные и электронные технологии" (СИЭТ-2006). - Одеса: ОНПУ. - 2006 . - С.166.

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

АНОТАЦІЯ

Терновой М.Ю. Підхід до обробки інформації на основі деревоподібних баз знань зі змішаною схемою виведення. Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - "Автоматизовані системи управління і прогресивні інформаційні технології". Національний технічний університет України "Київський політехнічний інститут", Київ, 2007.

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

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

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

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

ANNOTATION

Ternovoy M. Y. The information processing approach basing on tree-like fuzzy knowledgebases with combined inference scheme. Manuscript.

A Philosophy Doctor of Technical Sciences thesis in specialty 05.13.06 -- Automated control system and progressive information technologies. National Technical University of Ukraine “Kiev Polytechnic Institute”, Kiev, 2007.

The approach of unordered fuzzy knowledgebase reduction to tree-like structure is developed in thesis. The fuzzy inference system is modified. The limitations when the part of fuzzy knowledgebase might be used as logical knowledgebase are proposed. The construction and setup method of fuzzy knowledgebases is modified. The fuzzy logic model for classification problem solving is improved. The information processing method basing on tree-like fuzzy knowledgebases with combined inference scheme are developed.

The information processing software modules design flexible technology for application of developed methods in complex organization system are constructed and described in paper. It includes software tools of problem domain associating; composition, ordering and setup of fuzzy knowledgebase.