Етапи побудови дерев рішень

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

Правило розбиття – яким чином потрібно вибирати ознаку?

Для побудови дерева на кожному внутрішньому вузлі необхідно знайти таку умову (перевірку), яка б розбивала множину, асоційовану із цим вузлом, на підмножини. В якості такої перевірки можна вибрати один із атрибутів – так званий атрибут розщеплення. Загальне правило для вибору атрибута можна сформулювати так: обраний атрибут повинен розбити множину так, щоб одержані підмножини складалися з об'єктів одного класу або були максимально наближені до цього, тобто кількість об'єктів з інших класів («домішок») у кожній з одержаних підмножин повинна бути якомога меншою.

Серед безлічі розроблених критеріїв для вибору найкращого атрибута виділимо два:

1. Теоретико-інформаційний критерій – алгоритм C4.5, що є удосконаленою версією алгоритму ID3 (Iterative Dichotomizer) – використовує теоретико-інформаційний підхід.

2. Статистичний критерій – алгоритм CART, що використовує так званий індекс Gini (в честь італійського економіста Corrado Gini) для оцінювання «відстані» між розподілами класів.

Правило зупинки. Розбивати вузол далі, чи визначати його як листок?

На додачу до основного методу побудови дерев рішень були запропоновані такі правила:

- Використання статистичних методів для оцінювання доцільності подальшого розбиття – так звана «рання зупинка» (prepruning). «Рання зупинка» процесу побудови дозволяє зекономити час навчання, проте реалізує менш точні класифікаційні моделі. Тому використання «ранньої зупинки» в більшості випадків є небажаним.

- Можна задати глибину дерева. Тобто, якщо подальше розбиття не повинне привести до дерева з глибиною, що перевищує задане значення.

- Можна задати мінімальну кількість об’єктів у вузлі. Тобто розбиття повинне бути нетривіальним, щоб вузли, одержані в результаті розбиття, містили не менше заданої кількості об’єктів.

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

Правило відсікання. Яким чином потрібно відсікати гілки дерева?

Дуже часто алгоритми побудови дерев рішень видають складні, «переповнені даними» дерева, що мають багато вузлів і гілок. Такі сильно розгалужені дерева дуже важкі для розуміння. Крім того, сильно «гіллясте» дерево з багатьма вузлами розбиває навчальну множину на все велику кількість маленьких підмножин. Проте цінність правила, що містить лише 2-3 об’єкти, є вкрай низькою, тому таке правило не можна використати для аналізу даних. Набагато краще мати дерево, що має невелику кількість вузлів з великою кількістю об’єктів з навчальної вибірки. Виникає питання: чи можна побудувати всі можливі варіанти дерев для однієї навчальної множини, а тоді вибрати дерево з найменшою глибиною? На жаль, це завдання не має ефективних методів вирішення.

Для розв’язання описаної вище проблеми часто використовується так зване відсікання гілок (pruning).

Нехай точність (розпізнавання) дерева рішень – це відношення правильно класифікованих об'єктів при навчанні до загальної кількості об'єктів з навчальної множини. Тоді помилка – це відношення кількості неправильно класифікованих об’єктів до загальної кількості об’єктів у навчальній множині.

Якщо відомий спосіб оцінювання помилки дерева, гілок і листків, то можна використати таке просте правило:

- побудувати дерево;

- відсікти або замінити піддеревом ті гілки, відсічення яких не приведе до зростання помилки.

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

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