Особенности прогнозов решающего дерева

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

Прогнозы для классификации

Рассмотрим задачу бинарной классификации на красный и синий класс в пространстве двух признаков.

Ниже приведены прогнозы для решающего дерева глубины 1,2,3,10:

Как видим, дерево получается слишком простым при глубине 1,2, а при глубине 10 уже переобучается на отдельные наблюдения.

Стороны прямоугольников перпендикулярны осям координат, поскольку сами прямоугольники получаются пересечением условий вида [признак $\le$ порог] и [признак>порога]. Прогнозная функция $\hat{y}(\mathbf{x})$ имеет ступенчатый кусочно-постоянный вид, показанной на графике ниже в центре [1]:

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

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

Прогнозы для регрессии

Пусть целевая регрессионная зависимость имеет вид

$$y=\sin(x)+\varepsilon$$

где $x$ - одномерный признак, а $\varepsilon$ - небольшой Гауссов шум. Построим решающее дерево глубины 1,2,3,4,5,10. Целевую зависимость $\sin(x)$ обозначим пунктирной линией, обучающие объекты - черными точками, а прогнозную функцию дерева - синей кривой. Тогда получим следующую визуализацию прогнозов дерева разной глубины:

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

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

Композиция алгоритмов

Решающему дереву сложно моделировать линейные зависимости между признаками и откликом, но это легко делать линейным моделям. Зато решающие деревья легко настраиваются на зависимости, в которых признаки оказывают совместное влияние на отклик (например, способны обработать совместный случай, когда число просрочек по кредиту>0 и объем задолженности $<$ 10.000 в задаче кредитного скоринга). Линейные же модели учитывают вклад каждого признака независимо от значений остальных признаков. За счёт этого модели хорошо компенсируют ошибки друг друга, если действуют в композиции друг с другом. Построение прогнозов набором моделей будет изучено в отдельном разделе учебника.

Вариант комбинации линейных моделей и решающих деревьев

Также для комбинации линейных моделей и решающих деревьев в своё время был предложен алгоритм RuleFit [2], который:

1. настраивает решающие деревья;

2. по ним извлекает набор бинарных признаков соответствующих индикаторам попадания объекта в каждый из узлов образовавшихся деревьев;

3. строит линейную модель по исходным и извлечённым бинарным признакам.

Пример запуска в Python

Решающее дерево CART для классификации:

from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
from sklearn.metrics import brier_score_loss

X_train, X_test, Y_train, Y_test = get_demo_classification_data()  

# инициализация дерева (criterion - функция неопределённости):
model = DecisionTreeClassifier(criterion='gini')  
model.fit(X_train, Y_train)    # обучение модели   
Y_hat = model.predict(X_test)  # построение прогнозов
print(f'Точность прогнозов: {100*accuracy_score(Y_test, Y_hat):.1f}%')

P_hat = model.predict_proba(X_test)  # можно предсказывать вероятности классов
loss = brier_score_loss(Y_test, P_hat[:,1])  # мера Бриера на вер-ти положительного класса
print(f'Мера Бриера ошибки прогноза вероятностей: {loss:.2f}')

Больше информации. Полный код.

Решающее дерево CART для регрессии:

from sklearn.tree import DecisionTreeRegressor
from sklearn.metrics import mean_absolute_error

X_train, X_test, Y_train, Y_test = get_demo_regression_data()  

# инициализация дерева (criterion - функция неопределённости):
model = DecisionTreeRegressor(criterion='absolute_error')  
model.fit(X_train, Y_train)    # обучение модели   
Y_hat = model.predict(X_test)  # построение прогнозов
print(f'Средний модуль ошибки (MAE): \
        {mean_absolute_error(Y_test, Y_hat):.2f}')  

Больше информации. Полный код.

Литература

1. Wikipedia: decision tree learning.
2. Friedman J. H., Popescu B. E. Predictive learning via rule ensembles //The Annals of Applied Statistics. – 2008. – Т. 2. – №. 3. – С. 916-954.