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

Коротко

Definition

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

Дерево решений строит иерархическую структуру:

• внутренние узлы задают условия по признакам;
• рёбра соответствуют исходам условий;
• листья содержат итоговое предсказание.

Дерево можно читать как набор правил вида:

$$\text{если условие 1, затем условие 2, затем условие 3, то предсказание}$$

Интуиция

Дерево решений похоже на серию вопросов.

Например, для классификации клиента:

1. Возраст больше 30?
2. Доход выше заданного порога?
3. Были ли просрочки?
4. Какой итоговый класс в листе?

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

Главная идея:

$$\text{хорошее разделение}\Rightarrow \text{более чистые листья}\Rightarrow \text{лучшее предсказание}$$

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

Дерево решений относится к supervised learning и может решать:

Характеристика	Значение
Тип модели	Непараметрическая модель
Тип обучения	Обучение с учителем
Задачи	Задачи классификации, Задачи регрессии
Тип данных	Чаще всего Табличные данные
Выход классификации	Класс или вероятности классов
Выход регрессии	Численное значение

Для классификации целевая переменная обычно принимает значения:

$$y\in \{0,1,\dots ,K-1\}$$

Для регрессии:

$$y\in \mathbb{R}$$

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

Входы и выходы

Вход дерева решений:

$$X\in {\mathbb{R}}^{n\times d}$$

где:

• $n$ — число объектов;
• $d$ — число признаков;
• $X$ — матрица признаков.

Для классификации выход:

• предсказанный класс;
• вероятности классов в листе.

Для регрессии выход:

• среднее или медианное значение целевой переменной в листе.

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

Как обучается

Обучение дерева — это жадный рекурсивный процесс.

Общий алгоритм:

1. Инициализировать корневой узел всем обучающим набором данных.
2. Для каждого признака перебрать возможные варианты разделения.
3. Для каждого разделения оценить качество дочерних узлов.
4. Выбрать лучшее разделение.
5. Разделить данные на дочерние узлы.
6. Повторять процесс для каждого дочернего узла.
7. Остановиться при выполнении условий остановки.

Для количественного признака возможные пороги часто выбирают между соседними отсортированными уникальными значениями.

Например, если значения признака:

$$2,5,8$$

то возможные пороги:

$$3.5,6.5$$

Для категориальных признаков часто используют кодирование или специальные правила разделения. В простых реализациях категориальные признаки можно превратить в бинарные признаки через one-hot encoding.

Функция потерь

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

Вместо этого дерево выбирает разбиения по критерию качества узла.

Классификация: индекс Джини

Индекс Джини измеряет impurity, то есть неоднородность классов в узле:

$$G(Y)=1-\sum _{k=1}^K{p}_k^2$$

где $p_k$ — доля объектов класса $k$ в узле.

Если в узле все объекты одного класса, то impurity равна 0. Если классы сильно перемешаны, impurity выше.

Для пары дочерних узлов считают взвешенную impurity:

$$G_{\text{split}}=\frac{n_1}{N}{G}_1+\frac{n_2}{N}{G}_2$$

где:

• $n_1$, $n_2$ — число объектов в дочерних узлах;
• $N$ — число объектов в исходном узле;
• $G_1$, $G_2$ — impurity дочерних узлов.

Алгоритм выбирает разделение, которое уменьшает impurity сильнее всего.

Классификация: энтропия

Энтропия также измеряет неоднородность классов:

$$H(Y)=-\sum _{k=1}^K{p}_k{\log }_2{p}_k$$

Для пары узлов:

$$H_{\text{split}}=\frac{n_1}{N}{H}_1+\frac{n_2}{N}{H}_2$$

Связанная идея — information gain:

$$IG=H_{\text{parent}}-H_{\text{split}}$$

Чем больше information gain, тем лучше разделение.

Регрессия: уменьшение разброса

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

Часто используют MSE:

$$MSE=\frac{1}{n}\sum _{i=1}^n(y_i-\bar{y}{)}^2$$

Для split считают взвешенную ошибку в дочерних узлах и выбирают разбиение с наименьшим значением.

Гиперпараметры

Основные гиперпараметры дерева решений:

• критерий разбиения;
• максимальная глубина;
• минимальное число объектов в узле для разбиения;
• минимальное число объектов в листе;
• максимальное число листьев;
• максимальное число признаков, рассматриваемых при split;
• минимальное уменьшение impurity для split;
• веса классов;
• коэффициент регуляризации или pruning-параметры.

Критерий разбиения

Для классификации часто используют:

Критерий	Смысл
Gini impurity	Насколько перемешаны классы в узле
Entropy / information gain	Насколько split уменьшает неопределённость классов

Для регрессии используют критерии вроде:

• squared error;
• absolute error;
• Poisson deviance для специальных задач.

Ограничения глубины

Ограничения глубины и размера листьев нужны для борьбы с переобучением.

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

Типичные параметры регуляризации:

• max_depth;
• min_samples_split;
• min_samples_leaf;
• max_leaf_nodes;
• min_impurity_decrease.

Когда использовать

Дерево решений хорошо использовать, если:

• данные табличные;
• важна интерпретируемость;
• нужно получить понятные правила;
• признаки имеют нелинейные зависимости;
• есть взаимодействия между признаками;
• нужен простой baseline;
• не хочется сильно усложнять предобработку.

Дерево решений может работать и для классификации, и для регрессии.

Преимущество: его можно визуализировать и объяснить человеку.

Когда не использовать

Дерево решений может быть плохим выбором, если:

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

Одиночное дерево часто уступает ансамблям деревьев:

• Случайный лес;
• Градиентный бустинг.

Эти модели строят много деревьев и обычно дают более устойчивое качество.

Предсказание

Классификация

Для классификации объект проходит от корня дерева до листа.

В листе вероятность класса $k$ можно оценить как долю объектов этого класса среди обучающих объектов, попавших в лист:

$$p_k=\frac{n_k}{n}$$

где:

• $n_k$ — число объектов класса $k$ в листе;
• $n$ — общее число объектов в листе.

Предсказывается класс с максимальной вероятностью:

$$\hat{y}=\arg \underset{k}{\max }{p}_k$$

Регрессия

Для регрессии объект также проходит до листа.

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

$$\hat{y}=\frac{1}{n}\sum _{i=1}^n{y}_i$$

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

Метрики оценки

Для классификации используют:

• Метрики качества классификаторов;
• ROC-кривая.

Для регрессии используют:

• Метрики качества регрессоров.

Важно оценивать дерево не только на train, но и на validation/test. Глубокое дерево может легко переобучиться.

Типичные ошибки понимания

Думать, что дерево всегда хорошо обобщает

Дерево решений может идеально подогнаться под train-выборку, но плохо работать на новых данных. Поэтому важны ограничения глубины, pruning и validation.

Считать дерево линейной моделью

Дерево не строит одну линейную границу. Оно разбивает пространство признаков на области с помощью последовательности условий.

Игнорировать нестабильность дерева

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

Интерпретировать вероятности слишком буквально

Вероятности в листьях — это доли классов среди обучающих объектов. Если в листе мало объектов, такие вероятности могут быть шумными.

Не ограничивать глубину

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

Минимальный пример

Пусть нужно классифицировать клиентов по риску ухода.

Клиент	Месяцев в сервисе	Жалобы	Ушёл
1	2	3	yes
2	4	2	yes
3	20	0	no
4	30	1	no

Дерево может построить простое правило:

1. Если Месяцев в сервисе <= 6, перейти в левый узел.
2. Иначе перейти в правый узел.
3. В левом узле большинство объектов — yes.
4. В правом узле большинство объектов — no.

Такое дерево можно прочитать как правило:

$$\text{если клиент новый, риск ухода выше}$$

Это делает дерево решений удобным для объяснения, но в реальных данных дерево обычно требует ограничений, чтобы не переобучиться.

Связанные понятия

• Регуляризация