Простое объяснение того, как алгоритм дерева решений принимает решения

Интуиция за алгоритмом дерева решений

Дерево решений — очень популярный алгоритм машинного обучения. Он работает как для линейных, так и для нелинейных данных. Кроме того, его можно использовать как для классификации, так и для регрессии. Благодаря отличным библиотекам и пакетам, доступным в Python и R, любой может легко использовать дерево решений и другие алгоритмы машинного обучения, даже не зная, как они работают. Но знание интуиции или механизма алгоритма помогает принимать решения о том, где его использовать.

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

Эта статья будет включать:

Общее введение в рабочий процесс алгоритма дерева решений. Не беспокойтесь, если это общее введение не так ясно. Следующая часть — подробное объяснение с примером. Так будет понятнее.

Пример и математический расчет решений в дереве решений: в этой части будет показано реальное принятие решений алгоритмом дерева решений с использованием математических расчетов.

Введение в дерево решений

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

Как вы можете видеть на рисунке, все начинается с корневого условия, и на основе решения из этого корневого условия мы получаем три ветви: C1, C2 и C3. Это не обязательно должно быть три ветви. Ветвей может быть и больше, в зависимости от количества классов в фиче корневого узла. Одна ветка закончилась листом. Листовой узел означает окончательное решение или прогноз. C1 и C3 корневого узла получили Confition1 и Condition2.

Условие1 и условие2 — это две разные функции. Далее мы разделим данные на основе категорий в условии1 и условии3. На приведенном выше рисунке показано, что и условие1, и условие3 имеют по две функции. Как обычно, категорий может быть больше. Это высокоуровневая идея того, как дерево решений делает прогнозы. Мы увидим более подробно, как на самом деле мы выбирали функции для корневого узла и других условий.

Вот некоторые термины, которые необходимо прояснить, прежде чем углубляться:

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

Узлы принятия решений. Посмотрите на узлы «условие1» и «условие3» выше. Мы получили эти узлы после разделения на основе корневого узла, а затем разделили на основе узла решения.

Листовые узлы. Это конечные узлы, в которых дерево решений принимает окончательные решения, и дальнейшее разделение невозможно. На картинке выше Decision2 и Decision3 — конечные узлы.

Пример и математический расчет решений в дереве решений

Вот синтетический набор данных, который я создал для этого примера. Этот набор данных имеет двоичный класс и три переменные N1, N2 и N3. Все три переменные являются категориальными. Я взял все категориальные переменные, потому что это легче объяснить. После того как вы разовьете интуицию, вам будет легче понять, как использовать непрерывные переменные.

У нас есть набор данных. Согласно предыдущему обсуждению, нам нужен корневой узел, на основе которого мы начнем разбивать данные. Но у нас есть три переменные. Как определить корневой узел? Должен ли я просто начать с N1, потому что он стоит первым в наборе данных?

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

Корневой узел или первый тестовый атрибут выбирается на основе статистического показателя, называемого приростом информации.

В целом выбор тестовых атрибутов зависит от «меры чистоты». Это меры чистоты:

Прирост информации
Коэффициент усиления
Индекс Джини

В этой статье мы подробно поговорим о «Получении информации».

Получение информации

Представьте, что 10 друзей тусуются. 5 из них хотят посмотреть фильм и 5 из них хотят пойти куда-нибудь. Принять решение в этом случае очень сложно. Если 8 или 9 из них захотят посмотреть фильм и только 1 или 2 захотят пойти куда-нибудь, принять решение будет легче. Верно? Лучше всего, если все 10 из них хотят одного и того же. Принимать решения очень просто. Никакой путаницы!

В дереве решений также, если весь класс принадлежит либо да, либо нет, набор данных является самым чистым. С другой стороны, если 50 % класса принадлежат «да», а остальные 50 % — «нет», то набор данных крайне нечист. Потому что трудно принять решение. Решение очень неопределенное!

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

Расчет прироста информации зависит от информации. Это также называется энтропией.

Формула для информации:

Давайте поработаем на примере.

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

Теперь давайте рассчитаем информацию для нашего фиктивного набора данных. Этот набор данных имеет в общей сложности 14 строк данных, 8 классов «да» и 6 классов «нет».

Итак, информация:

Информация выходит 0,985. Это родительская энтропия.

Далее нам нужно вычислить Info для трех переменных N1, N2 и N3 одну за другой.

Начиная с N1:

Нам нужно рассчитать количество информации, необходимой для классификации выборок, разбив набор данных на N1:

Во-первых, давайте проанализируем данные в N1. Есть:

4 «Дождливая», где 2 «Да» и 2 «Н» класса

4 «Солнечно», где 2 «Y» и 2 «N» класса

6 «Облачно», где классы 4 «Y» и 2 «N»

Информация, необходимая для классификации набора данных на основе N1:

Это дает 0,964.

Info_gain(N1) = 0,985–0,964 = 0,02

Таким образом, энтропия уменьшится на 0,02, если N1 станет корневым узлом.

Таким же образом мы можем рассчитать Info(DN2) и Info(DN3) как 0,972 и 0,983 соответственно.

Таким образом, прирост информации для N2 и N3 составляет:

Info_gain(N2) = 0,985–0,972 = 0,012

Info_gain(N3) = 0,985–0,983 = 0,001

Энтропия уменьшится на 0,012 и 0,001 соответственно, если мы сделаем N2 или N3 нашим корневым узлом.

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

На этом этапе с фиксированным корневым узлом дерево решений будет выглядеть так:

Мы выбрали корневой узел и разделили данные на основе корневого узла. На рисунке показано точное разделение данных с соответствующими классами.

Что дальше?

Как вы можете видеть, когда «дождливо» или «солнечно», энтропия очень высока. Потому что там одинаковое количество Y и N. Но энтропия ниже, когда «облачно». Таким образом, класс может быть Y, когда «облачно». Мы можем снова разделить данные на основе N2 и N3. Для этого мы должны рассчитать прирост информации для каждого из подузлов «Дождь», «Облачно» и «Солнечно», чтобы решить, какая функция будет следующей и где. Как видите, для каждого подразделения у нас теперь гораздо меньшие наборы данных.

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

Где прекратить расщепление

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

Для этого в функции дерева решений библиотеки scikit-learn есть параметр max_depth. Если параметр максимальной глубины большой, дерево будет больше. Итак, мы можем выбрать глубину дерева. Хотя вы всегда можете использовать любой метод выбора функций по вашему выбору, чтобы выбрать меньшее количество функций для алгоритма.

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

Пожалуйста, смотрите документацию для других параметров.

Основные преимущества алгоритма дерева решений

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

Основные недостатки алгоритма дерева решений

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

Заключение

Python и R имеют очень хорошие пакеты для всех популярных алгоритмов машинного обучения. Так что теперь работать очень легко. Но знание лежащих в основе механизмов значительно облегчает принятие решений о выборе правильного алгоритма машинного обучения для вашего проекта.