Узнайте, как дерево решений разбивает узлы только для минимизации функции потерь.

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

Какая функция потерь? Что ж, каждой модели машинного обучения нужна функция потерь. Функция потерь определяет разницу между прогнозами модели и фактическими данными. Альтернативным термином является ошибка в прогнозе модели. Модель дерева решений не является исключением.

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

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

Как дерево регрессии делает прогнозы

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

Мы хотим, чтобы наше дерево регрессии предсказывало целевую переменную Зарплату, которая является непрерывной величиной, отсюда и название «дерево регрессии» из двух функций, Возраста, который является непрерывным, и Пол, который является категоричным. Для зарплаты я использую от y₁ до y₇ вместо реальных чисел, чтобы подчеркнуть тот факт, что мы не должны знать зарплату других людей. Пусть sₒ={y₁, y₂, y₃, y₄, y₅, y₆, y₇} представляет все записи данных о зарплате.

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

В следующем дереве используется кортеж условия разделения (Возраст, 41, ‹) для разделения полного набора данных s₀ на два подмножества s1={y₁, y₃, y₅} и s2={y₂, y₄, y₆, y₇}. Кортеж (Возраст, 41, ‹) означает, что дерево использует условие «Возраст ‹ 41» для разделения всех точек данных, которые достигают текущего корня, который на данный момент является полным набором данных, на два непересекающихся подмножества.

Я визуализировал это разделение, поместив подмножество s1 на левую ветвь и s2 на правую ветвь. Обратите внимание, что кортеж условия разделения (Возраст, 41 год, ‹) предназначен для иллюстрации и может быть не оптимальным для примера набора данных.

Дерево регрессии делает прогнозы путем усреднения

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

Если этот человек моложе 41 года, он достигает левой ветви, т. е. подмножества s1; затем модель прогнозирует количество ŷₛ₁, которое является средним значением заработной платы в подмножестве s1:

Если этот человек старше или равен 41 году, он достигает правой ветви, т. е. подмножества s2; модель предсказывает количество ŷₛ₂, которое является средним значением заработной платы в подмножестве s2:

Другими словами, для точки данных дерево регрессии делает прогноз по:

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

Функция потерь для деревьев регрессии

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

Для подмножества s1:

Для подмножества s2:

где |s1| обозначает размер подмножества s1, то есть 3, а |s2| размер подмножества s2, т. е. 4. Нормализация ⅓ и ¼ фактически определяет размер двух подмножеств в функции потерь. Таким образом, Lₛ₁ и Lₛ₂ являются усредненными потерями на точку данных.

Тогда общие потери для всего дерева представляют собой сумму этих двух членов потерь:

Тот факт, что Lₛ₁ и Lₛ₂ усредняются по потерям в точке данных, означает, что нам не нужно ставить перед ними коэффициенты в общих потерях L для учета разницы в размерах s1 и s2. Разница в размере подмножества уже учтена нормировочной константой ⅓ и ¼.

Нахождение условия разделения дерева решений

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

В дереве регрессии на каждом ветвлении параметром модели является кортеж условия разделения, например (Возраст, 40, ‹). Алгоритм выбора кортежа для разделения дерева включает следующие три шага:

1. Определите подходящее подмножество кортежей условий разделения

Просмотр функций в данных и поиск возможных условий разделения среди всех возможных условий разделения:

  • Если функция является непрерывной, например, Возраст, посмотрите на диапазон этой функции и выберите короткий список значений разделения. Например, возраст в данных находится в диапазоне от 20 до 70, тогда краткий список значений разбиения может быть 30, 40, 50, 60. Это дает следующие четыре кортежа (Возраст, 30, ‹), (Возраст, 40, ‹), (Возраст, 50, ‹) и (Возраст, 60, ‹). Для непрерывной функции может быть бесконечное количество значений разделения, алгоритм может позволить себе выбрать только небольшое подмножество с помощью эвристики. Это подмножество может быть не оптимальным, но это компромисс между точностью модели и вычислениями.
  • Если функция является категориальной, например Пол, используйте ее значения в качестве значений разделения. Это дает два кортежа (Пол, Мужской, =), (Пол, Женский, =), которые сводятся к одному кортежу (Пол, Мужской, =) для этой двоичной функции.

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

2. Разделите данные, используя кортежи условий разделения, и оцените потери

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

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

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

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

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

Именно так дерево регрессии разбивает узлы — оно разбивает узлы, чтобы минимизировать функцию потерь, то есть среднеквадратичную потерю. Мы надеемся, что после разделения модель сможет делать лучшие прогнозы в том смысле, что прогнозы дают меньшие ошибки. Модель может это сделать, потому что она извлекает информацию из набора данных. Чтобы количественно определить, сколько информации было извлечено до и после разделения, рассчитайте потери по полному набору данных s₀, т. е.

Затем сделайте различие между ними:

Снижение дисперсии

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

Прогноз:

Потеря:

Вы поймете, что для списка чисел y₁, y₃, y₅ предсказание дерева регрессии ŷₛ₁ является средним значением этих чисел, которое мы обычно обозначаем как ȳ . А среднеквадратическая ошибкаLₛ₁ имеет ту же структуру, что и формула для вычисления дисперсии этого списка чисел:

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

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

Как дерево классификации делает прогнозы

Давайте сначала создадим набор данных для задачи классификации, поменяв местами столбцы «Пол» и «Зарплата» из предыдущего набора данных:

Здесь целевой переменной для прогнозирования является пол, который является категориальной переменной, поэтому нам нужно дерево классификации. Две функции - это возраст и зарплата.

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

Это дерево должно классифицировать точку данных в классе Женский или в классе Мужской. Предположим, что это дерево по-прежнему использует условие Возраст ‹ 41 для разбиения набора данных s₀ на s1={y₁F, y₃F, y₅M} и s2={y₂M, y₄F, у₆М, у₇F}. Я прикрепил символ пола «F» или «M» к каждой точке данных, например «y1F», чтобы сделать пол каждой точки данных, достигающей листового узла, более ясным.

Таким образом, после разделения ⅔ точек данных, поступивших в левый конечный узел, являются женскими, что обозначается P(F)=⅔, что говорит о вероятности появления женских данных. точек в этом узле составляет ⅔. Аналогично, для мужчин это P(M)=⅓.

Деревья классификации делают прогнозы большинством голосов

Нам нужен механизм прогнозирования, отличный от усреднения (как в случае с деревом регрессии), потому что ⅔ женщины плюс ⅓ мужчины — это не вещь, несмотря на активное ЛГБТ-движение в последние годы.

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

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

Функция потерь для деревьев классификации

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

  1. Наше дерево предсказывает женщину для левого узла, это предсказание верно на ⅔ времени и неверно ⅓ времени. Другими словами, если распределение различных классов в узел менее однороден, прогноз лучше.
  2. Он предсказывает Male для правильного узла, этот прогноз верен только в половине случаев. Другими словами, если распределение разных классов в узле более равномерное, прогноз хуже.

Поэтому нам нужна мера единообразия меток классов в наборе точек данных. Существует множество мер. Обычный выбор - энтропия:

где сумма указана по всем классам c, в нашем случае Female и Male. P(c) – это вероятность появления класса c. А log(P(c)) — это логарифм вероятности этого события.

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

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

Для левого листового узла:

Для правого листового узла:

Мы видим, что потери для левого конечного узла Hₛ₁=0,637 действительно меньше, чем потери для правого конечного узла Hₛ₂=0,693, что соответствует прогнозу модели. лучше для точек данных в левом узле.

Теперь, как и в случае с деревом регрессии, нам нужно объединить Hₛ₁ и Hₛ₂ вместе, чтобы представить общие потери для всего дерева.

В случае дерева регрессии мы добавили Lₛ₁ и Lₛ₂ вместе, потому что Lₛ₁ и Lₛ₂ представляют собой точки данных потерь с нормализованными размерами различных подмножеств s1 и s2. Но в случае дерева классификации это не относится к приведенным выше условиям потерь на основе энтропии. Если вы посмотрите на приведенное выше определение Hₛ₁ и Hₛ₂, размер подмножества s1 и s2 не упоминается.

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

Чтобы определить размер подмножества данных, мы определяем общую потерю H как взвешенную сумму Hₛ₁ и Hₛ₂, с весами, принадлежащими пропорциям подмножества данных:

Нахождение условия разделения для дерева классификации

С функцией потерь H, определенной для дерева классификации, мы можем применить тот же алгоритм, что и для дерева регрессии, для разделения узлов. Нам просто нужно использовать новую потерю H для классификации вместо потери L для регрессии.

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

Как удивительно!

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

Как и в случае с деревом регрессии, вы можете измерить информацию, извлеченную из данных между и после разделения, вычислив потери в корневом узле Hₛ₀, который находится до разделения, и сделать разность с H, то есть H-Hₛ₀.

Получение информации

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

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

Выводы

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