Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
21
НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ
ІНСТИТУТ КІБЕРНЕТИКИ ім. В.М. Глушкова
ДЮЛІЧЕВА Юлія Юріївна
УДК 519.68
МОДЕЛІ КОРЕКЦІЇ
РЕДУКОВАНИХ БІНАРНИХ РОЗВЯЗУЮЧИХ ДЕРЕВ
01.05.01 - Теоретичні основи інформатики та кібернетики
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ - 2004 р.
Дисертацією є рукопис.
Робота виконана в Таврійському національному університеті
ім. В.І. Вернадського, м. Сімферополь.
Науковий керівник доктор фізико-математичних наук, професор
Донськой Володимир Йосипович, завідувач
кафедри інформатики, декан факультету
математики та інформатики Таврійського
національного університету ім. В.І. Вернадського
Офіційні опоненти: доктор фізико-математичних наук, професор
Кнопов Павло Соломонович, завідувач
відділом математичних методів
дослідження операцій, Інститут кібернетики
ім. В.М. Глушкова НАН України
доктор технічних наук, професор
кафедри математичних методів системного
аналізу Бідюк Петро Іванович, Інститут
прикладного системного аналізу НАН України
та Міністерства освіти і науки України
Провідна установа Київський національний університет ім. Тараса
Шевченка, кафедра системного аналізу
та теорії прийняття рішень, м. Київ
Захист відбудеться “24” вересня 2004 р. о 11 годині
на засіданні спеціалізованої вченої ради Д 26.194.02 в Інституті
кібернетики ім. В.М. Глушкова НАН України, 03022, м. Київ,
просп. Глушкова, 40.
З дисертацією можна ознайомитись в науково-технічному
архіві Інституту кібернетики ім. В.М. Глушкова НАН України,
, м. Київ, просп. Глушкова, 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. Створити необхідне програмне забезпечення і провести експерименти на реальних даних з метою підтвердження теоретичних результатів, отриманих у дисертації.
Для вирішення поставлених задач використовуються методи дискретної математики, алгебри, теорії множин, теорії ймовірностей і математичної статистики та широкий арсенал засобів теоретичної інформатики й кібернетики, включаючи статистичну теорію навчання Вапніка-Червоненкіса й алгебраїчну теорію Ю.І. Журавльова корекції евристичних процедур прийняття рішень.
Наукова новизна отриманих результатів. У дисертаційній роботі отримані такі нові результати, що виносяться на захист.
Практичне значення отриманих результатів дисертаційної роботи полягає в можливості застосування розроблених у ній алгоритмів синтезу і прийняття рішень емпіричним розвязуючим лісом для побудови інформаційних інтелектуалізованих систем, виявлення схованих структурних закономірностей у даних, побудови логічних описів класів обєктів у вигляді дизюнктивних нормальних форм. Зокрема, як результат рішення практичної задачі, у дисертації побудований емпіричний розвязуючий ліс, що дозволяє розпізнавати типи (класи) вібріонів і вивчати особливості цих класів на основі знайдених конюнктивних закономірностей.
Особистий внесок здобувача. Усі представлені в дисертації результати отримані особисто автором. Науковому керівнику професору Донському В.Й., співавтору робіт [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 - редукованого емпіричного розвязуючого лісу.
1. Синтезується дерево одним з відомих методів розгалуження. Якщо воно коректно на і ранги його ребер не перевищують заданий ранг r, то синтез завершений, і ліс складається з одного дерева………….. Інакше - перейти на 2.
2. Позначимо через …………… - вихідна множина ознак. Нехай - множина ознак, використаних для синтезу дерева . Якщо дерево має ребро рангу, більше ніж r, то це ребро редукується з посиланням на дерево . Редукція ребра РД полягає в заміні - ої вершини термінальною вершиною спеціального виду - посиланням. Конюнкція, що відповідає редукованому ребру, визначає область відмови. Розвязуюче дерево, що має посилання (непорожні області відмови), називається далі r - редукованим. Посилання на РД установлюються для всіх областей відмови РД . Потім синтезується розвязуюче дерево , причому при добудуванні (галуженні) спочатку використовуються ознаки множини…………., якщо вона не порожня і ознак досить для синтезу дерева . Якщо…………….., то змінюється порядок вибору ознак у порівнянні з порядком, використаним при синтезі РД . Нехай - область відмови дерева . ………….. - обєкти різних класів вибірки , що потрапили в область відмови. Дерево будується за таблицею , а тільки потім добудовується на обєктах…………... Виходить, взагалі кажучи, r - некоректне дерево і ліс…………... Якщо виконується одна з умов зупинки синтезу, описана нижче, то синтез завершено. Інакше - синтезується дерево (повторюються основні дії кроку 2).
Критерії зупинки синтезу емпіричного розвязуючого лісу:
Наведемо критерій існування r - коректного емпіричного розвязуючого лісу для заданої несуперечливої навчальної таблиці…..
Теорема 3.1. Для існування r - коректного емпіричного розвязуючого лісу щодо таблиці навчання необхідно і досить, щоб для кожного обєкта ………… існував інтервал рангу не більше, ніж r такий, що ………….. і в множині ………….. містилися обєкти тільки одного і того ж класу.
З урахуванням структури побудованого емпіричного розвязуючого лісу запропоновано кілька різних алгоритмів прийняття рішень r - коректним емпіричним лісом:
- Послідовний алгоритм із переходами за посиланнями реалізує умовний перехід на перше по порядку посилань дерево емпіричного лісу, яке для заданого обєкта дозволяє прийняти рішення з припустимою оцінкою імовірності невипадковості конюнктивної закономірності (якщо граничний ранг r заздалегідь обраний з урахуванням такої припустимої оцінки, останнє рівнозначне “виходу” на мітку класу).
- Алгоритм прийняття рішень на основі найбільш “компетентного” ребра передбачає перегляд усіх дерев емпіричного лісу і вибір ребра з міткою класу, що відповідає інтервалу, до якого попадають обєкти, що класифікуються, і має мінімальний ранг. Програючи у швидкості одержання рішення, цей алгоритм дозволяє вибрати ребро з найкращою статистичною оцінкою.
- Алгоритм голосування ребер використовує широко застосовуване мажоритарне правило, що є спрощеним варіантом процедури алгебраїчної корекції.
У підрозділі 3.3 побудовані несуперечливі логічні описи класів у вигляді дизюнктивних нормальних форм по емпіричному розвязуючому лісу. Для опису класів у вигляді ДНФ, звичних і корисних при аналізі одиничних РД, в ЕРЛ фігурує істотно складніша конструкція. Перш, ніж приступити до її побудови, зазначимо, що процес прийняття рішення і його опис істотно різні речі. Коректний ЕРЛ визначає розбивку куба на області, що відповідають класам і, відповідно, однозначні розвязуючі правила (алгоритмічні функції класів).
Нехай ………………- алгоритмічне відображення, обумовлене i-м РД лісу……………………., де - число класів, - відмовлення від рішення,…..
Областю компетентності i-го розвязуючого дерева будемо називати множину………………., а областю компетентності упорядкованої множини …………………… емпіричних розвязуючих дерев - …………………., причому……………………………...
Теорема 3.2. Емпіричний розвязуючий ліс ……………………….. коректний відносно стандартної таблиці навчання тоді і тільки тоді, коли………………………….
Кожне наступне по порядку, визначеному алгоритмом прийняття рішень, РД лісу “вичислює” відображення тільки на звуженні………………………., що може бути описано у вигляді логічної формули……………………………. Ця формула може бути представлена деякою ДНФ…………………………... Якщо в визначене розвязуюче правило ……………………для деякого класу у вигляді ДНФ, то для логічного опису цього класу слід використовувати вираження……………………….. Але, незважаючи на це, складні формули визначають не використовувані для виведення рішення конюнкції, а лише логічний опис рішення разом з областями компетентності.
Побудова ДНФ класу по ЕРЛ як опису рішення.
1. Узяти всі ребра першого розвязуючого дерева лісу, позначені мітками класів, і “розписати” конюнкції за класами, одержуючи ДНФ…………., ………….. як опис j - го класу за першим РД. Записати ДНФ , що відповідає ребрам, позначеним міткою cut (- опис області відмови першим РД емпіричного лісу).
i. Нехай побудовані……………….., ……….. (………..,………- опис перетинання областей відмови 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) - інформаційно-розпізнавальна система - призначена для рішення задач навчання і розпізнавання обєктів на основі технології розвязуючих дерев і нових підходів до оцінювання і редукції окремих класифікаторів й організації послідовних процедур побудови розвязуючого середовища. Демонструються результати практичного застосування алгоритму синтезу емпіричного розвязуючого лісу для класифікації бази даних патогенних вібріонів і аеромонад, що викликають шлунково-кишкові захворювання. На основі побудованого програмного комплексу методом статистичного моделювання здійснюється порівняння характеристик одного розвязуючого дерева й емпіричного розвязуючого лісу, причому істотним є той факт, що при синтезі емпіричного розвязуючого лісу й окремого розвязуючого дерева використовується той самий критерій для вибору ознакових предикатів у внутрішні вершини дерев. Проведені експерименти достовірно продемонстрували підвищення точності розпізнавання обєктів, які раніше не брали участь у навчанні, емпіричним розвязуючим лісом порівняно з окремим розвязуючим деревом.
У висновку підбиваються підсумки дисертаційної роботи.
ВИСНОВКИ
Основними результатами цієї дисертації є:
У підсумку можна зазначити, що розроблений у дисертації процедурний спосіб корекції редукованих БРД - емпіричний розвязуючий ліс - дозволяє одержати більш точний алгоритм розпізнавання, ніж алгоритми, які реалізуються окремими коректними БРД. При цьому емпіричний розвязуючий ліс зберігає можливість логічного опису обєктів у вигляді дизюнктивний нормальних форм, і його застосування в сучасних інтелектуалізованих інформаційних системах доцільне, що підтверджується апробованою в роботі програмною реалізацією.
СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
АНОТАЦІЇ
Дюлічева Ю.Ю. Моделі корекції редукований бінарних розвязуючих дерев. - Рукопис.
Дисертація на здобуття вченого ступеня кандидата фізико-математичних наук за фахом 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 Kolmogorovapproach, 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 branchesrank 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.