Подробный пример построения дерева решений для классификации

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

Введение

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

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

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

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

Прежде чем вдаваться в подробности того, как строится это дерево, давайте определимся с некоторыми важными терминами.

Условия

Корневой узел

Узел верхнего уровня. Первое принятое решение. В нашем примере корневой узел «любит гравитацию».

Ветви

Ветви представляют поддеревья. Наш пример имеет две ветви. Одна ветвь, например. поддерево от «любит собак» и второе от «возраст ‹ 40,5» и далее.

Узел

Узел представляет собой разделение на дополнительные (дочерние) узлы. В нашем примере это узлы «любит гравитацию», «любит собак» и «возраст ‹ 40,5».

Лист

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

Родительский узел

Узел, который предшествует (дочернему) узлу, называется родительским узлом. В нашем примере «любит гравитацию» является родительским узлом «любит собак», а «любит собак» является родительским узлом «возраст ‹ 40,5».

Дочерний узел

Узел под другим узлом является дочерним узлом. В нашем примере «любит собак» является дочерним узлом «любит гравитацию», а «возраст ‹ 40,5» — дочерним узлом «любит собак».

Разделение

Процесс разделения узла на два (дочерних) узла.

Обрезка

Удаление (дочерних) узлов родительского узла называется обрезкой. Дерево растет путем расщепления и уменьшается в результате обрезки. В нашем примере, если бы мы удалили узел «возраст ‹ 40,5», мы бы обрезали дерево.

Мы также можем заметить, что дерево решений позволяет нам смешивать типы данных. Мы можем использовать числовые данные («возраст») и категориальные данные («любит собак», «любит гравитацию») в одном и том же дереве.

Создайте дерево решений

Наиболее важным шагом в создании дерева решений является разделение данных. Нам нужно найти способ разделить набор данных (D) на два набора данных (D_1) и (D_2). Существуют различные критерии, которые можно использовать для поиска следующего разделения. "здесь". Мы сосредоточимся на одном из них: Gini Impurity, который является критерием для категориальных целевых переменных, а также критерием, используемым библиотекой Python scikit-learn.

Примесь Джини

Примесь Джини для набора данных D рассчитывается следующим образом:

при n = n_1 + n_2 размер набора данных (D) и

с D_1 и D_2 подмножествами D, 𝑝_𝑗 вероятностью выборок, принадлежащих классу 𝑗 в данном узле, и 𝑐 количеством классов. Чем ниже примесь Джини, тем выше однородность узла. Примесь Джини чистого узла равна нулю. Чтобы разделить дерево решений с помощью примеси Джини, необходимо выполнить следующие шаги.

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

Повторяйте шаги 1–3 до тех пор, пока дальнейшее разделение не станет возможным.

Чтобы лучше понять это, давайте посмотрим на пример.

Первый пример: дерево решений с двумя бинарными функциями

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

Первое, что нам нужно решить, это то, какая функция будет корневым узлом. Мы делаем это, предсказывая цель только с одной из функций, а затем используем функцию с наименьшей примесью Джини в качестве корневого узла. То есть в нашем случае мы строим два неглубоких дерева только с корневым узлом и двумя листами. В первом случае мы используем «любит гравитацию» в качестве корневого узла, а во втором случае «любит собак». Затем мы вычисляем примесь Джини для обоих. Деревья выглядят так:

Примесь Джини для этих деревьев рассчитывается следующим образом:

Случай 1:

Набор данных 1:

Набор данных 2:

Примесь Джини представляет собой средневзвешенное значение обоих:

Случай 2:

Набор данных 1:

Набор данных 2:

Примесь Джини представляет собой средневзвешенное значение обоих:

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

Второй пример: добавление числовой переменной

До сих пор мы рассматривали только подмножество нашего набора данных — категориальные переменные. Теперь мы добавим числовую переменную «возраст». Критерий разделения тот же. Мы уже знаем примеси Джини для «любит гравитацию» и «любит собак». Вычисление примеси Джини для числовой переменной аналогично, однако для принятия решения требуется больше вычислений. Необходимо выполнить следующие шаги

  1. Сортировка фрейма данных по числовой переменной («возраст»)
  2. Вычислить среднее значение соседних значений
  3. Рассчитайте примесь Джини для всех расщеплений для каждого из этих средних значений.

Это снова наши данные, отсортированные по возрасту, а среднее значение соседних значений указано слева.

Тогда у нас есть следующие возможные расщепления.

Мы видим, что примесь Джини для всех возможных разделений «возраст» выше, чем для «любит гравитацию» и «любит собак». Самая низкая примесь Джини возникает при использовании «любит гравитацию», т. е. это наш корневой узел и первое разделение.

Подмножество Набор данных 2 уже является чистым, то есть этот узел является листом, и дальнейшее разбиение не требуется. Ветвь слева, набор данных 1, не является чистым и может быть разделен дальше. Мы делаем это так же, как и раньше: мы вычисляем примесь Джини для каждого признака: «любит собак» и «возраст».

Мы видим, что наименьшую примесь Джини дает разбивка «любит собак». Теперь мы можем построить наше финальное дерево.

Использование Python

В Python мы можем использовать метод scikit-learn DecisionTreeClassifier для построения дерева решений для классификации. Обратите внимание, что scikit-learn также предоставляет DecisionTreeRegressor, метод использования деревьев решений для регрессии. Предположим, что наши данные хранятся во фрейме данных df, затем мы можем обучить их, используя метод подгонки:

from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier()
X = df['age', 'likes dogs', 'likes graviy']
y = df['going_to_be_an_astronaut']
clf.fit(X,y)

Мы можем визуализировать результирующее дерево, используя метод ‘plot_tree’. Он такой же, как мы построили, только критерии разбиения названы с «‹=» вместо «‹», а «истинный» и «ложный» пути идут в другую сторону. То есть есть некоторые отличия во внешнем виде.

plot_tree(clf, feature_names=[‘age’,‘likes_dogs’,‘likes_gravity’], fontsize=8);

Преимущества и недостатки деревьев решений

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

Плюсы

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

Минусы

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

Заключение

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

Рекомендации

Все изображения, если не указано иное, принадлежат автору.



Получать электронное письмо каждый раз, когда фрауке Альбрехт публикует.
Получать электронное письмо, когда фрауке Альбрехт публикует. Зарегистрировавшись, вы создадите учетную запись Medium, если вы еще этого не сделали…medium.com





Присоединяйтесь к Medium по моей реферальной ссылке — Фрауке Альбрехт
Прочитайте все статьи Фрауке Альбрехт (и тысяч других авторов на Medium). Ваш членский взнос напрямую поддерживает…medium.com