Введение

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

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

Потребность в деревьях решений

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

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

  • Классы на изображении справа хорошо разделены.
  • У них есть линейная граница принятия решения.

Напомним, что граница принятия решения — это поверхность, на которой вероятность оказаться в положительном классе равна вероятности оказаться в отрицательном классе.

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

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

Основы дерева решений

Формально модель дерева решений определяется как древовидная структура/блок-схема, в которой окончательный результат модели основан на серия сравнений значений предикторов с пороговыми значениями.

Прочитав приведенное выше определение, я бы определил дерево решений как не что иное, как набор причудливых операторов if-else!!

В графическом представлении (блок-схема),

  • Внутренние узлы дерева представляют тестирование атрибутов.
  • Переход на следующий уровень определяется значением атрибута (да/нет).
  • Конечные листовые узлы представляют назначения классов.

На изображении выше представлено дерево решений. Блоки на блок-схеме называются узлами дерева. Первый узел называется корневым узлом, а последние узлы дерева называются конечными узлами. Каждое сравнение и разветвление представляет собой разделение области в пространстве признаков на один признак. Обычно на каждой итерации мы разделяем один раз по одному измерению (один предиктор).

Теперь вам может прийти в голову несколько вопросов, например: как мы решим, какой предиктор станет корневым узлом? до когда мы должны вырастить дерево? как нам разделить дерево? Мы ответим на все подобные вопросы в следующем разделе, где мы поговорим о математике, стоящей за деревом решений.

Алгоритм дерева решений и математика, стоящая за ним

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

  1. Начните с пустого дерева решений (неразделенное пространство признаков).
  2. Выберите «оптимальный» предиктор для разделения и выберите «оптимальное» пороговое значение для разделения.
  3. Рекурсия на каждом новом узле, пока не будет выполнено условие остановки.

Теперь мы знаем об алгоритме и можем сосредоточиться на ответах на такие вопросы, как «Как разделить дерево?», «Как определить корневой узел?», «Как определить условие остановки?» Далее мы отвечаем на эти вопросы по одному.

В. Как разделить дерево?

Как правило, существует 2 критерия, по которым мы можем разделить дерево: один называется индексом Джини, а другой называется энтропия. Мы обсудим это один за другим.

1. Индекс Джини

Индекс Джини узла — это показатель его загрязненности. Узел считается «чистым», если его индекс Джини равен 0, т. е. все точки обучения принадлежат одному классу. Математически индекс Джини определяется как

Где pi – это отношение количества экземпляров, принадлежащих классу i, к общему количеству экземпляров в данном узле.

2. Энтропия

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

Итак, теперь мы знаем 2 критерия, по которым можно разделить дерево. Далее попробуем ответить на вопрос «Как определить корневой узел?»

В. Как определить корневой узел?

Чтобы определиться с корневым узлом, мы определяем еще один показатель, который называется Получение информации. Он определяется как уменьшение энтропии или случайности системы.

  1. Мы вычисляем исходную энтропию для всей системы, т. е. энтропию до того, как произошло какое-либо разделение.
  2. Мы случайным образом берем предиктор, разделяем его на основе порога и вычисляем энтропию для каждого дочернего узла.
  3. Затем мы берем взвешенную сумму энтропий обоих дочерних узлов, где вес равен отношению количества точек данных в соответствующем дочернем узле к общему количеству точек данных в обоих дочерних узлах. дочерние узлы.
  4. Затем мы вычисляем разницу между энтропией исходного шага, т. е. рассчитанной на шаге 1, и энтропией преобразованной системы, т. е. рассчитанной на шаге 3.
  5. В качестве корневого узла выбирается переменная или предиктор, дающий максимальный информационный прирост из всех предикторов.

Чтобы понять концепцию Получения информации с помощью примера, обратитесь к этому замечательному видео от StatQuest. Далее мы ответим на вопрос Как определить условие остановки?

В. Как определить условие остановки?

На этот вопрос немного (без каламбура!) ответить легче. Чтобы принять решение об условии остановки, нам нужно принять во внимание две вещи.

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

Заключение

Теперь я хотел бы завершить часть-I «Дерева решений с нуля». В следующей части мы напишем весь алгоритм с нуля на Python и проверим его производительность на фиктивном наборе данных.

Я надеюсь, что вы нашли этот пост в блоге проницательным. Пожалуйста, поделитесь ею со своими друзьями и семьей и подпишитесь на мой блог Keeping Up With Data Science, чтобы получать больше информативного контента о науке о данных прямо в свой почтовый ящик. Вы можете связаться со мной в Twitter и LinkedIn. Я довольно активен там, и я буду рад поговорить с вами. Пожалуйста, не стесняйтесь оставлять свои отзывы в комментариях, которые помогают мне улучшить качество моей работы. Я буду продолжать делиться большим количеством контента по мере того, как буду расти и становиться специалистом по данным. До следующего раза, Продолжайте работать и идти в ногу с наукой о данных. Удачного обучения 🙂