2.5 Метод
последовательного ветвления.
Данный метод представляет собой процедуру поэтапного ветвления, при котором на каждом шаге выбирается лучший вариант разделения.
Пусть задана максимально
допустимая сложность дерева (например, число листьев Mmax).
Метод состоит из следующих шагов (рис. 12).
1)
Разделить
корневую вершину на заданное число (две, три) новых вершин, перебрав по очереди все характеристики X1,...,Xn
и все варианты разделения по каждой характеристике; оставляется наилучший по
заданному критерию качества вариант разделения.
2)
Проверить
перспективность ветвления для каждой из новых висячих вершин; если какая-либо
вершина становится листом, присвоить ей соответствующее решение.
3)
Каждую
вершину не-лист разделить на новые вершины аналогично п.1.Если ветвление данной
вершины не приводит к улучшению качества дерева (или качество улучшается, но
меньше чем на величину заданного порога), то ветвление не производится; вершина
объявляется листом и ей приписывается решение.
Далее шаги 2,3 повторяются,
пока не останется более перспективных для ветвления вершин, либо не будет
достигнута максимально допустимая сложность дерева.
Рис.12
Описанный метод является
наиболее простым и быстрым в исполнении. Однако недостатком данного метода
является то, что при большой допустимой сложности и малом числе наблюдений
полученное дерево, как правило, является излишне «оптимистичным», т.е. ошибка
прогнозирования, определенная по обучающей выборке, будет намного меньше, чем «истинная»
ошибка. Этот эффект возникает из-за того, что наблюдения являются случайными, и
дерево, которое слишком «настроено» на них, улавливает также случайные закономерности.
Еще один недостаток
заключается в том, что в случае сложной зависимости между характеристиками
полученное решение, как правило, не будет совпадать с оптимальным. Это
объясняется тем, что на каждом шаге рассматривается только одна характеристика,
без учета ее взаимосвязи с другими.