Понимание классификатора дерева решений

Концептуально на примере с использованием алгоритма ID3

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

Классификацию можно определить как задачу изучения целевой функции f, которая отображает каждый набор атрибутов x к одному из предопределенных ярлыков y.

Примеры:

• Отнесение новости к одной из предопределенных категорий.
• Обнаружение спама в сообщениях электронной почты на основе заголовка и содержимого сообщения
• Классификация клеток как злокачественных или доброкачественных на основании результатов МРТ.
• Классификация галактик по их форме

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

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

• корневой узел, у которого нет входящих ребер и ноль или более исходящих ребер.
• Внутренние узлы, каждый из которых имеет ровно одно входящее ребро и два или более исходящих ребра.
• Листовые или оконечные узлы, каждый из которых имеет ровно одно входящее ребро и не имеет исходящих ребер.

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

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

Когда мы исследуем этот набор данных, мы видим:

1. Атрибут Владелец дома является двоичным по своей природе и состоит только из Да и Нет.
2. Атрибут Семейное положение является категориальным по своему характеру и состоит из холост, женат или разведен.
3. Атрибут Годовой доход является непрерывным по своей природе и состоит из числовых значений.
4. Атрибут Заемщик по умолчанию является двоичным по своей природе, состоящим только из Да и Нет, и является нашим целевым атрибутом или меткой класса.

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

• Исходное дерево содержит единственный узел с меткой класса Заемщик по умолчанию = Нет
• Дерево необходимо уточнить, так как этот корневой узел содержит записи из обоих классов.
• Впоследствии записи делятся в зависимости от результатов выполнения условия Домовладелец.
• Это делается рекурсивно
• Из приведенного выше набора данных все заемщики, являющиеся домовладельцами (домовладелец = Да), успешно погасили свои ссуды. Тогда левый дочерний элемент корневого узла будет помечен как Заемщик по умолчанию = Нет.
• Для правильного потомка нам нужно применять рекурсивный шаг, пока все записи не будут принадлежать одному классу.

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

Проблемы проектирования индукции дерева решений

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

→ Как следует разделять записи о тренировках?

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

→ Как следует остановить процедуру разделения?

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

Методы выражения условий проверки атрибутов

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

• Двоичные атрибуты: два возможных результата.

• Номинальные атрибуты:
  а) Многостороннее разбиение
  б) Двоичное разбиение.

• Порядковые атрибуты:
  а) Многостороннее разбиение
  б) Двоичное разбиение.

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

• Непрерывные атрибуты: условие теста может быть выражено как сравнительный тест (A ‹v) или (A≥v) с бинарными результатами или как диапазон с результатами в форме v (i) ≤ A ≤ v (i + 1) для i = 1,2,3… k
  a) Для двоичного случая алгоритм должен учитывать все возможные позиции разбиения v и выбирать ту, которая дает лучшее разбиение.
  б) Для многостороннего разделения алгоритм должен учитывать все возможные диапазоны непрерывных значений.

Меры по выбору лучшего сплита

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

Пример: узел с распределением классов (0, 1) имеет нулевую примесь, тогда как узел с равномерным распределением классов (0,5, 0,5) имеет самую высокую степень примеси.

Меры по содержанию примесей

где,

D = обучающая выборка, где v принадлежит D и является узлом дерева,

L = {y1, y2,…, yk} набор меток / классов

Давайте разберемся с указанными выше мерами примесей на некоторых примерах:

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

Для узла v, разбитого по значениям атрибутов a, принадлежащих узлу A, на дочерние элементы (v, a), усиление разделения составляет:

Примечание: Inf Gain - это информационное усиление.

Коэффициент усиления

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

где,

ID3 алгоритм

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

Вместо того, чтобы набирать длинные уравнения, я использую картинки и объясню все сокращения, которые я использовал.

На картинке выше Д = Да и Н = Нет.

На картинке выше W = T и W = F - True и False значения атрибута Windy.

На изображениях выше O = S, O = O, O = R - это солнечные, облачные и дождливые значения атрибута Outlook.

На изображении выше Temp. = Температура и T = H, T = M, T = C - высокие, мягкие и холодные значения атрибута Температура.

На картинке выше H = H, H = N - это высокие и нормальные значения атрибута Влажность.

Поскольку выгода для Outlook наиболее высока, Outlook является нашим корневым узлом.

Теперь расчет на первом дочернем узле с Outlook = Sunny

Поскольку получение информации для Outlook = Sunny, Humidity является самым высоким, он становится нашим первым дочерним узлом.

Для второго дочернего узла с Outlook в корневом узле мы рассматривали пару Outlook = Overcast и обнаружили, что, когда Outlook = Overcast, Play = Yes, то напрямую ведет к конечному узлу Yes.

Для третьего дочернего узла с Outlook в корневом узле мы рассматриваем пару Outlook = Rainy

Поскольку получение информации для Outlook = Rainy, Windy является самым высоким, он становится нашим третьим дочерним узлом.

Спускаясь дальше, углубляясь в первый дочерний узел, где Outlook = Sunny и Humidity, мы видим, что разделение на влажность является чистым, и, следовательно, нам не нужно рассчитывать прирост информации и напрямую помещать листовые узлы.

То же самое происходит с Outlook = Rainy и Windy, мы видим, что разделение на Windy чистое.

Имеется в виду

• когда Outlook = Солнечно и Влажность = Высокая, целевой атрибут Play = Нет.
• когда Outlook = Солнечно и Влажность = Нормальный, целевой атрибут Play = Да
• когда Outlook = Rainy и Windy = True, целевой атрибут Play = No
• когда Outlook = Rainy и Windy = False, целевой атрибут Play = Yes

Окончательное дерево решений выглядит так:

Я раздаю бесплатную электронную книгу о согласованности. Получите бесплатную электронную книгу здесь .

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

Кроме того, я написал пост о реализации указанного Дерева решений с нуля с использованием Python3 и XML без использования какой-либо библиотеки машинного обучения.

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

Вот список моих рассказов: