НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ“

хАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Міненкова Злата Євгенівна

УДК 681.3

МОДЕЛІ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ПОБУДОВИ ДІАГНОСТИЧНИХ ЕКСПЕРТНИХ СИСТЕМ З ВЕЛИКИМ ОБ’ЄМОМ ЗАЛЕЖНИХ ВХІДНИХ ДАНИХ

Спеціальність 05.13.06 - Автоматизовані системи управління та прогресивні

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

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

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

Харків – 2003

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

Робота виконана в Національному технічному університеті “Харківський політехнічний інститут” Міністерства освіти і науки України, м. Харків.

Науковий керівник: доктор технічних наук, професор

Раскін Лев Григорович

Національний технічний університет “Харківський політехнічний інститут”,

професор кафедри економічної кібернетики та маркетингового менеджменту.

Офіційні опоненти: доктор технічних наук, професор

Шаронова Наталія Валеріївна,

Національний технічний університет “Харківський політехнічний інститут”,

професор кафедри педагогіки і психології управління соціальними системами

доктор технічних наук, професор

Абрамов Юрій Олексійович,

Академія пожежної безпеки України,

проректор з наукової роботи.

Провідна установа: Харківський національний університет радіоелектроніки,

кафедра системотехніки, Міністерства освіти і науки України,

м. Харків

Захист відбудеться " 23 " грудня 2003 р. о 1430 годині на засіданні спеціалізованої вченої ради Д64.050.07 у Національному технічному університеті “Харківський політехнічний інститут” за адресою: 61002, м. Харків, вул. Фрунзе, 21.

З дисертацією можна ознайомитися у бібліотеці Національного технічного університету “Харківський політехнічний інститут”.

Автореферат розісланий "18" листопада 2003 р.

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

спеціалізованої вченої ради Голоскоков О. Є.

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

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

Зв’язок роботи з науковими програмами, планами, темами В основу дисертації покладено теоретичні дослідження та практичні результати, отримані при виконанні науково-дослідних тем, що виконувались в Національному технічному університеті “Харківський політехнічний інститут” за безпосередньою участю автора: М7212 "Розробка методичного, математичного та програмного забезпечення систем дагностики прогнозування" (1997р); угода про творче співробітництво з Харківським науково-дослідним інститутом медичної радіології МОЗ України за темою: “Розробка і впровадження методів та інформаційних технологій обробки результатів лабораторних та клінічних досліджень пацієнтів щодо діагностики їх стану” (2001р).

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

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

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

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

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

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

- розробка методики корекції бази знань експертної системи на підставі інформації про верифіковані стани контрольованого об'єкта.

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

Предмет дослідження - діагностичні експертні системи з великою кількістю взаємопов'язаних контрольованих ознак та параметрв.

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

Наукова новизна одержаних результатів

У процесі роботи над дисертацією були отримані такі найбільш суттєві результати, що мають наукову новизну:

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

- запропоновано принципово нові технолог групування об'єктв, розташування яких у просторі задано не координатами, а тільки відстанню мж ними;

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

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

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

Апробація результатів дисертації Основні висновки, положення й результати дисертації доповідалися на міжнародній науково-практичній конференції "Технічний прогрес та ефективність виробництва" Оптимум-2001 (Харків, 2001); міжвідомчому науково-дослідному семнар в межах Ради з проблем кібернетики НАН України "Математичні методи моделі в соціально-економічних системах" (Харків, 2001); міжкафедральному науково-технічному семнар НТУ "ХПI" з проблеми "Сучасні технолог оцінки стану обєктів" (Харків, 2002); конференції "Компютерне моделювання та інформаційні технолог в науці, економіці та освіті" (Черкаси, 2003); 7-му Міжнародному молодіжному форум "Радіоелектроніка молодь в XXI столітті" (Харків, 2003); XI міжнародній науково-практичній конференції “Інформаційні технології: наука, техніка, технологія, освіта, здоров’я” MicroCAD-2003 (Харків, 2003).

Публікації Результати дисертації опубліковані в 7 працях у провідних наукових фахових виданнях України.

Обсяг і структура дисертації Дисертаційна робота складається зі вступу, чотирьох розділів, висновків і восьми додатків. Повний обсяг дисертації складає 268 сторінок; з них 4 ілюстрації по тексту, 25 ілюстрацій на 22 сторінках; 18 таблиць по тексту, 16 таблиць на 14 сторінках; 8 додатків на 77 сторінках; список використаних літературних джерел з 119 найменувань на 10 сторінках.

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

У першому розділі наведено приклади існуючих діагностичних експертних систем, проаналізовано загальні принципи їх функціонування та структурні схеми, проведено класифікацію експертних систем (ЕС) за принципом побудови механізму логічного висновку (МЛВ).

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

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

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

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

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

Позначимо

, , …, - контрольовані експертною системою параметри;

, ,…,- відомі експертній системі стани об'єкта;

- апріорна імовірність того, що об'єкт знаходиться в стані ;

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

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

Апостеріорні імовірності розраховуються поступово. На першому кроці, відповідно до теореми Байеса, маємо:

, . (1)

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

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

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

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

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

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

.

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

Далі обчислені апостеріорні імовірності і на черговому кроці використовуються в формулі Байеса як апріорні.

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

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

Інформаційна цінність параметра для пари станів об'єкта і може визначатися наступним чином:

,

де - умовні щільності розподілу параметра для двох діагнозів та .

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

Рис. 1. Ілюстрація поняття “інформаційна цінність”

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

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

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

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

Граничні значення і відшукуються в результаті розв’язання такої задачі оптимізації: знайти

(2)

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

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

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

У третьому розділі проведено аналіз існуючих методів групування та запропоновано методи, які поліпшують якість існуючих процедур та забезпечують побудову комбінованого МЛВ. Розглянуто методи, для вирішення задач групування двох типів: 1) коли немає даних про координати об’єктів групування; 2) коли є дані про координати об’єктів групування.

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

При аналізі традиційних методів групування був виявлений ряд їхніх недоліків, головними з яких є: відсутність наукового обґрунтування вибору центрів групування; залежність якості розподілу на групи від типу і розмірності даних (зі зменшенням кількості класів і збільшенням розмірності простору якість класифікації знижується).

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

Методи групування, що вимагають знання координат групованих об’єктів.

Групування з утворенням центрів групування (алгоритм 1). У багатьох практичних задачах заздалегідь відома кількість груп, на яку потрібно розбити вихідну множину об’єктів.

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

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

Групування шляхом формування центрів ваги (алгоритм 2). Даний алгоритм є модифікацією алгоритму групування, що використовує утворення центрів групування. Відмінність полягає в "приєднанні" об’єктів не до центрів групування, а до центрів ваги одержуваних підгруп.

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

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

Групування шляхом формування центрів групування на сфері ( алгоритм 4). У всіх розглянутих вище алгоритмах на першому етапі відшукувалися об’єкти максимально віддалені один від одного, що використовувалися як центри групування. Але цю роль не обов'язково повинні відігравати елементи, що відповідають реальним об'єктам. Центри можна розташувати, наприклад, таким чином, щоб групування було максимально ефективним. Так, в двомірному випадку, центри груп можна розташувати на колі з центром на початку координат і радіусом, що забезпечує охоплення цим колом всіх об’єктів множини, на рівній відстані один від одного.

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

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

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

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

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

Геометрико-імовірностний підхід у задачах кластеризації (алгоритм 7). Пропонується методика розв’язання задач кластеризації, що поєднує відомі геометричний і теоретико-імовірностний підходи. На першому етапі, з використанням будь-якого з “геометричних” методів, здійснюється початковий розподіл об'єктів на класи. Потім для кожної з отриманих груп проводиться оцінювання параметрів розподілу за допомогою багатопараметричного універсального розподілу імовірностей. За результатами оцінювання здійснюється перерозподіл об'єктів кластеризації по групах, після чого процедура оцінювання повторюється. Кластеризація вважається закінченою, коли результати розподілу на двох послідовних кроках збігаються.

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

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

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

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

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

Для порівняння в табл.1 наведено результати роботи розглянутих вище алгоритмів кластеризації та метода Уорда (алгоритм 9), який було визнано кращим із традиційних методів групування, для 10 різних наборів.

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

Крім того, з’ясувалося, що ефективність алгоритмів залежить від набору об’єктів, оскільки, для одного набору алгоритм 1 краще алгоритмів 2 і 3, а для іншого набору, навпаки, кращим виявляється алгоритм 2 чи 3, аналогічна ситуація виникає і для пари алгоритмів 3 і 4. Геометрико-імовірностний же метод пропонується застосовувати з алгоритмом, що дав для конкретного набору об’єктів кращий результат з метою його можливого поліпшення.

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

Таблиця 1.

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

№ набору об’єктів | Алгоритми групування

1 | 2 | 3 | 4 | 5 | 6 | 7* | 8 | 9

1 | 2,2395 | 2,18243 | 2,3689 | 2,3257 | 2,41129 | 2,2324 | 2,41129 | 2,1913 | 1,8534

2 | 1,6559 | 2,08689 | 2,0986 | 2,2209 | 2,17043 | 2,1328 | 2,1956 | 2,0012 | 1,9899

3 | 1,8505 | 1,88311 | 1,8452 | 2,1117 | 2,1117 | 2,0121 | 2,1117 | 1,9982 | 1,9580

4 | 1,8505 | 1,97534 | 2,0125 | 2,1462 | 2,1462 | 2,0053 | 2,1475 | 1,9452 | 1,7351

5 | 2,2172 | 2,3554 | 2,2959 | 2,4536 | 2,5028 | 2,3102 | 2,5028 | 2,2354 | 2,0102

6 | 1,8952 | 2,1022 | 1,7784 | 2,4562 | 2,4135 | 1,9892 | 2,4624 | 2,1258 | 1,7551

7 | 1,9283 | 2,0670 | 2,2157 | 2,2135 | 2,3642 | 2,0124 | 2,3642 | 2,1025 | 1,9985

8 | 2,0596 | 1,8971 | 1,6334 | 2,6891 | 2,6600 | 2,1324 | 2,6600 | 2,2157 | 2,0112

9 | 2,0371 | 2,2737 | 2,4125 | 2,4521 | 2,5621 | 2,3148 | 2,5621 | 2,2546 | 2,0025

10 | 2,3582 | 2,1609 | 2,2089 | 2,4683 | 2,5292 | 2,4128 | 2,5756 | 2,3454 | 1,9568

* - початковий розподіл зроблено за допомогою алгоритму 5.

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

Експертна система діагностики типу імунопатологічної реакції розроблена за участю фахівців-лікарів Харківського науково-дослідного інституту медичної радіології МОЗ України, що забезпечили формулювання задачі на створення ЕС, опис складу вхідної інформації та верифікацію результатів роботи системи.

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

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

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

Система використовує комбінований механізм логічного висновку.

Рис. 2. Структурна схема експертної системи з комбінованим механізмом

логічного висновку.

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

Ефективність роботи експертної системи діагностики типу імунологічної реакції підтверджено на практиці. За три роки у Харківському науково-дослідному інституті медичної радіології МЗ України за допомогою цієї експертної системи був обстежений 871 пацієнт. Результатом процесу діагностики є розподіл імовірностей наявності у пацієнта кожного з п’яти типів імунопатологічних реакцій. Впродовж лікування проводилася верифікація діагнозів. На діаграмах показано у відсотковому співвідношенні розподіл діагнозів, наданих експертною системою, за відношенням до верифікованих (Рис. 3).

Рис. 3. Розподіл діагнозів, наданих експертною системою, за відношенням до верифікованих.

Експертна система діагностики патогенетичних варіантів бронхіальної астми розроблена за участю фахівців-лікарів Харківського науково-дослідного інституту медичної радіології МЗ України і Дніпропетровського обласного діагностичного центра за аналогією до експертної системи діагностики типу імунологічної реакції.

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

ВИСНОВКИ

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

При цьому отримані такі основні наукові та практичні результати.

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

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

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

4. Показано принципову можливість корекції бази знань експертної системи в процесі експлуатації на підставі введеної інформації про верифіковані стани контрольованого об'єкта. Запропоновано відповідну процедуру корекції.

5. Запропоновано при розрахунку критерію розпізнавання стану об'єктів використовувати апріорні імовірності прояву симптомів, а також модифікацію критерію розпізнавання.

6. Розроблені ЕС реалізовані в Харківському науково-дослідному інституті медичної радіології МЗ України та Дніпропетровському діагностичному центрі.

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

1. Раскин Л. Г., Климко Е. В., Миненкова З. Е. Эффективный алгоритм кластеризации в пространстве произвольной метрики. // Вестник Харьковского государственного политехнического университета.- Харьков: ХГПУ, 1999.-Вып. №51.-С.40-42.

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

2. Миненкова З. Е. Процедура группирования контролируемых параметров в диагностической экспертной системе. // Радиоэлектроника и информатика, Харьковский государственный технический университет радиоэлектроники. - Харьков: ХТУРЭ, 2000. – Вып. №3(12). - С.114-116.

3. Раскин Л. Г., Серая О. В., Миненкова З. Е. Кластеризация объектов на нечетких множествах. // Автоматизированные системы управления и приборы автоматики, Харьковский государственный технический университет радиоэлектроники. – Харьков: ХТУРЭ, 2000. - Вып. №113. - С.49-51.

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

4. Раскин Л. Г., Серая О. В., Миненкова З. Е. Геометрико-вероятностный подход в задачах кластеризации. // Вестник Харьковского государственного политехнического университета.- Харьков: ХГПУ, 2000.-Вып. №121.-С.63-65.

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

5. Раскин Л. Г., Серая О. В., Миненкова З. Е. Группирование в многомерном пространстве параметров. Проблемы, решения. // Вестник Национального технического университета “Харьковский политехнический институт”.- Харьков: НТУ “ХПИ”, 2001. – Вып. №24.-С.33-36.

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

6. Раскин Л. Г., Серая О. В., Миненкова З. Е. Симптомокомплексная диагностическая экспертная система. // Вестник Национального технического университета “Харьковский политехнический институт”.- Харьков: НТУ “ХПИ”, 2002. – Вып. №13.-С.31-33.

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

7. Миненкова З. Е. Комбинированный механизм логического вывода байесовой диагностической экспертной системы. // Вестник Национального технического университета “Харьковский политехнический институт”.- Харьков: НТУ “ХПИ”, 2003. – Вып. №6.-С.69-74.

АНОТАЦІЇ

Міненкова З. Є. Моделі та інформаційні технології побудови діагностичних експертних систем з великим об’ємом залежних вхідних даних. - Рукопис.

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

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

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

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

Миненкова З. Е. Модели и информационные технологии построения диагностических экспертных систем с большим объемом зависимых входных данных. - Рукопись.

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

Диссертация посвящена вопросам разработки принципов построения математического и программного обеспечения диагностических экспертных систем для оценки состояния объекта на основании обработки большого числа зависимых контролируемых параметров.

Проведенный анализ существующих методик и принципов построения диагностических экспертных систем показал, что применение чисто байесового или чисто продукционного подхода при построении механизма логического вывода (МЛВ) не позволяет построить эффективную ЭС, обрабатывающую сотни и тысячи зависимых контролируемых параметров. Реализация чисто продукционного МЛВ требует либо формирования слишком большого количества правил, что существенно затрудняет их обработку, либо сокращения количества контролируемых параметров, что является неприемлемым при построении ЭС диагностики реальных объектов. В свою очередь, байесов подход может быть корректно реализован на практике лишь в ситуации, когда имеет место как независимость между контролируемыми параметрами, так и независимость между состояниями объекта, в противном случае применение формулы Байеса ведет к существенному снижению качества диагностики.

В диссертации разработан комбинированный механизм логического вывода диагностических экспертных систем, сочетающий в себе байесов и продукционный подходы к построению МЛВ и свободный от их недостатков. Показано, что его применение позволяет существенно повысить качество диагностики.

Для реализации комбинированного МЛВ предложена методика разбиения исходного множества контролируемых параметров на независимые группы и выработан критерий оценки качества такого разбиения. В рамках данного направления исследования разработаны новые технологии группирования объектов, положение которых в пространстве с нелинейной метрикой задано не координатами, а только расстоянием между ними. В работе предложены методы кластеризации, использующие координаты обрабатываемых объектов: методом деления множества точек пополам; с образованием центров группирования; путем формирования центров тяжести; путем формирования центров тяжести с определением порядка присоединения нераспределенных объектов; путем формирования центров группирования на окружности с центром в начале координат. Проведен сравнительный анализ алгоритмов группирования и отмечено, что использование предложенных методов обеспечивает в среднем более эффективное решение задачи кластеризации, нежели известные и традиционно используемые методы. Показана возможность построения методики решения задач кластеризации, которая объединяет геометрический и теоретико-вероятностный подходы.

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

Результаты теоретических исследований, проведенных в рамках данной диссертационной работы, практически использованы при разработке двух экспертных медицинских диагностических экспертных систем: "Экспертная система диагностики типа иммунологической реакции", которая внедрена в Харьковском НИИ Медицинской Радиологии МЗ Украины и "Экспертная система диагностики патогенетических вариантов бронхиальной астмы", которая успешно эксплуатируется в Днепропетровском областном диагностическом центре.

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

Minenkova Z. E. Models and information technologies of construction of diagnostic consulting models with great volume of dependent input data. - The Manuscript.

The Dissertation on competition for the Cand.Tech.Sci. scientific degree on the Speciality of 05.13.06 – “Automized Control Systems and Progressive Information Technologies”. The National Technical University “Kharkov Polytechnic Institute” of the Ministry of the Education and Sciences of the Ukraine, Kharkov, 2003.

The Dissertation is devoted the Software Development Principles for Diagnostic Expert Systems (ES) of the object state based on the computing the large amount the dependent control parameters.

In the Dissertation the combined Inference Engine (IE) for the Diagnostic ES, combining in itself the Bayes and the Rule-based methods to construction for the IE and free from its disadvantages is developed.

The Methods of the initial assemblage division for control parameters to independent groups of the control parameters required for the combined IE application is offered. The criterion of an quality estimation for division is developed.

The further evolution of the design technology for the expert systems database and a knowledge base is received. The some of required subsystems for operation the ES is developed: the choice an optimal processing subsystem for the control parameters; the estimation subsystem for information worth of control parameters; the correction subsystem for knowledge base.

Key words: expert system, interference engine, knowledge base, information technology, optimization, classification, performance criterion.