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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Побудова дерева рішень

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

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

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

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

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

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

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

Процес прийняття управлінських рішень за допомогою дерева рішень у загальному випадку припускає виконання п'яти етапів:

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

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

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

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

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

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

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

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

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

Розглянуте завдання класифікації відноситься до стратегії навчання з учителем. Спочатку збирається статистична інформація про об'єкти, для яких вже відомо їх клас. Набір цих об'єктів називається навчальною вибіркою. Далі до цих даних застосовується алгоритм навчання, в результаті чого виходить навчений класифікатор або модель. Тобто модель = алгоритм + навчальна вибірка.

Перед тим як застосовувати модель на реальних даних, як правило, проводять тестування її продуктивності. Найбільш поширеним методом тестування є так звана перехресна перевірка (cross-validation). Її суть полягає в тому, що навчальна вибірка поділяється на n частин. Класифікатор навчається на (n-1) частинах, а одну частину використовують безпосередньо для перевірки результату. Ця процедура повторюється n разів, а результатом вважається середнє арифметичне результатів окремих тестів.

Алгоритми конструювання дерев рішень складаються з етапів "побудови" або "створення" дерева (tree building) і "скорочення" дерева (tree pruning). У ході створення дерева вирішуються питання вибору критерію розгалуження і зупинки навчання (якщо це передбачено алгоритмом). В ході етапу скорочення дерева вирішується питання відсікання деяких його гілок.

Критерій розгалуження

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

Розмір дерева

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

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

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

Тут існує дві можливі стратегії. Перша полягає в нарощуванні дерева до певного розміру відповідно до параметрів, що задано користувачем. Визначення цих параметрів може ґрунтуватися на досвіді та інтуїції аналітика, а також на деяких "діагностичних повідомленнях" системи, яка конструює дерево рішень.

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

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

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

Зупинка побудови дерева

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

Зупинка - це момент у процесі побудови дерева, коли слід припинити подальше розгалуження.

Один з варіантів правил зупинки - "рання зупинка" (prepruning), вона визначає доцільність розділення вузла. Перевага використання такого варіанту - зменшення часу на навчання моделі. Однак тут виникає ризик зменшення точності класифікації. Тому, рекомендується замість «зупинки» використовувати «відсікання».

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

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

Скорочення дерева або відсікання гілок

Вирішенням проблеми занадто гіллястого дерева є його скорочення шляхом відсікання (pruning) деяких гілок.

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

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

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

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

Алгоритми побудови дерев рішень

Алгоритми побудови дерев рішень розрізняються наступними характеристиками:

• Вид розгалуження - бінарне (binary), множинне (multi-way).
• Критерії розгалуження - ентропія, Gini, інші.
• Можливість обробки пропущених значень.
• Процедура скорочення гілок або відсікання.
• Можливості витягування правил з дерев.

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

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

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

3. Застосування методу дерева рішень

• Банківська справа – оцінка кредитоспроможності.
• Промисловість – контроль за якістю продукції (виявлення дефектів), випробування (якість зварювання).
• Медицина – діагностика захворювань.
• Молекулярна біологія – аналіз будови сполучень.
• Програмування. Будь-яка програма або веб-сторінка побудовані за принципом алгоритму і руху від цілого до безлічі.

Приклад використання алгоритму в банківській сфері

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

• вік;
• рівень доходу;
• утриманці , сімейний стан;
• кредити в інших організаціях;
• наявність рухомого і нерухомого майна.

Тепер по кожній з ключових гілок необхідно скласти приблизний план можливих дій.

Почнемо з віку. Більше 21? Відповідь "так" або "ні". "Ні" відразу приводить нас до нуля. Після відповіді "Д а" рухаємося до наступного питання.

Рівень доходу вище 5000 грн в місяць? "Ні" - це відразу нуль "Так" - переходимо до наступній гілці.

Сімейний стан . У цьому розділі можуть з'являтися додаткові отв етвления , які будуть важливими для нашого рішення. Скільки чоловік в сім'ї? Скільки з них утриманці , який дохід у чоловіка / дружини. Якщо відповіді нас задовольнили, можна переходити до наступного сектору.

Кредити в інших організаціях. Тут раціонально виділити: яку суму брали, як швидко віддали, чи є борги?

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

Приклад використання алгоритму в медицині

Розглянемо типову ситуацію. До лікаря прийшов на огляд пацієнт з кашлем. При постановці діагнозу лікар оцінює людини за декількома параметрами:

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

Відповідь на кожне з цих питань призведе до доктора постановці правильного діагнозу

4. Переваги та недоліки застосування методу дерева рішень

Переваги дерев рішень:

1. Інтуїтивність дерев рішень. Класифікаційна модель, що представлена у вигляді дерева рішень, є інтуїтивною і спрощує розуміння розв'язуваної задачі. Результат роботи алгоритмів конструювання дерев рішень легко інтерпретується користувачем. Ця властивість дерев рішень не стільки важлива при віднесенні нового об'єкта до певного класу, але й корисна при інтерпретації моделі класифікації в цілому. Дерево рішень дозволяє зрозуміти і пояснити, чому конкретний об'єкт відноситься до того чи іншого класу.

2. Можливість формувати правила з бази даних природною мовою. Приклад правила: Якщо Вік> 35 і Дохід> 2000, тоді видати кредит.

3. Створення класифікаційних моделей в тих областях, де аналітику досить складно формалізувати знання.

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

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

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

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

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

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

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

Недоліки дерев рішень:

1. Вимагає значних витрат часу на проведення дослідження.

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

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

5. Дерева рішень в R