НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ
НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ
ІНСТИТУТ КІБЕРНЕТИКИ ім. В.М. Глушкова
ДЮЛІЧЕВА Юлія Юріївна
УДК 519.68
МОДЕЛІ КОРЕКЦІЇ
РЕДУКОВАНИХ БІНАРНИХ РОЗВ’ЯЗУЮЧИХ ДЕРЕВ
01.05.01 - Теоретичні основи інформатики та кібернетики
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ - 2004 р.
Дисертацією є рукопис.
Робота виконана в Таврійському національному університеті
ім. В.І. Вернадського, м. Сімферополь.
Науковий керівник доктор фізико-математичних наук, професор
Донськой Володимир Йосипович, завідувач
кафедри інформатики, декан факультету
математики та інформатики Таврійського
національного університету ім. В.І. Вернадського
Офіційні опоненти: доктор фізико-математичних наук, професор
Кнопов Павло Соломонович, завідувач
відділом математичних методів
дослідження операцій, Інститут кібернетики
ім. В.М. Глушкова НАН України
доктор технічних наук, професор
кафедри математичних методів системного
аналізу Бідюк Петро Іванович, Інститут
прикладного системного аналізу НАН України
та Міністерства освіти і науки України
Провідна установа Київський національний університет ім. Тараса
Шевченка, кафедра системного аналізу
та теорії прийняття рішень, м. Київ
Захист відбудеться “24” вересня 2004 р. о 11 годині
на засіданні спеціалізованої вченої ради Д 26.194.02 в Інституті
кібернетики ім. В.М. Глушкова НАН України, 03022, м. Київ,
просп. Глушкова, 40.
З дисертацією можна ознайомитись в науково-технічному
архіві Інституту кібернетики ім. В.М. Глушкова НАН України,
03022, м. Київ, просп. Глушкова, 40.
Автореферат розісланий “25” червня 2004 р.
Учений секретар
спеціалізованої вченої ради В.Ф. Синявський
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Дисертаційна робота присвячена дослідженню й удосконаленню алгоритмів навчання і розпізнавання, заснованих на побудові бінарних розв’язуючих дерев; розробці обґрунтованих правил редукції бінарних розв’язуючих дерев, заснованих на оцінюванні кон’юнктивних закономірностей; створенню послідовної процедури синтезу сукупності розв’язуючих дерев - алгоритму синтезу емпіричного розв’язуючого лісу - і методів корекції сукупності редукованих розв’язуючих дерев як набору евристичних процедур прийняття рішень.
Актуальність теми. Задача навчання розпізнаванню за прецедентами є однією з центральних задач кібернетики. Фахівців у галузі розпізнавання образів розв’язуючі дерева (РД) приваблюють можливістю “стислого” опису заданої численності навчальних прецедентів, простотою програмної реалізації РД. На фоні інших класифікуючих моделей розв’язуючі дерева вигідно виділяються можливістю подання виявлених емпіричних закономірностей у вигляді, що легко сприймається та інтерпретується фахівцями різних галузей знань. Важливим є і той факт, що РД дозволяють виявляти інформативні підсистеми ознак з їхньої вихідної сукупності, звертаючи увагу дослідника на сховані зв’язки між об’єктами.
Розв’язуючі дерева є найважливішим інструментом реалізації алгоритмічних відображень, що апроксимують початкову (прецедентну) інформацію, і засобом синтезу структурних моделей закономірностей. Починаючи від перших наукових праць Ховленда (Hoveland), Ханта (Hunt) і А.Ш. Блоха в 50-60-х роках XX століття, дослідники і розроблювачі інформаційних систем в усьому світі донині активно вивчають методи аналізу, синтезу і редукції РД і публікують результати з теорії та практичного використання розв’язуючих дерев. У зв’язку з небажаністю ускладнення РД у результаті “перенастроювання” на навчальну вибірку, особливо актуальною є проблема обґрунтування обмеження складності розв’язуючих дерев. Ця проблема з точки зору структури РД пов’язана з редукцією розв’язуючих дерев.
Однак більшість існуючих алгоритмів синтезу і редукції РД засновані на інтуїтивних міркуваннях дослідників і не мають чіткого математичного обґрунтування. У дисертації наведено теоретичне узагальнення і нове рішення наукової проблеми розробки математично обґрунтованих методів редукції РД і корекції редукованих дерев, як методів виявлення нових структурних закономірностей у даних, шляхом побудови сукупності розв’язуючих дерев досить простої структури.
Розв’язуючі дерева ефективно застосовуються на практиці, що підтверджено численними публікаціями й експериментальними даними, зокрема, для вирішення задач діагностики захворювань, геологічного прогнозування, розпізнавання письмових знаків, мови, зображень і в багатьох інших практичних застосуваннях.
Практична корисність досліджень і розробок за темою дисертації визначається істотною мірою і тим, що в останні роки інтерес до розв’язуючих дерев підвищився у зв’язку з активними розробками інтелектуалізованого програмного забезпечення, розвитком інформаційних технологій Machine Learning і Data Mining.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану науково-дослідної роботи кафедри інформатики Таврійського національного університету ім. В.І. Вернадського за держбюджетною тематикою на 2001-2004 рр. “Розробка гібридної універсальної програмної оболонки для побудови експертних систем і логічних систем підтримки прийняття рішень” № державної реєстрації роботи 0102U001575.
Мета роботи. 1. Обґрунтувати доцільність редукції бінарних розв’язуючих дерев, використовуючи методи дискретної математики і імовірнісного оцінювання. 2. Знайти й обґрунтувати методи зниження складності древоподібних класифікаторів, зберігаючи вимогу їхньої коректності на достовірній навчальній інформації. 3. Запропонувати й обґрунтувати методи прийняття рішень, засновані на корекції сукупності редукованих розв’язуючих дерев як набору евристичних (і в загальному випадку некоректних) процедур.
Для досягнення поставлених цілей у дисертаційній роботі вирішуються наступні задачі. 1. Розробити імовірнісний критерій відсікання (редукції) ребер бінарного розв’язуючого дерева, що мають число внутрішніх вершин, яке перевищує задане значення рангу . Обґрунтувати таку редукцію з точки зору невипадковості (закономірності) виявлення в емпіричній вибірці кон’юнктивної закономірності рангу . 2. На основі оцінок VCD (складності класу розв’язуючих правил за теорією Вапніка-Червоненкіса) для класів алгоритмів розпізнавання, обумовлених бінарними розв’язуючими деревами з обмеженням на число вершин, обґрунтувати доцільність ускладнення правил розпізнавання та процедур корекції рішень. 3. Розробити методи побудови коректної сукупності розв’язуючих дерев (емпіричного розв’язуючого лісу), що забезпечують можливість точного настроювання на навчальну вибірку з одночасним дотриманням обмеження на ранг ребер РД. 4. Одержати оцінку складності емпіричного розв’язуючого лісу та вивчити інші його властивості як спеціального сімейства алгоритмів розпізнавання. 5. Розробити алгоритми корекції сукупності некоректних емпіричних розв’язуючих дерев, які забезпечують підвищення точності класифікації. 6. Створити необхідне програмне забезпечення і провести експерименти на реальних даних з метою підтвердження теоретичних результатів, отриманих у дисертації.
Для вирішення поставлених задач використовуються методи дискретної математики, алгебри, теорії множин, теорії ймовірностей і математичної статистики та широкий арсенал засобів теоретичної інформатики й кібернетики, включаючи статистичну теорію навчання Вапніка-Червоненкіса й алгебраїчну теорію Ю.І. Журавльова корекції евристичних процедур прийняття рішень.
Наукова новизна отриманих результатів. У дисертаційній роботі отримані такі нові результати, що виносяться на захист.
1.
Обґрунтовано процес редукції ребер РД на основі імовірнісного підходу до оцінювання емпіричних закономірностей як невипадковостей. Отримано оцінки випадкового виявлення в стандартних навчальних таблицях кон’юнктивних закономірностей як ребер РД заданого рангу й у цілому - оцінки можливості “випадкового” виявлення РД-структури заданої складності.
2.
Запропоновано новий алгоритм синтезу сукупності розв’язуючих дерев з обмеженням на ранг ребер.
3.
Розв’язано проблему синтезу емпіричного розв’язуючого лісу, як розв’язуючого правила, у якому дотримується обмеження на ранг ребер (кон’юнкцій) РД, і зберігається можливість правильної класифікації всіх об’єктів навчальної вибірки.
4.
На основі ємнісної характеристики Вапніка-Червоненкіса досліджена складність і отримана оцінка VCD класу розв’язуючих правил, породжуваних емпіричним розв’язуючим лісом.
5.
На основі алгебраїчного підходу до розпізнавання побудована модель алгебраїчної корекції
- некоректного емпіричного лісу.
6.
Отримано експериментальне підтвердження того, що емпіричний розв’язуючий ліс у середньому на численності розв’язуваних задач забезпечує більш точне розпізнавання, ніж окремі РД.
Практичне значення отриманих результатів дисертаційної роботи полягає в можливості застосування розроблених у ній алгоритмів синтезу і прийняття рішень емпіричним розв’язуючим лісом для побудови інформаційних інтелектуалізованих систем, виявлення схованих структурних закономірностей у даних, побудови логічних описів класів об’єктів у вигляді диз’юнктивних нормальних форм. Зокрема, як результат рішення практичної задачі, у дисертації побудований емпіричний розв’язуючий ліс, що дозволяє розпізнавати типи (класи) вібріонів і вивчати особливості цих класів на основі знайдених кон’юнктивних закономірностей.
Особистий внесок здобувача. Усі представлені в дисертації результати отримані особисто автором. Науковому керівнику професору Донському В.Й., співавтору робіт [2, 3, 11] належать постановки задач і частина спільно проведених експериментів з розв’язуючими деревами на модельних експериментальних даних з використанням програмного комплексу “Дуель” [1].
Апробація результатів дисертації. Результати роботи доповідалися й обговорювалися на Міжнародній науково-практичній конференції “Знання - Діалог - Рішення” (Санкт-Петербург, червень, 2001 р.); Міжнародній конференції з індуктивного моделювання (Львів, травень, 2002 р.); IV Міжнародній науковій конференції “Інтелектуалізація обробки інформації” (Алушта, червень, 2002 р.); Міжнародній науковій конференції “On Problems of Decision Making and Control under Uncertainties” (Алушта, вересень, 2003 р.); 11-й Всеросійській конференції “Математичні методи розпізнавання образів” (Пущино, листопад, 2003 р.); на наукових конференціях професорсько-викладацького складу факультету математики та інформатики Таврійського національного університету ім. В.І. Вернадського (2002, 2003 рр.); на науковому семінарі кафедри інформатики Таврійського національного університету ім. В.І. Вернадського.
Публікації. Перелічені результати відображені в 11 публікаціях, серед яких 3 статті в наукових виданнях зі списку наукових кваліфікаційних видань України, затверджених ВАК України; 5 статей у наукових журналах і збірниках наукових праць; 3 публікації в тезах наукових конференцій.
Структура й обсяг роботи. Зміст роботи викладений у рукописі, що складається з 108 сторінок, 12 малюнків, 8 таблиць. Дисертаційна робота включає вступ, чотири розділи, висновок і список використаних джерел з 161 найменування.
ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЇ
У вступі наводиться загальна характеристика дисертаційної роботи, дається обґрунтування актуальності обраної теми, анонсуються основні отримані результати і демонструється їхнє практичне значення.
У розділі 1 дисертаційної роботи наводиться постановка задачі навчання розпізнаванню за прецедентами; звертається увага на актуальність і корисність використання розв’язуючих дерев у задачі навчання розпізнаванню за прецедентами; розглядаються основні властивості бінарних розв’язуючих дерев; наводиться огляд результатів, пов’язаних із сучасними підходами до синтезу, редукції й інших моделей корекції розв’язуючих дерев. На основі висновків по даному розділу формуються цілі та задачі дослідження, спрямовані на вирішення дилеми між точним настроюванням на початкову навчальну інформацію й обмеженням складності розв’язуючих дерева, які забезпечують можливість узагальнення властивостей навчальної інформації з гарантованою точністю.
У розділі 2 дисертаційної роботи на підставі імовірнісного підходу до оцінювання емпіричних закономірностей обґрунтований процес редукції розв’язуючих дерев. Імовірнісний підхід до оцінювання емпіричних закономірностей і розв’язуючих правил ґрунтується на поданні закономірності як невипадковості. Ключова (основна) ідея оцінювання закономірностей-гіпотез як невипадковостей, заснована на колмогоровському підході, передбачає використання моделі генеральної сукупності з рівномірним розподілом об’єктів.
Кон’юнкцію …………………….. рангу r називають кон’юнктивною закономірністю рангу r щодо таблиці , якщо вона перетворюється на одиницю на деяких об’єктах з цієї таблиці, які належать одному і тому ж зафіксованому класу, і перетворюється на нуль на всіх об’єктах таблиці, які не належать до цього зафіксованого класу.
Теорема 2.1. Нехай - булева таблиця, випадково обрана з генеральної сукупності таблиць розмірності із рівномірним розподілом на . Тоді ймовірність ………… виявлення кон’юнктивної закономірності рангу r щодо таблиці задовольняє нерівності
………………………………… (2.1)
Теорема 2.1 дає оцінку цієї ймовірності випадкового виведення рішення за допомогою емпіричної кон’юнктивної закономірності. Нерівність (2.1) була отримана А.Д. Закревським і наводиться тут через її важливість для викладу подальших результатів.
Якщо бінарне розв’язуюче дерево ………….. із листям коректно на деякій таблиці , то воно визначає набір кон’юнктивних закономірностей…………………….., що забезпечують виведення рішення. Ці кон’юнкції попарно ортогональні, оскільки відповідають різним ребрам дерева. З урахуванням теореми 2.1 одержано наступну оцінку.
Теорема 2.2. Імовірність …………….. того, що при використанні бінарного розв’язуючого дерева ………….. із листям, коректного на емпіричній таблиці , буде отриманий випадковий висновок про властивість для довільного об’єкта………………….., обраного рівномірно з багатьох булевих векторів довжини , задовольняє нерівності
………………………………………. (2.2),
де ……………….. - ранги кон’юнкцій, що відповідають ребрам бінарного розв’язуючого дерева.
Зауваження 2.1. У випадку, коли цільова перемінна (цільовий стовпець) задана окремо від емпіричної таблиці навчання , тобто не входить до числа її стовпців, нерівність аналогічна (2.2) має вигляд
………………………………………… (2.3),
де ………………. - імовірність випадкового виведення цільової властивості деревом, побудованим за стандартною початковою інформацією з булевими ознаками.
Позначимо …….. - клас усіляких розв’язуючих дерев з рівно листям які можуть бути побудовані на об’єктах стандартної таблиці навчання . Виходячи з оцінки (2.3), введемо на множині ………. функціонал якості ……………… наступного вигляду:
……………………………………………… (2.4)
Функціонал є оцінкою “гіршого” випадку при використанні для прийняття рішення “найнесприятливішого” ребра дерева - ребра дерева найбільшого рангу. Цей факт обґрунтовано лемою 2.1.
Лема 2.1. Величина …………………….. монотонно зростає з ростом рангу ребра r, при і .
Поставлено задачу мінімізації функціонала якості і доведено, що мінімум функціонала якості досягається на рівномірних деревах.
Лема 2.2. Мінімум функціонала ………….. на множині РД ……….
…………………………………………………
досягається при………., ……….. у випадку, якщо - повне дерево; а при ………. - у випадку, коли дерево має таку властивість………………., де ……………………… - ранги кон’юнкцій, що відповідають ребрам РД .
Визначення 2.2. Бінарне розв’язуюче дерево називається рівномірним, якщо ранги його ребер відрізняються не більше ніж на одиницю.
Теорема 2.3. У класі емпіричних розв’язуючих дерев …………… найменшу рівномірну оцінку (2.4) імовірності одержання випадкового висновку мають рівномірні дерева.
У підрозділах 2.3.1 і 2.3.2 отримано оцінки VCD для основних класів розв’язуючих функцій, представлених розв’язуючими деревами, на підставі яких можна стверджувати, що оптимізація за числом листя більш обґрунтована з точки зору теорії Вапніка-Червоненкіса і забезпечує істотно більш високу швидкість рівномірної збіжності при навчанні, ніж оптимізація за рангом дерев.
Відомо індуктивне визначення рангу БРД T. Якщо БРД T містить єдину вершину, то його ранг . Якщо T містить корінь, ліве піддерево рангу і праве піддерево рангу , то
……………………………………………………….
Позначимо …………….. - клас булевих функцій від n змінних, представлених у вигляді БРД рангу не більш r, і …………….. - ємність цього класу. Відомо, що…………………...
У підрозділі 2.3.1 доведено, що …………………… при будь-якій заданій константі r і .
Розглянемо кінцеву множину БРД із не більш ніж листям, позначимо його і відповідний цій множині клас булевих функцій…………...
Теорема 2.4. ………………………………….
Наслідок 2.1. При будь-якому ………….. та має місце оцінка……………………….
У розділі 3 дисертаційної роботи описана нова класифікуюча модель - емпіричний розв’язуючий ліс (підрозділ 3.1). Побудова емпіричного розв’язуючого лісу спрямована на пошук системи ребер лісу, яка правильно класифікує всі об’єкти несуперечливої навчальної вибірки на основі кон’юнктивної закономірності заданого граничного рангу.
Визначення 3.1. Областю відмови емпіричного бінарного розв’язуючого дерева називається інтервал……………., що відповідає ребру дерева з рангом……………, де - задане значення, що обмежує ранг.
Передбачається, що в область відмови емпіричного бінарного розв’язуючого дерева попадають об’єкти, які викликають зайве ускладнення структури БРД (ріст числа листків, ріст рангу окремих ребер).
Визначення 3.2. Посиланням дерева на дерево називається покажчик на кореневу вершину дерева , розміщений у кожному листку дерева , який відповідає деякій області відмови.
Визначення 3.3. Упорядкований набір емпіричних розв’язуючих дерев ……………….. з посиланнями ………………… називається емпіричним розв’язуючим лісом.
Емпіричний розв’язуючий ліс визначає розв’язуючу процедуру розпізнавання приналежності об’єктів класам.
Визначення 3.4. Емпіричний розв’язуючий ліс називається r - коректним щодо таблиці , якщо дерева……………, які входять до нього, не містять ребер рангу, що перевищує r, останнє по порядку дерево не має ребер, що відповідають областям відмови і розв’язуюче правило, що відповідає емпіричному розв’язуючому лісу, безпомилково визначає клас кожного об’єкта з таблиці……….. Якщо ж емпіричний розв’язуючий ліс помилково класифікує хоча б один об’єкт таблиці , він називається r - некоректним щодо цієї таблиці.
Позначимо ДНФ …………….., де ………. - індекс дерева………….; - кон’юнкція, що відповідає ребру дерева ; …….. - множина номерів ребер, що мають мітку в дереві .
Визначення 3.5. ДНФ ……………………… називається множинним логічним описом класу за емпіричним лісом .
Множинний логічний опис може розглядатися і як розв’язуюча функція для класу, однак вона не визначає, якою саме кон’юнкцією ДНФ приймається рішення.
Різні дерева лісу можуть бути побудовані на різних і навіть непересічних підмножинах ознак. Тому множинні логічні описи для двох різних класів можуть виявитися не ортогональними, що викличе неоднозначність рішення.
Зазначені властивості множинних логічних описів класів обґрунтовують необхідність розробки спеціальних процедур синтезу розв’язуючих правил на основі емпіричного розв’язуючого лісу, що забезпечують однозначне виведення рішень.
У підрозділі 3.2 наведений алгоритм синтезу емпіричного розв’язуючого лісу, а також різні алгоритми прийняття рішень емпіричним розв’язуючим лісом (підрозділ 3.3) - послідовний алгоритм прийняття рішень з переходами за посиланнями, алгоритм прийняття рішень на основі “найкомпетентнішого” ребра РД емпіричного розв’язуючого лісу, алгоритм прийняття рішень на основі голосування ребер РД емпіричного розв’язуючого лісу.
Етапи синтезу r - редукованого емпіричного розв’язуючого лісу.
10. Синтезується дерево одним з відомих методів розгалуження. Якщо воно коректно на і ранги його ребер не перевищують заданий ранг r, то синтез завершений, і ліс складається з одного дерева………….. Інакше - перейти на 20.
20. Позначимо через …………… - вихідна множина ознак. Нехай - множина ознак, використаних для синтезу дерева . Якщо дерево має ребро рангу, більше ніж r, то це ребро редукується з посиланням на дерево . Редукція ребра РД полягає в заміні - ої вершини термінальною вершиною спеціального виду - посиланням. Кон’юнкція, що відповідає редукованому ребру, визначає область відмови. Розв’язуюче дерево, що має посилання (непорожні області відмови), називається далі r - редукованим. Посилання на РД установлюються для всіх областей відмови РД . Потім синтезується розв’язуюче дерево , причому при добудуванні (галуженні) спочатку використовуються ознаки множини…………., якщо вона не порожня і ознак досить для синтезу дерева . Якщо…………….., то змінюється порядок вибору ознак у порівнянні з порядком, використаним при синтезі РД . Нехай - область відмови дерева . ………….. - об’єкти різних класів вибірки , що потрапили в область відмови. Дерево будується за таблицею , а тільки потім добудовується на об’єктах…………... Виходить, взагалі кажучи, r - некоректне дерево і ліс…………... Якщо виконується одна з умов зупинки синтезу, описана нижче, то синтез завершено. Інакше - синтезується дерево (повторюються основні дії кроку 20).
Критерії зупинки синтезу емпіричного розв’язуючого лісу:
1)
отримано r - коректний емпіричний розв’язуючий ліс;
2)
спроби синтезу нових дерев виконано більше заданого числа разів;
3)
перевищено припустимий обсяг пам’яті, який можуть займати розв’язуючі дерева ЕРЛ.
Наведемо критерій існування r - коректного емпіричного розв’язуючого лісу для заданої несуперечливої навчальної таблиці…..
Теорема 3.1. Для існування r - коректного емпіричного розв’язуючого лісу щодо таблиці навчання необхідно і досить, щоб для кожного об’єкта ………… існував інтервал рангу не більше, ніж r такий, що ………….. і в множині ………….. містилися об’єкти тільки одного і того ж класу.
З урахуванням структури побудованого емпіричного розв’язуючого лісу запропоновано кілька різних алгоритмів прийняття рішень r - коректним емпіричним лісом:
- Послідовний алгоритм із переходами за посиланнями реалізує умовний перехід на перше по порядку посилань дерево емпіричного лісу, яке для заданого об’єкта дозволяє прийняти рішення з припустимою оцінкою імовірності невипадковості кон’юнктивної закономірності (якщо граничний ранг r заздалегідь обраний з урахуванням такої припустимої оцінки, останнє рівнозначне “виходу” на мітку класу).
- Алгоритм прийняття рішень на основі найбільш “компетентного” ребра передбачає перегляд усіх дерев емпіричного лісу і вибір ребра з міткою класу, що відповідає інтервалу, до якого попадають об’єкти, що класифікуються, і має мінімальний ранг. Програючи у швидкості одержання рішення, цей алгоритм дозволяє вибрати ребро з найкращою статистичною оцінкою.
- Алгоритм голосування ребер використовує широко застосовуване мажоритарне правило, що є спрощеним варіантом процедури алгебраїчної корекції.
У підрозділі 3.3 побудовані несуперечливі логічні описи класів у вигляді диз’юнктивних нормальних форм по емпіричному розв’язуючому лісу. Для опису класів у вигляді ДНФ, звичних і корисних при аналізі одиничних РД, в ЕРЛ фігурує істотно складніша конструкція. Перш, ніж приступити до її побудови, зазначимо, що процес прийняття рішення і його опис істотно різні речі. Коректний ЕРЛ визначає розбивку куба на області, що відповідають класам і, відповідно, однозначні розв’язуючі правила (алгоритмічні функції класів).
Нехай ………………- алгоритмічне відображення, обумовлене i-м РД лісу……………………., де - число класів, - відмовлення від рішення,…..
Областю компетентності i-го розв’язуючого дерева будемо називати множину………………., а областю компетентності упорядкованої множини …………………… емпіричних розв’язуючих дерев - …………………., причому……………………………...
Теорема 3.2. Емпіричний розв’язуючий ліс ……………………….. коректний відносно стандартної таблиці навчання тоді і тільки тоді, коли………………………….
Кожне наступне по порядку, визначеному алгоритмом прийняття рішень, РД лісу “вичислює” відображення тільки на звуженні………………………., що може бути описано у вигляді логічної формули……………………………. Ця формула може бути представлена деякою ДНФ…………………………... Якщо в визначене розв’язуюче правило …………………для деякого класу у вигляді ДНФ, то для логічного опису цього класу слід використовувати вираження……………………….. Але, незважаючи на це, складні формули визначають не використовувані для виведення рішення кон’юнкції, а лише логічний опис рішення разом з областями компетентності.
Побудова ДНФ класу по ЕРЛ як опису рішення.
10. Узяти всі ребра першого розв’язуючого дерева лісу, позначені мітками класів, і “розписати” кон’юнкції за класами, одержуючи ДНФ…………., ………….. як опис j - го класу за першим РД. Записати ДНФ , що відповідає ребрам, позначеним міткою cut (- опис області відмови першим РД емпіричного лісу).
i0. Нехай побудовані……………….., ……….. (………..,………- опис перетинання областей відмови i-1 розв’язуючих дерев емпіричного лісу). За побудуємо опис j-го класу у вигляді рекурсивної процедури:………………………………...
Рішення обумовлене ЕРЛ відповідно до алгоритму розпізнавання з переходами за посиланнями, кожного разу приймається однією кон’юнкцією обмеженого рангу, але, можливо, в умовах відмовлення попередніх по порядку РД лісу. Важливою властивістю будь-якої такої приймаючої рішення кон’юнкції є коректність на навчальній таблиці : вона виконується тільки на об’єктах одного класу.
У підрозділі 3.4 на основі алгебраїчної підходу побудована модель корекції r - некоректного емпіричного розв’язуючого лісу. Розглянуто алгоритм, що ґрунтується на побудові лінійного замикання множини некоректних алгоритмів розпізнавання з класу РД-моделей, яке є коректним на множині задач з несуперечливою початковою інформацією і повною множиною ознакових предикатів. Цей алгоритм слід застосовувати, коли емпіричний ліс ………….. не є r-коректним.
Для кожного дерева r - некоректного емпіричного лісу кожен листок доповнюється інформацією…………, ………., ……….., де ………… - число листків дерева .
Для контрольної вибірки ………………. обчислюється матриць…………….., де…………….; - ребро дерева , що класифікує об’єкт ,………;………; - число класів. Позначимо ……………. - набір скалярів. Лінійна комбінація ……………. визначає оператор емпіричного лісу, що розпізнає.
Спочатку передбачається………,……. Нехай об’єкт контрольної вибірки належить класу . Якщо для всіх ………… виконується
…………………………. (3.1),
то оператор емпіричного лісу, що розпізнає,, забезпечує безпомилкову класифікацію всієї контрольної вибірки. Інакше умова (3.1) порушується …………….. разів. Тоді розв’язується задача мінімізації емпіричного функціоналу………..: …………… (3.2), де W - область припустимих значень скалярів. Якщо мінімум (3.2) досягається на наборі , то оператор ……………….. називається скоректованим (за контрольною вибіркою).
У підрозділі 3.5 отримана оцінка VCD r- редукованого емпіричного розв’язуючого лісу, яка дозволяє зробити висновок про те, що перехід від одиничного розв’язуючого дерева до r- редукованого емпіричного лісу не змінює порядку VCD. У той же час забезпечується корекція, яка дозволяє настроїться за навчальною вибіркою на правильну класифікацію як можна більшого числа об’єктів.
Отримано оцінку VCD кінцевого класу …………… розв’язуючих правил, утворених диз’юнктивними нормальними формами, які містять не більше кон’юнкцій рангу не більше r, що складаються з літералів n змінних.
Теорема 3.2. При ………. справедлива нерівність
………………………………………………………………….
Наслідок 3.1. ………………………. при ………… і
Наслідок 3.2. ………………………………. при …………… і
Теорема 3.3. ………………………………………………………………………..
Наслідок 3.4. ………………………………при ………….. і
Таким чином, побудований скоректований емпіричний розв’язуючий ліс не призводить до значного ускладнення породжуваного ним класу розв’язуючих правил порівняно з класом РП, породжених одним РД. Тим часом модель емпіричного розв’язуючого лісу у певному розумінні є компромісом між ускладнюючою РП перепідгонкою і погіршенням якості класифікації об’єктів навчальної вибірки, а також дозволяє виявляти нові емпіричні закономірності між ознаками.
У розділі 4 дисертаційної роботи описується програмна реалізація алгоритму синтезу емпіричного розв’язуючого лісу й алгоритму прийняття рішень емпіричним лісом з переходами за посиланнями. Ця програмна реалізація Forest Based Learning (FBL) - інформаційно-розпізнавальна система - призначена для рішення задач навчання і розпізнавання об’єктів на основі технології розв’язуючих дерев і нових підходів до оцінювання і редукції окремих класифікаторів й організації послідовних процедур побудови розв’язуючого середовища. Демонструються результати практичного застосування алгоритму синтезу емпіричного розв’язуючого лісу для класифікації бази даних патогенних вібріонів і аеромонад, що викликають шлунково-кишкові захворювання. На основі побудованого програмного комплексу методом статистичного моделювання здійснюється порівняння характеристик одного розв’язуючого дерева й емпіричного розв’язуючого лісу, причому істотним є той факт, що при синтезі емпіричного розв’язуючого лісу й окремого розв’язуючого дерева використовується той самий критерій для вибору ознакових предикатів у внутрішні вершини дерев. Проведені експерименти достовірно продемонстрували підвищення точності розпізнавання об’єктів, які раніше не брали участь у навчанні, емпіричним розв’язуючим лісом порівняно з окремим розв’язуючим деревом.
У висновку підбиваються підсумки дисертаційної роботи.
ВИСНОВКИ
Основними результатами цієї дисертації є:
1.
Розроблено імовірнісний критерій відсікання (редукції) ребер бінарного розв’язуючого дерева, що мають число внутрішніх вершин, яке перевищує задане значення рангу r. Обґрунтовано таку редукцію з точки зору невипадковості (закономірності) виявлення в емпіричній вибірці кон’юнктивної закономірності рангу r.
2.
На основі оцінок VCD (складності класу розв’язуючих правил за теорією Вапніка-Червоненкіса) для класів алгоритмів розпізнавання, обумовлених бінарними розв’язуючими деревами з обмеженням на число вершин, обґрунтовано доцільність ускладнення правил розпізнавання та процедур корекції рішень.
3.
Розроблено методи побудови коректної сукупності розв’язуючих дерев (емпіричного розв’язуючого лісу), що забезпечують можливість точного настроювання на навчальну вибірку з одночасним дотриманням обмеження на ранг ребер РД.
4.
Отримано оцінку складності емпіричного розв’язуючого лісу і вивчено інші його властивості як спеціального сімейства алгоритмів розпізнавання.
5.
Розроблено алгоритми корекції сукупності некоректних емпіричних розв’язуючих дерев, які забезпечують підвищення точності класифікації.
6.
Створено необхідне програмне забезпечення та проведено експерименти на реальних даних з метою підтвердження теоретичних результатів, отриманих у дисертації.
У підсумку можна зазначити, що розроблений у дисертації процедурний спосіб корекції редукованих БРД - емпіричний розв’язуючий ліс - дозволяє одержати більш точний алгоритм розпізнавання, ніж алгоритми, які реалізуються окремими коректними БРД. При цьому емпіричний розв’язуючий ліс зберігає можливість логічного опису об’єктів у вигляді диз’юнктивний нормальних форм, і його застосування в сучасних інтелектуалізованих інформаційних системах доцільне, що підтверджується апробованою в роботі програмною реалізацією.
СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1.
Донськой В.Й., Дюлічева Ю.Ю. Бінарні розв’язуючі дерева в задачах інтелектуального аналізу інформації // Наукові вісті Національного технічного університету України “Київський політехнічний інститут”. - 2001. - Вип.5. - С.12-18.
2.
Донской В.И., Дюличева Ю.Ю. Деревья решений с k - значными переменными // Труды Международной конференции “Знание - Диалог - Решение”. - Санкт-Петербург: Издательство “Лань”. - 2001. - Т.1. - С.201-207.
3.
Донской В.И., Дюличева Ю.Ю. Индуктивная модель r - корректного эмпирического леса // Труды Международной конференции по индуктивному моделированию: Львов. - 2002. - C.54-58.
4.
Дюличева Ю.Ю. Оценка VCD r - редуцированного эмпирического леса // Таврический вестник информатики и математики. - 2003. - №1. - С.31-42.
5.
Дюличева Ю.Ю. Принятие решений на основе индуктивной модели эмпирического леса // Искусственный интеллект. - 2002. - №2. - С.110-115.
6.
Дюличева Ю.Ю. О программной реализации и апробации алгоритма DFBSA синтеза эмпирического решающего леса // Таврический вестник информатики и математики. - 2003. - №2. - С.35-43.
7.
Дюличева Ю.Ю. Стратегии редукции решающих деревьев (обзор) // Таврический вестник информатики и математики. - 2002. - №1. - С.10-17.
8.
Дюличева Ю.Ю. О критерии существования и логическом описании r-корректного эмпирического решающего леса // Искусственный интеллект. - 2004. - №1. - С. 167-172.
9.
Дюличева Ю.Ю. Принятие решений на основе индуктивной модели эмпирического леса // Тезисы докладов Международной научной конференции “Интеллектуализация обработки информации”. - Симферополь: КНЦ НАН Украины. - 2002. - С.38-39.
10.
Дюличева Ю.Ю. DFBSA - алгоритм синтеза эмпирического леса по “ссылкам” // Тезисы докладов Международной научной конференции “On Problems of Decision Making and Control under Uncertainties”. - 2003. - C.95-97.
11.
Донской В.И., Дюличева Ю.Ю. Алгоритмы синтеза редуцированного эмпирического леса // ММРО-11: тезисы докладов. - Пущино. - 2003. - С.71-74.
АНОТАЦІЇ
Дюлічева Ю.Ю. Моделі корекції редукований бінарних розв’язуючих дерев. - Рукопис.
Дисертація на здобуття вченого ступеня кандидата фізико-математичних наук за фахом 01.05.01 - теоретичні основи інформатики та кібернетики. - Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2004.
Дисертаційна робота присвячена дослідженню й удосконаленню алгоритмів навчання і розпізнавання, заснованих на побудові бінарних розв’язуючих дерев; розробці правил редукції бінарних розв’язуючих дерев, заснованих на оцінюванні кон’юнктивних закономірностей; створенню послідовної процедури синтезу сукупності розв’язуючих дерев - алгоритму синтезу емпіричного розв’язуючого лісу - і методів корекції сукупності редукованих бінарних розв’язуючих дерев як набору евристичних процедур прийняття рішень.
Розроблено імовірнісний критерій відсікання (редукції) ребер бінарного розв’язуючого дерева, що мають число внутрішніх вершин, яке перевищує задане значення рангу r. Розроблено методи побудови коректної сукупності розв’язуючих дерев (емпіричного розв’язуючого лісу), що забезпечують можливість точного настроювання на навчальну вибірку з одночасним дотриманням обмеження на ранг ребер РД. Отримано оцінку складності (VCD) емпіричного розв’язуючого лісу. Розроблено модель алгебраїчної корекції сукупності некоректних емпіричних розв’язуючих дерев, що забезпечує підвищення точності класифікації. Створено програмне забезпечення, що реалізує розроблені алгоритми, і проведені експерименти на реальних даних.
Ключові слова: бінарне розв’язуюче дерево, кон’юнктивна закономірність, редукція, перепідгонка, емпіричний розв’язуючий ліс, VCD класу розв’язуючих правил.
Дюличева Ю.Ю. Модели коррекции редуцированных бинарных решающих деревьев. - Рукопись.
Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2004.
Диссертационная работа посвящена исследованию и усовершенствованию алгоритмов обучения и распознавания, основанных на построении бинарных решающих деревьев; разработке правил редукции бинарных решающих деревьев, основанных на оценивании конъюнктивных закономерностей; созданию последовательной процедуры синтеза совокупности решающих деревьев - алгоритма синтеза эмпирического решающего леса - и методов коррекции совокупности редуцированных бинарных решающих деревьев как набора эвристических процедур принятия решений.
Разработан вероятностный критерий отсечения (редукции) ветвей бинарного решающего дерева, имеющих число внутренних вершин, превышающее заданное значение ранга r. Разработаны методы построения корректной совокупности решающих деревьев (эмпирического решающего леса), обеспечивающие возможность точной настройки на обучающую выборку с одновременным соблюдением ограничения на ранг ветвей РД. Получена оценка сложности (VCD) эмпирического решающего леса. Разработана модель алгебраической коррекции совокупности некорректных эмпирических решающих деревьев, обеспечивающая повышение точности классификации. Создано программное обеспечение, реализующее разработанные алгоритмы, и проведены эксперименты на реальных данных.
Ключевые слова: бинарное решающее дерево, конъюнктивная закономерность, редукция, переподгонка, эмпирический решающий лес, VCD класса решающих правил.
Dyulicheva Yu.Yu., Pruned Binary Decision Tree Correction Models. - Manuscript.
The thesis for obtaining the Candidate of physical and mathematical degree on speciality 01.05.01 - Computer Science Theory and Cybernetics. - V. Glushkov Institute of Cybernetics of National Academy Of Sciences of Ukraine, Kiev, 2004.
The dissertation is dedicated to research and improvement of learning and recognition algorithms based on building up binary decision trees; to working out the rules for binary decision trees pruning on the basis of conjunctive regularity evaluation; to creating consistent procedure of decision tree family synthesis (i.e. the em-pirical decision forest synthesis algorithm) and pruned decision trees family correction methods as a set of heu- ristic procedures for decision making.
Since it is undesirable to complicate the DT (Decision Tree) in connection with their overfitting on training samples, the decision tree complexity ground problem is becoming especially important.
For DT structure this problem is connected with decision tree pruning.
Based on Kolmogorov’ approach, which considers regularity as non-randomness, the evaluation of randomness of a correct binary decision tree was obtained. If the decision tree being built according to the standard initial information with Boolean attributes, then the probability of the random finding of this tree is evaluated by the following inequality:
…………………………………………..
where ……... being the ranks of conjunctions that correspond to BDT branches; and being the number of leaves. Value ………….. is growing monotonously along with the growth of BDT branches’ rank r. This allows using the DT branch pruning criterion as an inequality ………….. for the given value .
The empirical decision forest (EDF) synthesis procedure suggested in dissertation is aimed at searching for such forest branch system that would give a correct classification for all objects of the noncontradictory training sample based on conjunctive regularity of the predetermined (admissible) rank. The EDF with such branch system is named - correct. The main idea of the decision rules synthesis based on empirical decision forest that is made up by the decision tree family …………. is as follows. In case there is no conjunctive regularity in tree with the rank admissible for the classification of the object that is not part of learning, its classification is to be performed by another tree . If there is no conjunctive regularity in tree with admissible rank, the object is to be “transferred” to the next tree that is defined by the order of the forest tree synthesis. The EDF correctness condition will be met if some conjunctive regularity of admissible rank is found for each object of the non-contradictory training table. The criterion for r - correct empirical decision forest was proved. If r - correct EDF can not be built, the algebraic correction model is suggested.
The evaluations of VCD of decision rules class generating from the empirical decision forest were derived:
………………………………………………………………….
……………………………, where ,
The evaluations show that the recognition algorithms class based on empirical decision forest synthesis has the same degree of complexity as the class of algorithms that are based on single decision tree use.
The major results of the work done are as follows. The probabilistic decision tree pruning criterion was worked out which applies to the branches with the number of internal nodes exceeding the predetermined value of r rank. The grounding for the pruning as viewed as non-randomness of detecting r rank conjunctive regularity in the empirical sample is suggested in the work. The methods for building up a correct decision tree family so called empirical decision forest were worked out which offers a possibility for accurate fitting for a training sample, with the restriction applying to DT rank branches being observed. The appropriateness of further complication of recognition rules for building up decision making correction procedures is grounded on the basis of VCD (with the decision rules complexity according to Vapnik-Chervonenkis theory) evaluation for recognition class algorithms that are defined by the binary decision tree with the pruning applying to the number of nodes. The algebraic correction model of the incorrect empirical decision trees family was worked out which gives way to more accurate classification. The software was created to implement the algorithms introduced in the dissertation, and experiments had been carried out with real data involved that justified the theoretical results reached.
The procedural technique of pruned BDT correction so called empirical decision forest that is introduced in the dissertation enables one to achieve a much more recognition algorithm compared to the algorithms that are realized by the single correct BDTs. Along with that the EDF is still available for logical description of objects as disjunctive normal forms. The appropriateness of applying the empirical decision forest in modern intellectualized informational systems is justified by Forest Based Learning - program realization that was tested and approved in the work.
Key words: binary decision tree, conjunctive regularity, pruning, overfitting, empirical decision forest, VCD of the decision rules class.
