На обучении дерево почти не ошибается, но на валидации заметно проигрывает. Объясните, как post pruning по cost complexity выбирает, какие поддеревья удалить, и как в этом участвует параметр α.

Question

Accepted Answer

Cost complexity pruning минимизирует сумму ошибки дерева и штрафа за его сложность: \ R \alpha T =R T +\alpha\cdot|	ext{листья}|\ . Для каждого внутреннего узла сравнивают качество его поддерева с качеством одного листа, которым это поддерево можно заменить; удаляют поддеревья, дающие наименьший прирост ошибки на каждый убранный лист. При росте α штраф за число листьев усиливается, поэтому выбираются всё более компактные вложенные деревья. Значение α подбирают по кросс валидации: цель — снизить переобучение и улучшить обобщающую способность, а не получить минимальную ошибку на обучающей выборке.