«Адвент-календарь» машинного обучения. День 7: Классификатор дерева решений

Как классификатор дерева решений выбирает свое первое разбиение

Делиться

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

Сегодня, в седьмой день «Адвент-календаря» по машинному обучению, мы продолжаем тот же подход, но с классификатором дерева решений — классификационным аналогом вчерашней модели.

Быстрый интуитивный эксперимент с двумя простыми наборами данных

Начнем с очень небольшого пробного набора данных, который я сгенерировал, с одной числовой характеристикой и одной целевой переменной с двумя классами: 0 и 1.

Идея состоит в том, чтобы разбить набор данных на две части по одному правилу. Но вопрос в том: каким должно быть это правило? Какой критерий определяет, какое разделение лучше?

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

А визуально это будет 8 или 12 , да?

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

Если рассуждать интуитивно:

• С разделением на 8 :
  • левая сторона: нет ошибочной классификации
  • правая сторона: одна ошибочная классификация
• С разделением на 12 :
  • правая сторона: нет ошибочной классификации
  • левая сторона: две ошибочные классификации

Так что, очевидно, что разделение на 8 кажется более выгодным.

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

Здесь я обозначаю их 0, 1, 3 и располагаю их вертикально.

Но будьте осторожны: эти числа — всего лишь названия категорий , а не числовые значения. Их не следует интерпретировать как «упорядоченные».

Поэтому интуиция всегда такова: насколько однороден каждый регион после разделения?

Но визуально определить наилучший вариант сложнее.

Теперь нам нужен математический способ выразить эту идею.

Это как раз тема следующей главы.

Мера примеси как критерий разделения

В регрессоре дерева решений мы уже знаем:

• Прогноз для региона представляет собой среднее значение целевого показателя.
• Качество разделения измеряется с помощью MSE .

В классификаторе дерева решений:

• Прогноз для региона — это класс большинства региона.
• Качество разделения измеряется мерой примеси : коэффициентом Джини или энтропией .

Оба индекса входят в стандартную комплектацию учебников и доступны в scikit-learn. По умолчанию используется индекс Джини.

НО что же такое эта мера примеси на самом деле?

Если посмотреть на кривые Джини и энтропии , то они обе ведут себя одинаково:

• Они равны 0, когда узел чистый (все образцы имеют один и тот же класс).
• Они достигают своего максимума , когда классы равномерно смешаны (50 процентов на 50 процентов).
• Кривая гладкая , симметричная и увеличивается с беспорядком.

Это существенное свойство любой меры примеси :

Уровень загрязнения низок, когда группы чистые, и высок, когда группы смешанные.

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

Разделить с одной непрерывной функцией

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

Список всех возможных разделений

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

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

Возьмем разделенное значение, например, x = 5,5 .

Мы разделяем набор данных на две области:

• Регион L: x < 5,5
• Регион R: x ≥ 5,5

Для каждого региона:

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

Выберите разделение с наименьшим содержанием примесей

Как в случае с регрессором:

• Перечислите все возможные разделения
• Вычислить примеси для каждого
• Оптимальным считается разделение с минимальным количеством примесей.

Синтетическая таблица всех сплитов

Чтобы сделать все автоматически в Excel,
мы организуем все расчеты в одной таблице , где:

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

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

Многоклассовая классификация

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

В структуре алгоритма ничего не меняется:

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

Только формула примеси Джини становится немного длиннее.

Примесь Джини с тремя классами

Если область содержит пропорции p1, p2, p3

для трех классов примесь Джини составляет:

Та же идея, что и раньше:
регион считается «чистым», когда доминирует один класс,
и примесь становится больше, когда классы смешиваются.

Левый и правый регионы

Для каждого разделения:

• Регион L содержит некоторые наблюдения классов 1, 2 и 3.
• Регион R содержит оставшиеся наблюдения

Для каждого региона:

1. подсчитайте, сколько баллов принадлежит каждому классу
2. вычислить пропорции p1,p2,p3
3. вычислить примесь Джини, используя формулу выше

Все точно так же, как и в двоичном случае, только с одним дополнительным членом.

Сводная таблица для 3-классового разделения

Как и прежде, мы собираем все вычисления в одну таблицу:

• каждая строка — это одно возможное разделение
• мы считаем класс 1, класс 2, класс 3 слева
• мы считаем класс 1, класс 2, класс 3 справа
• мы вычисляем Джини (слева), Джини (справа) и взвешенный Джини

Дерево решений выбирает разделение с наименьшим взвешенным значением примеси .

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

Насколько на самом деле различаются показатели примесей?

Мы всегда упоминаем в качестве критериев коэффициент Джини или энтропию, но действительно ли они различаются ? Глядя на математические формулы, некоторые могут сказать:

Ответ – не так уж и много.

Теоретически, почти во всех практических ситуациях:

• Джини и Энтропия выбирают одно и то же разделение
• Структура дерева почти идентична
• Прогнозы те же.

Почему?

Потому что их кривые выглядят чрезвычайно похожими.

Они оба достигают пика при 50-процентном смешивании и падают до нуля при чистоте.

Единственное отличие — это форма кривой:

• Функция Джини является квадратичной . Она наказывает за неправильную классификацию более линейно.
• Энтропия — логарифмическая функция, поэтому она немного сильнее штрафует неопределенность вблизи 0,5.

Но на практике разница невелика, и это можно сделать в Excel!

Другие меры по измерению примесей?

Другой естественный вопрос: можно ли придумать/использовать другие меры?

Да, вы можете придумать свою собственную функцию, если:

• Это 0, когда узел чистый.
• Максимально , когда классы смешанные.
• Он плавно и строго увеличивается в «беспорядке»

Например: Примесь = 4*p0*p1

Это ещё один допустимый показатель примеси. И он фактически равен индексу Джини , умноженному на константу, когда имеется всего два класса.

Итак, снова, это даёт те же самые расщепления . Если вы не уверены, вы можете

Вот еще несколько мер, которые можно использовать.

Упражнения в Excel

Тесты с другими параметрами и характеристиками

После создания первого разделения вы можете расширить свой файл:

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

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

Реализации правил для набора данных о выживании на «Титанике»

Естественным последующим упражнением является воссоздание правил принятия решений для знаменитого набора данных о выживании на «Титанике» ( CC0 / Public Domain ).

Во-первых, мы можем начать только с двух характеристик: пола и возраста .

Реализация правил в Excel — долгий и немного утомительный процесс, но в этом-то и суть: он позволяет вам понять, как на самом деле выглядят правила принятия решений.

Они представляют собой не что иное, как последовательность операторов IF/ELSE , повторяющихся снова и снова.

Вот истинная природа дерева решений: простые правила, наложенные друг на друга.

Заключение

Реализация классификатора дерева решений в Excel на удивление доступна.

С помощью нескольких формул вы раскроете суть алгоритма:

• список возможных разделений
• вычислить примеси
• выбрать самый чистый сплит

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

И следите за новостями завтра, День 8 !

Источник: towardsdatascience.com