Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Класифікація та регресія. Методи та алгоритми побудови дерев рішень
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Інтелектуальний аналіз даних
Частина тексту файла (без зображень, графіків і формул):
Методичні вказівки
до лабораторної роботи №2
“Класифікація та регресія.
Методи та алгоритми побудови дерев рішень”
з дисципліни
“Інтелектуальний аналіз даних”
Лабораторна робота №2
Мета: Оволодіти методами та алгоритмами побудови дерев рішень.
Етап 1. Формулювання завдання.
Насамперед необхідно відкинути всі фактори, що не стосуються проблеми, а серед безлічі тих, що залишилися, виділити суттєві і несуттєві. Це дозволить привести опис завдання щодо прийняття управлінського рішення у форму, що піддається аналізу. Повинні бути виконані такі основні процедури:
визначення можливостей збору інформації для експериментування і реальних дій;
складання переліку подій, що з певною імовірністю можуть відбутися;
установлення часового порядку розміщення подій, у наслідках яких міститься корисна і доступна інформація, і тих послідовних дій, які можна розпочати.
Оскільки нам потрібно побудувати дерево рішень яке б розв’язувало завдання для якоїсь спортивної події чи змагання, а саме відповідало на питання чи отримає учасник медаль нам потрібно створити даних, аналіз яких дозволив нам б відсіяти слабких спортсменів, і залишити учасників які б мали великі шанси на завоювання медалі у стрільбі,плаванні чи шахах.
Для побудови нашого дерева рішень ми маєм 3 категорії інформації.
Вид спорту.
Очки.
Час.
Саме ці фактори (Вид, очки і час) є суттєвими для нашого рішення, і дозволять привести опис завдання щодо прийняття управлінського рішення у форму, що піддається аналізу.
Побудова дерева рішень
Завдання 10
Нехай потрібно побудувати дерево рішень, задача якого – відповісти на питання: «Чи буде медаль?». Щоб вирішити задачу, тобто оцінити чи буде у спортсмена медаль, необхідно віднести дану ситуацію до одного з відомих класів (в цьому випадку це два класи: «Буде медаль» та «Не буде медалі»). Для цього потрібно проаналізувати ряд даних).
Таблиця 10
Вид спорту
Очки
Час(хв)
Чи буде медаль?
Стрільба
40
2
Ні
Стрільба
100
2
Так
Плавання
20
1
Ні
Плавання
110
2
Так
Шахи
100
15
Так
Шахи
30
15
Ні
Зрозуміло, що дерево прийняття рішень буде набувати різних виглядів в залежності від послідовності обирання атрибутів на кожній ітерації алгоритму ID3. Зазвичай атрибути впорядковуються за важливістю, яку може заздалегідь визначити експерт в галузі проблеми задачі.
Алгоритм ID3 – один із найважливіших методів індуктивного відновлення правил за прикладами, який забезпечує автоматичну побудову баз знань діагностичних експертних систем.
Класифікація і регресія
В задачі класифікації і регресії потрібно виділити значення залежної змінної об’єкту на основі значень інших змінних, які характеризують даний об’єкт. Формально задачу класифікації і регресії можна описати наступним чином. Нехай ми маємо множину об’єктів:
I = {i1,i2…,ij,…,in}
де іj – досліджуваний об’єкт. Прикладом таких об’єктів може бути інформація про спортсменів та отримання ними медалі.(табл. 5.1).
Вид спорту
Очки
Час(хв)
Чи буде медаль?
Стрільба
40
2
Ні
Стрільба
100
2
Так
Плавання
20
1
Ні
Плавання
110
2
Так
Шахи
100
15
Так
Шахи
30
15
Ні
Табл. 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 століття.
Область використання методу "дерева рішень" можна об'єднати в три класи:
Опис даних: застосування "дерева рішень" дозволяє зберігати інформацію про вибірку даних в компактній і зручній для обробки формі, що містить в собі точні описи об'єктів;
Класифікація: застосування "дерева рішень" дозволяє справитися із завданнями класифікації, тобто відношення об'єктів до одного з описаних класів;
Регресія: якщо змінна має недостовірні значення, то застосування "дерева рішень" дозволяє визначити залежність цієї цільової змінної від незалежних (вхідних) змінних;
Головна перевага "дерева рішень" перед іншими методами - можливість пов'язати ставлення цілі з діями, що підлягають реалізації в сьогоденні. При побудові багаторівневого "дерева рішень" досягнення мети кожного з рівнів моделі забезпечується комплексом заходів попереднього рівня. Кожен рівень "дерева рішень" повинен займати певне місце в ієрархічній послідовності, складеної на основі дотримання причинно-наслідкових зв'язків.
Алгоритм ID3
Розглянемо критерій вибору незалежної змінної, від якої буде будуватися дерево. Повний набір варіантів розбиття | X | це кількість незалежних змінних. Розглянемо перевірку змінної Xn, яка приймає m значень – Cn1, Cn2,…, Cnm. Тоді розбиття множини об'єктів вибірки N для перевірки змінної Xn дасть підмножини T1, T2, …, Tm.
Ми очікуємо, що при розбитті множини, будемо отримувати підмножини з меншим числом об'єктів, зате більш впорядковані. Так, щоб у кожному з них були по-можливості об'єкти одного класу. Ця міра впорядкованості (невизначеності) характеризується інформацією. У контексті розглянутої задачі це кількість інформації, необхідна для того, щоб віднести об'єкт до того чи іншого класу. При поділі множини на підмножини, невизначеність належності об'єктів до конкретних класів буде зменшуватися.
Єдина доступна інформація - яким чином класи розподілені в множині T і її підмножинах, одержуваних при розбитті. Саме вона і використовується при виборі змінної.
Розглянемо приклад, в якому потрібно побудувати дерево рішень щодо того, чи отримає спортсмен медаль. Виходячи з минулих спостережень (накопичення історичних даних), можливо три варіанти розбиття дерева (мал. 5.2).
Мал. 5.2. Три варіанти розбиття дерева.
Нехай – число об’єктів із навчальної вибірки, які відносяться до класу сr. Тоді ймовірність того, що випадково вибраний об’єкт із навчальної вибірки множини буде належати класу сr рівна:
(5)
Підрахуємо кількість інформації, ґрунтуючись на числі об’єктів того чи іншого класу, які будуть знаходитись у вузлі дерева після розбиття вхідної множини.
Згідно теорії інформації оцінку середньої кількості інформації, необхідної для визначення класа об’єкта із множини Т, дозволяє обчислити вираз:
, (6)
Підставивши у дану формулу отримане значення для Р, отримаємо:
, (7)
Оскільки використовується логарифм з двійковою основою, то цей вираз дає кількісну оцінку в бітах.
Для оцінки кількості інформації справедливі наступні твердження:
Якщо кількість об’єктів того або іншого класа в отриманій підмножині рівна 0, то кількість інформації також – 0.
Якщо кількість об’єктів одного класу дорівнює кількості об’єктів іншого класу, то кількість інформації максимальна.
Мал. 5.3. Варіанти розбиття.
Аналогічно можна обчислити значення Gain для кожного розбиття:
Gain (вид спорту) = 0.034 біт.
Gain (очки) = 1біт.
Отже, що наступною змінною, по якій розбиватимуть підмножину Т (сонячно) буде «очки».
Подальші розбиття в цій вітці уже не потребуються, оскільки в отриманих підмножинах всі об’єкти відносяться тільки до одного класу.
Якщо в процесі роботи алгоритму отриманий вузол, асоційований з порожньою множиною, то він відмічається як лист, і в якості розв’язку листа вибирається найбільш частий клас у безпосереднього предка даного листа.
Приклад дерева рішень
Покроковий алгоритм побудови дерева
Вік>=21
Нерухомість
Освіта
Дохід>10000
Чи давати кредит?
18
Ні
Середня
5000
Ні
25
Так
Вища
7000
Так
18
Ні
Середня
12000
…
24
Так
Вища
15000
Так
31
Так
Вища
18000
Так
23
Так
Нема
1000
Ні
Чи давати кредит? – це атрибут прийняття рішень. Множина всіх умовних атрибутів A = {«вік», «нерухомість», «освіта», «дохід»} відповідає кореневій вершині. Виберемо атрибут «освіта» та позначимо ним кореневу вершину. Множина значень цього атрибуту складається з трьох елементів: середня, вища, нема. Кореневій вершині поставимо у відповідність три ребра, кожному з яких припишемо значення атрибуту «освіта». Множину прикладів розіб’ємо на три підмножини, які відповідають значенням атрибуту «освіта»; ці підмножини
відповідають кожній із вершин 2, 3, 4 дерева, зображеного на рис.
Атрибут «освіта» вилучимо з множини A та отримаємо множину A = {«вік»,«дохід»«нерухомість»}.
Перший крок роботи алгоритму ID3.
Крок 2
Вилучення атрибуту «Освіта».
Крок 3
Вилучення атрибуту «Нерухомість».
У вершині 3 приклади мають однакові значення атрибуту «Чи давати кредит» -так, тому ми замінюєм їх на ТАК.
У вершині 4 приклад один і він має значення атрибуту «Чи давати кредит» - ні,
тому ми замінюєм їх на НІ.
Дерево рішень для таблиці 1
За побудованим деревом прийняття рішень можемо визначити множину правил:
якщо (освіта=так) то (“Чи давати кредит” = ТАК);
якщо (освіта=нема) то (“Чи давати кредит” = НІ);
якщо (освіта=середня) і (нерухомість=ні) і (Дохід=5000), то (“Чи давати кредит” =ні);
якщо (освіта=середня) і (нерухомість=ні) і (Дохід=12000), то (“Чи давати кредит” =…);
Зрозуміло, що дерево прийняття рішень буде набувати різних виглядів в залежності від послідовності обирання атрибутів на кожній ітерації алгоритму ID3. Зазвичай атрибути впорядковуються за важливістю, яку може заздалегідь визначити експерт в галузі проблеми задачі.
Алгоритм ID3 – один із найважливіших методів індуктивного відновлення правил за прикладами, який забезпечує автоматичну побудову баз знань діагностичних експертних систем.
Алгоритм С4.5
Представляє собою покращений варіант алгоритму ID3. Серед покращень потрібно відмітити наступні:
можливість працювати не тільки з категоріальними атрибутами, але й з числовими. Для цього алгоритм розбиває область значень незалежної змінної на декілька інтервалів і ділить початкову множину на підмножини відповідно з тим інтервалом, в який попадає значення залежної змінної;
після побудови дерева відбувається обрізання його віток. Якщо отримане дерево занадто велике, то виконується або групування декількох вузлів в один лист, або заміщення вузла дерева нижче розміщеним піддеревом. Перед операцією над деревом обчислюється помилка правила класифікації, який міститься в поточному вузлі. Якщо після заміщення (або групування) помилка не збільшиться (і не сильно збільшиться ентропія), це означає, що заміну можна виконати без втрат для побудованої моделі.
Один з недоліків алгоритму ID3 є те, що він некоректно працює з атрибутами, які мають унікальні значення для всіх об'єктів з вибірки. Для таких об'єктів інформаційна ентропія дорівнює нулю і ніяких нових даних від залежної змінної отримати не вдасться. Оскільки після розбиття отримувані підмножини будуть містити по одному об'єкту.
Алгоритм C4.5 вирішує цю проблему шляхом введення нормалізації. Оцінюється не кількість об'єктів того чи іншого класу після розбиття, а число підмножин і їх потужність (число елементів).
Вираз
(10)
оцінює потенційну інформацію, що отримується при розбитті множини Т на m підмножин.
Критерієм вибору змінної для розбиття буде вираз:
(11)
або
(12)
За умови, що є k класів і n (число об'єктів в навчальній вибірці і кількість значень змінних), тоді чисельник максимально буде рівний, а знаменник максимально рівний . Якщо припустити, що кількість об'єктів значно більше кількості класів, то знаменник зростає швидше, ніж чисельник і, відповідно, значення виразу буде невеликим.
У вибірці можуть бути об'єкти з пропущеними значеннями атрибутів. У цьому випадку їх або відкидають (що дає ризик втратити частину даних), або застосувати підхід, який припускає, що пропущені значення розподілені пропорційно частоті появи існуючих значень.
Ідею алгоритму можна представити у графічному вигляді (рис 5.4). При наявності в об’єктів тільки двох змінних, то їх можна представити у вигляді точок двовимірного простору. Об’єкти різних класів відмічені знаками «+»і«-». З рисунку видно, що при розбитті множини на підмножини будується дерево, що покриває тільки об’єкти вибраного класу (мал. 5.4).
Мал. 5.4. Ідея алгоритму С 4.5
Для постановки правил з використанням даного алгоритму необхідно щоб у навчальній вибірці були присутні все можливі комбінації значень незалежних змінних. Наприклад, дані, що дозволяють порекомендувати тип контактних лінз, представлені у табл. 5.5
Переваги використання дерев рішень:
швидкий процес навчання;
створення правил в областях, де експерту важко формалізувати свої знання;
інтуїтивно зрозуміла класифікаційна модель;
висока точність прогнозу, порівнянна з іншими методами (статистика, нейронні мережі);
Області застосування дерев рішень.
Дерева рішень є прекрасним інструментом в системах підтримки прийняття рішень, інтелектуального аналізу даних (data mining). До складу багатьох пакетів, призначених для інтелектуального аналізу даних, уже включені методи побудови дерев рішень.
Дерева рішень успішно застосовуються для вирішення практичних завдань у наступних областях:
банківська справа, - оцінка кредитоспроможності клієнтів банку при видачі кредитів.
промисловість, - контроль за якістю продукції (виявлення дефектів), випробування без руйнувань (наприклад перевірка якості зварювання) і т.д.
медицина, - діагностика захворювань.
молекулярна біологія, - аналіз будови амінокислот.
Висновок : під час виконання даної лабораторної роботи я розглянув основні алгоритми побудови дерева рішень; визначити переваги та недоліки методів, реалізував на практиці алгоритми С4.5 та ID3 та намалював дерево рішень.
21.12.2013 22:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора