2.6 Метод усечения.
Как было отмечено, описанный выше простейший метод
построения дерева может давать излишне «оптимистичное» решение. В этом методе
оценивание качества дерева проводится по той же самой обучающей выборке, по которой
и строится дерево решений.
Для более объективной оценки
и отсеивания случайных закономерностей нужно использовать выборку, которая не
участвовала в построении дерева.
В методе усечения обучающая
выборка делится на две части. Первая часть используется для построения дерева
методом последовательного ветвления, причем параметры правила остановки
задаются такими, чтобы обеспечить максимально возможную точность полученного
решения, при этом число листьев дерева будет очень большим.
Вторая часть выборки служит
для усечения («упрощения») полученного дерева. Для этого выполняются следующие
шаги.
1)
Рассматриваются
по очереди все внутренние вершины дерева.
2)
Проводится
операция усечения для рассматриваемой вершины.
3)
Оценивается
ошибка прогнозирования для усеченного варианта дерева по второй части выборки.
Вариант, для которого ошибка минимальна, и выступает в качестве результата (рис. 13).
Рис.13
Описанный метод дает более
объективную оценку качества, однако если первоначальное дерево далеко от
оптимального, то и усеченный вариант будет также неидеальным.