Дерево ухвалення рішень

У Вікіпедії є статті про інші значення цього терміна: Рішення.

Дерево ухвалення рішень (також можуть називатися деревами класифікацій або регресійними деревами) — використовується в галузі статистики та аналізу даних для прогнозних моделей. Структура дерева містить такі елементи: «листя» і «гілки». На ребрах («гілках») дерева ухвалення рішення записані атрибути, від яких залежить цільова функція, в «листі» записані значення цільової функції, а в інших вузлах — атрибути, за якими розрізняються випадки. Щоб класифікувати новий випадок, треба спуститися по дереву до листа і видати відповідне значення. Подібні дерева рішень широко використовуються в інтелектуальному аналізі даних. Мета полягає в тому, щоб створити модель, яка прогнозує значення цільової змінної на основі декількох змінних на вході.

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

(x,Y)=(x_{1},x_{2},x_{3}\dots x_{k},Y)

Залежна змінна Y є цільовою змінною, яку необхідно проаналізувати, класифікувати й узагальнити. Вектор х складається з вхідних змінних $x_{1}$ , $x_{2}$ , $x_{3}$ тощо, які використовуються для виконання цього завдання.

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

В аналізі рішень «дерево рішень» використовуються як візуальний і аналітичний інструмент підтримки ухвалення рішень, де розраховуються очікувані значення (або очікувана корисність) конкуруючих альтернатив.

Дерево рішень складається з трьох типів вузлів:

Вузли рішення — зазвичай представлені квадратами
Імовірнісні вузли — представляються у вигляді кола
Замикаючі вузли — представляються у вигляді трикутника

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

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

Дерево рішень можна лінеаризувати в правила рішень,^[1] де результатом є вміст листкових вузлів, а умови на шляху до листка утворюють конюнкцію в умові правила. Загалом правила мають форму:

якщо умова1 і умова2 і умова3 тоді результат.

Правила рішень можна генерувати конструюючи асоціативні правила з цільовою змінною справа. Вони можуть також описувати часові або причинні зв'язки.^[2]

Типологія дерев ред.

Дерева рішень, використовувані в Data Mining, бувають двох основних типів:

Аналіз дерева класифікації, коли прогнозований результат є класом, до якого належать дані;
Регресійний аналіз дерева, коли прогнозований результат можна розглядати як дійсне число (наприклад, ціна на будинок, або тривалість перебування пацієнта в лікарні).

Згадані вище терміни вперше були використані Брейманом та ін.^[3] Перераховані типи мають деякі подібності, а також деякі відмінності, такі, як процедура, що використовується для визначення місця, де розбивати.^[3] Деякі методи дозволяють побудувати більше одного дерева рішень:

Дерево рішень «мішок», найбільш раннє дерево рішень, будує кілька дерев рішень, неодноразово інтерполюючи дані із заміною, і дерева голосувань для прогнозу консенсусу;^[4]
Випадковий класифікатор «лісовий» використовує ряд дерев рішень, з метою поліпшення ставки класифікації;
«Підвищені» дерева можуть бути використані для регресійного типу та класифікації типу проблем.^[5]
«Обертання лісу» — дерева, в яких кожне дерево рішень аналізується першим застосуванням методу головних компонент (PCA) на випадкові підмножини вхідних функцій.^[6]

Алгоритми побудови дерева ред.

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

Вибираємо черговий атрибут $Q$ , поміщаємо його в корінь.
Для всіх його значень $i$ :
- Залишаємо з тестових прикладів тільки ті, у яких значення атрибута $Q$ дорівнює $i$
- Рекурсивно будуємо дерево в цьому нащадку

Основне питання: як вибирати черговий атрибут?

Є різні способи вибирати черговий атрибут:

Алгоритм ID3, де вибір атрибута відбувається на підставі приросту інформації (англ. Gain), або на підставі Коефіцієнту Джині.
Алгоритм C4.5 (поліпшена версія ID3), де вибір атрибута відбувається на підставі нормалізованого приросту інформації (англ. Gain Ratio).
Алгоритм CART^[ru] і його модифікації — IndCART, DB-CART.
Автоматичний детектор взаємодії Хі-квадрат (CHAID). Виконує багаторівневий поділ при розрахунку класифікації дерев;^[7]
MARS: розширює дерева рішень для поліпшення обробки цифрових даних.

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

Регулювання глибини дерева ред.

Регулювання глибини дерева — це техніка, яка дозволяє зменшувати розмір дерева рішень, видаляючи ділянки дерева, які мають маленьку вагу.

Одне з питань, яке виникає в алгоритмі дерева рішень — це оптимальний розмір кінцевого дерева. Так, невелике дерево може не охопити ту чи іншу важливу інформацію щодо вибіркового простору. Тим не менше, важко сказати, коли алгоритм повинен зупинитися, тому що неможливо спрогнозувати, додавання якого вузла дозволить значно зменшити помилку. Ця проблема відома як «ефект горизонту». Тим не менш, загальна стратегія обмеження дерева зберігається, тобто видалення вузлів реалізується в разі, якщо вони не дають додаткової інформації^[8].

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

Методи регулювання ред.

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

Приклад завдання ред.

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

Чи вище перебуває суперник по турнірній таблиці;
Чи вдома проходить матч;
Чи пропускає матч хтось із лідерів команди;
Чи йде дощ.

У нас є деяка статистика на цей рахунок:

Суперники	Граємо	Лідери	Дощ	Перемога
Вище	Вдома	На місці	Так	Ні
Вище	Вдома	На місці	Ні	Так
Вище	Вдома	Пропускають	Ні	Ні
Нижче	Вдома	Пропускають	Ні	Так
Нижче	У гостях	Пропускають	Ні	Ні
Нижче	Вдома	Пропускають	Так	Так
Вище	У гостях	На місці	Так	Ні
Нижче	У гостях	На місці	Ні	???

Хочеться зрозуміти, чи виграє наша команда в черговій грі.

Див. також ред.

Random forest — класифікатор, заснований на застосуванні комітетів з вирішальних дерев
Перенавчання
Цикл прийняття рішень
Таблиця ухвалення рішень^[en]

Примітки ред.

↑ Quinlan, J. R. (1987). Simplifying decision trees. International Journal of Man-Machine Studies. 27 (3): 221—234. CiteSeerX 10.1.1.18.4267. doi:10.1016/S0020-7373(87)80053-6.
↑ K. Karimi and H.J. Hamilton (2011), "Generation and Interpretation of Temporal Decision Rules", International Journal of Computer Information Systems and Industrial Management Applications, Volume 3
↑ ^а ^б Breiman, Leo; Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. ISBN 978-0-412-04841-8.
↑ Breiman, L. (1996). Bagging Predictors. «Machine Learning, 24»: pp. 123–140.
↑ Friedman, J. H. (1999). Stochastic gradient boosting. Stanford University.
↑ Hastie, T., Tibshirani, R., Friedman, J. H. (2001). The elements of statistical learning: Data mining, inference, and prediction. New York: Springer Verlag.
↑ Kass, G. V. (1980). «An exploratory technique for investigating large quantities of categorical data». Applied Statistics 29 (2): 119–127. DOI: 10.2307/2986296. JSTOR 2986296.
↑ Fast, Bottom-Up Decision Tree Pruning Algorithm

Посилання ред.

Конспект лекції по деревах ухвалення рішень [Архівовано 2 квітня 2022 у Wayback Machine.]
Алгоритми побудови дерев рішень [Архівовано 15 березня 2015 у Wayback Machine.] (BaseGroup Labs)
Decision trees applet provides several sample data sets of examples to learn and classify

Література ред.

Паклин Н.Б., Орешков В.И. Глава 9. // Бизнес-аналитика: от данных к знаниям(+CD): Учебное пособие. 2-е изд. — ISBN 978-5-459-00717-6.
Ананій В. Левітін. Глава 10. Обмеження потужності алгоритмів: Дерева прийняття рішення // Алгоритми: введення в розробку й аналіз = Introduction to The Design and Analysis of Aigorithms. — ISBN 0-201-74395-7.

[1] Quinlan, J. R. (1987). Simplifying decision trees. International Journal of Man-Machine Studies. 27 (3): 221—234. CiteSeerX 10.1.1.18.4267. doi:10.1016/S0020-7373(87)80053-6.

[2] K. Karimi and H.J. Hamilton (2011), "Generation and Interpretation of Temporal Decision Rules", International Journal of Computer Information Systems and Industrial Management Applications, Volume 3

[autogenerated1-3] а ^б Breiman, Leo; Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. ISBN 978-0-412-04841-8.

[4] Breiman, L. (1996). Bagging Predictors. «Machine Learning, 24»: pp. 123–140.

[5] Friedman, J. H. (1999). Stochastic gradient boosting. Stanford University.

[6] Hastie, T., Tibshirani, R., Friedman, J. H. (2001). The elements of statistical learning: Data mining, inference, and prediction. New York: Springer Verlag.

[7] Kass, G. V. (1980). «An exploratory technique for investigating large quantities of categorical data». Applied Statistics 29 (2): 119–127. DOI: 10.2307/2986296. JSTOR 2986296.

[8] Fast, Bottom-Up Decision Tree Pruning Algorithm

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]