Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Інформаційні технології
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Звіт
до лабораторної роботи №4
«Застосування дерев рішень для задач класифікації»
Короткі теоретичні відомості
Стрімкий розвиток інформаційних технологій, а зокрема, прогрес у методах збору, зберігання та обробки даних, дозволив багатьом організаціям збирати величезні масиви даних, які потребують аналізу. Обсяги цих даних настільки великі, що можливостей людей-експертів уже не вистачає. Тому потреба у методах автоматичного аналізу даних зростає з кожним роком.
Дерева рішень (decision trees) – один із таких методів автоматичного аналізу даних. Перші ідеї створення дерев рішень прозвучали у роботах Ховленда (Hoveland) і Ханта (Hunt) кінця 50-х років XX століття. Проте основною роботою, що дала імпульс для розвитку цього напрямку, стала книга Ханта, Мерина і Стоуна ((Hunt, Marin, Stone) «Experiments in Induction» у 1966р.
Термінологія
Введемо основні поняття з теорії дерев рішень, які будуть вживатися далі:
Назва
Опис
Об'єкт
Приклад; шаблон; спостереження
Атрибут
Ознака; незалежна змінна; властивість
Мітка класу
Залежна змінна; цільова змінна; ознака, що визначає клас об'єкта
Вузол
Внутрішній вузол дерева; вузол перевірки
Листок
Кінцевий вузол дерева; вузол рішення
Перевірка (test)
Умова на вузлі
Дерева рішень – це один із методів автоматичного аналізу даних, що дозволяє представляти правила в ієрархічній, послідовній структурі, де кожному об'єкту відповідає єдиний вузол-рішення. Під правилом розуміємо логічну конструкцію виду «якщо ..., то...»
Область застосувань дерев рішень нині є душе широкою, проте всі задачі, що розв’язуються за допомогою цього апарату можна умовно об’єднати в такі три класи:
Опис даних: дерева рішень дозволяють зберігати інформацію про дані в компактній формі – замість самих даних можна зберігати дерево рішень, що містить точний опис об'єктів.
Класифікація: дерева рішень чудово підходять для задач класифікації, тобто віднесення об'єктів до одного із заздалегідь відомих класів. При цьому цільова змінна може приймати тільки дискретні значення.
Регресія: якщо цільова змінна приймає неперервні значення, то дерева рішень дозволяють встановити залежність цільової змінної від незалежних (вхідних) змінних; до цього класу відносять завдання чисельного прогнозування (прогнозування цільової змінної).
Приклад дерева рішень
Нехай потрібно побудувати дерево рішень, задача якого – відповісти на питання: «Чи варто грати в гольф?». Що вирішити задачу, тобто прийняти рішення щодо гри в гольф, необхідно віднести дану ситуацію до одного з відомих класів (в цьому випадку це два класи: «Грати в гольф» та «Не грати в гольф»). Для цього потрібно відповісти на ряд запитань, що щнаходяться у вузлах цього дерева, починаючи з його кореня (першого запитання) – Рис. 1.
Рис. 1. Дерево рішень «Чи грати в гольф?».
В цьому випадку коренем дерева є запитання: «Сонячно?». Внутрішніми вузлами або вузлами перевірки є запитання: «Температура повітря висока?» та «Йде дощ?». Листками або кінцевими вузлами дерева є твердження: «Не грати в гольф» та «Грати в гольф». Гілками дерева є випадки відповідей: «Так» і «Ні».
В розглянутому випадку вирішується задача бінарної класифікації, тобто створюється дихотомічна класифікаційна модель. Приклад демонструє роботу так званих бінарних дерев: в кожному вузлі розгалуження може відбуватись тільки в двох напрямках, тобто існують тільки два варіанти можливої відповіді на запитання. Бінарні дереває частковим, найбільш простим, випадком дерев рішень. В інших випадках відповідей на запитання (і, відповідно, гілок) може бути більше, ніж дві.
Як побудувати дерево рішень?
Нехай задана певна навчальна вибірка , що містить об'єкти (приклади), кожен з яких характеризується атрибутами (ознаками), причому один з цих атрибутів вказує на приналежність об'єкта до певного класу. Нехай через позначені класи (значення мітки класу). У цьому випадку можливі три випадки:
множина містить один або більше об’єктів, що відносяться до одного класу . Тоді дерево рішень для – це листок, що визначає клас ;
множина не містить жодного об’єкта, тобто це порожня множина. Тоді це знову листок, і клас, що відноситься до цього листка, вибирається з іншої множини, яка відмінна від безлічі відмінного від (наприклад, з множини, що асоційована з батьком);
множина містить об’єкти, що відносяться до різних класів. У цьому випадку множину варто розбити на деякі підмножини. Для цього вибирається одна з ознак, що має два і більше відмінних одне від одного значень . розбивається на підмножини, де кожна підмножина містить всі об’єкти, що мають значення для вибраної ознаки. Ця процедура буде рекурсивно тривати доти, доки кінцева множина не буде складатися із об’єктів одного класу.
Описана вище процедура лежить в основі багатьох сучасних алгоритмів побудови дерев рішень, цей метод відомий ще за назвою «поділ та захоплення» (divide and conquer). Очевидно, що при використанні цієї методики побудова дерева рішень буде відбуватися зверху вниз. Оскільки всі об'єкти були заздалегідь віднесені до відомих нам класів, то такий процес побудови дерева рішень називається «навчанням з учителем» (supervised learning). Процес навчання також називають індуктивним навчанням або індукцією дерев (tree induction).
Нині існує велика кількість алгоритмів, що реалізують дерева рішень, проте найбільш поширеними є такі два:
CART (Classification and Regression Tree) – алгоритм побудови бінарного дерева рішень – дихотомічної класифікаційної моделі. Кожний вузол дерева при розбивці має тільки двох нащадків. Як видно із назви алгоритму, він вирішує задачі класифікації та регресії.
C4.5 – алгоритм побудови дерева рішень, в якому кількість нащадків вузла є необмеженою. Такі дерева призначені тільки для задач класифікації.
Більшість із відомих алгоритмів є «жадібними алгоритмами» (Greedy algorithm) – вони полягають у прийнятті локально оптимальних рішень на кожному етапі, допускаючи що кінцеве рішення також виявиться оптимальним. При цьому, якщо один раз був обраний атрибут, і за ним було здійснене розбиття на підмножини, то алгоритм не може повернутися назад і вибрати інший атрибут, який дав би краще розбиття. Тому на етапі побудови не можна сказати чи в кінцевому результатів вибраний атрибут приведе до оптимального розбиття.
Етапи побудови дерев рішень
При побудові дерев рішень особлива увага приділяється таким питанням: вибір критерію атрибута, за яким буде розбиття, зупинка навчання та відсікання гілок.
Правило розбиття – яким чином потрібно вибирати ознаку?
Для побудови дерева на кожному внутрішньому вузлі необхідно знайти таку умову (перевірку), яка б розбивала множину, асоційовану із цим вузлом, на підмножини. В якості такої перевірки можна вибрати один із атрибутів – так званий атрибут розщеплення. Загальне правило для вибору атрибута можна сформулювати так: обраний атрибут повинен розбити множину так, щоб одержані підмножини складалися з об'єктів одного класу або були максимально наближені до цього, тобто кількість об'єктів з інших класів («домішок») у кожній з одержаних підмножин повинна бути якомога меншою. Серед безлічі розроблених критеріїв для вибору найкращого атрибута виділимо два:
Теоретико-інформаційний критерій – алгоритм C4.5, що є удосконаленою версією алгоритму ID3 (Iterative Dichotomizer) – використовує теоретико-інформаційний підхід.
Статистичний критерій – алгоритм CART, що використовує так званий індекс Gini (в честь італійського економіста Corrado Gini) для оцінювання «відстані» між розподілами класів.
Правило зупинки. Розбивати вузол далі, чи визначати його як листок?
На додачу до основного методу побудови дерев рішень були запропоновані такі правила:
Використання статистичних методів для оцінювання доцільності подальшого розбиття – так звана «рання зупинка» (prepruning). «Рання зупинка» процесу побудови дозволяє зекономити час навчання, проте реалізує менш точні класифікаційні моделі. Тому використання «ранньої зупинки» в більшості випадків є небажаним.
Можна задати глибину дерева. Тобто, якщо подальше розбиття не повинне привести до дерева з глибиною, що перевищує задане значення.
Можна задати мінімальну кількість об’єктів у вузлі. Тобто розбиття повинне бути нетривіальним, щоб вузли, одержані в результаті розбиття, містили не менше заданої кількості об’єктів.
Цей список евристичних правил можна продовжити, але нині не існує домінуючого правила. До кожного конкретного випадку потрібно підходити індивідуально.
Правило відсікання. Яким чином потрібно відсікати гілки дерева?
Дуже часто алгоритми побудови дерев рішень видають складні, «переповнені даними» дерева, що мають багато вузлів і гілок. Такі сильно розгалужені дерева дуже важкі для розуміння. Крім того, сильно «гіллясте» дерево з багатьма вузлами розбиває навчальну множину на все велику кількість маленьких підмножин. Проте цінність правила, що містить лише 2-3 об’єкти, є вкрай низькою, тому таке правило не можна використати для аналізу даних. Набагато краще мати дерево, що має невелику кількість вузлів з великою кількістю об’єктів з навчальної вибірки. Виникає питання: чи можна побудувати всі можливі варіанти дерев для однієї навчальної множини, а тоді вибрати дерево з найменшою глибиною? На жаль, це завдання не має ефективних методів вирішення.
Для розв’язання описаної вище проблеми часто використовується так зване відсікання гілок (pruning).
Нехай точність (розпізнавання) дерева рішень – це відношення правильно класифікованих об'єктів при навчанні до загальної кількості об'єктів з навчальної множини. Тоді помилка – це відношення кількості неправильно класифікованих об’єктів до загальної кількості об’єктів у навчальній множині.
Якщо відомий спосіб оцінювання помилки дерева, гілок і листків, то можна використати таке просте правило:
побудувати дерево;
відсікти або замінити піддеревом ті гілки, відсічення яких не приведе до зростання помилки.
На відміну від процесу побудови дерева, відсікання його гілок відбувається знизу вверх, рухаючись з листків дерева, позначаючи вузли як листки, або заміняючи їх піддеревом. Процедура відсікання є більш популярною, ніж використання правил зупинки. Дережа, одержані в результаті відсікання називають усіченими деревами.
Хоча відсікання не є панацеєю, проте у більшості практичних завдань дає гарні результати, що дозволяє говорити про правомірність використання подібної методики.
Переваги використання дерев рішень та області їх застосування
Розглянувши основні проблеми, що виникають при побудові дерев, варто також перелічити деякі їх переваги:
швидкий процес навчання;
генерація правил в областях, де експертові важко формалізувати свої знання;
формулювання правил природною мовою;
інтуїтивно зрозуміла класифікаційна модель;
висока точність прогнозування в порівнянні з іншими методами (статистика, нейронні мережі);
тощо.
Дерева рішень успішно використовуються для вирішення практичних завдань у таких областях:
Банківська справа (оцінка кредитоспроможності клієнтів банку при видачі кредитів).
Промисловість (контроль за якістю продукції (виявлення дефектів), випробування без руйнувань, наприклад, перевірка якості зварювання, тощо).
Медицина (діагностика різних захворювань).
Молекулярна біологія (аналіз будови амінокислот).
Виконання роботи:
1. Ознайомився з теоретичними вказівками.
2. Запустив програмний пакет Deductor та ознайомився із його основними можливостями.
3. Відкрив тестовий приклад сценарію та проаналізувати готову гілку з побудованим деревом рішень. Проаналізувати отримані результати.
4. Ознайомився з процесом побудови дерева рішень.
5. Використовуючи один із готових файлів даних, пройшов всі необхідні кроки для побудови дерева рішень.
6. Сформував власні дані, вибравши тему видачі іпотеки. Використав наступні поля:
Розмір іпотеки, $
Строк, р
Дохід, грн
Наявність нерухомості
Наявність авто
Стать
Сімейний стан
Вік
Забезпеченість позики
Давати іпотеку
7. Для імпорту даних використав Мастер
8. Під час імпорту типізую дані. Це буде необхідно для формування дерева рішень
Фрагмент імпортовнаих даних
9. По завершенні імопрту даних завантажую Майстер обробки і обираю Побудову дерев. Проходжу всі необхідні кроки, при тому налаштовую необхідні параметри
10. Завершаю.чим етапом є запуск побудови дерева рішень. Якщо % розпізнавань в межах 80-100, то дерево рішень побудовано добре.
Отримані результати:
Висновки: Отже, на цій лабораторній роботі, я вивчив процес формування дерев рішень за допомогою пакета Deductor
11.06.2013 17:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора