Методы классификации и прогнозирования. Деревья решений
На сегодняшний день существует большое число алгоритмов, реализующих деревья решений: CART , C4.5, CHAID, CN2, NewId, ITrule и другие.
Алгоритм CART
Алгоритм CART ( Classification and Regression Tree), как видно из названия, решает задачи классификации и регрессии. Он разработан в 1974-1984 годах четырьмя профессорами статистики — Leo Breiman (Berkeley), Jerry Friedman (Stanford), Charles Stone (Berkeley) и Richard Olshen (Stanford).
Атрибуты набора данных могут иметь как дискретное, так и числовое значение.
Алгоритм CART предназначен для построения бинарного дерева решений . Бинарные деревья также называют двоичными. Пример такого дерева рассматривался в начале лекции.
Другие особенности алгоритма CART :
- функция оценки качества разбиения;
- механизм отсечения дерева;
- алгоритм обработки пропущенных значений;
- построение деревьев регрессии.
Каждый узел бинарного дерева при разбиении имеет только двух потомков, называемых дочерними ветвями. Дальнейшее разделение ветви зависит от того, много ли исходных данных описывает данная ветвь . На каждом шаге построения дерева правило , формируемое в узле, делит заданное множество примеров на две части. Правая его часть ( ветвь right) — это та часть множества, в которой правило выполняется; левая ( ветвь left) — та, для которой правило не выполняется.
Функция оценки качества разбиения, которая используется для выбора оптимального правила , — индекс Gini — был описан выше. Отметим, что данная оценочная функция основана на идее уменьшения неопределенности в узле. Допустим, есть узел, и он разбит на два класса. Максимальная неопределенность в узле будет достигнута при разбиении его на два подмножества по 50 примеров, а максимальная определенность — при разбиении на 100 и 0 примеров.
Правила разбиения. Напомним, что алгоритм CART работает с числовыми и категориальными атрибутами. В каждом узле разбиение может идти только по одному атрибуту. Если атрибут является числовым, то во внутреннем узле формируется правило вида xi внутреннем узле формируется правило xi V(xi), где V(xi) — некоторое непустое подмножество множества значений переменной xi в обучающем наборе данных.
Механизм отсечения. Этим механизмом, имеющим название minimal cost-complexity tree pruning , алгоритм CART принципиально отличается от других алгоритмов конструирования деревьев решений. В рассматриваемом алгоритме отсечение — это некий компромисс между получением дерева «подходящего размера» и получением наиболее точной оценки классификации. Метод заключается в получении последовательности уменьшающихся деревьев, но деревья рассматриваются не все, а только «лучшие представители».
Перекрестная проверка (V- fold cross-validation) является наиболее сложной и одновременно оригинальной частью алгоритма CART . Она представляет собой путь выбора окончательного дерева, при условии, что набор данных имеет небольшой объем или же записи набора данных настолько специфические, что разделить набор на обучающую и тестовую выборку не представляется возможным.
Итак, основные характеристики алгоритма CART : бинарное расщепление, критерий расщепления — индекс Gini, алгоритмы minimal cost-complexity tree pruning и V- fold cross-validation, принцип «вырастить дерево, а затем сократить», высокая скорость построения, обработка пропущенных значений.
Алгоритм C4.5
Алгоритм C4.5 строит дерево решений с неограниченным количеством ветвей у узла. Данный алгоритм может работать только с дискретным зависимым атрибутом и поэтому может решать только задачи классификации. C4.5 считается одним из самых известных и широко используемых алгоритмов построения деревьев классификации.
Для работы алгоритма C4.5 необходимо соблюдение следующих требований:
- Каждая запись набора данных должна быть ассоциирована с одним из предопределенных классов, т.е. один из атрибутов набора данных должен являться меткой класса.
- Классы должны быть дискретными. Каждый пример должен однозначно относиться к одному из классов.
- Количество классов должно быть значительно меньше количества записей в исследуемом наборе данных.
Последняя версия алгоритма — алгоритм C4.8 — реализована в инструменте Weka как J4.8 (Java). Коммерческая реализация метода: C5.0, разработчик RuleQuest, Австралия.
Алгоритм C4.5 медленно работает на сверхбольших и зашумленных наборах данных.
Мы рассмотрели два известных алгоритма построения деревьев решений CART и C4.5. Оба алгоритма являются робастными, т.е. устойчивыми к шумам и выбросам данных.
Алгоритмы построения деревьев решений различаются следующими характеристиками:
- вид расщепления — бинарное (binary), множественное (multi-way)
- критерии расщепления — энтропия, Gini, другие
- возможность обработки пропущенных значений
- процедура сокращения ветвей или отсечения
- возможности извлечения правил из деревьев.
Ни один алгоритм построения дерева нельзя априори считать наилучшим или совершенным, подтверждение целесообразности использования конкретного алгоритма должно быть проверено и подтверждено экспериментом.
Разработка новых масштабируемых алгоритмов
Наиболее серьезное требование, которое сейчас предъявляется к алгоритмам конструирования деревьев решений — это масштабируемость, т.е. алгоритм должен обладать масштабируемым методом доступа к данным.
Разработан ряд новых масштабируемых алгоритмов, среди них — алгоритм Sprint, предложенный Джоном Шафером и его коллегами [36]. Sprint, являющийся масштабируемым вариантом рассмотренного в лекции алгоритма CART , предъявляет минимальные требования к объему оперативной памяти.
Выводы
В лекции мы рассмотрели метод деревьев решений; определить его кратко можно как иерархическое, гибкое средство предсказания принадлежности объектов к определенному классу или прогнозирования значений числовых переменных.
Качество работы рассмотренного метода деревьев решений зависит как от выбора алгоритма, так и от набора исследуемых данных. Несмотря на все преимущества данного метода, следует помнить, что для того, чтобы построить качественную модель, необходимо понимать природу взаимосвязи между зависимыми и независимыми переменными и подготовить достаточный набор данных.
Источник