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]) классификацию.

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

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

Примеры

• Построение поверхности решений деревьев решений, обученных на наборе данных Ирис
• Понимание структуры дерева решений

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 значений выходов в листьях, вместо 1;
• Использовать критерии разделения, которые вычисляют среднее уменьшение по всем n выходам.

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

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

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

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

Примеры

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

Ссылки

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

1.10.4. Сложность

В общем случае, стоимость времени выполнения для построения сбалансированного двоичного дерева составляет \(O(n_{samples}n_{features}\log(n_{samples}))\), а время запроса — \(O(\log(n_{samples}))\). Хотя алгоритм построения дерева стремится создать сбалансированные деревья, они не всегда будут сбалансированными. Предполагая, что поддеревья остаются приблизительно сбалансированными, стоимость в каждом узле состоит из поиска среди \(O(n_{features})\), чтобы найти признак, который обеспечивает наибольшее уменьшение критерия нечистоты, например, логарифмической потери (что эквивалентно приросту информации). Это имеет стоимость \(O(n_{features}n_{samples}\log(n_{samples}))\) в каждом узле, что приводит к общей стоимости по всему дереву (суммированием стоимости в каждом узле) \(O(n_{features}n_{samples}^{2}\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()\), выбор которой зависит от решаемой задачи (классификация или регрессия).

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

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

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

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

Поддерживаемые критерии при наличии пропущенных значений — 'gini', 'entropy или 'log_loss', для классификации или 'squared_error', 'friedman_mse' или 'poisson' для регрессии.

Сначала мы опишем, как 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).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)\) традиционно определяется как общая доля неправильных классификаций терминальных узлов. В качестве альтернативы, 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 параметр.

Примеры

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

Ссылки

• https://ru.wikipedia.org/wiki/Обучение_с_помощью_деревьев_решений
• https://ru.wikipedia.org/wiki/Прогностический_анализ
• Дж. Р. Квинлан. C4. 5: программы для машинного обучения. Morgan Kaufmann, 1993.
• Т. Хасти, Р. Тибширани и Дж. Фридман. Элементы статистического обучения, Springer, 2009.