Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Класифікація та Регресія. Дерево рішень
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки до виконання дипломних та магістерських кваліфікаційних робіт
Предмет:
Інтелектуальний аналіз даних
Частина тексту файла (без зображень, графіків і формул):
Методичні вказівки
до лабораторної роботи №3
“Класифікація та Регресія.
Дерево рішень.”
з дисципліни
“Інтелектуальний аналіз даних”
для студентів базового напрямку підготовки по спеціальності
“Комп’ютерні науки” (шифр 0804)
Львів-2012
Методичні вказівки до лабораторної роботи № 1 “Класифікація та Регресія.
Дерево рішень.” з дисципліни “Інтелектуальний аналіз даних” для студентів спеціальності - шифр 0804 “Комп’ютерні науки”/ Укл. доц.Ковівчак Я.В.,Львів: Національний університет “Львівська політехніка”, 2012.
Методичні вказівки обговорено та схвалено на засіданні кафедри АСУ Протокол № ___________ від «___»___________2011 р.
Завідувач кафедрою АСУ ______________ Рашкевич Ю. М.
Методичні вказівки обговорено та схвалено на засіданні методичної комісії базового напрямку підготовки
Протокол № ___________ від «___»___________2011 р.
Лабораторна робота №3
Розробка програмного продукту.
Мета: Освоєння методів дерева рішень.
Завдання: Навчитись будувати дерева рішень.
1.Теоретичні відомості
Алгоритм CART
Алгоритм CART (ClassificationandRegressionTree), як видно з назви, вирішує завдання класифікації і регресії. Він розроблений в 1974-1984 роках чотирма професорами статистики - LeoBreiman (Berkeley), JerryFriedman (Stanford), CharlesStone (Berkeley) і RichardOlshen (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-foldcross-validation) є найбільш складною і одночасно оригінальною частиною алгоритму CART. Вона являє собою шлях вибору остаточного дерева, за умови, що набір даних має невеликий об'єм або ж запису набору даних настільки специфічні, що розділити набір на навчальну та тестову вибірку не представляється можливим.
Отже, основні характеристики алгоритму CART: бінарне розщеплення, критерій розщеплення - індекс Gini, алгоритми minimal cost-complexity tree pruning і V-fold cross-validation, принцип "виростити дерево, а потім скоротити", висока швидкість побудови, обробки пропущених значень
Алгоритм ID3
Абстрактний
Ця стаття докладно ID3 алгоритму класифікації. Дуже просто, ID3 будує дерево рішень з фіксованим набором прикладів. В результаті дерево використовується для класифікації майбутніх зразків. Наприклад має кілька атрибутів і належить до класу (наприклад, так чи ні). Листя дерева рішень містити ім'я класу, в той час як не-лист вузол є рішенням вузла. Рішення вузол є атрибутом тесту з кожної гілки (в іншій дерево рішень), що є можливим значенням атрибута. ID3 використовує інформацію посилення, щоб допомогти йому вирішити, який атрибут входить у вирішенні вузла. Перевага навчання дерева рішень є те, що програми, а не знання інженера, викликає знань від експерта.
Введення
Дж. Росс Quinlan спочатку розроблений ID3 в Університеті Сіднея. Він вперше представлений ID3 в 1975 році в книзі, Machine Learning, вип. 1, немає. 1. ID3 базується Концепція системи навчання (CLS) алгоритм. Основний алгоритм CLS над безліччю підготовки випадків C:
Крок 1: Якщо всі екземпляри в C позитивні, то створіть YES вузлів і зупинився.
Якщо всі екземпляри в C негативні, створити NO вузлів і зупинився.
В іншому випадку виберіть функцію, F зі значеннями v1, ..., Vn і створити рішення вузла.
Крок 2: Розділ підготовки випадках, C на підмножини, C1, C2, ..., Cn відповідно до значень В.
Крок 3: застосувати алгоритм рекурсивно для кожного з множин Ci.
Відзначимо, що тренер (експерт) вирішує, які маються для вибору.
ID3 покращує CLS, додавши евристичного вибору функції. ID3 пошуку по атрибутах підготовки випадках і екстракти атрибут, який відділяє кращих наведені приклади. Якщо атрибут прекрасно класифікує навчання встановлюється потім ID3 зупинках, в іншому випадку рекурсивно діє на N (де N = число можливих значень атрибутів) розподіляють підмножини, щоб отримати свої "кращі" атрибут. Алгоритм використовує жадібний пошук, тобто, він вибирає кращий атрибут і ніколи не оглядається назад, щоб переглянути раніше вибори.
Обговорення
ID3 є ненаращіваемого алгоритму, тобто він отримує свої класи від фіксованого набору навчальних екземплярів. Інкрементний алгоритм змінює поточне визначення поняття, при необхідності, нового зразка. Класи, створені за ID3 є індуктивними, тобто, враховуючи невеликий набір навчальних випадках, конкретні класи, створені за ID3 будуть працювати для всіх майбутніх випадків. Розподіл невідомих повинно бути таким же, як тестів. Індукційна класи не можуть бути доведені, щоб працювати в будь-якому випадку, так як вони можуть класифікувати нескінченну кількість екземплярів. Зверніть увагу, що ID3 (або будь-якого індуктивного алгоритму) можуть неправильної класифікації даних.
Опис даних
Вибірка даних, використовуваних ID3 є певні вимоги, які є:
Атрибут Значення Опис - ті ж атрибути повинні описати кожен приклад і мають фіксоване число значень.
Визначених класів - атрибути Наприклад, мають бути вже визначені, тобто, вони не впізнали по ID3.
Дискретна класи - класи повинні бути чітко розмежовані. Безперервна класи розбиті на невизначений такі категорії, як металом "жорсткий, досить жорстка, гнучка, м'яка, досить м'які» є підозрюваного.
Достатня прикладів - з індуктивного узагальнення використовується (тобто не доказовою) має бути достатньо тестів, щоб відрізнити дійсний моделей від випадковостей.
Вибір атрибутів
Як ID3 вирішити, який атрибут краще? Статистичні властивості, називається приріст інформації, використовується. Посилення заходів наскільки добре даний атрибут відокремлює навчальних прикладів в цільові класи. З вищою інформації (відомостей, що становлять найбільш корисні для класифікації) вибраний. Для того щоб визначити коефіцієнт підсилення, ми спочатку запозичувати ідеї з теорії інформації називають ентропією. Ентропія вимірює кількість інформації в атрибуті.
Алгоритм C4.5
C4.5 є вдосконаленою версією алгоритму ID3 того ж автора. Зокрема, в нову версію були додані відсікання гілок (англ. pruning), можливість роботи з числовими атрибутами, а також можливість побудови дерева з неповної навчальної вибірки, в якій відсутні значення деяких атрибутів.
Вимоги до даних
Для того, щоб за допомогою C4.5 побудувати вирішальне дерево і застосовувати його, дані повинні задовольняти декільком умовам.
Інформація про об'єкти, які необхідно класифікувати, повинна бути представлена у вигляді кінцевого набору ознак (атрибутів), кожен з яких має дискретне або числове значення. Такий набір атрибутів назвемо прикладом. Для всіх прикладів кількість атрибутів і їх склад мають бути постійними.
Безліч класів, на які будуть розбиватися приклади, повинно мати кінцеве число елементів, а кожен приклад має однозначно ставитися до конкретного класу. Для випадків з нечіткою логікою, коли приклади належать до класу із певною ймовірністю, C4.5 непридатний.
У навчальній вибірці кількість прикладів повинна бути значно більше кількості класів, до того ж кожен приклад має бути заздалегідь асоційований зі своїм класом. З цієї причини C4.5 є варіантом машинного навчання з учителем.
Побудова дерева
Нехай є Т - навчальна вибірка прикладів, а С - множина класів, що складається з k- елементів. Для кожного прикладу з T відома його приналежність до якогось із класів C1…Ck
Побудова дерева рішень алгоритмом C4.5 принципово не відрізняється від його побудови в ID3. На першому кроці є корінь і асоційована з ним множина Т, яку необхідно розбити на підмножини. Для цього необхідно вибрати один з атрибутів в якості перевірки.
Обраний атрибут А має n значень, що дає розбиття на nпідмножин. Далі створюються nнащадків кореня, кожному з яких поставлено у відповідність своя підмножина, отримана при розбитті Т. Процедура вибору атрибута і розбиття по ньому рекурсивно застосовується до всіх nнащадків і зупиняється в двох випадках:
після чергового розгалуження в вершині опиняються приклади з одного класу (тоді вона стає листом, а клас, якому належать її приклади, буде рішенням аркуша),
вершина виявилася асоційованою з порожньою множиною (тоді вона стає листом, а в якості рішення вибирається клас,який найбільш часто зустрічається у безпосереднього предка цієї вершини).
2.Застосування дерев рішень для задач класифікації.
Основні визначення
Стрімкий розвиток інформаційних технологій, а зокрема, прогрес у методах збору, зберігання та обробки даних, дозволив багатьом організаціям збирати величезні масиви даних, які потребують аналізу. Обсяги цих даних настільки великі, що можливостей людей-експертів уже не вистачає. Тому потреба у методах автоматичного аналізу даних зростає з кожним роком.
Дерева рішень (decision trees) – один із таких методів автоматичного аналізу даних. Перші ідеї створення дерев рішень прозвучали у роботах Ховленда (Hoveland) і Ханта (Hunt) кінця 50-х років XX століття. Проте основною роботою, що дала імпульс для розвитку цього напрямку, стала книга Ханта, Мерина і Стоуна ((Hunt, Marin, Stone) «Experiments in Induction» у 1966р.
Термінологія
Введемо основні поняття з теорії дерев рішень, які будуть вживатися далі:
Назва
Опис
Об'єкт
Приклад; шаблон; спостереження
Атрибут
Ознака; незалежна змінна; властивість
Мітка классу
Залежна змінна; цільова змінна; ознака, що визначає клас об'єкта
Вузол
Внутрішній вузол дерева; вузол перевірки
Листок
Кінцевий вузол дерева; вузол рішення
Перевірка (test)
Умова на вузлі
Дерева рішень – це один із методів автоматичного аналізу даних, що дозволяє представляти правила в ієрархічній, послідовній структурі, де кожному об'єкту відповідає єдиний вузол-рішення. Під правилом розуміємо логічну конструкцію виду «якщо ..., то...» (Мал. 1).
/
Мал. 1. Приклад фрагменту дерева рішень.
Область застосувань дерев рішень нині є душе широкою, проте всі задачі, що розв’язуються за допомогою цього апарату можна умовно об’єднати в такі три класи:
Опис даних: дерева рішень дозволяють зберігати інформацію про дані в компактній формі – замість самих даних можна зберігати дерево рішень, що містить точний опис об'єктів.
Класифікація: дерева рішень чудово підходять для задач класифікації, тобто віднесення об'єктів до одного із заздалегідь відомих класів. При цьому цільова змінна може приймати тільки дискретні значення.
Регресія: якщо цільова змінна приймає неперервні значення, то дерева рішень дозволяють встановити залежність цільової змінної від незалежних (вхідних) змінних; до цього класу відносять завдання чисельного прогнозування (прогнозування цільової змінної).
Приклад дерева рішень
Нехай потрібно побудувати дерево рішень, задача якого – відповісти на питання: «Чи варто грати в гольф?». Щоб вирішити задачу, тобто прийняти рішення щодо гри в гольф, необхідно віднести дану ситуацію до одного з відомих класів (в цьому випадку це два класи: «Грати в гольф» та «Не грати в гольф»).Для цього потрібно відповісти на ряд запитання) – Мал. 2.
/
Мал. 2. Дерево рішень «Чи грати в гольф?».
В цьому випадку коренем дерева є запитання: «Сонячно?». Внутрішніми вузлами або вузлами перевірки є запитання: «Температура повітря висока?» та «Йде дощ?». Листками або кінцевими вузлами дерева є твердження: «Не грати в гольф» та «Грати в гольф». Гілками дерева є випадки відповідей: «Так» і «Ні».
В розглянутому випадку вирішується задача бінарної класифікації, тобто створюється дихотомічна класифікаційна модель. Приклад демонструє роботу так званих бінарних дерев: в кожному вузлі розгалуження може відбуватись тільки в двох напрямках, тобто існують тільки два варіанти можливої відповіді на запитання. Бінарні дерева є частковим, найбільш простим, випадком дерев рішень. В інших випадках відповідей на запитання (і, відповідно, гілок) може бути більше, ніж дві.
Як побудувати дерево рішень?
Нехай задана певна навчальна вибірка , що містить об'єкти (приклади), кожен з яких характеризується атрибутами (ознаками), причому один з цих атрибутів вказує на приналежність об'єкта до певного класу. Нехай через {C1,C2,…,Ck} позначені класи (значення мітки класу). У цьому випадку можливі три випадки:
множина містить один або більше об’єктів, що відносяться до одного класу Ck. Тоді дерево рішень для – це листок, що визначає клас Ck;
множина не містить жодного об’єкта, тобто це порожня множина. Тоді це знову листок, і клас, що відноситься до цього листка, вибирається з іншої множини, яка відмінна від безлічі відмінного від (наприклад, з множини, що асоційована з батьком);
множина містить об’єкти, що відносяться до різних класів. У цьому випадку множину варто розбити на деякі підмножини. Для цього вибирається одна з ознак, що має два і більше відмінних одне від одного значень O1,O2,…,On. розбивається на підмножини T1,T2,…,Tn, де кожна підмножина містить всі об’єкти, що мають значення для вибраної ознаки. Ця процедура буде рекурсивно тривати доти, доки кінцева множина не буде складатися із об’єктів одного класу.
Описана вище процедура лежить в основі багатьох сучасних алгоритмів побудови дерев рішень, цей метод відомий ще за назвою «поділ та захоплення» (divide and conquer). Очевидно, що при використанні цієї методики побудова дерева рішень буде відбуватися зверху вниз. Оскільки всі об'єкти були заздалегідь віднесені до відомих нам класів, то такий процес побудови дерева рішень називається «навчанням з учителем» (supervised learning). Процес навчання також називають індуктивним навчанням або індукцією дерев (tree induction).
Нині існує велика кількість алгоритмів, що реалізують дерева рішень, проте найбільш поширеними є такі два:
CART (ClassificationandRegressionTree) – алгоритм побудови бінарного дерева рішень – дихотомічної класифікаційної моделі. Кожний вузол дерева при розбивці має тільки двох нащадків. Як видно із назви алгоритму, він вирішує задачі класифікації та регресії.
C4.5 – алгоритм побудови дерева рішень, в якому кількість нащадків вузла є необмеженою. Такі дерева призначені тільки для задач класифікації.
Більшість із відомих алгоритмів є «жадібними алгоритмами» (Greedyalgorithm) – вони полягають у прийнятті локально оптимальних рішень на кожному етапі, допускаючи що кінцеве рішення також виявиться оптимальним. При цьому, якщо один раз був обраний атрибут, і за ним було здійснене розбиття на підмножини, то алгоритм не може повернутися назад і вибрати інший атрибут, який дав би краще розбиття. Тому на етапі побудови не можна сказати чи в кінцевому результатів вибраний атрибут приведе до оптимального розбиття.
Етапи побудови дерев рішень
При побудові дерев рішень особлива увага приділяється таким питанням: вибір критерію атрибута, за яким буде розбиття, зупинка навчання та відсікання гілок.
Правило розбиття – яким чином потрібно вибирати ознаку?
Для побудови дерева на кожному внутрішньому вузлі необхідно знайти таку умову (перевірку), яка б розбивала множину, асоційовану із цим вузлом, на підмножини. В якості такої перевірки можна вибрати один із атрибутів – так званийатрибут розщеплення. Загальне правило для вибору атрибута можна сформулювати так: обраний атрибут повинен розбити множину так, щоб одержані підмножини складалися з об'єктів одного класу або були максимально наближені до цього, тобто кількість об'єктів з інших класів («домішок») у кожній з одержаних підмножин повинна бути якомога меншою.
Серед безлічі розроблених критеріїв для вибору найкращого атрибута виділимо два:
Теоретико-інформаційний критерій – алгоритм C4.5, що є удосконаленою версією алгоритму ID3 (Iterative Dichotomizer) – використовує теоретико-інформаційний підхід.
Статистичний критерій – алгоритм CART, що використовує так званий індекс Gini (в честь італійського економіста Corrado Gini) для оцінювання «відстані» між розподілами класів.
Правило зупинки. Розбивати вузол далі, чи визначати його як листок?
На додачу до основного методу побудови дерев рішень були запропоновані такі правила:
Використання статистичних методів для оцінювання доцільності подальшого розбиття – так звана «рання зупинка» (prepruning). «Рання зупинка» процесу побудови дозволяє зекономити час навчання, проте реалізує менш точні класифікаційні моделі. Тому використання «ранньої зупинки» в більшості випадків є небажаним.
Можна задати глибину дерева. Тобто, якщо подальше розбиття не повинне привести до дерева з глибиною, що перевищує задане значення.
Можна задати мінімальну кількість об’єктів у вузлі. Тобто розбиття повинне бути нетривіальним, щоб вузли, одержані в результаті розбиття, містили не менше заданої кількості об’єктів.
Цей список евристичних правил можна продовжити, але нині не існує домінуючого правила. До кожного конкретного випадку потрібно підходити індивідуально.
Правило відсікання. Яким чином потрібно відсікати гілки дерева?
Дуже часто алгоритми побудови дерев рішень видають складні, «переповнені даними» дерева, що мають багато вузлів і гілок. Такі сильно розгалужені дерева дуже важкі для розуміння. Крім того, сильно «гіллясте» дерево з багатьма вузлами розбиває навчальну множину на все велику кількість маленьких підмножин. Проте цінність правила, що містить лише 2-3 об’єкти, є вкрай низькою, тому таке правило не можна використати для аналізу даних. Набагато краще мати дерево, що має невелику кількість вузлів з великою кількістю об’єктів з навчальної вибірки. Виникає питання: чи можна побудувати всі можливі варіанти дерев для однієї навчальної множини, а тоді вибрати дерево з найменшою глибиною? На жаль, це завдання не має ефективних методів вирішення.
Для розв’язання описаної вище проблеми часто використовується так зване відсікання гілок (pruning).
Нехай точність (розпізнавання) дерева рішень – це відношення правильно класифікованих об'єктів при навчанні до загальної кількості об'єктів з навчальної множини. Тоді помилка – це відношення кількості неправильно класифікованих об’єктів до загальної кількості об’єктів у навчальній множині.
Якщо відомий спосіб оцінювання помилки дерева, гілок і листків, то можна використати таке просте правило:
побудувати дерево;
відсікти або замінити піддеревом ті гілки, відсічення яких не приведе до зростання помилки.
На відміну від процесу побудови дерева, відсікання його гілок відбувається знизу вверх, рухаючись з листків дерева, позначаючи вузли як листки, або заміняючи їх піддеревом. Процедура відсікання є більш популярною, ніж використання правил зупинки. Дерева, одержані в результаті відсікання називають усіченими деревами.
Хоча відсікання не є панацеєю, проте у більшості практичних завдань дає гарні результати, що дозволяє говорити про правомірність використання подібної методики.
Переваги використання дерев рішень та області їх застосування
Розглянувши основні проблеми, що виникають при побудові дерев, варто також перелічити деякі їх переваги:
швидкий процес навчання;
генерація правил в областях, де експертові важко формалізувати свої знання;
формулювання правил природною мовою;
інтуїтивно зрозуміла класифікаційна модель;
висока точність прогнозування впорівнянні з іншими методами (статистика, нейронні мережі);
тощо.
В силу цих та багатьох інших причин, методологія дерев рішень є важливим інструментом у роботі кожного фахівця, що займається аналізом даних. Дерева рішень є зручним інструментом у системах підтримки прийняття рішень, інтелектуального аналізу даних (data mining), особливо в галузях, де високою є ціна помилки.
Дерева рішень успішно використовуються для вирішення практичних завдань у таких областях:
Банківська справа (оцінка кредитоспроможності клієнтів банку при видачі кредитів).
Промисловість (контроль заякістю продукції (виявлення дефектів), випробування без руйнувань, наприклад, перевірка якості зварювання, тощо).
Медицина (діагностика різних захворювань).
Молекулярна біологія (аналіз будови амінокислот).
Тощо.
Побудова дерев рішень засобами Deductor
Першим етапом побудови дерева рішень є налаштування призначення полів.
/
Мал. 3. Вікно програми Deductor на 2 кроці процесу побудови дерева рішень: налаштування призначення стовпців.
Тут необхідно вказати, як будуть використовуватися поля початкового набору даних при навчанні дерева і подальшій практичній роботі з ним. У лівій частині вікна є список всіх полів вхідного набору даних. Для налаштування поля потрібно виділити його в списку, при чому в правій частині вікна відображаються поточні параметри поля:
Ім'я стовпця – ідентифікатор поля, визначений у вхідному наборі даних, який тут змінити не можна.
Тип даних – тип даних, що містяться у відповідному стовпці (дійсний, стрічковий, дата, тощо). Тип даних також задається у вхідному наборі та не можу тут змінюватись.
Призначення – тут необхідно вибрати спосіб використання даного поля при навчанні та роботі дерева рішень. Вибір здійснюється за допомогою випадаючого списку:
/ Вхідне – значення поля будуть вхідними даними для побудови і подальшої практичної роботи дерева рішень, на їх основі буде здійснюватись класифікація.
/ Вихідне – це поле буде містити результати класифікації. Вихідне поле може бути тільки одне та воно має бути дискретним.
/ Інформаційне – поле не буде використатися при навчанні дерева, але буде поміщене в результуючий набір без змін.
/Невикористовуване – поле не буде використовуватися при побудові та роботі дерева рішень та буде виключене з результуючої вибірки. Навідміну від непридатного, таке поле може бути використаним, якщо в цьому виникне необхідність.
/ Непридатне – поле не може бути використаним при побудові та роботі алгоритму, але буде поміщено в результуючий набір без змін.
Вид даних – вказує на характер даних, що містяться в полі (неперервний або дискретний). Цю властивість також не можна тут змінити. В залежності від виду даних внизу відображаються певні характеристики значень для даного поля.
Статус непридатного поля встановлюється тільки автоматично та надалі може бути зміненим лише на невикористовуване або інформаційне. Поле стає непридатним, якщо:
поле є дискретним і містить всього одне унікальне значення.
неперервне поле з нульовою дисперсією (відхиленням).
поле містить пропущені значення.
За допомогою кнопки «Налаштування нормалізації» можна здійснити нормалізацію вхідних даних, налаштувавши параметри у відповідному вікні:
/
Мал. 4. Вікно нормалізації даних.
Метою нормалізації значень полів є перетворення даних до вигляду, який найкраще підходить для опрацювання засобами пакету Deductor. Для побудови дерева рішень дані, що надходять на вхід, повинні мати числовий тип. У цьому випадку нормалізатор може перетворити дискретні дані в набір унікальних індексів.
Для кожного поля визначається свій вид нормалізації поля: / лінійна нормалізація вихідних значень або / перетворення унікальних значень у їх індекси.
Наступним кроком необхідно задати налаштування навчальної вибірки:
/
Мал. 5. Вікно програми Deductor на 3 кроці процесу побудови дерева рішень: налаштування навчальної та тестової вибірок.
Тут можна розбити навчальну вибірку для на дві підмножини – навчальну та тестову.
Навчальна множина – включає записи (приклади або об’єкти), які будуть використовуватися в якості вхідних даних та відповідних бажаних вихідних значень.
Тестова множина – також включає записи із вхідними та бажаними вихідними значеннями, але використовується не для навчання моделі, а для перевірки результатів.
Для розбивки вихідної множини навчальну та тестову необхідно налаштувати ряд параметрів:
Зі списку «Спосіб поділу вихідної множини» вибирається порядок відбору записів в усі три множини: вхідну, навчальну та тестову. Якщо обрано варіант «По порядку», то порядок записів при їх поділі не змінюється. Множини послідовно формуються відповідно до заданої для них кількості записів. Якщо ж обрано варіант «Випадково», то відбір записів відбувається випадковим чином.
Далі необхідно вказати, які множини будуть використовуватися. Для того щоб множинабула сформована, потрібно встановити прапорець ліворуч від його назви. Якщо прапорець не встановлений, то множина використовуватися не буде. Навчальна множина використовується завжди, тому скинути прапорець для неї не можна.
Для кожної з використовуваних множин потрібно задати її розмір, який може задаватись кількістю записів або у відсотках від обсягу вхідної вибірки. Для цього у відповідній клітинці треба ввести значення з клавіатури. Можна використовувати не всі записи, а тільки частину з них – тоді сумарне число записів розраховується автоматично і є меншим за 100%. Якщо ж сумарне число записів буде перевищувати максимальне для даної вхідної вибірки, то автоматично включається баланс множин, тобто при вказанні для однієї з множин розміру, результаті якого сумарне число буде перевищувати максимальне, розмір інших множин буде відповідно зменшеним.
У стовпці «Порядок сортування» можна визначити порядок проходження записів всередині кожної множини. Для цього потрібно двічі клацнути мишкою на стовпці «Порядок сортування» для відповідної множини та вибрати значення з випадаючого меню. У правій частині вікна розташовані кнопки, які дозволяють змінювати порядок застосування множин у процесі навчання.
Важливо: Для того, щоб навчальна множина була репрезентативною, необхідно, щоб у ній були присутні всі унікальні значення всіх дискретних стовпців.
Наступним кроком є налаштування параметрів навчання:
/
Мал. 6. Вікно програми Deductor на 4 кроці процесу побудови дерева рішень: налаштування параметрів процесу навчання при побудові дерева рішень.
В цьому вікні потрібно задати параметри, відповідно до яких буде проводитися навчання дерева:
Параметри ранньої зупинки:
«Мінімальна кількість прикладів, за якої буде створений новий вузол» – якщо у вузол потрапляє менше прикладів, ніж задано, то вузол ввашається листком і подальше розгалуження припиняється.
«Будувати дерево з більш достовірними правилами, спричиняючи складність дерева» – встановлення прапорця включає спеціальний алгоритм, що збільшує вірогідність результатів класифікації, ускладнюючи структуру дерева. Скидання прапорця, хоча й приводить до спрощення дерева, знижує вірогідність результатів класифікації.
Параметри відсікання
«Будувати дерево з більш достовірними правилами, спричиняючи складність дерева» – встановлення прапорця включає спеціальний алгоритм, що збільшує вірогідність результатів класифікації, ускладнюючи структуру дерева. Скидання прапорця, хоча й приводить до спрощення дерева, знижує вірогідність результатів класифікації.
«Рівень довіри, що використовується при відсіканні вузлів дерева». Значення цього параметра задається у відсотках (вибирається зі списку) і повинне бути в межах від 0% до 100%. Чим більший рівень довіри, тим більш гіллястим вийде дерево. Чим менший рівень довіри, тим більше вузлів буде відсічено при побудові дерева.
Після налаштування параметрів навчання відбувається запуск процесу навчання, під час якого, власне, будується дерево рішень (Мал. 7). Цей процес може зайняти певний час, тривалість якого залежить від величини вхідної вибірки даних та потужності комп’ютера.
/
Мал. 7. Вікно програми Deductor на 5 кроці процесу побудови дерева рішень: побудова дерева рішень.
Для керування процесом побудови дерева передбачені відповідні кнопки керування: «Пуск», «Пауза», «Стоп». У секції «Розподілено, шт.» відображається кількість об’єктів навчальної безлічі, які були розпізнані або не розпізнані в процесі побудови дерева. У секції «Розпізнано, %» вказується відсоток розпізнаних об’єктів окремо для навчальної та тестової вибірок – якщо цей відсоток буде досить великим (80%–95%), то побудову дерева можна вважати успішною. Кількість розпізнаних та не розпізнаних у процесі навчання об’єктів відображається на графіку в нижній частині вікна. Розпізнані об’єкти показуються синьою штрих-пунктирною лінією, а нерозпізнані – червоною.
Щоб краще роздивитись будь-яку область на графіку, можна збільшити її масштаб, рухаючи мишкою з натиснутою лівою клавішею у напрямку від лівого верхнього кута до правого нижнього кута. При зміні напрямку руху курсора з правого нижнього кута до лівого верхнього кута масштаб буде зменшуватись.
У правій частині вікна відображається така інформація:
кількість вузлів в отриманому дереві.
кількість правил.
тривалість навчання – час, що пройшов від початку побудови дерева до його завершення.
темп відновлення – можна задати період відновлення графіка, що відображає побудову дерева.
Під графіком розташований прогрес-індикатор, що відображає процес побудови дерева.
Останнім кроком є вибір способу відображення дерева та присвоєння його назви.
Завдання до лабораторної роботи
Ознайомитись з теоретичними вказівками.
Запустити Deductor та ознайомитись із його основними можливостями.
Відкрити тестовий приклад сценарію та проаналізувати готову гілку з побудованим деревом рішень. Проаналізувати отримані результати.
Вивчити процес побудови дерева рішень.
Використовуючи один із готових файлів даних, пройти всі необхідні кроки для побудови дерева рішень.
Сформувати власні дані, вибравши довільну тему.
Пройти всі кроки на власних даних, приділивши більшу увагу налаштуванню параметрів.
Проаналізувати отримані результати і зробити висновок.
Підготувати звіт до лабораторної роботи з власними даними (скріншоти, результати).
Завдання 1
Небо
Температура
Вологість
Вітряно
Гуляти?
Сонячно
30
85
Ні
Не гуляти
Сонячно
27
90
Так
Не гуляти
Хмарно
28
78
Ні
Гуляти
Дощ
21
96
Ні
Гуляти
Дощ
20
80
Ні
Гуляти
Дощ
18
70
Так
Не гуляти
Хмарно
18
65
Так
Гуляти
Сонячно
22
95
Ні
Не гуляти
Сонячно
21
70
Ні
Гуляти
Дощ
24
80
Ні
Гуляти
Сонячно
24
70
Так
Гуляти
Хмарно
22
90
Так
Гуляти
Хмарно
27
75
Ні
Гуляти
Хмарно
27
75
Ні
Гуляти
Дощ
22
80
Так
Не гуляти
Завдання 2
Вік
Конкуренція
Тип
Виручка
Старий
Так
ПЗ
Низька
Старий
Ні
ПЗ
Низька
Старий
Ні
Залізо
Низька
Середній
Так
ПЗ
Низька
Середній
Так
Залізо
Низька
Середній
Ні
Залізо
Висока
Середній
Ні
ПЗ
Висока
Новий
Так
ПЗ
Висока
Новий
Ні
Залізо
Висока
Новий
Ні
ПЗ
Висока
Завдання 3
День
Прогноз
Температура
Вологість
Вітер
Грати в м’яч
D1
Сонячний
Гаряча
Висока
Слабкі
Ні
D2
Сонячний
Гаряча
Висока
Сильні
Ні
D3
Похмуро
Гаряча
Висока
Слабкі
Так
D4
Дощ
М'яка
Висока
Слабкі
Так
D5
Дощ
Прохолодний
Нормальний
Слабкий
Так
D6
Дощ
Прохолодний
Нормальний
сильний
Ні
D7
Похмуро
Прохолодний
Нормальний
Сильні
Так
D8
Сонячний
М'яка
Висока
Слабкі
Ні
D9
Сонячний
Прохолодний
Нормальний
Слабкий
Так
D10
Дощ
М'який
Нормальний
Слабкий
Так
D11
Сонячний
М'яка
Нормальний
Сильні
Так
D12
Похмуро
М'яка
Висока
Сильні
Так
D13
Похмуро
Гарячі
Нормальний
Слабкий
Так
D14
Дощ
М'яка
Висока
Сильні
Ні
Завдання 4
Вік>=21
Нерухомість
Освіта
Дохід>10000
Чи давати кредит?
18
Ні
Середня
5000
Ні
25
Так
Вища
7000
Так
18
Ні
Середня
12000
…
24
Так
Вища
15000
Так
31
Так
Вища
18000
Так
23
Так
Нема
1000
Ні
Завдання 5
Студент
Середній бал>=71
Стан стипендії
С1
71
Так
С2
69
Ні
С3
88
Підвищена
С4
74
Так
С5
70
Ні
С6
93
Підвищена
С7
83
Так
Завдання 6
Водій
Порушення
Штраф
В1
Так
Так
В2
Ні
Ні
В3
Так
Так
В4
Так
Так
В5
Ні
Ні
В6
Ні
Ні
В7
Так
Так
Завдання 7
Тип послуги
Ціна (грн)
Сума на рахунку(грн)
Чи надавати послугу ?
Дзвінок
0,50
0,45
Ні
Дзвінок
0,50
1,70
Так
02.02.2013 01:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора