Дерева рішень

Метод дерева рішень – це один з методів автоматичного аналізу величезних масивів даних. Перші ідеї створення "дерев рішень" починаються з робіт П.Ховленда і Е.Ханта кінця 50-х років XX століття.

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

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

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

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

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

Застосування методу "дерева рішень" дозволяє:

1. Визначати шляхи досягнення мети з виконанням кількісної оцінки складності виникають завдань та оцінкою труднощі здійснення того чи іншого варіанту;

2. поліпшувати якість рішень в умовах невизначеності;

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

Етап 1. Формулювання завдання.

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

• визначення можливостей збору інформації для експериментування і реальних дій;

• складання переліку подій, що з певною імовірністю можуть відбутися;

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

Етап 2. Побудова "дерева рішень".

Етап 3. Оцінка ймовірностей станів середовища, тобто зіставлення шансів виникнення кожної конкретної події. Слід зазначити, що вказані ймовірності визначаються або на підставі наявної статистики, або експертним шляхом.

Етап 4. Установлення виграшів (чи програшів, як виграшів зі знаком мінус) для кожної можливої комбінації альтернатив (дій) і станів середовища.

Етап 5. Вирішення завдання.

Методика «розділяй і владарюй»

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

Спершу вибирається незалежна змінна, яку поміщують в корінь дерева.

Із вершини будуються вітки, що відповідають всім можливим значенням вибраної незалежної змінної.

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

Таким чином, в кожній підмножині будуть знаходитись об’єкти. У яких значення вибраної незалежної змінної будуть однакові.

Відносно навчальної вибірки Т і множини класів С можливі три ситуації:

• множина Т містить один або декілька об’єктів, що відносяться до одного класу С_r. Тоді дерево рішень для Т – це лист, який визначає (оприділяє) клас С_r;

• множина Т не містить ніодного об’єкта (порожня множина). Тоді це знову ж таки – лист, і клас, який асоціюють з листом, вибирається із іншої множини, відмінної від Т, наприклда із множини, асоціайованої з предком;

• множина Т містить об’єкти, які відносяться до різних класів. В такому випадку потрібно розбити множину Т на деякі підмножини. Для цього вибирається одна із незалежних змінних х_h, яка має два і більше відмінних одне від одного значень с_h², c_h², …, c_hⁿ. Множина Т розбивається на підмножини Т₁, Т₂, …, Т_n, де кожна підмножина Т_і містить всі об’єкти, у яких значення вибраної залежної змінної дорівнює с_h^і. Далі процес продовжується рекурсивно для кожної підмножини до тих пір, поки значення залежної змінної у новостворенії підмножині не буде однаковим (коли об’єкти належать одному класу). В цьому випадку процес даної вітки дерева зупиняється.

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

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

Загальне правило для вибору змінної для розбиття: вибрана змінна повинна розбити множину так, щоб отримати в результаті підмножину, яка складатиметься з об’єктів, які належатимуть одному класу і будуть максимально приближені до цього, тобто щоб кількість об’єктів із інших класів ("домішок") в кожному з цих множин було мінімальним.  Іншою проблемою при побудові дерева є проблема зупинки його розбиття. Методи її вирішення:

1.            Рання зупинка. Використання статистичних методів для оцінки доцільності подальшого розбиття. Заощаджує час побудови моделі, але будує менш точні моделі.

2.            Обмеження глибини дерева. Потрібно зупинити подальшу побудову, якщо розбиття перевищує задане значення глибини дерева.

3.            Розбиття не повинно бути тривіальним, тобто отримані в результаті розбиття вузли повинні містити не менше заданої кількості об'єктів.

4.            Відсікання гілок (знизу вгору). Побудувати дерево, відсікти або замінити піддеревом ті гілки, які призведуть до зростання кількості неправильно класифікованих об'єктів.

Побудувати всі можливі варіанти розбиття і вибрати найкращий є проблематично, якщо є багато незалежних змінних чи можливих класів.