Перегляд вихідного коду сторінки Дерево ухвалення рішень

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

[[Файл:CART tree titanic survivors.png]]

Кожен лист являє собою значення цільової змінної, зміненої в ході руху від кореня по листа. Кожен внутрішній вузол відповідає одній з вхідних змінних. Дерево може бути також «вивчено» поділом вихідних наборів змінних на підмножини, що засновані на тестуванні значень атрибутів. Це процес, який повторюється на кожному з отриманих підмножин. Рекурсія завершується тоді, коли підмножина в вузлі має ті ж значення цільової змінної, таким чином, воно не додає цінності для пророкувань. Процес, що йде «згори донизу», індукція дерев рішень (TDIDT), є прикладом поглинаючого «жадібного» алгоритму, і на сьогодні є найбільш поширеною стратегією дерев рішень для даних, але це не єдина можлива стратегія. В інтелектуальному аналізі даних, дерева рішень можуть бути використані як математичні та обчислювальні методи, щоб допомогти описати, класифікувати і узагальнити набір даних, які можуть бути записані таким чином:
: <math>(x, Y) = (x_1, x_2, x_3\dots x_k, Y)</math>
Залежна змінна Y є цільовою змінною, яку необхідно проаналізувати, класифікувати й узагальнити. Вектор х складається з вхідних змінних <math>x_1</math>, <math>x_2</math>, <math>x_3</math> тощо, які використовуються для виконання цього завдання.

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

Дерево рішень складається з трьох типів вузлів:
* Вузли рішення&nbsp;— зазвичай представлені квадратами
* Імовірнісні вузли&nbsp;— представляються у вигляді кола
* Замикаючі вузли&nbsp;— представляються у вигляді трикутника

[[Файл:Дерево21..svg]]

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

[[Файл:Дерево3-2.svg]]


=== Правила рішень ===
<!-- сюди перенаправляється [[Правила рішень]] -->
Дерево рішень можна [[лінеаризація|лінеаризувати]] в '''правила рішень''',<ref>{{Cite journal | doi = 10.1016/S0020-7373(87)80053-6| title = Simplifying decision trees| journal = International Journal of Man-Machine Studies| volume = 27| issue = 3| pages = 221–234| year = 1987| last1 = Quinlan | first1 = J. R. | citeseerx = 10.1.1.18.4267}}</ref> де результатом є вміст листкових вузлів, а умови на шляху до листка утворюють конюнкцію в умові правила. Загалом правила мають форму:
: ''якщо'' умова1 ''і'' умова2 ''і'' умова3 ''тоді'' результат.

Правила рішень можна генерувати конструюючи [[Навчання асоціативних правил|асоціативні правила]] з цільовою змінною справа. Вони можуть також описувати часові або причинні зв'язки.<ref>K. Karimi and H.J. Hamilton (2011), "[https://arxiv.org/abs/1004.3334 Generation and Interpretation of Temporal Decision Rules]", International Journal of Computer Information Systems and Industrial Management Applications, Volume 3</ref>

== Типологія дерев ==
Дерева рішень, використовувані в [[Data Mining]], бувають двох основних типів:
* Аналіз дерева класифікації, коли прогнозований результат є класом, до якого належать дані;
* Регресійний аналіз дерева, коли прогнозований результат можна розглядати як дійсне число (наприклад, ціна на будинок, або тривалість перебування пацієнта в лікарні).
Згадані вище терміни вперше були використані Брейманом та ін.<ref name="autogenerated1">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.</ref> Перераховані типи мають деякі подібності, а також деякі відмінності, такі, як процедура, що використовується для визначення місця, де розбивати.<ref name=autogenerated1 />
Деякі методи дозволяють побудувати більше одного дерева рішень:
# Дерево рішень «мішок», найбільш раннє дерево рішень, будує кілька дерев рішень, неодноразово інтерполюючи дані із заміною, і дерева голосувань для прогнозу консенсусу;<ref>Breiman, L. (1996). Bagging Predictors. «Machine Learning, 24»: pp. 123–140.</ref>
# Випадковий класифікатор «лісовий» використовує ряд дерев рішень, з метою поліпшення ставки класифікації;
# «Підвищені» дерева можуть бути використані для регресійного типу та класифікації типу проблем.<ref>Friedman, J. H. (1999). Stochastic gradient boosting. Stanford University.</ref>
# «Обертання лісу»&nbsp;— дерева, в яких кожне дерево рішень аналізується першим застосуванням методу головних компонент (PCA) на випадкові підмножини вхідних функцій.<ref>Hastie, T., Tibshirani, R., Friedman, J. H. (2001). The elements of statistical learning: Data mining, inference, and prediction. New York: Springer Verlag.</ref>

== Алгоритми побудови дерева ==
Загальна схема побудови дерева ухвалення рішень за тестовими прикладам виглядає таким чином:
* Вибираємо черговий атрибут <math>Q</math>, поміщаємо його в корінь.
* Для всіх його значень <math>i</math>:
** Залишаємо з тестових прикладів тільки ті, у яких значення атрибута <math>Q</math> дорівнює <math>i</math>
** [[Рекурсія|Рекурсивно]] будуємо дерево в цьому нащадку

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

Є різні способи вибирати черговий атрибут:
* [[ID3 (алгоритм)|Алгоритм ID3]], де вибір атрибута відбувається на підставі приросту інформації ({{lang-en | [[: en: Information gain in decision trees|Gain]]}}), або на підставі [[Коефіцієнт Джині|Коефіцієнту Джині]].
* [[C4.5 (алгоритм)|Алгоритм C4.5]] (поліпшена версія ID3), де вибір атрибута відбувається на підставі нормалізованого приросту інформації ({{lang-en | [[: en: Information gain ratio|Gain Ratio]]}}).
* Алгоритм {{нп|CART (алгоритм)|CART|ru|CART (алгоритм)}} і його модифікації&nbsp;— IndCART, DB-CART.
* Автоматичний детектор взаємодії Хі-квадрат (CHAID). Виконує багаторівневий поділ при розрахунку класифікації дерев;<ref>{{Cite news|url=https://www.jstor.org/stable/10.2307/2986296?origin=crossref|title=An Exploratory Technique for Investigating Large Quantities of Categorical Data|first1=G. V.|last1=Kass|date=1980|pages=119|language=|work=[[Applied Statistics]]|volume=29|doi=10.2307/2986296.|pmc=|pmid=|issue=2|issn=|access-date=2024-12-20}}</ref>
* MARS: розширює дерева рішень для поліпшення обробки цифрових даних.

На практиці в результаті роботи цих алгоритмів часто виходять занадто деталізовані дерева, які при їх подальшому застосуванні дають багато помилок. Це пов'язано з явищем [[перенавчання]]. Для скорочення дерев використовується відсікання гілок ({{lang-en | [[: en: Pruning (decision trees)|pruning]]}}).

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

Одне з питань, яке виникає в алгоритмі дерева рішень&nbsp;— це оптимальний розмір кінцевого дерева. Так, невелике дерево може не охопити ту чи іншу важливу інформацію щодо вибіркового простору. Тим не менше, важко сказати, коли алгоритм повинен зупинитися, тому що неможливо спрогнозувати, додавання якого вузла дозволить значно зменшити помилку. Ця проблема відома як «ефект горизонту». Тим не менш, загальна стратегія обмеження дерева зберігається, тобто видалення вузлів реалізується в разі, якщо вони не дають додаткової інформації<ref>Fast, Bottom-Up Decision Tree Pruning Algorithm</ref>.

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

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

== Приклад завдання ==
Припустімо, що нас цікавить, чи виграє наша улюблена футбольна команда наступний матч.
Ми знаємо, що це залежить від ряду параметрів; перераховувати їх всі&nbsp;— завдання безнадійне, тому обмежимося основними:
* Чи вище перебуває суперник по турнірній таблиці;
* Чи вдома проходить матч;
* Чи пропускає матч хтось із лідерів команди;
* Чи йде дощ.
У нас є деяка статистика на цей рахунок:
{| class="wikitable"
|-
! Суперники !! Граємо !!Лідери !! Дощ !! Перемога
|-
| Вище || Вдома || На місці || Так || Ні
|-
| Вище || Вдома || На місці || Ні || Так
|-
| Вище || Вдома || Пропускають || Ні || Ні
|-
| Нижче || Вдома || Пропускають || Ні || Так
|-
| Нижче || У гостях || Пропускають || Ні || Ні
|-
| Нижче || Вдома || Пропускають || Так || Так
|-
| Вище || У гостях || На місці || Так || Ні
|-
| Нижче || У гостях || На місці || Ні || ???
|}

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

== Див. також ==
* [[Random forest]]&nbsp;— класифікатор, заснований на застосуванні комітетів з вирішальних дерев
* [[Перенавчання]]
* [[Цикл прийняття рішень]]
* [[Таблиця рішень|Таблиця ухвалення рішень]]

== Примітки ==
{{Примітки | 2}}

== Посилання ==
* [Http://logic.pdmi.ras.ru/~sergey/teaching/ml/notes-01-dectrees.pdf Конспект лекції по деревах ухвалення рішень] {{Webarchive|url=https://web.archive.org/web/20220402113852/https://logic.pdmi.ras.ru/~sergey/teaching/ml/notes-01-dectrees.pdf |date=2 квітня 2022 }}
* [Http://www.basegroup.ru/library/analysis/tree/ Алгоритми побудови дерев рішень] {{Webarchive|url=https://web.archive.org/web/20150315044731/http://www.basegroup.ru/library/analysis/tree/ |date=15 березня 2015 }} (BaseGroup Labs)
* [https://web.archive.org/web/20070502112247/http://www.cs.ubc.ca/nest/lci/CIspace/Version4/dTree/ Decision trees applet provides several sample data sets of examples to learn and classify]

== Література ==
* {{Книга
|Частина = Глава 9.
|Заголовок = Бизнес-аналитика: от данных к знаниям(+CD): Учебное пособие. 2-е изд.
|Автор = Паклин Н.Б., Орешков В.И.
|Посилання = 
|ISBN = 978-5-459-00717-6
|Сторінки = 428-472
|год = 2013
|Місце =  СПб
|Видавництво = Питер
}}
* {{Книга
| Частина = Глава 10. Обмеження потужності алгоритмів: Дерева прийняття рішення
| Заголовок = Алгоритми: введення в розробку й аналіз
| Оригінал = Introduction to The Design and Analysis of Aigorithms
| Автор = Ананій В. Левітін
| Посилання =
| ISBN = 0-201-74395-7
| Сторінки = 409-417
| Рік = 2006
| Місце = М.
| Видавництво = Вільямс
}}

{{перекласти|en}}

[[Категорія:Дерева прийняття рішень| *]]
[[Категорія:Аналіз даних]]