Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Застосування дерев рішень для задач класифікації
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
КН
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2018
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Методи і системи штучного інтелекту
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
КАФЕДРА АВТОМАТИЗОВАНИХ СИСТЕМ УПРАВЛІННЯ
Звіт до лабораторної роботи №4
з дисципліни " Методи та системи штучного інтелекту "
на тему: " Застосування дерев рішень для задач класифікації "
Короткі теоретичні відомості
Стрімкий розвиток інформаційних технологій, а зокрема, прогрес у методах збору, зберігання та обробки даних, дозволив багатьом організаціям збирати величезні масиви даних, які потребують аналізу. Обсяги цих даних настільки великі, що можливостей людей-експертів уже не вистачає. Тому потреба у методах автоматичного аналізу даних зростає з кожним роком.
Дерева рішень (decision trees) – один із таких методів автоматичного аналізу даних. Перші ідеї створення дерев рішень прозвучали у роботах Ховленда (Hoveland) і Ханта (Hunt) кінця 50-х років XX століття. Проте основною роботою, що дала імпульс для розвитку цього напрямку, стала книга Ханта, Мерина і Стоуна ((Hunt, Marin, Stone) «Experiments in Induction» у 1966р.
Дерева рішень – це один із методів автоматичного аналізу даних, що дозволяє представляти правила в ієрархічній, послідовній структурі, де кожному об'єкту відповідає єдиний вузол-рішення. Під правилом розуміємо логічну конструкцію виду «якщо ..., то...» (Рис. 1).
/
Рис. 1. Приклад фрагменту дерева рішень.
Область застосувань дерев рішень нині є душе широкою, проте всі задачі, що розв’язуються за допомогою цього апарату можна умовно об’єднати в такі три класи:
Опис даних: дерева рішень дозволяють зберігати інформацію про дані в компактній формі – замість самих даних можна зберігати дерево рішень, що містить точний опис об'єктів.
Класифікація: дерева рішень чудово підходять для задач класифікації, тобто віднесення об'єктів до одного із заздалегідь відомих класів. При цьому цільова змінна може приймати тільки дискретні значення.
Регресія: якщо цільова змінна приймає неперервні значення, то дерева рішень дозволяють встановити залежність цільової змінної від незалежних (вхідних) змінних; до цього класу відносять завдання чисельного прогнозування (прогнозування цільової змінної).
Приклад дерева рішень
Нехай потрібно побудувати дерево рішень, задача якого – відповісти на питання: «Чи варто грати в гольф?». Що вирішити задачу, тобто прийняти рішення щодо гри в гольф, необхідно віднести дану ситуацію до одного з відомих класів (в цьому випадку це два класи: «Грати в гольф» та «Не грати в гольф»). Для цього потрібно відповісти на ряд запитань, що щнаходяться у вузлах цього дерева, починаючи з його кореня (першого запитання) – Рис. 2.
/
Рис. 2. Дерево рішень «Чи грати в гольф?».
В цьому випадку коренем дерева є запитання: «Сонячно?». Внутрішніми вузлами або вузлами перевірки є запитання: «Температура повітря висока?» та «Йде дощ?». Листками або кінцевими вузлами дерева є твердження: «Не грати в гольф» та «Грати в гольф». Гілками дерева є випадки відповідей: «Так» і «Ні».
В розглянутому випадку вирішується задача бінарної класифікації, тобто створюється дихотомічна класифікаційна модель. Приклад демонструє роботу так званих бінарних дерев: в кожному вузлі розгалуження може відбуватись тільки в двох напрямках, тобто існують тільки два варіанти можливої відповіді на запитання. Бінарні дереває частковим, найбільш простим, випадком дерев рішень. В інших випадках відповідей на запитання (і, відповідно, гілок) може бути більше, ніж дві.
Як побудувати дерево рішень?
Нехай задана певна навчальна вибірка , що містить об'єкти (приклади), кожен з яких характеризується атрибутами (ознаками), причому один з цих атрибутів вказує на приналежність об'єкта до певного класу. Нехай через позначені класи (значення мітки класу). У цьому випадку можливі три випадки:
множина містить один або більше об’єктів, що відносяться до одного класу . Тоді дерево рішень для – це листок, що визначає клас ;
множина не містить жодного об’єкта, тобто це порожня множина. Тоді це знову листок, і клас, що відноситься до цього листка, вибирається з іншої множини, яка відмінна від безлічі відмінного від (наприклад, з множини, що асоційована з батьком);
множина містить об’єкти, що відносяться до різних класів. У цьому випадку множину варто розбити на деякі підмножини. Для цього вибирається одна з ознак, що має два і більше відмінних одне від одного значень . розбивається на підмножини, де кожна підмножина містить всі об’єкти, що мають значення для вибраної ознаки. Ця процедура буде рекурсивно тривати доти, доки кінцева множина не буде складатися із об’єктів одного класу.
Описана вище процедура лежить в основі багатьох сучасних алгоритмів побудови дерев рішень, цей метод відомий ще за назвою «поділ та захоплення» (divide and conquer). Очевидно, що при використанні цієї методики побудова дерева рішень буде відбуватися зверху вниз. Оскільки всі об'єкти були заздалегідь віднесені до відомих нам класів, то такий процес побудови дерева рішень називається «навчанням з учителем» (supervised learning). Процес навчання також називають індуктивним навчанням або індукцією дерев (tree induction).
Нині існує велика кількість алгоритмів, що реалізують дерева рішень, проте найбільш поширеними є такі два:
CART (Classification and Regression Tree) – алгоритм побудови бінарного дерева рішень – дихотомічної класифікаційної моделі. Кожний вузол дерева при розбивці має тільки двох нащадків. Як видно із назви алгоритму, він вирішує задачі класифікації та регресії.
C4.5 – алгоритм побудови дерева рішень, в якому кількість нащадків вузла є необмеженою. Такі дерева призначені тільки для задач класифікації.
Більшість із відомих алгоритмів є «жадібними алгоритмами» (Greedy algorithm) – вони полягають у прийнятті локально оптимальних рішень на кожному етапі, допускаючи що кінцеве рішення також виявиться оптимальним. При цьому, якщо один раз був обраний атрибут, і за ним було здійснене розбиття на підмножини, то алгоритм не може повернутися назад і вибрати інший атрибут, який дав би краще розбиття. Тому на етапі побудови не можна сказати чи в кінцевому результатів вибраний атрибут приведе до оптимального розбиття.
Завдання до лабораторної роботи:
Ознайомитись з теоретичними вказівками.
Запустити Deductor та ознайомитись із його основними можливостями.
Відкрити тестовий приклад сценарію та проаналізувати готову гілку з побудованим деревом рішень. Проаналізувати отримані результати.
Вивчити процес побудови дерева рішень.
Використовуючи один із готових файлів даних, пройти всі необхідні кроки для побудови дерева рішень.
Сформувати власні дані, вибравши довільну тему.
Пройти всі кроки на власних даних, приділивши більшу увагу налаштуванню параметрів.
Проаналізувати отримані результати і зробити висновок.
Виконання лабораторної роботи:
/
Імпортовані дані
Майстер обробки
/
Дерево рішень
Висновок: під час виконання даної лабораторної роботи я ознайомився з деревом рішень (decision tree)
01.12.2018 15:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора