Разбираемся в ML без воды: от базы до Attention. Часть 9: Дерево решений

В восьмой части мы завершили изучение SVM и разобрались с Kernel Trick. Теперь пришло время познакомиться с деревьями решений — одним из самых популярных и интуитивно понятных алгоритмов машинного обучения.

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

Дерево решений

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

В конечном счёте множество данных разделяется на подмножества, удовлетворяющие тем или иным правилам разбиения. Количество таких подмножеств соответствует количеству листьев дерева.

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

Строим дерево и измеряем хаос

Что нам хотелось бы? Раз уж мы делим данные на подгруппы, было бы хорошо на каждом шаге выбрать такой признак и такое пороговое значение, которые разделят данные на максимально однородные (чистые) группы. В идеале — чтобы в каждом подмножестве оказались объекты только одного класса.

Но как компьютеру понять и сравнить, какое разбиение “чище”? Для этого введем критерии информативности, которые измеряют уровень неопределенности или хаоса в данных. В задачах классификации их два, причем, с одним мы познакомились еще в в шестой части, когда изучали логистическую регрессию и разбирали понятие кросс-энтропии.

1. Entropy (Энтропия Шеннона)

Напомню вкратце, что в шестой части мы подробно разбирали, что энтропия — это мера случайности, хаоса или неопределенности распределения. Мы даже считали её на примере монетки: если шансы 50 на 50, энтропия максимальна и равна единице. Если распределение смещено (0.9 на 0.1), энтропия падает до 0.47, так как неопределенности становится меньше.

В двух словах, энтропия — это число, которое показывает, насколько уверенно мы можем сделать предсказание. Причем, если она равна 1 (для двух классов), то мы способны лишь ткнуть пальцем в небо, а с её уменьшением, растут наши экстрасенсорные навыки.

В деревьях решений энтропия работает аналогично. Она измеряет хаос в конкретном узле (ноде) дерева. Формула для выборки с классами выглядит так:

Где это доля (вероятность) объектов -го класса в текущем узле.

2. Gini Impurity (Критерий Джини)

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

Критерий Джини показывает вероятность того, что случайно выбранный объект из нашего узла будет классифицирован неправильно, если мы назначим ему класс наугад (просто на основе распределения классов в этой же кучке).

Формула для выборки с классами выглядит так:

Заметим, что как и в случае с энтропией, в идеальном варианте мы получим ноль. Однако если рассмотреть худший случай (объекты в ноде распределены поровну между классами), то энтропия будет равна , а Джини даст скромные .

С вычислительной точки зрения Джини работает эффективнее, ибо компьютеру не приходится лишний раз вычислять логарифмы, поэтому на практике обычно выбирают именно его. К слову, в библиотеке scikit-learn он как раз и используется по умолчанию. И, казалось бы, раз их поведение примерно одинаковое, зачем вообще использовать энтропию с логарифмами?

Задайте этот вопрос МЛ инженерам, и большинство из них скажет, что незачем, потому что разница практически незаметна. И они будут правы. В большинстве прикладных задач разница действительно будет минимальной. Но если копнуть чуть глубже, энтропия и Джини имеют абсолютно разную философию:

• Энтропия строит более сбалансированные деревья. Логарифмичность энтропии делает критерий очень чувствительным к малейшим изменениям вероятностей вблизи “пика хаоса”. Она до последнего пытается найти скрытую структуру и сбалансировать ветви.

• Джини жадный и любит доминирующие классы. Критерий Джини пытается сразу же изолировать самый частый класс. Но такое разделение может привести к тому, что во второй ветке получится каша из оставшихся классов.

• Джини хуже работает на несбалансированных данных. Если в датасете 95% здоровых пациентов и 5% больных, Джини может просто создать один гигантский список с предсказанием “здоров”. Энтропия же за счет логарифма почувствует скрытую неопределенность этих 5% редкого класса гораздо лучше и продолжит копать глубже.

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

Information Gain (Прирост информации)

Information Gain (IG) — это метрика, которая математически оценивает “выгоду” от конкретного разделения. Она показывает, насколько снижается хаос после очередного разделения.

Идея достаточно простая: состоит в оценивании разницы между исходным хаосом и полученным, с учетом масштабов. Формула для разбиения родительского узла на дочерние подмножества выглядит следующим образом:

где

• — это исходный хаос (энтропия или Джини) в родительском узле. То есть то, что мы имели ДО разделения.

• — это хаос в полученных дочерних узлах ПОСЛЕ того, как мы разделили данные выбранным признаком (вопросом).

• — это вес (доля) объектов, которая ушла в конкретную -ю ветку.

  Здесь — количество объектов в дочернем узле, а — общее количество объектов в родительском узле.

По сути, вся задача обучения дерева решений сводится к одной простой рекурсивной вещи: для каждого текущего узла Q нам нужно выбрать такой признак A (и такой порог для него), который максимизирует Information Gain.

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

Осталось понять как дерево решений задает те самые “разделяющие вопросы”. Давайте разбираться.

Формирование предикатов для разбиения признакового пространства

Начнем с приятного. В предыдущих частях, когда мы мучили линейные модели и SVM, нам приходилось постоянно возиться с кодированием текста в числа (One-Hot Encoding, Label Encoding и т.д.). Подавать сырые категории напрямую в те алгоритмы было нельзя — имя на цвет не умножишь.

Деревья прекрасно работают с категориальными признаками. Если у нас есть признак “Цвет шерсти” со значениями [Рыжий, Черный, Белый], дерево просто берет эти категории как готовые варианты для вопросов: “Цвет == Рыжий?”, “Цвет == Черный?”. Ему не нужно переводить котов и собак в единицы и нули, чтобы посчитать энтропию или Джини. Оно просто считает количество объектов по факту их наличия в ноде.

Здесь возникает вопрос: обязательно ли должно получаться ровно 2 нода? Математически — нет. Старые классические алгоритмы из учебников (например, C4.5) умеют строить небинарные деревья. Если у нас есть признак “цвет шерсти” с тремя категориями, дерево за один шаг создаст три дочерних нода.

Но в реальном мире (да и в том же scikit-learn) практически всегда используется алгоритм CART, который строит строго бинарные деревья (всегда делит узел строго на 2 части). Это сделано для защиты от переобучения.

Если бы дерево создавало по ветке на каждую категорию, то после признака вроде “Город” с 500 значениями модель превратится в лучшем случае во что-то похожее на старую-добрую игру Akinator.
Бинарное же дерево просто скомбинирует категории или разделит их последовательно (сначала отсечет один город, а на следующем уровне — другой), сохранив более стабильную и контролируемую структуру.

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

Происходит это всего в три шага:

1. Сортировка: Все уникальные значения числового признака, которые есть у объектов в текущем узле, и сортируются по возрастанию.

2. Поиск серединных точек: Вопросы создаются строго как среднее арифметическое между каждыми двумя соседними значениями после сортировки. Это и есть наши потенциальные пороги разбиения.

3. Выбор лучшего через IG: Полученный список порогов отправляется на кастинг. Для каждого порога рассчитывается IG, и дерево выбирает вариант с максимальным IG.

К слову, повторное использование категориального признака ничего не даст, однако нигде не запрещается использовать один и тот же числовой признак дважды. Например, сначала можно использовать age <= 50, а затем age >= 25. В этом плане деревья гораздо гибче линейных моделей, которые строят одну общую прямую для всего признака.

Проблема переобучения

Дерево решений жадный алгоритм. Если дать ему полную волю и никак не ограничивать в росте, оно будет плодить узлы до тех пор, пока в каждом финальном листе не останется ровно по одному объекту из обучающей выборки.

Получим некий аналог kNN для k=1. На трейне гордые 100% точности, а на валидации или реальных данных модель ведет себя как студент на экзамене, который выучил только один билет.

Чтобы не уйти в переобучение, можно сделать одно из двух:
Либо изначально ограничить рост (критерии остановки или Pre-pruning), либо дать дереву вырасти на максимум, а потом обрезать лишнее (стрижка дерева или Post-pruning).

Pre-pruning (Ранняя остановка)

Мы бьем алгоритм по рукам прямо во время обучения, заставляя его остановиться до того, как он начнет зазубривать шум. За это отвечают следующие гиперпараметры:

• Максимальная глубина max_depth: Ограничение на количество уровней дерева. Если поставить max_depth=3, алгоритм сделает максимум три шага вниз от корня и остановится, даже если в узлах еще остался хаос. Короткие деревья обычно недообучены, слишком глубокие — переобучены;

• Минимальное число объектов для сплита min_samples_split: Сколько минимум объектов должно быть в узле, чтобы узел превратился в лист. Если в нод пришло 10 объектов, порог у нас 20, то этот нод автоматически становится финальным листом и дальше не режется. При большом значении обычно идет недообучение, а при маленьком — переобучение;

• Минимальное число объектов в дочернем нодеmin_samples_leaf: Сколько объектов обязано остаться в каждом из получившихся дочерних нодов после разделения. Если вопрос дает хороший Information Gain, но при этом в одну ветку улетает 100 объектов, а в другую — всего 1, то при min_samples_leaf=2 алгоритм заблокирует этот вопрос. Защищает от создания листьев-одиночек, заточенных под шум. Большое значение ведет к переобучению, маленькое — к недообучению;

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

• Минимальный прирост информации min_impurity_decrease: Дерево прекращает делить нод, если максимальный полученный Information Gain для всех возможных вопросов оказывается меньше определенного порога : . Причем, чем больше , тем меньше шанс переобучения.

Естественно, никто не запрещает придумать и другие критерии для остановки дерева. Например, можно экспериментально измерить время, за которое дерево вырастает до самого конца без ограничений, и дать ему на обучение всего 80% от этого времени (возможно, в каких-то специфических задачах это даже сработает). Но суть всегда остается одной и той же: нам нужно вовремя нажать на тормоза, чтобы дерево не росло до самого конца.

Post-pruning (Стрижка дерева)

Если при Pre-pruning мы бьем алгоритм по рукам в процессе роста, то в Post-pruning мы даем дереву полную свободу. Мы позволяем ему вырасти на абсолютный максимум, а затем берем садовые ножницы и начинаем стрижку.

Идея в том, что мы берем готовое гигантское дерево, идем снизу вверх (от листьев к корню) и для каждой веточки проводим мысленный эксперимент:
“А что, если отрезать эти два листа и превращать их родительский узел в финальный лист? Сильно ли упадет качество модели?”.
Если качество на валидационной выборке не изменилось или даже выросло (потому что мы убрали зазубренный шум), ветка срезается навсегда.

Математически это минимизация штрафной функции стоимости дерева:

Где

• — количество листьев в исходном дереве

• R(T) — риск дерева T (суммарный хаос по Джини/энтропии)

• — количество листьев в дереве.

• (Cost-Complexity Pruning alpha) — гиперпараметр, коэффициент регуляризации

  Если , штрафа за сложность нет. Дерево растет огромным и переобученным. При увеличении , модель понимает, что каждый новый лист теперь имеет цену. Чтобы минимизировать функцию, ему выгодно отсекать листья, которые не приносят огромной пользы.

Что в итоге выбрать?

Post-pruning, скорее всего, считается более правильным подходом. Дело в том, что при ранней остановке дерево может наткнуться на признак с плохим Information Gain и остановиться. Но если бы мы разрешили ему сделать этот один “плохой” шаг, то на следующем уровне глубины могли бы открыться еще два признака, которые дали бы гениальное разделение. Pre-pruning об этом никогда не узнает, а Post-pruning — узнает, оценит и сохранит эту ветку.

С другой стороны Post-pruning требует огромных вычислительных ресурсов: растить дерево до упора, а потом перебирать все ветки обратно — это долго. Поэтому на практике в большинстве случаев легче крутить всякие max_depth и min_samples_split.

Особенности для регрессии

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

Когда мы обучаем дерево решений для регрессии, принципиально меняются две вещи:

1. Финальный ответ в листьях

   Как мы уже знаем, для классификации ответом становится самый частый класс в листе. В задаче регрессии ответом в финальном листе становится среднее арифметическое целевых значений всех объектов, которые в этот лист попали. (В редких случаях вместо среднего берут медиану).

2. Критерии информативности

Так как классов нет, мы не можем использовать критерии Джини или энтропию. Вместо них мерой хаоса в ноде становится дисперсия (Variance) выборки или среднеквадратичная ошибка (MSE):

Где — реальные числовые метки объектов в узле, а — их среднее арифметическое.

Суть в том, что здесь точно так же рассчитывается Information Gain для каждого вопроса-кандидата, но теперь модель ищет такой сплит, который сильнее всего уменьшит разброс (дисперсию) чисел в дочерних нодах (минимизация ).

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

Именно из-за такого подхода у классического регрессионного дерева есть одна большая проблема: представьте, что мы построили дерево на достаточно хорошем датасете с недвижимостью, а нашей целью является определение стоимости квартиры. Допустим, обучение прошло более чем успешно, все метрики у нас идеальные, никакого пере- или недообучения нет. И вот в один прекрасный день к нашей модели обращается объект: 100500-этажный дом с золотыми стенами, частным аэропортом и т. п. (в общем, вы меня поняли). Как думаете, какую оценку стоимости даст наша модель?

Оказывается, из-за того, что каждый лист дает предсказание строго по среднему арифметическому своих объектов, модель оценит этот чудо-дворец не выше цены самого дорогого дома из обучающего датасета. Аналогичная ситуация произойдет и с другого полюса: условная будка для собаки получит стоимость не меньше, чем цена самой дешевой однушки в базе. То есть поведение дерева может быть адекватным только на тех объектах, которые сопоставимы с данными из обучения. На нестандартных данных, требующих экстраполяции, дерево абсолютно бессильно.

Конечно, умные люди придумали решение для этой проблемы и даже не одно: например, Модельные деревья (Model Trees). Идея заключается в скрещивании дерева с линейной регрессией: вместо константного среднего мы строим полноценную модель линейной регрессии внутри каждого листа. Но такие подходы уже выходят за рамки классического дерева решений.

Плюсы и минусы + заключение

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

Преимущества:

• Абсолютная интерпретируемость. Мы всегда можем проследить всю цепочку условий от корня до листа и точно понять, почему алгоритм принял именно такое решение;

• Никаких энкодингов. Дерево умеет работать с категориальными признаками;

• Устойчивость к масштабу. Деревьям совершенно не важна стандартизация или нормализация признаков (StandardScaler можно смело выбрасывать);

• Устойчивость к выбросам. Если в данных затесался один аномальный клиент с доходом в миллиард рублей, линейная модель сойдет с ума. Дерево же просто создаст под него один аккуратный сплит и изолирует его, не испортив предсказания для остальных.

Недостатки:

• Склонность к переобучению. Без жесткого контроля дерево превращается в шпаргалку, зазубривая шум и выдавая 100% точность на трейне при ужасном качестве в реальном мире.

• Отсутствие экстраполяции. В задачах регрессии дерево физически не способно предсказать число за пределами диапазона обучающей выборки.

• Сильная неустойчивость. Малейшее изменение в обучающей выборке (выкинуть/добавить всего пару строк) может привести к тому, что алгоритм выберет в корне абсолютно другой признак и в итоге у нас получится совершенно другое дерево.

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

Но что, если мы соберем целый лес из сотен таких нестабильных деревьев, чтобы они компенсировали ошибки друг друга и выдавали хороший усредненный результат?

Именно этой масштабной идее “мудрости толпы” и будет посвящена следующая часть, в которой мы детально разберем, как устроен Бэггинг, откуда берется 63.2% и как скрестив случайные объекты со случайными признаками, можно получить один из самых мощных алгоритмов — Случайный Лес (Random Forest).