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

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

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

Обсуждение[править | править код]

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

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

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

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

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

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

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

Типы деревьев решений[править | править код]

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

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

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

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

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

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

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

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

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

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

Метрики[править | править код]

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

Примесь (критерий) Джини[править | править код]

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

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

${\displaystyle \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. используется Информационный выигрыш, который основывается на понятии энтропии и объёма информации из теории информации.

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

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

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

$${\displaystyle \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)}}}$$

${\displaystyle =-\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 точками данных. Для построения дерева решений по этим данным нам нужно сравнить информационный выигрыш каждого из четырёх деревьев, на которые расщепляется согласно одному из четырёх признаков. Расщепление с максимальным информационным выигрышем будет взято в качестве первого расщепления и процесс продолжается, пока все наследники не станут простыми или пока информационный выигрыш не станет нулём.

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

${\displaystyle 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}$

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

${\displaystyle 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}$

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

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

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

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

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

${\displaystyle IG}$ (ветер) ${\displaystyle =I_{E}([9,5])-I_{E}([3,3],[6,2])=0,940286-0,8921589=0,0481271}$

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

Понижение дисперсии[править | править код]

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

${\displaystyle 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)}$,

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

Применение[править | править код]

Преимущества[править | править код]

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

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

Ограничения[править | править код]

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

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

Реализации[править | править код]

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

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

Расширения[править | править код]

Графы решений[править | править код]

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

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

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

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

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

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

Литература для дальнейшего чтения[править | править код]

• 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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.