1.10. Деревья решений

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)
[...]

Другие способы экспорта деревьев

Можно также экспортировать дерево в формате 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 эти графики также отображаются автоматически:

>>> 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

Кроме того, дерево можно экспортировать в текстовом формате с помощью функции 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

Примеры

• Визуализация разделяющей поверхности деревьев решений, обученных на наборе данных iris
• Изучение структуры дерева решений

1.10.2. Регрессия

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

Как и в случае классификации, метод fit принимает в качестве аргументов массивы 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 является двумерным массивом формы (n_samples, n_outputs).

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

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

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

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

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

Использование деревьев с несколькими выходами для регрессии демонстрируется в примере Регрессия с помощью дерева решений. В этом примере вход X — это одно вещественное значение, а выходы Y — синус и косинус X.

Использование деревьев с несколькими выходами для классификации демонстрируется в примере Восстановление лица с помощью оценщиков с несколькими выходами. В этом примере входы X — это пиксели верхней половины лиц, а выходы Y — пиксели их нижней половины.

Примеры

• Восстановление лица с помощью оценщиков с несколькими выходами

Ссылки

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

1.10.4. Сложность

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

В общем случае стоимость обучения при построении сбалансированного бинарного дерева в каждом узле равна

Первое слагаемое — стоимость сортировки \(n_{samples}\), повторяемой для \(n_{features}\). Второе слагаемое — линейный перебор точек-кандидатов для разбиения с целью найти признак, обеспечивающий наибольшее уменьшение критерия нечистоты. Для стратегии жадного разделителя «best» последнее слагаемое имеет меньший порядок, поэтому обычно его не учитывают.

Независимо от стратегии разбиения, после суммирования стоимости по всем внутренним узлам общая сложность линейно зависит от \(n_{nodes}=n_{leaves}-1\), что в худшем случае имеет порядок \(\mathcal{O}(n_{samples})\), то есть когда дерево растёт до тех пор, пока каждый образец не окажется в отдельном листе.

Во многих реализациях, например в scikit-learn, используются эффективные приёмы кэширования для отслеживания общего порядка индексов в каждом узле, поэтому признаки не требуется сортировать заново в каждом узле; следовательно, временная сложность таких реализаций составляет всего \(\mathcal{O}(n_{features}n_{samples}\log(n_{samples}))\) [1].

Стоимость вывода не зависит от стратегии разбиения. Она зависит только от глубины дерева и составляет \(\mathcal{O}(\text{depth})\). В приблизительно сбалансированном бинарном дереве каждое разбиение делит данные пополам, а количество таких делений растёт с глубиной как степени двойки. Если этот процесс продолжается до тех пор, пока каждый образец не окажется в отдельном листе, полученная глубина будет иметь порядок \(\mathcal{O}(\log(n_{samples}))\).

Ссылки

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

• Деревья решений склонны к переобучению на данных с большим количеством признаков. Важно правильно подобрать соотношение количества образцов и признаков, поскольку дерево, обученное на малом количестве образцов в пространстве высокой размерности, с большой вероятностью переобучится.
• Рассмотрите возможность предварительного снижения размерности (PCA, ICA или отбор признаков), чтобы повысить вероятность того, что дерево найдёт дискриминативные признаки.
• Изучение структуры дерева решений поможет лучше понять, как дерево решений делает предсказания, что важно для понимания значимых признаков в данных.
• Визуализируйте дерево в процессе обучения с помощью функции 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.

• Перед обучением сбалансируйте набор данных, чтобы дерево не было смещено в сторону доминирующих классов. Балансировку классов можно выполнить, выбрав одинаковое количество образцов из каждого класса, а ещё лучше — нормализовав сумму весов образцов (sample_weight) для каждого класса до одного и того же значения. Также обратите внимание, что критерии предварительной обрезки, основанные на весах, например 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?

В 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)\)

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

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

Стратегия выбора разбиения в каждом узле задаётся параметром splitter:

• При использовании наилучшего разделителя (по умолчанию, splitter='best') \(\theta^*\) определяется с помощью жадного полного перебора всех доступных признаков и всех возможных пороговых значений \(t_m\) (то есть средних значений между отсортированными различными значениями признака); выбирается пара, точно минимизирующая \(G(Q_m, \theta)\).
• При использовании случайного разделителя (splitter='random') \(\theta^*\) определяется путём выбора одного случайного возможного порогового значения для каждого доступного признака. Это даёт стохастическое приближение жадного поиска и фактически сокращает время вычислений (см. Сложность).

После выбора оптимального разбиения \(\theta^*\) в узле \(m\) та же процедура разбиения рекурсивно применяется к каждому подмножеству \(Q_m^{left}(\theta^*)\) и \(Q_m^{right}(\theta^*)\), пока не будет достигнуто условие остановки, например:

• достигнута максимально допустимая глубина (max_depth);
• \(n_m\) меньше min_samples_split;
• уменьшение неоднородности при этом разбиении меньше min_impurity_decrease.

Другие условия остановки см. в строке документации соответствующего оценщика.

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

DecisionTreeClassifier, DecisionTreeRegressor имеют встроенную поддержку пропущенных значений с использованием splitter='best', при котором разбиения определяются жадным способом. ExtraTreeClassifier и ExtraTreeRegressor имеют встроенную поддержку пропущенных значений для splitter='random', при котором разбиения определяются случайным образом. Подробнее о том, чем разделитель отличается при работе с непропущенными значениями, см. в разделе о лесах.

Сначала опишем, как DecisionTreeClassifier и DecisionTreeRegressor обрабатывают пропущенные значения в данных.

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

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

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

  >>> 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, max_depth=1).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])
  

ExtraTreeClassifier и ExtraTreeRegressor обрабатывают пропущенные значения несколько иначе. При разбиении узла для разделения непропущенных значений выбирается случайное пороговое значение. Затем непропущенные значения направляются в левый или правый дочерний узел в зависимости от выбранного случайным образом порога, а пропущенные значения также случайным образом направляются в левый или правый дочерний узел. Это повторяется для каждого признака, рассматриваемого при каждом разбиении. Из всех вариантов выбирается наилучшее разбиение.

При предсказании пропущенные значения обрабатываются так же, как и в дереве решений:

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

1.10.9. Обрезка с минимальной стоимостью и сложностью

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

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

Примеры

• Постобрезка деревьев решений с помощью обрезки с учётом стоимости и сложности

Литература

• https://en.wikipedia.org/wiki/Decision_tree_learning
• https://en.wikipedia.org/wiki/Predictive_analytics
• J.R. Quinlan. C4. 5: программы машинного обучения. Morgan Kaufmann, 1993.
• T. Hastie, R. Tibshirani и J. Friedman. «Основы статистического обучения». Springer, 2009.