Decision Trees

Последовательность вопросов «признак > порог», разбивающая пространство на прямоугольные области.

Gain = H (R) - \frac{∣ R _{ℓ} ∣}{∣ R ∣} H (R_{ℓ}) - \frac{∣ R _{r} ∣}{∣ R ∣} H (R_{r})

Что означает каждый компонент

$H (R)$ неоднородность до разбиения (Джини или энтропия)
$\frac{∣ R _{ℓ} ∣}{∣ R ∣} H (R_{ℓ})$ неоднородность левой части, взвешенная её долей объектов
$\frac{∣ R _{r} ∣}{∣ R ∣} H (R_{r})$ то же для правой части. Дерево выбирает порог, максимизирующий разность

Ключевые тезисы

Критерии разбиения: Gini и энтропия для классификации, дисперсия для регрессии.
Не требуют масштабирования и сами ловят нелинейности и взаимодействия.
Без ограничения глубины и обрезки переобучаются практически всегда.

Тема также относится к главам:Интерпретируемость моделейПрозрачные модели

Подробный разбор

3 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Устройство дерева

Корень, предикаты, листья — и как из них получается предсказание.

Каждый внутренний узел содержит предикат вида «признак $x_{j}$ > порог $t$ ». Объект спускается от корня к листу, отвечая на вопросы; в листе хранится ответ: доля классов или среднее значение цели.

Границы всегда параллельны осям — отсюда «лесенка» вместо наклонной прямой.
Дерево глубины $h$ разбивает пространство максимум на $2^{h}$ прямоугольных областей.
Пропуски и разные масштабы признаков дереву не мешают.

Критерий информативности и Information Gain

Как алгоритм выбирает лучший вопрос на каждом шаге.

Gain = H (R) - \frac{∣ R _{ℓ} ∣}{∣ R ∣} H (R_{ℓ}) - \frac{∣ R _{r} ∣}{∣ R ∣} H (R_{r})

Обозначения

$H (p)$ энтропия — мера неопределённости распределения
$r$ награда, полученная агентом на шаге

Прирост информации: насколько разбиение снизило неоднородность

H_{Gini} (R) = 1 - k \sum p_{k}^{2}, H_{entropy} (R) = - k \sum p_{k} lo g_{2} p_{k}

Обозначения

$p$ вероятность (или плотность распределения)
$k$ номер или количество: индекс шага, число соседей, кластеров или позиций
$\sum$ суммирование по всем перечисленным элементам
$lo g$ логарифм: превращает произведения в суммы и сжимает масштаб

Считаем

В узле 10 объектов: 6 класса 1 и 4 класса 0. $p_{1} = 0.6$ , Джини $= 1 - (0.36 + 0.16) = 0.48$ . Если разбиение даёт слева (5 объектов: 5 и 0) и справа (5 объектов: 1 и 4), то Gain $= 0.48 - 0.5 \cdot 0 - 0.5 \cdot 0.32 = 0.32$ .

H(корень)0.498

H(лево)0.375

H(право)0.245

Information Gain0.183

Порог предиката x > t0.50

Критерий информативности

Двигайте порог и следите за Information Gain — жадный алгоритм выбирает его максимум

Переобучение и стрижка

Дерево без ограничений всегда доучится до нулевой ошибки на train.

max_depth — самый понятный ограничитель сложности.
min_samples_leaf — не позволяет создавать листья из одного-двух объектов.
min_impurity_decrease — не делать разбиение, если выигрыш ничтожен.
Cost-Complexity Pruning (ccp_alpha) — сначала вырастить дерево, потом обрезать ветви, чей вклад не окупает сложности.

R_{α} (T) = R (T) + α ∣ листьев (T) ∣

Критерий стрижки: ошибка плюс штраф за размер дерева

Связанные темы

Деревья и ансамбли

Ключевые тезисы

Подробный разбор

Устройство дерева

Критерий информативности и Information Gain

Переобучение и стрижка

Связанные темы

Random Forest85%

Gradient Boosting85%

XGBoost85%

LightGBM85%

CatBoost85%

SHAP85%

Encoding85%