Основні визначення

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

Дерева рішень (decision trees) – один із таких методів автоматичного аналізу даних. Перші ідеї створення дерев рішень прозвучали у роботах Ховленда (Hoveland) і Ханта (Hunt) кінця 50-х років XX століття. Проте основною роботою, що дала імпульс для розвитку цього напрямку, стала книга Ханта, Мерина і Стоуна ((Hunt, Marin, Stone) «Experiments in Induction» у 1966р.

Термінологія

Введемо основні поняття з теорії дерев рішень, які будуть вживатися далі:

Дерева рішень – це один із методів автоматичного аналізу даних, що дозволяє представляти правила в ієрархічній, послідовній структурі, де кожному об'єкту відповідає єдиний вузол-рішення. Під правилом розуміємо логічну конструкцію виду «якщо ..., то...» (Мал. 1).

Мал. 1. Приклад фрагменту дерева рішень.

Область застосувань дерев рішень нині є душе широкою, проте всі задачі, що розв’язуються за допомогою цього апарату можна умовно об’єднати в такі три класи:

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

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

- Регресія: якщо цільова змінна приймає неперервні значення, то дерева рішень дозволяють встановити залежність цільової змінної від незалежних (вхідних) змінних; до цього класу відносять завдання чисельного прогнозування (прогнозування цільової змінної).

Приклад дерева рішень

Нехай потрібно побудувати дерево рішень, задача якого – відповісти на питання: «Чи варто грати в гольф?». Щоб вирішити задачу, тобто прийняти рішення щодо гри в гольф, необхідно віднести дану ситуацію до одного з відомих класів (в цьому випадку це два класи: «Грати в гольф» та «Не грати в гольф»).Для цього потрібно відповісти на ряд запитання) – Мал. 2.

Мал. 2. Дерево рішень «Чи грати в гольф?».

В цьому випадку коренем дерева є запитання: «Сонячно?». Внутрішніми вузлами або вузлами перевірки є запитання: «Температура повітря висока?» та «Йде дощ?». Листками або кінцевими вузлами дерева є твердження: «Не грати в гольф» та «Грати в гольф». Гілками дерева є випадки відповідей: «Так» і «Ні».

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