Глоссарий

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

Отсечение ветвей дерева решений производится в направлении, противоположном «росту» дерева, т.е. снизу вверх, путем преобразования узлов в листья. Фактически при отсечении ветвей создается множество поддеревьев в порядке увеличения их сложности. Затем выбирается дерево, оптимальное с точки зрения некоторого критерия. Чтобы добиться максимальной обобщающей способности, выбирают дерево с наименьшей ошибкой на валидационном множестве. Иногда используют и ошибку обучения: полное дерево имеет нулевую ошибку обучения, когда все примеры распознаны. По мере упрощения в нем появляются ошибки, т.е. примеры, попавшие в узел, ассоциированный с другим классам. Можно задаться допустимой величиной ошибки и отсекать ветви до тех пор, пока ошибка дерева не станет больше допустимой. Еще одним критерием может быть минимальное число примеров в узле: отсекаются все узлы, число примеров в которых больше заданного.

Отсечение ветвей является более затратной в вычислительном плане процедурой, чем ранняя остановка. Однако ранняя остановка имеет риск потери потенциально интересных правил, до которых алгоритм может просто не «дойти».