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

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

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

УДК 004.855:681.518

МОДЕЛІ І МЕТОДИ ПОБУДОВИ ТА АНАЛІЗУ БАЙЄСІВСЬКИХ МЕРЕЖ ДЛЯ ІНТЕЛЕКТУАЛЬНОГО АНАЛІЗУ ДАНИХ

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

Автореферат

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

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

ТЕРЕНТЬЄВ ОЛЕКСАНДР МИКОЛАЙОВИЧ

КИЇВ 2009



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

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

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

Навчально-науковий комплекс “Інститут прикладного системного аналізу” Національного технічного університету України “Київський політехнічний інститут”, провідний науковий співробітник відділу математичних методів системного аналізу.

Офіційні опоненти: доктор технічних наук, професор Гриша Сергій Миколайович, Національний технічний університет України „Київський політехнічний інститут”, професор кафедри автоматизованих систем обробки інформації та управління;

кандидат технічних наук, доцент Баклан Ігор Всеволодович, Національна академія управління,

завідуючий кафедрою інтелектуальних систем.

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

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

Автореферат розісланий “ 16 ” квітня 2009 р.

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

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

д.т.н., професор О.М. Новіков



АНОТАЦІЇ

Терентьєв О.М. Моделі і методи побудови та аналізу байєсівських мереж для інтелектуального аналізу даних. - Рукопис.

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

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

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

Розроблена і програмно реалізована оригінальна система підтримки прийняття рішень для інтелектуального аналізу даних на основі БМ, яка грунтується на запропонованих методах побудови структури та ймовірнісного висновку. СППР впроваджена в першій київській філії ВАТ VAB “ВіЕйБі Банк”, що дало можливість побудувати ефективні прогнозуючі моделі для підтримки прийняття рішень з метою оцінки ризиків при кредитуванні фізичних осіб. Наукові результати використані у навчальних курсах НТУУ „КПІ”.

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

інтелектуальний дискретний байєсівський мережа



Терентьев А.Н. Модели и методы построения и анализа байесовских сетей для интеллектуального анализа данных. - Рукопись.

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

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

Для построения структуры БС предложен эвристический метод обучения линейной сложности по статистическим данным. Для определения меры связи между вершинами метод использует значение взаимной информации, а в качестве функции оценивания структуры модели - описание минимальной длиной (ОМД). Также разработан метод построения точного вероятностного вывода в БС по учебным данным. Для вычисления значений вероятностей состояний вершин вместо таблиц условных вероятностей используется матрица эмпирических значений общего распределения вероятностей всей сети. Для оценивания качества построенной структуры в работе предложена новая модификация, которая в отличие от функции Купера-Герсковича, существенно ускоряет процесс вычислений и снимает ограничение на размер выборок данных.

Разработана и программно реализована оригинальная СППР для интеллектуального анализа данных на основе БС, которая основывается на предложенных методах построения структуры и вероятностного вывода. СППР внедрена в первом отделении киевского филиала ОАО VAB Банк, что дало возможность построить эффективные прогнозирующие модели для поддержки принятия решений при оценке рисков кредитования физических лиц. Полученные научные результаты использованы также в учебных курсах НТУУ «КПИ».

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



Terentyev O.M. Models and methods of construction and analysis of the Bayesian networks for the intellectual data analysis. - Manuscript.

Thesis in fulfillment of the requirements for the degree of candidate of engineering sciences on the speciality 05.13.06 - Information technologies. - National Technical University of Ukraine “Kyiv Polytechnic Institute”, Kyiv, 2009.

The thesis deals with the problem of improvement of speed and quality of data mining by development of a new method for construction and application of discrete Bayesian networks (BN), methods of generation of probabilistic inference and creating on their basis of the new decision support system. A review and analysis of methods for intellectual data analysis is proposed and substantiation of efficiency of BM vehicle application is considered.

To construct BN structure a heuristic learning procedure is developed that is characterized by linear complexity and uses statistical data for learning. To determine a measure of interaction between the nodes the method uses values of mutual information. As a scoring measure for determining the model structure the minimum description length is used (MDL). It has also been proposed the method for exact probabilistic inference generation which uses the matrix of empirical values of joint distribution of nodes for the whole net instead of the conditional probability table. To evaluate the quality of the net constructed a new modification of Cooper-Herskovits function is proposed that is distinguished with substantially shorter computing time and relieves the restriction to the learning data size.

An original decision support system has been developed and implemented for intellectual data analysis on the basis of BN. The system is based on the proposed methods of BN structure learning and probabilistic inference generation. The DSS is been used in the first Kiev branch of VAB Bank what resulted in the possibility of development of effective forecasting models to support decision making aiming estimating and minimization of credit risks for bank clients. The scientific results acquired are also been used in several student courses at the NTUU “KPI”.

Keywords: Bayesian network, probabilistic inference, machine learning, data mining.



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

Актуальність теми дисертаційного дослідження

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

В рамках системного аналізу для опису концепцій і методів, які поліпшують бізнесові рішення шляхом використання систем підтримки прийняття рішень (СППР), у 1980-х роках запропоновано термін “Business Intelligence” (BІ), діловий інтелект, бізнес-аналітика або бізнес-інтелект. Бізнес-інтелект складається з алгоритмічно-програмних продуктів таких класів: (1) засоби побудови сховищ даних; (2) системи оперативної аналітичної обробки даних; (3) інформаційно-аналітичні системи; (4) засоби інтелектуального аналізу даних (ІАД); (5) інструменти для реалізації запитів і побудови звітів. Значний вклад у розробку методів інтелектуального аналізу даних внесли зарубіжні та вітчизняні вчені, зокрема В. М. Глушков, О. Г. Івахненко, Г. С. Поспелов, М. З. Згуровський, О. А. Павлов, Н. Д. Панкратова, Д. В. Єфімов, Г. П'ятецький-Шапіро, Дж. Перл, К. Мерфі, Р. Шехтер, Р. Дехтер.

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

Актуальність застосування БМ в якості інструменту ІАД визначило тему і напрями дисертаційних досліджень.

Зв'язок роботи з науковими програмами, планами, темами

Дисертаційна робота виконувалась у відповідності до науково-дослідних робіт, виконаних в ННК “ІПСА” НТУУ “КПІ”: “Розробка якісно-кількісного методу ситуаційного аналізу на основі байєсівських мереж” (№ ДР 0103U000528; 2003-2005р.); “Розробка методів аналізу, прогнозування та діагностики процесів з невизначеностями на основі байєсівської теорії” (№ ДР 0106U000246, 2006-2008р.); “Інтелектуальний аналіз слабоструктурованих даних за допомогою байєсових мереж” (грант НТУУ “КПІ” № 3/5-ГР, 2006-2007р.)

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

Досягнення сформульованої мети вимагає постановки і розв'язання таких задач:

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

2. Розробити евристичний метод побудови топології БМ за навчальними даними із застосуванням функції опису мінімальної довжини (ОМД).

3. Створити точний метод побудови ймовірнісного висновку в мережі Байєса за навчальними даними.

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

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

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

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

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

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

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

2. За оціночну функцію для методу евристичної побудови БМ запропонована модифікація функції Купера-Герсковича (ФКГ). Її перевага у порівнянні з функцією ФКГ полягає у переході від обчислення факторіалів до сум, що суттєво прискорює процес обчислень та знімає обмеження на розмір вибірок навчальних даних.

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

4. На основі запропонованих методів і алгоритмів розроблена та програмно реалізована оригінальна інформаційна СППР для ІАД на основі БМ, яка застосована для розв'язання прикладних задач.

Практичне значення одержаних результатів. В результаті виконаного дисертаційного дослідження запропоновано новий евристичний метод побудови топології БМ та формування ймовірнісного висновку за навчальними даними. На основі запропонованих методів розроблена та реалізована оригінальна архітектура системи підтримки прийняття рішень для ІАД на основі БМ, яка придатна для розв'язання практичних задач моделювання, класифікації та прогнозування. За цією структурою запропоновано пристрій для обробки слабоструктурованих даних [1].

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

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

Результати роботи впроваджені в навчальний процес кафедри математичних методів системного аналізу ННК “Інститут прикладного системного аналізу” Національного технічного університету “Київський політехнічний інститут” і використовуються в курсі “Проектування комп'ютерних інформаційних систем”.

Особистий внесок здобувача

Всі наукові положення і результати, що складають основний зміст роботи, автором отримані самостійно. В працях, написаних у співавторстві, здобувачеві належать: дослідження різних типів БМ та їх практичного використання [8, 9]; підходи та структури методів побудови топології БМ [4, 6, 7]; методи та алгоритми побудови імовірнісного висновку в БМ [5, 9]; опис оціночних функцій ОМД та МФКГ для побудови БМ [7, 9].

Апробація результатів дисертації. Основні положення роботи доповідались і обговорювались на наступних міжнародних семінарах, конференціях і симпозіумах, презентувались в збірках наукових праць з метою апробації поточних результатів досліджень: міжнародні науково-практичні конференції з автоматичного керування “Автоматика” - 2004, 2007 [10,11]; міжнародні науково-практичні конференції „Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій” (ISDMIT - 2005, 2006, 2007) [12, 13, 14]; міжнародна науково-практична конференція “Інтелектуальні системи прийняття рішень та проблеми обчислювального інтелекту” (ISDMCI-2008) [15]; міжнародна науково-практична конференція “Системний аналіз та інформаційні технології” (САІТ-2007) [16]; міжнародна науково-практична конференція “Інформаційні технології і інформаційна безпека в науці, техніці та освіті” (InfoTech-2007) [17]; міжнародна науково-практична конференція “Математичне та програмне забезпечення інтелектуальних систем” (MPZIS-2007, 2008) [19, 22]; науково-технічна конференція “Моделювання-2008” [20]; міжнародна науково-практична конференція “Control and Optimization with Industrial Application” (COIA-2008) [21]; міжнародна науково-практична конференція “Проблеми впровадження інформаційних технологій в економіці” [18].

Публікації. За матеріалами дисертаційних досліджень опубліковано 22 друкованих наукових праці, з них 7 у фахових виданнях, перелік яких затверджений ВАК України [3-9], отримано 1 патент на винахід України [1], 1 авторське свідоцтво на комп'ютерну програму [2] та 13-и матеріалах і тезах науково-технічних конференцій [10-22].

Структура та обсяг роботи

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

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

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

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

В рамках технології ІАД широке застосування знайшла теорія БМ, яка виникла на перетині двох наук: теорії ймовірностей і теорії графів. Термін “байєсівська мережа” запропонував Джуді Перл у 1985 році з метою акцентування трьох аспектів: (1) об'єктивної природи вхідних даних; (2) отримання достовірної інформації при застосуванні теореми Байєса; (3) ідея дослідження причин та наслідків, запропонована в 1763 році в роботі Томаса Байєса.

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

Другий розділ присвячено опису граф-теоретичного представлення БМ у вигляді дерева, полідерева та мережі. Виконано аналіз інформаційних потоків (повідомлень), які мають місце між вузлами мережі.

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

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

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

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

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

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

Алгоритм евристичного методу побудови БМ за навчальними даними

Другий етап.

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

Як приклад побудови топології БМ із використанням запропонованого евристичного методу розглянута мережа "Азія", що складається з 8 вершин: 1 - “Чи палите?”; 2 - “Рак легенів”; 3 - “Туберкульоз”; 4 - “Туберкульоз або рак”; 5. “Чи відвідували Азію?”; 6 - “Рентгенограма”; 7 - “Бронхіт”; 8 - “Задишка?”. Навчальна вибірка складається з 7200 записів. В табл. 1 наведені ЗВІ між усіма вершинами, що обчислюються на першому етапі алгоритму.

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

Всього проаналізовано 84 структури на 28 ітераціях алгоритму, тоді як при звичайному повному переборі потрібно проаналізувати 783 702 329 343 структур. На рис. 3 наведено графік зміни чисельного значення функції ОМД в залежності від кількості ітерацій алгоритму. Найкраща структура мережі знайдена на 15-й ітерації, саме тому функція ОМД після цієї ітерації не спадає.

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

Окрім функції ОМД другою розповсюдженою функцією для побудови структури БМ є ФКГ:

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

Порівняння ефективності оціночних функцій. Результати наведених у розділі обчислювальних експериментів показали що на коротких навчальних вибірках (до 170 записів) і мережах, що складаються не більш ніж з 10 вершин, ФКГ працює швидше у порівнянні з функціями МФКГ та ОМД. Але функції МФКГ та ОМД, на відміну від ФКГ, можуть працювати з навчальними вибірками будь-якого розміру. Також з'ясовано, що методи побудови БМ із використанням ФКГ та її модифікацій, можуть перенавчати БМ, тобто такі мережі часто містять зайві дуги.

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

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

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

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

Алгоритм методу.

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

Вихідні дані: значення ймовірностей всіх можливих станів усіх неінстанційованих вершин.

П'ятий розділ присвячено розробці комп'ютерної інформаційної системи підтримки прийняття рішень для інтелектуального аналізу даних на основі байєсівських мереж (СППР ІАД БМ) [1], яка грунтується на запропонованих в попередніх розділах методах побудови топології та ймовірнісного висновку в БМ.

На підставі розробленої архітектури створена комп'ютерна СППР [2], яка забезпечує виконання таких функцій: (1) введення та накопичення інформації кількісного і якісного характеру, що надходить від експертів та баз даних; (2) побудову ймовірнісних моделей у вигляді БМ і (3) формування ймовірнісного висновку стосовно того чи іншого заданого стану процесу. Розроблена система відноситься до типу СППР-генератора, оскільки кожна БМ, побудована на основі навчальних даних, представляє собою причинно-наслідкову мережу, яку можна наближено розглядати як окрему СППР.

Наведені приклади використання комп'ютерної системи побудови моделей процесів різної природи, а саме: (1) скорингова система (рис. 6) для оцінювання кредитоспроможності фізичних осіб у вигляді мережі Байєса для першої філії Ві Єй Бі банку; (2) модель прогнозування композитного індексу Нью-йоркської фондової біржі для ТОВ “Smart Group”; (3) медична експертна система прогнозування інфаркту міокарда у вигляді мережі Байєса (для навчання використана база даних медичного університету Нью-Джерсі).

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

При моделюванні та прогнозуванні композитного індексу Нью-йоркської фондової біржі для ТОВ “Smart Group”, що працює на фондових ринках, за даними сайту Нью-Йоркської фондової біржі http://www.nyse.com сформована навчальна вибірка із 500 значень. В 96% випадків точно спрогнозовано зростання або спадання значень композитного індексу, а в 52% випадків оцінки прогнозів та реальні значення відхилень композитного індексу від значень в попередні моменти часу повністю збіглися.

Для побудови скорингової моделі використана база даних клієнтів з 3347 записів, а для перевірки прогнозуючих характеристик - вибірка із 100 записів. Змінні процесу представлені десятьома атрибутами: 1 - стать; 2 - вік; 3 - сімейний стан; 4 - кількість дітей; 5 - чоловік (дружина) працює; 6 - освіта; 7 - тип трудозайнятості; 8 - поручитель; 9 - сума кредиту; 10 - результат (кредитоспроможний чи ні?).

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

В додатках докладно розглянута задача побудови скорингової системи із використанням сучасних методамів ІАД, а саме: (1) кластерного аналізу; (2) дерев рішень, (3) регресійного аналізу та (4) штучних нейронних мереж (ШНМ). В табл. 3 та 4 наведені отримані результати. Серед моделей, побудованих у вигляді ШНМ, кращими виявилися мережі, наведені в табл. 4, з двома та трьома нейронами у прихованому шарі. Інші, складніші архітектури, погано навчалися або зовсім не навчалися. Для алгоритму Resilient propagation було задано 2000 епох навчання.

Скорингова система, створена при використанні СППР ІАД БМ, дала 15% похибок при класифікації нових клієнтів з тестової вибірки, а це означає, що із 100 виданих кредитів 15 класифіковані некоректно.

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

Додатки містять опис пристрою для обробки слабоструктурованих даних на основі мереж Байєса [1] та акти впровадження дисертаційної роботи.



ВИСНОВКИ

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

2. Для побудови структури БМ запропоновано евристичний метод навчання лінійної складності за статистичними даними. Для визначення міри зв'язку між вершинами метод використовує значення взаємної інформації, а в якості функції оцінювання структури моделі - опис мінімальною довжиною (ОМД). Швидкодія побудови моделей, у порівнянні з методами повного перебору, зростає в 10-20 разів.

3. Розроблено метод побудови точного ймовірнісного висновку в БМ за навчальними даними. Для обчислення значень ймовірностей станів вершин замість таблиць умовних ймовірностей використовується матриця емпіричних значень спільного розподілу ймовірностей всієї мережі. Головними перевагами методу є залежність швидкості роботи тільки від розміру навчальної вибірки, відсутність потреби у попередньому перетворенні структури БМ та простота її реалізації. Швидкодія побудови ймовірнісного висновку зростає в 2-5 разів.

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

5. Розроблена і програмно реалізована оригінальна інформаційна система підтримки прийняття рішень для інтелектуального аналізу даних на основі БМ, яка грунтується на запропонованих методах побудови структури та ймовірнісного висновку. СППР впроваджена в першій київській філії ВАТ VAB “ВіЕйБі Банк”, що дало можливість побудувати ефективні прогнозуючі моделі для підтримки прийняття рішень з метою оцінювання ризиків кредитування фізичних осіб.

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



СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ за темою дисертації

1. Пат. 28751 U України, МПК G 06 F 17 / 17, F 17/18, F 17/30 . Пристрій для обробки слабоструктурованих даних на основі мереж Байєса / Терентьєв О.М., Бідюк П.І., Коршевнюк Л.О. (Україна). - № u200707506 ; заявл. 04.07.2007; опубл. 25.12.2007, Бюл. “Промислова власність” № 21.

2. А. с. 20853 України Комп'ютерна програма “Інформаційна система підтримки прийняття рішень для інтелектуального аналізу даних на основі Байєсових мереж” / О. М. Терентьєв - № 20918; заявл. 16.04.2007; опуб. 11.06.2007.

3. Терентьев А. Н., Методы построения байесовских сетей / А. Н. Терентьев, П. И. Бидюк // Межведомственный научно-технический сборник „Адаптивные системы автоматического управления”. - Днепропетровск: Системные технологии, 2005. - № 8. - С. 130-141.

4. Бидюк П. И. Построение и методы обучения байесовских сетей / П. И. Бидюк, А. Н. Терентьев, А. С. Гасанов // Кибернетика и системный анализ. - 2005. - № 4. - C. 134-147.

5. Бидюк П. И. Метод вероятностного вывода в байесовских сетях по обучающим данным / П.И. Бидюк, А.Н. Терентьев // Кибернетика и системный анализ. - 2007. - № 3. - C. 93-99.

6. Згуровский М. З. Методы построения байесовских сетей на основе оценочных функций / М. З. Згуровский, П.И. Бидюк, А.Н. Терентьев // Кибернетика и системный анализ. - 2008. - № 2. - C. 81-88.

7. Терентьев А. Н. Эвристический метод построения байесовских сетей / А.Н. Терентьев, П.И. Бидюк // Математические машины и системы. - К.: ТОВ “РВПК ЕКСЛИБРИС”, 2006. - № 3. - С. 12-23.

8. Терентьев А. Н. Байесовская сеть - инструмент интеллектуального анализа данных / А.Н. Терентьев, П.И. Бидюк, Л.А. Коршевнюк // Проблемы управления и информатики. - К.: ИКИ НАНУ-НКАУ, 2007. - № 4. - С. 83-92.

9. Згуровський М. З. Системна методика побудови байєсових мереж / М.З. Згуровський, П.І. Бідюк, О.М. Терентьев // “Наукові вісті” НТУУ “КПІ”. - 2007. - №4. - С. 47-61.

10. Бідюк П. І. Застосування байєсівського підходу в медичній діагностиці / П. І. Бідюк, О. М. Терентьєв / Автоматика-2004: зб. наук. праць за матеріалами XI міжнар. конф., 27-30 вер. 2004 р., Київ. - К.: НУХТ, 2004. - Т. 3 - С. 32.

11. Бидюк П.И. Прогнозирование экономических показателей при помощи сетей Байеса / П.И. Бидюк, А.Н. Терентьев, Л.А. Коршевнюк / Автоматика-2007: зб. наук. праць за матеріалами XIV міжнар. конф., 10-14 вер. 2007 р., Севастополь. - Севастополь: СНУЯЄтаП, 2007. - Т. 2 - С. 91-93.

12. Терентьев А.Н. Использование метода минимальной длины описания при обучении байесовской сети доверия / А.Н. Терентьев, П.И. Бидюк / Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий: сб. науч. трудов по материалам I-й междунар. конф., 18-21 мая 2005 г., Евпатория. - Херсон: ХМИ, 2005.- Т. 1. - С. 151-152.

13. Терентьев А.Н. Эвристический метод построения байесовских сетей / А.Н. Терентьев, П.И. Бидюк / Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий: сб. науч. трудов по материалам II междунар. конф., 15-18 мая 2006 г., Евпатория. - Херсон: ХМИ, 2006.- Т. 1. - С. 401-403.

14. Бидюк П. И. Применение байесовских сетей для интеллектуального анализа данных / П. И. Бидюк, А. Н. Терентьев, Л. А. Коршевнюк / Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий: сб. науч. трудов по материалам III междунар. конф., 15-18 мая, 2007 г., Евпатория. - Херсон: ПП Вишемирський В. С., 2007 - Т. 2. - С. 15-17.

15. Терентьев А. Н. Использование байесовских сетей в кредитном скоринге / А. Н. Терентьев, П. И. Бидюк / Интеллектуальные системы принятия решений и проблемы вычислительного интеллекта: сб. науч. трудов по материалам междунар. конф., 19 мая-23 мая 2008 г., Евпатория. - Херсон: ПП Вишемирский В. С., 2008. - Т. 3, №2 - С. 101-103.

16. Терентьев А.Н. Алгоритм вероятностного вывода в байесовских сетях / А.Н. Терентьев, П.И. Бидюк, Л.А. Коршевнюк / Системный анализ и информационный технологии: сб. науч. трудов по материалам IX междунар. науч.-тех. конф., 15-19 мая 2007 г., Киев. - К.: Екмо, 2007. - С. 76.

17. Бидюк П.И. Использование модифицированной логарифмической функции Купера-Герсковича при построении сетей Байеса / П.И. Бидюк, А.Н. Терентьев, Л.А. Коршевнюк / Информационные технологии и информационная безопасность в науке, технике и образовании: сб. науч. трудов по материалам междунар. науч.-прак. конф., 10 -16 сентября 2007 г. - Севастополь: СевНТУ, 2007. - Т. 2. - С. 6-8.

18. Бидюк П.И. Метод формирования вывода в Байесовских сетях и его использование для прогнозирования ФЭП / П.И. Бидюк, А.Н. Терентьев, А.С. Гасанов / Проблемы внедрения информационных технологий в экономике: сб. науч. трудов по материалам междунар. науч.-прак. конф., 31 мая - 1 июня.2007 г., Ирпень,. - С. 334-337.

19. Терентьєв О.М. Застосування SPI-методу для формування ймовірносного висновку в мережах Байєса / О.М. Терентьєв, П.І. Бидюк / Математичне та програмне забезпечення інтелектуальних систем: зб. наук. праць за матеріалами V міжнар. наук.-прак. конф., 14-16 лист. 2007 р., Дніпропетровськ. - Дніпропетровськ: ДНУ, 2007. - С. 189-190.

20. Бидюк П.И. Дифференциальный подход для формирования вероятностного вывода в сетях Байеса / П.И. Бидюк, А.С. Гасанов, А.Н. Терентьев / Моделирование: сб. науч. трудов по материалам междунар. науч.-тех. конф., 10-11 января 2008 г., Киев. - Львов: ПП “Системы, технологии, информационные услуги”, 2008. - С. 7-8.

21. Terentyev A. N. Bayesian networks in credit scoring / A. N. Terentyev, L. T. Gasanova / The second international conference on control and optimization with industrial applications (COIA-1008), June 2-8, 2008, Baku, Azerbaijan. - Baku: Institute of applied mathematics BSU, 2008. - P. 171.

22. Терентьєв О.М. Оцінювання кредитоспроможності фізичних осіб за допомогою дерев рішень / О.М. Терентьєв, П.І. Бідюк, А.С. Гасанов, К.О. Свердел / Математичне та програмне забезпечення інтелектуальних систем: зб. наук. праць за матеріалами VI міжнар. наук.-прак. конф., 12-14 лист. 2008 р., Дніпропетровськ. - Дніпропетровськ: ДНУ, 2008. - С. 296-297.

Размещено на Allbest.ru