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