Modeling technology based on fuzzy object-oriented Bayesian belief networks
The basic components of information technology inductive modeling causation under uncertainty based on fuzzy object-oriented Bayesian networks is proposed. The technology is based on a combination of transformation algorithms Bayesian network in the junction tree. New more efficient algorithms for B...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/194 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-194 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/b3/c7ef219cc5969fcc309bf77e313ca9b3.pdf |
| spelling |
pp_isofts_kiev_ua-article-1942024-04-28T13:09:57Z Modeling technology based on fuzzy object-oriented Bayesian belief networks Технология моделирования на основе нечетких объектно-ориентированных байесовских сетей доверия Технологія моделювання на основі нечітких об’єктно-орієнтованих байєсівських мереж довіри Yershov, S.V. Kostukevich, F.V. Bayesian network; object-oriented Bayesian network; fuzzy Bayesian network; transformation algorithms; moral graph; junction tree; fuzzy probability UDC 681.3.06 байесовская сеть; объектно-ориентированная байесовская сеть; нечеткая байесовская сеть; алгоритм трансформации; узловое дерево; моральный граф; нечеткая вероятность УДК 681.3.06 байєсівська мережа; об’єктно-орієнтована байєсівська мережа; нечітка байєсівська мережа алгоритми трансформації; вузлове дерево; моральний граф; нечітка імовірність УДК 681.3.06 The basic components of information technology inductive modeling causation under uncertainty based on fuzzy object-oriented Bayesian networks is proposed. The technology is based on a combination of transformation algorithms Bayesian network in the junction tree. New more efficient algorithms for Bayesian network transformation are resulted from modifications known algorithms; algorithms based on the use of more information on the graphical representation of the network are considered. Structurally functional model are described, it is designed to implement the transformation of fuzzy object-oriented Bayesian networks.Problems in programming 2016; 2-3: 179-187 Представлены основные компоненты информационной технологии индуктивного моделирования причинно-следственных связей в условиях неопределенности на основе нечетких объектно-ориентированных байесовских сетей доверия. Технология построена на основе алгоритмов трансформации байесовской сети в узловое дерево. Рассмотрены новые более эффективные алгоритмы трансформации байесовской сети, полученные в результате модификации известных алгоритмов, основанных на использовании дополнительной информации о графическом представлении сети. Конструктивно изложена функциональная модель, которая предназначена для реализации процессов трансформации нечеткой объектно-ориентированной байесовской сети доверия.Problems in programming 2016; 2-3: 179-187 Представлені основні компоненти інформаційної технології індуктивного моделювання причинно-наслідкових зв’язків в умовах невизначеності на основі нечітких об’єктно-орієнтованих байєсівських мереж довіри. Технологія побудована на основі алгоритмів трансформації байєсівської мережі в вузлове дерево. Розглянуті нові більш ефективні алгоритми трансформації байєсівськоїмережі, отримані в результаті модифікації відомих алгоритмів, які ґрунтуються на використанні додаткової інформації про графічне представлення мережі. Конструктивно викладена функціональна модель, яка призначена для реалізації процесів трансформації нечіткої об’єктно-орієнтованої байєсівської мережі довіри.Problems in programming 2016; 2-3: 179-187 Інститут програмних систем НАН України 2018-07-06 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/194 10.15407/pp2016.02-03.179 PROBLEMS IN PROGRAMMING; No 2-3 (2016); 179-187 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2016); 179-187 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2016); 179-187 1727-4907 10.15407/pp2016.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/194/189 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T13:09:57Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
Bayesian network object-oriented Bayesian network fuzzy Bayesian network transformation algorithms moral graph junction tree fuzzy probability UDC 681.3.06 |
| spellingShingle |
Bayesian network object-oriented Bayesian network fuzzy Bayesian network transformation algorithms moral graph junction tree fuzzy probability UDC 681.3.06 Yershov, S.V. Kostukevich, F.V. Modeling technology based on fuzzy object-oriented Bayesian belief networks |
| topic_facet |
Bayesian network object-oriented Bayesian network fuzzy Bayesian network transformation algorithms moral graph junction tree fuzzy probability UDC 681.3.06 байесовская сеть объектно-ориентированная байесовская сеть нечеткая байесовская сеть алгоритм трансформации узловое дерево моральный граф нечеткая вероятность УДК 681.3.06 байєсівська мережа об’єктно-орієнтована байєсівська мережа нечітка байєсівська мережа алгоритми трансформації вузлове дерево моральний граф нечітка імовірність УДК 681.3.06 |
| format |
Article |
| author |
Yershov, S.V. Kostukevich, F.V. |
| author_facet |
Yershov, S.V. Kostukevich, F.V. |
| author_sort |
Yershov, S.V. |
| title |
Modeling technology based on fuzzy object-oriented Bayesian belief networks |
| title_short |
Modeling technology based on fuzzy object-oriented Bayesian belief networks |
| title_full |
Modeling technology based on fuzzy object-oriented Bayesian belief networks |
| title_fullStr |
Modeling technology based on fuzzy object-oriented Bayesian belief networks |
| title_full_unstemmed |
Modeling technology based on fuzzy object-oriented Bayesian belief networks |
| title_sort |
modeling technology based on fuzzy object-oriented bayesian belief networks |
| title_alt |
Технология моделирования на основе нечетких объектно-ориентированных байесовских сетей доверия Технологія моделювання на основі нечітких об’єктно-орієнтованих байєсівських мереж довіри |
| description |
The basic components of information technology inductive modeling causation under uncertainty based on fuzzy object-oriented Bayesian networks is proposed. The technology is based on a combination of transformation algorithms Bayesian network in the junction tree. New more efficient algorithms for Bayesian network transformation are resulted from modifications known algorithms; algorithms based on the use of more information on the graphical representation of the network are considered. Structurally functional model are described, it is designed to implement the transformation of fuzzy object-oriented Bayesian networks.Problems in programming 2016; 2-3: 179-187 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/194 |
| work_keys_str_mv |
AT yershovsv modelingtechnologybasedonfuzzyobjectorientedbayesianbeliefnetworks AT kostukevichfv modelingtechnologybasedonfuzzyobjectorientedbayesianbeliefnetworks AT yershovsv tehnologiâmodelirovaniânaosnovenečetkihobʺektnoorientirovannyhbajesovskihsetejdoveriâ AT kostukevichfv tehnologiâmodelirovaniânaosnovenečetkihobʺektnoorientirovannyhbajesovskihsetejdoveriâ AT yershovsv tehnologíâmodelûvannânaosnovínečítkihobêktnooríêntovanihbajêsívsʹkihmereždovíri AT kostukevichfv tehnologíâmodelûvannânaosnovínečítkihobêktnooríêntovanihbajêsívsʹkihmereždovíri |
| first_indexed |
2024-09-16T04:07:33Z |
| last_indexed |
2024-09-16T04:07:33Z |
| _version_ |
1818568162990358528 |
| fulltext |
Інтелектуальні інформаційні технології
© С.В. Єршов, Ф.В. Костукевич, 2016
ISSN 1727-4907. Проблеми програмування. 2016. № 2–3. Спеціальний випуск 179
УДК 681.3.06
ТЕХНОЛОГІЯ МОДЕЛЮВАННЯ НА ОСНОВІ НЕЧІТКИХ
ОБ’ЄКТНО-ОРІЄНТОВАНИХ БАЙЄСІВСЬКИХ МЕРЕЖ ДОВІРИ
С.В. Єршов, Ф.В. Костукевич
Представлені основні компоненти інформаційної технології індуктивного моделювання причинно-наслідкових зв’язків в умовах
невизначеності на основі нечітких об’єктно-орієнтованих байєсівських мереж довіри. Технологія побудована на основі алгоритмів
трансформації байєсівської мережі в вузлове дерево. Розглянуті нові більш ефективні алгоритми трансформації байєсівської
мережі, отримані в результаті модифікації відомих алгоритмів, які ґрунтуються на використанні додаткової інформації про
графічне представлення мережі. Конструктивно викладена функціональна модель, яка призначена для реалізації процесів
трансформації нечіткої об’єктно-орієнтованої байєсівської мережі довіри.
Ключові слова: байєсівська мережа, об’єктно-орієнтована байєсівська мережа, нечітка байєсівська мережа алгоритми
трансформації, вузлове дерево, моральний граф, нечітка імовірність.
Представлены основные компоненты информационной технологии индуктивного моделирования причинно-следственных связей в
условиях неопределенности на основе нечетких объектно-ориентированных байесовских сетей доверия. Технология построена на
основе алгоритмов трансформации байесовской сети в узловое дерево. Рассмотрены новые более эффективные алгоритмы
трансформации байесовской сети, полученные в результате модификации известных алгоритмов, основанных на использовании
дополнительной информации о графическом представлении сети. Конструктивно изложена функциональная модель, которая
предназначена для реализации процессов трансформации нечеткой объектно-ориентированной байесовской сети доверия.
Ключевые слова: байесовская сеть, объектно-ориентированная байесовская сеть, нечеткая байесовская сеть, алгоритм
трансформации, узловое дерево, моральный граф, нечеткая вероятность.
The basic components of information technology inductive modeling causation under uncertainty based on fuzzy object-oriented Bayesian
networks is proposed. The technology is based on a combination of transformation algorithms Bayesian network in the junction tree. New
more efficient algorithms for Bayesian network transformation are resulted from modifications known algorithms; algorithms based on the
use of more information on the graphical representation of the network are considered. Structurally functional model are described, it is
designed to implement the transformation of fuzzy object-oriented Bayesian networks.
Key words: Bayesian network, object-oriented Bayesian network, fuzzy Bayesian network, transformation algorithms, moral graph,
junction tree, fuzzy probability.
Вступ
Мережі довіри, також відомі, як байєсівські мережі (БМ) широко застосовуються для моделювання
складних систем з невизначеностями [1, 2]. Отримання більш адекватних моделей та отримання більш
інформативних результатів є можливим, якщо врахувати особливості внутрішньої будови БМ та використати
апарату теорії нечітких множин. Для повноти викладення та однозначності розуміння матеріалу наведемо
також, дотримуючись [3–7], визначення кількох ключових понять.
Під нечіткою оцінкою імовірності P (далі просто – нечіткою імовірністю) будемо розуміти нечітке число
fuzP , яке визначено на чіткій підмножині універсальної множини [0;1];
fuzP , )(
fuzPdom [0;1] – його функція
належності та область її визначення відповідно.
Результатом операції «» (додавання «+», добутку «», різниці «-», ділення « ») нечітких
імовірностей 1fuzP та 2fuzP , які задані -перетинами [3], нечітких (толерантних або унімодальних) чисел, є
нечітка імовірність 3fuzP :
]1,0[
2211213 ],[
babaPPP fuzfuzfuz (1) (1)
з функцією приналежності
))(),(min(sup)( 213 21
213
3
xxx
fuzfuz
fuzfuzfuz
fuz PP
PPP
P
, (2)
де )( iPi fuz
domx , i=1,2,3, його функція приналежності та область її визначення відповідно.
Нечіткі імовірності ifuzP , i=1,2,…n, нормалізуються за формулою
fuzifuzifuz PPP , де
n
i
ifuzfuz PP
1
.
Після нормалізації
n
i
ifuzP
1
1 (чітка 1).
Інтелектуальні інформаційні технології
180
Нехай }X...,,X,{XX n21 – множина імовірнісних змінних, область визначення яких – це повна
(вичерпна) множина подій, що взаємно виключають одна одну. Декартовий добуток областей визначення
змінних множини Х утворює простір станів, який позначається dom(X) , а екземпляр dom(X),x який
називається інформаційним станом (надалі, коротко, станом), асоціюється або умовно-залежними подіями, або
з умовними подіями.
Нечіткий імовірнісний потенціал (далі, де це не приводить до двозначності – коротко, потенціал) – це
функція φ: dom(X)→{ ifuzP } (i=1,2,…m=|| dom(X) ||), яка ставить у відповідність кожному стану dom(X)xi
нечітку імовірність ifuzP . Область визначення потенціалу dom()= dom(X) . Потенціал, який визначений над
простором станів dom(X) , позначається X або )X( . Якщо елементи простору станів dom(X) – це умовно-
залежні стани, тоді потенціал )X( – це розподіл умовних нечітких імовірностей, інакше – він визначає
загальний розподіл нечітких імовірностей змінних множини Х. Над нечіткими імовірнісними потенціалами, як і
над чіткими потенціалами [6], визначені операції суми, добутку, різниці, маргіналізації (проектування на
підмножину), масштабування та нормалізації.
Як відомо [6, 7], мережа )G,X,(N називається нечіткою байєсівською мережею (НБМ), якщо вона
складається з:
1) ациклічного орграфа )EV,(G з вузлами }v,...,{vV n1 та дугами E=VV;
2) множини імовірнісних змінних X (в контексті класичної теорії імовірності), які належать вузлам
графа G ;
3) множини розподілів нечітких імовірностей (нечітких потенціалів), які представляють апріорні
розподіли (умовні або маргінальні); кожному вузлу співставляється відповідний нечіткий потенціал.
Мережний клас в об’єктно-орієнтованій нечіткій байєсівській мережі (ООНБМ) ),,( OINС – це
поіменований та самодостатній опис НБМ, який складається з:
1) НБМ )G,X,(N ;
2) множина базових вузлів поділяється на підмножини:
O – множина вихідних вузлів; вузли, які можуть бути батьківськими вузлами для вузлів поза N ;
I – множина вхідних вузлів, які не належать класу, але використовується як батьківські вузли всередині
екземплярів класу; вхідні вузли не можуть мати батьківських вузлів в цьому класі;
H – множина прихованих (захищених) вузлів, які можуть мати батьківські вузли та вузли-нащадки
тільки всередині цього класу.
Будь-який екземпляр представляє певну реалізацію мережного класу в межах іншого класу. На рис. 1
екземпляр, який складається з вузлів Gamma_IN, Delta, Gamma_OUT є реалізацію мережного класу Epsilon, де
вузол Gamma_IN є вхідним, вузол Gamma_OUT – вихідними, Delta – є прихованим (або захищеним). Для того,
щоб клас Epsilon підтримував специфікацію нечітких потенціалів для кожного вузла Gamma_IN, він повинен
мати такий самий простір станів як батьківський вузол у класі, який інкапсулює Epsilon. Цей вузол не
відповідає фактичному вузлу НБМ, а є лише "заповнювачем", який дозволяє визначити розподіл нечітких
імовірностей для Gamma_IN.
Рис. 1. Екземпляр мережного класу Epsilon
З огляду на вищенаведений опис класу Epsilon, на рис. 2 показане представлення ООНБМ, яка
складається з двох екземплярів класу Epsilon, а на рис. 3 еквівалентне представлення цієї ж мережі у вигляді
екземплярів дерева: кореневий екземпляр {Alpha, Beta, Cappa1, Cappa2, Cappa}, та два екземпляри класу
Epsilon.
Екземплярний зв’язок – це дуга, яка з’єднує клас, що інкапсулює екземпляр, з вхідним вузлом екземпляру.
Батьківський вузол та вузол-нащадок для екземплярного зв’язку мають однаковий простір станів. Дуги
AlphaGamma_IN та BetaGamma_IN є екземплярними дугами.
Екземпляр
класу Epsilon
класу
Інтелектуальні інформаційні технології
181
Дерево екземплярів Т ООНБМ– це дерево над множиною екземплярів класів в ООНБМ. Два вузли iv та
jv в T (де, iv ближче до кореня T , ніж jv ) з’єднані ребром тоді і тільки тоді, коли екземпляр, представлений
вузлом iv містить екземпляр, представлений вузлом jv . Корінь дерева екземплярів – це верхнього рівня
мережний клас, що не реалізується жодним іншим мережним класом в межах моделі.
Граф називається моральним (а процес його створення моралізацією), коли він отриманий з НБМ після
виконання таких дій:
1) всі дуги НБС замінити ребрами;
2) якщо вузол має кілька батьківських вузлів, тоді всі вони попарно з’єднуються між собою ребрами.
Кластером UCl , визначений над підмножиною вузлів VU називається множина, де вузли утворюють
повний підграф графа G . Сепаратором є кластер, який навантажує ребро у вузловому дереві.
Кластерним або вузловим деревом, заданим над множиною вузлів НБМ називається неорієнтоване дерево,
яке складається з кластерів, визначених над множиною вузлів цієї ж НБМ. Для вузлового дерева виконується
умова: для довільних двох кластерів ACl та BCl , якщо ACl BCl та BCl ACl , тоді на шляху між ними
об’єднання всіх сепараторів є підмножиною перетину цих кластерів ACl BCl .
Рис. 2. Нечітка об’єктно-орієнтована байєсівська мережа з двома екземплярами, інкапсульованими в
батьківський клас
Рис. 3. Нечітка об’єктно-орієнтована байєсівська мережа у вигляді екземплярів
Визначну роль у розвитку та застосуванні ООНБМ відіграв алгоритм розповсюдження довіри, який
запропонував Джуді Перл [8]. Однією з головних проблем, які виникають під час застосування цього
алгоритму, є проблема трансформації ООНБМ в вузлове дерево. Доведено [9–11], що для будь-якої ООНБМ
існує вузлове дерево, коли моральний граф можна декомпонувати на множину повних підграфів. З цього
випливає, що для прискорення трансформації ООНБМ слід врахувати її ієрархічну будову. На основі [5],
авторами запропонована модифікація відомих алгоритмів, яка полягає у використанні властивостей нечітких
Інтелектуальні інформаційні технології
182
потенціалів для створення кластерів. Використовуючи таку модифікацію вдалось побудувати алгоритм
трансформації ООНБМ, який на порядок скоріший відомих [12, 13]. Як полігон для проведення
обчислювальних експериментів по реалізації трансформації розроблене відповідне інструментальне
середовище у вигляді підсистеми трансформації ОНБМ (далі ПТ). Підсистема реалізує трансформацію БМ на
основі розроблених модифікованих алгоритмів, призначених для побудови вузлового дерева. В представленій
доповіді викладаються найбільш принципові питання побудови цієї системи.
Сервісні можливості моделі та архітектура підсистеми трансформації
До основних сервісів ПТ належать: створення екземпляра ООНБМ на основі вбудованого генератора
мережі; моралізація графа; створення вузлового дерева на основі класичного алгоритму; створення вузлового
дерева на основі модифікованого алгоритму.
Графічний інтерфейс ПТ (рис. 4) реалізовує доступ до відповідних функцій, що надає можливість
користувачу багаторазово виконувати перетворення різних ООБМ.
Рис. 4. Графічний інтерфейс підсистеми трансформації ООНБМ
На рис. 5 показано фрагмент інформаційного файлу, який містить інформацію загального характеру про
ООНБМ: вузли, екземпляри, зв’язки між ними, потенціали і т. д. Формат інформаційного файлу JSON: переваги
такого формату:
1) інформація подається в структурованому вигляді;
2) не потребує складних процедур читання/запису;
3) пітримується веб-технологіями для передачі даних через мережі.
Рис. 5. Фрагмент інформаційного файлу для ООНБМ в JSON-форматі
Генератор ООНБМ дозволяє створювати імовірнісні моделі різної складності: користувач вказує
кількість вузлів, максимальну та мінімальну кількість станів, групування вузлів, обмеження на нечіткі
параметри моделі. Після генерування модель візуалізується у графічному інтерфейсі (рис. 6). Після візуалізації
користувач вручну може внести зміни в структуру мережі.
Інтелектуальні інформаційні технології
183
Рис. 6. Візуалізований фрагмент ООНБМ (знак «+» означає, що вершина є екземпляром, який складається з
інших вузлів, наприклад, вузол «0» вказує на вхідний вузол «3» екземпляра {3, 10, 11, 12, 13})
Після візуалізації вхідної інформації, користувач може виконати перетворення над моделлю: моралізацію
та трансформацію у вузлове дерево двома способами (рис. 7).
Рис. 7. Візуалізований фрагмент ООНБМ (знак «+» означає, що вершина є екземпляром, який складається з
інших вузлів, наприклад, вузол «0» вказує на вхідний вузол «3» екземпляра {3, 10, 11, 12, 13})
Виконання класичного алгоритму трансформації ООНБМ в вузлове дерево передбачає триангуляцію
графа, тобто додавання ребер в граф за вибраним критерієм та утворення кластерів з вершин вхідної мережі.
Для роботи алгоритму використовується додаткова структура для зберігання попередньо складених списків
ребер-кандидатів на додавання в моральний граф. Під час виконання класичного алгоритму побудови
вузлового дерева відбуваються наступні операції.
1. Для кожної вершини морального графа:
а) створити підмножину vh , яка складається з трьох частин – список ребер, які додаються в граф,
згідно вибраного критерію [2, 10], їх кількість, вага кластера; vhHH .
2. Встановити початкове значення лічильника вершин n:i .
3. Поки існують ненумеровані вершини:
а) серед ненумерованих вершин v морального графа знайти таку підмножину Hhv , щоб кількість
ребер, які додаються в граф була мінімальною; якщо таких підмножин кілька, тоді серед них вибрати ту, що
створює найменший кластер за простором станів вузлів, які входять до кластера;
б) добавити нові ребра в моральний граф з підмножини vh , зберегти кластер vv ССС ;
в) вилучити вершину iv разом з інцидент ними їй ребрами в моральному графі, а також з усіх
підмножин uh , де u – суміжна з iv вершина;
г) зменшити лічильник вершин на 1.
Як показано в [10], за рахунок додаткового аналізу ребер, пошуку оптимальної кількості їх додавання
кількість кроків в алгоритмі поліноміально залежить від кількості вершин та оцінюється, як )O(n3 . Тому
важливим питання є вибір таких евристик, які б дозволили прискорити роботу алгоритму, збільшити його
ефективність.
Інтелектуальні інформаційні технології
184
В запропонованій модифікації наведеного вище алгоритмі застосовується той факт, що області
визначення нечітких потенціалів породжують кластери вузлового дерева. Якщо врахувати ці структурні
особливості нечітких потенціалів, тоді в алгоритмі відбуваються наступні кроки.
1. Впорядкувати множину нечітких потенціалів за спаданням розміру їх простору станів, тобто
розміру областей визначення потенціалів.
2. Якщо потенціал має в області визначення більше трьох змінних байєсівської мережі, то він, внаслідок
моралізації вхідного графа, вже створює повний підграф, тобто кластер. Для областей визначення кожного
такого потенціалу утворити кластер.
3. Якщо в області визначення нечіткого потенціалу дві змінні, тоді утворити множину з усіх не
розглянутих потенціалів, до яких входять ці змінні; в моральному графі відшукати найменший цикл, до якого
входять всі змінні потенціалів з утвореної множини; з змінних, які входять до мінімального циклу утворити
кластер.
Крок 3 наведеного алгоритму повторюється поки не розглянуті всі нечіткі потенціали вхідної моделі.
Згідно означення ООНБМ, кожній змінній ставиться у відповідність умовний або маргінальний
апріорний нечіткий потенціал. Якщо в ООНБМ n вузлів, тоді для аналізу кожного нечіткого потенціалу
потрібно n раз повторити третій крок алгоритму. На кожному такому кроці потрібно відшукати найменший
цикл – це можна зробити, використовуючи алгоритм пошуку в глибину, який згідно [14], має складність
e)O(n , де e – кількість ребер у графі. Як показано в [1, 2], більшість байєсівських мереж, в тому числі
ООНБМ, є розрідженими, тобто 2ne 2 . Тому у практичних задачах складність модифікованого алгоритму є
)O(n)nnC(nne)C(ne)nC(n 3222 . Таким чином, складність запропонованого алгоритму є
поліноміальною та меншою за 3n . На рис. 8 показано результати експерименту, де досліджувалась залежність
часу виконання алгоритму від кількості вузлів. Як видно з графіків – при збільшенні кількості вузлів в ООНБМ,
модифікований алгоритм показує більшу ефективність у порівняння з класичним алгоритмом розбудови
кластерів.
Рис. 8. Залежність часу виконання алгоритмів побудови кластерів для вузлового
дерева від кількості вузлів у ООНБМ
Після утворення кластерів виконується друга частина побудови вузлового дерева – з’єднання кластерів у
вузлове дерево. Основна ідея цього етапу, це впорядкування множини сепараторів перед циклом, в якому
будується дерево. Впорядковування такої множини зводиться до порівняння цілих чисел, які позначають розмір
простору станів тих змінних, які утворили відповідний кластер. Тому для сортування сепараторів можна
вибрати будь-який алгоритм сортування логарифмічної складності [14]. Схема алгоритму побудови вузлового
дерева буде наступною:
1. Для кожного кластера iC , відшукати кластер, який утворює сепаратор з найбільшим простором станів.
Якщо таких кластерів кілька, тоді вибрати довільний з них.
2. З’єднати знайдені кластери у дерево.
3. Повторити кроки 1 та 2 поки залишаються неприєднаними кластери.
Інтелектуальні інформаційні технології
185
Після утворення вузлового дерева до кластерів приєднуються нечіткі потенціали за правилом: область
визначення потенціалу має співпадати або бути підмножиною до множини вузлів, з яких складається кластер.
Приєднавши потенціали до кластерів, отримаємо готове вузлове дерево над яким застосовується імовірнісний
алгоритм виведення, зокрема, алгоритм розповсюдження довіри [11–13].
Особливості трансформації об’єктно-орієнтованих нечітких байєсівських мереж
Оскільки ООНБМ підтримують модульну структуру то в них можна проводити локальну
трансформацію, не перебудовуючи всю мережу. Для цього потрібно забезпечити виконання наступної умови:
жодних ребер не додається між вузлами, якщо вони належать різним екземплярам. Для виконання цієї умови
вище наведені алгоритми побудови вузлового дерева необхідно модифікувати наступним чином:
1) виконати утворення кластерів на основі зв’язків між екземплярами (глобальна трансформація);
2) створити кластери на основі зв’язків в самих екземплярах (локальна трансформація).
Алгоритм глобальної трансформації матиме наступні кроки.
1. Вибрати один з вузлів в якості кореневого вузла; кореневим вузлом може бути як базовий вузол, так і
екземпляр класу.
2. Впорядкувати множину потенціалів за спаданням розміру простору станів.
3. Згідно одного з вище наведених алгоритмів трансформації утворити кластери з вузлів та екземплярів.
Для ООНБ, показаної на рис. 3 вузлове дерево після глобальної трансформації буде складатись з трьох
кластерів (рис. 9).
Рис. 9. Результат глобальної трансформації для ООНБМ з рис. 3
Під час виконання глобальної трансформації отримується валідне дерево глобальних кластерів, оскільки
описаний алгоритм гарантує. що немає зв’язків між вузлами, які належать різним екземплярам та є
прихованими.
По завершенню глобальної трансформації можна виконувати локальну трансформацію окремих
екземплярів. Єдина вимога ставиться до екземплярів, що вхідні вузли екземпляру розглядаються останніми.
При цьому оптимальна трансформація екземплярів не гарантує оптимальності для глобальної трансформації
мережі. Однак, при внесенні змін в екземпляр, достатньо буде виконати повторну трансформацію екземпляру, а
не всієї мережі.
Складніший процес виникає, коли ООНБМ трансформована в вузлове дерево, а після цього вносяться
зміни в її структуру. В такому випадку необхідно правильно визначити локальні вогнища трансформації і
виконати її лише для визначених кластерів (рис. 10).
Можливі чотири випадки:
1) вилучення або додавання вузла чи ребра у вхідну ООНБМ;
2) вилучення або додавання ребра, утвореного внаслідок трансформації мережі в вузлове дерево;
3) вилучення або додавання екземпляру;
4) зміна специфікації мережного класу.
Зауважимо, що лише в останньому випадку виникає потреба глобальної трансформації. Для решти
випадків достатньо трансформації правильно локалізувати.
У першому випадку, коли вилучається чи добавляється вузол, ребро, необхідно:
1) виконувати локальну трансформацію в межах екземпляру, якщо це приховані вузли;
Інтелектуальні інформаційні технології
186
2) якщо зміни відбуваються з інтерфейс ними вузлами екземпляру, тоді локальна трансформація
відбувається для екземпляру та сусіднього вузла з відповідного сусіднього екземпляру.
Якщо додається ребро між екземплярами, то це не веде до виконання алгоритму трансформації. Зміни в
зв’язках між екземплярами ведуть до зміни інтерфейсу екземпляру та апріорного нечіткого потенціалу для
вхідних вузлів, але трансформація екземплярів не виконується.
Рис. 10. Результат локальної трансформації в екземплярах ООНБМ з рис. 3
У випадку, коли додається новий екземпляр, то локальна трансформація не відбувається. Саме ж дерево
екземплярів буде оновлюватись, тобто доповнюватись новим під деревом. загальне вузлове дерево
перетвориться на ліс.
Видалення екземпляру здійснюється шляхом вилучення піддерева з вузлового дерева та повторно буде
виконана локальна трансформація для батьківського екземпляра. Зміна специфікацій може включати будь-яку з
описаних вище трьох ситуацій. Такі ситуації, якщо виникають часто, тоді зручно буде дочекатись завершення
внесення змін в мережу, а лише потім виконати глобальну та локальні трансформації.
Важливо відмітити, що вся інформація, яка необхідна для виконання трансформації буде доступна
локально в кожному екземплярі після виконання глобальної трансформації. Якщо зміни були внесені в клас, то
варто лише змінити екземпляри цього класу. Вибір між лише локальною трансформацією та поєднання її з
глобальною залежатиме від кількості внесених змін та складності зв’язків у самій мережі.
Висновок
Описані в роботі алгоритми трансформації є спільними для НБМ та ООНБМ в тому, що вони вимагають
аналізу зв’язків між складовими моделі. Відмінністю в цих алгоритмах є вираховування гранулярності ООНБМ
та виконання двічі алгоритму трансформації: спочатку для глобальних зв’язків, а потім для локальних
екземплярів. Екперименти з алгоритмами трансформації показали напрямки покращення ефективності їх
виконання на основі аналізу області визначення нечітких потенціалів. Створена підсистема трансформації
дозволяє візуально оцінити ефективність роботи алгоритмів та дослідити ООНБМ різної складності за своєю
структурою.
1. Сowell R.G., Dawid A.P., Spiegelhalter D.J., Lauritzen S.L. Probabilistic Networks and Expert Systems. – Springer–Verlag, New York, Inc.,
1999. – 321 p.
2. Kjaerulff U.B., Madsen A.L. Bayesian Networks and Influence Diagrams. – Springer Science+Business Media, LLC, 2008. – 318 p.
3. Заде Л.А. Основы нового подхода к анализу сложных систем и процессов принятия решений // Математика сегодня (сборник статей,
перевод с англ.). М.: Знание, 1974 . – С. 5–48.
4. Верьовка О.В., Парасюк И.Н. О распространении вероятностей в нечетких байесовских сетях с недетерминированными состояниями
// Кибернетика и системный анализ. – 2008. – № 6. – С. 153–169.
5. Парасюк И.Н., Костукевич Ф.В. Методы трансформации байесовской сети для построения узлового дерева и их модификация //
Компьютерная математика. К.: Ин-т кибернетики им. В.М.Глушкова НАН Украины. – 2008. – № 1. – C. 70–80.
6. Парасюк И.Н., Костукевич Ф.В. Нечеткие потенциалы и вопросы их применения в алгоритмах распространения доверия на
байесовских сетях // Компьютерная математика. К.: Ин-т кибернетики им. В.М.Глушкова НАН Украины. – 2009. – № 1. – С. 67–75.
7. Парасюк И.Н., Костукевич Ф.В. Об одном эффективном алгоритме распространения вероятностей в нечетких байесовских сетях
доверия // Компьютерная математика. К.: Ин-т кибернетики им. В.М.Глушкова НАН Украины. – 2010. – № 2. – С. 102–112.
8. Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. – Morgan Kaufmann, San Mateo, CA, 1991. – 552 p.
9. Lauritzen S.L., Spiegelhalter D.J. Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems //
Journal of the Royal Statistical Society, Series B. – 1988. – Vol. 50, N 2. – P. 157–224.
10. Heggernes P. Minimal triangulations of graphs: A survey // Discrete Mathematics, Volume 306, Issue 3. – Department of Informatics,
University of Bergen, N-5020 Bergen, Norway, 2006. – P. 297–317.
Інтелектуальні інформаційні технології
187
11. Shenoy P.P., Shafer G. Axioms for probability and belief-function propagation. // In Uncertainty in Artificial Intelligence 4, 1990. –
P. 169–198.
12. Jensen F., Lauritzen S., Oesen K. Bayesian updating in causal probabilistic networks by local computations // SIAM Journal on Computing, 4,
1990. – P. 269–282.
13. Lepar V., Shenoy P. A comparison of Lauritzen-Spiegelhalter, Hugin and Shenoy-Shafer architectures for computing marginals of probability
distributions // In G. Cooper and S. Moral, editors, Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI-98),
Morgan Kaufmann, 1998. – P. 328–337.
References
1. Сowell R.G., Dawid A.P., Spiegelhalter D.J., Lauritzen S .L. (1999) Probabilistic Networks and Expert Systems. – Springer–Verlag, New York,
Inc.
2. Uffe B. Kjaerulff, Anders L. Madsen (2008) Bayesian Networks and Influence Diagrams. – Springer Science+Business Media, LLC
3. Lotfy Zade (1974) Problem is based on a new approach to the analysis of complex systems and decision-making processes // Mathematics
Today (collection of articles translated from English.). M. "Knowledge".
4. Verovka O.V., Parasjuk I .N. (2008) On the propagation of probabilities in Bayesian networks with fuzzy non-deterministic states // Cybernetics
and Systems Analysis, №6.
5. Parasyuk I.M., Kostukevich F.V. (2008) The methods of transform Bayesian network methods to construct a tree of nodes and their
modification // Computer mathematics, №1, K .: Institute of Cybernetics Glushkov National Academy of Sciences of Ukraine.
6. Parasyuk I.M., Kostukevich F.V. (2009) Fuzzy potentials and problems of their use in algorithms spread confidence in the Bayesian networks //
Computer mathematics, №1.- K. : Institute of Cybernetics. Glushkov National Academy of Sciences of Ukraine.
7. Parasyuk I.M., Kostukevich F.V. (2010) An efficient algorithm of fuzzy probability distribution in Bayesian networks of trust / / Computer
mathematics, №2.- K .: Institute of Cybernetics. Glushkov. National Academy of Sciences of Ukraine.
8. Pearl J. (1991) Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. – Morgan Kaufmann, San Mateo, CA.
9. Steffen L. Lauritzen, David J. Spiegelhalter (1988) Local Computations with Probabilities on Graphical Structures and Their Application to
Expert Systems // Journal of the Royal Statistical Society, Series B, Vol. 50, No. 2.
10. Pinar Heggernes (2006) Minimal triangulations of graphs: A survey// Discrete Mathematics, Volume 306, Issue 3. – Department of Informatics,
University of Bergen, N-5020 Bergen, Norway
11. Shenoy P.P. and Shafer G. (1990) Axioms for probability and belief-function propagation. // In Uncertainty in Artificial Intelligence 4
12. F. Jensen, S. Lauritzen, and K. Oesen (1990) Bayesian updating in causal probabilistic networks by local computations // SIAM Journal on
Computing, 4.
13. V. Lepar and P. Shenoy. (1998) A comparison of Lauritzen-Spiegelhalter, Hugin and Shenoy-Shafer architectures for computing marginals of
probability distributions. // In G. Cooper and S. Moral, editors, Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence
(UAI-98), Morgan Kaufmann
Про авторів:
Єршов Сергій Володимирович,
доктор фізико-математичних наук, завідувач відділу.
Кількість наукових публікацій в українських виданнях – 63.
Кількість наукових публікацій в іноземних виданнях – 9,
Костукевич Фелікс Віталійович,
вчитель вищої категорії.
Кількість наукових публікацій в українських виданнях – 6.
Кількість наукових публікацій в іноземних виданнях – 1.
Місце роботи авторів:
Інститут кібернетики імені В.М. Глушкова НАН України,
03680, Київ-187, проспект Академіка Глушкова, 40.
Тел.: (044) 526 6422.
E-mail: sershv@ukr.net.
Маяківський навчально-виховний комплекс
“Загальноосвітня школа-інтернат I-III ступенів – лінгвістичний ліцей”,
45630, вул. 17 Вересня, 72, c. Маяки, Луцький район, Волинська область.
Тел.: (332) 79 1539.
E-mail: felkost@gmail.com.
mailto:felkost@gmail.com
|