Какие внутренние критерии определяют терминальность листа дерева
Что проверяют
Понимаете ли вы, когда алгоритм построения дерева перестаёт делить узел и как это связано с переобучением. Следом обычно просят показать остановку в коде или спрашивают, как подобрать max_depth и что такое post-pruning.
Как отвечать
Разделите критерии на внутренние, которые следуют из данных в узле, и пороги, которые задаются гиперпараметрами. Внутренние:
- чистота узла: все объекты одного класса или с одинаковым таргетом, impurity равна нулю, делить нечего;
- нет допустимого разбиения: у всех объектов одинаковые значения признаков, или ни одно разбиение не уменьшает Gini, энтропию или MSE;
- мало объектов: любое разбиение оставит в потомке меньше допустимого минимума.
Пороги в sklearn.tree.DecisionTreeClassifier:
max_depth: максимальная глубина, по умолчаниюNone, то есть без ограничения;min_samples_split: минимум объектов, чтобы узел можно было делить, по умолчанию 2;min_samples_leaf: минимум объектов в листе, по умолчанию 1;min_impurity_decrease: минимальный выигрыш по критерию для разбиения;max_leaf_nodes: предел числа листьев, дерево растёт от лучших разбиений.
В бустинге то же другими словами. В XGBoost это max_depth (по умолчанию 6), min_child_weight как минимальная сумма гессиана в потомке и gamma как минимальное снижение лосса. В LightGBM дерево растёт по листьям, и главный ограничитель это num_leaves, плюс min_data_in_leaf.
Добавьте, что хранит лист: долю классов в классификации, среднее таргета в регрессии, а в градиентном бустинге вес, посчитанный через суммы градиентов и гессианов.
Где спотыкаются
Называют «минимальную глубину» критерием остановки. Останавливает максимальная глубина, минимальной в стандартных реализациях нет.
Считают, что лист обязан быть чистым. С настройками по умолчанию дерево в sklearn действительно растёт до чистых листьев и переобучается, поэтому пороги задают почти всегда.
Путают pre-pruning и post-pruning. Пороги выше останавливают рост заранее, а ccp_alpha подрезает уже выращенное дерево по стоимости сложности, это разные инструменты.