Як побудувати дерево рішень
Нехай нам задано деякий навчальну множину T, що містить об'єкти (приклади), кожен з яких характеризується m атрибутами (атрибутами), причому один з них вказує на приналежність об'єкта до певного класу.
Ідею побудови дерев рішень з безлічі T, вперше висловлену Хантом, наведемо по Р. Куінлену (R. Quinlan).
Нехай через 1. C2. Ck> позначені класи (значення мітки класу), тоді існують 3 ситуації:
безліч T містить один або більше прикладів, що відносяться до одного класу Ck. Тоді дерево рішень для Т - це лист, який визначає клас Ck;
безліч T не містить жодного прикладу, тобто порожня множина. Тоді це знову лист, і клас, асоційований з листом, вибирається з іншого безлічі відмінного від T, скажімо, з безлічі, асоційованого з батьком;
безліч T містить приклади, відносяться до різних класів. В цьому випадку слід розбити безліч T на деякі підмножини. Для цього вибирається один з ознак, що має два і більше відмінних один від одного значень O1. O2. On. T розбивається на підмножини T1. T2. Tn. де кожна підмножина Ti містить всі приклади, що мають значення Oi для вибраної ознаки. Це процедура буде рекурсивно тривати до тих пір, поки кінцеве множина не буде складатися із прикладів, що відносяться до одного і того ж класу.
Вищеописана процедура лежить в основі багатьох сучасних алгоритмів побудови дерев рішень, цей метод відомий ще під назвою поділу і захоплення (divide and conquer). Очевидно, що при використанні даної методики, побудова дерева рішень буде відбувається зверху вниз.
Оскільки всі об'єкти були заздалегідь віднесені до відомих нам класів, такий процес побудови дерева рішень називається навчанням з учителем (supervised learning). Процес навчання також називають індуктивним навчанням або індукцією дерев (tree induction).
На сьогоднішній день існує дуже багато алгоритмів, що реалізують дерева рішень CART, C4.5, NewId, ITrule, CHAID, CN2 і т.д. Але найбільшого поширення і популярність отримали наступні два:
CART (Classification and Regression Tree) - це алгоритм побудови бінарного дерева рішень - дихотомічної класифікаційної моделі. Кожен вузол дерева при розбитті має тільки двох нащадків. Як видно з назви алгоритму, вирішує завдання класифікації і регресії.
C4.5 - алгоритм побудови дерева рішень, кількість нащадків у вузла не обмежена. Не вміє працювати з безперервним цільовим полем, тому вирішує тільки завдання класифікації.
Більшість з відомих алгоритмів є "жадібними алгоритмами". Якщо один раз був обраний атрибут, і по ньому було вироблено розбиття на підмножини, то алгоритм не може повернутися назад і вибрати інший атрибут, який дав би краще розбиття. І тому на етапі побудови можна сказати дасть обраний атрибут, в кінцевому підсумку, оптимальне розбиття.
Етапи побудови дерев рішень
При побудові дерев рішень особлива увага приділяється наступним питанням: вибору критерію атрибута, за яким піде розбиття, зупинки навчання і відсікання гілок. Розглянемо всі ці питання по порядку.