Семейство алгоритмов деревьев решений
1. ID3 (1986) — Дедушка всех деревьев 👴
Автор: Росс Куинлан
Главная идея: Выбирай вопрос с максимальной информационной выгодой!
Как работает:
- Считает энтропию
- Выбирает признак с максимальной IG
- Делит данные и повторяет рекурсивно
Плюсы:
- ✅ Простой и понятный
- ✅ Легко объяснить
Минусы:
- ❌ Работает только с категориальными признаками (да/нет)
- ❌ Склонен к переобучению
- ❌ Любит признаки с большим числом значений
Аналогия: Как игра "20 вопросов" — задаёшь самые информативные вопросы.
2. C4.5 (1993) — Умный внук ID3 🎓
Автор: Тот же Росс Куинлан
Главная идея: ID3 + исправление недостатков!
Что нового:
- 🔥 Работает с непрерывными признаками (находит пороги)
- 🔥 Использует Gain Ratio вместо IG (справедливее к признакам)
- 🔥 Умеет обрезать дерево (pruning) — убирает лишние ветки
- 🔥 Обрабатывает пропущенные значения
Gain Ratio = IG / SplitInfo
(наказывает признаки с большим числом значений)
Плюсы:
- ✅ Намного практичнее ID3
- ✅ Меньше переобучается
- ✅ Работает с реальными данными
Минусы:
- ❌ Сложнее в реализации
- ❌ Медленнее ID3
Аналогия: ID3 научили новым фокусам — теперь он взрослый и умный!
3. CART (1984) — Конкурент из Америки 🇺🇸
Авторы: Брейман, Фридман, Олшен, Стоун
Название: Classification And Regression Trees
Главная идея: Используй индекс Джини и строй бинарные деревья!
Как работает:
- Использует Gini Impurity вместо энтропии (быстрее!)
- Всегда делит на ровно 2 ветки (бинарное дерево)
- Работает с регрессией (предсказание чисел) и классификацией
Плюсы:
- ✅ Быстрее C4.5 (нет логарифмов)
- ✅ Работает и для классификации, и для регрессии
- ✅ Это то, что используется в scikit-learn!
Минусы:
- ❌ Только бинарные разделения
- ❌ Тоже склонен к переобучению
Аналогия: Всегда спрашивает "Да или Нет?" — никаких "может быть"!
Важно: Когда ты пишешь DecisionTreeClassifier() в Python — это CART!
4. Random Forest (2001) — Команда деревьев! 🌲🌲🌲
Автор: Лео Брейман
Главная идея: Много глупых деревьев лучше одного умного!
Как работает:
- Построй 100 (или 500, или 1000) деревьев
- Каждое дерево видит случайную часть данных
- Каждое дерево использует случайную часть признаков
- При предсказании — голосование большинства!
Почему это работает:
- Одно дерево может ошибиться
- Но если 100 деревьев сказали "Да" — скорее всего правда!
- Это называется ансамблевое обучение
Плюсы:
- ✅ Очень точный
- ✅ НЕ переобучается (магия усреднения!)
- ✅ Работает "из коробки"
- ✅ Показывает важность признаков
Минусы:
- ❌ Медленнее одного дерева
- ❌ Сложнее интерпретировать (100 деревьев!)
- ❌ Требует больше памяти
Аналогия: Спросить совета у 100 друзей вместо одного эксперта.
5. Gradient Boosting (XGBoost, LightGBM, CatBoost) 🚀
Главная идея: Деревья учатся на ошибках друг друга!
Как работает:
- Первое дерево делает предсказания
- Второе дерево учится исправлять ошибки первого
- Третье — исправляет ошибки первых двух
- И так далее...
- Финальный ответ = сумма всех деревьев
Популярные реализации:
- XGBoost — самый популярный на Kaggle
- LightGBM — самый быстрый
- CatBoost — лучше работает с категориями
Плюсы:
- ✅✅✅ Самая высокая точность
- ✅ Побеждает на соревнованиях
- ✅ Умеет в feature importance
Минусы:
- ❌ Сложно настроить (много гиперпараметров)
- ❌ Может переобучиться
- ❌ Медленнее Random Forest
Аналогия: Делаешь домашку, находишь ошибки, исправляешь, снова проверяешь... Каждая итерация улучшает результат!
📊 Сравнительная таблица
| Алгоритм |
Год |
Критерий |
Скорость |
Точность |
Используется? |
| ID3 |
1986 |
Энтропия (IG) |
🐇 Быстро |
⭐⭐ |
Редко (учебный) |
| C4.5 |
1993 |
Gain Ratio |
🐢 Средне |
⭐⭐⭐ |
Иногда |
| CART |
1984 |
Gini |
🐇 Быстро |
⭐⭐⭐ |
✅ Da! (sklearn) |
| Random Forest |
2001 |
Ансамбль |
🐌 Медленно |
⭐⭐⭐⭐ |
✅✅ Очень часто! |
| XGBoost |
2014 |
Градиентный бустинг |
🐢 Средне |
⭐⭐⭐⭐⭐ |
✅✅✅ Топ на Kaggle! |
Что выбрать?
Для обучения:
Для реальных задач:
- CART (DecisionTreeClassifier) — если нужна интерпретация
- Random Forest — если нужна надежность без настройки
- XGBoost — если нужна максимальная точность на соревновании
Интересные факты
- Netflix использует деревья для рекомендаций
- Банки оценивают кредиты через Random Forest
- Медицина диагностирует болезни через деревья
- Kaggle — 80% победителей используют XGBoost или LightGBM
- ID3 — до сих пор изучают в университетах, хотя ему почти 40 лет!
Главный вывод
- ID3 — показал путь (энтропия + IG)
- C4.5 — сделал практичным
- CART — упростил и ускорил
- Random Forest — объединил силу многих
- Boosting — научил учиться на ошибках
Все они — одна семья, каждый со своими суперспособностями!