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

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

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

Обсуждение

Файл:CART tree titanic survivors (RU).svg

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

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

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

Дерево может быть «обучено» путём расщепления множества на подмножества, основываясь на проверку значений атрибутов. Этот процесс, повторяющийся на каждом полученном подмножестве рекурсивно, называется Шаблон:Не переведено 5. Рекурсия прекращается, когда подмножество в узле имеет одно и то же значение целевой переменной или когда разбиение не добавляет значения в предсказания. Этот процесс индукции сверху вниз деревьев решений (Шаблон:Lang-en, TDIDT)Шаблон:Sfn является примером жадного алгоритма, и служит наиболее часто применяемой стратегией обучения деревьев решений из данных.

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

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

$(\mathbf{\text{x}},Y)=(x_1,x_2,x_3,...,x_k,Y)$

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

Три различных представления дерева регрессии данных кифоза

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

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

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

• Анализ Шаблон:Не переведено 5, когда предсказываемый выход является классом, которому данные принадлежат.
• Анализ дерева регрессии, когда предсказываемый выход может считаться вещественным числом (например, цена дома или продолжительность нахождения пациента в больнице).

Термин анализ по дереву классификации и регрессии (Шаблон:Lang-en, CART) является обобщающим термином и он используется для обозначения двух упомянутых выше процедур, первую из которых ввели Брейман с соавторами в 1984Шаблон:Sfn. Деревья, используемые для регрессии, и деревья, используемые для классификации, имеют некоторую схожесть, однако имеют и отличия, такие как процедура, используемая для определения места расщепленияШаблон:Sfn.

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

• Шаблон:Не переведено 5 (Шаблон:Lang-en) строят шаг за шагом сборку путём тренировки каждого нового экземпляра, делая упор на тренировку ранее не попадающих в модель экземпляров. Типичным примером является AdaBoost. Это может быть использовано как для задач регрессионного типа, так и задач классификации Шаблон:SfnШаблон:Sfn.
• Бэггинг деревьев решений, ранний метод сборки, строящий несколько деревьев решений путём повторной выборки тренировочных данных с заменой и голосованием за деревья для согласования предсказанияШаблон:Sfn.
  • Классификатор на основе случайного леса является специфичным видом бэггинга
• Ротационный лес — подход, в котором каждое дерево решений сначала тренируется применением метода главных компонент (Шаблон:Lang-en, PCA) на случайном подмножестве входных признаковШаблон:Sfn.

Специальным случаем деревьев решений является Шаблон:Не переведено 5Шаблон:Sfn, который является односторонним деревом решений, так что любой внутренний узел имеет в точности 1 лист и в точности 1 внутренний узел в качестве наследника (за исключением самого нижнего узла, единственным наследником которого является один лист). Хотя эти списки менее выразительны, их легче понять, чем общие деревья решений, ввиду их разреженности, что разрешает применение методов обучения, не являющихся жаднымиШаблон:Sfn, а также позволяют наложение монотонных ограниченийШаблон:Sfn.

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

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

• ID3 (Шаблон:Lang-en)
• C4.5 (преемник алгоритма ID3)
• Классификация и регрессия построением дерева решений. (Шаблон:Lang-en, CART)
• Шаблон:Не переведено 5 (Шаблон:Lang-en, CHAID). Осуществляет многоуровневое расщепление при вычислении деревьев классификацииШаблон:Sfn.
• Шаблон:Не переведено 5 (Шаблон:Lang-en, MARS): расширяет деревья решений для лучшей обработки количественных данных.
• Деревья условного вывода (Шаблон:Lang-en). Подход на основе статистики, который использует непараметрические тесты в качестве критерия расщепления, скорректированные для многократного тестирования во избежание переобучения. Этот подход приводит к выбору несмещённого предсказателя и не требует обрезкиШаблон:SfnШаблон:Sfn.

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

Метрики

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

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

Шаблон:Не путать Используемый в алгоритме деревьев классификации и регрессии (Шаблон:Lang-en, CART) критерий Джини является мерой, насколько часто случайно выбранный элемент из набора неверно помечается, если он случайным образом помечается согласно распределению меток в подмножестве. Критерий Джини может быть вычислен путём суммирования вероятности $p_i$ элемента с выбранной меткой $i$, умноженной на вероятность $\sum _{k\ne i}{p}_k=1-p_i$ ошибки категоризации этого элемента. Критерий принимает минимум (нуль), когда все случаи в узле попадают в одну целевую категорию.

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

${\mathrm{I}}_G(p)=\sum _{i=1}^J{p}_i\sum _{k\ne 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)={\mathrm{I}}_E(p_1,p_2,...,p_J)=-\sum _{i=1}^J{p}_i{\log }_2{p}_i$,

где $p_1,p_2,...$ являются долями, в сумме дающими 1, которые представляют процент каждого класса, полученный от разбиения в деревеШаблон:Sfn.

$$\stackrel{\text{Information Gain}}{\overbrace{IG(T,a)}}=\stackrel{\text{Entropy (parent)}}{\overbrace{\mathrm{H}(T)}}-\stackrel{\text{Weighted Sum of Entropy (Children)}}{\overbrace{\mathrm{H}(T|a)}}$$$=-\sum _{i=1}^J{p}_i{\log }_2{p}_i-\sum _{a}p(a)\sum _{i=1}^J-\mathrm{Pr}(i|a){\log }_2\mathrm{Pr}(i|a)$

В формуле

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

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

Рассмотрим пример набора данных с четырьмя атрибутами: погода (солнечно, облачно, дождь), температура (жарко, мягкая погода, холодно), влажность (высокая, нормальная) и ветер (есть, нет) с бинарной целевой переменной (да или нет) игра и 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$

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

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

Представленное в CARTШаблон:Sfn понижение дисперсии часто используется в случаях, когда целевая переменная непрерывна (дерево регрессии), это означает, что использование многих других метрик требовало бы дискретизации перед применением. Понижение дисперсии узла Шаблон:Mvar определяется как общее сокращение дисперсии целевой переменной Шаблон:Mvar как следствие расщепления в этом узле:

$I_V(N)=\frac{1}{|S{|}^2}\sum _{i\in S}\sum _{j\in S}\frac{1}{2}(x_i-x_j{)}^2-(\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)$,

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

Применение

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

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

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

Ограничения

• Деревья могут оказаться существенно неустойчивыми. Небольшие изменения в Шаблон:Не переведено 5 могут привести к существенным изменения в дереве, а в конце концов и к конечным предсказаниямШаблон:Sfn.
• Известно, что задача обучения до оптимального дерева решений NP-полна по некоторым вопросам оптимальности и даже для простых концепцийШаблон:SfnШаблон:Sfn. Как следствие, практические обучающие алгоритмы дерева решений основаны на эвристике, такой как жадный алгоритм, когда локальные оптимальные решения принимаются для каждого узла. Такие алгоритмы не могут гарантировать получение глобально оптимального дерева решений. Чтобы уменьшить эффект локальной оптимальности, предлагаются некоторые методы, такие как дерево двойственного информационного расстояния (Шаблон:Lang-en, DID)Шаблон:Sfn.

• Обучение дерева решений может создать сверхсложные деревья, которые не обобщаются хорошо из тренировочных данных (что известно как переобучениеШаблон:Sfn). Механизмы, такие как Шаблон:Не переведено 5, становятся необходимыми для избежания этой проблемы (за исключением некоторых алгоритмов, таких подходов, как условное умозаключение (Шаблон:Lang-en), которое не требует обрезки)Шаблон:SfnШаблон:Sfn.
• Для данных, имеющих качественные переменные с различным числом уровней Шаблон:Не переведено 5 смещён в сторону атрибутов с бо́льшими уровнямиШаблон:Sfn. Однако проблема смещения с помощью условного умозаключенияШаблон:Sfn, двухступенчатого подходаШаблон:Sfn или адаптивного отбора признаков по отдельным объектамШаблон:Sfn.

Реализации

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

Примерами служат Salford Systems CART (который лицензировал проприетарный код оригинальных авторов CART)Шаблон:Sfn, Шаблон:Не переведено 5, Шаблон:Не переведено 5, Шаблон:Не переведено 5, Matlab, R (программное обеспечение с открытым кодом для статистических вычислений, которое включает несколько реализаций CART, таких как пакеты rpart, party и randomForest), Weka (свободно распространяемый пакет программ с открытым кодом для интеллектуального анализа данных, содержащий много алгоритмов дерева решений), Шаблон:Не переведено 5, Шаблон:Не переведено 5, Microsoft SQL Server [1] и scikit-learn (свободно распространяемая библиотека на языке Python с открытым кодом для машинного обучения).

Расширения

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

В дереве решений все пути из корневого узла к листу идут через конъюнкцию (AND). В графе решений возможно использование дизъюнкции (OR) для объединения путей с помощью сообщения минимальной длины (Шаблон:Lang-en, MML) . Графы решений расширяются далее с разрешением до этого не использованных атрибутов обучать динамически и использовать в различных местах графа. Более общая схема кодирования приводит к лучшим предсказаниям и показателям логарифмических потерь. В общем случае графы решений дают модели с меньшим числом листьев, чем деревья решений.

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

Эволюционные алгоритмы использовались для исключения локальных оптимальных решений и поиска деревьев решений с меньшим априорным смещениемШаблон:SfnШаблон:Sfn.

Можно упростить деревья с помощью метода Монте-Карло для цепей Маркова (Шаблон:Lang-en, MCMC)Шаблон:Sfn.

Дерево можно просматривать снизу вверхШаблон:Sfn.

См. также

• Шаблон:Не переведено 5
• Бинарная диаграмма решений
• Шаблон:Не переведено 5
• CART
• ID3 (алгоритм)
• Алгоритм C4.5
• Шаблон:Не переведено 5, используются, например, в алгоритме AdaBoost
• Шаблон:Не переведено 5
• Шаблон:Не переведено 5
• Шаблон:Не переведено 5
• Шаблон:Не переведено 5
• Шаблон:Не переведено 5
• Иерархическая кластеризацияШаблон:Div col end

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга

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

• Шаблон:Книга

Ссылки

• 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