Деревья решений: пошаговый подход к созданию DT

Деревья решений: пошаговый подход к созданию DT

Вступление

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

Контекст

В этой статье мы обсудим следующие темы

1. Что такое деревья решений в целом
2. Типы деревьев решений.
3. Алгоритмы, используемые для построения деревьев решений.
4. Пошаговый процесс построения дерева решений.

Что такое деревья принятия решений?

Картинка выше - это простое дерево решений. Если человек не вегетарианец, то он ест курицу (скорее всего), в противном случае он не ест курицу. Дерево решений, как правило, задает вопрос и классифицирует человека на основе ответа. Это дерево решений основано на вопросе «да / нет». Так же просто построить дерево решений на основе числовых данных.

Если человек едет со скоростью более 80 км / ч, мы можем считать это превышением скорости, иначе - нет.

Вот еще одно простое дерево решений. Это дерево решений основано на ранжированных данных, где 1 означает, что скорость слишком высока, а 2 соответствует гораздо меньшей скорости. Если человек превышает 1 ранг, значит, он / она сильно разгоняется. Если человек выше 2-го уровня скорости, но ниже 1-го уровня скорости, он / она превышает скорость, но не так сильно. Если у человека уровень скорости ниже 2, значит, он / она едет в пределах допустимой скорости.

Классификация в дереве решений может быть как категориальной, так и числовой.

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

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

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

Построение дерева решений

Существует несколько алгоритмов построения дерева решений.

1. CART-классификация и деревья регрессии
2. ID3-Итерационный дихотомайзер 3
3. C4.5
4. Автоматическое обнаружение взаимодействия CHAID-Chi-squared

Мы будем обсуждать только алгоритмы CART и ID3, поскольку они наиболее часто используются.

КОРЗИНА

CART - это алгоритм DT, который создает двоичные классификационные или регрессионные деревья, в зависимости от того, является ли зависимая (или целевая) переменная категориальной или числовой соответственно. . Он обрабатывает данные в их необработанном виде (без предварительной обработки) и может использовать одни и те же переменные более одного раза в разных частях одного и того же DT, что может выявить сложные взаимозависимости между наборами переменных.

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

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

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

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

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

Показатель, используемый в алгоритме CART для измерения примесей, - это показатель примеси Джини. Вычислить примесь Джини очень просто. Начнем с расчета примеси Джини для боли в груди.

Для левого листа

Gini impurity = 1 - (probability of ‘yes’)² - (probability of ‘no’)²
              = 1 - (105/105+39)² - (39/105+39)²
Gini impurity = 0.395

Аналогичным образом рассчитайте примесь Джини для правого листового узла.

Gini impurity = 1 - (probability of ‘yes’)² - (probability of ‘no’)²
              = 1 - (34/34+125)² - (125/34+125)²
Gini impurity = 0.336

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

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

Gini impurity = (144/144+159)*0.395 + (159/144+159)*0.336
              = 0.364

Аналогичным образом общая примесь Джини для «хорошего кровообращения» и «закупоренных артерий» рассчитывается как

Gini impurity for ‘good blood circulation’ = 0.360
Gini impurity for ‘blocked arteries’ = 0.381

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

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

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

Примесь Джини оказалась равной 0,3. Затем мы делаем то же самое с «закупоренными артериями».

Примесь Джини оказалась равной 0,29. Поскольку «заблокированные артерии» имеют наименьшую примесь Джини, мы будем использовать ее в левом узле на рисунке 10 для дальнейшего разделения пациентов.

Все, что у нас осталось, это «боль в груди», поэтому мы увидим, насколько хорошо она разделяет 49 пациентов в левом узле (24 с сердечным заболеванием и 25 без сердечного заболевания).

Мы видим, что боль в груди хорошо разделяет пациентов.

Итак, это последние листовые узлы левой части этой ветви дерева. Теперь давайте посмотрим, что происходит, когда мы пытаемся отделить узел, имея 13/102 пациентов, использующих «боль в груди». Обратите внимание, что почти 90% людей в этом узле не страдают сердечными заболеваниями.

Примесь Джини этого разделения составляет 0,29. Но примесь Джини для родительского узла перед использованием боли в груди для разделения пациентов

Gini impurity = 1 - (probability of yes)² - (probability of no)²
              = 1 - (13/13+102)² - (102/13+102)²
Gini impurity = 0.2

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

На этом этапе мы проработали всю левую часть дерева. Те же шаги необходимо выполнить, чтобы выработать правую часть дерева.

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

ID3

Процесс построения дерева решений с использованием алгоритма ID3 почти аналогичен использованию алгоритма CART, за исключением метода, используемого для измерения чистоты / примеси. Метрика, используемая в алгоритме ID3 для измерения чистоты, называется Энтропия.

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

Энтропия всегда дает число от 0 до 1. Таким образом, если подмножество, сформированное после разделения с использованием атрибута, является чистым, то нам потребуются нулевые биты, чтобы определить, является ли оно положительным или отрицательным. Если сформированное подмножество имеет равный номер. положительных и отрицательных элементов тогда нет. необходимых бит будет 1.

На приведенном выше графике показана связь между энтропией и вероятностью положительного класса. Как мы видим, энтропия достигает 1, что является максимальным значением, когда есть равные шансы, что элемент будет либо положительным, либо отрицательным. Энтропия минимальна, когда p (+) стремится к нулю (символ x отрицателен) или 1 (символ x положителен).

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

Рассмотрим эту часть проблемы, которую мы обсуждали выше для алгоритма CART. Нам нужно решить, какой атрибут из chest pain и blocked arteries использовать для разделения левого узла, содержащего 164 пациента (37 с сердечными заболеваниями и 127 без сердечных заболеваний). Мы можем вычислить энтропию перед расщеплением как

Посмотрим, насколько хорошо chest pain разделяет пациентов

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

Аналогично энтропия для правого узла

Общий прирост энтропии после разделения с использованием chest pain

Это означает, что если в текущей ситуации мы выберем chest pain для разделения пациентов, мы получим 0,098 бита с уверенностью в отношении пациента, имеющего или не имеющего сердечное заболевание. Проделав то же самое для blocked arteries, полученное усиление составило 0,117. Поскольку разделение с помощью blocked arteries дает нам больше уверенности, он будет выбран. Мы можем повторить ту же процедуру для всех узлов, чтобы построить DT на основе алгоритма ID3.

Примечание. Решение о том, разделить ли узел на 2 или объявить его листовым узлом, можно принять, установив минимальный порог для требуемого значения усиления. Если полученное усиление выше порогового значения, мы можем разделить узел, в противном случае оставить его как листовой узел.

Резюме

Ниже приведены выводы из этой статьи.

1. Общая концепция деревьев решений.
2. Основные типы деревьев решений.
3. Различные алгоритмы построения дерева решений.
4. Построение дерева решений с использованием алгоритма CART.
5. Построение дерева решений с использованием алгоритма ID3.

использованная литература

1. Обратитесь к этому плейлисту на YouTube, чтобы узнать больше о построении деревьев решений с использованием алгоритма CART.

2. Обратитесь к этому плейлисту на YouTube, чтобы узнать больше о построении деревьев решений с использованием алгоритма ID3.

PS: - Скоро я опубликую еще одну статью о деревьях регрессии и случайных лесах. Следите за обновлениями :)

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