Методы классификации и прогнозирования. Деревья решений
На сегодняшний день существует большое число алгоритмов, реализующих деревья решений: 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 , предъявляет минимальные требования к объему оперативной памяти.
Выводы
В лекции мы рассмотрели метод деревьев решений; определить его кратко можно как иерархическое, гибкое средство предсказания принадлежности объектов к определенному классу или прогнозирования значений числовых переменных.
Качество работы рассмотренного метода деревьев решений зависит как от выбора алгоритма, так и от набора исследуемых данных. Несмотря на все преимущества данного метода, следует помнить, что для того, чтобы построить качественную модель, необходимо понимать природу взаимосвязи между зависимыми и независимыми переменными и подготовить достаточный набор данных.
Источник
31. Алгоритм cart построения дерева решений
алгоритм CART (Classification and Regression Tree – деревья классификации и регрессии). Деревья решений, построенные с помощью алгоритма CART, являются бинарными, то есть содержат только два потомка в каждом узле.
Пусть задано обучающее множество, содержащее примеров и классов. В алгоритме используется показатель эффективности разбиения, полученного на основе конкретного атрибута
где – показатель эффективности, – идентификатор разбиения, – идентификатор узла;
и – левый и правый потомки узла ;
– отношение числа примеров в левом потомке узла к общему числу примеров;
– отношение числа примеров в правом потомке узла к общему числу примеров;
– отношение числа примеров ‑ro класса в к общему числу примеров в ;
– отношение числа примеров ‑ro класса в к общему числу примеров в .
Тогда наилучшим разбиением в узле будет то, которое максимизирует показатель .
32. Принципы упрощения деревьев решений
Формально дерево решений будет строиться до тех пор, пока могут быть найдены новые разбиения, пока не будут получены абсолютно чистые листья или пока листья не будут содержать только одно наблюдение. В результате будет построено так называемое полное дерево. Полное дерево может быть сложным, те есть содержать много узлов и листьев. Полное дерево, как правило, является результатом переобучения (overfitting), то есть адаптации модели к частным случаям, нетипичным примерам, шумам в данных и т. п. Такое дерево идеально работает на обучающем множестве, но может давать много ошибок на тестовом множестве, на котором сеть не обучалась.
Другой крайностью является недообучение (underfitting). Недообученное дерево получается слишком простым, содержит мало разбиений и не обеспечивает высокую точность обучения.
Таким образом, необходимо найти баланс между точностью и сложностью дерева. Для этого используется комплекс методов, называемый упрощение дерева решений (pruning – отсечение, обрезка ветвей или reduction – сокращение, уменьшение).
Известны два основных подхода к выбору оптимальной сложности дерева решений [1]:
– ранняя остановка (preprunning);
– отсечение ветвей (postprunning).
Ранняя остановка означает, что при достижении некоторого условия рост дерева останавливается. В качестве условий остановки роста дерева принимают следующие:
– ошибка дерева: если отношение числа неправильно классифицированных записей к общему числу записей, поступивших в корневой узел, станет меньше заданной величины, то дальнейший рост дерева останавливается;
– минимальное допустимое количество примеров в узле: рост дерева останавливается, если количество примеров в узле станет меньше заданного;
– глубина дерева: задается допустимое число разбиений для каждой ветви;
– статистическая значимость разбиений: разбиение прекращается, если в результате разбиение примеров оказывается статистически незначимым, то то разбиение следует прекратить.
Идею отсечения ветвей рассмотрим на примере алгоритма CART [1, 15]. Для отсечения ветвей вводится понятие скорректированной ошибки дерева (поддерева)
где – показатель количества ошибок (в простейшем случае это количество ошибок классификации, допущенных деревом в данном узле); – число листов (терминальных узлов) дерева, – некоторый параметр, который постепенно увеличивается по мере создания новых поддеревьев.
Скорректированная ошибка дерева состоит из двух компонент – ошибки классификации дерева и штрафа за его сложность. Тогда менее ветвистое дерево, дающее большую ошибку классификации, будет иметь меньшую скорректированную ошибку, чем дерево, дающее меньшую ошибку, но более ветвистое.
Сначала строится полное дерево, а затем производится его упрощение путем отсечения ветвей. Для этого находятся все поддеревья‑кандидаты. Первым кандидатом является полное дерево. Остальные поддеревья получаются отсечение листьев (все кандидаты содержат корневой узел). Для каждого кандидата вычисляется скорректированная ошибка. Если скорректированная ошибка поддерева меньше скорректированной ошибки полного дерева, то данное поддерево является кандидатом на модель.
Когда определены все поддеревья‑кандидаты, из них выбирается лучшее, дающее наименьшую ошибку на тестовых данных, на которых дерево не обучалось. Рассмотренную процедуру можно применить к выбранному поддереву т. д., пока ошибка не превысит допустимую величину.
Ранняя остановка проще отсечения ветвей, но возникает риск потери хороших разбиений, которые могут следовать за плохими. Поэтому отсечение ветвей, как правило, дает лучшие результаты и шире используется
Источник