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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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