Дерева рішень та регресії
Дерева рішень та регресивні ансамблі «Випадкові ліси»
Дані та модель Принцип загальноприйнятий Класифікація Регресія Формальний: ми маємо дані навчання у вигляді векторів X i з позначками Y i. Мітки такі: Категорії (дискретні) для класифікації Продовжуйте для регресії
Індукційний принцип індукції: ми витягуємо правила з прикладів. Ми припускаємо, що правила діють навіть тоді, коли ми маємо багато даних. Парадигма індукції та дедукції: На індуктивному кроці ми формуємо правила.
Дерева класифікації та регресії Дерево - це прогнозована модель, яка: Конструює на основі набору двійкових рішень Обчислює вихідне значення Різниця між регресією та класифікацією (у побудові) задається цільовою функцією
Використовуйте індуктивний підхід Використовуйте конкретні дані для побудови набагато більш загальних правил Прогностична модель, заснована на серії булевих тестів Послідовність тестів сильніша за багато складних класифікаторів Як виглядає дерево рішень Як виглядає дерево рішень?
Ця тварина є. Вага кота чи собаки> 6 кг Так Ні Удар за хвилину> 150 снів> 15 годин Собаки більш масивні, але є ожирілі коти та є чихуахуа Чудові собаки багато сплять Так Кішка Ні Собака Так Ні Вага> 35 кг Собака Тварина = (вага, удари за хвилину, під час сну, індекс краси) індекс краси не корисний Так Ні Яка тварина є тією, яку описують (45,80, 10 9) Кішка Собака Але (8,180,18,7)
Індуктивне навчання У цьому дереві рішень ми прийняли низку бінарних рішень і побудували гілку Тварина: яка нудота у неї? Скільки він спить? Який ваш пульс? Відповідаючи на ці запитання ТАК чи НІ, ми розрізняємо собак та котів
Дані в таблиці Набір для навчання Приклад Атрибути Етикетка Вага Частота серцевих скорочень Спляча красуня Лапа 5 100 8 5 Собака - Лабрадор Пухнастий 3,5 180 16 9 Кішка - Європейська Макс 65 45 13 7 Вівчарка Рекс 6 130 16 8 Собача собака Дінго 00 15 7 Кішка - слабаного Брута 1,5 140 7 1 Собака - Пекінес Аски 15 160 19 8 Кішка - завтра кун-гра Муці 1 130 0 Кішка - ожиріння Карамель 5 10 16 9 Кішка - Бірманський Чорний 4 0 16 10 Кішка - Норвезький Нейж 0 80 18 10 Собака - Хаскі Гарфілд 8 180 19 4 Кішка - руда Тото 30 85 1 6 Собака - корцитура
Вибір атрибутів У попередній таблиці наведено 4 атрибути: вага, частота серцевих скорочень, тривалість сну та краса. Але рішення приймається на основі лише трьох. Краса не актуальна Чому? Це добре?
Як створити дерево рішень Дані описуються списком атрибутів. Атрибути можуть бути дискретними або неперервними. Розгляньте кожен атрибут по черзі і на поточний момент виберіть той, який дає найкращий поділ. Встановіть поріг і отримайте дві підзадачі, які вирішується рекурсивно аналогічно
Побудова дерева Навчання Які змінні використовуються в поточному порівнянні та де? Коли ми зупиняємось? Ми продовжуємо? Кінцевий вузол отримує мітку.
Алгоритм для дерева рішень Основна ідея: Виберіть найкращий атрибут для порівняння та розділіть приклади відповідно до прийнятого рішення, виходячи з цього атрибута. Повторіть процес, рекурсивно, для кожного піддерева. Ми зупиняємося, коли: підзадача має однакову мітку Немає більше атрибутів для спроби Немає більше даних
Класифікаційний захід, який слід оптимізувати: індекс GINI (індекс домішок) GINI (X) 1 N p i i1 P i відносна частота класу i у наборі даних X (під) відповідного розділення Нижчі значення GINI є кращими. Джині == 0 чистий клас Спочатку вимірює соціальний дисбаланс
Дерево класифікації (рішення) Дані навчання Obj x 1 xy X 1 0,14 1,6 3 X 3,7 1,4 1 X 3,4 0,6 XN 0,15 0,87 3 x 0 4 SPLIT (Жадібний): MinGINI = RealMAX Для кожного виміру d = x 1 x Для val = min (d 1 d N-1): max (d 1 d N-1 Розподіл між val d_i та val d_i + 1 Значення підмножини = більшість значень у підмножині Обчислити GINI. Якщо менше, ніж MinGINI, зберегти кінець Кінець Використовуйте розмір і val, які ведуть до MinGINI x 1
Дерево класифікації (рішення) Дані навчання Obj x 1 x y X 1 0,14 1,3 3 X 3,7 1,4 3 X 3 1,7 0,7 X 4 0,5 1,6 3 x 1 0 4 x 1 X 5 1,5. X 6 0,7 0,3 1 X 7,4 1,8 1 X 8,7 0,87 1
Дані тренувань Obj x 1 x y X 1 0,14 1,3 3 X 3,7 1,4 3 X 3 1,7 0,7 X 4 0,5 1,6 3 X 5 1,5. X 6 0,7 0,3 1 X 7,4 1,8 1 X 8,7 0,87 1 Дерево класифікації (рішення) x 1 0 Розділення x 1