Тема 6. Дерева рішень як метод дейтамайнінгу

1. Що собою являє дерево рішень?

Дерево рішень - це графічне зображення послідовності рішень і станів навколишнього середовища з зазначенням відповідних ймовірностей і виграшів для будь-яких комбінацій альтернатив і станів середовищ.

Метод дерева рішень - це один з методів автоматичного аналізу величезних масивів даних. Перші ідеї створення "дерев рішень" починаються з робіт П.Ховленда і Е.Ханта кінця 50-х років XX століття. Проте основоположною роботою, що дала імпульс для розвитку цього напряму, стала книга Е.Ханта, Дж.Мерина і П.Стоуна "Experiments in Induction", яку було опубліковано в 1966 р.

Область використання методу "дерева рішень" можна об'єднати в три класи:

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

класифікація: застосування "дерева рішень" дозволяє справитися із завданнями класифікації, тобто відношення об'єктів до одного з описаних класів;

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

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

Послідовність збору даних для побудови "дерева рішень":

• 1) визначення складу і тривалості фаз життєвого циклу проекту;
• 2) визначення ключових подій, які можуть вплинути на подальший розвиток проекту;
• 3) визначення часу настання ключових подій;
• 4) формулювання всіх можливих рішень, які можуть бути прийняті в результаті настання кожного ключового події;
• 5) визначення ймовірності прийняття кожного рішення;
• 6) визначення вартості кожного етапу здійснення проекту (вартості робіт між ключовими подіями) в поточних цінах.

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

В результаті побудови "дерева рішень" розраховуються ймовірність кожного сценарію розвитку проекту, NPV по кожному сценарієм, а також ряд інших принципово важливих як для аналізу ризиків проекту, так і для прийняття управлінських рішень показників.

В основу методу "дерева цілей" покладено підпорядкованість, розгортаємість і ранжування цілей. Дерево цілей з кількісними показниками, що використовуються в якості одного із засобів при прийнятті рішень, і носить назву "дерева рішень".

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

Рис.1. Структура дерева рішень

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

У найбільш простому вигляді дерево рішень - це спосіб представлення правил «Якщо, тоді» в ієрархічній, послідовної структурі. Основою такої структури є відповіді "Так" або "Ні" на ряд питань.