Решающие деревья
Знакомимся с деревьями решений — интуитивно понятная модель, которая лежит в основе всех ансамблей.
Как работает решающее дерево
Представь, что ты врач и пытаешься поставить диагноз. Ты задаёшь вопросы по очереди: «Температура выше 38?» → «Есть кашель?» → «Длится больше 3 дней?». Каждый ответ ведёт к следующему вопросу или к финальному диагнозу.
Решающее дерево (Decision Tree) работает точно так же. Оно разбивает пространство признаков последовательными вопросами вида «признак X > порог T?». В каждом узле выбирается тот признак и порог, которые лучше всего разделяют данные.
Разбиение пространства признаков
Каждый узел дерева — это разделение по одному признаку. В результате пространство признаков нарезается на прямоугольные области (для двумерного случая — буквально прямоугольники).
- Корневой узел (root) — первое разбиение, покрывающее все данные
- Внутренние узлы — промежуточные разбиения
- Листья (leaves) — конечные области, в которых модель выдаёт предсказание
- Для классификации — лист выдаёт класс большинства; для регрессии — среднее значение
Критерии разбиения: Gini и Entropy
Как дерево выбирает, по какому признаку и порогу разделить? Оно перебирает все возможные варианты и выбирает тот, который лучше всего уменьшает «примесь» (impurity) в получившихся группах.
Gini Impurity
Где pᵢ — доля объектов класса i в узле. Gini = 0, когда все объекты в узле одного класса (идеальная чистота). Gini максимален, когда классы распределены равномерно.
Entropy (Information Gain)
Энтропия из теории информации. Тоже измеряет «неопределённость» в узле. Entropy = 0 → все объекты одного класса. Information Gain — это разница энтропий до и после разбиения.
🎤 В чём разница между Gini и Entropy? На практике — почти нет
Оба критерия дают очень похожие деревья. Gini чуть быстрее (не нужен логарифм). Entropy чуть больше «стремится» к чистым узлам. В sklearn по умолчанию используется Gini. На собесе достаточно знать формулы обоих и сказать, что на практике разница минимальна.
Переобучение и как с ним бороться
Главная проблема решающих деревьев — переобучение. Без ограничений дерево может расти до тех пор, пока каждый лист не будет содержать ровно один объект. Такое дерево идеально запомнит обучающую выборку, но будет бесполезно на новых данных.
Способы ограничения
- max_depth — максимальная глубина дерева. Самый важный гиперпараметр
- min_samples_split — минимальное число объектов для разбиения узла
- min_samples_leaf — минимальное число объектов в листе
- max_leaf_nodes — максимальное число листьев
- Pruning (обрезка) — строим полное дерево, потом убираем ветки, которые не улучшают качество на валидации
Преимущества и недостатки
Преимущества
- Интерпретируемость — дерево можно визуализировать и объяснить бизнесу
- Не нужна нормализация данных
- Работает с числовыми и категориальными признаками
- Автоматически обрабатывает нелинейные зависимости
- Быстрое предсказание (O(log n) по глубине)
Недостатки
- Нестабильность — небольшое изменение данных → совсем другое дерево
- Склонность к переобучению без ограничений
- Границы решений всегда параллельны осям (не может поставить диагональную границу)
- Жадный алгоритм — выбирает лучший сплит «сейчас», не думая о будущем
Именно из-за нестабильности...
...были придуманы ансамбли: Random Forest и градиентный бустинг. Одно дерево нестабильно → объединяем много деревьев → получаем стабильный и мощный классификатор. Об этом — в следующих разделах.
Итого
- Дерево последовательно разбивает пространство признаков вопросами «признак > порог?»
- Критерии разбиения: Gini = 1 − Σpᵢ², Entropy = −Σpᵢlog₂pᵢ
- Главная проблема — переобучение. Лечится ограничением глубины и pruning
- Плюс: интерпретируемость. Минус: нестабильность
- Одно дерево — слабый ученик. Много деревьев — ансамбль (RF, бустинг)