Решающие деревья

Каждый классификатор из раздела о линейных моделях, бинарный или многоклассовый, оценивает объект взвешенной суммой его признаков. Взвешенная сумма не может выразить взаимодействие (interaction) — правило, в котором влияние одного признака зависит от значения другого: «высокий доход снижает риск дефолта, если только долг тоже не высок». Заметка о ядрах добавила взаимодействия через отображение признаков (feature map), но ядро нужно выбирать, стоимость растёт как квадрат размера выборки, а входы должны быть числами в сравнимых масштабах. Табличные данные редко таковы: в них смешаны счётчики, денежные суммы, категории и пропущенные значения. Решающее дерево (decision tree) справляется со всем этим с помощью простейшего строительного блока — вопроса «да или нет» об одном признаке, а взаимодействия строит, задавая следующий вопрос только по одну сторону от предыдущего ответа.

Обозначения. Обучающая выборка — $(x_i, y_i)$, $i = 1, \dots, n$, где $x_i \in \mathbb R^d$, а $x_{ij}$ — её $j$-й признак. Узел (node) — множество $S$ индексов обучающих объектов; разбиение (split) $(j, t)$ отправляет $i \in S$ в левого потомка $S_\ell = \{i \in S : x_{ij} \le t\}$ или в правого потомка $S_r = S \setminus S_\ell$. В классификации с $K$ классами $p_k = \frac{1}{|S|} \sum_{i \in S} [y_i = k]$ — доля класса $k$ в узле. $H(S)$ — неоднородность (impurity): число, равное нулю, когда узел чистый. Листья $S_1, \dots, S_J$ дерева разбивают пространство входов на области $A_1, \dots, A_J$.

Что вычисляет дерево#

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

$$f(x) = \sum_{m=1}^{J} c_m \, [x \in A_m] ,$$

где $c_m$ — значение в листе $m$. Если посмотреть иначе, это линейная модель над $J$ признаками-индикаторами: дерево сначала конструирует признаки $[x \in A_m]$ по данным, а затем подбирает по одному весу на признак. Путь от корня до листа — конъюнкция, «$x_1 > 0.44$ и $x_2 > 0.485$», и это ровно тот вид взаимодействия, которого недостаёт взвешенной сумме.

Рисунок

Решающее дерево и разбиение плоскости

На рисунке такое дерево строится по 18 точкам. Классы меняются местами в зависимости от $x_1$: слева класс 1 находится при малых $x_2$, справа — при больших $x_2$. Никакая прямая их не разделяет, и никакая взвешенная сумма $x_1$ и $x_2$ их не описывает. Дереву нужны три вопроса:

1. Корень спрашивает об $x_1$; слева остаётся 8 точек, из них 2 класса 1, справа 10 точек, из них 7 класса 1.
2. Левый узел спрашивает $x_2 \le 0.315$.
3. Правый узел спрашивает $x_2 \le 0.485$ — другой порог по тому же признаку.
4. Остаются четыре чистых листа, и влияние $x_2$ меняет знак между двумя половинами.

Из вида вопросов следуют два свойства. Дерево только сравнивает каждый признак с порогами, поэтому не меняется при любом возрастающем преобразовании признака: логарифмирование дохода или его стандартизация дают то же дерево. И каждая граница — лесенка из отрезков, параллельных осям, поэтому граница вдоль диагонали, которую один линейный классификатор проводит точно, стоит дереву многих листьев. Разбиения по линейным комбинациям $\langle w, x \rangle \le t$ существуют, но используются редко: их веса трудно оптимизировать дискретным перебором, и они теряют и инвариантность, и читаемость (Hastie, Tibshirani and Friedman, 2009, раздел 9.2.4).

Насколько хорошо разбиение?#

Разбиение хорошее, если его потомки чище родителя. Неоднородность узла лучше всего определить как потери лучшего константного предсказания в нём:

$$H(S) = \min_{c} \frac{1}{|S|} \sum_{i \in S} L(y_i, c) ,$$

а прирост (gain) от разбиения — как уменьшение неоднородности, взвешенной по размерам:

$$\Delta(j, t) = H(S) - \frac{|S_\ell|}{|S|} H(S_\ell) - \frac{|S_r|}{|S|} H(S_r) .$$

Разные функции потерь дают знакомые критерии.

• Регрессия, квадратичная ошибка. Лучшая константа — среднее $\bar y_S$, а $H(S) = \frac{1}{|S|} \sum_{i \in S} (y_i - \bar y_S)^2$ — дисперсия значений целевой переменной в узле. Для шести значений $1, 2, 3, 7, 8, 9$ дисперсия равна $58/6 = 9.67$; разбиение между 3 и 7 оставляет два узла с дисперсией $2/3$ каждый, прирост $9.0$. С абсолютной ошибкой лучшая константа — медиана, а неоднородность — среднее абсолютное отклонение от неё; это то же соответствие функции потерь и сводной характеристики, что и в заметке об условном математическом ожидании.
• Классификация, логистическая функция потерь (log-loss). Предскажем распределение $c = (c_1, \dots, c_K)$ для каждой точки узла и заплатим $-\log c_{y_i}$. Средние потери равны $-\sum_k p_k \log c_k$ — кросс-энтропии между долями классов и $c$, которая минимальна при $c = p$. Поэтому неоднородность — это энтропия $H(S) = -\sum_k p_k \log p_k$ долей классов, ожидаемая неожиданность из заметки об энтропии, а прирост — информационный выигрыш (information gain) алгоритма ID3 (Quinlan, 1986).
• Классификация, квадратичная ошибка на one-hot-метках (мера Брайера, Brier score). Для каждого класса $k$ индикатор $[y_i = k]$ — величина со значениями 0/1 и средним $p_k$; лучшая константа для неё — $p_k$, а её средний квадрат отклонения равен $p_k(1 - p_k)$, дисперсии бернуллиевской величины. Сумма по классам даёт индекс Джини (Gini index) алгоритма CART (Breiman et al., 1984):

$$H_{\text{Gini}}(S) = \sum_{k=1}^{K} p_k (1 - p_k) = 1 - \sum_{k=1}^{K} p_k^2 .$$

• Классификация, функция потерь 0–1. Лучшая константа — самый частый класс, а $H(S) = 1 - \max_k p_k$ — доля ошибок (misclassification rate) узла.

Почему не разбивать по доле ошибок — величине, которая в конечном счёте нас интересует? Потому что она слишком груба. Возьмём узел с 8 точками каждого класса и два кандидата: разбиение A даёт потомков с численностями классов $(7, 3)$ и $(1, 5)$, разбиение B — $(8, 4)$ и $(0, 4)$. Оба делают 4 ошибки, так что доля ошибок у обоих падает с $0.5$ до $0.25$. B создаёт чистый узел, который больше не нужно разбивать, и оба гладких критерия это видят: взвешенный индекс Джини равен $0.367$ для A и $0.333$ для B, взвешенная энтропия — $0.795$ и $0.689$ бита. Кроме того, доля ошибок кусочно-линейна по долям классов, поэтому многие разбиения дают одинаковое значение, и разбиение может иметь нулевой прирост по доле ошибок, хотя готовит идеальное разбиение уровнем ниже. Джини и энтропия строго вогнуты по $p$, поэтому прирост строго положителен, если доли классов в потомках отличаются от долей в родителе; на практике они выбирают почти одинаковые деревья (то же сравнение есть у Hastie, Tibshirani and Friedman, 2009, раздел 9.2.3).

Для двух классов индекс Джини равен $2p(1 - p)$, удвоенной дисперсии метки 0/1. Поэтому классификационное дерево, выращенное по Джини, — это регрессионное дерево на метках 0/1, а значения $p$ в его листьях — оценки вероятности класса 1.

Жадный поиск разбиений и его стоимость#

Найти бинарное дерево, которое опознаёт каждую обучающую точку за наименьшее ожидаемое число проверок, то есть с наименьшей суммой длин путей от корня до листьев, — NP-полная задача (Hyafil and Rivest, 1976), поэтому любой практический алгоритм жадный: выбрать лучшее разбиение корня, затем рекурсивно перейти в каждого потомка и никогда не пересматривать принятые решения. Для одного узла и одного признака отсортируем $|S|$ значений; пороги-кандидаты — середины между соседними различными значениями, их не больше $|S| - 1$. Если перебирать их по порядку, перенося по одной точке из правого потомка в левого, то численности классов (или суммы $\sum y_i$ и $\sum y_i^2$ в регрессии) обновляются за константное время, и прирост тоже. Поэтому узел стоит $O(d \, |S| \log |S|)$ на сортировку и $O(d \, |S|)$ на проход. Узлы одной глубины разбивают обучающую выборку, так что один уровень дерева стоит $O(d \, n \log n)$, а дерево глубины $D$ — $O(D \, d \, n \log n)$; если отсортировать каждый признак один раз в начале и сохранять порядок при разбиении данных, повторные сортировки исчезают.

У жадности есть цена. На шаблоне XOR — четыре точки, класс 1 в $(0, 1)$ и $(1, 0)$, класс 0 в $(0, 0)$ и $(1, 1)$ — любое одиночное разбиение оставляет по одной точке каждого класса с каждой стороны: прирост любого разбиения корня равен нулю, хотя два уровня разбиений классифицируют четыре точки безошибочно. Жадный алгоритм, который отвергает разбиения без прироста, не сделает и первого шага; тот, что их принимает, найдёт дерево. Для больших наборов данных библиотеки заменяют точный перебор гистограммой: каждый признак один раз разбивается не более чем на несколько сотен бинов, и пробуются только границы бинов. Построение гистограммы узла по-прежнему проходит по каждой его точке один раз, $O(d \, |S|)$, но сортировка исчезает, а перебор порогов стоит $O(d \, B)$ для $B$ бинов вместо $O(d \, |S|)$; после однократного разбиения на бины дерево глубины $D$ стоит $O(D \, d \, n)$. На этом построены библиотеки бустинга из заметки о градиентном бустинге.

Когда остановиться: правила остановки и обрезка#

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

Правила остановки (stopping rules) прерывают рекурсию раньше: максимальная глубина, минимальное число точек в листе или для разбиения, максимальное число листьев, минимальный прирост. Они дёшевы, и именно их библиотеки предлагают в первую очередь. Их слабость — та же проблема XOR в другом обличье: разбиение, которое выглядит бесполезным, может открыть дорогу полезному под ним, и порог на прирост останавливает слишком рано (Hastie, Tibshirani and Friedman, 2009, раздел 9.2.2).

Обрезка (pruning) сначала выращивает большое дерево $T_0$, а затем укорачивает его. Стоимостно-сложностная обрезка (cost-complexity pruning; Breiman et al., 1984) назначает каждому листу цену $\alpha \ge 0$:

$$C_\alpha(T) = R(T) + \alpha \, |T| ,$$

где $R(T)$ — потери на обучении поддерева $T \subseteq T_0$ (суммарная неоднородность его листьев, взвешенная по их размерам, или число ошибок на обучении), а $|T|$ — число его листьев. Для каждого $\alpha$ существует единственное наименьшее поддерево, минимизирующее $C_\alpha$, и с ростом $\alpha$ минимизаторы образуют вложенную последовательность от $T_0$ до одного корня. Последовательность находится обрезкой по самому слабому звену (weakest-link pruning). Для внутреннего узла $s$ с поддеревом $T_s$ свёртывание $s$ в лист повышает потери с $R(T_s)$ до $R(s)$ и убирает $|T_s| - 1$ листьев, поэтому оно окупается, как только

$$\alpha \ge g(s) = \frac{R(s) - R(T_s)}{|T_s| - 1} .$$

Первым свёртывается узел с наименьшим $g(s)$, затем $g$ пересчитывается, и так далее. Игрушечный пример с подсчётом ошибок на обучении: узел $s$ как лист сделал бы 6 ошибок, а со своим поддеревом из 4 листьев делает 2, поэтому $g(s) = (6 - 2)/3 = 1.33$; узел $u$ как лист сделал бы 3 ошибки, а с 2 листьями делает 1, поэтому $g(u) = (3 - 1)/1 = 2$. Когда $\alpha$ переходит через $1.33$, первым обрезается $s$, через $2$ — $u$. Само значение $\alpha$ выбирается кросс-валидацией, как в заметке о валидации. На данных о раке груди (398 обучающих и 171 тестовая точка, 30 признаков) полностью выращенное дерево имеет 16 листьев, глубину 6 и долю правильных ответов (accuracy) на обучении 1.0, а на тесте достигает $0.906$; стоимостно-сложностная обрезка с $\alpha = 0.0088$, выбранным 5-кратной кросс-валидацией, оставляет 6 листьев и глубину 4, с долей правильных ответов $0.977$ на обучении и $0.918$ на тесте.

$C_\alpha$ имеет вид любой регуляризованной целевой функции этого курса: потери на обучении плюс штраф за сложность, здесь — число листьев вместо нормы весов, как в заметке о регуляризации.

Категориальные признаки и пропуски#

Категориальные признаки. У признака с $q$ неупорядоченными значениями (уровнями), например города, нет порогов. Естественное бинарное разбиение отправляет влево подмножество уровней, и таких подмножеств $2^{q-1} - 1$ — слишком много, чтобы перебрать их при больших $q$. Для двух классов есть короткий путь: упорядочить уровни по доле класса 1 и пробовать только $q - 1$ разбиений, согласованных с этим порядком; лучшее из них — лучшее среди всех подмножеств для Джини и энтропии, и то же верно для квадратичной ошибки, если упорядочить уровни по среднему значению целевой переменной (Breiman et al., 1984; Fisher, 1958; Hastie, Tibshirani and Friedman, 2009, раздел 9.2.4). В игрушечном примере с четырьмя уровнями по 10 точек и 2, 8, 3 и 7 положительными точками 7 разбиений по подмножествам сводятся к 3 упорядоченным: в порядке A, C, D, B второе упорядоченное разбиение, $\{A, C\}$ против $\{B, D\}$, имеет наименьший взвешенный индекс Джини, $0.375$, такой же, как лучшее из всех 7. Две оговорки. При многих классах такого короткого пути нет. А признак с большим числом уровней предлагает много способов разбиения и поэтому может подогнаться под шум. Упорядочивание уровней по целевой переменной обучающих данных — не утечка: это часть поиска разбиения, как и выбор порога, и оно находит то же разбиение, что и перебор всех подмножеств. Опасность здесь — переобучение, и его контролируют обрезка и валидация. Утечка, о которой предупреждает заметка о данных, требует метки, которую обучение видеть не должно: метки отложенной точки или собственной метки точки внутри признака, как когда каждый уровень заменяют средним значением целевой переменной по всем точкам, включая саму точку. От этого защищают упорядоченные целевые статистики (ordered target statistics) CatBoost из заметки о градиентном бустинге. One-hot кодирование требует многих разбиений, чтобы выделить группу уровней. Разбиение по подмножеству уровней — свойство метода, а не каждой библиотеки: DecisionTreeClassifier из scikit-learn, используемый в разделе «Код», принимает только числа, поэтому категории нужно сначала закодировать, а HistGradientBoostingClassifier из scikit-learn (с аргументом categorical_features), LightGBM и CatBoost разбивают по категориям напрямую.

Пропуски. Деревья предлагают несколько способов сохранить строки с пропущенными значениями (Hastie, Tibshirani and Friedman, 2009, раздел 9.2.4):

• считать «пропуск» отдельным уровнем (для категориальных признаков), чтобы дерево могло выучить, что сам факт пропуска предсказывает целевую переменную;
• суррогатные разбиения (surrogate splits, CART): в каждом узле ранжировать разбиения по другим признакам по тому, насколько хорошо они воспроизводят выбранное разбиение, и отправлять точку с пропущенным признаком по лучшему из доступных ей суррогатов;
• выученное направление (learned direction): вычислить прирост каждого порога дважды — со всеми пропусками, отправленными влево, и со всеми, отправленными вправо, — и оставить лучший вариант; предсказание следует сохранённому направлению. Так делает XGBoost (Chen and Guestrin, 2016, раздел 3.4), а также DecisionTreeClassifier из scikit-learn.
• C4.5 отправляет точку с пропуском по обеим ветвям с весами, пропорциональными размерам ветвей, и усредняет предсказания.

На описанном выше разбиении данных о раке груди скрытие 30% значений корневого признака и в обучающей, и в тестовой выборке оставляет работоспособное дерево с долей правильных ответов на тесте $0.947$ против $0.918$ на полных данных; разница лежит в пределах изменчивости одного дерева от выборки к выборке, которой посвящён следующий раздел.

Деревья неустойчивы и переобучаются#

Жадное построение делает дерево оценкой с большой дисперсией. Небольшое изменение данных может изменить разбиение корня, и каждое разбиение ниже наследует это изменение (Hastie, Tibshirani and Friedman, 2009, раздел 9.2.4). Деревья, выращенные на двух случайных половинах одной и той же обучающей выборки о раке груди, разбивают корень по разным признакам (worst perimeter и mean concave points) и расходятся на 10.5% тестовых точек. Глубина управляет этим эффектом:

Рисунок

Деревья растущей глубины на двух выборках

Полностью выращенное дерево имеет нулевую ошибку на обучении и худшую тестовую ошибку из трёх, а расхождение между двумя деревьями, выращенными на выборках из одного распределения, почти вчетверо больше, чем у пня (stump). Глубокое дерево имеет малое смещение, поскольку может следовать любой функции, и большой разброс, поскольку следует шуму своей выборки. Следующая заметка уточняет, что значит «малое смещение, большой разброс», а две заметки после неё обращают неустойчивость в преимущество.

Что изменилось#

	Линейный классификатор	Решающее дерево
Модель	$\operatorname{sign}\langle w, x \rangle$	$\sum_m c_m [x \in A_m]$, прямоугольные области из разбиений, параллельных осям
Взаимодействия	нужно добавлять вручную	строятся ветвлением
Признаки	числовые, масштабированные	любая монотонная шкала; категории и пропуски в самом правиле разбиения (поддержка зависит от библиотеки)
Обучение	выпуклая функция потерь, градиентные методы	жадный перебор разбиений, $O(D \, d \, n \log n)$
Управление сложностью	штраф на норму	глубина, размер листа, стоимостно-сложностная обрезка
Типичный провал	смещение: граница слишком проста	разброс: неустойчиво, переобучается

Ограничения#

• Большая дисперсия. Отдельное дерево сильно меняется вместе с обучающей выборкой, а вместе с ним меняется и его интерпретация.
• Кусочно-постоянная функция. Предсказания не гладкие, а вне диапазона обучающих данных постоянны: дерево не может экстраполировать тренд.
• Разбиения параллельны осям. Диагональной границе или аддитивному эффекту, распределённому по многим признакам, нужно много разбиений; в ESL отмечено, что у дерева нет специального способа представлять аддитивную структуру (Hastie, Tibshirani and Friedman, 2009, раздел 9.2.4).
• Жадность. Найденное дерево — не лучшее дерево своего размера, и закономерности, которые окупаются только после двух разбиений, как XOR, могут быть пропущены.

Что нужно запомнить#

• Дерево разбивает входы на прямоугольные области вопросами $x_j \le t$ и предсказывает константу в каждой области; пути — конъюнкции, поэтому деревья моделируют взаимодействия.
• Неоднородность — потери лучшей константы в узле: дисперсия для квадратичной ошибки, энтропия для логистической функции потерь, Джини $\sum_k p_k(1 - p_k)$ для меры Брайера, $1 - \max_k p_k$ для функции потерь 0–1.
• Джини — ожидаемая ошибка случайной разметки точек узла по долям классов; для двух классов это удвоенная дисперсия метки 0/1.
• Разбиения выбираются жадно по приросту; один уровень стоит $O(d \, n \log n)$; поиск оптимального дерева NP-труден.
• Стоимостно-сложностная обрезка минимизирует $R(T) + \alpha |T|$; обрезка по самому слабому звену даёт вложенную последовательность; $\alpha$ выбирается кросс-валидацией.
• Категориальные уровни, упорядоченные по доле класса или среднему значению целевой переменной, дают оптимальное бинарное разбиение для двух классов и для регрессии; пропуски уходят в отдельный уровень, в суррогатное разбиение или по выученному направлению.
• Глубокие деревья: малое смещение, большой разброс; небольшие изменения данных меняют дерево.

Код#

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

import numpy as np
from itertools import combinations
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.tree import DecisionTreeClassifier

# неоднородности узла по численностям классов и взвешенная неоднородность разбиения
def error(c): return 1 - max(c) / sum(c)
def gini(c): return 1 - sum((k / sum(c)) ** 2 for k in c)
def entropy(c): return -sum(k / sum(c) * np.log2(k / sum(c)) for k in c if k)
def after(children, H): return sum(sum(c) * H(c) for c in children) / sum(sum(c) for c in children)
A, B = [(7, 3), (1, 5)], [(8, 4), (0, 4)]             # два разбиения узла с 8 + 8 точками
for H in (error, gini, entropy):
    print(H.__name__, round(H((8, 8)), 3), round(after(A, H), 3), round(after(B, H), 3))
# error 0.5 0.25 0.25 | gini 0.5 0.367 0.333 | entropy 1.0 0.795 0.689

# Джини как ошибка случайной разметки: каждая метка выбирается по долям классов узла
rng = np.random.default_rng(0)
labels = np.repeat([0, 1, 2], [6, 3, 1])
draws = rng.choice(labels, size=(100_000, labels.size))
print(round(gini((6, 3, 1)), 3), round(float((draws != labels).mean()), 3))   # 0.54 0.539

# категориальный признак с 4 уровнями: все 2^(q-1) - 1 = 7 разбиений по подмножествам против 3 разбиений в порядке среднего значения целевой переменной
pos = {'A': 2, 'B': 8, 'C': 3, 'D': 7}                 # положительные точки из 10 на уровень
def subset_gini(left):
    l = sum(pos[c] for c in left); r = sum(pos.values()) - l
    return after([(l, 10 * len(left) - l), (r, 10 * (4 - len(left)) - r)], gini)
splits = [s for k in (1, 2) for s in combinations('ABCD', k) if k == 1 or 'A' in s]
best = min(splits, key=subset_gini)
order = sorted(pos, key=pos.get)
print(len(splits), best, round(subset_gini(best), 3), order, [round(subset_gini(order[:k]), 3) for k in (1, 2, 3)])
# 7 ('A', 'C') 0.375 ['A', 'C', 'D', 'B'] [0.44, 0.375, 0.44]

# рак груди: полностью выращенное дерево, затем стоимостно-сложностная обрезка с alpha, выбранным 5-кратной кросс-валидацией
X, y = load_breast_cancer(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
full = DecisionTreeClassifier(random_state=0).fit(Xtr, ytr)
alphas = full.cost_complexity_pruning_path(Xtr, ytr).ccp_alphas
cv = GridSearchCV(DecisionTreeClassifier(random_state=0), {'ccp_alpha': alphas}, cv=5).fit(Xtr, ytr)
for t in (full, cv.best_estimator_):
    print(t.get_n_leaves(), t.get_depth(), round(t.score(Xtr, ytr), 3), round(t.score(Xte, yte), 3))
print(round(cv.best_params_['ccp_alpha'], 4))
# 16 6 1.0 0.906 | 6 4 0.977 0.918 | 0.0088

# неустойчивость: деревья, выращенные на двух случайных половинах обучающей выборки
names = load_breast_cancer().feature_names
half = rng.permutation(len(ytr)); h1, h2 = half[: len(half) // 2], half[len(half) // 2:]
t1 = DecisionTreeClassifier(random_state=0).fit(Xtr[h1], ytr[h1])
t2 = DecisionTreeClassifier(random_state=0).fit(Xtr[h2], ytr[h2])
print(names[t1.tree_.feature[0]], '|', names[t2.tree_.feature[0]], round(float((t1.predict(Xte) != t2.predict(Xte)).mean()), 3))
# worst perimeter | mean concave points 0.105

# пропуски: скрываем 30% значений корневого признака; каждое разбиение выучивает, в какого потомка идут пропуски
Xm = Xtr.copy(); Xm[rng.random(len(Xm)) < 0.3, full.tree_.feature[0]] = np.nan
Xtm = Xte.copy(); Xtm[rng.random(len(Xtm)) < 0.3, full.tree_.feature[0]] = np.nan
print(round(DecisionTreeClassifier(random_state=0, ccp_alpha=cv.best_params_['ccp_alpha']).fit(Xm, ytr).score(Xtm, yte), 3))   # 0.947

Дальше#

Глубокое дерево идеально подгоняется под обучающую выборку, и рисунок выше показал, чего это стоит: тестовая ошибка хуже, чем у неглубокого дерева, и два дерева из одного распределения, которые расходятся почти везде. «Гибкие модели переобучаются» — верно, но расплывчато. Следующая заметка раскладывает ожидаемую тестовую ошибку любого метода обучения на три части — шум, квадрат смещения и разброс — и с помощью этого разложения объясняет выбор глубины для деревьев, $k$ для ближайших соседей и $\lambda$ для гребневой регрессии, а также почему усреднение многих деревьев должно помогать.

Литература#

• L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone. Classification and Regression Trees. Wadsworth, 1984 (CRC Press reprint). Индекс Джини, суррогатные разбиения, стоимостно-сложностная обрезка, упорядочивание категориальных уровней для двух классов.
• J. R. Quinlan. Induction of Decision Trees. Machine Learning, 1(1), 1986. ID3 и информационный выигрыш.
• L. Hyafil, R. L. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1), 1976.
• W. D. Fisher. On Grouping for Maximum Homogeneity. Journal of the American Statistical Association, 53(284), 1958. Результат об упорядочивании для количественной целевой переменной.
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Раздел 9.2 (регрессионные и классификационные деревья, стоимостно-сложностная обрезка, меры неоднородности и интерпретации индекса Джини, категориальные предикторы, пропуски, неустойчивость).
• T. Chen, C. Guestrin. XGBoost: A Scalable Tree Boosting System. KDD, 2016. Раздел 3.4 (поиск разбиений с учётом разреженности и направлением по умолчанию).
• scikit-learn developers. Decision Trees, руководство пользователя scikit-learn: поддержка пропусков и минимальная стоимостно-сложностная обрезка.
• E. Sokolov et al. Машинное обучение (HSE). Конспект, лекция 9: решающие деревья; семинар 9: решающие деревья.