Один из самых популярных и используемых алгоритмов машинного обучения

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

Каковы компоненты дерева решений?

Основные составляющие:

а ) Корневой узел: обычно в этом узле будут доступны все обучающие данные. Данные из всех классов будут перемешаны.

б) Узлы решений: обычно они имеют формат, подобный атрибуту «A» и некоторому условию «k». Например, Age ›30, что создает еще два узла.

c) Внутренний узел и Терминальный узел: внутренние узлы являются результатом узлов принятия решения, если они достаточно чистые, они могут быть Терминальными узлами, в противном случае они являются внутренними узлами, которые должны будут пройти повторное решение. узлы. Узел принятия решения может четко сказать нам, какое неизвестное наблюдение будет помечено, если оно приземлится в этом узле.

Давайте проиллюстрируем это на очень простом примере, допустим, у нас есть данные 10 учеников, их оценки по вербальным способностям и математике. Студенты распределяются по классам в зависимости от успешности их размещения. Эти три класса: «Помещено немедленно» (PI), «Помещено через некоторое время» (PA), Незамещено (U) соответственно.

В случае дерева решений оно будет иметь структуру, как показано ниже, для вышеуказанных данных. Дерево имеет один корневой узел, два узла принятия решений (Maths = High, English = High) и трехконечные узлы, соответствующие трем классам.

Наблюдения:

  • Корневой узел очень смешанный с точки зрения классов, поскольку мы переходим к конечным узлам, узлы имеют более однородную совокупность (максимум 2 класса и 1 класс - большинство).
  • Теперь, если у нас есть ученик Сэм, и мы знаем, что он имеет высокие баллы как по математике, так и по английскому, мы знаем, что, следуя дереву решений, его шанс сразу занять место очень высок.

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

Как формально измерить однородность или неоднородность узла?

Это требует введения в понятие энтропии.

Энтропия:

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

Мы понимаем, что к настоящему времени энтропия будет функцией вероятности.

X - случайная величина, H (X) - энтропия случайной величины. S - это набор значений, которые может принимать случайная величина, или пространство выборки. s - точка выборки. Думаю, вы согласитесь с тем, что подбрасывание монеты - это лучший мир любого случайного эксперимента.

Когда это честная монета, она совершенно случайна или неопределенна, постепенно мы можем смещать ее и сравнять с ней 1. Давайте снова разберемся с этим на примере. Возьмем разные сценарии вероятности выпадения.

Наблюдения:

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

Итак, мы понимаем, что нам следует перейти от узлов с высокой энтропией к низкой энтропии, но если есть два атрибута «a» и «b», как нам использовать энтропию для принятия этого решения.

Время для сбора информации, чтобы сделать запись.

Что такое получение информации?

Формально это определяется приведенным ниже уравнением. Идея проста. Допустим, у корневого узла есть энтропия E, и когда мы разделяем атрибутом «a» при некотором условии (например, по математике score = high), мы получаем еще два узла N1 и N2, имеющих соответствующие энтропии, такие как E1 и E2.

Самый первый прирост информации среза будет E - (E1 + E2) / 2. На следующем шаге мы просто делаем уточнение, взвешивая энтропии по количеству элементов, присутствующих в N1 и N2 соответственно. Это формализовано в приведенном ниже уравнении.

H (T) - энтропия до разделения H (T / a) - энтропия после разделения по атрибуту «a» при некотором условии

Как получение информации применяется для выбора атрибута для разделения?

Давайте дополнительно разберемся с этим с помощью необходимых математических расчетов, давайте сравним два возможных варианта разделения, обозначенных как «A» и «B».

Расчет прироста информации будет выглядеть следующим образом

Наблюдение

  • Сценарий A имеет энтропию 0,81, а сценарий B имеет энтропию 0,69.
  • Корневой узел имеет энтропию 1.0 (тот же сценарий, что и при подбрасывании честной монеты)
  • Таким образом, информационный прирост в первом случае составляет 0,19, а во втором - 0,31 . Следовательно, будет выбран атрибут B.

Есть еще один эквивалентный показатель получения информации, называемый индексом Джини. Согласно ссылке [1], только в 2% случаев имеет значение, используете ли вы индекс Джини или получение информации. Так что давайте не будем углубляться в это.

Какие бывают варианты деревьев?

  • Это скорее академический интерес, и здесь мы обсуждаем предварительные деревья, такие как ID3, C4.5, C5.0 и CART.
  • ID3 Iterative Dichotomiser 3 использует сбор информации. Изобретен Россом Куинланом в 1986 году.
  • Он начинается с поиска наилучшего категориального признака для разделения.
  • Затем рекурсивно выберите следующий атрибут (не выбран)
  • Пока больше не будет возможности разделения, будет достигнут листовой узел или не останется атрибутов для разделения
  • Это жадный алгоритм, не откатывается.
  • В C4.5 снято ограничение категориального атрибута, но разрешено преобразование числового атрибута в категориальный атрибут (J48)
  • C 4.5 обладал способностью обрабатывать недостающие данные. C4.5 имел возможность отката. Он стал довольно популярным после того, как занял первое место в 10 лучших алгоритмах интеллектуального анализа данных, опубликованном Springe r.
  • C 5.0 был дальнейшим улучшением с точки зрения создания дерева меньшего размера, эффективного использования памяти и увеличения
  • CART - еще один очень известный алгоритм, который может работать как с числовыми, так и с категориальными атрибутами, работать как с классификацией, так и с регрессией, а также может обрабатывать выбросы. Это двухстороннее разделение.

Как мы справляемся с переобучением в деревьях решений?

Как и любая проблема с машинным обучением, эти модели также подвержены переобучению. Если дерево переоборудовано, оно, как правило, будет иметь большую глубину. большее количество оконечных узлов. Таким образом, более гладкое дерево будет менее приспособленным. Здесь мы обсуждаем некоторые стратегии.

а) Минимальное количество наблюдений в листовом или конечном узле:

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

б) Минимальное количество наблюдений, необходимых для разделения узла:

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

c) Допустимая максимальная глубина:

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

Приведенная выше диаграмма является результатом наших экспериментов с использованием дерева решений (https://www.kaggle.com/saptarsi/decision-tree-sg/), есть еще несколько интересных экспериментов, которые вы можете уловить.

Он ясно показывает, что глубина 12 - это хорошо, после этого особого повышения точности теста не наблюдается.

г) Регуляризуйте функцию потерь:

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

Итак, если у нас есть два дерева, оба имеют одинаковую квадратичную ошибку. Дерево 1 имеет 5 листовых узлов, а дерево 2 - 4 листовых узла. Это уравнение предпочтет второе. (Воспроизведено с ISLR)

Заключение:

  • Деревья решений обеспечивают отличную визуализацию, а причина классификации понятна бизнес-пользователю и, следовательно, является моделью белого ящика.
  • Очень просто понять
  • Однако может не дать оптимальной производительности (это можно решить с помощью случайного леса, ускорения и т. Д.)

========================================

Спасибо, что дочитали до этого места. Это некоторые дополнительные ресурсы, созданные нами в Лаборатории анализа данных Университета Калькутты.

а) Классификация с помощью Python (https://www.youtube.com/playlist?list=PLTS7rWcD0Do2ZoO4Sad3jRxnVFyxHd6_S)

б) Кластеризация с помощью Python (https://www.youtube.com/playlist?list=PLTS7rWcD0Do3ts44xgWGVgxMeoHYFi3pM)

Ссылка:

[1] Райляну Л.Е., Стоффель К. Теоретическое сравнение индекса Джини и критериев получения информации. Анналы математики и искусственного интеллекта. 2004 1 мая; 41 (1): 77–93.

[2] https://towardsdatascience.com/the-complete-guide-to-decision-trees-28a4e3c7be14

[3] https://towardsdatascience.com/decision-trees-in-machine-learning-641b9c4e8052