01 — ВведениеЗачем нужны деревья

До сих пор мы изучали два алгоритма: линейную регрессию (для предсказания чисел) и логистическую регрессию (для классификации). Оба работают прекрасно, но у них есть важное ограничение — они рисуют только прямую линию между классами.

А что, если граница между классами не прямая? Что, если она ломаная, кусочная, сложной формы? Попробуйте мысленно провести прямую, которая отделит «спелый арбуз» от «неспелого», если это зависит одновременно от цвета, звука, размера и сорта. Или разделить прямой линией клетки с раком от здоровых клеток на медицинском снимке.

Деревья решений — это совершенно другой подход. Они не рисуют линии. Они задают вопросы. И через последовательность простых вопросов приходят к сложному ответу.

02 — ИнтуицияОсновная идея

Подумайте, как биолог определяет вид растения в поле. Он не знает сразу ответ — он идёт по определителю:

• Листья простые или сложные?
• Если простые — с зубцами или гладкие?
• Если с зубцами — цветки белые или жёлтые?

После 5–7 вопросов биолог уверенно называет вид. Каждый вопрос сокращает количество возможных ответов. Это и есть логика дерева решений.

Главное отличие: биолог и создатели Акинатора составляли вопросы вручную, опираясь на свои знания. Дерево решений придумывает вопросы само, глядя на данные. Именно это делает его алгоритмом машинного обучения.

03 — СтруктураАнатомия дерева

Математики называют эту структуру «дерево», потому что она похожа на ботаническое дерево, но растёт сверху вниз — корень наверху, листья внизу. Вот как она устроена:

Дерево всегда бинарное в классических реализациях: каждый вопрос имеет ровно два ответа. Любой сложный вопрос можно разбить на серию бинарных — это математически удобно.

04 — ИспользованиеКак делать предсказание

Начнём с более простой части: допустим, дерево уже обучено. Как использовать его, чтобы классифицировать новый объект?

Возьмём пример с Титаником. У нас обученное дерево и новый пассажир: мужчина, 30 лет, 3-й класс. Куда его отнести — выжил или погиб?

1. Начинаем с корня: «Пол — женщина?» → нет (мужчина) → идём вправо
2. Следующий узел: «Возраст ≤ 9,5?» → нет (30 лет) → идём вправо
3. Попадаем в лист: Погиб

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

05 — ПримененияДва вида задач

Деревья решений универсальны — они работают и для классификации, и для регрессии. Различие только в том, что хранится в листьях.

В этом курсе мы сосредоточимся на классификации — она чаще встречается на практике и проще для понимания. Но важно помнить, что регрессионные деревья тоже существуют и работают по тем же принципам.

06 — ОбучениеКак дерево обучается

Это главный и самый интересный вопрос. Мы видели, что дерево — это набор вопросов. Но откуда берутся эти вопросы? Как алгоритм решает, что спросить первым делом?

Принцип «чистоты»

Представьте, что у нас есть 100 пассажиров Титаника: 40 выжили, 60 погибли. Мы хотим разделить их на две группы одним вопросом. Какой вопрос будет лучшим?

Сравним два варианта:

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

Метрика Gini

Чтобы сравнивать вопросы численно, нужна формула «чистоты». Самая популярная — индекс Джини (Gini impurity). Идея простая: возьмём вероятности каждого класса в группе, возведём в квадрат, сложим, вычтем из единицы.

Не пугайтесь формулы — интуитивно всё просто:

• Если в группе все одного класса (идеальная чистота): p_A=1, p_B=0, Gini = 1 − 1 − 0 = 0
• Если половина на половину (худший случай): p_A=0,5, p_B=0,5, Gini = 1 − 0,25 − 0,25 = 0,5

Чем Gini меньше — тем группа чище. Ноль = идеал, 0,5 = полный хаос (для двух классов).

Прирост информации

Качество разбиения оценивают так: берут Gini до разбиения (для всей группы) и вычитают средневзвешенный Gini двух получившихся подгрупп. Чем больше разница — тем лучше вопрос.

Алгоритм перебирает все возможные вопросы по всем признакам и выбирает тот, у которого Gain максимальный. Это называется жадным подходом — алгоритм на каждом шаге выбирает локально лучший вариант, не заглядывая вперёд.

07 — АлгоритмРекурсивное построение

Теперь соберём всё вместе. Алгоритм построения дерева называется CART (Classification and Regression Trees) — один из самых известных алгоритмов в машинном обучении. Вот он целиком:

1. Взять всю обучающую выборку.
2. Для каждого признака и каждого возможного порога посчитать Gain.
3. Выбрать вопрос с максимальным Gain — это корень.
4. Разбить данные на две подгруппы по этому вопросу.
5. Для каждой подгруппы повторить шаги 2–4 (рекурсия).
6. Остановиться, когда:
   • в группе все объекты одного класса (Gini = 0), или
   • достигнута максимальная глубина дерева, или
   • в группе слишком мало объектов для дальнейшего разбиения.
7. Оставшиеся группы становятся листьями. В каждом листе записывается преобладающий класс.

Заметьте: алгоритм рекурсивный. Ту же процедуру, которую применяют ко всему набору данных, потом применяют к каждой подгруппе. Дерево строится сверху вниз, ветвь за ветвью.

08 — ОпасностьГлавный враг: переобучение

А что если позволить дереву строиться без ограничений? Оно продолжит делить данные, пока в каждом листе не останется ровно одна точка. Точность на обучающих данных будет 100%. Казалось бы — идеал?

Нет. Это и есть главная проблема деревьев — переобучение (overfitting).

Представьте, что вы готовитесь к экзамену, заучив наизусть все 50 задач из сборника. На контрольной будут другие 50 задач по той же теме — и вы провалитесь, потому что «учились» не понимать предмет, а запоминать ответы.

Точно так же необорудованное дерево запоминает конкретные точки, а не улавливает закономерности. Решение — не давать дереву расти слишком глубоко. Это называется регуляризацией.

Признаки переобучения

• Точность на обучении сильно выше, чем на тесте (например, 99% против 70%)
• Дерево очень глубокое и ветвистое
• В листьях часто лежит всего 1–2 объекта
• Результаты нестабильны — при небольшом изменении данных структура сильно меняется

09 — НастройкаОсновные гиперпараметры

Гиперпараметры — это настройки модели, которые мы задаём до обучения. В отличие от параметров (которые алгоритм учит сам), гиперпараметры подбирает человек. Для деревьев главные три:

На Python это выглядит так:

Правильные значения подбирают экспериментально — обычно через кросс-валидацию или grid search. Но это тема отдельного разговора.

10 — ИтогиПлюсы и минусы

Давайте подведём честный итог. У деревьев решений есть сильные и слабые стороны — знать обе стороны важно, чтобы понимать, когда применять этот алгоритм.

Сильные стороны

• Интерпретируемость. Дерево можно нарисовать и показать человеку. Врач, юрист или менеджер поймёт, почему модель приняла то или иное решение. Это бесценно в медицине и финансах.
• Не требует подготовки данных. Нормализация, кодирование категорий, масштабирование — всё это деревьям не нужно. Работают «из коробки» с любыми данными.
• Нелинейность. Улавливают сложные зависимости, которые не видит линейная модель.
• Скорость. Обучение быстрое даже на тысячах объектов. Предсказание — просто проход по дереву.
• Важность признаков. Дерево показывает, какие признаки реально влияют на результат.

Слабые стороны

• Склонность к переобучению. Без регуляризации дерево зазубривает данные.
• Нестабильность. Небольшое изменение данных может полностью перестроить дерево.
• Жадность. Алгоритм на каждом шаге выбирает локально лучший вопрос — глобально оптимальное дерево может выглядеть иначе, но его построение — очень сложная задача.
• Ступенчатые границы. Деревья рисуют только горизонтальные и вертикальные линии в пространстве признаков. Для плавных границ нужны другие модели.
• Уступают ансамблям. Одиночное дерево почти всегда проигрывает по точности ансамблям деревьев.

11 — СравнениеТри алгоритма, три границы

Мы уже знаем три алгоритма классификации: логистическую регрессию, k-ближайших соседей и деревья решений. Все они решают одну задачу — разделить объекты на классы. Но видят пространство признаков совершенно по-разному.

Посмотрите на одни и те же точки глазами трёх алгоритмов:

В чём суть различий

Логистическая регрессия проводит одну прямую линию через всё пространство. Слева от неё — класс A, справа — класс B. Математически это формула w₁·x₁ + w₂·x₂ + b = 0. Просто, быстро, устойчиво — но работает хорошо только когда классы действительно разделяются прямой.

K-ближайших соседей вообще ничего не строит заранее. Когда приходит новая точка, алгоритм ищет её k ближайших соседей в обучающих данных и проводит голосование: «3 из 5 соседей синие → ты тоже синяя». Граница получается плавной и извилистой — она возникает как побочный эффект того, где меняется состав соседей.

Дерево решений режет пространство прямыми линиями, параллельными осям: сначала вертикальной (x₁ > 0,5?), потом горизонтальной (x₂ ≤ 0,3?) и так далее. Получаются прямоугольные зоны — «ступеньки». Отсюда и характерный вид границы.

Таблица сравнения

Когда что выбирать

12 — ПерспективаЧто дальше

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

Оба подхода используют обычные деревья как «кирпичики». Поэтому всё, что вы сейчас узнали об одиночном дереве — фундамент для понимания самых мощных современных методов машинного обучения на табличных данных.