В контексте обучения с учителем дерево решений - это дерево для прогнозирования выходных данных для заданных входных данных. Мы начинаем с корня дерева и задаем конкретный вопрос о вводе. В зависимости от ответа спускаемся к тому или иному из его потомков. Ребенок, которого мы посещаем, является корнем другого дерева. Итак, повторяем процесс, т.е. задаем здесь другой вопрос. В конце концов, мы достигаем листа, то есть узла без дочерних элементов. Этот узел содержит окончательный ответ, который мы выводим и останавливаем.
Этот процесс изображен ниже.
Давайте посмотрим на пример.
В машинном обучении деревья решений представляют интерес, потому что они могут быть изучены автоматически из помеченных данных. Помеченный набор данных - это набор пар (x, y). Здесь x - входной вектор, а y - целевой выходной.
Ниже представлен помеченный набор данных для нашего примера.
Weather Temperature Action Sunny Warm Go to park Sunny Cold Stay at home Sunny Hot Stay at home Rainy Warm Stay at home Rainy Cold Stay at home
Почему деревья решений?
Изученные деревья решений часто дают хорошие предикторы. Поскольку они работают в древовидной структуре, они могут фиксировать взаимодействия между переменными-предикторами. (Это будет регистрироваться, когда мы увидим больше примеров.)
Дополнительным преимуществом является то, что изученные модели прозрачны. То есть мы можем изучить их и сделать выводы, как они предсказывают. Напротив, нейронные сети непрозрачны. Глубокие тем более.
Конечно, когда точность прогнозов имеет первостепенное значение, можно мириться с непрозрачностью. Деревья принятия решений охватывают и это. Ансамбли деревьев решений (в частности, случайный лес) обладают высочайшей точностью.
Так что в любом случае полезно узнать об обучении на основе дерева решений.
Обучение деревьям решений
Ладно, перейдем к делу. Мы сосредоточимся на бинарной классификации, поскольку этого достаточно, чтобы выявить ключевые идеи в обучении. Для полноты картины мы также обсудим, как преобразовать двоичный классификатор в мультиклассовый классификатор или в регрессор.
Педагогический подход, который мы используем ниже, отражает процесс индукции. Мы начнем с изучения базовых случаев, а затем перейдем к более сложным.
Базовый пример обучения 1. Одночисловой предиктор
Рассмотрим следующую проблему. Вход - температура. Результатом является субъективная оценка отдельным человеком или коллективом того, является ли температура ГОРЯЧЕЙ или НЕТ.
Давайте изобразим наши помеченные данные следующим образом: - обозначает НЕ, а + обозначает HOT. Температуры указаны в порядке горизонтальной линии.
- - - - - + + + + +
Эти данные линейно разделимы. Все -и идут перед +-ми.
В общем, это не обязательно, как показано ниже.
- - - - - + - + - - - + - + + - + + - + + + + + + + +
Возможно, ярлыки основаны на мнениях нескольких людей. Могут быть некоторые разногласия, особенно рядом с границей, отделяющей большую часть минусов от большинства плюсов.
Наша задача - узнать порог, который дает наилучшее правило принятия решения. Что мы подразумеваем под «правилом принятия решения». Для любого порога T мы определяем это как
IF temperature < T return NOT ELSE return HOT
Точность этого решающего правила на обучающей выборке зависит от T.
Цель обучения - найти T, который дает нам наиболее точное правило принятия решения. Такой T называется оптимальным разбиением.
Фактически, мы только что видели наш первый пример изучения дерева решений. Дерево решений изображено ниже.
Базовый сценарий обучения 2: единый категориальный предиктор
Считайте сезон предиктором, а солнечно или дождливым - двоичным исходом. Допустим, у нас есть тренировочный набор ежедневных записей. Для каждого дня, был ли день солнечным или дождливым, записывается как результат, который необходимо предсказать. Сезон, в который был день, записывается как предсказатель.
Эта проблема проще, чем базовый случай обучения 1. Предиктор имеет только несколько значений. Четыре сезона. Оптимального раскола не нужно выучить. Как будто все, что нам нужно сделать, это заполнить «предсказывающие» части оператора case.
case season when summer: Predict sunny when winter: Predict rainy when fall: ?? when spring: ??
Тем не менее, у нас действительно есть проблема «шумных этикеток». Это просто означает, что результат не может быть определен с уверенностью. Летом бывают дождливые дни.
Решить эту проблему несложно. На листе дерева мы храним распределение по количеству двух результатов, которые мы наблюдали в обучающей выборке. Это изображено ниже.
Скажем, сейчас лето. Соответствующий лист показывает 80: солнечно и 5: дождливо. Таким образом, мы бы предсказали солнечную погоду с уверенностью 80/85.
Общий пример 1: несколько числовых предикторов
Неудивительно, что это более сложно.
Мы начинаем с наложения упрощающего ограничения, согласно которому решающее правило в любом узле дерева проверяет только одно измерение входных данных.
Назовите наши переменные-предикторы X 1,…, X n. Это означает, что в корне дерева мы можем проверить ровно одно из них. Вопрос в том, какой именно?
Мы отвечаем на это следующим образом. Для каждой из n переменных-предикторов мы рассматриваем проблему прогнозирования результата исключительно на основе этой переменной-предиктора. Это дает нам решение n одномерных задач прогнозирования. Мы вычисляем оптимальные разбиения T 1,…, T n для них способом, описанным в первом базовом случае. При этом мы также записываем точность обучающего набора, которую обеспечивает каждое из этих разбиений.
В корне дерева мы проверяем тот X i, оптимальное разбиение которого T i дает наиболее точный (одномерный) предиктор. Это изображено ниже.
Итак, теперь нам нужно повторить этот процесс для двух потомков A и B этого корня. Для этого сначала мы выводим обучающие наборы для A и B следующим образом. Обучающий набор для A (B) - это ограничение родительского обучающего набора теми экземплярами, в которых X i меньше, чем T (›= T ). Давайте также удалим измерение X i из каждой обучающей выборки.
Теперь у нас есть два экземпляра одной и той же задачи обучения. Итак, мы возвращаемся.
И так продолжается до тех пор, пока в нашем обучающем наборе нет предикторов. Только бинарные исходы. Узел, к которому прикреплен такой обучающий набор, является листом. Нечего тестировать. Данные на листе - это пропорции двух результатов в обучающей выборке. Этого достаточно, чтобы предсказать как лучший результат на листе, так и уверенность в нем.
Общий случай обучения 2: несколько категориальных предикторов
Здесь у нас есть n категориальных переменных-предикторов X 1,…, X n. Как и для нескольких числовых предикторов, мы выводим из этого n задач одномерного прогнозирования, решаем каждую из них и вычисляем их точность, чтобы определить наиболее точный одномерный классификатор. Переменная-предиктор этого классификатора - это та, которую мы помещаем в корень дерева решений.
Затем мы настраиваем обучающие наборы для дочерних элементов этого корня.
Для каждого значения v переменной-предиктора X i существует один дочерний элемент. Обучающий набор в этом дочернем элементе является ограничением обучающего набора корневого каталога теми экземплярами, в которых X i равно v. Мы также удаляем атрибут X i из этого обучающего набора.
Теперь мы выполняем рекурсию, как и с несколькими числовыми предикторами.
Пример
Давайте проиллюстрируем это обучение на слегка улучшенной версии нашего первого примера ниже. Мы назвали эти два результата O и I, чтобы обозначить их на улице и в помещении соответственно. Мы также подсчитали эти два результата. Строка со счетом o для O и i для I обозначает o экземпляры с меткой O и i экземпляры с меткой I.
Weather Temperature Action Sunny Warm O (50), I (10) Sunny Cold O (10), I (40) Sunny Hot O (5), I (30) Rainy Warm O (10), I (25) Rainy Cold O (1), I (35) Rainy Hot O (2), I(7)
Итак, какую переменную-предиктор мы должны проверить в корне дерева? Что ж, погода дождливая предсказывает меня. (То есть мы остаемся дома.) Солнечная погода сама по себе не предсказуема. Теперь рассмотрим температуру. Неудивительно, что температура высокая или низкая также предсказывает I.
Какая переменная победит? Не ясно. Давайте отдадим предпочтение температуре, поскольку два из трех ее значений предсказывают результат. (Это субъективное предпочтение. Не принимайте это слишком буквально.)
Теперь рекурсивно.
Итоговое дерево результатов показано ниже.
Смешанные переменные-предикторы
Что, если у нас есть как числовые, так и категориальные переменные-предикторы? Разумный подход - игнорировать разницу. Чтобы выяснить, какую переменную проверять на узле, просто определите, как и раньше, какая из доступных переменных-предикторов лучше всего предсказывает результат. Для числового предиктора это потребует в первую очередь поиска оптимального разделения.
Алгоритм обучения: абстрагирование от ключевых операций
Давайте абстрагируемся от ключевых операций в нашем алгоритме обучения. Эти абстракции помогут нам описать его расширение на случай мультиклассов и случай регрессии.
Ключевые операции:
- Оцените, насколько точно любая переменная предсказывает ответ.
- Получите дочерние обучающие наборы из родительских.
Универсальный кейс
Что, если наша переменная ответа имеет более двух результатов? В качестве примера скажем, что к проблеме принятия решения о том, что делать в зависимости от погоды и температуры, мы добавляем еще один вариант: пойти в торговый центр.
Принципиально ничего не меняется. Добавление большего количества результатов к переменной ответа не влияет на нашу способность выполнять операцию 1. (Однако метрика оценки может отличаться.) Операция 2 также не затрагивается, поскольку она даже не учитывает ответ.
Регрессия
Что, если наша переменная ответа числовая? Вот один пример. Прогнозируйте высокую температуру дня по месяцу года и широте.
Можем ли мы по-прежнему оценивать точность, с которой любой единственный предиктор предсказывает ответ? Возникает вопрос. Как нам даже предсказать числовой ответ, если какая-либо из переменных-предикторов категориальна?
Начнем с обсуждения. Сначала смотрим на
Базовый случай 1. Одна категориальная переменная-предиктор
Для каждого значения этого предиктора мы можем записать значения переменной ответа, которые мы видим в обучающем наборе. Разумный прогноз - это среднее значение этих ответов.
Запишем это формально. Пусть X обозначает категориальный предиктор, а y - числовой ответ. Наш прогноз y, когда X равен v, является оценкой ожидаемого значения в этой ситуации, т. Е. E [y | X = v].
Давайте посмотрим на числовой пример. Рассмотрим обучающий набор
X A A B B y 1 2 4 5
Наши прогнозируемые значения y для X = A и X = B составляют 1,5 и 4,5 соответственно.
Базовый случай 2. Одночисловая переменная-предиктор
Для любого конкретного split T числовой предиктор работает как логическая категориальная переменная. Таким образом, предыдущий раздел также рассматривает этот случай.
За исключением того, что нам нужен дополнительный цикл для оценки различных кандидатов T и выбора того, который работает лучше всего. Говоря о том, что «работает лучше всего», мы еще не рассмотрели это. Сделаем это ниже.
Оценочный показатель
И ответ, и его прогнозы являются числовыми. Нам просто нужна метрика, которая количественно определяет, насколько близок к целевому отклику предсказанный. Разумный показатель может быть получен из суммы квадратов расхождений между целевым ответом и прогнозируемым ответом.
Общий случай
Мы рассмотрели операцию 1, то есть оценку качества переменной-предиктора для числового ответа. Операция 2, получение детских обучающих наборов из родительских, не требует изменений. Как отмечалось ранее, этот процесс вывода вообще не использует ответ.
Прогнозируемый ответ
Как и в случае классификации, обучающий набор, прикрепленный к листу, не имеет переменных-предикторов, а только набор результатов. Как отмечалось ранее, разумное предсказание на листе будет средним из этих результатов. Вот что мы должны делать, когда дойдем до листа.
Моделирование компромиссов
Рассмотрим наш пример регрессии: спрогнозируйте высокую температуру дня по месяцу года и широте.
Рассмотрим месяц в году. Мы могли бы рассматривать его как категориальный предиктор со значениями январь, февраль, март,… или как числовой предиктор со значениями 1 , 2, 3,…
Какие компромиссы? Рассмотрение его как числового предиктора позволяет нам увеличивать порядок в месяцах. Февраль близок к январю и далеко от августа. Тем не менее, как нам запечатлеть, что декабрь и январь являются соседними месяцами? 12 и 1, поскольку числа сильно различаются.
Возможно, что еще более важно, обучение дерева решений с числовым предиктором работает только через разбиения. Это означало бы, что узел на дереве, который проверяет эту переменную, может принимать только двоичные решения. Напротив, использование категориального предиктора дает нам 12 детей. В принципе, это позволяет принимать более тонкие решения.
Теперь рассмотрим широту. Мы можем рассматривать его как числовой предсказатель. Или как категориальный, вызванный определенным биннингом, например в единицах + или - 10 градусов. Последний позволяет принимать более детальные решения в дереве решений.
Резюме
В этом посте мы описали обучающие деревья решений с интуицией, примерами и картинками. Мы рассмотрели оба дерева решений для задач классификации и регрессии. Мы также рассмотрели как числовые, так и категориальные переменные-предикторы.
Дополнительная информация
