Приклади алгоритму дерева рішень у видобутку даних

decision tree algorithm examples data mining

Цей поглиблений посібник пояснює все про алгоритм дерева рішень при видобутку даних. Ви дізнаєтесь про приклади дерева рішень, алгоритм та класифікацію:

Ми подивились пару Приклади інтелектуального аналізу даних у нашому попередньому уроці в Безкоштовні навчальні серії з обробки даних .

Видобуток дерева рішень - це тип техніки видобутку даних, який використовується для побудови моделей класифікації. Він будує класифікаційні моделі у вигляді деревоподібної структури, як і її назва. Цей вид майнінгу належить до контрольованого класного навчання.

При контрольованому навчанні цільовий результат вже відомий. Дерева рішень можна використовувати як для категоріальних, так і для числових даних. Категоричні дані представляють стать, сімейний стан тощо, тоді як числові дані - вік, температуру тощо.

гарнітура віртуальної реальності для xbox 360 - -

Приклад дерева рішень із набором даних наведено нижче.

(зображення джерело )

Що ви дізнаєтесь:

• Яке використання дерева рішень?
• Класифікаційний аналіз
• Регресійний аналіз
• Як працює дерево рішень?
• Алгоритм індукції дерева рішень
• Індукція дерева рішень
• КОРОБКА
• Індукція дерева рішень для машинного навчання: ID3
• Що таке жадібне рекурсивне двійкове розщеплення?
• Як вибрати атрибути для створення дерева?
  • # 1) Збільшення інформації
  • # 2) Коефіцієнт посилення
  • # 3) Індекс Джині
• Переобладнання в деревах прийняття рішень
• Що таке обрізка дерев?
• Що таке прогнозне моделювання?
• Переваги класифікації дерева рішень
• Недоліки класифікації дерева рішень
• Висновок
• Рекомендована література

Яке використання дерева рішень?

Дерево рішень використовується для побудови моделей класифікації та регресії. Він використовується для створення моделей даних, які передбачатимуть мітки класів або значення для процесу прийняття рішень. Моделі побудовані на основі навчального набору даних, що подається до системи (навчання під контролем).

Використовуючи дерево рішень, ми можемо візуалізувати рішення, які полегшують розуміння, і, отже, це популярна техніка видобутку даних.

Класифікаційний аналіз

Класифікація даних - це форма аналізу, яка створює модель, яка описує важливі змінні класу.Наприклад, модель, побудована для класифікації заявок на банківські позики як безпечних або ризикованих. Методи класифікації використовуються в машинному навчанні та розпізнаванні зразків.

Застосування класифікації включає виявлення шахрайства, медичну діагностику, цільовий маркетинг тощо. Результатом проблеми класифікації вважається 'Режим' усіх спостережуваних значень термінального вузла.

Для побудови класифікаційної моделі дотримується двоетапного процесу.

1. На першому етапі, тобто навчання: побудована модель класифікації, що базується на даних навчання.
2. На другому етапі, тобто класифікації, перевіряється точність моделі, а потім модель використовується для класифікації нових даних. Наведені тут мітки класів мають форму дискретних значень, таких як 'так' або 'ні', 'безпечно' або 'ризиковано'.

Загальний підхід до побудови класифікаційних моделей наведено нижче:

(зображення джерело )

Регресійний аналіз

Регресійний аналіз використовується для прогнозування числових атрибутів.

Числові атрибути також називаються неперервними значеннями. Модель, побудована для прогнозування неперервних значень замість міток класів, називається моделлю регресії. Результатом регресійного аналізу є 'середнє значення' всіх спостережуваних значень вузла.

Як працює дерево рішень?

Дерево рішень - це керований алгоритм навчання, який працює як для дискретних, так і для неперервних змінних. Він розділяє набір даних на підмножини на основі найважливішого атрибута в наборі даних. Як дерево рішень ідентифікує цей атрибут і як відбувається це розбиття, визначається алгоритмами.

Найбільш значущим предиктором позначається кореневий вузол, розбиття здійснюється для формування підвузлів, які називаються вузлами прийняття рішень, а вузли, які не розбиваються далі, є кінцевими або листовими вузлами.

У дереві рішень набір даних поділяється на однорідні та неперекриваються регіони. Це дотримується підходу зверху вниз, оскільки верхній регіон представляє всі спостереження в одному місці, яке розділяється на дві або більше гілок, які далі розділяються. Цей підхід також називають а жадібний підхід оскільки він враховує лише поточний вузол між відпрацьованими, не фокусуючись на майбутніх вузлах.

Алгоритми дерева рішень продовжуватимуть працювати, доки не буде досягнуто такі критерії зупинки, як мінімальна кількість спостережень тощо.

Після побудови дерева рішень багато вузлів можуть представляти відхилення або галасливі дані. Метод обрізки дерев застосовується для видалення небажаних даних. Це, в свою чергу, покращує точність класифікаційної моделі.

Щоб знайти точність моделі, використовується набір тестів, що складається з тестових кортежів та міток класів. Відсотки кортежів набору тестів правильно класифікують за моделлю, щоб визначити точність моделі. Якщо модель визнана точною, вона використовується для класифікації наборів даних, для яких мітки класів невідомі.

Деякі алгоритми дерева рішень включають Алгоритм Ханта, ID3, CD4.5 та CART.

Приклад створення дерева рішень

(Приклад взято з концепцій видобутку даних: Хан та Кімбер)

# 1) Крок навчання: Дані навчання подаються в систему для аналізу за допомогою алгоритму класифікації. У цьому прикладі мітка класу є атрибутом, тобто “рішенням про позику”. Модель, побудована на основі цих навчальних даних, представлена ​​у вигляді правил прийняття рішень.

# 2) Класифікація: Тестовий набір даних подається в модель для перевірки точності правила класифікації. Якщо модель дає прийнятні результати, тоді вона застосовується до нового набору даних із невідомими змінними класу.

Алгоритм індукції дерева рішень

Індукція дерева рішень

Індукція дерева рішень - це метод вивчення дерев рішень з навчального набору. Навчальний набір складається з атрибутів та ярликів класів. Застосування індукції дерева рішень включає астрономію, фінансовий аналіз, медичну діагностику, виробництво та виробництво.

Дерево рішень - це деревоподібна структура блок-схеми, яка зроблена з наборів навчальних наборів. Набір даних розбивається на менші підмножини і присутній у вигляді вузлів дерева. Деревоподібна структура має кореневий вузол, внутрішні вузли або вузли прийняття рішень, листовий вузол та гілки.

Кореневий вузол - це найвищий вузол. Він являє собою найкращий атрибут, обраний для класифікації. Внутрішні вузли вузлів прийняття рішень представляють випробування атрибута листового вузла набору даних або термінального вузла, який представляє класифікацію або мітку прийняття рішення. Гілки показують результат проведеного тесту.

Деякі дерева рішень є лише двійкові вузли , це означає рівно дві гілки вузла, тоді як деякі дерева рішень не є двійковими.

На зображенні нижче показано дерево рішень для набору даних 'Титанік', щоб передбачити, виживе пасажир чи ні.

(зображення джерело )

КОРОБКА

Модель CART, тобто класифікація та регресія - це алгоритм дерева рішень для побудови моделей. Модель дерева рішень, де цільові значення мають дискретний характер, називається моделями класифікації.

Дискретне значення - це скінченний або злічувано нескінченний набір значень, Наприклад, вік, розмір тощо. Моделі, де цільові значення представлені безперервними значеннями, зазвичай є числами, які називаються моделями регресії. Безперервні змінні - це змінні з плаваючою комою. Ці дві моделі разом називаються CART.

CART використовує індекс Джині як матрицю класифікації.

Індукція дерева рішень для машинного навчання: ID3

Наприкінці 1970-х - на початку 1980-х років Дж. Росс Квінлан був дослідником, який побудував алгоритм дерева рішень для машинного навчання. Цей алгоритм відомий як ID3, Ітеративний дихотомайзер . Цей алгоритм був продовженням концепції систем навчання, описаних Е. Б. Хант, Дж. Та Маріном.

Пізніше ID3 отримав назву C4.5. ID3 та C4.5 дотримуються жадібного підходу зверху вниз для побудови дерев рішень. Алгоритм починається з навчального набору даних із мітками класів, які розподіляються на менші підмножини під час побудови дерева.

# 1) Спочатку існує три параметри, тобто список атрибутів, спосіб вибору атрибутів та розділ даних . Список атрибутів описує атрибути кортежів набору тренувань.

# два) Метод вибору атрибутів описує метод вибору найкращого атрибута для дискримінації між кортежами. Методами, що використовуються для вибору атрибутів, можуть бути Інформаційний приріст або Індекс Джині.

c ++ випадкове число між

# 3) Структура дерева (двійкова або недвійкова) визначається методом вибору атрибутів.

# 4) При побудові дерева рішень воно починається як єдиний вузол, що представляє кортежі.

# 5) Якщо кортежні кортежні вузли представляють різні мітки класів, тоді він викликає метод вибору атрибута, щоб розділити або розділити кортежі. Крок призведе до формування гілок та вузлів прийняття рішень.

# 6) Метод розбиття визначає, який атрибут слід вибрати для розділення кортежів даних. Він також визначає гілки, які потрібно вирощувати з вузла, відповідно до результату тесту. Основним мотивом критеріїв розділення є те, що розділ на кожній гілці дерева рішень повинен представляти одну і ту ж мітку класу.

Приклад атрибута розділення наведено нижче:

a. Порціювання вище має дискретне значення.

b. Порція вище призначена для безперервної оцінки.

# 7) Вищезазначені кроки розділення виконуються рекурсивно, щоб сформувати дерево рішень для наборів навчальних наборів даних.

# 8) Розділення зупиняється лише тоді, коли зроблені або всі розділи, або коли інші кортежі не можуть бути розділені далі.

# 9) Складність алгоритму описується n * | D | * журнал | D | де n - кількість атрибутів у наборі даних D та | D | - кількість кортежів.

Що таке жадібне рекурсивне двійкове розщеплення?

У двійковому методі розщеплення кортежі розбиваються і обчислюється кожна функція розщепленої вартості. Вибрано найнижчий розподіл витрат. Метод розщеплення - двійковий, який утворюється у вигляді 2 гілок. За своєю суттю він рекурсивний, оскільки той самий метод (обчислення вартості) використовується для розбиття інших кортежів набору даних.

Цей алгоритм називається таким жадібним, оскільки він фокусується лише на поточному вузлі. Він зосереджений на зниженні його вартості, тоді як інші вузли ігноруються.

Як вибрати атрибути для створення дерева?

Заходи відбору атрибутів також називаються правилами розділення, щоб вирішити, як кортежі будуть розділятися. Критерії розбиття використовуються для найкращого розділення набору даних. Ці заходи забезпечують ранжування атрибутів для розділення навчальних кортежів.

Найпопулярнішими методами вибору атрибуту є отримання інформації, індекс Джині.

# 1) Збільшення інформації

Цей метод є основним методом, який використовується для побудови дерев рішень. Це зменшує інформацію, необхідну для класифікації кортежів. Це зменшує кількість тестів, необхідних для класифікації даного кортежу. Вибирається атрибут з найбільшим прирістом інформації.

Оригінальна інформація, необхідна для класифікації кортежу в наборі даних D, надається:

Де p - ймовірність належності кортежу до класу C. Інформація кодується у бітах, тому використовується журнал до бази 2. E (s) представляє середній обсяг інформації, необхідний для з'ясування мітки класу набору даних D. Цей інформаційний приріст також називається Ентропія .

Інформація, необхідна для точної класифікації після порціонування, подається за формулою:

Де P (c) - вага перегородки. Ця інформація представляє інформацію, необхідну для класифікації набору даних D при порціонуванні X.

Інформаційний приріст - це різниця між вихідною та очікуваною інформацією, необхідною для класифікації наборів даних D.

Коефіцієнт посилення - це зменшення кількості інформації, необхідне завдяки знанню значення X. Атрибут із найбільшим коефіцієнтом інформаційного посилення вибирається як 'найкращий'.

# 2) Коефіцієнт посилення

Збільшення інформації іноді може призвести до порціонування марним для класифікації. Однак коефіцієнт посилення розбиває набір навчальних даних на розділи та враховує кількість кортежів результату відносно загальної кількості кортежів. Атрибут із коефіцієнтом максимального посилення використовується як атрибут розділення.

# 3) Індекс Джині

Індекс Джині розраховується лише для двійкових змінних. Він вимірює домішки в навчальних кортежах набору даних D, як

P - ймовірність належності кортежу до класу C. Індекс Джині, який обчислюється для двійкового розділеного набору даних D за атрибутом A, визначається як:

Де n - n-й розділ набору даних D.

Зменшення домішок дається різницею індексу Джіні вихідного набору даних D та індексу Джіні після розділення за атрибутом A.

Максимальне зменшення домішок або максимальний індекс Джині вибрано як найкращий атрибут для розщеплення.

Переобладнання в деревах прийняття рішень

Переобладнання відбувається, коли дерево рішень намагається бути якомога досконалішим, збільшуючи глибину тестів і тим самим зменшуючи помилку. Це призводить до дуже складних дерев і призводить до переобладнання.

Переобладнання зменшує прогнозний характер дерева рішень. Підходи, що дозволяють уникнути переобладнання дерев, включають попередню та післярізальну обрізку.

Що таке обрізка дерев?

Обрізка - це метод видалення невикористаних гілок з дерева рішень. Деякі гілки дерева рішень можуть представляти відхилення або галасливі дані.

Обрізка дерев - це метод зменшення небажаних гілок дерева. Це зменшить складність дерева та допоможе у ефективному прогнозному аналізі. Це зменшує переобладнання, оскільки видаляє неважливі гілки з дерев.

Є два способи обрізки дерева:

# 1) Підготовка : При такому підході побудова дерева рішень зупиняється достроково. Це означає, що вирішено більше не розділяти гілки. Останній побудований вузол стає листовим, і цей листовий вузол може містити найпоширеніший клас серед кортежів.

Заходи вибору атрибутів використовуються для з'ясування ваги розколу. Порогові значення призначаються, щоб вирішити, які спліти вважаються корисними. Якщо порціонування вузла призводить до розщеплення, падаючи нижче порогового значення, тоді процес зупиняється.

# 2) Постріппінг : Цей метод видаляє відкинуті гілки з повністю вирощеного дерева. Небажані гілки видаляють і замінюють листовим вузлом, що позначає найпоширеніший ярлик класу. Ця техніка вимагає більших обчислень, ніж попередня обрізка, однак вона більш надійна.

Обрізані дерева є більш точними та компактними у порівнянні з необрізаними деревами, але вони мають недоліки тиражування та повторення.

Повторення відбувається, коли той самий атрибут тестується знову і знову вздовж гілки дерева. Реплікація відбувається, коли повторювані піддерева присутні в дереві. Ці питання можуть бути вирішені за допомогою багатоваріантних розколів.

На зображенні внизу показано необрізане та обрізане дерево.

Приклад алгоритму дерева рішень

Приклад Джерело

Побудова дерева рішень

Візьмемо приклад останніх 10 днів набору даних про погоду з атрибутами прогноз, температура, вітер та вологість. Змінна результату буде грати в крикет чи ні. Ми використаємо алгоритм ID3 для побудови дерева рішень.

Крок 1: Першим кроком буде створення кореневого вузла.

Крок 2: Якщо всі результати 'так', то повернеться вузол 'так', інакше повернеться вузол 'ні'.

Крок 3: З’ясуйте Ентропію всіх спостережень та ентропію з атрибутом “x”, тобто E (S) та E (S, x).

Крок 4: Дізнайтеся про приріст інформації та виберіть атрибут з високим обсягом інформації.

Крок 5: Повторюйте наведені вище кроки, поки не будуть охоплені всі атрибути.

Розрахунок ентропії:

так ні

9 5

Якщо ентропія дорівнює нулю, це означає, що всі члени належать до одного класу, а якщо ентропія одна, то це означає, що половина кортежів належить одному класу, а один з них належить іншому класу. 0,94 означає справедливий розподіл.

операційні системи з відкритим кодом для ПК

Знайдіть атрибут отримання інформації, який дає максимальний приріст інформації.

Наприклад “Вітер”, він приймає два значення: Сильний і Слабкий, отже, x = {Сильний, Слабкий}.

Знайдіть H (x), P (x) для x = слабкий та x = сильний. H (S) вже розраховано вище.

Слабкий = 8

Сильний = 8

За “слабкий” вітер 6 з них кажуть “Так”, щоб пограти в крикет, а 2 з них кажуть “Ні”. Отже, ентропія буде такою:

За “сильний” вітер 3 сказали “Ні” грати в крикет, а 3 сказали “Так”.

Це показує ідеальну випадковість, оскільки половина предметів належить одному класу, а решта половини належить іншим.

Обчислити приріст інформації,

Аналогічним чином приріст інформації для інших атрибутів:

Атрибут outlook має найвищий приріст інформації 0,246, таким чином він обраний коренем.

Похмуро має 3 значення: Сонячно, Похмуро та Дощ. Похмуре з ігровим крикетом завжди 'Так'. Тож це закінчується листовим вузлом, 'так'. Для інших значень “Сонячно” та “Дощ”.

Таблиця для Outlook як “Сонячна” буде такою:

Ентропія для 'Outlook' 'Sunny':

Виграш інформації для атрибутів щодо Сонячного становить:

Приріст інформації щодо вологості є найвищим, тому його вибирають наступним вузлом. Подібним чином Ентропія розраховується для Дощу. Вітер дає найбільший приріст інформації .

Дерево рішень буде виглядати нижче:

Що таке прогнозне моделювання?

Моделі класифікації можна використовувати для прогнозування результатів невідомого набору ознак.

Коли набір даних із невідомими мітками класів подається в модель, він автоматично призначає їй мітку класу. Цей метод застосування ймовірності для прогнозування результатів називається прогнозним моделюванням.

Переваги класифікації дерева рішень

Нижче наведено різні переваги класифікації дерева рішень:

1. Класифікація дерева рішень не вимагає знань доменів, отже, вона підходить для процесу виявлення знань.
2. Подання даних у вигляді дерева легко зрозуміле людям і воно інтуїтивне.
3. Він може обробляти багатовимірні дані.
4. Це швидкий процес з великою точністю.

Недоліки класифікації дерева рішень

Нижче наведено різні недоліки класифікації дерева рішень:

1. Іноді дерева рішень стають дуже складними, і їх називають переобладнаними деревами.
2. Алгоритм дерева рішень може бути не оптимальним рішенням.
3. Дерева рішень можуть повертати упереджене рішення, якщо якась мітка класу домінує над ним.

Висновок

Дерева рішень - це методи аналізу даних для класифікації та регресійного аналізу.

Зараз ця техніка охоплює багато областей, таких як медична діагностика, цільовий маркетинг тощо. Ці дерева побудовані за алгоритмом, таким як ID3, CART. Ці алгоритми знаходять різні способи розділити дані на розділи.

Це найбільш відома техніка навчання під контролем, яка використовується в машинному навчанні та аналізі шаблонів. Дерева рішень передбачають значення цільової змінної шляхом побудови моделей шляхом вивчення навчального набору, що надається системі.

Ми сподіваємось, що ви дізналися все про видобуток дерев рішень з цього інформаційного посібника !!

НАЗАД Підручник | НАСТУПНИЙ підручник

Рекомендована література

• Приклади інтелектуального аналізу даних: Найпоширеніші програми інтелектуального аналізу даних 2021
• Методи видобутку даних: алгоритм, методи та найпопулярніші інструменти видобування даних
• Видобуток даних: процес, методи та основні проблеми аналізу даних
• Структура даних дерева B та дерева B + у C ++
• Структура даних двійкового дерева в C ++
• Процес видобутку даних: задіяні моделі, етапи процесу та виклики
• Структура даних дерева та купи AVL у C ++
• Видобуток даних проти машинного навчання проти штучного інтелекту проти глибокого навчання