Decision Trees 🌳

Открой sklearn.tree.DecisionTreeClassifier, обучи его на любых данных и попробуй нарисовать результат функцией plot_tree. Ты увидишь ровно ту структуру данных, которую разбирал в уроке 256: корень, внутренние узлы с условиями вроде «возраст > 30?», рёбра-ответы «да/нет» и листья с итоговым предсказанием. Это не метафора и не учебная иллюстрация — модель дерева решений в буквальном смысле хранится в памяти как дерево из урока 256, со всеми его терминами: корнем, глубиной, высотой, поддеревьями. Предсказание для нового объекта — это обычный спуск от корня к листу, ровно такой же, как обход дерева файловой системы или дерева выражения, только на каждом шаге направление выбирает не программист, а значение конкретного признака объекта.

А вот то, как это дерево вообще возникает при обучении, — это прямое применение жадного алгоритма из урока 271. На каждом узле дерево решений выбирает один признак и один порог разбиения, максимизирующие критерий качества прямо сейчас, для этого конкретного узла, — и больше никогда не пересматривает этот выбор, что бы ни случилось дальше при построении дерева. Никакого перебора всех возможных деревьев, никакого отката назад ради глобально лучшей структуры — именно та схема «кандидаты → функция выбора → функция допустимости → выбрать и забыть», которую ты уже видел на примере Прима, Крускала и Дейкстры. И, как ты уже знаешь из урока 271, за эту жадность приходится платить: задача построения по-настоящему оптимального дерева решений доказанно NP-полна (Хайафил и Ривест, 1976), поэтому CART, ID3 и C4.5 сознательно жертвуют гарантией глобального оптимума ради вычислимости за разумное время.

В этом уроке ты разберёшь, как абстрактная структура данных «дерево» и абстрактная жадная стратегия становятся конкретной, работающей и при этом на удивление прозрачной моделью машинного обучения: критерии, по которым дерево выбирает лучшее разбиение (энтропия и прирост информации, индекс Джини), полную арифметику построения маленького дерева на игрушечном датасете шаг за шагом, почему неограниченное дерево решений склонно к катастрофическому переобучению (прямое продолжение bias-variance разложения из урока 304) и какими гиперпараметрами и приёмами с этим борются, а также самое ценное практическое свойство дерева решений — интерпретируемость: возможность буквально прочитать логику модели как список правил «если... и... то...».

Этот урок — не конечная точка, а фундамент сразу для двух следующих моделей курса. Урок 317 про Random Forest (случайный лес) покажет, что происходит, если вырастить много независимых, намеренно переобученных деревьев решений и усреднить их голоса — жадность и склонность к переобучению одного дерева превращаются в источник разнообразия, а не в проблему. Урок 318 про Gradient Boosting (градиентный бустинг) пойдёт другим путём: вместо параллельного леса — последовательность маленьких, специально неглубоких деревьев, каждое из которых исправляет ошибки предыдущих. Обе модели — фактически надстройки над механизмом, который ты разберёшь именно сейчас, поэтому от того, насколько глубоко ты поймёшь одно дерево, будет напрямую зависеть, насколько легко дадутся оба следующих урока.

🎯 Ты узнаешь:

• Как структура дерева из урока 256 (корень, внутренние узлы, листья, глубина, высота) превращается в конкретную модель машинного обучения — дерево решений
• Как жадная схема из урока 271 применяется к построению дерева решений — и почему это дерево не гарантированно оптимально
• Что такое энтропия и прирост информации (information gain), откуда берётся формула $-\sum p_i \log_2 p_i$ и как её вывести из первых принципов
• Как устроен альтернативный критерий — индекс Джини, и чем он отличается от энтропии на практике
• Как построить маленькое дерево решений полностью вручную, с расчётом энтропии и прироста информации на каждом шаге
• Почему неограниченное дерево решений переобучается, и какими гиперпараметрами (max_depth, min_samples_leaf, обрезка дерева) с этим борются
• Как извлечь из обученного дерева человекочитаемые правила «если... то...» — и почему это главное практическое преимущество модели

История

Алгоритм, положивший начало семейству деревьев решений в машинном обучении, называется ID3 (Iterative Dichotomiser 3) — его в 1986 году опубликовал австралийский информатик Росс Куинлан. ID3 опирался на более раннюю идею: ещё в 1960-х психолог Эрл Хант с коллегами разрабатывал систему CLS (Concept Learning System), моделирующую то, как человек классифицирует объекты через последовательность вопросов о признаках. Куинлан формализовал эту идею математически: ID3 на каждом узле выбирает признак, максимизирующий прирост информации, вычисленный через энтропию Шеннона, и рекурсивно строит поддеревья до тех пор, пока в узле не останутся объекты одного класса или не закончатся признаки для разбиения. У ID3 было три существенных ограничения: он умел работать только с категориальными признаками (никаких порогов вроде «возраст > 30?»), не умел обрабатывать пропущенные значения и был систематически смещён в сторону признаков с большим числом уникальных значений — например, признак «ID клиента», уникальный для каждой строки, идеально «разбивал» бы обучающую выборку и получал максимальный прирост информации, при этом будучи абсолютно бесполезным для новых объектов.

Куинлан сам же исправил эти проблемы в 1993 году в алгоритме C4.5: тот умеет находить оптимальный порог разбиения для непрерывных признаков (именно механизм «просканировать все кандидаты-пороги и выбрать лучший», который ты разберёшь дальше в этом уроке), использует скорректированный критерий — коэффициент прироста (gain ratio), — чтобы не давать необоснованное преимущество многозначным признакам, умеет работать с пропущенными значениями и, что важно, впервые вводит обрезку дерева (pruning) после построения — явную коррекцию результата жадного алгоритма, которой в исходном ID3 не было вовсе.

Параллельно, независимо от Куинлана, в 1984 году статистики Лео Брейман, Джером Фридман, Ричард Ольшен и Чарльз Стоун опубликовали монографию с описанием алгоритма CART (Classification And Regression Trees). CART во многом эквивалентен C4.5 по духу, но отличается в деталях, которые дожили до сегодняшних библиотек: он использует по умолчанию индекс Джини вместо энтропии (вычислительно немного дешевле — не нужно считать логарифмы), поддерживает не только классификацию, но и регрессию — предсказание непрерывного числа в листе вместо класса, — и, что напрямую продолжает материал урока 256 про виды деревьев, всегда строит строго бинарное дерево, даже когда исходный категориальный признак принимает больше двух значений: вместо узла с тремя ветками CART находит наилучшее бинарное разбиение категорий на две группы. Именно алгоритм CART, почти в неизменном виде, реализован сегодня в sklearn.tree.DecisionTreeClassifier и DecisionTreeRegressor, а также лежит в основе построения отдельных деревьев внутри Random Forest и Gradient Boosting — то есть буквально всех древовидных моделей, с которыми ты столкнёшься в следующих двух уроках.

Структура дерева решений и урок 256

Интуиция

Возьми любую задачу бинарной классификации — скажем, банк решает, одобрить кредит или нет. Естественный способ рассуждать — задавать вопросы по одному: «доход клиента выше 50 000?», и в зависимости от ответа — следующий вопрос, и так далее, пока не станет ясно, что отвечать. Это в точности структура дерева из урока 256, применённая к конкретной задаче: корень — первый и самый информативный вопрос, внутренние узлы — последующие уточняющие вопросы, а листья — не абстрактные «конечные точки», а конкретные вердикты: «одобрить» или «отказать».

Формальное определение

Определение: Деревом решений называется бинарное дерево (в терминологии урока 256 — именно бинарное, а не n-арное, по причинам, разобранным в примере 3 того урока), в котором каждый внутренний узел хранит пару (признак $j$, порог $t$) и правило разбиения: объекты со значением $x_j \le t$ уходят в левое поддерево, объекты с $x_j > t$ — в правое (для категориального признака порог заменяется разбиением множества категорий на две группы). Каждый лист хранит итоговое предсказание: для дерева классификации — метку класса, обычно как класс большинства среди обучающих объектов, попавших в этот лист (или вектор вероятностей классов — их долей в листе); для дерева регрессии — число, обычно среднее значение целевой переменной среди объектов, попавших в лист.

Обрати внимание: это определение — не новая структура данных, а тот же самый объект из урока 256 с двумя дополнительными деталями: внутренний узел хранит не произвольное условие, а конкретно пару «признак + порог», а лист хранит не любые данные, а именно предсказание модели.

Примеры с разбором

Пример 1 (лёгкий, трассировка объекта через дерево). Пусть банк уже обучил дерево: корень — «Доход высокий?», если да — лист «Одобрить»; если нет — узел «Возраст > 30?», если нет — лист «Отказать»; если да — узел «Возраст > 45?», если нет — лист «Одобрить»; если да — лист «Отказать». (Это дерево мы построим и обоснуем расчётами чуть дальше в этом уроке — сейчас важна только механика спуска.) Новый клиент: доход низкий, возраст 38 лет. Спускаемся: «Доход высокий?» — нет, идём в правое поддерево. «Возраст > 30?» — 38 > 30, да, идём в правое поддерево. «Возраст > 45?» — 38 > 45 не выполняется, идём в левое поддерево — лист «Одобрить».

Пример 2 (средний, дерево регрессии — лист хранит число). Агентство недвижимости оценивает квартиры по площади. Обучающие данные: шесть квартир площадью 40, 45, 50, 80, 85, 90 м² с ценами 4.0, 4.2, 4.5, 7.0, 7.3, 7.5 млн рублей. Разбиение по порогу «площадь > 65 м²?» даёт две группы: {40, 45, 50} с ценами {4.0, 4.2, 4.5} и {80, 85, 90} с ценами {7.0, 7.3, 7.5}. Лист для первой группы предсказывает среднее: $(4.0+4.2+4.5)/3 = 4.233$ млн; лист для второй — $(7.0+7.3+7.5)/3 = 7.267$ млн. Здесь нет никаких классов и голосования большинством — только числа и их среднее, а критерий разбиения для регрессии — не энтропия и не индекс Джини (они определены только для распределений классов), а уменьшение дисперсии (variance reduction) или, эквивалентно, суммы квадратов отклонений от среднего внутри листа — в sklearn этому соответствует параметр criterion="squared_error" у DecisionTreeRegressor.

Пример 3 (сложный, явная связь с терминологией урока 256). Возьми дерево из примера 1: три внутренних узла и четыре листа. По определениям урока 256: глубина корня — $0$, глубина узла «Возраст > 30?» — $1$, глубина узла «Возраст > 45?» — $2$, глубина листьев на этом пути — $1$ (лист «Одобрить» сразу под корнем) и $3$ (два листа под узлом «Возраст > 45?»). Высота этого дерева — глубина самого глубокого листа, то есть $3$. Когда ты задаёшь в sklearn гиперпараметр max_depth=2, ты буквально запрещаешь дереву иметь высоту больше $2$ — а значит, в этом конкретном примере запрещаешь появление узла «Возраст > 45?» и двух листьев под ним, и вместо них узел «Возраст > 30?» сразу станет листом (с каким именно предсказанием — увидишь в разделе про переобучение). А то, что дерево из примера 1 — строго бинарное, при этом признак «Доход» вообще-то мог принимать больше двух значений (например, «низкий/средний/высокий») — прямое следствие того, что CART, как было сказано в разделе про историю, всегда бинаризует разбиение, даже когда исходный признак категориальный, — ровно то свойство деревьев решений, которое урок 256 предсказал заранее в примере 3 своего раздела про виды деревьев.

Почему это важно

Понимание дерева решений как экземпляра абстрактной структуры данных, а не отдельной, изолированной концепции, экономит тебе целый пласт путаницы: гиперпараметры вроде max_depth, min_samples_leaf, атрибуты вроде tree_.node_count в обученной модели sklearn — это не специфичная для машинного обучения терминология, а прямое применение словаря из урока 256. И симметрично — когда ты в будущем встретишь незнакомую древовидную структуру (индекс базы данных, синтаксическое дерево компилятора, дерево разбора в задачах обработки естественного языка), ты уже знаешь, какие вопросы задать: что здесь внутренний узел, что лист, ограничена ли высота, бинарное дерево или n-арное.

Жадное построение дерева и урок 271

Интуиция

Дерево решений не появляется целиком — оно строится рекурсивно, узел за узлом, начиная с корня. На каждом шаге алгоритм стоит перед выбором: какой из множества возможных признаков и порогов разбиения взять для текущего узла? Полный перебор всех возможных структур дерева, как ты уже знаешь из урока 271, вычислительно неподъёмен — число различных бинарных деревьев над $n$ обучающими объектами растёт комбинаторно, и Хайафил с Ривестом ещё в 1976 году доказали, что поиск оптимального дерева — NP-полная задача. Поэтому CART, C4.5 и ID3 действуют ровно так же, как Прим, Крускал и жадный размен монет из урока 271: на каждом узле оценивают всех кандидатов, выбирают локально наилучшего по критерию качества и никогда не возвращаются к этому выбору, даже если позже выяснится, что альтернативное разбиение на этом узле привело бы к более компактному дереву дальше вниз.

Формальное определение

Жадная схема построения дерева решений (в терминах общей схемы жадных алгоритмов из урока 271):

1. Кандидаты — все пары (признак $j$, порог $t$): для непрерывного признака $t$ перебирается по серединам между соседними различными отсортированными значениями признака в текущем узле; для категориального — по всем способам разбить множество его категорий на две группы.
2. Функция выбора — критерий качества разбиения (прирост информации на основе энтропии или уменьшение индекса Джини — подробно в следующем разделе); выбирается кандидат с максимальным значением критерия.
3. Функция допустимости — разбиение должно оставлять в каждом из двух получившихся узлов не меньше min_samples_leaf объектов (иначе кандидат отбрасывается), а глубина узла не должна превышать max_depth.
4. Данные текущего узла разбиваются по выбранному кандидату на левое и правое поддерево, и шаги 1–3 рекурсивно повторяются для каждого из двух новых узлов — независимо и без пересмотра выбора родителя.
5. Рекурсия останавливается, когда все объекты узла принадлежат одному классу (энтропия $=0$), или закончились допустимые кандидаты, или достигнут max_depth — тогда узел становится листом.

Примеры с разбором

Дальше в этом уроке мы будем много раз возвращаться к одному сквозному игрушечному датасету, поэтому введём его один раз. Банк рассматривает 10 заявок на кредит с двумя признаками — «Доход высокий?» (да/нет) и «Возраст» (число) — и решением «Одобрить» (да/нет):

id  Возраст  Доход    Одобрить
1   22       низкий   Нет
2   25       низкий   Нет
3   28       высокий  Да
4   30       низкий   Нет
5   35       высокий  Да
6   38       высокий  Да
7   40       низкий   Да
8   45       высокий  Да
9   50       низкий   Нет
10  55       высокий  Да

Пример 1 (лёгкий, кандидаты корня). На корневом узле есть минимум два содержательных кандидата: категориальный признак «Доход = высокий?» и пороговый «Возраст > 30?». В разделе про критерии качества мы посчитаем для обоих прирост информации: получится $IG(\text{Доход}) \approx 0{,}6100$ бит против $IG(\text{Возраст}>30) \approx 0{,}2564$ бит. Жадная функция выбора берёт максимум — «Доход» побеждает с большим отрывом, и это разбиение фиксируется в корне окончательно: как бы дальше ни строилось дерево, алгоритм больше никогда не спросит себя «а что, если бы в корне стоял признак „Возраст“?».

Пример 2 (средний, жадность не гарантирует лучшее дерево целиком). Представь гипотетическую ситуацию: разбиение A даёт на первом шаге чуть меньший прирост информации, чем разбиение B, но зато после разбиения A обе получившиеся группы становятся почти чистыми и дерево можно завершить одним дополнительным уровнем, а после «более удачного» на вид разбиения B одна из групп остаётся сильно перемешанной и требует ещё двух-трёх уровней вложенных разбиений, чтобы её распутать. Жадный алгоритм этого не видит и не может видеть — у него просто нет механизма «посмотреть на несколько шагов вперёд» и сравнить итоговый размер двух вариантов дерева, потому что для этого пришлось бы построить оба дерева целиком, а это и есть тот самый полный перебор, которого жадность специально избегает. В отличие от Прима и Крускала, для которых в уроке 271 было доказано (через свойство разреза) свойство жадного выбора — гарантия, что локально лучший выбор всегда расширяется до глобального оптимума, — для построения дерева решений такого доказательства не существует и не может существовать, потому что задача NP-полна: если бы жадность гарантированно давала оптимум, задача решалась бы за полиномиальное время, что противоречит доказанной NP-полноте.

Пример 3 (сложный, полная рекурсия на игрушечном датасете). Забегая немного вперёд по вычислениям (полностью раскроем их в следующем разделе): жадный алгоритм на нашем датасете из 10 заявок сначала фиксирует в корне «Доход = высокий?» ($IG \approx 0{,}61$). Ветка «Доход = высокий» оказывается чистой (все пять объектов — «Одобрить»), рекурсия для неё останавливается: это лист. Ветка «Доход = низкий» (пять объектов: №1, 2, 4, 7, 9) ещё смешанная, и на ней рекурсивно запускается тот же самый процесс заново — снова перебор кандидатов (среди оставшихся пяти объектов), снова выбор максимума прироста информации, на этот раз побеждает «Возраст > 30?» ($IG \approx 0{,}32$). Ветка «Возраст ≤ 30» внутри этой группы (№1, 2, 4) оказывается чистой — лист «Отказать». Ветка «Возраст > 30» внутри неё (№7 и №9 — всего два объекта, один «Да», один «Нет») всё ещё смешанная, и рекурсия идёт дальше: на этих двух объектах находится идеальное разбиение «Возраст > 45?», дающее два чистых листа из одного объекта каждый. Дерево готово. Обрати внимание: ни на одном из трёх уровней рекурсии алгоритм ни разу не оглянулся на решение, принятое уровнем выше, — а на последнем уровне он с абсолютной серьёзностью «нашёл идеальное правило», отделяющее одного тридцативосьмилетнего клиента от одного пятидесятилетнего, имея для этого всего два примера. Это уже прямой предвестник темы следующего раздела — переобучения.

Почему это важно

Жадное построение дерева решений — не упрощение ради удобства реализации, а единственный практически осуществимый способ построить дерево решений на реальных объёмах данных за разумное время: сложность жадного построения — порядка $O(n \cdot m \cdot \log n)$ на уровень глубины (где $n$ — число объектов, $m$ — число признаков), тогда как полный перебор структур дерева растёт экспоненциально. Именно поэтому все промышленные библиотеки — scikit-learn, XGBoost, LightGBM, CatBoost — строят деревья решений исключительно жадно, ни одна из них не пытается искать «действительно оптимальное» дерево. А цена этой жадности — риск построить структурно неоптимальное и, как ты увидишь дальше, склонное к переобучению дерево — компенсируется не отказом от жадности, а совершенно другим приёмом: выращиванием не одного, а сотен жадно построенных деревьев сразу (Random Forest, урок 317) или последовательности деревьев, каждое из которых жадно исправляет ошибки предыдущих (Gradient Boosting, урок 318).

Критерии качества разбиения: энтропия, прирост информации и индекс Джини

Интуиция

На каждом шаге жадного алгоритма нужна числовая функция выбора, которая говорит: «вот это разбиение лучше вот того». Интуиция за этой функцией — «чистота» узла. Если после разбиения оба получившихся узла состоят почти целиком из объектов одного класса, разбиение хорошее — оно «навело порядок». Если после разбиения узлы остались такими же перемешанными, как и родитель, разбиение бесполезное. Формализовать «беспорядок» помогает понятие из теории информации — энтропия: чем более неопределёнен исход (чем ближе распределение классов к равномерному), тем выше энтропия; чем более предсказуем исход (все объекты одного класса), тем она ниже, вплоть до нуля.

Формальное определение

Выведем формулу энтропии не как данность, а из требований к тому, что вообще должна измерять «неожиданность» одного исхода. Пусть событие происходит с вероятностью $p$. Естественно потребовать: (1) чем событие менее вероятно, тем больше информации несёт весть о том, что оно произошло — функция «неожиданности» $I(p)$ должна убывать по $p$; (2) для двух независимых событий с вероятностями $p_1$ и $p_2$ совместная неожиданность должна складываться из отдельных: $I(p_1 \cdot p_2) = I(p_1) + I(p_2)$, потому что независимость означает, что весть о втором событии не добавляет и не убавляет информации о первом. Единственный класс функций, превращающий умножение аргументов в сложение значений, — логарифмы: $I(p) = -\log_b(p)$ (знак минус нужен, чтобы функция убывала по $p$, ведь $\log p \le 0$ для $p \in (0,1]$). Выбор основания $b=2$ фиксирует единицу измерения — бит: сообщение с вероятностью $p=1/2$ несёт ровно $-\log_2(1/2)=1$ бит информации, что соответствует интуиции «один правильный ответ на вопрос да/нет».

Энтропия узла — это не неожиданность одного конкретного исхода, а ожидаемая неожиданность по всем возможным классам, взвешенная их вероятностями:

$$H(S) = -\sum_{i} p_i \log_2 p_i$$

где $p_i$ — доля объектов класса $i$ в узле $S$. Для узла, где все объекты одного класса ($p_i=1$ для одного класса, $0$ для остальных), $H(S)=0$ — полная определённость (по соглашению $0 \log_2 0 = 0$). Для бинарной задачи с равными долями классов $H(S) = -0{,}5\log_2 0{,}5 - 0{,}5\log_2 0{,}5 = 1$ бит — максимальная неопределённость.

Прирост информации (information gain) сравнивает энтропию узла до разбиения с взвешенной суммой энтропий узлов после разбиения:

$$IG(S, A) = H(S) - \sum_{v} \frac{|S_v|}{|S|} H(S_v)$$

где $A$ — испытываемый признак (и порог), $S_v$ — подмножество объектов узла $S$, попавших в ветку $v$ после разбиения по $A$. Жадная функция выбора берёт кандидата с максимальным $IG$.

Индекс Джини — альтернативный, вычислительно более дешёвый критерий (не требует логарифмов), измеряющий вероятность того, что два случайно и независимо выбранных из узла объекта окажутся разных классов:

$$\mathrm{Gini}(S) = 1 - \sum_i p_i^2$$

Как и энтропия, индекс Джини равен $0$ для чистого узла и максимален при равномерном распределении классов (для бинарного случая максимум $=0{,}5$ при $p_1=p_2=0{,}5$). Выбор разбиения по индексу Джини делается по аналогичной формуле уменьшения примеси: $\Delta\mathrm{Gini}(S,A) = \mathrm{Gini}(S) - \sum_v \frac{|S_v|}{|S|}\mathrm{Gini}(S_v)$, и снова выбирается кандидат с максимальным уменьшением.

Примеры с разбором

Вернёмся к датасету из 10 заявок на кредит из предыдущего раздела и распишем вычисления полностью.

Пример 1 (лёгкий, энтропия корня и двух кандидатов). Среди 10 заявок 6 «Да» и 4 «Нет»: $H(S) = -0{,}6\log_2 0{,}6 - 0{,}4\log_2 0{,}4 = 0{,}6 \cdot 0{,}7370 + 0{,}4 \cdot 1{,}3219 = 0{,}4422 + 0{,}5288 = 0{,}9710$ бит. Разбиение по «Доход = высокий?»: группа «высокий» — 5 объектов (№3, 5, 6, 8, 10), все «Да» — $H=0$; группа «низкий» — 5 объектов (№1, 2, 4, 7, 9), 1 «Да» и 4 «Нет» — $H = -0{,}2\log_2 0{,}2 - 0{,}8\log_2 0{,}8 = 0{,}2\cdot2{,}3219+0{,}8\cdot0{,}3219=0{,}4644+0{,}2575=0{,}7219$ бит. Взвешенная энтропия после разбиения: $0{,}5\cdot0+0{,}5\cdot0{,}7219=0{,}3610$. Прирост информации: $IG(\text{Доход}) = 0{,}9710-0{,}3610=0{,}6100$ бит.

Пример 2 (средний, проигравший кандидат и худший кандидат). Разбиение по «Возраст > 30?»: группа «> 30» — 6 объектов (№5,6,7,8,9,10), 5 «Да» и 1 «Нет» — $H=-\frac{5}{6}\log_2\frac{5}{6}-\frac{1}{6}\log_2\frac{1}{6}=\frac{5}{6}\cdot0{,}2630+\frac{1}{6}\cdot2{,}5850=0{,}2192+0{,}4308=0{,}6500$; группа «≤ 30» — 4 объекта (№1,2,3,4), 1 «Да» и 3 «Нет» — $H=0{,}75\cdot0{,}4150+0{,}25\cdot2=0{,}3113+0{,}5=0{,}8113$. Взвешенная энтропия: $0{,}6\cdot0{,}6500+0{,}4\cdot0{,}8113=0{,}3900+0{,}3245=0{,}7145$; $IG(\text{Возраст}>30)=0{,}9710-0{,}7145=0{,}2564$ бит — почти втрое хуже «Дохода». А порог «Возраст > 40?» ещё хуже: группа «>40» — 3 объекта (№8,9,10): 2 «Да», 1 «Нет» — $H=0{,}9183$; группа «≤40» — 7 объектов: 4 «Да», 3 «Нет» — $H=0{,}9852$; взвешенная $0{,}3\cdot0{,}9183+0{,}7\cdot0{,}9852=0{,}2755+0{,}6896=0{,}9651$; $IG\approx0{,}9710-0{,}9651=0{,}0059$ бит — практически ноль. Это наглядно показывает, зачем C4.5 и CART перебирают все кандидатные пороги между соседними значениями признака, а не пробуют один «интуитивный» — большинство порогов оказываются почти бесполезными, и только перебор находит действительно сильный.

Пример 3 (сложный, индекс Джини и сравнение с энтропией). Для того же корня: $\mathrm{Gini}(S)=1-(0{,}6^2+0{,}4^2)=1-0{,}52=0{,}48$. Разбиение по «Доход»: $\mathrm{Gini}(\text{высокий})=1-(1^2+0^2)=0$; $\mathrm{Gini}(\text{низкий})=1-(0{,}2^2+0{,}8^2)=1-0{,}68=0{,}32$; взвешенное $0{,}5\cdot0+0{,}5\cdot0{,}32=0{,}16$; уменьшение примеси $=0{,}48-0{,}16=0{,}32$. Разбиение по «Возраст > 30?»: $\mathrm{Gini}(>30)=1-((5/6)^2+(1/6)^2)=1-0{,}7222=0{,}2778$; $\mathrm{Gini}(\le30)=1-(0{,}25^2+0{,}75^2)=1-0{,}625=0{,}375$; взвешенное $0{,}6\cdot0{,}2778+0{,}4\cdot0{,}375=0{,}1667+0{,}15=0{,}3167$; уменьшение $=0{,}48-0{,}3167=0{,}1633$. Ранжирование совпало с энтропией: «Доход» ($0{,}32$) побеждает «Возраст > 30» ($0{,}1633$) при любом из двух критериев — так бывает в подавляющем большинстве практических случаев, потому что энтропия и индекс Джини — качественно очень похожие меры примеси, отличающиеся в основном формой кривой (энтропия чуть резче штрафует смешанные узлы), а не тем, какое разбиение считать лучшим. Именно поэтому в sklearn параметр criterion="gini" стоит по умолчанию — он не хуже энтропии выбирает разбиения, но считается быстрее, не требуя логарифмов.

Почему это важно

Критерий качества разбиения — это в точности та самая «функция выбора» из жадной схемы урока 271, сердце всего алгоритма построения дерева. От выбора между энтропией и индексом Джини (параметр criterion в DecisionTreeClassifier) итоговое дерево на практике меняется незначительно, но сама идея — свести субъективное понятие «хорошее разбиение» к одному вычислимому числу, которое можно сравнить у тысяч кандидатов за доли секунды, — это то, что вообще делает жадное построение дерева решений возможным. Без числового критерия шаг 2 жадной схемы («функция выбора») был бы неопределён, и вся конструкция рассыпалась бы.

Переобучение дерева решений и способы борьбы с ним

Интуиция

В примере 3 раздела про жадное построение мы честно довели рекурсию до конца: последний узел дерева отделил одного клиента 40 лет от одного клиента 50 лет идеальным разбиением по возрасту, получив прирост информации ровно в 1 бит на выборке из двух объектов. Формально это абсолютно корректный жадный шаг — правило выбора максимизировало критерий, как и требовалось. Но по существу это чистое переобучение: правило «если тебе от 41 до 45 лет — одобрить, если 46 и старше — отказать» не отражает никакой реальной закономерности кредитоспособности, оно просто идеально разделило два конкретных человека в обучающей выборке. Дерево без ограничений будет расти, пока каждый лист не станет чистым (либо не кончатся признаки), а значит, в пределе оно способно запомнить обучающую выборку целиком, включая весь её шум, — ровно та ситуация «высокая дисперсия, низкое смещение» из разложения ошибки $\text{bias}^2 + \text{variance} + \text{irreducible error}$, которую ты разбирал в уроке 304. Чем глубже дерево, тем больше в нём узлов и порогов — то есть больше эффективных параметров модели, — и тем выше риск подогнаться под случайные совпадения в конкретной обучающей выборке вместо общей закономерности.

Формальное определение

Гиперпараметры-ограничители (pre-pruning, предварительная обрезка):

• max_depth — максимальная высота дерева (в терминах урока 256): запрещает узлам находиться глубже заданного значения, тем самым напрямую ограничивая длину самой длинной цепочки условий.
• min_samples_leaf — минимальное число обучающих объектов, которое обязано остаться в каждом из двух листьев после разбиения; кандидат, нарушающий это условие, отбрасывается ещё на этапе выбора функцией допустимости.
• min_samples_split — минимальное число объектов в узле, при котором вообще разрешено пробовать его разбивать (если объектов меньше — узел сразу становится листом).

Обрезка дерева после построения (post-pruning): сначала дерево строится жадно и без ограничений до конца, а затем излишние поддеревья «подрезаются» обратно до листа. Классический подход CART — обрезка по минимальной цене-сложности (cost-complexity pruning): для параметра $\alpha \ge 0$ минимизируется

$$R_\alpha(T) = R(T) + \alpha \cdot |\text{листья}(T)|$$

где $R(T)$ — ошибка дерева $T$ на обучающих данных, а $|\text{листья}(T)|$ — штраф за сложность (число листьев). При $\alpha=0$ побеждает полное неподрезанное дерево; чем больше $\alpha$, тем сильнее штраф за каждый лишний лист и тем компактнее становится итоговое дерево. Оптимальное значение $\alpha$ подбирается кросс-валидацией (урок 306), а не жадно за один проход — это единственный момент во всём алгоритме, где происходит нечто похожее на «пересмотр» жадных решений, принятых при построении.

Примеры с разбором

Пример 1 (лёгкий, диагностика переобученного листа). Полное дерево из раздела про жадное построение на последнем шаге разделило №7 (возраст 40, «Да») и №9 (возраст 50, «Нет») правилом «Возраст > 45?» на два листа по одному объекту. Если завтра придёт новый клиент 42 лет с низким доходом, дерево ответит «Одобрить» (42 ≤ 45), а клиент 48 лет — «Отказать» (48 > 45) — при том, что оба решения опираются на данные всего одного исторического клиента и статистически неотличимы от подбрасывания монетки. Диагноз очевиден: лист с одним обучающим объектом — почти всегда переобучение, а не найденная закономерность.

Пример 2 (средний, max_depth=2). Ограничим высоту дерева до $2$. Первые два уровня строятся как прежде: корень «Доход = высокий?», затем внутри ветки «низкий» — узел «Возраст > 30?». Но на глубине $2$ рекурсия обязана остановиться, поэтому узел «Возраст > 30?» сам становится листом вместо того, чтобы породить ещё один уровень. В этом листе оказываются №7 и №9 — один «Да», один «Нет», ровно поровну. Модель вынуждена предсказывать по большинству при полном отсутствии большинства: sklearn в таком случае обычно возвращает класс с меньшим численным индексом (или вероятность $0{,}5/0{,}5$, если запрошены вероятности через predict_proba) — и это честнее, чем притворяться, будто у нас есть правило, отличающее 40-летних от 50-летних.

Пример 3 (сложный, min_samples_leaf, запрещающий конкретно переобучающее разбиение). Установим min_samples_leaf=2. Кандидат «Возраст > 45?» на узле с №7 и №9 создаёт два листа по одному объекту каждый — это нарушает min_samples_leaf=2 ещё на этапе проверки допустимости, и кандидат отбрасывается, даже несмотря на идеальный прирост информации в 1 бит. Других кандидатов на этих двух объектах не остаётся (признак «Доход» уже зафиксирован веткой «низкий», а по возрасту любой порог даст то же разбиение 1-к-1), так что узел становится листом с теми же двумя объектами и тем же неопределённым большинством — результат идентичен ограничению max_depth=2 из примера 2, но достигнут другим механизмом: не через ограничение общей высоты дерева, а через прямой запрет на «нечестно уверенные» листья.

Пример 4 (обрезка после построения, cost-complexity pruning). Представь, что полное неподрезанное дерево на реальном (не игрушечном, гораздо большем) датасете содержит одну ветку, которая целиком посвящена разделению всего пяти обучающих объектов на пять отдельных листьев — типичный признак переобучения на локальном шуме. При малом $\alpha$ штраф за лишний лист невелик, и такая ветка сохраняется. По мере роста $\alpha$ штраф за пять лишних листьев начинает перевешивать ту небольшую выгоду по $R(T)$, которую они дают на обучающей выборке, — и алгоритм «схлопывает» всю ветку обратно в один лист с предсказанием по большинству объектов этой ветки. Ключевое отличие от max_depth и min_samples_leaf: обрезка смотрит на уже построенное дерево целиком и решает, какие его части не окупают своей сложности, тогда как max_depth и min_samples_leaf — это ограничения, накладываемые заранее, ещё до того, как алгоритм увидел, к чему привело бы то или иное разбиение.

Почему это важно

Способность дерева решений идеально подстроиться под любую обучающую выборку — прямая иллюстрация того, что глубина дерева — это фактически число его эффективных параметров, а безграничная глубина — это модель с неограниченной ёмкостью, обречённая (в терминах урока 304) на низкое смещение и катастрофически высокую дисперсию, если её ничем не ограничить. В sklearn.tree.DecisionTreeClassifier за это отвечают параметры max_depth, min_samples_leaf, min_samples_split и ccp_alpha (реализация cost-complexity pruning), и подбор их значений с помощью кросс-валидации (урок 306) — не опциональный штрих, а обязательная часть обучения любого дерева решений на реальных данных.

Интерпретируемость: как «прочитать» логику дерева

Интуиция

В уроке 256 ты уже видел приём: модифицированный обход в глубину с накоплением пути и откатом (backtracking) — функция extract_rules, которая спускается по дереву, дописывая в список условие на каждом шаге, а достигнув листа, печатает накопленный путь целиком как готовое правило. Применительно к дереву решений этот же приём превращает обученную модель — набор чисел, порогов и указателей — в список фраз, понятных человеку без единого упоминания энтропии или градиентов.

Формальное определение

Извлечение правил из дерева решений — это прямой обход в глубину (preorder), при котором на спуске в левое поддерево в путь дописывается условие «$x_j \le t$», при спуске в правое — «$x_j > t$», а по достижении листа накопленный путь целиком выводится как правило вида «ЕСЛИ (условие) И (условие) И … ТО (предсказание)», после чего последнее условие удаляется из пути при возврате из рекурсии (в точности код extract_rules из урока 256, применённый не к абстрактному дереву решения о кредите как к иллюстрации обхода в глубину, а к настоящей обученной модели).

Примеры с разбором

Пример 1 (лёгкий, полный список правил). Для дерева из раздела «Структура дерева решений» (без ограничения глубины, четыре листа) обход даёт четыре правила: «ЕСЛИ Доход = высокий ТО Одобрить»; «ЕСЛИ Доход = низкий И Возраст ≤ 30 ТО Отказать»; «ЕСЛИ Доход = низкий И Возраст > 30 И Возраст ≤ 45 ТО Одобрить»; «ЕСЛИ Доход = низкий И Возраст > 30 И Возраст > 45 ТО Отказать». Заметь: третье и четвёртое правило (различающиеся только по одному человеку из обучающей выборки, как обсуждалось в разделе про переобучение) при чтении сразу выглядят подозрительно узкими и надуманными — интерпретируемость не только объясняет модель, но и помогает диагностировать переобучение на глаз, просто взглянув на список правил.

Пример 2 (средний, сравнение с «чёрным ящиком»). Логистическая регрессия из урока 313 для той же задачи выдала бы одно уравнение вида $z = w_0 + w_1 \cdot \text{Доход} + w_2 \cdot \text{Возраст}$ с конкретными числовыми весами — формально это тоже «интерпретируемая» модель, но объяснить клиенту банка, почему ему отказали, фразой «взвешенная сумма ваших признаков с коэффициентами $-0{,}42$ и $0{,}03$ дала отрицательный логит» практически невозможно. Правило «вам отказали, потому что ваш доход не высокий, а возраст больше 45 лет» из дерева решений понятно без единой формулы — и именно поэтому дерево решений (и его потомки — Random Forest с оговорками, но особенно единичное дерево) остаётся стандартом там, где требуется объяснимость: кредитный скоринг, медицинская диагностика, юридически значимые автоматические решения, подпадающие под регуляции вроде «права на объяснение».

Пример 3 (сложный, интерпретируемость как отладочный инструмент). Представь, что дерево решений для медицинской диагностики выдало правило «ЕСЛИ Номер_страховки > 500000 ТО Диагноз = Здоров» — абсурдное с медицинской точки зрения, но идеально «сработавшее» на обучающих данных из-за случайного совпадения (например, более новые страховые полисы с большими номерами оформлялись преимущественно молодой и потому более здоровой аудиторией). Для модели-чёрного ящика (глубокой нейросети) заметить и понять такую паразитную закономерность практически невозможно без специальных инструментов интерпретации постфактум (SHAP, LIME). Для дерева решений эта закономерность видна невооружённым глазом прямо в списке правил, извлечённых extract_rules, — ты замечаешь бессмысленный признак в условии и сразу понимаешь, что с данными или с моделью что-то не так, задолго до того, как модель попадёт в продакшен.

Почему это важно

Интерпретируемость — не побочный приятный бонус дерева решений, а зачастую главная причина выбрать именно эту модель, даже когда она заведомо уступает в точности более сложным альтернативам. Random Forest и Gradient Boosting из следующих двух уроков дают, как правило, заметно более высокую точность предсказаний, но ценой этой точности становится потеря прямой читаемости: у леса из сотен деревьев или у последовательности бустинговых поправок уже нет единого списка правил, который можно прочитать целиком, — там на смену приходят агрегированные метрики важности признаков и специальные инструменты объяснения. Одиночное дерево решений — последняя точка в этом курсе, где модель полностью, без всяких приближений, объясняет саму себя.

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. В узле 6 объектов класса «Да» и 4 объекта класса «Нет». Вычисли энтропию узла.

Задание 2. Для того же узла (6 «Да», 4 «Нет») вычисли индекс Джини.

Задание 3. Дано дерево: корень «Доход = высокий?» → лист «Одобрить»; иначе → «Возраст > 30?» → если нет → лист «Отказать»; если да → «Возраст > 45?» → если нет → лист «Одобрить»; если да → лист «Отказать». Клиент: доход низкий, возраст 38. Какое решение выдаст дерево?

Задание 4. Для дерева из задания 3 назови все внутренние узлы и все листья.

Задание 5. Объясни своими словами, что означает энтропия узла, равная нулю.

Задание 6. В узле 5 объектов, все класса «Да» (0 объектов «Нет»). Вычисли энтропию.

Задание 7. В узле поровну объектов двух классов (например, 4 «Да» и 4 «Нет»). Вычисли энтропию и объясни, почему получилось именно такое значение.

Задание 8. Разбиение делит узел на подгруппу A (6 объектов, $H=0{,}65$) и подгруппу B (4 объекта, $H=0$). Вычисли взвешенную энтропию после разбиения.

Задание 9. Признак A даёт прирост информации $IG(A)=0{,}61$ бит, признак B — $IG(B)=0{,}26$ бит. Какой признак жадный алгоритм выберет для разбиения узла и почему?

Задание 10. Путь в дереве: «Доход = высокий?» → да → лист «Одобрить». Запиши этот путь как правило вида «ЕСЛИ … ТО …».

Средние (задания 11–20)

Задание 11. В узле 7 объектов «Да» и 3 «Нет». Вычисли энтропию.

Задание 12. Родительский узел из задания 11 (7 «Да», 3 «Нет», $H=0{,}8813$) разбит признаком C на группу 1 (4 объекта: 3 «Да», 1 «Нет») и группу 2 (6 объектов: 4 «Да», 2 «Нет»). Вычисли прирост информации.

Задание 13. Для той же ситуации (задание 12) вычисли уменьшение индекса Джини и сравни ранжирование с приростом информации.

Задание 14. Непрерывный признак принимает отсортированные значения $[12, 15, 15, 18, 22, 30]$. Перечисли все кандидатные пороги разбиения (середины между соседними различными значениями).

Задание 15. Датасет из 6 объектов, признак «Возраст» = $[20,24,29,33,41,50]$, класс = [Нет,Нет,Да,Да,Да,Нет]. Сравни прирост информации для порогов «Возраст > 24» и «Возраст > 29».

Задание 16. Опиши структуру дерева, которое построит жадный алгоритм на первых двух уровнях для датасета из 10 заявок на кредит из основного текста урока (напомним: на корне побеждает «Доход», внутри ветки «низкий» — «Возраст > 30?»).

Задание 17. Объясни, почему жадное построение дерева решений не гарантирует глобально оптимальное (наименьшее по числу узлов при заданной точности) дерево.

Задание 18. Дерево решений на реальных данных выросло до глубины 5, часть листьев содержит ровно 1 обучающий объект. Что это означает и какой гиперпараметр стоит изменить в первую очередь?

Задание 19. Кандидат разбиения делит узел из 10 объектов на подгруппы размером 2 и 8. Установлен min_samples_leaf=3. Разрешит ли алгоритм это разбиение?

Задание 20. Объясни в общих чертах, что происходит с деревом по мере роста параметра $\alpha$ в обрезке по минимальной цене-сложности $R_\alpha(T)=R(T)+\alpha|\text{листья}(T)|$.

Сложные (задания 21–30)

Задание 21. Новый датасет из 8 объектов с признаками «Жанр» (Комедия/Драма) и «Рейтинг» (высокий/низкий), класс «Смотреть» (Да/Нет): (Комедия, высокий, Да), (Комедия, высокий, Да), (Комедия, низкий, Нет), (Комедия, низкий, Да), (Драма, высокий, Да), (Драма, высокий, Нет), (Драма, низкий, Нет), (Драма, низкий, Нет). Вычисли прирост информации для обоих признаков на корне.

Задание 22. Продолжи построение дерева из задания 21: алгоритм выбрал «Рейтинг» для корня. Раздели ветку «высокий» (Да,Да,Да,Нет) дальше по признаку «Жанр» и вычисли прирост информации этого второго уровня.

Задание 23. Для разбиения корня из задания 21 («Рейтинг») вычисли уменьшение индекса Джини и сравни с приростом информации по критерию согласованности выбора.

Задание 24. Лист дерева регрессии содержит целевые значения $[4{,}0;\ 4{,}2;\ 4{,}5]$ (млн рублей). Вычисли предсказание листа и его «примесь» (impurity) как дисперсию значений внутри листа.

Задание 25. В основном тексте урока последний узел полного дерева разделил всего два объекта (возраст 40 «Да» и возраст 50 «Нет») порогом «Возраст > 45?» с приростом информации ровно 1 бит. Объясни, почему такой высокий прирост информации не является доказательством найденной закономерности.

Задание 26. Датасет из 200 объектов содержит несколько почти одинаковых по признакам, но противоречащих друг другу по классу выбросов. Объясни, почему для такого датасета полезнее задать одновременно и max_depth, и min_samples_leaf, а не полагаться на что-то одно.

Задание 27. Извлеки все правила «ЕСЛИ… ТО…» из полного (неподрезанного) дерева на датасете из 10 заявок на кредит из основного текста урока (4 листа: «Доход=высокий → Одобрить»; «Доход=низкий, Возраст≤30 → Отказать»; «Доход=низкий, Возраст>30, Возраст≤45 → Одобрить»; «Доход=низкий, Возраст>30, Возраст>45 → Отказать»).

Задание 28. Объясни своими словами, почему построение по-настоящему оптимального дерева решений вычислительно неподъёмно даже для датасета из нескольких сотен объектов.

Задание 29. Объясни, почему выращивание множества независимых, намеренно глубоких (и потому переобученных) деревьев решений с последующим усреднением их предсказаний (идея Random Forest, урок 317) может дать более качественную модель, чем одно аккуратно подрезанное дерево.

Задание 30. Датасет из 10 сотрудников с признаками «Стаж > 3 лет?» (да/нет) и «Оценка» (высокая/низкая), класс «Премия» (Да/Нет): (да,высокая,Да), (да,высокая,Да), (да,низкая,Нет), (да,низкая,Нет), (нет,высокая,Да), (нет,высокая,Нет), (нет,низкая,Нет), (нет,низкая,Нет), (да,высокая,Да), (нет,низкая,Нет). Построй дерево решений полностью вручную (энтропия и прирост информации на каждом шаге) и определи предсказание для нового сотрудника: стаж 2 года, оценка высокая.

Частые ошибки

❌ Ошибка: считать, что дерево решений без ограничений — это «более точная» модель, потому что оно безошибочно классифицирует обучающую выборку. ✅ Правильно: безошибочность на обучающих данных — не признак качества, а часто прямой признак переобучения. 💡 Почему: дерево, растущее до идеальной чистоты каждого листа, запоминает конкретные обучающие объекты (включая шум), а не общую закономерность — на новых данных такая модель обычно работает заметно хуже подрезанной.

❌ Ошибка: пытаться найти глобально лучшее разбиение, перебирая только «удобные», интуитивно выбранные пороги вроде круглых чисел. ✅ Правильно: перебирать все кандидатные пороги — середины между соседними различными значениями признака в текущем узле. 💡 Почему: как показал пример с порогами «Возраст > 24» и «Возраст > 29» в разделе про критерии, случайно выбранный «на глаз» порог может оказаться почти бесполезным, тогда как соседний с ним даёт в разы больший прирост информации.

❌ Ошибка: думать, что жадное построение дерева гарантированно даёт оптимальное по размеру дерево, потому что «жадные алгоритмы обычно работают хорошо» (по аналогии с Примом и Крускалом). ✅ Правильно: помнить, что для деревьев решений не доказано свойство жадного выбора, а задача поиска оптимального дерева NP-полна. 💡 Почему: аналогия с минимальным остовным деревом и кратчайшими путями вводит в заблуждение — там жадность доказуемо оптимальна благодаря свойству разреза, а для деревьев решений такого доказательства нет и не может быть при $P \ne NP$.

❌ Ошибка: использовать в качестве признака что-то вроде ID клиента, номера договора или другого почти уникального идентификатора. ✅ Правильно: исключать признаки с уникальными или почти уникальными значениями на этапе подготовки данных. 💡 Почему: такой признак может дать колоссальный прирост информации на обучающей выборке (буквально идентифицируя каждый объект), но не несёт никакой обобщающей закономерности и на новых данных абсолютно бесполезен.

❌ Ошибка: ограничивать только max_depth, считая, что этого достаточно для борьбы с переобучением. ✅ Правильно: комбинировать max_depth, min_samples_leaf, min_samples_split и при необходимости обрезку по ccp_alpha, подбирая их через кросс-валидацию. 💡 Почему: max_depth ограничивает только общую высоту дерева, но не мешает возникновению крошечных листьев на небольшой глубине из-за случайных выбросов в данных — разные ограничения решают разные аспекты переобучения.

❌ Ошибка: доверять энтропии и индексу Джини как единственному критерию правильности разбиения без учёта размера подгрупп. ✅ Правильно: обращать внимание не только на значение прироста информации, но и на то, сколько объектов участвует в разбиении. 💡 Почему: идеальный прирост информации в 1 бит на группе из двух объектов (как в примере с возрастом 40 и 50 лет в этом уроке) статистически ничего не стоит — критерий качества разбиения не «знает» о размере выборки, на которой он посчитан.

Главное запомнить

✅ Дерево решений — конкретная реализация структуры данных «дерево» из урока 256: внутренние узлы хранят условие «признак + порог», листья хранят предсказание (класс или число)

✅ Дерево решений строится жадно, по общей схеме из урока 271: на каждом узле выбирается локально наилучший кандидат разбиения без пересмотра и без гарантии глобального оптимума

✅ Энтропия $H(S)=-\sum p_i\log_2 p_i$ измеряет неопределённость распределения классов в узле; прирост информации $IG=H(S)-\sum \frac{|S_v|}{|S|}H(S_v)$ измеряет, насколько разбиение уменьшает эту неопределённость

✅ Индекс Джини $\mathrm{Gini}(S)=1-\sum p_i^2$ — вычислительно более лёгкая альтернатива энтропии, на практике почти всегда ранжирующая кандидатов так же

✅ Для непрерывных признаков перебираются все кандидатные пороги между соседними различными значениями — «интуитивный» порог часто оказывается далеко не лучшим

✅ Дерево без ограничений растёт до полной чистоты каждого листа и неизбежно переобучается — это прямое продолжение bias-variance разложения из урока 304

✅ max_depth, min_samples_leaf, min_samples_split ограничивают рост дерева заранее (pre-pruning); обрезка по цене-сложности $R_\alpha(T)=R(T)+\alpha|\text{листья}(T)|$ упрощает уже построенное дерево (post-pruning)

✅ Дерево решений для регрессии предсказывает в листе среднее значение целевой переменной, а критерием качества служит уменьшение дисперсии вместо энтропии или индекса Джини

✅ Главное практическое преимущество дерева решений — интерпретируемость: любой путь от корня до листа можно прочитать как правило «ЕСЛИ… ТО…» без единой формулы

✅ Дерево решений — фундамент для Random Forest (урок 317, много независимых деревьев) и Gradient Boosting (урок 318, последовательность исправляющих друг друга деревьев)

Связь с темами курса

Урок 256 (деревья: определение и виды). Всё, что ты знаешь о корне, внутренних узлах, листьях, глубине и высоте, применяется к дереву решений без единой оговорки — это буквально та же структура данных. Ограничение max_depth — это прямое ограничение высоты дерева в терминах урока 256. Строгая бинарность CART, которую урок 256 уже предсказывал в разборе видов деревьев, — не случайность инженерной реализации, а сознательный выбор авторов алгоритма ради математической простоты и эффективных алгоритмов работы с бинарными деревьями.

Урок 271 (жадные алгоритмы). Построение дерева решений — учебниковый пример жадной схемы «кандидаты → функция выбора → функция допустимости → фиксация без пересмотра», уже названной прямо в уроке 271 как пример задачи без доказанного свойства жадного выбора. Ссылка на NP-полноту оптимального построения дерева (Хайафил и Ривест, 1976), процитированная в конце урока 271, — именно та теорема, которая объясняет, почему CART, ID3 и C4.5 вынуждены довольствоваться жадным приближением.

Урок 304 (переобучение и недообучение). Раздел про переобучение дерева решений в этом уроке — прямое продолжение bias-variance разложения: неограниченная глубина дерева соответствует зоне низкого смещения и высокой дисперсии на графике сложности модели, а гиперпараметры max_depth, min_samples_leaf и обрезка дерева — это ровно тот же механизм регуляризации, который в общем виде обсуждался в уроке 304.

Урок 306 (кросс-валидация). Подбор оптимальных значений max_depth, min_samples_leaf и параметра обрезки ccp_alpha выполняется не на глаз, а через кросс-валидацию — без неё сравнение разных настроек регуляризации дерева было бы ненадёжным.

Урок 317 (Random Forest) и урок 318 (Gradient Boosting). Оба следующих урока строятся буквально поверх механизма этого урока: Random Forest выращивает множество независимых, намеренно неподрезанных (и потому высокодисперсных) деревьев решений и усредняет их предсказания, превращая индивидуальный недостаток одного дерева — высокую дисперсию — в источник силы ансамбля. Gradient Boosting идёт другим путём — строит последовательность маленьких неглубоких деревьев, каждое из которых обучается исправлять ошибки суммы всех предыдущих. Чтобы понять, что именно варьируется, усредняется или последовательно корректируется в этих моделях, нужно сначала до тонкостей понимать, как устроено и как строится одно дерево, — это и есть цель настоящего урока.

Интересные факты

🌳 Алгоритм CART, лежащий в основе sklearn.tree.DecisionTreeClassifier, был впервые опубликован в 1984 году — на два года раньше знаменитого ID3 Куинлана 1986 года, хотя в популярной литературе ID3 почти всегда упоминают первым как «исторически исходную» точку отсчёта для деревьев решений.

🌳 Первая версия алгоритма Куинлана — ID3 — была протестирована на задаче классификации шахматных эндшпилей и на данных о пригодности грунта для выращивания сои; ни один из этих датасетов не был похож на современные табличные задачи машинного обучения, но именно на них впервые была продемонстрирована практическая ценность построения дерева через прирост информации.

🌳 Индекс Джини, используемый в деревьях решений, назван в честь итальянского статистика Коррадо Джини, который ввёл его в 1912 году совершенно для другой цели — измерения неравенства доходов населения (тот самый коэффициент Джини из экономики) — и лишь спустя семьдесят лет эта же математическая идея оказалась удобной мерой «примеси» узла дерева.

🌳 Формула энтропии $H=-\sum p_i\log_2 p_i$ была введена Клодом Шенноном в 1948 году в работе «Математическая теория связи» для совершенно другой задачи — измерения количества информации, необходимого для передачи сообщения по каналу связи с шумом, — и уже оттуда, спустя почти сорок лет, перекочевала в алгоритм ID3.

Лайфхаки

💡 Перед тем как обучать дерево решений на реальных данных, всегда проверь распределение классов в целевой переменной: сильный дисбаланс классов заставит даже хорошо настроенное дерево скатываться к предсказанию мажоритарного класса почти везде — иногда полезнее заранее сбалансировать выборку или взвесить классы параметром class_weight="balanced".

💡 Не доверяй визуализации plot_tree на глубоких деревьях буквально — если дерево имеет глубину больше 5–6 уровней, картинка становится нечитаемой; для реальной интерпретации возьми export_text и посмотри на правила текстом, начиная с самых «уверенных» (с наибольшим числом объектов в листе).

💡 Если два признака на каком-то узле дают почти одинаковый прирост информации (как в задании 21 этого урока), не удивляйся нестабильности выбора признака при небольших изменениях обучающей выборки — это ожидаемое поведение жадного алгоритма на «ничьей», а не баг.

💡 Начинай подбор гиперпараметров дерева не с max_depth, а с min_samples_leaf — он напрямую контролирует, насколько «уверенным» разрешено быть каждому листу, и часто даёт более предсказуемый эффект на переобучение, чем абстрактное ограничение глубины.

💡 Прежде чем переходить к Random Forest и Gradient Boosting, обязательно обучи одно дерево решений на своей задаче и посмотри на извлечённые правила — даже если в итоге ты будешь использовать ансамбль ради точности, одно дерево почти всегда покажет тебе, какие признаки в принципе значимы, и станет базовой линией (baseline), с которой имеет смысл сравнивать более сложные модели.

💡 Атрибут feature_importances_ у обученного дерева считает, насколько сильно каждый признак в среднем уменьшил примесь (энтропию или Джини) по всем узлам, где он использовался, взвешенно по числу объектов в каждом узле — это быстрый и бесплатный способ первичного отбора признаков ещё до перехода к более тяжёлым моделям.

Дерево решений — редкий случай в машинном обучении, где абстрактная теория информатики (структура данных «дерево» из урока 256), абстрактная теория алгоритмов (жадная стратегия из урока 271) и математическая мера неопределённости из совсем другой области (энтропия Шеннона) сходятся в одной простой, при этом полностью прозрачной модели. Ты только что построил такую модель вручную, шаг за шагом, от первой строчки таблицы данных до готового списка правил «если… то…» — и теперь знаешь не просто как вызвать DecisionTreeClassifier.fit(), а что именно происходит внутри этого вызова. Это понимание не устареет ни в следующем уроке про Random Forest, ни через урок про Gradient Boosting — оно будет работать под капотом обеих моделей ровно так же, как работает сейчас.