Дерево решений — один из самых простых алгоритмов для понимания и интерпретации. Если вы знакомы с операторами if-else в программировании, то это почти все, что вам нужно знать, чтобы понять, как работает алгоритм дерева решений. Даже если вы не знакомы с программированием, но если вы примените свой здравый смысл и обратитесь к примерам из реальной жизни, вы легко поймете алгоритм дерева решений. Например, если в автомобиле есть топливо, то он заведется, если вы попытаетесь, то вы можете потерпеть неудачу или добиться успеха, если идет дождь, совпадение не произойдет и т. д. Таким образом, на основе этих условных утверждений только дерево решений помогает нам построить модель, чтобы что-то предсказать. для будущего.
Дерево решений — это контролируемый алгоритм машинного обучения, который используется для регрессии обоих типов задач (то есть прогнозирования непрерывного значения для будущей цены дома, количества часов, в течение которых матч может быть сыгран в условиях пасмурной погоды и т. д.), и классификации (то есть классификации различных объектов на соответствующие категории или классы, например, учитывая пасмурную погоду, матч будет сыгран или нет, данное изображение принадлежит кошке или собаке и т. д.).
Содержание
- Важные определения
- Однородные и разнородные данные
- Энтропия и получение информации
- Джини и примесь Джини
- Снижение стандартного отклонения
- Различные узлы в дереве решений
- Различные алгоритмы, используемые для построения дерева решений
- Дерево решений для классификации
- Построение дерева решений для заданных данных с использованием энтропии и прироста информации
- Построение дерева решений для заданных данных с использованием Джини и индекса Джини
- Полный код для построения дерева решений в python
- Дерево решений для регрессии
- Построить дерево решений, используя стратегию уменьшения стандартного отклонения
Важные определения
Однородные и разнородные узлы данных
Понимание однородной природы узлов данных очень важно, когда речь идет о дереве решений. Это напрямую связано с предсказательной силой построения дерева. Если вы выберете случайный элемент данных из полностью однородного узла, вам не составит труда определить, к какому классу он принадлежит. Есть идея? если нет, то позвольте мне объяснить, что подразумевается под гомогенными и неоднородными узлами данных.
Полностью однородный узел — это узел, в котором все элементы данных принадлежат одному и тому же классу. И по мере того, как мы продолжаем смешивать элементы данных из разных классов, он становится неоднородным или гетерогенным узлом. Таким образом, полностью гетерогенным узлом данных будет тот, который имеет равную долю всех элементов данных классов. Давайте поймем то же самое, визуализируя некоторые графики, как показано ниже:
Рисунок выше говорит сам за себя, но я все же хочу подчеркнуть одну вещь: как математически вы будете измерять уровень однородности в узле? Потому что этот уровень однородности помогает вам решить, где разделить данные и как сформировать дерево решений. Вот где появляются концепции энтропии, прироста информации и примеси Джини.
Энтропия и информационный прирост
Энтропия — это мера случайности ваших данных. Чем больше случайности, тем больше энтропии, тем сложнее делать какие-либо выводы или труднее классифицировать. Давайте свяжем это с концепцией однородности, описанной выше, чтобы упростить понимание. Если ваш узел данных неоднороден, будет трудно сделать какой-либо вывод об этом узле данных, что приведет к более высокой энтропии.
Высокая энтропия означает большую случайность, что означает меньшую однородность (гетерогенность)
Таким образом, в дереве решений каждое разделение основано на уменьшении энтропии, чтобы мы могли добраться до менее разнородного или более однородного узла. Поэтому мы разбиваем таким образом, чтобы после каждого разбиения мы получали более однородный узел, чтобы сделать вывод было легко. И, следовательно, при каждом расщеплении будет уменьшаться энтропия. И это снижение энтропии известно как получение информации.
на приведенном выше графике видно, что когда у нас есть идеальный результат, среднее значение вероятности которого равно 1 или 0, тогда энтропия равна 0. Это означает, что случайность отсутствует. И когда степень случайности увеличивается, вероятность будет отображаться в диапазоне от 0 до 1. Для вероятности = 0,5 (оба события равновероятны) будет максимальная случайность, и, следовательно, энтропия будет максимальной, равной 1.
Мы будем использовать приведенные ниже данные для целей расчета (даже для следующих определений в посте)
Расчет энтропии
Получение информации
Прирост информации — это мера однородности, которую мы достигаем после разделения узла данных. В статистической терминологии величина снижения энтропии после разделения узла данных называется приростом информации.
Из приведенной выше формулы вы можете легко сказать, что:
Больше информации = меньше энтропии (T,X) = более однородный узел
Это соответствует нашей цели получить более однородный узел данных после разделения. Таким образом, мы вычисляем энтропию цели с каждой независимой переменной и видим, где прирост информации больше означает, где мы получаем более однородный узел. Таким образом, переменная, которая имеет больший информационный прирост, будет помещена в корень.
Предположим, набор данных содержит две переменные, которые означают два узла. И на изображении ниже я попытался визуализировать, как будет выглядеть разделение, если мы попытаемся разделить на A и B отдельно. Итак, если вы видите, что когда мы пытаемся разделить с помощью B, мы получаем сравнительно более однородные узлы. Это означает, что разделенные узлы имеют большую долю одного класса, чем другого класса.
Есть еще один критерий для разделения узла, использующего Gini и Gini Impurity. Давайте больше разберемся с критериями Джини.
Джини и примесь Джини
Джини рассчитывается по формуле — сумма квадратов вероятности успеха и неудачи (p²+q²)
Джини прямо пропорционален однородности. Чем выше значение Джини, тем выше уровень однородности после разделения.
Примесь Джини обратно пропорциональна однородности. Таким образом, при разделении мы ищем наименьшую примесь Джини, и узел с наименьшей примесью Джини делается корневым узлом.
Алгоритм дерева классификации и регрессии (CART) использует показатель Джини в качестве критерия для разделения узлов в дереве решений. И другим важным моментом является то, что Gini работает только для бинарного разделения с категориальной целью как успех или неудача.
Давайте возьмем данные примера футбольного матча и рассчитаем коэффициент Джини для столбца Outlook.
Здесь снова, аналогично энтропии цели по отношению к независимой переменной, будет вычисляться Джини цели по отношению к независимой переменной, и это также известно как взвешенное Джини.
Здесь также будут вычисляться взвешенные значения Джини по отношению к дождливым, пасмурным и солнечным строкам и суммироваться, чтобы получить окончательное значение Джини для столбца прогноза.
Точно так же вы можете создать примесь Джини для других независимых переменных и посмотреть, какая из них имеет наименьшую примесь Джини. Тот, который имеет наименьшую примесь Джини, будет корневым узлом.
Уменьшение дисперсии или уменьшение стандартного отклонения — SDR
Энтропия, прирост информации и примесь Джини используются в задачах классификации. Так что насчет регрессии? Подобно получению информации, то есть уменьшению энтропии, у нас есть уменьшение дисперсии или уменьшение стандартного отклонения, которое используется для задачи регрессионного типа в дереве решений.
Итак, мы вычисляем взвешенный SDR относительно независимой переменной и смотрим, где мы получаем большее значение SDR, и это будет корневой узел.
Чтобы рассчитать стандартное отклонение для отдельных атрибутов, например, для прогноза дождя, рассмотрите только данные дождливых строк и примените формулу к часам игры.
Сокращение стандартного отклонения основано на уменьшении стандартного отклонения после разделения. Таким образом, переменная, дающая наибольшее значение SDR, будет объявлена корневым узлом. И самый высокий SDR будет соответствовать наиболее однородным узлам после разделения.
Понимание различных узлов в деревьях решений
- Корневой узел. Он представляет собой всю совокупность или выборку, которая затем делится на два или более однородных набора. Если вы рассматриваете прирост информации, то узел с максимальным приростом информации станет корневым узлом.
- Узел принятия решения. Когда подузел разделяется на дополнительные подузлы, он называется узлом принятия решения. В основном это помогает вам решить, следует ли выбрать (выбрать или перейти) правое поддерево или левое поддерево.
- Листовой/терминальный узел:узлы, которые не разделяются, называются конечными или конечными узлами.
- Ветвь/Поддерево.Подраздел всего дерева называется ветвью или поддеревом.
- Родительский и дочерний узел.Узел, который разделен на подузлы, называется родительским узлом подузлов, тогда как подузлы являются дочерними по отношению к родительскому узлу.
- Сокращение. Когда мы удаляем подузлы узла принятия решений, этот процесс называется сокращением. Можно сказать обратный процесс расщепления. Он используется при настройке гиперпараметров в деревьях решений.
Различные алгоритмы, используемые для построения дерева решений
Дерево решений используется для обоих типов задач: классификации и регрессии. Поэтому в зависимости от типов задач используются разные алгоритмы.
Алгоритмы также классифицируются на основе различных критериев разделения, таких как энтропия, прирост информации, Джини и индекс Джини, а также уменьшение стандартного отклонения.
Давайте посмотрим на некоторые алгоритмы, используемые в деревьях решений:
ID3 → (Итеративный дихотомайзер 3, использует энтропию и информацию для задач классификации и уменьшение стандартного отклонения для задач регрессии)
→ (преемник ID3 и используется для классификация)
CART→ (Дерево классификации и регрессии. Используется как для классификации, так и для регрессии)
CHAID→ (Автоматический хи-квадрат обнаружение взаимодействия Выполняет многоуровневое разбиение при вычислении деревьев классификации)
MARS→ (многомерные адаптивные регрессионные сплайны)
Дерево решений для задач классификации
Построение дерева решений для заданных данных с использованием энтропии и информации
Пожалуйста, посмотрите видео, объясняющее формирование дерева решений и разделение с использованием энтропии и прироста информации.
Построение дерева решений для заданных данных с использованием Джини и индекса Джини
Пожалуйста, посмотрите видео, в котором объясняется формирование дерева решений с использованием Джини и индекса Джини.
Полный код для построения дерева решений для классификации с использованием Python
Пожалуйста, обратитесь к моему сообщению с пошаговым руководством по построению дерева решений с использованием python.
Дерево решений для регрессии
Пожалуйста, обратитесь к моему сообщению с пошаговым руководством по построению дерева решений для регрессии.
https://medium.com/p/3aa1d29329af
Первоначально опубликовано на http://ashutoshtripathi.com 29 марта 2022 г.
