1.10. Деревья решений (Decision Trees)

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

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

../_images/sphx_glr_plot_tree_regression_001.png

Некоторые преимущества деревьев решений:

  • Простота понимания и интерпретации. Деревья можно визуализировать.

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

  • Стоимость использования дерева (т. е. предсказания данных) логарифмически зависит от количества точек данных, используемых для обучения дерева.

  • Способно работать как с числовыми, так и с категориальными данными. Однако реализация scikit-learn пока не поддерживает категориальные переменные. Другие методы обычно специализируются на анализе наборов данных, содержащих только один тип переменных. Дополнительную информацию см. в алгоритмы.

  • Умеет решать задачи с несколькими выходами.

  • Использует модель “белого ящика”. Если данная ситуация наблюдаема в модели, то объяснение состояния легко объясняется с помощью булевой логики. Напротив, в модели “черного ящика” (например, в искусственной нейронной сети) результаты может быть сложнее интерпретировать.

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

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

К недостаткам деревьев решений относятся:

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

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

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

  • Известно, что проблема обучения оптимального дерева решений является NP-полной задачей в нескольких аспектах оптимальности и даже для простых концепций. Следовательно, практические алгоритмы обучения дерева решений основаны на эвристических алгоритмах, таких как жадный алгоритм, в котором локально оптимальные решения принимаются в каждом узле. Такие алгоритмы не могут гарантировать возвращение глобально оптимального дерева решений. Это можно смягчить, обучив несколько деревьев в ансамблевом обучающем устройстве, где признаки и образцы выбираются случайным образом с заменой.

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

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

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

DecisionTreeClassifier - это класс, способный выполнять многоклассовую классификацию на наборе данных.

Как и другие классификаторы, DecisionTreeClassifier принимает на вход два массива: массив X, разреженный или плотный, формы (n_samples, n_features), содержащий обучающие выборки, и массив Y из целочисленных значений формы (n_samples,), содержащий метки классов для обучающих выборок:

>>> from sklearn import tree
>>> X = [[0, 0], [1, 1]]
>>> Y = [0, 1]
>>> clf = tree.DecisionTreeClassifier()
>>> clf = clf.fit(X, Y)

После обучения модель может быть использована для предсказания класса образцов:

>>> clf.predict([[2., 2.]])
array([1])

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

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

>>> clf.predict_proba([[2., 2.]])
array([[0., 1.]])

DecisionTreeClassifier способен как к бинарной (где метками являются [-1, 1]) классификации, так и к мультиклассовой (где метками являются [0, …, K-1]) классификации.

Используя набор данных Iris, мы можем построить дерево следующим образом:

>>> from sklearn.datasets import load_iris
>>> from sklearn import tree
>>> iris = load_iris()
>>> X, y = iris.data, iris.target
>>> clf = tree.DecisionTreeClassifier()
>>> clf = clf.fit(X, y)

После обучения дерево можно построить с помощью функции plot_tree:

>>> tree.plot_tree(clf)
[...]
../_images/sphx_glr_plot_iris_dtc_002.png

Альтернативные способы экспорта деревьев Click for more details

Мы также можем экспортировать дерево в формат Graphviz с помощью экспортера export_graphviz. Если вы используете менеджер пакетов conda, двоичные файлы graphviz и пакет python могут быть установлены с помощью conda install python-graphviz.

В качестве альтернативы двоичные файлы graphviz можно загрузить с домашней страницы проекта graphviz, а Python-обертку установить из pypi с помощью pip install graphviz.

Ниже приведен пример экспорта в graphviz вышеупомянутого дерева, обученного на всем наборе данных iris; результаты сохранены в выходном файле iris.pdf:

>>> import graphviz 
>>> dot_data = tree.export_graphviz(clf, out_file=None) 
>>> graph = graphviz.Source(dot_data) 
>>> graph.render("iris")

Экспортер export_graphviz также поддерживает различные эстетические опции, включая раскраску узлов по их классу (или значению для регрессии) и использование явных имен переменных и классов по желанию. Блокноты Jupyter также автоматически отображают эти графики в режиме inline:

>>> dot_data = tree.export_graphviz(clf, out_file=None, 
...                      feature_names=iris.feature_names,  
...                      class_names=iris.target_names,  
...                      filled=True, rounded=True,  
...                      special_characters=True)  
>>> graph = graphviz.Source(dot_data)  
>>> graph
../_images/iris.svg
../_images/sphx_glr_plot_iris_dtc_001.png

В качестве альтернативы дерево можно экспортировать в текстовый формат с помощью функции export_text. Этот метод не требует установки внешних библиотек и является более компактным:

>>> from sklearn.datasets import load_iris
>>> from sklearn.tree import DecisionTreeClassifier
>>> from sklearn.tree import export_text
>>> iris = load_iris()
>>> decision_tree = DecisionTreeClassifier(random_state=0, max_depth=2)
>>> decision_tree = decision_tree.fit(iris.data, iris.target)
>>> r = export_text(decision_tree, feature_names=iris['feature_names'])
>>> print(r)
|--- petal width (cm) <= 0.80
|   |--- class: 0
|--- petal width (cm) >  0.80
|   |--- petal width (cm) <= 1.75
|   |   |--- class: 1
|   |--- petal width (cm) >  1.75
|   |   |--- class: 2

1.10.2. Регрессия

../_images/sphx_glr_plot_tree_regression_001.png

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

Как и в случае с классификацией, метод обучения принимает в качестве аргументов массивы X и y, только в этом случае y будет иметь значения с плавающей точкой, а не целочисленные значения:

>>> from sklearn import tree
>>> X = [[0, 0], [2, 2]]
>>> y = [0.5, 2.5]
>>> clf = tree.DecisionTreeRegressor()
>>> clf = clf.fit(X, y)
>>> clf.predict([[1, 1]])
array([0.5])

1.10.3. Проблемы с несколькими выходами

Многовыводная задача - это задача контролируемого обучения с несколькими выходами, которые нужно предсказать, то есть когда Y - это 2d массив формы (n_samples, n_outputs).

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

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

  • Хранить в листьях не 1, а n выходных значений;

  • Использовать критерии разбиения, которые вычисляют среднее сокращение по всем n выходам.

Этот модуль обеспечивает поддержку проблем с несколькими выходами, реализуя эту стратегию как в DecisionTreeClassifier, так и в DecisionTreeRegressor. Если дерево решений настраивается на выходной массив Y формы (n_samples, n_outputs), то результирующая оценка будет:

  • Выводить значения n_output на predict;

  • Выводить список из n_output массивов вероятностей классов при predict_proba.

Использование многовыводных деревьев для регрессии продемонстрировано в Multi-output Decision Tree Regression. В этом примере на входе X - одно вещественное значение, а на выходе Y - синус и косинус X.

../_images/sphx_glr_plot_tree_regression_multioutput_001.png

Использование многовыводных деревьев для классификации продемонстрировано в Face completion with a multi-output estimators. В этом примере входами X являются пиксели верхней половины лиц, а выходами Y - пиксели нижней половины этих лиц.

../_images/sphx_glr_plot_multioutput_face_completion_001.png

Ссылки Click for more details

1.10.4. Сложность

В общем случае, затраты времени на построение сбалансированного бинарного дерева составляют \(O(n_{samples}n_{features}\log(n_{samples}))\), а время запроса \(O(\log(n_{samples}))\). Хотя алгоритм построения деревьев пытается генерировать сбалансированные деревья, они не всегда будут сбалансированными. Если предположить, что поддеревья остаются примерно сбалансированными, то затраты в каждом узле состоят из перебора \(O(n_{features})\), чтобы найти признак, который предлагает наибольшее уменьшение критерия примеси, например, log loss (что эквивалентно информационному выигрышу). Это требует затрат \(O(n_{features}n_{samples}\log(n_{samples}))\) в каждом узле, что приводит к общей стоимости по всем деревьям (путем суммирования стоимости в каждом узле) \(O(n_{features}n_{samples}^{2}\log(n_{samples}))\).

1.10.5. Советы по практическому использованию

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

  • Рассмотрите возможность предварительного снижения размерности (PCA, ICA, или Отбор признаков (Feature selection)), чтобы дать дереву больше шансов найти дискриминативные признаки.

  • Understanding the decision tree structure поможет получить больше информации о том, как дерево решений делает предсказания, что важно для понимания важных особенностей в данных.

  • Визуализируйте дерево в процессе обучения с помощью функции export. Используйте max_depth=3 в качестве начальной глубины дерева, чтобы почувствовать, как дерево подходит к вашим данным, а затем увеличивайте глубину.

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

  • Используйте min_samples_split или min_samples_leaf для обеспечения того, чтобы множество образцов использовалось для принятия каждого решения в дереве, контролируя, какие образцы будут рассматриваться. Очень маленькое число обычно означает, что дерево будет перестраиваться, в то время как большое число не позволит дереву изучить данные. Попробуйте использовать min_samples_leaf=5 в качестве начального значения. Если размер выборки сильно варьируется, можно использовать плавающее число в качестве процента в этих двух параметрах. В то время как min_samples_split может создавать произвольно маленькие листья, min_samples_leaf гарантирует, что каждый лист имеет минимальный размер, что позволяет избежать узлов листа с низкой вариацией и переобучения в задачах регрессии. Для классификации с небольшим количеством классов min_samples_leaf=1 часто является лучшим выбором.

    Обратите внимание, что min_samples_split учитывает выборки напрямую и не зависит от sample_weight, если он указан (например, узел с m взвешенными выборками по-прежнему считается имеющим ровно m выборок). Рассмотрите вариант min_weight_fraction_leaf или min_impurity_decrease, если требуется учет весов образцов при расщеплении.

  • Сбалансируйте набор данных перед обучением, чтобы предотвратить смещение дерева в сторону доминирующих классов. Балансировка классов может быть выполнена путем выборки равного количества образцов из каждого класса, или, что более предпочтительно, путем нормализации суммы весов образцов (вес_образца) для каждого класса к одному и тому же значению. Также обратите внимание, что критерии предварительной обрезки, основанные на весах, такие как min_weight_fraction_leaf, будут менее предвзяты к доминирующим классам, чем критерии, не знающие весов образцов, такие как min_samples_leaf.

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

  • Все деревья решений используют массивы np.float32 внутри себя. Если обучающие данные не в этом формате, будет сделана копия набора данных.

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

1.10.6. Древовидные алгоритмы: ID3, C4.5, C5.0 и CART

Что представляют собой различные алгоритмы деревьев решений и чем они отличаются друг от друга? Какой из них реализован в scikit-learn?

Различные алгоритмы деревьев решений Click for more details

ID3 (Iterative Dichotomiser 3) был разработан в 1986 году Россом Куинланом. Алгоритм создает многоходовое дерево, находя для каждого узла (т. е. жадным образом) категориальный признак, который даст наибольший прирост информации для категориальных целей. Деревья растут до максимального размера, а затем обычно применяется шаг обрезки, чтобы улучшить способность дерева обобщаться на невидимые данные.

C4.5 является преемником ID3 и снимает ограничение на то, что признаки должны быть категориальными, динамически определяя дискретный атрибут (основанный на числовых переменных), который разбивает непрерывное значение признака на дискретный набор интервалов. C4.5 преобразует обученные деревья (т. е. результаты работы алгоритма ID3) в наборы правил “если - то”. Затем оценивается точность каждого правила, чтобы определить порядок их применения. Обрезка производится путем удаления предварительного условия правила, если без него точность правила повышается.

C5.0 - это последняя версия Куинлана, выпущенная под проприетарной лицензией. Она использует меньше памяти и строит меньшие наборы правил, чем C4.5, при этом являясь более точной.

CART (Classification and Regression Trees) очень похож на C4.5, но отличается от него тем, что поддерживает числовые целевые переменные (регрессия) и не вычисляет наборы правил. CART строит бинарные деревья, используя признак и порог, которые дают наибольший прирост информации в каждом узле.

scikit-learn использует оптимизированную версию алгоритма CART; однако реализация scikit-learn пока не поддерживает категориальные переменные.

1.10.7. Математическая формулировка

Учитывая обучающие векторы \(x_i \in R^n\), i=1,…, l и вектор меток \(y \in R^l\), дерево решений рекурсивно разбивает пространство признаков таким образом, что образцы с одинаковыми метками или одинаковыми целевыми значениями группируются вместе.

Пусть данные в узле \(m\) представлены \(Q_m\) с \(n_m\) выборками. Для каждого кандидатного разбиения \(\theta = (j, t_m)\), состоящего из признака \(j\) и порога \(t_m\), разделите данные на подмножества \(Q_m^{left}(\theta)\) и \(Q_m^{right}(\theta)\).

\[ \begin{align}\begin{aligned}Q_m^{left}(\theta) = \{(x, y) | x_j \leq t_m\}\\Q_m^{right}(\theta) = Q_m \setminus Q_m^{left}(\theta)\end{aligned}\end{align} \]

Затем вычисляется качество кандидата на разбиение узла \(m\) с помощью функции примеси или функции потерь \(H()\), выбор которой зависит от решаемой задачи (классификация или регрессия)

\[G(Q_m, \theta) = \frac{n_m^{left}}{n_m} H(Q_m^{left}(\theta)) + \frac{n_m^{right}}{n_m} H(Q_m^{right}(\theta))\]

Выбор параметров, минимизирующих примесь

\[\theta^* = \operatorname{argmin}_\theta G(Q_m, \theta)\]

Перебор подмножеств \(Q_m^{left}(\theta^*)\) и \(Q_m^{right}(\theta^*)\) до достижения максимально допустимой глубины, \(n_m < \min_{samples}\) или \(n_m = 1\).

1.10.7.1. Критерии классификации

Если целью является результат классификации, принимающий значения 0,1,…,K-1, для узла \(m\), пусть

\[p_{mk} = \frac{1}{n_m} \sum_{y \in Q_m} I(y = k)\]

доля наблюдений класса k в узле \(m\). Если \(m\) является терминальным узлом, то predict_proba для этой области устанавливается равным \(p_{mk}\). Общими мерами примесей являются следующие.

Gini (Джини):

\[H(Q_m) = \sum_k p_{mk} (1 - p_{mk})\]

Log Loss или энтропия:

\[H(Q_m) = - \sum_k p_{mk} \log(p_{mk})\]

Энтропия Шеннона. Click for more details

Критерий энтропии вычисляет энтропию Шеннона возможных классов. В качестве вероятности он принимает частоты классов обучающих точек данных, достигших данного листа \(m\). Использование энтропии Шеннона в качестве критерия разбиения узлов дерева эквивалентно минимизации логарифмической потери (также известной как кросс-энтропия и мультиномиальная дисперсия) между истинными метками \(y_i\) и вероятностными предсказаниями \(T_k(x_i)\) модели дерева \(T\) для класса \(k\).

Чтобы увидеть это, сначала вспомним, что log loss древовидной модели \(T\), вычисленной на наборе данных \(D\), определяется следующим образом:

\[\mathrm{LL}(D, T) = -\frac{1}{n} \sum_{(x_i, y_i) \in D} \sum_k I(y_i = k) \log(T_k(x_i))\]

где \(D\) - обучающий набор данных из \(n\) пар \((x_i, y_i)\).

В дереве классификации предсказанные вероятности классов в узлах листьев постоянны, то есть: для всех \((x_i, y_i) \in Q_m\), имеет место: \(T_k(x_i) = p_{mk}\) для каждого класса \(k\).

Это свойство позволяет переписать \(\mathrm{LL}(D, T)\) как сумму энтропий Шеннона, вычисленных для каждого листа \(T\), взвешенных по количеству обучающих точек данных, попавших в каждый лист:

\[\mathrm{LL}(D, T) = \sum_{m \in T} \frac{n_m}{n} H(Q_m)\]

1.10.7.2. Критерии регрессии

Если цель - непрерывная величина, то для узла \(m\) общими критериями для минимизации при определении мест для будущих разбиений являются средняя квадратичная ошибка (MSE или ошибка L2), дисперсия Пуассона, а также средняя абсолютная ошибка (MAE или ошибка L1). MSE и дисперсия Пуассона устанавливают предсказанное значение конечных узлов на выученное среднее значение \(\bar{y}_m\) узла, тогда как MAE устанавливает предсказанное значение конечных узлов на медиану \(median(y)_m\).

Средняя квадратичная ошибка:

\[ \begin{align}\begin{aligned}\bar{y}_m = \frac{1}{n_m} \sum_{y \in Q_m} y\\H(Q_m) = \frac{1}{n_m} \sum_{y \in Q_m} (y - \bar{y}_m)^2\end{aligned}\end{align} \]

Полупуассоновская дисперсия:

\[H(Q_m) = \frac{1}{n_m} \sum_{y \in Q_m} (y \log\frac{y}{\bar{y}_m} - y + \bar{y}_m)\]

Установка criterion="poisson" может быть хорошим выбором, если ваша цель - количество или частота (количество на некоторую единицу). В любом случае, \(y >= 0\) является необходимым условием для использования этого критерия. Обратите внимание, что он сходится гораздо медленнее, чем критерий MSE.

Средняя абсолютная ошибка:

\[ \begin{align}\begin{aligned}median(y)_m = \underset{y \in Q_m}{\mathrm{median}}(y)\\H(Q_m) = \frac{1}{n_m} \sum_{y \in Q_m} |y - median(y)_m|\end{aligned}\end{align} \]

Обратите внимание, что он сходится гораздо медленнее, чем критерий MSE.

1.10.8. Поддержка пропущенных значений

В DecisionTreeClassifier и DecisionTreeRegressor встроена поддержка отсутствующих значений, когда splitter='best' и критерием является 'gini', 'entropy' или 'log_loss' для классификации или 'squared_error', 'friedman_mse' или 'poisson' для регрессии.

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

Решения принимаются следующим образом:

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

    >>> from sklearn.tree import DecisionTreeClassifier
>>> import numpy as np

>>> X = np.array([0, 1, 6, np.nan]).reshape(-1, 1)
>>> y = [0, 0, 1, 1]

>>> tree = DecisionTreeClassifier(random_state=0).fit(X, y)
>>> tree.predict(X)
array([0, 0, 1, 1])

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

    >>> from sklearn.tree import DecisionTreeClassifier
>>> import numpy as np

>>> X = np.array([np.nan, -1, np.nan, 1]).reshape(-1, 1)
>>> y = [0, 0, 1, 1]

>>> tree = DecisionTreeClassifier(random_state=0).fit(X, y)

>>> X_test = np.array([np.nan]).reshape(-1, 1)
>>> tree.predict(X_test)
array([1])

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

    >>> from sklearn.tree import DecisionTreeClassifier
>>> import numpy as np

>>> X = np.array([0, 1, 2, 3]).reshape(-1, 1)
>>> y = [0, 1, 1, 1]

>>> tree = DecisionTreeClassifier(random_state=0).fit(X, y)

>>> X_test = np.array([np.nan]).reshape(-1, 1)
>>> tree.predict(X_test)
array([1])

1.10.9. Обрезка с минимальной стоимостью и сложностью (Minimal cost-complexity pruning)

Minimal cost-complexity pruning - это алгоритм, используемый для обрезки дерева, чтобы избежать переобучение, описанный в главе 3 [BRE]. Этот алгоритм параметризуется параметром \(\alpha\ge0\), известным как параметр сложности. Параметр сложности используется для определения меры стоимости-сложности, \(R_\alpha(T)\) данного дерева \(T\):

\[R_\alpha(T) = R(T) + \alpha|\widetilde{T}|\]

где \(|\widetilde{T}|\) - количество терминальных узлов в \(T\), а \(R(T)\) традиционно определяется как общий коэффициент неправильной классификации терминальных узлов. В качестве альтернативы scikit-learn использует взвешенную по выборке общую примесь терминальных узлов для \(R(T)\). Как показано выше, примесь узла зависит от критерия. Обрезка с минимальной сложностью затрат находит поддерево \(T\), которое минимизирует \(R_\alpha(T)\).

Мера сложности затрат для одного узла - \(R_\alpha(t)=R(t)+\alpha\). Ветвь, \(T_t\), определяется как дерево, корнем которого является узел \(t\). В общем случае, примесь узла больше суммы примесей его терминальных узлов, \(R(T_t)<R(t)\). Однако мера сложности узла, \(t\), и его ветви, \(T_t\), может быть одинаковой в зависимости от \(\alpha\). Мы определяем эффективную \(\alpha\) узла как значение, при котором они равны, \(R_\alpha(T_t)=R_\alpha(t)\) или \(\alpha_{eff}(t)=\frac{R(t)-R(T_t)}{|T|-1}\). Нетерминальный узел с наименьшим значением \(\alpha_{eff}\) является самым слабым звеном и будет обрезан. Этот процесс прекращается, когда минимальное значение \(\alpha_{eff}\) обрезанного дерева больше параметра ccp_alpha.

Ссылки Click for more details

[BRE]

L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.