Правило відсікання
Дуже часто алгоритми побудови дерев рішень дають складні дерева, які переповнені даними, мають багато вузлів і гілок. Такі "гіллясті" дерева дуже важко зрозуміти. До того ж гіллясте дерево, що має багато вузлів, розбиває навчальну множину на все більшу кількість підмножин, що складаються з меншої кількості об'єктів. Цінність правила, справедливого, скажімо, для 2-3 об'єктів, вкрай низька, і з метою аналізу даних таке правило практично непридатне. Набагато краще мати дерево, що складається з малої кількості вузлів, яким відповідала б велика кількість об'єктів з навчальної вибірки. І тут виникає питання: а чи не побудувати всі можливі варіанти дерев, що відповідають навчальній множині, і з них вибрати дерево з найменшою глибиною? На жаль, це завдання є NP-повною, це було показано Л. Хайфілем (L. Hyafill) та Р. Рівестом (R. Rivest), і, як відомо, цей клас завдань не має ефективних методів вирішення.
Для вирішення вищеописаної проблеми часто застосовується так зване відсікання гілок (pruning).
Нехай під точністю (розпізнавання) дерева рішень розуміється відношення правильно класифікованих об'єктів під час навчання до загальної кількості об'єктів з навчальної множини, а під помилкою – кількість неправильно класифікованих. Припустимо, що нам відомий спосіб оцінки помилки дерева, гілок та листя. Тоді, можна використовувати наступне просте правило:
відсікти чи замінити поддеревом ті гілки, які призведуть до зростання помилки.
На відміну від процесу побудови, відсікання гілок відбувається знизу вгору, рухаючись з листя дерева, відзначаючи вузли як листя, або замінюючи їх піддеревом. Хочавідсікання не є панацеєю, але в більшості практичних завдань дає хороші результати, що дозволяє говорити про правомірність використання подібної методики.
Іноді навіть усічені дерева можуть бути складні для сприйняття. У такому разі можна вдатися до методики вилучення правил з дерева з подальшим створенням наборів правил, що описують класи.
Для отримання правил необхідно досліджувати всі шляхи від кореня до кожного листа дерева. Кожен такий шлях дасть правило, де умовами будуть перевірки з вузлів, що зустрілися на шляху.
Переваги використання дерев рішень
Розглянувши основні проблеми, що виникають при побудові дерев, було б несправедливо не згадати про їх переваги:
швидкий процес навчання;
генерація правил у галузях, де експерту важко формалізувати свої знання;
вилучення правил природною мовою;
інтуїтивно зрозуміла класифікаційна модель;
висока точність прогнозу, яка можна порівняти з іншими методами (статистика, нейронні мережі);
побудова непараметричних моделей.
З цих і багатьох інших причин, методологія дерев рішень є важливим інструментом у роботі кожного фахівця, що займається аналізом даних, незалежно від того практик він чи теоретик.
Області застосування дерев рішень
Дерева рішень є чудовим інструментом у системах підтримки прийняття рішень, інтелектуального аналізу даних (data mining). До складу багатьох пакетів, призначених для інтелектуального аналізу даних, вже включено методи побудови дерев рішень. В областях, де висока ціна помилки, вони послужать чудовою підмогою аналітика чи керівника
Дерева рішень успішно застосовуютьсядля вирішення практичних завдань у таких областях:
Банківська справа. Оцінка кредитоспроможності клієнтів банку при видачі кредитів.
Промисловість. Контроль за якістю продукції (виявлення дефектів), випробування без руйнувань (наприклад, перевірка якості зварювання) і т.д.
Медицина. Діагностика різних захворювань.
Молекулярна біологія. Аналіз будови амінокислот.
Це далеко не повний список областей, де можна використовувати дерева рішень. Не досліджено ще багато потенційних сфер застосування.