Решающие деревья и ансамбли

1. Как строится решающее дерево?

Процесс построения (жадный алгоритм):

1. Начинаем с корня (все данные)
2. Выбираем лучший признак и порог для разделения
   - Для каждого признака перебираем возможные пороги
   - Считаем, насколько разделение улучшит качество
   - Выбираем лучший вариант
3. Делим данные на две части
4. Рекурсивно повторяем для каждой части
5. Останавливаемся, когда:
   - Все объекты в узле одного класса
   - Достигли максимальной глубины
   - В узле слишком мало объектов

Критерии разделения:

• Классификация:
• Джини (Gini): $Gini = 1 - Σ(p_i²)$
• Энтропия (Entropy): $H = -Σ(p_i·log(p_i))$
• Регрессия:
• MSE (Mean Squared Error): $MSE = \frac{1}{n}Σ(y_i - \hat{y})²$

Простой пример:

"Купить квартиру?"
├── Цена > 10 млн? (Да/Нет)
│   ├── Да → Район = центр? → [Да: покупаем, Нет: не покупаем]
│   └── Нет → Метро рядом? → [Да: покупаем, Нет: смотрим дальше]

---

2. Плюсы и минусы дерева

✅ Плюсы:

1. Интерпретируемость — можно понять логику решений
2. Нужна минимальная подготовка данных:
   - Работает с категориальными признаками
   - Не требует масштабирования
   - Устойчив к выбросам
3. Быстрое обучение и предсказание
4. Улавливает нелинейные зависимости

❌ Минусы:

1. Склонность к переобучению — главная проблема!
2. Нестабильность — небольшое изменение данных может дать совсем другое дерево
3. Плохо работает с линейными зависимостями (лучше линейная модель)
4. Жадный алгоритм — может не найти глобальный оптимум
5. Проблемы с экстраполяцией — плохо предсказывает вне диапазона обучения

---

3. Как регуляризировать дерево?

Регуляризация = ограничение сложности

Основные гиперпараметры:

1. max_depth — максимальная глубина дерева
   - Чем меньше, тем проще модель
   - Обычно: 3-10 для ансамблей, 10-30 для одиночного дерева

2. min_samples_split — минимальное число объектов для разделения узла
   - Пример: min_samples_split=10 → не делим узлы с <10 объектов

3. min_samples_leaf — минимальное число объектов в листе
   - Пример: min_samples_leaf=5 → в каждом листе ≥5 объектов

4. max_features — максимальное число признаков для поиска разделения
   - Пример: max_features=5 → смотрим только 5 случайных признаков

5. ccp_alpha — параметр обрезки (Cost Complexity Pruning)
   - Автоматически удаляет незначимые ветви

Практика:

# Хорошие стартовые значения
params = {
    'max_depth': 5,           # не слишком глубоко
    'min_samples_split': 20,  # узлы с ≥20 объектов
    'min_samples_leaf': 10,   # листья с ≥10 объектов
    'max_features': 'sqrt'    # √(число признаков)
}

---

4. Почему дерево склонно к переобучению?

Главные причины:

1. Может расти до полного разделения — пока каждый объект не попадёт в свой лист
2. Запоминает шум и выбросы в данных
3. Варьирование в данных воспринимает как закономерность
4. Слишком сложные правила — тысячи условий

Аналогия: Студент, который запоминает ответы на билеты, а не понимает тему.

Как проявляется:
- На обучающих данных: 99% точности
- На новых данных: 60% точности
- Дерево имеет сотни листьев

---

5. Что такое бэггинг?

Bagging = Bootstrap Aggregating

Идея:

1. Создаём много случайных подвыборок из данных (с возвращением)
2. Обучаем на каждой подвыборке отдельную модель
3. Усредняем предсказания всех моделей

Как работает:

Исходные данные: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Бутстрэп-выборки (пример):
Выборка 1: [2, 2, 3, 5, 5, 7, 8, 9, 10, 10]  # с повторениями
Выборка 2: [1, 1, 3, 4, 6, 6, 7, 7, 9, 9]
Выборка 3: [1, 2, 4, 4, 5, 6, 8, 8, 10, 10]
... и так 100 выборок

Обучаем 100 деревьев → усредняем их предсказания

Плюсы:

• Уменьшает дисперсию (разброс предсказаний)
• Устойчивее к переобучению
• Можно распараллелить

Пример: Random Forest

• Бэггинг + случайный выбор признаков
• Одно из лучших решений "из коробки"

---

6. Что такое бустинг?

Boosting = Последовательное усиление

Идея:

1. Обучаем первое простое дерево
2. Анализируем ошибки — на каких объектах ошиблось
3. Обучаем второе дерево, которое исправляет ошибки первого
4. Повторяем много раз, каждое новое дерево исправляет ошибки предыдущих

Как работает:

Шаг 1: Дерево 1 → ошибки на [X1, X3, X7]
Шаг 2: Дерево 2 (фокусируется на [X1, X3, X7]) → ошибки на [X2, X5]
Шаг 3: Дерево 3 (фокусируется на [X2, X5]) → ошибки на [X4, X9]
... и так 100 раз

Особенности:

• Последовательно, а не параллельно
• Каждое следующее дерево зависит от предыдущих
• Обычно мелкие деревья (пни, depth=3-6)

Примеры:

• AdaBoost — первые бустинговые алгоритмы
• Gradient Boosting (XGBoost, LightGBM, CatBoost) — современные

---

7. Почему в бустинге используют деревья, а не линейные модели?

Деревья лучше подходят, потому что:

1. Гибкость — улавливают сложные нелинейные зависимости
2. Автоматический feature engineering — создают взаимодействия признаков
3. Устойчивость к разным типам данных (числовые, категориальные)
4. Интерпретируемость ансамбля из сотен деревьев всё ещё можно анализировать
5. Эффективность — быстрое обучение и предсказание

Проблемы линейных моделей для бустинга:

1. Слабая гибкость — плохо улавливают сложные зависимости
2. Чувствительность к мультиколлинеарности
3. Требуют масштабирования и обработки признаков
4. Меньшая эффективность при последовательном улучшении

Исключение: Есть линейные бустеры, но они менее популярны.

---

8. Что будет, если убрать первое дерево?

В бэггинге (Random Forest):

• Почти ничего не изменится — деревья независимы
• Качество снизится незначительно (на 1/n_trees)
• Пример: было 100 деревьев → стало 99, качество упадёт на ~1%

В бустинге (Gradient Boosting):

• Катастрофа! — всё сломается
• Второе дерево обучалось на ошибках первого
• Третье — на ошибках первого и второго
• Без первого дерева вся последовательность теряет смысл

Аналогия:
- Бэггинг: Хор из 100 певцов, одного заболевшего не заметят
- Бустинг: Эстафета, если первый бегун не побежал — эстафета сорвана

---

9. Что будет при увеличении числа деревьев в 100 раз?

Для бэггинга (Random Forest):

Было: 10 деревьев → Стало: 1000 деревьев

Что произойдёт:
1. Качество: Сначала улучшится, потом выйдет на plateau
- После 100-200 деревьев улучшения почти нет
- Закон убывающей отдачи
2. Время обучения: Увеличится в ~100 раз
3. Память: Нужно хранить в 100 раз больше деревьев
4. Предсказание: Медленнее в 100 раз

Рекомендация: Для Random Forest достаточно 100-500 деревьев.

Для бустинга (Gradient Boosting):

Было: 10 деревьев → Стало: 1000 деревьев

Что произойдёт:
1. Высокий риск переобучения! — каждое новое дерево может запоминать шум
2. Качество: Сначала улучшится, потом может ухудшиться (переобучение)
3. Нужна регуляризация:
- Уменьшить learning rate (шаг обучения)
- Использовать раннюю остановку
4. Время: Очень долгое обучение

Рекомендация: Для бустинга лучше увеличивать не число деревьев, а их качество.

---

Ключевые выводы:

Правильный подход:

1. Начинайте с Random Forest — проще, устойчивее, хороший baseline
2. Для максимального качества — пробуйте Gradient Boosting (XGBoost, LightGBM)
3. Контролируйте сложность — регуляризуйте деревья в ансамбле
4. Используйте раннюю остановку в бустинге
5. Не гонитесь за количеством — 100 хороших деревьев лучше, чем 1000 плохих

Практические числа:

• Random Forest: 100-500 деревьев, depth=10-30
• Gradient Boosting: 100-1000 деревьев, depth=3-6, learning_rate=0.01-0.1
• Обязательно: валидация и подбор гиперпараметров!