В этой статье вы получите общее представление о деревьях решений, строительном блоке современных алгоритмов машинного обучения, таких как XGBoost и LightGBM. Сначала мы подробно рассмотрим принцип работы, а затем реализуем его с помощью Scikit-Learn.

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

Поскольку алгоритм дерева решений является основой LightGBM и XGBoost, очень важно понимать его логику. Таким образом, в первой статье этой серии мы объясняем деревья решений, а в следующих статьях мы перейдем к более сложным алгоритмам.

Что такое дерево решений?

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

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

В деревьях решений оператор вверху называется корневым узлом, а операторы в середине — узлами решений/внутренними узлами или ветвями. Операторы внизу называются конечными узлами или листьями.

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

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

Пример дерева классификации

1- Выбор корневого узла
Возьмем пример с канала Youtube StatQuest with Josh Starmer. У нас есть набор данных с 3 функциями и целевой переменной Loves Cool As Ice. Цель состоит в том, чтобы предсказать, любит ли человек фильм Крутой как лед, используя эти 3 функции.

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

Давайте возьмем первую функцию Loves Popcorn в качестве корневого узла.

Чтобы рассчитать примесь Джини попкорна, нам нужно рассчитать Джини листьев по формуле:

Примесь Джини для листа = 1–(вероятность ответа «Да»)²–(вероятность ответа «Нет»)²

Для левого листа Джини = 1-(1/(1+3))²-(3/(1+3))²=0,375

Для правого листа Джини = 1-(2/(2+1))²-(1/(2+1))²=0,444

Затем мы берем средневзвешенное значение результатов, чтобы вычислить примесь Джини корневого узла, используя приведенную ниже формулу:

Общая примесь Джини = (количество наблюдений на левом листе / общее количество наблюдений) * Джини на левом листе + (количество наблюдений на правом листе / общее количество наблюдений) * Джини на правом листе

Примесь Джини для функции Loves Popcorn = (4/(4+3))*0,375 + (3/(4+3))*0,444 = 0,405

Теперь мы знаем, как вычислить метрику примеси Джини для категориальной переменной, поэтому мы можем легко вычислить ее и для переменной Loves Soda, что дает значение 0,214.

Итак, что насчет числовых переменных? Поскольку у них нет категорий, мы не можем напрямую разделить эти функции. Вместо этого мы сначала сортируем их от низшего к высшему. Затем мы вычисляем среднее значение переменной между каждыми соседними точками данных. В нашем примере после сортировки возраста функции мы сначала вычисляем среднее значение между первой и второй точкой данных, в результате чего получается 9,5. Затем мы вычисляем значение между второй и третьей точками как 15 и продолжаем до последней точки данных.

Используя каждое из этих значений в качестве пороговых, мы выращиваем поддеревья и вычисляем индексы Джини корней-кандидатов так же, как мы вычисляем Джини для категориальной переменной. Например, для первого порогового значения 9,5 индекс Джини равен 0,429.

Вы можете увидеть рассчитанные индексы Джини для каждого порога ниже:

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

Мы рассчитали примесь Джини для всех переменных в нашем наборе данных. Переменная Loves soda дает наименьшее значение, 0,214. Таким образом, мы выбираем его в качестве корневого узла.

2- Выращивание дерева

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

С другой стороны, для левого листа у нас все еще есть некоторая примесь. Мы проверим, можем ли мы уменьшить неопределенность в этом листе.

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

Поскольку возраст ‹ 12,5 лет дает самый низкий коэффициент Джини, мы используем это утверждение в качестве следующей ветви.

Наше результирующее дерево становится:

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

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

Реализация дерева классификации с помощью Scikit-Learn

Существуют различные алгоритмы дерева решений, такие как алгоритмы ID3 и CART. Scikit-Learn использует CART, который выращивает исключительно бинарные поддеревья, что означает, что максимальное количество дочерних элементов ветки может быть равно двум.

Scikit-Learn выращивает деревья, как описано выше. Он пытается найти корневой узел, сканируя все функции (если вы не укажете параметр max_features) и выбирает атрибут с наименьшим критерием неопределенности, выбранным для достижения самых чистых поддеревьев. Затем он пытается найти ветви, повторяя процесс, и так далее.

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

max_depth: maximum depth of the tree
min_samples_split: minimum number of data points a node needs before split
min_samples_leaf: minimum number of data points needed at each leaf
min_weight_fraction_leaf: the same as min_samples_leaf, only represents the fraction of the total number of weighted samples
max_leaf_nodes: maximum number of leaves
max_features: maximum number of the features that are evaluated for each split
min_impurity_decrease: minimum decrease in the uncertainty metric for a node to split

Как правило, увеличение параметров, начинающихся с min, или уменьшение параметров, начинающихся с max, упорядочивает модель.

Возьмем игрушечный пример.

Предположим, мы хотим оценить, совершит ли клиент покупку в следующем месяце. Для простоты мы используем три функции.

Для выращивания небольшого дерева указан только параметр max_depth. После подбора классификатора вызывается функция GraphViz sklearn для визуализации дерева. Поскольку функция выводит файл .dot, формат изменяется на .png с помощью этой команды bash:

$ dot -Tpng freq_tree.dot -o freq_tree.png

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

Одним из важных атрибутов классификатора является feature_importances_, который показывает общее снижение метрики неопределенности, связанной с каждой функцией.

tree_clf.feature_importances_
array([0.71795632, 0.19818226, 0.08386142])

Мы видим, что функция_1 вызывает наибольшее снижение Джини, тогда как функция_2 отвечает почти за 20%, а функция_3, похоже, не вызывает значительного снижения.

Сокращение

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

Для пост-обрезки sklearn использует параметр сложности стоимости, ccp_alpha. Увеличение этого параметра увеличивает количество удаляемых узлов. Мы можем определить, какое значение ccp_alpha использовать, используя метод cost_complexity_pruning_path класса DecisionTreeClassifier. Метод дает нам возможные значения ccp_alpha, которые мы можем перебрать, чтобы найти оптимальный классификатор.

Вы можете увидеть наше обрезанное дерево ниже:

Существует множество других методов и атрибутов, которые можно использовать с DecisionTreeClassifier, и вы можете изучить больше из документации Scikit-Learn.

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

Вы также можете взглянуть на DecisionTreeRegressor sklearn.

Зачем использовать дерево решений, если существуют современные алгоритмы на основе дерева?

  • Дерево решений — это одна из моделей белого ящика, то есть ее легко интерпретировать, поскольку известны движущие факторы, лежащие в основе отдельного прогноза. Напротив, другие древовидные алгоритмы, такие как Random Forest, LightGBM и XGBoost, называются черным ящиком, потому что не так просто узнать, почему создается конкретный результат. Тем не менее, есть некоторые методы, с помощью которых мы можем анализировать влияние каждого атрибута. Мы рассмотрим эти методы в другой статье.
  • Дерево решений говорит нам, какая функция более полезна в нашей проблеме. Мы можем использовать эту силу, используя алгоритм выбора признаков. Затем мы можем реализовать более сложные модели с полученными функциями.

Ссылки:

  1. https://www.youtube.com/watch?v=_L39rN6gz7Y&t=915s
  2. Орельен Жерон (2019). Практическое машинное обучение с помощью Scikit-Learn, Keras и TensorFlow: концепции, инструменты и методы создания интеллектуальных систем, 2-е издание
  3. https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html