Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Класифікація та регресія. Методи та алгоритми побудови дерев рішень
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Інтелектуальний аналіз даних
Частина тексту файла (без зображень, графіків і формул):
Методичні вказівки
до лабораторної роботи №5
“Класифікація та регресія. Методи та алгоритми побудови дерев рішень”
з дисципліни
“Інтелектуальний аналіз даних”
для студентів базового напрямку підготовки по спеціальності
“ Комп’ютерні науки ” (шифр 0804)
Львів-2012
Методичні вказівки до лабораторної роботи №5 “Класифікація та регресія. Методи та алгоритми побудови дерев рішень” з дисципліни “Інтелектуальний аналіз даних” для студентів спеціальності - шифр 0804 “Комп’ютерні науки”/ Укл. доц. Ковівчак Я.В., Львів: Національний університет “Львівська політехніка”, 2012.
Методичні вказівки обговорено та схвалено на засіданні кафедри АСУ Протокол № ___________ від «___»___________2012 р.
Завідувач кафедрою АСУ ______________ Медиковський М. О.
Методичні вказівки обговорено та схвалено на засіданні методичної комісії базового напрямку підготовки
Протокол № ___________ від «___»___________2012 р. Лабораторна робота №5
Мета: Оволодіти методами та алгоритмами побудови дерев рішень.
Теоретична частина:
Класифікація і регресія
В задачі класифікації і регресії потрібно виділити значення залежної змінної об’єкту на основі значень інших змінних, які характеризують даний об’єкт. Формально задачу класифікації і регресії можна описати наступним чином. Нехай ми маємо множину об’єктів:
I = {i1,i2…,ij,…,in}
де іj – досліджуваний об’єкт. Прикладом таких об’єктів може бути інформація про проведення ігор при різних погодних умовах (табл. 5.1).
Спостереження
Температура
Вологість
Вітер
Гра
Сонце
Жарко
Висока
Ні
Ні
Сонце
Жарко
Висока
Так
Ні
Хмарно
Жарко
Висока
Ні
Так
Дощ
Норма
Висока
Ні
Так
Дощ
Холодно
Норма
Ні
Так
Дощ
Холодно
Норма
Так
Ні
Хмарно
Холодно
Норма
Так
Так
Сонце
Норма
Висока
Ні
Ні
Сонце
Холодно
Норма
Ні
Так
Дощ
Норма
Норма
Ні
Так
Сонце
Норма
Норма
Так
Так
Хмарно
Норма
Висока
Так
Так
Хмарно
Жарко
Норма
Ні
Так
Дощ
Норма
Висока
Так
Ні
Табл. 5.1. Інформація про проведення ігор при різних погодних умовах
Кожен об’єкт характеризується набором змінних: Іj = {x1,x2,…,xh,…,xm,y},
де xh – незалежні змінні, значення яких відомі і на основі них знаходиться значення залежної змінної y. В даному прикладі незалежні змінні являються: спостереження, температура, вологість і вітер. Залежною змінною являється гра.
В Data Mining часто набір незалежних змінних позначають у вигляді вектора:
X = {x1, x2, …, xh, …, xm}, (1)
Кожна змінна xh може приймати значення із деякого проміжку:
Ch = {ch1, ch2, …}, (2)
Якщо значеннями змінної являються елементи скінченної множини, то говорять, що вона має категоріальний тип. Наприклад, змінна спостереження приймає значення на множині значень (сонце, хмарно, дощ).
Якщо множина значень С = {c1,c2,…,ci,…,ck} змінної y скінченне, то задача називається задачею класифікації. Якщо змінна y приймає значення на множині дійсних чисел R, то задача називається задачею регресії.
В задачах класифікації і регресії виявлена функціональна залежність між змінними може бути представлена одним із наступних способів:
Класифікаційні правила;
Дерева рішень;
Математичні функції;
В даній лабораторній роботі ми розглядатимемо методи та алгоритми побудови дерев рішень.
Дерева рішень
Метод дерева рішень – це один з методів автоматичного аналізу величезних масивів даних. Перші ідеї створення "дерев рішень" починаються з робіт П.Ховленда і Е.Ханта кінця 50-х років XX століття.
Область використання методу "дерева рішень" можна об'єднати в три класи:
Опис даних: застосування "дерева рішень" дозволяє зберігати інформацію про вибірку даних в компактній і зручній для обробки формі, що містить в собі точні описи об'єктів;
Класифікація: застосування "дерева рішень" дозволяє справитися із завданнями класифікації, тобто відношення об'єктів до одного з описаних класів;
Регресія: якщо змінна має недостовірні значення, то застосування "дерева рішень" дозволяє визначити залежність цієї цільової змінної від незалежних (вхідних) змінних;
Головна перевага "дерева рішень" перед іншими методами - можливість пов'язати ставлення цілі з діями, що підлягають реалізації в сьогоденні. При побудові багаторівневого "дерева рішень" досягнення мети кожного з рівнів моделі забезпечується комплексом заходів попереднього рівня. Кожен рівень "дерева рішень" повинен займати певне місце в ієрархічній послідовності, складеної на основі дотримання причинно-наслідкових зв'язків.
Застосування методу "дерева рішень" дозволяє:
Визначати шляхи досягнення мети з виконанням кількісної оцінки складності виникають завдань та оцінкою труднощі здійснення того чи іншого варіанту;
поліпшувати якість рішень в умовах невизначеності;
Етапи побудови дерева рішень
Етап 1. Формулювання завдання.
Насамперед необхідно відкинути всі фактори, що не стосуються проблеми, а серед безлічі тих, що залишилися, виділити суттєві і несуттєві. Це дозволить привести опис завдання щодо прийняття управлінського рішення у форму, що піддається аналізу. Повинні бути виконані такі основні процедури:
визначення можливостей збору інформації для експериментування і реальних дій;
складання переліку подій, що з певною імовірністю можуть відбутися;
установлення часового порядку розміщення подій, у наслідках яких міститься корисна і доступна інформація, і тих послідовних дій, які можна розпочати.
Етап 2. Побудова "дерева рішень".
Етап 3. Оцінка ймовірностей станів середовища, тобто зіставлення шансів виникнення кожної конкретної події. Слід зазначити, що вказані ймовірності визначаються або на підставі наявної статистики, або експертним шляхом.
Етап 4. Установлення виграшів (чи програшів, як виграшів зі знаком мінус) для кожної можливої комбінації альтернатив (дій) і станів середовища.
Етап 5. Вирішення завдання.
Методика «розділяй і владарюй»
Методика ґрунтується на рекурсивному розбитті множини об’єктів із навчаючої вибірки на підмножини, які містять об’єкти, що відносяться до однакових класів.
Спершу вибирається незалежна змінна, яку поміщують в корінь дерева.
Із вершини будуються вітки, що відповідають всім можливим значенням вибраної незалежної змінної.
Множина об’єктів із навчальної вибірки розбивається на декілька підмножин у відповідність до значення вибраної незалежної змінної.
Таким чином, в кожній підмножині будуть знаходитись об’єкти. У яких значення вибраної незалежної змінної будуть однакові.
Відносно навчальної вибірки Т і множини класів С можливі три ситуації:
множина Т містить один або декілька об’єктів, що відносяться до одного класу Сr. Тоді дерево рішень для Т – це лист, який визначає (оприділяє) клас Сr;
множина Т не містить ні одного об’єкта (порожня множина). Тоді це знову ж таки – лист, і клас, який асоціюють з листом, вибирається із іншої множини, відмінної від Т, наприклад із множини, асоційованої з предком;
множина Т містить об’єкти, які відносяться до різних класів. В такому випадку потрібно розбити множину Т на деякі підмножини. Для цього вибирається одна із незалежних змінних хh, яка має два і більше відмінних одне від одного значень сh2, ch2, …, chn. Множина Т розбивається на підмножини Т1, Т2, …, Тn, де кожна підмножина Ті містить всі об’єкти, у яких значення вибраної залежної змінної дорівнює сhі. Далі процес продовжується рекурсивно для кожної підмножини до тих пір, поки значення залежної змінної у новоствореній підмножині не буде однаковим (коли об’єкти належать одному класу). В цьому випадку процес даної вітки дерева зупиняється.
При використанні даної методики побудова дерева рішень буде відбуватись зверху вниз. Більшість алгоритмів, які її використовують є «жадібними алгоритмами». Це означає, що якщо один раз змінна була вибрана і по ній відбулось розбиття, то алгоритм не може повернутись назад і вибрати іншу змінну, яка дала би краще розбиття.
Питання полягає в тому, що невідомо яку змінну треба вибрати для початкового розбиття. Від цього повністю залежить якість отриманого в майбутньому дерева.
Загальне правило для вибору змінної для розбиття: вибрана змінна повинна розбити множину так, щоб отримати в результаті підмножину, яка складатиметься з об’єктів, які належатимуть одному класу і будуть максимально приближені до цього, тобто щоб кількість об’єктів із інших класів ("домішок") в кожному з цих множин було мінімальним. Іншою проблемою при побудові дерева є проблема зупинки його розбиття. Методи її вирішення:
1. Рання зупинка. Використання статистичних методів для оцінки доцільності подальшого розбиття. Заощаджує час побудови моделі, але будує менш точні моделі.
2. Обмеження глибини дерева. Потрібно зупинити подальшу побудову, якщо розбиття перевищує задане значення глибини дерева.
3. Розбиття не повинно бути тривіальним, тобто отримані в результаті розбиття вузли повинні містити не менше заданої кількості об'єктів.
4. Відсікання гілок (знизу вгору). Побудувати дерево, відсікти або замінити піддеревом ті гілки, які призведуть до зростання кількості неправильно класифікованих об'єктів.
Побудувати всі можливі варіанти розбиття і вибрати найкращий є проблематично, якщо є багато незалежних змінних чи можливих класів.
Алгоритм CART
Алгоритм CART (Classification and Regression Tree), як видно з назви, призначений для вирішення завданнь класифікації об’єктів і побудови регресійної моделі. Він розроблений в 1974-1984 роках чотирма професорами статистики - Leo Breiman (Berkeley), Jerry Friedman (Stanford), Charles Stone (Berkeley) і Richard Olshen (Stanford).
Атрибути набору даних можуть мати як дискретне, так і числове значення. Алгоритм CART призначений для побудови бінарного дерева рішень. Бінарні дерева також називають двійковими.
Інші особливості алгоритму CART:
• функція оцінки якості розбиття;
• механізм відсікання дерева;
• алгоритм обробки пропущених значень;
• побудова дерев регресії.
Кожен вузол бінарного дерева при розбитті має тільки двох нащадків, званих дочірніми гілками. Подальший поділ гілки залежить від того, чи багато вихідних даних описує дана гілка. На кожному кроці побудови дерева правило, сформоване у вузлі, ділить заданий безліч прикладів на дві частини. Права його частина (гілка right) - це та частина множини, в якій зазвичай виконується; ліва (гілка left)-та, для якої правило не виконується.
Функція оцінки якості розбиття, яка використовується для вибору оптимального правила, - індекс Gini. Відзначимо, що дана оцінна функція заснована на ідеї зменшення невизначеності в вузлі. Припустимо, є вузол, і він розбитий на два класи. Максимальна невизначеність у вузлі буде досягнута при розбитті його на дві підмножини по 50 прикладів, а максимальна визначеність - при розбитті на 100 і 0 прикладів.
Нагадаємо, що алгоритм CART працює з числовими і категоріальними атрибутами. У кожному вузлі розбиття може йти тільки по одному атрибуту. Якщо атрибут є числовим, то у внутрішньому вузлі формується правило виду xi <= c, Значення c в більшості випадків вибирається як середнє арифметичне двох сусідніх впорядкованих значень змінної xi навчального набору даних. Якщо ж атрибут відноситься до категоріального типу, то у внутрішньому вузлі формується правило xi V(xi), де V(xi) - деякий непорожня підмножина множини значень змінної xi в навчальному наборі даних.
Механізм відсікання. Цим механізмом, що має назву minimal cost-complexity tree pruning, алгоритм CART принципово відрізняється від інших алгоритмів конструювання дерев рішень. У розглянутому алгоритмі відсікання - це певний компроміс між отриманням дерева "підходящого розміру" і отриманням найбільш точної оцінки класифікації. Метод полягає в отриманні послідовності зменшуваних дерев, але дерева розглядаються не всі, а тільки "кращі представники".
Перехресна перевірка (V-fold cross-validation) є найбільш складною і одночасно оригінальною частиною алгоритму CART. Вона являє собою шлях вибору остаточного дерева, за умови, що набір даних має невеликий об'єм або ж запису набору даних настільки специфічні, що розділити набір на навчальну та тестову вибірку не представляється можливим.
Отже, основні характеристики алгоритму CART: бінарне розщеплення, критерій розщеплення - індекс Gini, алгоритми minimal cost-complexity tree pruning і V-fold cross-validation, принцип "виростити дерево, а потім скоротити", висока швидкість побудови, обробки пропущених значень
Розглянемо задачу з двома класами і вузлом, який містить 50 прикладів одного класа. Нехай вузол має максимульну «забрудненість». Якщо буде знайдено розбиття, яке розбиває дані. Наприклад на дві підгрупи (40:5 прикладів в одній і 10:45 в іншій), то інтуїтивно «забрудненість» буде зменшено. Вона повністю зникне, коли буде знайдено розбиття, яке створить підгрупи 50:0 та 0:50. В даному алгоритмі ідея «забрудненості» формалізована в індекcі Gini. Якщо набір даних Т містить дані n класів, тоді даний індекс обраховується, як
Gini(T) = 1 - (3)
де параметр рі – ймовірність класа і в Т.
Якщо набір Т розбивається на дві частини Т1 і Т2 з числом прикладів в кожному N1 і N2 відповідно, то показник якості розбиття буде
(4)
Найкращим вважається те розбиття, для якого найменше.
Алгоритм ID3
Розглянемо критерій вибору незалежної змінної, від якої буде будуватися дерево. Повний набір варіантів розбиття | X | це кількість незалежних змінних. Розглянемо перевірку змінної Xn, яка приймає m значень – Cn1, Cn2,…, Cnm. Тоді розбиття множини об'єктів вибірки N для перевірки змінної Xn дасть підмножини T1, T2, …, Tm.
Ми очікуємо, що при розбитті множини, будемо отримувати підмножини з меншим числом об'єктів, зате більш впорядковані. Так, щоб у кожному з них були по-можливості об'єкти одного класу. Ця міра впорядкованості (невизначеності) характеризується інформацією. У контексті розглянутої задачі це кількість інформації, необхідна для того, щоб віднести об'єкт до того чи іншого класу. При поділі множини на підмножини, невизначеність належності об'єктів до конкретних класів буде зменшуватися.
Завдання полягає в виборі таких незалежних змінних, щоб максимально зменшити цю невизначеність і в кінцевому підсумку отримати підмножини з об'єктами тільки одного класу. В останньому випадку невизначеність дорівнює нулю.
Єдина доступна інформація - яким чином класи розподілені в множині T і її підмножинах, одержуваних при розбитті. Саме вона і використовується при виборі змінної. Розглянемо приклад, в якому потрібно побудувати дерево рішень щодо того, чи відбудеться гра при заданих погодних умовах. Виходячи з минулих спостережень (накопичення історичних даних), можливо чотири варіанти розбиття дерева (мал. 5.2).
Мал. 5.2. Чотири варіанти розбиття дерева.
Нехай – число об’єктів із навчальної вибірки, які відносяться до класу сr. Тоді ймовірність того, що випадково вибраний об’єкт із навчальної вибірки множини буде належати класу сr рівна:
(5)
Підрахуємо кількість інформації, ґрунтуючись на числі об’єктів того чи іншого класу, які будуть знаходитись у вузлі дерева після розбиття вхідної множини.
Згідно теорії інформації оцінку середньої кількості інформації, необхідної для визначення класа об’єкта із множини Т, дозволяє обчислити вираз:
, (6)
Підставивши у дану формулу отримане значення для Р, отримаємо:
, (7)
Оскільки використовується логарифм з двійковою основою, то цей вираз дає кількісну оцінку в бітах.
Для оцінки кількості інформації справедливі наступні твердження:
Якщо кількість об’єктів того або іншого класа в отриманій підмножині рівна 0, то кількість інформації також – 0.
Якщо кількість об’єктів одного класу дорівнює кількості об’єктів іншого класу, то кількість інформації максимальна.
Обчислимо значення інформаційної ентропії для даної множини до розбиття.
Таку ж оцінку, але вже після розбиття множини Т по хh обчислює наступний вираз:
, (8)
Наприклад, для змінної "Спостереження":
Критерієм для вибору атрибута (залежної змінної) буде наступна формула:
, (9)
Для всіх незалежних змінних розраховується критерій Gain, а потім вибирається змінна з максимальним значенням Gain. Необхідно вибрати таку змінну, щоб при розбитті нею, один з класів мав найбільшу ймовірність появи. Це можливо тоді, коли ентропія infox має мінімальне значення і, відповідно, критерій Gain (X) досягає максимуму. У нашому прикладі значення Gain для незалежної змінної "Спостереження" (перспектива) дорівнюватиме:
Gain (перспектива) = Info (I) - Info (перспектива) = 0.94 - 0.693 = 0.247 біт.
Аналогічні розрахунки можна провести для інших незалежних змінних. В результаті отримуємо:
Gain (спостереження) = 0.247 біт.
Gain (температура) = 0.029 біт.
Gain (вологість) = 0.152 біт.
Gain (вітер) = 0.048 біт.
Таким чином, для початкового розбиття краще всього вибрати незалежну змінну "Спостереження". Далі потрібно вибрати наступну змінну для розбиття. Варіанти розбиття представлені на малюнку 5.3.
Мал. 5.3. Варіанти розбиття.
Аналогічно можна обчислити значення Gain для кожного розбиття:
Gain (температура) = 0.571 біт.
Gain (вологість) = 0.971 біт.
Gain (вітер) = 0.002 біт.
Отже, що наступною змінною, по якій розбиватимуть підмножину Т (сонячно) буде «Волога».
Подальші розбиття в цій вітці уже не потребуються, оскільки в отриманих підмножинах всі об’єкти відносяться тільки до одного класу.
Якщо в процесі роботи алгоритму отриманий вузол, асоційований з порожньою множиною, то він відмічається як лист, і в якості розв’язку листа вибирається найбільш частий клас у безпосереднього предка даного листа.
Алгоритм С4.5
Представляє собою покращений варіант алгоритму ID3. Серед покращень потрібно відмітити наступні:
можливість працювати не тільки з категоріальними атрибутами, але й з числовими. Для цього алгоритм розбиває область значень незалежної змінної на декілька інтервалів і ділить початкову множину на підмножини відповідно з тим інтервалом, в який попадає значення залежної змінної;
після побудови дерева відбувається обрізання його віток. Якщо отримане дерево занадто велике, то виконується або групування декількох вузлів в один лист, або заміщення вузла дерева нижче розміщеним піддеревом. Перед операцією над деревом обчислюється помилка правила класифікації, який міститься в поточному вузлі. Якщо після заміщення (або групування) помилка не збільшиться (і не сильно збільшиться ентропія), це означає, що заміну можна виконати без втрат для побудованої моделі.
Один з недоліків алгоритму ID3 є те, що він некоректно працює з атрибутами, які мають унікальні значення для всіх об'єктів з вибірки. Для таких об'єктів інформаційна ентропія дорівнює нулю і ніяких нових даних від залежної змінної отримати не вдасться. Оскільки після розбиття отримувані підмножини будуть містити по одному об'єкту.
Алгоритм C4.5 вирішує цю проблему шляхом введення нормалізації. Оцінюється не кількість об'єктів того чи іншого класу після розбиття, а число підмножин і їх потужність (число елементів).
Вираз
(10)
оцінює потенційну інформацію, що отримується при розбитті множини Т на m підмножин.
Критерієм вибору змінної для розбиття буде вираз:
(11)
або
(12)
За умови, що є k класів і n (число об'єктів в навчальній вибірці і кількість значень змінних), тоді чисельник максимально буде рівний, а знаменник максимально рівний . Якщо припустити, що кількість об'єктів значно більше кількості класів, то знаменник зростає швидше, ніж чисельник і, відповідно, значення виразу буде невеликим.
У вибірці можуть бути об'єкти з пропущеними значеннями атрибутів. У цьому випадку їх або відкидають (що дає ризик втратити частину даних), або застосувати підхід, який припускає, що пропущені значення розподілені пропорційно частоті появи існуючих значень.
Ідею алгоритму можна представити у графічному вигляді (рис 5.4). При наявності в об’єктів тільки двох змінних, то їх можна представити у вигляді точок двовимірного простору. Об’єкти різних класів відмічені знаками «+»і«-». З рисунку видно, що при розбитті множини на підмножини будується дерево, що покриває тільки об’єкти вибраного класу (мал. 5.4).
Мал. 5.4. Ідея алгоритму С 4.5
Для постановки правил з використанням даного алгоритму необхідно щоб у навчальній вибірці були присутні все можливі комбінації значень незалежних змінних. Наприклад, дані, що дозволяють порекомендувати тип контактних лінз, представлені у табл. 5.5
Табл. 5.5. Дані, що дозволяють порекомендувати тип контактних лінз.
Вік
Приписання
Астигматизм
Ступінь зносу
Рекомендації
Юний
Короткозорість
Ні
Понижений
Ні
Юний
Короткозорість
Ні
Нормальний
М’які
Юний
Короткозорість
Так
Понижений
Ні
Юний
Короткозорість
Так
Нормальний
Жорсткі
Юний
Далекозорість
Ні
Понижений
Ні
Юний
Далекозорість
Ні
Нормальний
М’які
Юний
Далекозорість
Так
Понижений
Ні
Юний
Далекозорість
Так
Нормальний
Жорсткі
Літній
Короткозорість
Ні
Понижений
Ні
Літній
Короткозорість
Ні
Нормальний
М’які
Літній
Короткозорість
Так
Понижений
Ні
Літній
Короткозорість
Так
Нормальний
Жорсткі
Літній
Далекозорість
Ні
Понижений
Ні
Літній
Далекозорість
Ні
Нормальний
М’які
Літній
Далекозорість
Так
Понижений
Ні
Літній
Далекозорість
Так
Нормальний
Ні
Старечий
Короткозорість
Ні
Понижений
Ні
Старечий
Короткозорість
Ні
Нормальний
Ні
Старечий
Короткозорість
Так
Понижений
Ні
Старечий
Короткозорість
Так
Нормальний
Жорсткі
Старечий
Далекозорість
Ні
Понижений
Ні
Старечий
Далекозорість
Ні
Нормальний
М’які
Старечий
Далекозорість
Так
Понижений
Ні
Старечий
Далекозорість
Так
Нормальний
Ні
На кожному кроці алгоритму вибирається значення змінної, що розділяє всю множину на дві підмножини так, щоб всі об’єкти класу, для якого будується дерево, належали одній підмножині. Таке розбиття проводиться до тих пір, поки не буде побудована підмножина, зо містить тільки об’єкти одного класу.
Для вибору незалежної змінної і її значення, яке розділяє множину, виконуються наступні дії:
З побудованої на попередньому етапі підмножини (для першого етапу це вся навчальна вибірка), що включає об’єкти, що відносяться до вибраного класу для кожної незалежної змінної, вибираються всі значення, що зустрічаються в даній підмножині.
Для кожного значення кожної змінної підраховується кількість об’єктів, що задовольняють дану умову і відносяться до вибраного класу.
Вибираються умови, що покривають найбільшу кількість об’єктів вибраного класу.
Вибрана умова є умовою розбиття підмножини на дві нових.
Після побудови дерева для одного класу аналогічні дії виконуються для інших класів.
Приведемо приклад для даних, представлених у табл. 5.2. Нехай потрібно побудувати правило для визначення умов, при яких необхідно рекомендувати жорсткі лінзи:
якщо (?) рекомендація = жорсткі
Виконуємо оцінку кожної незалежної змінної і всіх її можливих значень:
вік = юний – 2/8;
вік = літній – 1/8;
вік = старечий – 1/8;
приписання = короткозорість – 3/12;
приписання = далекозорість – 1/12;
астигматизм = ні – 0/12;
астигматизм = так – 4/12;
ступінь зносу = низька – 0/12;
ступінь зносу = нормальна 4/12.
Вибираємо змінну і значення з максимальною оцінкою астигматизм = так. Таким чином отримуємо уточнене правило наступного виду:
якщо (астигматизм = так і ?) тоді рекомендація = жорсткі.
Дане правило утворює підмножину, в яку входять об’єкти, що відносяться до класу жорсткі. Крім них до неї входять і інші об’єкти, відповідно правило необхідно уточняти (табл. 5.6).
Табл. 5.6.
Вік
Приписання
Астигматизм
Ступінь зносу
Рекомендації
Юний
Короткозорість
Так
Понижений
Ні
Юний
Короткозорість
Так
Нормальний
Жорсткі
Юний
Далекозорість
Так
Понижений
Ні
Юний
Далекозорість
Так
Нормальний
Жорсткі
Літній
Короткозорість
Так
Понижений
Ні
Літній
Короткозорість
Так
Нормальний
Жорсткі
Літній
Далекозорість
Так
Понижений
Ні
Літній
Далекозорість
Так
Нормальний
Ні
Старечий
Короткозорість
Так
Понижений
Ні
Старечий
Короткозорість
Так
Нормальний
Жорсткі
Старечий
Далекозорість
Так
Понижений
Ні
Старечий
Далекозорість
Так
Нормальний
Ні
Виконуємо повторну оцінку для незалежних змінних, що залишились, і їх значень, але вже на новій множині:
вік = юний – 2/4;
вік = літній – 1/4;
вік = старечий – 1/4;
приписання = короткозорість – 3/6;
приписання = далекозорість – 1/6;
ступінь зносу = низька – 0/6;
ступінь зносу = нормальна – 4/6.
Після уточнення отримаємо правило і множину, представлену в табл. 5.7:
якщо (астигматизм = так і ступінь зносу = нормальна) то рекомендація = жорсткі.
Табл. 5.7.
Вік
Приписання
Астигматизм
Ступінь зносу
Рекомендації
Юний
Короткозорість
Так
Нормальний
Жорсткі
Юний
Далекозорість
Так
Нормальний
Жорсткі
Літній
Короткозорість
Так
Нормальний
Жорсткі
Літній
Далекозорість
Так
Нормальний
Ні
Старечий
Короткозорість
Так
Нормальний
Жорсткі
Старечий
Далекозорість
Так
Нормальний
Ні
Так як у отриманій множині залишаються об’єкти, що не належать класу жорсткі , то необхідно виконати уточнення:
вік = юний – 2/2;
вік = літній – 1/2;
вік = старечий – 1/2;
приписання = короткозорість – 3/3;
приписання = далекозорість – 1/3;
Очевидно, що уточнене правило матиме наступний вигляд:
якщо (астигматизм = так і ступінь зносу = нормальна і приписання = короткозорість) то рекомендація = жорсткі.
Однак в отриманій підмножині відсутній один з об’єктів, що відноситься до класу жорсткі, тому необхідно вирішити, яке з двох останніх правил більш прийнятне для аналітика.
Переваги використання дерев рішень:
швидкий процес навчання;
створення правил в областях, де експерту важко формалізувати свої знання;
інтуїтивно зрозуміла класифікаційна модель;
висока точність прогнозу, порівнянна з іншими методами (статистика, нейронні мережі);
Області застосування дерев рішень.
Дерева рішень є прекрасним інструментом в системах підтримки прийняття рішень, інтелектуального аналізу даних (data mining). До складу багатьох пакетів, призначених для інтелектуального аналізу даних, уже включені методи побудови дерев рішень.
Дерева рішень успішно застосовуються для вирішення практичних завдань у наступних областях:
банківська справа, - оцінка кредитоспроможності клієнтів банку при видачі кредитів.
промисловість, - контроль за якістю продукції (виявлення дефектів), випробування без руйнувань (наприклад перевірка якості зварювання) і т.д.
медицина, - діагностика захворювань.
молекулярна біологія, - аналіз будови амінокислот.
Контрольні питання:
Формально опишіть задачу класифікації і регресії
Способи представлення функціональної залежності між змінними
Класи використання методу "дерева рішень"
Етапи побудови дерев рішень
На чому ґрунтується методика "розділяй і владарюй"
Методи вирішення проблеми зупинки розбиття.
Основні особливості алгоритму CART
Критерій вибору змінної для розбиття (CART) - призначення та формула знаходження
Формула для знаходження ентропії
Критерій вибору змінної для розбиття (ID3) - призначення та формула знаходження
Основні особливості алгоритму С4.5
Критерій вибору змінної для розбиття (C4.5) - призначення та формула знаходження
Переваги використання дерев рішень.
Області застосування дерев рішень.
Навчальне видання
“Інтелектуальний аналіз даних”
Методичні вказівки до лабораторної роботи № 5 “Класифікація та регресія. Методи та алгоритми побудови дерев рішень” з дисципліни “Інтелектуальний аналіз даних” для студентів спеціальності 0804 “Комп’ютерні науки”
Укладач:
доц. Ковівчак Ярослав Васильович
Комп’ютерний набір, верстку та редагування
здійснили ст. гр. КН-30, каф. АСУ, Гаврилишин Ю., Гладкий Р., Дзюрак Л.
22.02.2013 12:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора