Просмотр кода страницы Обучение дерева решений

'''Обучение дерева решений''' использует [[дерево решений]] (как {{не переведено 5|Прогнозное моделирование|предиктивную модель||Predictive modelling}}), чтобы перейти от наблюдений над объектами (представленными в ветвях) к заключениям о целевых значениях объектов (представленных в листьях). Это обучение является одним из подходов моделирования предсказаний, используемых в [[Статистика|статистике]], [[data mining|интеллектуальном анализе данных]] и [[Машинное обучение|машинном обучении]]. Модели деревьев, в которых целевая переменная может принимать дискретный набор значений, называются '''деревьями классификации'''. В этих структурах деревьев  [[Дерево (структура данных)|листья]] представляют метки классов, а ветки представляют [[Конъюнкция|конъюнкции]] признаков, которые ведут в эти метки классов. Деревья решений, в которых целевая переменная может принимать непрерывные значения (обычно, [[Вещественное число|вещественные числа]]) называются '''деревьями регрессии'''.

В анализе решений может быть использовано дерево решений для визуального и явного представления [[принятие решений|принятия решений]]. При [[data mining|интеллектуальном анализе данных]] дерево решений описывает данные (но результирующее дерево классификации может быть входом для [[Принятие решений|принятия решений]]). Эта страница имеет дело с деревьями решений при [[data mining|интеллектуальном анализе данных]].

== Обсуждение ==
[[Файл:CART tree titanic survivors (RU).svg|thumb|240x240px|
Дерево, показывающее выживаемость пассажиров [[Титаник]]а ("родств." — это число семейных пар или родственников на борту).
Фигуры под листами показывают вероятность выживания и процент от полного числа.
Итог: Ваш шанс выжить был бы хорошим, если бы вы были (i) женщиной или (ii) мальчиком до 9.5 лет с менее чем 2.5 родственниками.]]
Обучение дерева решений — это метод, обычно используемый в интеллектуальном анализе данных{{sfn|Rokach, Maimon|2008}}. Целью является создание модели, которая предсказывает значение целевой переменной, основываясь на некоторых входных переменных. Пример показан на диаграмме справа. Каждый [[Дерево (структура данных)|внутренний узел]] соответствует одной из входных переменных. Есть рёбра к потомкам для каждого возможного значения этой входной переменной.  Каждый лист представляет значение целевой переменной, которое определяется значениями входных переменных от корня до листа.

Дерево решений является простым представлением для примеров классификации. Для данного раздела предположим, что все входные [[Признак (машинное обучение)|признаки]] представлены конечными дискретными множествами и имеется единственный целевой признак, называемый «классификацией». Каждый элемент классификации называется ''классом''.
Дерево решений или дерево классификации — это дерево, в котором каждый внутренний (нелистовой) узел помечен входным признаком. Дуги, исходящие из узла, помеченного входным параметром, помечаются всеми возможными значениями выходного признака или дуга ведёт в подчинённый узел решения с другим входным признаком. Каждый лист дерева помечается классом или распределением вероятности по классам.

Дерево может быть «обучено» путём расщепления [[Множество|множества]] на подмножества, основываясь на проверку значений атрибутов. Этот процесс, повторяющийся на каждом полученном подмножестве рекурсивно, называется {{не переведено 5|Рекурсивное секционирование|рекурсивным секционированием||recursive partitioning}}.
[[Рекурсия]] прекращается, когда подмножество в узле имеет одно и то же значение целевой переменной или когда разбиение не добавляет значения в предсказания. Этот процесс ''индукции сверху вниз деревьев решений'' ({{lang-en|top-down induction of decision trees}}, TDIDT){{sfn|Quinlan|1986|с=81-106}} является примером  [[Жадный алгоритм|жадного алгоритма]], и служит наиболее часто применяемой стратегией обучения деревьев решений из данных.

При [[data mining|интеллектуальном  анализе данных]] деревья решений могут быть описаны также как комбинация математических и вычислительных техник с целью описания, категоризации и обобщения заданного набора данных.

Данные приходят в виде записей вида:

:<math>(\textbf{x},Y)=(x_1, x_2, x_3, ..., x_k, Y)</math>

Зависимая переменная Y является целевой переменной, которую мы пытаемся понять, классифицировать или обобщить. Вектор '''x''' составлен из признаков x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub> и т.д., которые используются для задачи.

[[Файл:Cart tree kyphosis (RU).svg|thumb|400px|
alt=Три различных представления дерева регрессии данных кифоза|
Пример дерева, который оценивает вероятность [[кифоз]]а после операции, в зависимости от возраста пациента и номера позвонка, на котором была проведена операция.
Одно и то же дерево показано тремя различными способами.
'''Сверху''' Цветные листья показывают вероятность [[кифоз]]а после операции и процент пациентов на листе.
'''Середина''' Дерево как псевдотрёхмерная диаграмма.
'''Внизу''' Вид той же диаграммы сверху.
Вероятность кифоза после операции тем больше, чем темнее область.
]]

== Типы деревьев решений ==
Деревья решений используются при [[data mining|интеллектуальном анализе данных]] и бывают двух основных типов:

* Анализ '''{{не переведено 5|Дерево классификации|дерева классификации||Classification tree}}''', когда предсказываемый выход является классом, которому данные принадлежат.
* Анализ '''дерева регрессии''', когда предсказываемый выход может считаться вещественным числом (например, цена дома или продолжительность нахождения пациента в больнице).

Термин анализ по '''дереву классификации и регрессии''' ({{lang-en|Classification And Regression Tree}}, CART) является обобщающим термином и он используется для обозначения двух упомянутых выше процедур, первую из которых ввели [[Брейман, Лео|Брейман]] с соавторами в 1984{{sfn|Breiman, Friedman, Olshen, Stone|1984}}. Деревья, используемые для регрессии, и деревья, используемые для классификации, имеют некоторую схожесть, однако имеют и отличия, такие как процедура, используемая для определения места расщепления{{sfn|Breiman, Friedman, Olshen, Stone|1984}}.

Некоторые техники, часто называемые методами ''сборки'', строят более одного дерева решений:
* '''{{не переведено 5|Градиентный бустинг|Расширяемые деревья||Gradient boosted trees}}''' ({{lang-en|Boosted Trees}}) строят шаг за шагом сборку путём тренировки каждого нового экземпляра, делая упор на тренировку ранее не попадающих в модель экземпляров. Типичным примером является [[AdaBoost]]. Это может быть использовано как для задач регрессионного типа, так и задач классификации {{sfn|Friedman|1999}}{{sfn|Hastie, Tibshirani, Friedman|2001}}.
* '''[[Бэггинг]]''' деревьев решений, ранний метод сборки, строящий несколько деревьев решений путём повторной выборки тренировочных данных с заменой и голосованием за деревья для согласования предсказания{{sfn|Breiman|1996|с=123–140}}.
** Классификатор на основе '''[[random forest|случайного леса]]''' является специфичным видом [[бэггинг]]а
* '''Ротационный лес''' — подход, в котором каждое дерево решений сначала тренируется применением [[Метод главных компонент|метода главных компонент]] ({{lang-en|Principal Component Analysis}}, PCA) на случайном подмножестве входных признаков{{sfn|Rodriguez, Kuncheva, Alonso|2006|с=1619–1630}}.

Специальным случаем деревьев решений является {{не переведено 5|список решений|||Decision list}}{{sfn|Rivest|1987|с=229–246}}, который является односторонним деревом решений, так что любой внутренний узел имеет в точности 1 лист и в точности 1 внутренний узел в качестве наследника (за исключением самого нижнего узла, единственным наследником которого является один лист). Хотя эти списки менее выразительны, их легче понять, чем общие деревья решений, ввиду их разреженности, что разрешает применение методов обучения, не являющихся жадными{{sfn|Letham, Rudin, McCormick, Madigan|2015|с=1350–1371}}, а также позволяют наложение монотонных ограничений{{sfn|Wang, Rudin|2015}}.

'''Обучение дерева решений''' является построением дерева решений из помеченных классами тренировочных кортежей. Дерево решений является структурой, подобной блок-схеме, в которой каждый внутренний (нелистовой) узел означает тест атрибута, каждая ветвь представляет результат теста, а каждый лист (терминальный узел) содержит метку класса. Верхняя вершина является корневым узлом.

Есть много алгоритмов деревьев решений. Наиболее заметные из них:

* [[ID3 (алгоритм)|ID3]] ({{lang-en|Iterative Dichotomiser 3}})
* [[C4.5]] (преемник алгоритма ID3)
* [[CART (алгоритм)|Классификация и регрессия построением дерева решений.]] ({{lang-en|Classification And Regression Tree}}, CART)
* {{не переведено 5|Автоматическое выявление зависимостей по критерию хи-квадрат|||CHAID}} ({{lang-en|CHi-squared Automatic Interaction Detector}}, CHAID). Осуществляет многоуровневое расщепление при вычислении деревьев классификации{{sfn|Kass|1980|с=119–127}}.
* {{не переведено 5|Многомерные адаптивные регрессионные сплайны|||Multivariate adaptive regression splines}} ({{lang-en|Multivariate adaptive regression splines}}, MARS): расширяет деревья решений для лучшей обработки количественных данных.
* Деревья условного вывода ({{lang-en|Conditional Inference Trees}}). Подход на основе статистики, который использует непараметрические тесты в качестве критерия расщепления, скорректированные для многократного тестирования во избежание переобучения. Этот подход приводит к выбору несмещённого предсказателя и не требует обрезки{{sfn|Hothorn, Hornik, Zeileis|2006|с=651–674}}{{sfn|Strobl, Malley, Tutz|2009|с=323–348}}.

ID3 и CART были разработаны независимо и примерно в одно и то же время (между 1970 и 1980), однако используют близкие подходы для обучения дерева решений из тренировочных кортежей.

== Метрики ==
Алгоритмы построения деревья решений обычно работают сверху вниз путём выбора переменной на каждом шаге, которая лучшим образом разбивает множество элементов{{sfn|Rokach, Maimon|2005|с=476–487}}. Разные алгоритмы используют различные метрики для измерения «лучшего» решения.  Они обычно измеряют однородность целевой переменной на подмножествах. Некоторые примеры даны ниже. Эти метрики применяются к каждому подмножеству и получающиеся значения комбинируются (например, вычисляется среднее) для получения меры качества разбиения.

=== Примесь (критерий) Джини ===
{{Не путать|Коэффициент Джини}}
Используемый в алгоритме деревьев классификации и регрессии ({{lang-en|classification and regression tree}}, CART) критерий Джини является мерой, насколько часто случайно выбранный элемент из набора неверно помечается, если он случайным образом помечается согласно распределению меток в подмножестве. Критерий Джини может быть вычислен путём суммирования вероятности <math>p_i</math> элемента с выбранной меткой <math>i</math>, умноженной на вероятность <math>\sum_{k \ne i} p_k=1-p_i</math> ошибки категоризации этого элемента. Критерий принимает минимум (нуль), когда все случаи в узле попадают в одну целевую категорию.

Для вычисления критерия Джини для набора элементов с <math>J</math> классами, предположим, что <math>i \in \{1, 2, ...,J\}</math>, и пусть <math>p_i</math> будет долей элементов, помеченных классом <math>i</math> в наборе.

:<math>\operatorname{I}_{G}(p)=\sum_{i=1}^J p_i \sum_{k\neq i} p_k
=\sum_{i=1}^{J} p_i (1-p_i)
=\sum_{i=1}^{J} (p_i - {p_i}^2)
=\sum_{i=1}^J p_i - \sum_{i=1}^{J} {p_i}^2
=1 - \sum^{J}_{i=1} {p_i}^{2} </math>

=== Информационный выигрыш ===
{{Основная статья|Информационный выигрыш в деревьях решений}}
В алгоритмах генерации деревьев [[ID3 (алгоритм)|ID3]], [[C4.5]] и C5.0. используется [[Расстояние Кульбака — Лейблера|Информационный выигрыш]], который основывается на понятии [[Информационная энтропия|энтропии]] и [[Собственная информация|объёма информации]] из [[Теория информации|теории информации]].

Энтропия определяется следующим образом

:<math>\Eta(T)=\operatorname{I}_{E}\left(p_1, p_2, ..., p_J\right)
=- \sum^{J}_{i=1} {p_i \log_2 p_i}</math>,
где <math>p_1, p_2, ...</math> являются долями, в сумме дающими 1, которые представляют процент каждого класса, полученный от разбиения в дереве{{sfn|Witten, Frank, Hall|2011|с=102–103}}.

:<math display="block"> \overbrace{IG(T,a)}^\text{Information Gain}
= \overbrace{\Eta(T)}^\text{Entropy (parent)}
- \overbrace{\Eta(T|a)}^\text{Weighted Sum of Entropy (Children)} </math><math>=-\sum_{i=1}^{J}p_i\log_2{p_i} - \sum_{a}{p(a)\sum_{i=1}^{J}-\Pr(i|a)\log_2{\Pr(i|a)}}</math>

В формуле
* Information Gain=Информационный выигрыш
* Entropy (parent)=Энтропия (родитель)
* Weighted Sum of Entropy (Children)=Взвешенная сумма энтропии (наследники)

Информационный выигрыш используется для принятия решения, какой признак использовать для расщепления на каждом шаге построения дерева. Простота является лучшим выбором, так что мы хотим сохранять дерево небольшим. Чтобы это сделать, на каждом шаге нам следует выбрать расщепление, которое приводит к простейшим узлам-наследникам. Обычно используемая мера простоты называется ''информацией'', которая измеряется в [[бит]]ах. Для каждого узла дерева значение ''информации'' «представляет ожидаемое количество, которая нужна для определения, должен ли новый объект классифицирован как да или нет, если дано, что пример достигает этого узла»"{{sfn|Witten, Frank, Hall|2011|с=102–103}}.

Рассмотрим пример набора данных с четырьмя атрибутами: ''погода'' (солнечно, облачно, дождь), ''температура'' (жарко, мягкая погода, холодно), ''влажность'' (высокая, нормальная) и ''ветер'' (есть, нет) с бинарной целевой переменной (да или нет) ''игра'' и 14 точками данных. Для построения дерева решений по этим данным нам нужно сравнить информационный выигрыш каждого из четырёх деревьев, на которые расщепляется согласно одному из четырёх признаков. Расщепление с максимальным информационным выигрышем будет взято в качестве первого расщепления и процесс продолжается, пока все наследники не станут простыми или пока информационный выигрыш не станет нулём.

Расщепление, использующее признак ''ветер'', приводит к двум узлам-наследникам, один узел для признака ''ветер'' со значением '''есть''' и один со значением '''нет'''. В этом наборе данных имеется шесть точек данных со значением '''есть''' для ''ветер'', три имеют для целевого значения ''игра'' значение '''да''' и три имеют значение '''нет'''. Восемь оставшихся точек данных для параметра ''ветер'' со значением '''нет''' содержат два '''нет''' и шесть '''да'''. Информация ''ветер''=да узла вычисляется с помощью уравнения для энтропии выше. Поскольку имеется равное число '''да''' и '''нет''' в этом узле, мы имеем

:<math> I_{E}([3,3])=-\frac 3 6\log^{}_2 \frac 3 6 - \frac 3 6\log^{}_2 \frac 3 6=-\frac 1 2\log^{}_2 \frac 1 2 - \frac 1 2\log^{}_2 \frac 1 2=1 </math>

Для узла с ''ветер''=нет имелось восемь точек данных, шесть с целевым значением '''да''' и два с '''нет'''. Таким образом, мы имеем

:<math> I_{E}([6,2])=-\frac 6 8\log^{}_2 \frac 6 8 - \frac 2 8\log^{}_2 \frac 2 8=-\frac 3 4\log^{}_2 \frac 3 4 - \frac 1 4\log^{}_2 \frac 1 4=0,8112781 </math>

Чтобы найти ''информацию'' разбиения, вычислим взвешенное среднее этих двух чисел на основе количества наблюдений, попавших в каждый узел.

:<math>I_{E}([3,3],[6,2])=I_{E}</math> (ветер - да или нет) <math>= \frac 6 {14} \cdot 1 + \frac 8 {14} \cdot 0,8112781=0,8921589 </math>

Чтобы найти информационный выигрыш расщепления с помощью ''ветер'', мы должны вычислить ''информацию'' в данных до расщепления. Исходные данные содержали девять '''да''' и пять '''нет'''.

:<math> I_{E}([9,5])=-\frac 9 {14}\log^{}_2 \frac 9 {14} - \frac 5 {14}\log_2 \frac 5 {14}=0,940286 </math>

Теперь мы можем вычислить информационный выигрыш, получаемый расщеплением по признаку ''ветер''.

:<math>IG</math> (ветер) <math>= I_{E}([9,5]) - I_{E}([3,3],[6,2])=0,940286 - 0,8921589=0,0481271 </math>

Чтобы построить дерево, нужно вычислить информационный выигрыш каждого возможного первого расщепления. Лучшее первое расщепление, это то, которое даёт наибольший информационный выигрыш. Этот процесс повторяется для каждого узла (со смешанными признаками), пока дерево не будет построено. Этот пример заимствован из статьи Виттена, Франка и Холла{{sfn|Witten, Frank, Hall|2011|с=102–103}}.

=== Понижение дисперсии ===
Представленное в CART{{sfn|Breiman, Friedman, Olshen, Stone|1984}} понижение дисперсии часто используется в случаях, когда целевая переменная непрерывна (дерево регрессии), это означает, что использование многих других метрик требовало бы дискретизации перед применением. Понижение дисперсии узла {{mvar|N}} определяется как общее сокращение дисперсии целевой переменной {{mvar|x}} как следствие расщепления в этом узле:

:<math>
I_{V}(N)=\frac{1}{|S|^2}\sum_{i\in S} \sum_{j\in S} \frac{1}{2}(x_i - x_j)^2 - \left(\frac{1}{|S_t|^2}\sum_{i\in S_t} \sum_{j\in S_t} \frac{1}{2}(x_i - x_j)^2 + \frac{1}{|S_f|^2}\sum_{i\in S_f} \sum_{j\in S_f} \frac{1}{2}(x_i - x_j)^2\right)
</math>,

где <math>S</math>, <math>S_t</math> и <math>S_f</math> являются множеством индексов до расщепления, множеством индексов, для которых тест даёт true и множеством индексов, для которых тест даёт false соответственно. Каждое из слагаемых выше является оценкой [[Дисперсия случайной величины|величины отклонения]], хотя и записанной без прямой ссылки на среднее.

== Применение ==

=== Преимущества ===
Среди других методов анализа данных деревья решений имеют ряд преимуществ:
* '''Легки для понимания и интерпретации.''' Люди способны понять модели деревьев решений после краткого объяснения. Деревья можно изобразить графически таким образом, что их легко интерпретировать, не будучи экспертом{{sfn|Gareth, Witten, Hastie, Tibshirani|2015|с=315}}.
* '''Способны работать как с числовыми, так и [[Качественная переменная|качественными]] данными'''{{sfn|Gareth, Witten, Hastie, Tibshirani|2015|с=315}}. Другие техники обычно специализируются на анализе данных, которые имеют только один тип переменных. (Например, правила отношений могут быть использованы только с категориальными переменными, в то время как нейронные сети могут быть использованы только с числовыми (количественными) переменными или приведёнными к значениям 0/1.)
* '''Требует малой подготовки данных.''' Другие техники часто требуют нормализации данных. Поскольку деревья могут обрабатывать качественные независимые переменные, нет необходимости создавать [[Фиктивная переменная|фиктивные переменные]]{{sfn|Gareth, Witten, Hastie, Tibshirani|2015|с=315}}.
* '''Использует модель {{не переведено 5|Белый ящик (программирование)|белого ящика||white box (software engineering)}}.''' Если данная ситуация наблюдаема в модели, условия объясняются легко булевской логикой. В отличие от этого, в модели [[Чёрный ящик|чёрного ящика]] объяснение результатов обычно трудно понять, например, ввиду применения [[Искусственная нейронная сеть|искусственной нейронной сети]].
* '''Можно удостовериться в правильности модели с помощью статистических тестов.''' Это делает возможным проверять достоверность модели.
* Нестатистический подход, который не делает никаких предположений для тренировочных данных или отклонений предсказания. Например, не делается никаких предположений о распределении, независимости или постоянстве дисперсии
* '''Хорошо работает с большими наборами данных.''' Большое количество данных может быть проанализировано с помощью стандартных вычислительных ресурсов за приемлемое время.
* '''Отражают человеческое принятие решений более тесно, чем другие подходы'''{{sfn|Gareth, Witten, Hastie, Tibshirani|2015|с=315}}. Это может быть полезным при моделировании человеческих решений и человеческого поведения.
* Более устойчив к колинеарности.
* По выполненному [[Отбор признаков|отбору признаков]]. Дополнительные бесполезные признаки будут использованы в меньшей мере, так что они могут быть удалены из последующих прогонов.
* Деревья решений можно аппроксимировать любой булевой функцией, эквивалентной XOR{{sfn|Mehtaa, Raghavan|2002|с=609–623}}.

=== Ограничения ===
* Деревья могут оказаться существенно неустойчивыми. Небольшие изменения в {{не переведено 5|Тренировочные, тестовые и контрольные наборы|тренировочных данных||Training, test, and validation sets}} могут привести к существенным изменения в дереве, а в конце концов и к конечным предсказаниям{{sfn|Gareth, Witten, Hastie, Tibshirani|2015|с=315}}.
* Известно, что задача обучения до оптимального дерева решений [[NP-полная задача|NP-полна]] по некоторым вопросам оптимальности и даже для простых концепций{{sfn|Hyafil, Rivest|1976|с=15–17}}{{sfn|Murthy|1998}}. Как следствие, практические обучающие алгоритмы дерева решений основаны на эвристике, такой как  [[жадный алгоритм]], когда локальные оптимальные решения принимаются для каждого узла. Такие алгоритмы не могут гарантировать получение глобально оптимального дерева решений. Чтобы уменьшить эффект локальной оптимальности, предлагаются некоторые методы, такие как дерево двойственного информационного расстояния ({{lang-en|dual information distance}}, DID){{sfn|Ben-Gal, Dana, Shkolnik, Singer|2014|с=133–147}}.

* Обучение дерева решений может создать сверхсложные деревья, которые не обобщаются хорошо из тренировочных данных (что известно как [[переобучение]]{{sfn|Bramer|2007}}). Механизмы, такие как {{не переведено 5|Обрезка деревьев решений|обрезка||Decision tree pruning}}, становятся необходимыми для избежания этой проблемы (за исключением некоторых алгоритмов, таких подходов, как условное умозаключение ({{lang-en|Conditional Inference}}), которое не требует обрезки){{sfn|Hothorn, Hornik, Zeileis|2006|с=651–674}}{{sfn|Strobl, Malley, Tutz|2009|с=323–348}}.
* Для данных, имеющих качественные переменные с различным числом уровней {{не переведено 5|информационный выигрыш в дереве решений|||information gain in decision trees}} смещён в сторону атрибутов с бо́льшими уровнями{{sfn|Deng, Runger, Tuv|2011|с=293–300}}. Однако проблема смещения с помощью условного умозаключения{{sfn|Hothorn, Hornik, Zeileis|2006|с=651–674}}, двухступенчатого подхода{{sfn|Brandmaier, von Oertzen, McArdle, Lindenberger|2012|с=71–86}} или адаптивного отбора признаков по отдельным объектам{{sfn|Painsky, Rosset|2017|с=2142–2153}}.

=== Реализации ===
Многие пакеты интеллектуального анализа данных реализуют один или несколько алгоритмов деревьев решений.

Примерами служат Salford Systems CART (который лицензировал проприетарный код оригинальных авторов CART){{sfn|Breiman, Friedman, Olshen, Stone|1984}}, {{не переведено 5|SPSS Modeler|IBM SPSS Modeler||SPSS Modeler}}, {{не переведено 5|RapidMiner|||RapidMiner}}, {{не переведено 5|SAS (программный комплекс)|SAS Enterprise Miner||SAS (software)}}, [[Matlab]], [[R (язык программирования)|R]] (программное обеспечение с открытым кодом для статистических вычислений, которое включает несколько реализаций CART, таких как пакеты rpart, party и randomForest), [[Weka]] (свободно распространяемый пакет программ с открытым кодом для интеллектуального анализа данных, содержащий много алгоритмов дерева решений), {{не переведено 5|Orange (программный комплекс)|Orange||Orange (software)}}, {{не переведено 5|KNIME|||KNIME}}, [[Microsoft SQL Server]] [https://technet.microsoft.com/en-us/library/cc645868.aspx] и [[scikit-learn]] (свободно распространяемая библиотека на языке [[Python]] с открытым кодом для машинного обучения).

== Расширения ==

=== Графы решений ===
В дереве решений все пути из корневого узла к листу идут через конъюнкцию (''AND''). В графе решений возможно использование дизъюнкции (''OR'') для объединения путей с помощью [[Сообщение минимальной длины|сообщения минимальной длины]] ({{lang-en|Minimum message length}}, MML) <ref>{{cite web|url=http://citeseer.ist.psu.edu/oliver93decision.html|title=CiteSeerX|access-date=2019-01-02|archive-date=2008-03-21|archive-url=https://web.archive.org/web/20080321150740/http://citeseer.ist.psu.edu/oliver93decision.html|deadlink=no}}</ref>. Графы решений расширяются далее с разрешением до этого не использованных атрибутов обучать динамически и использовать в различных местах графа<ref>{{Cite web |url=http://www.csse.monash.edu.au/~dld/Publications/2003/Tan+Dowe2003_MMLDecisionGraphs.pdf |title=Tan & Dowe (2003) |access-date=2019-01-02 |archive-date=2016-05-28 |archive-url=https://web.archive.org/web/20160528142023/http://www.csse.monash.edu.au/~dld/Publications/2003/Tan+Dowe2003_MMLDecisionGraphs.pdf |deadlink=no }}</ref>. Более общая схема кодирования приводит к лучшим предсказаниям и показателям логарифмических потерь.  В общем случае графы решений дают модели с меньшим числом листьев, чем деревья решений.

=== Альтернативные методы поиска ===
Эволюционные алгоритмы использовались для исключения локальных оптимальных решений и поиска деревьев решений с меньшим ''априорным'' смещением{{sfn|Papagelis, Kalles|2001|с=393–400}}{{sfn|Barros, Basgalupp, Carvalho, Freitas|2012|с=291–312}}.

Можно упростить деревья с помощью [[Метод Монте-Карло для цепей Маркова|метода Монте-Карло для цепей Маркова]] ({{lang-en|Markov chain Monte Carlo}}, MCMC){{sfn|Chipman, George, McCulloch|1998|с=935–948}}.

Дерево можно просматривать снизу вверх{{sfn|Barros, Cerri, Jaskowiak, Carvalho|2011|с=450–456}}.

== См. также ==
{{Div col|colwidth=20em}}
* {{не переведено 5|Обрезка деревьев решений|||Decision tree pruning}}
* [[Бинарная диаграмма решений]]
* {{не переведено 5|Автоматическое выявление зависимостей по критерию хи-квадрат|CHAID||CHAID}}
* [[Предсказательная аналитика|CART]]
* [[ID3 (алгоритм)]]
* [[C4.5|Алгоритм C4.5]]
* {{не переведено 5|Решающий пень|Решающие пни||Decision stump}}, используются, например, в алгоритме [[AdaBoost]]
* {{не переведено 5|Список решений|||Decision list}}
* {{не переведено 5|Инкрементальные деревья решений|||Incremental decision tree}}
* {{не переведено 5|Чередующиеся решающие деревья|||Alternating decision tree}}
* {{не переведено 5|Анализ структурированных данных|||Structured data analysis (statistics)}}
* {{не переведено 5|Дерево логистической модели|||Logistic model tree}}
* [[Иерархическая кластеризация]]{{Div col end}}

== Примечания ==
{{примечания|2}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{книга
|ref=Rokach, Maimon
|автор=Lior Rokach, Maimon O.
|заглавие=Data mining with decision trees: theory and applications
|год=2008
|издательство=World Scientific Pub Co Inc
|isbn=978-9812771711
}}
* {{статья
|автор=Quinlan J. R.
|ref=Quinlan
|год=1986
|ссылка=https://link.springer.com/content/pdf/10.1007/BF00116251.pdf 
|заглавие=Induction of Decision Trees
|издание=Machine Learning
|выпуск=1
|страницы=81-106
|издательство=Kluwer Academic Publishers
}}
* {{книга
|ref=Breiman, Friedman, Olshen, Stone
|автор=Leo Breiman, Friedman J. H., Olshen R. A., Stone C. J.
|заглавие=Classification and regression trees
|год=1984
|издательство=Wadsworth & Brooks/Cole Advanced Books & Software
|место=Monterey, CA
|isbn=978-0-412-04841-8
}}
* {{статья
|автор=Friedman J. H.
|ref=Friedman
|год=1999
|ссылка=https://astro.temple.edu/~msobel/courses_files/StochasticBoosting(gradient).pdf 
|заглавие=Stochastic gradient boosting
|издательство=Stanford University
}}
* {{книга
|автор=Hastie T., Tibshirani R., Friedman J. H.
|ref=Hastie, Tibshirani, Friedman
|год=2001
|издание=2nd
|заглавие=The elements of statistical learning : Data mining, inference, and prediction
|место=New York
|издательство=Springer Verlag
|серия=Springer Series in Statistics
|ISBN=978-0-387-84857-0
|ISBN1=978-0-387-84858-7
}}
* {{статья
|ref=Breiman
|автор=Breiman L.
|год=1996
|заглавие=Bagging Predictors
|издание=Machine Learning
|том=24
|выпуск=2
|doi=10.1007/BF00058655 
}}
* {{статья
|автор=Rodriguez J. J., Kuncheva L. I., Alonso C. J.
|ref=Rodriguez, Kuncheva, Alonso
|год=2006
|заглавие=Rotation forest: A new classifier ensemble method
|издание=IEEE Transactions on Pattern Analysis and Machine Intelligence
|том=28
|выпуск=10
|doi=10.1109/TPAMI.2006.211
|pmid=16986543
|citeseerx=10.1.1.156.8277 
}}
* {{статья
|ref=Rivest
|автор=Ron Rivest
|заглавие=Learning Decision Lists
|издание=Machine Learning
|месяц=Nov
|год=1987
|том=3
|выпуск=2
|doi=10.1023/A:1022607331053
|ссылка=http://people.csail.mit.edu/rivest/pubs/Riv87b.pdf
}}
* {{статья
|автор=Ben Letham, Cynthia Rudin, Tyler McCormick, David Madigan
|ref=Letham, Rudin, McCormick, Madigan
|заглавие=Interpretable Classifiers Using Rules And Bayesian Analysis: Building A Better Stroke Prediction Model
|издание=Annals of Applied Statistics
|год=2015
|том=9
|выпуск=3
|doi=10.1214/15-AOAS848
|arxiv=1511.01644
}}
* {{статья
|автор=Fulton Wang, Cynthia Rudin
|ref=Wang, Rudin
|заглавие=Falling Rule Lists
|издание=Journal of Machine Learning Research
|год=2015
|том=38
|ссылка=http://www.jmlr.org/proceedings/papers/v38/wang15a.pdf
}}
* {{статья
|doi=10.2307/2986296
|ref=Kass 
|автор=Kass G. V.
|год=1980
|заглавие=An exploratory technique for investigating large quantities of categorical data
|jstor=2986296
|издание=Applied Statistics
|том=29
|выпуск=2
}}
* {{статья
|doi=10.1198/106186006X133933 
|автор=Hothorn T., Hornik K., Zeileis A.
|ref=Hothorn, Hornik, Zeileis
|год=2006 
|заглавие=Unbiased Recursive Partitioning: A Conditional Inference Framework 
|jstor=27594202
|издание=Journal of Computational and Graphical Statistics
|том=15
|выпуск=3
|citeseerx=10.1.1.527.2935
}}
* {{статья
|doi=10.1037/a0016973
|pmid=19968396
|pmc=2927982
|автор=Strobl C., Malley J., Tutz G.
|ref=Strobl, Malley, Tutz
|год=2009
|заглавие=An Introduction to Recursive Partitioning: Rationale, Application and Characteristics of Classification and Regression Trees, Bagging and Random Forests
|издание=Psychological Methods
|том=14
|выпуск=4
}}
* {{статья
|автор=Rokach L., Maimon O.
|ref=Rokach, Maimon
|заглавие=Top-down induction of decision trees classifiers-a survey
|издание=IEEE Transactions on Systems, Man, and Cybernetics, Part C
|том=35
|год=2005
|doi=10.1109/TSMCC.2004.843247
|выпуск=4
|citeseerx=10.1.1.458.7031 
}}
* {{книга
|заглавие=Data Mining
|автор=Ian Witten, Eibe Frank, Mark Hall
|ref=Witten, Frank, Hall
|издательство=Morgan Kaufmann
|год=2011
|isbn=978-0-12-374856-0
|место=Burlington, MA
}}
* {{книга
|заглавие=Principles of Data Mining
|ссылка=https://archive.org/details/principlesofdata0000bram
|doi=10.1007/978-1-84628-766-4
|год=2007
|издательство=Springer-Verlag
|серия=Undergraduate Topics in Computer Science
|автор=Max Bramer
|ref=Bramer
|isbn=978-1-84628-765-7 
|ISBN1=978-1-84628-766-4
}}
* {{книга
|заглавие=An Introduction to Statistical Learning
|автор=James Gareth, Daniela Witten, Trevor Hastie, Robert Tibshirani
|ref=Gareth, Witten, Hastie, Tibshirani
|издательство=Springer
|год=2015
|isbn=978-1-4614-7137-0
|место=New York
}}
* {{статья
|автор=Dinesh Mehtaa, Vijay Raghavan
|ref=Mehtaa, Raghavan
|заглавие=Decision tree approximations of Boolean functions
|издание=Theoretical Computer Science
|том=270
|выпуск=1–2
|год=2002
|страницы=609–623
|doi=10.1016/S0304-3975(01)00011-1 
}}
* {{статья
|doi=10.1016/0020-0190(76)90095-8
|автор=Laurent Hyafil, Rivest R.L.
|ref=Hyafil, Rivest
|год=1976
|заглавие=Constructing Optimal Binary Decision Trees is NP-complete
|издание=Information Processing Letters
|том=5
|выпуск=1
|страницы=15–17 
}}
* {{книга
|автор=Murthy S.
|ref=Murthy
|год=1998
|ссылка часть=https://cs.nyu.edu/~roweis/csc2515-2006/readings/murthy_dt.pdf 
|часть=Automatic construction of decision trees from data: A multidisciplinary survey
|заглавие=Data Mining and Knowledge Discovery
}}

* {{статья
|ссылка= http://www.eng.tau.ac.il/~bengal/DID.pdf|заглавие=Efficient Construction of Decision Trees by the Dual Information Distance Method
|автор= Irad Ben-Gal, Alexandra Dana, Niv Shkolnik, Gonen Singer
|ref=Ben-Gal, Dana, Shkolnik, Singer
|издание= Quality Technology & Quantitative Management
|том= 11
|выпуск=1
|страницы= 133–147
|год=2014
}}
* {{книга
|автор=Deng H., Runger G., Tuv E. 
|ref=Deng, Runger, Tuv 
|часть=Bias of importance measures for multi-valued attributes and solutions
|заглавие=Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN)
|год=2011
|страницы= 293–300
|ссылка=https://www.researchgate.net/profile/Houtao_Deng/publication/221079908_Bias_of_Importance_Measures_for_Multi-valued_Attributes_and_Solutions/links/0046351909faa8f0eb000000/Bias-of-Importance-Measures-for-Multi-valued-Attributes-and-Solutions.pdf
}}
* {{статья
|автор=Andreas M. Brandmaier, Timo von Oertzen, John J. McArdle, Ulman Lindenberger
|ref=Brandmaier, von Oertzen, McArdle, Lindenberger
|заглавие=Structural equation model trees.
|издание=Psychological Methods
|том=18
|выпуск=1
|страницы=71–86|doi=10.1037/a0030001
|pmid=22984789
|pmc=4386908
|год=2012
|hdl=11858/00-001M-0000-0024-EA33-9
}}
* {{статья
|автор=Amichai Painsky, Saharon Rosset
|ref=Painsky, Rosset
|заглавие=Cross-Validated Variable Selection in Tree-Based Methods Improves Predictive Performance
|издание=IEEE Transactions on Pattern Analysis and Machine Intelligence
|год=2017
|том=39
|выпуск=11
|страницы=2142–2153
|pmid=28114007
|doi=10.1109/TPAMI.2016.2636831
}}
* {{книга
|автор=Papagelis A., Kalles D. 
|ref=Papagelis, Kalles 
|год=2001
|часть=Breeding Decision Trees Using Evolutionary Techniques
|заглавие=Proceedings of the Eighteenth International Conference on Machine Learning, June 28–July 1, 2001
|страницы=393–400
|ссылка часть=http://www.gatree.com/wordpress/wp-content/uploads/2010/04/BreedinDecisioTreeUsinEvo.pdf 
}}
* {{статья
|автор=Rodrigo C. Barros, Basgalupp M. P., Carvalho A. C. P. L. F., Alex A. Freitas 
|ref=Barros, Basgalupp, Carvalho, Freitas 
|год=2012
|doi=10.1109/TSMCC.2011.2157494
|заглавие=A Survey of Evolutionary Algorithms for Decision-Tree Induction
|издание=IEEE Transactions on Systems, Man and Cybernetics
|серия=Part C: Applications and Reviews 
|том=42
|выпуск=3
|страницы=291–312
|citeseerx=10.1.1.308.9068
}}
* {{статья
|автор=Hugh A. Chipman, Edward I. George, Robert E. McCulloch
|ref=Chipman, George, McCulloch
|заглавие=Bayesian CART model search|ссылка=https://archive.org/details/sim_journal-of-the-american-statistical-association_1998-09_93_443/page/935
|издание=Journal of the American Statistical Association
|том=93
|выпуск=443
|год=1998
|страницы=935–948
|doi=10.1080/01621459.1998.10473750
|citeseerx=10.1.1.211.5573 
}}
* {{книга
|автор=Barros R. C., Cerri R., Jaskowiak P. A., Carvalho A. C. P. L. F.
|ref=Barros, Cerri, Jaskowiak, Carvalho
|doi=10.1109/ISDA.2011.6121697
|часть=A bottom-up oblique decision tree induction algorithm
|заглавие=Proceedings of the 11th International Conference on Intelligent Systems Design and Applications (ISDA 2011)
|страницы=450–456
|год=2011
|isbn=978-1-4577-1676-8 
}}
{{refend}}

== Литература для дальнейшего чтения ==
* {{книга
|автор=Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani
|часть=Tree-Based Methods
|заглавие=An Introduction to Statistical Learning: with Applications in R
|место=New York|издательство=Springer
|год=2017
|isbn=978-1-4614-7137-0
|ссылка часть=https://www-bcf.usc.edu/~gareth/ISL/ISLR%20Seventh%20Printing.pdf#page=317
|страницы=303–336
}}

== Ссылки ==
* [http://www.onlamp.com/pub/a/python/2006/02/09/ai_decision_trees.html Building Decision Trees in Python] From O'Reilly.
* [http://www.oreillynet.com/mac/blog/2007/06/an_addendum_to_building_decisi.html An Addendum to "Building Decision Trees in Python"] From O'Reilly.
* [http://people.revoledu.com/kardi/tutorial/DecisionTree/index.html Decision Trees Tutorial] using Microsoft Excel.
* [http://aitopics.org/topic/decision-tree-learning Decision Trees page at aitopics.org], a page with commented links.
* [http://ai4r.org/index.html Decision tree implementation in Ruby (AI4R)]
* [https://www.researchgate.net/publication/316471270_Decision_Stream_Cultivating_Deep_Decision_Trees Deep Decision Tree]|[https://github.com/aiff22/Decision-Stream Implementation]
* [http://www.cs.uwaterloo.ca/~mgrzes/code/evoldectrees/ Evolutionary Learning of Decision Trees in C++]
* [https://github.com/kobaj/JavaDecisionTree Java implementation of Decision Trees based on Information Gain]
* [http://christianherta.de/lehre/dataScience/machineLearning/decision-trees.html A very detailled explanation of information gain as splitting criterion]
{{Машинное обучение}}

[[Категория:Деревья принятия решений]]
[[Категория:Алгоритмы классификации]]
{{rq|checktranslate|style}}