Обучение дерева решений

Обучение дерева решений использует дерево решений (как предиктивную модель^[англ.]), чтобы перейти от наблюдений над объектами (представленными в ветвях) к заключениям о целевых значениях объектов (представленных в листьях). Это обучение является одним из подходов моделирования предсказаний, используемых в статистике, интеллектуальном анализе данных и машинном обучении. Модели деревьев, в которых целевая переменная может принимать дискретный набор значений, называются деревьями классификации. В этих структурах деревьев листья представляют метки классов, а ветки представляют конъюнкции признаков, которые ведут в эти метки классов. Деревья решений, в которых целевая переменная может принимать непрерывные значения (обычно, вещественные числа) называются деревьями регрессии.

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

Обсуждение

Дерево, показывающее выживаемость пассажиров Титаника ("родств." — это число семейных пар или родственников на борту). Фигуры под листами показывают вероятность выживания и процент от полного числа. Итог: Ваш шанс выжить был бы хорошим, если бы вы были (i) женщиной или (ii) мальчиком до 9.5 лет с менее чем 2.5 родственниками.

Обучение дерева решений — это метод, обычно используемый в интеллектуальном анализе данных^[1]. Целью является создание модели, которая предсказывает значение целевой переменной, основываясь на некоторых входных переменных. Пример показан на диаграмме справа. Каждый внутренний узел соответствует одной из входных переменных. Есть рёбра к потомкам для каждого возможного значения этой входной переменной. Каждый лист представляет значение целевой переменной, которое определяется значениями входных переменных от корня до листа.

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

Дерево может быть «обучено» путём расщепления множества на подмножества, основываясь на проверку значений атрибутов. Этот процесс, повторяющийся на каждом полученном подмножестве рекурсивно, называется рекурсивным секционированием^[англ.]. Рекурсия прекращается, когда подмножество в узле имеет одно и то же значение целевой переменной или когда разбиение не добавляет значения в предсказания. Этот процесс индукции сверху вниз деревьев решений (англ. top-down induction of decision trees, TDIDT)^[2] является примером жадного алгоритма, и служит наиболее часто применяемой стратегией обучения деревьев решений из данных.

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

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

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

Зависимая переменная Y является целевой переменной, которую мы пытаемся понять, классифицировать или обобщить. Вектор x составлен из признаков x₁, x₂, x₃ и т.д., которые используются для задачи.

Пример дерева, который оценивает вероятность кифоза после операции, в зависимости от возраста пациента и номера позвонка, на котором была проведена операция. Одно и то же дерево показано тремя различными способами. Сверху Цветные листья показывают вероятность кифоза после операции и процент пациентов на листе. Середина Дерево как псевдотрёхмерная диаграмма. Внизу Вид той же диаграммы сверху. Вероятность кифоза после операции тем больше, чем темнее область.

Типы деревьев решений

Деревья решений используются при интеллектуальном анализе данных и бывают двух основных типов:

Анализ дерева классификации^[англ.], когда предсказываемый выход является классом, которому данные принадлежат.
Анализ дерева регрессии, когда предсказываемый выход может считаться вещественным числом (например, цена дома или продолжительность нахождения пациента в больнице).

Термин анализ по дереву классификации и регрессии (англ. Classification And Regression Tree, CART) является обобщающим термином и он используется для обозначения двух упомянутых выше процедур, первую из которых ввели Брейман с соавторами в 1984^[3]. Деревья, используемые для регрессии, и деревья, используемые для классификации, имеют некоторую схожесть, однако имеют и отличия, такие как процедура, используемая для определения места расщепления^[3].

Некоторые техники, часто называемые методами сборки, строят более одного дерева решений:

Расширяемые деревья^[англ.] (англ. Boosted Trees) строят шаг за шагом сборку путём тренировки каждого нового экземпляра, делая упор на тренировку ранее не попадающих в модель экземпляров. Типичным примером является AdaBoost. Это может быть использовано как для задач регрессионного типа, так и задач классификации ^[4]^[5].
Бэггинг деревьев решений, ранний метод сборки, строящий несколько деревьев решений путём повторной выборки тренировочных данных с заменой и голосованием за деревья для согласования предсказания^[6].
- Классификатор на основе случайного леса является специфичным видом бэггинга
Ротационный лес — подход, в котором каждое дерево решений сначала тренируется применением метода главных компонент (англ. Principal Component Analysis, PCA) на случайном подмножестве входных признаков^[7].

Специальным случаем деревьев решений является список решений^[англ.]^[8], который является односторонним деревом решений, так что любой внутренний узел имеет в точности 1 лист и в точности 1 внутренний узел в качестве наследника (за исключением самого нижнего узла, единственным наследником которого является один лист). Хотя эти списки менее выразительны, их легче понять, чем общие деревья решений, ввиду их разреженности, что разрешает применение методов обучения, не являющихся жадными^[9], а также позволяют наложение монотонных ограничений^[10].

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

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

ID3 (англ. Iterative Dichotomiser 3)
C4.5 (преемник алгоритма ID3)
Классификация и регрессия построением дерева решений. (англ. Classification And Regression Tree, CART)
Автоматическое выявление зависимостей по критерию хи-квадрат^[англ.] (англ. CHi-squared Automatic Interaction Detector, CHAID). Осуществляет многоуровневое расщепление при вычислении деревьев классификации^[11].
Многомерные адаптивные регрессионные сплайны^[англ.] (англ. Multivariate adaptive regression splines, MARS): расширяет деревья решений для лучшей обработки количественных данных.
Деревья условного вывода (англ. Conditional Inference Trees). Подход на основе статистики, который использует непараметрические тесты в качестве критерия расщепления, скорректированные для многократного тестирования во избежание переобучения. Этот подход приводит к выбору несмещённого предсказателя и не требует обрезки^[12]^[13].

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

Метрики

Алгоритмы построения деревья решений обычно работают сверху вниз путём выбора переменной на каждом шаге, которая лучшим образом разбивает множество элементов^[14]. Разные алгоритмы используют различные метрики для измерения «лучшего» решения. Они обычно измеряют однородность целевой переменной на подмножествах. Некоторые примеры даны ниже. Эти метрики применяются к каждому подмножеству и получающиеся значения комбинируются (например, вычисляется среднее) для получения меры качества разбиения.

Примесь (критерий) Джини

Используемый в алгоритме деревьев классификации и регрессии (англ. classification and regression tree, CART) критерий Джини является мерой, насколько часто случайно выбранный элемент из набора неверно помечается, если он случайным образом помечается согласно распределению меток в подмножестве. Критерий Джини может быть вычислен путём суммирования вероятности $p_{i}$ элемента с выбранной меткой $i$ , умноженной на вероятность $\sum _{k\neq i}p_{k}=1-p_{i}$ ошибки категоризации этого элемента. Критерий принимает минимум (нуль), когда все случаи в узле попадают в одну целевую категорию.

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

\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 _{i=1}^{J}{p_{i}}^{2}

Информационный выигрыш

В алгоритмах генерации деревьев ID3, C4.5 и C5.0. используется Информационный выигрыш, который основывается на понятии энтропии и объёма информации из теории информации.

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

\mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},...,p_{J}\right)=-\sum _{i=1}^{J}{p_{i}\log _{2}p_{i}}

,

где $p_{1},p_{2},...$ являются долями, в сумме дающими 1, которые представляют процент каждого класса, полученный от разбиения в дереве^[15].

\overbrace {IG(T,a)} ^{\text{Information Gain}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropy (parent)}}-\overbrace {\mathrm {H} (T|a)} ^{\text{Weighted Sum of Entropy (Children)}}

=-\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)}}

В формуле

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

Информационный выигрыш используется для принятия решения, какой признак использовать для расщепления на каждом шаге построения дерева. Простота является лучшим выбором, так что мы хотим сохранять дерево небольшим. Чтобы это сделать, на каждом шаге нам следует выбрать расщепление, которое приводит к простейшим узлам-наследникам. Обычно используемая мера простоты называется информацией, которая измеряется в битах. Для каждого узла дерева значение информации «представляет ожидаемое количество, которая нужна для определения, должен ли новый объект классифицирован как да или нет, если дано, что пример достигает этого узла»"^[15].

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

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

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

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

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

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

I_{E}([3,3],[6,2])=I_{E}

(ветер - да или нет)

={\frac {6}{14}}\cdot 1+{\frac {8}{14}}\cdot 0,8112781=0,8921589

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

I_{E}([9,5])=-{\frac {9}{14}}\log _{2}^{}{\frac {9}{14}}-{\frac {5}{14}}\log _{2}{\frac {5}{14}}=0,940286

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

IG

(ветер)

=I_{E}([9,5])-I_{E}([3,3],[6,2])=0,940286-0,8921589=0,0481271

Чтобы построить дерево, нужно вычислить информационный выигрыш каждого возможного первого расщепления. Лучшее первое расщепление, это то, которое даёт наибольший информационный выигрыш. Этот процесс повторяется для каждого узла (со смешанными признаками), пока дерево не будет построено. Этот пример заимствован из статьи Виттена, Франка и Холла^[15].

Понижение дисперсии

Представленное в CART^[3] понижение дисперсии часто используется в случаях, когда целевая переменная непрерывна (дерево регрессии), это означает, что использование многих других метрик требовало бы дискретизации перед применением. Понижение дисперсии узла N определяется как общее сокращение дисперсии целевой переменной x как следствие расщепления в этом узле:

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)

,

где $S$ , $S_{t}$ и $S_{f}$ являются множеством индексов до расщепления, множеством индексов, для которых тест даёт true и множеством индексов, для которых тест даёт false соответственно. Каждое из слагаемых выше является оценкой величины отклонения, хотя и записанной без прямой ссылки на среднее.

Применение

Преимущества

Среди других методов анализа данных деревья решений имеют ряд преимуществ:

Легки для понимания и интерпретации. Люди способны понять модели деревьев решений после краткого объяснения. Деревья можно изобразить графически таким образом, что их легко интерпретировать, не будучи экспертом^[16].
Способны работать как с числовыми, так и качественными данными^[16]. Другие техники обычно специализируются на анализе данных, которые имеют только один тип переменных. (Например, правила отношений могут быть использованы только с категориальными переменными, в то время как нейронные сети могут быть использованы только с числовыми (количественными) переменными или приведёнными к значениям 0/1.)
Требует малой подготовки данных. Другие техники часто требуют нормализации данных. Поскольку деревья могут обрабатывать качественные независимые переменные, нет необходимости создавать фиктивные переменные^[16].
Использует модель белого ящика^[англ.]. Если данная ситуация наблюдаема в модели, условия объясняются легко булевской логикой. В отличие от этого, в модели чёрного ящика объяснение результатов обычно трудно понять, например, ввиду применения искусственной нейронной сети.
Можно удостовериться в правильности модели с помощью статистических тестов. Это делает возможным проверять достоверность модели.
Нестатистический подход, который не делает никаких предположений для тренировочных данных или отклонений предсказания. Например, не делается никаких предположений о распределении, независимости или постоянстве дисперсии
Хорошо работает с большими наборами данных. Большое количество данных может быть проанализировано с помощью стандартных вычислительных ресурсов за приемлемое время.
Отражают человеческое принятие решений более тесно, чем другие подходы^[16]. Это может быть полезным при моделировании человеческих решений и человеческого поведения.
Более устойчив к колинеарности.
По выполненному отбору признаков. Дополнительные бесполезные признаки будут использованы в меньшей мере, так что они могут быть удалены из последующих прогонов.
Деревья решений можно аппроксимировать любой булевой функцией, эквивалентной XOR^[17].

Ограничения

Деревья могут оказаться существенно неустойчивыми. Небольшие изменения в тренировочных данных^[англ.] могут привести к существенным изменения в дереве, а в конце концов и к конечным предсказаниям^[16].
Известно, что задача обучения до оптимального дерева решений NP-полна по некоторым вопросам оптимальности и даже для простых концепций^[18]^[19]. Как следствие, практические обучающие алгоритмы дерева решений основаны на эвристике, такой как жадный алгоритм, когда локальные оптимальные решения принимаются для каждого узла. Такие алгоритмы не могут гарантировать получение глобально оптимального дерева решений. Чтобы уменьшить эффект локальной оптимальности, предлагаются некоторые методы, такие как дерево двойственного информационного расстояния (англ. dual information distance, DID)^[20].

Обучение дерева решений может создать сверхсложные деревья, которые не обобщаются хорошо из тренировочных данных (что известно как переобучение^[21]). Механизмы, такие как обрезка^[англ.], становятся необходимыми для избежания этой проблемы (за исключением некоторых алгоритмов, таких подходов, как условное умозаключение (англ. Conditional Inference), которое не требует обрезки)^[12]^[13].
Для данных, имеющих качественные переменные с различным числом уровней информационный выигрыш в дереве решений^[англ.] смещён в сторону атрибутов с бо́льшими уровнями^[22]. Однако проблема смещения с помощью условного умозаключения^[12], двухступенчатого подхода^[23] или адаптивного отбора признаков по отдельным объектам^[24].

Реализации

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

Примерами служат Salford Systems CART (который лицензировал проприетарный код оригинальных авторов CART)^[3], IBM SPSS Modeler^[англ.], RapidMiner^[англ.], SAS Enterprise Miner^[англ.], Matlab, R (программное обеспечение с открытым кодом для статистических вычислений, которое включает несколько реализаций CART, таких как пакеты rpart, party и randomForest), Weka (свободно распространяемый пакет программ с открытым кодом для интеллектуального анализа данных, содержащий много алгоритмов дерева решений), Orange^[англ.], KNIME^[англ.], Microsoft SQL Server [1] и scikit-learn (свободно распространяемая библиотека на языке Python с открытым кодом для машинного обучения).

Расширения

Графы решений

В дереве решений все пути из корневого узла к листу идут через конъюнкцию (AND). В графе решений возможно использование дизъюнкции (OR) для объединения путей с помощью сообщения минимальной длины (англ. Minimum message length, MML) ^[25]. Графы решений расширяются далее с разрешением до этого не использованных атрибутов обучать динамически и использовать в различных местах графа^[26]. Более общая схема кодирования приводит к лучшим предсказаниям и показателям логарифмических потерь. В общем случае графы решений дают модели с меньшим числом листьев, чем деревья решений.

Альтернативные методы поиска

Эволюционные алгоритмы использовались для исключения локальных оптимальных решений и поиска деревьев решений с меньшим априорным смещением^[27]^[28].

Можно упростить деревья с помощью метода Монте-Карло для цепей Маркова (англ. Markov chain Monte Carlo, MCMC)^[29].

Дерево можно просматривать снизу вверх^[30].

См. также

Примечания

↑ Rokach, Maimon, 2008.
↑ Quinlan, 1986, с. 81-106.
↑ ¹ ² ³ ⁴ Breiman, Friedman, Olshen, Stone, 1984.
↑ Friedman, 1999.
↑ Hastie, Tibshirani, Friedman, 2001.
↑ Breiman, 1996, с. 123–140.
↑ Rodriguez, Kuncheva, Alonso, 2006, с. 1619–1630.
↑ Rivest, 1987, с. 229–246.
↑ Letham, Rudin, McCormick, Madigan, 2015, с. 1350–1371.
↑ Wang, Rudin, 2015.
↑ Kass, 1980, с. 119–127.
↑ ¹ ² ³ Hothorn, Hornik, Zeileis, 2006, с. 651–674.
↑ ¹ ² Strobl, Malley, Tutz, 2009, с. 323–348.
↑ Rokach, Maimon, 2005, с. 476–487.
↑ ¹ ² ³ Witten, Frank, Hall, 2011, с. 102–103.
↑ ¹ ² ³ ⁴ ⁵ Gareth, Witten, Hastie, Tibshirani, 2015, с. 315.
↑ Mehtaa, Raghavan, 2002, с. 609–623.
↑ Hyafil, Rivest, 1976, с. 15–17.
↑ Murthy, 1998.
↑ Ben-Gal, Dana, Shkolnik, Singer, 2014, с. 133–147.
↑ Bramer, 2007.
↑ Deng, Runger, Tuv, 2011, с. 293–300.
↑ Brandmaier, von Oertzen, McArdle, Lindenberger, 2012, с. 71–86.
↑ Painsky, Rosset, 2017, с. 2142–2153.
↑ CiteSeerX (неопр.). Дата обращения: 2 января 2019. Архивировано 21 марта 2008 года.
↑ Tan & Dowe (2003) (неопр.). Дата обращения: 2 января 2019. Архивировано 28 мая 2016 года.
↑ Papagelis, Kalles, 2001, с. 393–400.
↑ Barros, Basgalupp, Carvalho, Freitas, 2012, с. 291–312.
↑ Chipman, George, McCulloch, 1998, с. 935–948.
↑ Barros, Cerri, Jaskowiak, Carvalho, 2011, с. 450–456.

Литература

Lior Rokach, Maimon O. Data mining with decision trees: theory and applications. — World Scientific Pub Co Inc, 2008. — ISBN 978-9812771711.
Quinlan J. R. Induction of Decision Trees // Machine Learning. — Kluwer Academic Publishers, 1986. — Вып. 1. — С. 81-106.
Leo Breiman, Friedman J. H., Olshen R. A., Stone C. J. Classification and regression trees. — Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984. — ISBN 978-0-412-04841-8.
Friedman J. H. Stochastic gradient boosting. — Stanford University, 1999.
Hastie T., Tibshirani R., Friedman J. H. The elements of statistical learning : Data mining, inference, and prediction. — 2nd. — New York: Springer Verlag, 2001. — (Springer Series in Statistics). — ISBN 978-0-387-84857-0.
Breiman L. Bagging Predictors // Machine Learning. — 1996. — Т. 24, вып. 2. — doi:10.1007/BF00058655.
Rodriguez J. J., Kuncheva L. I., Alonso C. J. Rotation forest: A new classifier ensemble method // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2006. — Т. 28, вып. 10. — doi:10.1109/TPAMI.2006.211. — PMID 16986543.
Ron Rivest. Learning Decision Lists // Machine Learning. — 1987. — Ноябрь (т. 3, вып. 2). — doi:10.1023/A:1022607331053.
Ben Letham, Cynthia Rudin, Tyler McCormick, David 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. Falling Rule Lists // Journal of Machine Learning Research. — 2015. — Т. 38.
Kass G. V. An exploratory technique for investigating large quantities of categorical data // Applied Statistics. — 1980. — Т. 29, вып. 2. — doi:10.2307/2986296. — JSTOR 2986296.
Hothorn T., Hornik K., Zeileis A. Unbiased Recursive Partitioning: A Conditional Inference Framework // Journal of Computational and Graphical Statistics. — 2006. — Т. 15, вып. 3. — doi:10.1198/106186006X133933. — JSTOR 27594202.
Strobl C., Malley J., Tutz G. An Introduction to Recursive Partitioning: Rationale, Application and Characteristics of Classification and Regression Trees, Bagging and Random Forests // Psychological Methods. — 2009. — Т. 14, вып. 4. — doi:10.1037/a0016973. — PMID 19968396. — PMC 2927982.
Rokach L., Maimon O. Top-down induction of decision trees classifiers-a survey // IEEE Transactions on Systems, Man, and Cybernetics, Part C. — 2005. — Т. 35, вып. 4. — doi:10.1109/TSMCC.2004.843247.
Ian Witten, Eibe Frank, Mark Hall. Data Mining. — Burlington, MA: Morgan Kaufmann, 2011. — ISBN 978-0-12-374856-0.
Max Bramer. Principles of Data Mining. — Springer-Verlag, 2007. — (Undergraduate Topics in Computer Science). — ISBN 978-1-84628-765-7. — doi:10.1007/978-1-84628-766-4.
James Gareth, Daniela Witten, Trevor Hastie, Robert Tibshirani. An Introduction to Statistical Learning. — New York: Springer, 2015. — ISBN 978-1-4614-7137-0.
Dinesh Mehtaa, Vijay Raghavan. Decision tree approximations of Boolean functions // Theoretical Computer Science. — 2002. — Т. 270, вып. 1–2. — С. 609–623. — doi:10.1016/S0304-3975(01)00011-1.
Laurent Hyafil, Rivest R.L. Constructing Optimal Binary Decision Trees is NP-complete // Information Processing Letters. — 1976. — Т. 5, вып. 1. — С. 15–17. — doi:10.1016/0020-0190(76)90095-8.
Murthy S. Automatic construction of decision trees from data: A multidisciplinary survey // Data Mining and Knowledge Discovery. — 1998.

Irad Ben-Gal, Alexandra Dana, Niv Shkolnik, Gonen Singer. Efficient Construction of Decision Trees by the Dual Information Distance Method // Quality Technology & Quantitative Management. — 2014. — Т. 11, вып. 1. — С. 133–147.
Deng H., Runger G., Tuv E. Bias of importance measures for multi-valued attributes and solutions // Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). — 2011. — С. 293–300.
Andreas M. Brandmaier, Timo von Oertzen, John J. McArdle, Ulman Lindenberger. Structural equation model trees. // Psychological Methods. — 2012. — Т. 18, вып. 1. — С. 71–86. — doi:10.1037/a0030001. — PMID 22984789. — PMC 4386908.
Amichai Painsky, Saharon 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. — doi:10.1109/TPAMI.2016.2636831. — PMID 28114007.
Papagelis A., Kalles D. Breeding Decision Trees Using Evolutionary Techniques // Proceedings of the Eighteenth International Conference on Machine Learning, June 28–July 1, 2001. — 2001. — С. 393–400.
Rodrigo C. Barros, Basgalupp M. P., Carvalho A. C. P. L. F., Alex A. Freitas. A Survey of Evolutionary Algorithms for Decision-Tree Induction // IEEE Transactions on Systems, Man and Cybernetics. — 2012. — Т. 42, вып. 3. — С. 291–312. — doi:10.1109/TSMCC.2011.2157494.
Hugh A. Chipman, Edward I. George, Robert E. McCulloch. Bayesian CART model search // Journal of the American Statistical Association. — 1998. — Т. 93, вып. 443. — С. 935–948. — doi:10.1080/01621459.1998.10473750.
Barros R. C., Cerri R., Jaskowiak P. A., Carvalho A. C. P. L. F. A bottom-up oblique decision tree induction algorithm // Proceedings of the 11th International Conference on Intelligent Systems Design and Applications (ISDA 2011). — 2011. — С. 450–456. — ISBN 978-1-4577-1676-8. — doi:10.1109/ISDA.2011.6121697.

Литература для дальнейшего чтения

Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani. Tree-Based Methods // An Introduction to Statistical Learning: with Applications in R. — New York: Springer, 2017. — С. 303–336. — ISBN 978-1-4614-7137-0.

Ссылки

Building Decision Trees in Python From O'Reilly.
An Addendum to "Building Decision Trees in Python" From O'Reilly.
Decision Trees Tutorial using Microsoft Excel.
Decision Trees page at aitopics.org, a page with commented links.
Decision tree implementation in Ruby (AI4R)
Deep Decision Tree|Implementation
Evolutionary Learning of Decision Trees in C++
Java implementation of Decision Trees based on Information Gain
A very detailled explanation of information gain as splitting criterion

[_fc442085fc04ba12-1] Rokach, Maimon, 2008.

[_d3c15536516b21be-2] Quinlan, 1986, с. 81-106.

[_cf7c1522678c0db3-3] ¹ ² ³ ⁴ Breiman, Friedman, Olshen, Stone, 1984.

[_35e2165df53459b3-4] Friedman, 1999.

[_9db735ec3f094cf9-5] Hastie, Tibshirani, Friedman, 2001.

[_1efb174c1ce43150-6] Breiman, 1996, с. 123–140.

[_be77e5f9bacc8fb5-7] Rodriguez, Kuncheva, Alonso, 2006, с. 1619–1630.

[_38fbcbb828e5b053-8] Rivest, 1987, с. 229–246.

[_547fbd5ae985af67-9] Letham, Rudin, McCormick, Madigan, 2015, с. 1350–1371.

[_fe76ab1ffd3c414a-10] Wang, Rudin, 2015.

[_72dddc857bf75187-11] Kass, 1980, с. 119–127.

[_be7802559f349fb9-12] ¹ ² ³ Hothorn, Hornik, Zeileis, 2006, с. 651–674.

[_301eca4b441de5e1-13] ¹ ² Strobl, Malley, Tutz, 2009, с. 323–348.

[_957985bf8252f402-14] Rokach, Maimon, 2005, с. 476–487.

[_9d6bbe08d7deeced-15] ¹ ² ³ Witten, Frank, Hall, 2011, с. 102–103.

[_cb4872ff40d4fc03-16] ¹ ² ³ ⁴ ⁵ Gareth, Witten, Hastie, Tibshirani, 2015, с. 315.

[_599f81f35ca11ece-17] Mehtaa, Raghavan, 2002, с. 609–623.

[_8a49d2c06a23fb89-18] Hyafil, Rivest, 1976, с. 15–17.

[_d463401e57ffd657-19] Murthy, 1998.

[_175729eda2ad29a7-20] Ben-Gal, Dana, Shkolnik, Singer, 2014, с. 133–147.

[_c32890867ea45679-21] Bramer, 2007.

[_38242349af0520db-22] Deng, Runger, Tuv, 2011, с. 293–300.

[_2347da1f0fb716b9-23] Brandmaier, von Oertzen, McArdle, Lindenberger, 2012, с. 71–86.

[_e6e3410f114d2c09-24] Painsky, Rosset, 2017, с. 2142–2153.

[25] CiteSeerX (неопр.). Дата обращения: 2 января 2019. Архивировано 21 марта 2008 года.

[26] Tan & Dowe (2003) (неопр.). Дата обращения: 2 января 2019. Архивировано 28 мая 2016 года.

[_fcd1eb7475cf18c8-27] Papagelis, Kalles, 2001, с. 393–400.

[_5cd802aa65053fad-28] Barros, Basgalupp, Carvalho, Freitas, 2012, с. 291–312.

[_84134221151a1806-29] Chipman, George, McCulloch, 1998, с. 935–948.

[_45d9bad0fe900a5c-30] Barros, Cerri, Jaskowiak, Carvalho, 2011, с. 450–456.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]