Обучение дерева решений использует дерево решений (как ), чтобы перейти от наблюдений над объектами (представленными в ветвях) к заключениям о целевых значениях объектов (представленных в листьях). Это обучение является одним из подходов моделирования предсказаний, используемых в статистике, интеллектуальном анализе данных и машинном обучении. Модели деревьев, в которых целевая переменная может принимать дискретный набор значений, называются деревьями классификации. В этих структурах деревьев листья представляют метки классов, а ветки представляют конъюнкции признаков, которые ведут в эти метки классов. Деревья решений, в которых целевая переменная может принимать непрерывные значения (обычно, вещественные числа) называются деревьями регрессии.
В анализе решений может быть использовано дерево решений для визуального и явного представления принятия решений. При интеллектуальном анализе данных дерево решений описывает данные, но результирующее дерево классификации может быть входом для принятия решений. Эта страница имеет дело с деревьями решений при интеллектуальном анализе данных.
Обучение
Обучение дерева решений — это метод, обычно используемый в интеллектуальном анализе данных. Целью является создание модели, которая предсказывает значение целевой переменной, основываясь на некоторых входных переменных. Пример показан на диаграмме справа. Каждый внутренний узел соответствует одной из входных переменных. Есть рёбра к потомкам для каждого возможного значения этой входной переменной. Каждый лист представляет значение целевой переменной, которое определяется значениями входных переменных от корня до листа.
Дерево решений является простым представлением для примеров классификации. Для данного раздела предположим, что все входные признаки представлены конечными дискретными множествами и имеется единственный целевой признак, называемый «классификацией». Каждый элемент классификации называется классом. Дерево решений или дерево классификации — это дерево, в котором каждый внутренний (нелистовой) узел помечен входным признаком. Дуги, исходящие из узла, помеченного входным параметром, помечаются всеми возможными значениями выходного признака или дуга ведёт в подчинённый узел решения с другим входным признаком. Каждый лист дерева помечается классом или распределением вероятности по классам.
Дерево может быть «обучено» путём расщепления множества на подмножества, основываясь на проверку значений атрибутов. Этот процесс, повторяющийся на каждом полученном подмножестве рекурсивно, называется . Рекурсия прекращается, когда подмножество в узле имеет одно и то же значение целевой переменной или когда разбиение не добавляет значения в предсказания. Этот процесс индукции сверху вниз деревьев решений (, TDIDT) является примером жадного алгоритма, и служит наиболее часто применяемой стратегией обучения деревьев решений из данных.
При интеллектуальном анализе данных деревья решений могут быть описаны также как комбинация математических и вычислительных техник с целью описания, категоризации и обобщения заданного набора данных.
Данные приходят в виде записей вида:
Зависимая переменная Y является целевой переменной, которую мы пытаемся понять, классифицировать или обобщить. Вектор x составлен из признаков x1, x2, x3 и т. д., которые используются для задачи.
Типы деревьев решений Деревья решений используются при интеллектуальном анализе данных и бывают двух основных типов:
Анализ , когда предсказываемый выход является классом, которому данные принадлежат. Анализ дерева регрессии, когда предсказываемый выход может считаться вещественным числом (например, цена дома или продолжительность нахождения пациента в больнице).
Термин анализ по дереву классификации и регрессии (, CART) является обобщающим термином и он используется для обозначения двух упомянутых выше процедур, первую из которых ввели Брейман с соавторами в 1984. Деревья, используемые для регрессии, и деревья, используемые для классификации, имеют некоторую схожесть, однако имеют и отличия, такие как процедура, используемая для определения места расщепления.
Некоторые техники, часто называемые методами сборки, строят более одного дерева решений: () строят шаг за шагом сборку путём тренировки каждого нового экземпляра, делая упор на тренировку ранее не попадающих в модель экземпляров. Типичным примером является AdaBoost. Это может быть использовано как для задач регрессионного типа, так и задач классификации . Бэггинг деревьев решений, ранний метод сборки, строящий несколько деревьев решений путём повторной выборки тренировочных данных с заменой и голосованием за деревья для согласования предсказания. Классификатор на основе случайного леса является специфичным видом бэггинга Ротационный лес — подход, в котором каждое дерево решений сначала тренируется применением метода главных компонент (, PCA) на случайном подмножестве входных признаков.
Специальным случаем деревьев решений является , который является односторонним деревом решений, так что любой внутренний узел имеет в точности 1 лист и в точности 1 внутренний узел в качестве наследника (за исключением самого нижнего узла, единственным наследником которого является один лист). Хотя эти списки менее выразительны, их легче понять, чем общие деревья решений, ввиду их разреженности, что разрешает применение методов обучения, не являющихся жадными, а также позволяют наложение монотонных ограничений.
Обучение дерева решений является построением дерева решений из помеченных классами тренировочных кортежей. Дерево решений является структурой, подобной блок-схеме, в которой каждый внутренний (нелистовой) узел означает тест атрибута, каждая ветвь представляет результат теста, а каждый лист (терминальный узел) содержит метку класса. Верхняя вершина является корневым узлом.
Есть много алгоритмов деревьев решений. Наиболее заметные из них:
ID3 () C4.5 (преемник алгоритма ID3) Классификация и регрессия построением дерева решений. (, CART) (, CHAID). Осуществляет многоуровневое расщепление при вычислении деревьев классификации. (, MARS): расширяет деревья решений для лучшей обработки количественных данных. Деревья условного вывода (). Подход на основе статистики, который использует непараметрические тесты в качестве критерия расщепления, скорректированные для многократного тестирования во избежание переобучения. Этот подход приводит к выбору несмещённого предсказателя и не требует обрезки.
ID3 и CART были разработаны независимо и примерно в одно и то же время (между 1970 и 1980 гг.), однако используют близкие подходы для обучения дерева решений из тренировочных кортежей.
Метрики Алгоритмы построения деревья решений обычно работают сверху вниз путём выбора переменной на каждом шаге, которая лучшим образом разбивает множество элементов. Разные алгоритмы используют различные метрики для измерения «лучшего» решения. Они обычно измеряют однородность целевой переменной на подмножествах. Некоторые примеры даны ниже. Эти метрики применяются к каждому подмножеству и получающиеся значения комбинируются (например, вычисляется среднее) для получения меры качества разбиения.
Примесь (критерий) Джини
Используемый в алгоритме деревьев классификации и регрессии (, CART) критерий Джини является мерой, насколько часто случайно выбранный элемент из набора неверно помечается, если он случайным образом помечается согласно распределению меток в подмножестве. Критерий Джини может быть вычислен путём суммирования вероятности элемента с выбранной меткой , умноженной на вероятность ошибки категоризации этого элемента. Критерий принимает минимум (нуль), когда все случаи в узле попадают в одну целевую категорию.
Для вычисления критерия Джини для набора элементов с классами, предположим, что , и пусть будет долей элементов, помеченных классом в наборе.
Информационный выигрыш
В алгоритмах генерации деревьев ID3, C4.5 и C5.0. используется Информационный выигрыш, который основывается на понятии энтропии и объёма информации из теории информации.
Энтропия определяется следующим образом
, где являются долями, в сумме дающими 1, которые представляют процент каждого класса, полученный от разбиения в дереве.
В формуле Information Gain=Информационный выигрыш Entropy (parent)=Энтропия (родитель) Weighted Sum of Entropy (Children)=Взвешенная сумма энтропии (наследники)
Информационный выигрыш используется для принятия решения, какой признак использовать для расщепления на каждом шаге построения дерева. Простота является лучшим выбором, так что мы хотим сохранять дерево небольшим. Чтобы это сделать, на каждом шаге нам следует выбрать расщепление, которое приводит к простейшим узлам-наследникам. Обычно используемая мера простоты называется информацией, которая измеряется в битах. Для каждого узла дерева значение информации «представляет ожидаемое количество, которая нужна для определения, должен ли новый объект классифицирован как да или нет, если дано, что пример достигает этого узла».
Рассмотрим пример набора данных с четырьмя атрибутами: погода (солнечно, облачно, дождь), температура (жарко, мягкая погода, холодно), влажность (высокая, нормальная) и ветер (есть, нет) с бинарной целевой переменной (да или нет) игра и 14 точками данных. Для построения дерева решений по этим данным нам нужно сравнить информационный выигрыш каждого из четырёх деревьев, на которые расщепляется согласно одному из четырёх признаков. Расщепление с максимальным информационным выигрышем будет взято в качестве первого расщепления и процесс продолжается, пока все наследники не станут простыми или пока информационный выигрыш не станет нулём.
Расщепление, использующее признак ветер, приводит к двум узлам-наследникам, один узел для признака ветер со значением есть и один со значением нет. В этом наборе данных имеется шесть точек данных со значением есть для ветер, три имеют для целевого значения игра значение да и три имеют значение нет. Восемь оставшихся точек данных для параметра ветер со значением нет содержат два нет и шесть да. Информация ветер=да узла вычисляется с помощью уравнения для энтропии выше. Поскольку имеется равное число да и нет в этом узле, мы имеем
Для узла с ветер=нет имелось восемь точек данных, шесть с целевым значением да и два с нет. Таким образом, мы имеем
Чтобы найти информацию разбиения, вычислим взвешенное среднее этих двух чисел на основе количества наблюдений, попавших в каждый узел.
(ветер — да или нет)
Чтобы найти информационный выигрыш расщепления с помощью ветер, мы должны вычислить информацию в данных до расщепления. Исходные данные содержали девять да и пять нет.
Теперь мы можем вычислить информационный выигрыш, получаемый расщеплением по признаку ветер.
(ветер)
Чтобы построить дерево, нужно вычислить информационный выигрыш каждого возможного первого расщепления. Лучшее первое расщепление, это то, которое даёт наибольший информационный выигрыш. Этот процесс повторяется для каждого узла (со смешанными признаками), пока дерево не будет построено. Этот пример заимствован из статьи Виттена, Франка и Холла.
Понижение дисперсии Представленное в CART понижение дисперсии часто используется в случаях, когда целевая переменная непрерывна (дерево регрессии), это означает, что использование многих других метрик требовало бы дискретизации перед применением. Понижение дисперсии узла определяется как общее сокращение дисперсии целевой переменной как следствие расщепления в этом узле:
,
где , и являются множеством индексов до расщепления, множеством индексов, для которых тест даёт true и множеством индексов, для которых тест даёт false соответственно. Каждое из слагаемых выше является оценкой величины отклонения, хотя и записанной без прямой ссылки на среднее.
Применение
Преимущества Среди других методов анализа данных деревья решений имеют ряд преимуществ: Легки для понимания и интерпретации. Люди способны понять модели деревьев решений после краткого объяснения. Деревья можно изобразить графически таким образом, что их легко интерпретировать, не будучи экспертом.