Модуль 4. Деревья решений

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

Перед началом: модуль 1 (что такое ML и когда он нужен) и модуль 3 (логистическая регрессия); опыт бэкенд-разработки. Инструменты: песочница сайта (чистый Python), сниппет ниже. Трудоёмкость: ~1.5 ч (чтение 45 мин · сниппет и практика 30 мин).

🔥 200 правил, которые переписались сами

Помните крючок модуля 1: поддержка просила «умную сортировку тикетов», первый заход — 200 строк if-else, и правила противоречили друг другу. Теперь заглянем внутрь модели, которая справилась со второго захода — дерева решений. Оно устроено подозрительно знакомо:

если «лежит» в тексте → срочный
если длина > 500 и время 18:00–23:00 → срочный
иначе → обычный

Да это же те самые правила! Разница в одном: пороги (500, 18:00) и порядок вопросов никто не придумывал руками — дерево нашло их по размеченным примерам, перебирая признаки и пороги. Те самые «вопросы выучились сами».

Дерево решений — самый «ремесленный» алгоритм курса: никаких матриц и градиентов, только вопросы и ветви. Поэтому его любят там, где модель должна объясняться построчно: скоринг, алерты, отток. Начнём с того, из чего дерево состоит.

📖 4.1. Пороговый вопрос — это буквальный if

Дерево решений — это иерархия вопросов. Во внутреннем узле живёт проверка «признак ≤ порог?», ответ уводит в левого («да») или правого («нет») потомка, а лист хранит ответ: класс или число. Предсказание — спуск от корня до листа, одни сравнения, ни одного скалярного произведения (модуль 3):

если дождь ≤ 0.5:
    если температура ≤ 17.0: не гулять
    иначе: гулять
иначе: не гулять

Обратите внимание на словарь: дерево умеет работать только с числами и порогами вида «≤». Всё остальное — текст, категории, даты — сначала превращается в числа (кодирование фич — модуль 8), и уже потом дерево режет их порогами.

Как дерево выбирает вопросы? Оно перебирает все признаки и все пороги между соседними отсортированными значениями, считает «качество» каждого разбиения и берёт лучший вопрос в текущем узле. Затем рекурсивно повторяет процедуру в обеих ветвях. Алгоритм жадный: на шаг вперёд он не смотрит — только на выгоду прямо сейчас. На удивление, этого достаточно.

📖 4.2. Энтропия и информационный выигрыш на пальцах

Чтобы сравнивать вопросы, нужна мера неразберихи. Это энтропия: 0 — все примеры одного класса (идеальный порядок), 1 — классы перемешаны 50/50 (полная неопределённость). Формула (сумма −p·log2(p) по классам) есть в сниппете, но для практики хватит смысла: энтропия — сколько битов нужно, чтобы угадать метку в группе.

Информационный выигрыш = энтропия группы до вопроса минус средняя энтропия получившихся частей. Чем чище части — тем больше выигрыш. Пример из вывода сниппета: вопрос «дождь ≤ 0.5» даёт выигрыш 0.689, потому что правая ветвь — 7 дождливых дней — выходит идеально чистой (0:7), а левая почти чистой (0:1, 1:6). Вопрос «температура ≤ 17.0» там же выигрывает меньше — 0.592: он сильнее перемешивает гуляющих и домоседов.

Запомните два следствия. Первое: выигрыш — жадный критерий жадного алгоритма, он выбирает лучший вопрос локально и не обещает оптимального дерева. Второе: рядом живёт индекс Джини (в sklearn — критерий по умолчанию); он считает перемешанность чуть иначе, но ранжирует вопросы похоже. Смысл тот же: «насколько вопрос наводит порядок».

📖 4.3. Разбор сниппета: дерево на 14 примерах прогулки

Сниппет decision-tree.py строит дерево для задачи «идём ли гулять» по 14 примерам (признаки: дождь, температура, ветер) и печатает его на глубинах 1, 2 и 3. Читаем вывод сверху вниз.

Глубина 1 находит один вопрос: если дождь ≤ 0.5 (выигрыш 0.689, n=14). Слева — 7 дней без дождя: → гулять=1 (0:1, 1:6) — шесть прогулок и один домашний день. Справа — → гулять=0 (0:7): в дождь не гуляем ни разу. Точность уже 13/14; единственный промах — тот самый холодный день слева.

Глубина 2 уточняет левую ветвь: если температура ≤ 17.0 (выигрыш 0.592, n=7) — холодный день становится → гулять=0 (0:1), остальные шесть — → гулять=1 (1:6). Правая ветвь дерева не меняется. Итог — 14/14.

Глубина 3 печатает то же дерево, что глубина 2: третий уровень не вырос. Честный факт из вывода: на этом наборе у дерева больше нет выгодных вопросов — выигрыш любого из них ≤ 0, новый уровень не окупается. Третий признак, «ветер», вообще не понадобился: дождя и температуры хватило.

Заметьте главный нюанс: 14/14 — это точность на обучающих данных. На 14 почти разделимых примерах такая точность ничего не обещает в бою. Что происходит с деревом на больших и шумных данных — разбираем в 4.4.

📖 4.4. Переобучение деревом: глубина, листья по 1 примеру, обрезка

Дерево — рекордсмен по лёгкости переобучения. Ему ничто не мешает расти, пока листья не станут идеально чистыми: в пределе — по одному примеру на лист. Такой лист отвечает «гулять» буквально для одного дня из прошлого, а не для закономерности. Получаем 100% на обучающих данных и провал на новых — классическое переобучение (модуль 1, эффект k=1 у kNN).

В сниппете дерево дошло до 14/14 уже на глубине 2 — но вывод честно предупреждает: «на реальных больших данных всё иначе». Там неограниченное дерево будет резать шум: каждый необычный пример получит персональную ветвь. Лечится это тремя ручками — все гиперпараметры (модуль 11):

• max_depth — максимальная глубина. Главный тормоз: для табличных задач обычно хватает 3–8 уровней.
• min_samples_leaf — минимум примеров в листе (например, 5–20): правило, опирающееся на один пример, запрещено.
• Обрезка (pruning) — дерево сначала растят с избытком, затем отсекают ветви, которые не улучшают качество на валидации (cost-complexity pruning).

И правило, которое пригодится и в модулях 5–6: глубину и обрезку настраивают по валидации, а не по обучающей точности. 14/14 из вывода — это отчёт о прошлом, а не прогноз на будущее.

📖 4.5. Компромиссы

• Глубина vs недообучение. Мелкое дерево (глубина 1–2) объяснимо, но недоучивает взаимодействия; глубокое — выучивает, но запоминает шум. Рабочий диапазон между: решает валидация, а не обучающая точность.
• Дерево vs линейная модель. Линейная (модули 2–3) описывает плавные зависимости десятком коэффициентов и хороша при малых данных; дерево бесплатно ловит нелинейности и взаимодействия («дождь И холодно»), но незаметно перегибает.
• Объяснимость vs точность. Одно дерево читается как регламент; ансамбли из модулей 5–6 точнее, но объяснение придётся собирать из важностей признаков и вкладов.
• Локальная жадность vs глобальный оптимум. Жадный выбор вопроса хорош на этом шаге, но может пропустить вопрос, который раскрылся бы через два шага. Это ещё один аргумент в пользу ансамблей.
• Рукописные правила vs дерево. Правила фиксируют ваш опыт и сразу объяснимы; дерево пересматривает пороги по новым данным. Если правила уже есть — дерево можно прогнать как второе мнение и сравнить.

💻 Практика

1. (20 мин) Эксперимент в сниппете. Запустите decision-tree.py и добавьте в DATA один шумный пример — например (0, 25, 0, 0) (солнечный день, а гулять «нет»). Перезапустите: изменилась ли точность на глубине 2? Какой третий вопрос вырос на глубине 3 и почему именно он?
2. (15 мин) Дерево словами. Перепишите дерево глубины 2 из вывода в виде псевдокода if-else — так же, как выглядели 200 строк правил из модуля 1. Сравните объём: 6 строк против 200.
3. (15 мин) Своя задача. Возьмите табличную задачу со времён модуля 1 и выпишите три пороговых вопроса, которые дерево задало бы первыми. Хотя бы один — про взаимодействие двух признаков («дождь И температура»).
4. (10 мин) Ликбез для коллеги. Объясните разницу между «выигрышем 0.689» и «точностью 14/14»: первое — про структуру данных, второе — про качество на конкретных примерах.

🧩 Quiz "Проверь себя"

✅ Итоги модуля

• Объяснить, чем дерево решений похоже на рукописный if-else и чем отличается.
• На пальцах посчитать выигрыш вопроса через энтропию до и после.
• Прочитать дерево из вывода сниппета и связать уровни с точностью 13/14 → 14/14.
• Назвать три способа ограничить переобучение дерева.
• Записать дерево глубины 2 в виде псевдокода if-else.
• Сформулировать, почему 14/14 на обучающих данных — не гарантия.

🔗 Мостик к Модулю 5

Дерево из сниппета выросло на конкретных 14 примерах. Добавьте один шумный день — и дерево глубины 2 изменится: жадный рост нестабилен. Модель, которая капризничает от каждой новой строки, — плохой кандидат в прод. Но эту нестабильность можно превратить в силу: построить много разных деревьев и спросить у них совет. Как случайность побеждает разброс — в модуле 5.