решающее дерево в машинном обучении это
Руководство к использованию деревьев решений в машинном обучении и науке о данных
Feb 6, 2019 · 7 min read
Деревья решений являются классом очень эффективной модели машинного обучения, позволяющей получить высокую точность в решении многих задач, сохраняя при этом высокий уровень интерпретации. Четкость представления информации делает деревья решений особенными среди других моделей машинного обучения. Освоенные деревом решений «знания» напрямую формируются в иерархическую структуру, которая хранит и представляет знания в понятном даже для неспециалистов виде.
Деревья решений в реальной жизни
Вы скорее всего уже использовали деревья реше н ий для того, чтобы сделать какой-нибудь выбор в своей жизни. Например, нужно решить, чем вы займетесь на предстоящих выходных. Итог может зависеть от того, хотите ли вы пойти куда-то с друзьями или провести выходные в одиночестве. В обоих случаях решение зависит также и от погоды. Если она будет солнечной и друзья будут свободны, вы можете сходить поиграть в футбол. Если пойдет дождь, вы пойдете в кино. Если друзья будут заняты, то вы останетесь дома играть в видео игры, даже несмотря на хорошую погоду.
Этот пример хорошо демонстрирует дерево решений в реальной жизни. Мы построили дерево и смоделировали ряд последовательных, иерархических решений, которые, в конечном итоге, приводят к некоторому результату. Обратите внимание, что мы выбрали максимально общие варианты решения, чтобы дерево было маленьким. Дерево будет просто огромным, если мы установить много возможных вариантов погоды, например: 25 градусов, солнечно; 25 градусов, дождливо; 26 градусов, солнечно; 26 градусов, дождливо; 27 градусов, солнечно; 27 градусов, дождливо и т.д. Конкретная температура не важна. Нам нужно лишь знать, будет ли погода хорошей или нет.
В машинном обучении концепция деревьев решений такая же. Нам нужно построить дерево с набором иерархических решений, которые в конце приведут нас к результату, то есть к нашей классификации или прогнозу регрессии. Решения выбираются таким образом, чтобы дерево было максимально маленьким, но при этом сохраняло точность классификации или регрессии.
Деревья решений в машинном обучении
Модели дерева решений строятся в два этапа: индукция и отсечение. Индукция — это то, где мы строим дерево, то есть устанавливаем все границы иерархического решения, основываясь на наших данных. Из-за своего характера обучаемые деревья решений могут быть подвержены значительному переобучению. Отсечение — это процесс удаления ненужной структуры из дерева решений, эффективно упрощая его для понимания и избежания переобучения.
Индукция
Индукция дерева решений проходит 4 главных этапа построения:
Первый этап простой. Просто соберите свой набор данных!
На втором этапе выбор признака и определенного разбиения обычно осуществляется с помощью жадного алгоритма для уменьшения функции стоимости. Если подумать, разбиение при построении дерева решений эквивалентно разбиению признакового пространства. Мы будем несколько раз пробовать разные точки разбиения, а в конце выберем ту, которая имеет наименьшую стоимость. Конечно, можно проделать пару умных вещей, таких как разбиение только в диапазоне значений в нашем наборе данных. Это позволит сократить количество вычислений для тестирования точек разбиений, которые являются заведомо бесполезными.
Для дерева регрессии можно использовать простой квадрат ошибки в качестве функции стоимости:
Где Y — это достоверные данные, а Y с шапкой — это прогнозируемое значение. Мы суммируем по всем выборкам в нашем наборе данных, чтобы получить общую ошибку. Для классификации мы используем функцию коэффициента Джини:
Где pk — это доля обучающих примеров класса k в определенном узле прогнозирования. В идеале узел должен иметь значение ошибки, равное нулю, означающее, что каждое разбиение выводит один класс 100% времени. Это именно то, что нам нужно, так как добравшись до конкретно этого узла принятия решения, мы будем знать, каким будет вывод в зависимости от того, на какой стороне границы мы находимся.
Такая концепция единственного класса на узел в наборе данных называется «прирост информации». Посмотрите на пример ниже.
Если бы нам пришлось выбрать разбиение, на котором каждый выход имеет разные классы в зависимости от входных данных, тогда бы мы не добыли никакой информации. Мы не узнали бы больше о том, влияет ли конкретный узел, то есть функция, на классификацию данных! С другой стороны, если наше разбиение имеет высокий процент каждого класса для каждого выхода, то мы добыли информацию о том, что разбиение таким конкретным образом на эту конкретную переменную дает нам конкретный выход!
Теперь мы могли бы продолжить разбиение до тех пор, пока у нашего дерева не появятся тысячи ветвей… Но это плохая идея! Наше дерево решений было бы огромным, медленным и переобученным для нашего обучающего набора данных. Поэтому мы установим некоторые заранее определенные критерии остановки, чтобы прекратить построение дерева.
Наиболее распространенным методом остановки является использование минимального расчета по количеству обучающих примеров, назначенных для каждой вершины дерева. Если число меньше некоторого минимального значения, то разбиение не считается и узел назначается конечной вершиной дерева. Если все вершины дерева становятся конечными, то обучение прекращается. Чем меньше минимальное число, тем точнее будет разбиение и, соответственно, вы получите больше информации. Но в таком случае минимальное число склонно к переобучению обучающими данными. Слишком большое количество минимальных чисел приведет к остановке обучения слишком рано. Таким образом, минимальное значение обычно устанавливается на основе данных в зависимости от того, сколько примеров ожидается в каждом классе.
Отсечение
Из-за своего характера обучающие деревья решений могут быть подвержены значительному переобучению. Выбор правильного значения для минимального количества примеров на узел может оказаться сложной задачей. Во многих случаях можно было бы просто пойти по безопасному пути и сделать этот минимум очень маленьким. Но в таком случае, у нас было бы огромное количество разбиений и, соответственно, сложное дерево. Дело в том, что многие из получившихся разбиений окажутся лишними и не помогут увеличить точность модели.
Отсечение ветвей дерева — это метод, сокращающий количество разбиений с помощью удаления, т.е. отсечения, ненужных разбиений дерева. Отсечение обобщает границы решений, эффективно уменьшая сложность дерева. Сложность дерева решений определяется количеством разбиений.
Простой, но очень эффективный метод отсечения происходит снизу вверх через узлы, оценивая необходимость удаления определенного узла. Если узел не влияет на результат, то он отсекается.
Пример в Scikit-learn
Деревья решений как для классификации, так и для регрессии удобно использовать в библиотеке Scikit-learn со встроенным классом! Сначала загружаем набор данных и инициализируем дерево решений для классификации. Провести обучение будет очень просто!
Scikit-learn также позволяет визуализировать дерево с помощью библиотеки graphviz, в которой есть несколько очень полезных опций для визуализации узлов решений и разбиений, выученных моделью. Ниже обозначим узлы разными цветами, отталкиваясь от признаков имен, и отобразим класс и признак каждого узла.
Кроме того, в Scikit-learn можно указать несколько параметров для модели дерева решений. Ниже приведем некоторые из таких параметров, позволяющих получить лучший результат:
Советы по практическому применению деревьев решений
Ниже опишем все плюсы и минусы деревьев решений, которые помогут вам понять, нужно ли строить такую модель для решения определенной задачи или нет. Также дадим некоторые советы о том, как их можно эффективно использовать.
Что такое дерево решений и где его используют?
Ребята, привет! Сегодня команда ProductStar подготовила для вас статью, в которой мы рассмотрели общие принципы работы и области применения дерева решений. Материал подготовлен на основе работы Акобира Шахиди «Деревья решений: общие принципы»
Дерево решений — метод автоматического анализа больших массивов данных. В этой статье рассмотрим общие принципы работы и области применения.
Дерево решений — эффективный инструмент интеллектуального анализа данных и предсказательной аналитики. Он помогает в решении задач по классификации и регрессии.
В отличие от нейронных сетей, деревья как аналитические модели проще, потому что правила генерируются на естественном языке: например, «Если реклама привела 1000 клиентов, то она настроена хорошо».
Правила генерируются за счет обобщения множества отдельных наблюдений (обучающих примеров), описывающих предметную область. Поэтому их называют индуктивными правилами, а сам процесс обучения — индукцией деревьев решений.
В обучающем множестве для примеров должно быть задано целевое значение, так как деревья решений — модели, создаваемые на основе обучения с учителем. По типу переменной выделяют два типа деревьев:
дерево классификации — когда целевая переменная дискретная;
дерево регрессии — когда целевая переменная непрерывная.
Развитие инструмента началось в 1950-х годах. Тогда были предложены основные идеи в области исследований моделирования человеческого поведения с помощью компьютерных систем.
Дальнейшее развитие деревьев решений как самообучающихся моделей для анализа данных связано с Джоном Р. Куинленом (автором алгоритма ID3 и последующих модификаций С4.5 и С5.0) и Лео Брейманом, предложившим алгоритм CART и метод случайного леса.
Структура дерева решений
Рассмотрим понятие более подробно. Дерево решений — метод представления решающих правил в определенной иерархии, включающей в себя элементы двух типов — узлов (node) и листьев (leaf). Узлы включают в себя решающие правила и производят проверку примеров на соответствие выбранного атрибута обучающего множества.
Простой случай: примеры попадают в узел, проходят проверку и разбиваются на два подмножества:
первое — те, которые удовлетворяют установленное правило;
второе — те, которые не удовлетворяют установленное правило.
Далее к каждому подмножеству снова применяется правило, процедура повторяется. Это продолжается, пока не будет достигнуто условие остановки алгоритма. Последний узел, когда не осуществляется проверка и разбиение, становится листом.
Лист определяет решение для каждого попавшего в него примера. Для дерева классификации — это класс, ассоциируемый с узлом, а для дерева регрессии — соответствующий листу модальный интервал целевой переменной. В листе содержится не правило, а подмножество объектов, удовлетворяющих всем правилам ветви, которая заканчивается этим листом.
Пример попадает в лист, если соответствует всем правилам на пути к нему. К каждому листу есть только один путь. Таким образом, пример может попасть только в один лист, что обеспечивает единственность решения.
Терминология
Изучите основные понятия, которые используются в теории деревьев решений, чтобы в дальнейшем было проще усваивать новый материал.
Какие задачи решает дерево решений?
Его применяют для поддержки процессов принятия управленческих решений, используемых в статистистике, анализе данных и машинном обучении. Инструмент помогает решать следующие задачи:
Классификация. Отнесение объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные задачи.
Регрессия (численное предсказание). Предсказание числового значения независимой переменной для заданного входного вектора.
Описание объектов. Набор правил в дереве решений позволяет компактно описывать объекты. Поэтому вместо сложных структур, используемых для описания объектов, можно хранить деревья решений.
Процесс построения дерева решений
Основная задача при построении дерева решений — последовательно и рекурсивно разбить обучающее множество на подмножества с применением решающих правил в узлах. Но как долго надо разбивать? Этот процесс продолжают до того, пока все узлы в конце ветвей не станут листами.
Узел становится листом в двух случаях:
естественным образом — когда он содержит единственный объект или объект только одного класса;
после достижения заданного условия остановки алгоритм — например, минимально допустимое число примеров в узле или максимальная глубина дерева.
В основе построения лежат «жадные» алгоритмы, допускающие локально-оптимальные решения на каждом шаге (разбиения в узлах), которые приводят к оптимальному итоговому решению. То есть при выборе одного атрибута и произведении разбиения по нему на подмножества, алгоритм не может вернуться назад и выбрать другой атрибут, даже если это даст лучшее итоговое разбиение. Следовательно, на этапе построения дерева решений нельзя точно утверждать, что удастся добиться оптимального разбиения.
Популярные алгоритмы, используемых для обучения деревьев решений, строятся на базе принципа «разделяй и властвуй». Задают общее множество S, содержащее:
n примеров, для каждого из которых задана метка класса Ci(i = 1..k);
m атрибутов Aj(j = 1..m), которые определяют принадлежность объекта к тому или иному классу.
Тогда возможно три случая:
Примеры множества S имеют одинаковую метку Ci, следовательно, все обучающие примеры относятся к одному классу. В таком случае обучение не имеет смысла, потому что все примеры в модели будут одного класса, который и «научится» распознавать модель. Само дерево будет похоже на один большой лист, ассоциированный с классом Ci. Тогда его использование не будет иметь смысла, потому что все новые объекты будут относиться к одному классу.
Множество S — пустое множество без примеров. Для него сформируется лист, класс которого выберется из другого множества. Например, самый распространенный из родительского множества класс.
Множество S состоит из обучающих примеров всех классов Ck. В таком случае множество разбивается на подмножества в соответствии с классами. Для этого выбирают один из атрибутов Aj множества S, состоящий из двух и более уникальных значений: a1, a2, …, ap), где p — число уникальных значений признака. Множество S разбивают на p подмножеств (S1, S2, …, Sp), состоящих из примеров с соответствующим значением атрибута. Процесс разбиения продолжается, но уже со следующим атрибутом. Он будет повторяться, пока все примеры в результирующих подмножества не окажутся одного класса.
Третья применяется в большинстве алгоритмов, используемых для построения деревьев решений. Эта методика формирует дерево сверху вниз, то есть от корневого узла к листьям.
Сегодня существует много алгоритмов обучения: ID3, CART, C4.5, C5.0, NewId, ITrule, CHAID, CN2 и другие. Самыми популярными считаются:
ID3 (Iterative Dichotomizer 3). Алгоритм позволяет работать только с дискретной целевой переменной. Деревья решений, построенные на основе ID3, получаются квалифицирующими. Число потомков в узле неограниченно. Алгоритм не работает с пропущенными данными.
C4.5. «Продвинутая» версия ID3, дополненная возможностью работы с пропущенными значениями атрибутов. В 2008 году издание Spring Science провело исследование и выявило, что C4.5 — самый популярный алгоритм Data Mining.
CART (Classification and Regression Tree). Алгоритм решает задачи классификации и регрессии, так как позволяет использовать дискретную и непрерывную целевые переменные. CART строит деревья, в каждом узле которых только два потомка.
Основные этапы построения дерева решений
Построение осуществляется в 4 этапа:
Выбрать атрибут для осуществления разбиения в данном узле.
Определить критерий остановки обучения.
Выбрать метод отсечения ветвей.
Оценить точность построенного дерева.
Далее рассмотрим каждый подробнее.
Выбор атрибута разбиения
Разбиение должно осуществляться по определенному правилу, для которого и выбирают атрибут. Причем выбранный атрибут должен разбить множество наблюдений в узле так, чтобы результирующие подмножества содержали примеры с одинаковыми метками класса или были максимально приближены к этому. Иными словами — количество объектов из других классов в каждом из этих множеств должно быть как можно меньше.
Критериев существует много, но наибольшей популярностью пользуются теоретико-информационный и статистический.
Теоретико-информационный критерий
В основе критерия лежит информационная энтропия:
где n — число классов в исходном подмножестве, Ni — число примеров i-го класса, N — общее число примеров в подмножестве.
Энтропия рассматривается как мера неоднородности подмножества по представленным в нем классам. И даже если классы представлены в равных долях, а неопределенность классификации наибольшая, то энтропия тоже максимальная. Логарифм от единицы будет обращать энтропию в ноль, если все примеры узла относятся к одному классу.
Если выбранный атрибут разбиения Aj обеспечивает максимальное снижение энтропии результирующего подмножества относительно родительского, его можно считать наилучшим.
Но на деле об энтропии говорят редко. Специалисты уделяют внимание обратной величине — информации. В таком случае лучшим атрибутом будет тот, который обеспечит максимальный прирост информации результирующего узла относительно исходного:
где Info(S) — информация, связанная с подмножеством S до разбиения, Info(Sa) — информация, связанная с подмножеством, полученным при разбиении атрибута A.
Задача выбора атрибута в такой ситуации заключается в максимизации величины Gain(A), которую называют приростом информации. Поэтому теоретико-информационный подход также известен под название «критерий прироста информации.
Статистический подход
В основе этого метода лежит использования индекса Джини. Он показывает, как часто случайно выбранный пример обучающего множества будет распознан неправильно. Важное условие — целевые значения должны браться из определенного статистического распределения.
Если говорить проще, то индекс Джини показывает расстояние между распределениями целевых значений и предсказаниями модели. Минимальное значение показателя говорит о хорошей работе модели.
Индекс Джини рассчитывается по формуле:
где Q — результирующее множество, n — число классов в нем, pi — вероятность i-го класса (выраженная как относительная частота примеров соответствующего класса).
Значение показателя меняется от 0 до 1. Если индекс равен 0, значит, все примеры результирующего множества относятся к одному классу. Если равен 1, значит, классы представлены в равных пропорциях и равновероятны. Оптимальным считают то разбиение, для которого значение индекса Джини минимально.
Критерий остановки алгоритма
Алгоритм обучения может работать до получения «чистых» подмножеств с примерами одного класса. В таком случае высока вероятность получить дерево, в котором для каждого примера будет создан отдельный лист. Такое дерево не получится применять на практике из-за переобученности. Каждому примеру будет соответствовать свой уникальный путь в дереве. Получится набор правил, актуальный только для данного примера.
Переобучение в случае дерева решений имеет схожие с нейронными сетями последствия. Оно будет точно распознавать примеры из обучения, но не сможет работать с новыми данными. Еще один минус — структура переобученного дерева сложна и плохо поддается интерпретации.
Специалисты решили принудительно останавливать строительство дерева, чтобы оно не становилось «переобученным».
Для этого используют несколько подходов:
Ранняя остановка. Алгоритм останавливается после достижения заданного значения критерия (например, процентной доли правильно распознанных примеров). Преимущество метода — сокращение временных затрат на обучение. Главный недостаток — ранняя остановка негативно сказывается на точности дерева. Из-за этого многие специалисты советуют отдавать предпочтение отсечению ветей.
Ограничение глубины дерева. Алгоритм останавливается после достижения установленного числа разбиений в ветвях. Этот подход также негативно сказывается на точности дерева.
Задание минимально допустимого числа примеров в узле. Устанавливается ограничение на создание узлов с числом примером меньше заданного (например, 7). В таком случае не будут создаваться тривиальные разбиения и малозначимые правила.
Этими подходами пользуются редко, потому что они не гарантируют лучшего результата. Чаще всего, они работают только в каких-то определенных случаях. Рекомендаций по использованию какого-либо метода нет, поэтому аналитикам приходится набирать практический опыт путем проб и ошибок.
Отсечение ветвей
Без ограничения «роста» дерево решений станет слишком большим и сложным, что сделает невозможной дальнейшую интерпретацию. А если делать решающие правила для создания узлов, в которые будут попадать по 2-3 примера, они не лишатся практической ценности.
Поэтому многие специалисты отдают предпочтение альтернативному варианту — построить все возможные деревья, а потом выбрать те, которые при разумной глубине обеспечивают приемлемый уровень ошибки распознавания. Основная задача в такой ситуации — поиск наиболее выгодного баланса между сложностью и точностью дерева.
Но и тут есть проблема: такая задача относится к классу NP-полных задач, а они, как известно, эффективных решений не имеют. Поэтому прибегают к методу отсечения ветвей, который реализуется в 3 шага:
Строительство полного дерева, в котором листья содержат примеры одного класса.
Определение двух показателей: относительную точность модели (отношение числа правильно распознанных примеров к общему числу примеров) и абсолютную ошибку (число неправильно классифицированных примеров).
Удаление листов и узлов, потеря которых минимально скажется на точности модели и увеличении ошибки.
Отсечение ветвей проводят противоположно росту дерева, то есть снизу вверх, путем последовательного преобразования узлов в листья.
Главное отличие метода «отсечение ветвей» от преждевременной остановки — получается найти оптимальное соотношение между точностью и понятностью. При этом уходит больше времени на обучение, потому что в рамках этого подхода изначально строится полное дерево.
Извлечение правил
Иногда упрощения дерева недостаточно, чтобы оно легко воспринималось и интерпретировалось. Тогда специалисты извлекают из дерева решающие правила и составляют из них наборы, описывающие классы.
Для извлечения правил нужно отслеживать все пути от корневого узла к листьям дерева. Каждый путь дает правило с множеством условий, представляющих собой проверку в каждом узле пути.
Если представить сложное дерево решений в виде решающих правил (вместо иерархической структуры узлов), оно будет проще восприниматься и интерпретироваться.
Преимущества и недостатки дерева решений
Преимущества:
Формируют четкие и понятные правила классификации. Например, «если возраст
Дерево решений: метод «белого ящика» в машинном обучении
Дерево решений — логическая схема, позволяющие получить окончательное решение о классификации объекта после ответов на иерархически организованную систему вопросов. Стоит сказать, большинство высоко результативных решений на Kaggle — комбинация XGboost-ов, одного из вариантов деревьев решений, и очень качественного фичер-инжиниринга.
Один уровень
Стоящая за деревьями решений идея проста. Представим датасет, созданный путем записи времени ухода из дома и времени прихода на работу. Анализируя эти данные, можно увидеть, что в большинстве случаев выход из дома раньше 8:15 приводит к своевременному прибытию на работу, а выход после 8:15 — к опозданию.
Теперь этот паттерн можно выразить через дерево решений. В самой первой точке разветвления следует задать вопрос: “Выход из дома осуществляется раньше 8:15?”. Теперь есть две ветви — “да” и “нет”. Для согласованности будем считать положительный ответ левой веткой. Вводя такую границу решения, мы разбиваем данные на две группы. Хотя в таком случаем есть некоторые исключения и сложности, общее правило — разделение по времени с границей 8:15. Если вы выходите до 8:15, можете быть уверены, что попадете на работу вовремя. В противном случае — будьте уверены, что опоздаете.
Это самое простое дерево решений, состоящее из одной пары ветвей.
Два уровня
Мы можем уточнить оценку пунктуальности с помощью разделения обеих ветвей. Если мы добавим дополнительные границы решений со значениями 8:00 и 8:30, можем получить более точное предсказание исхода.
Выход до 8:00 однозначно приведет к своевременному появлению на работе, тогда как с 8:00 до 8:15 — лишь к высокой вероятности прийти вовремя, но не к гарантии. Похожим образом ветвь с выходом после 8:15 делится на две ветви с решающим вопросом: “отправление до 8:30?”. Если ответ положительный, то есть большая вероятность опоздать, если же отрицательный — вы гарантированно опоздаете.
Это дерево решений имеет уже два уровня. В общем случае, они могут иметь столько уровней, сколько вы захотите. В большинстве случаем каждый узел (решающий вопрос) имеет только две ветви.
Рассматриваемый пример использует только один фактор и одну целевую переменную, которую необходимо предсказать. Фактором выступает время отправления, а целевая переменная — приедем ли мы вовремя. Целевая переменная категориальная, так как она имеет только два различных значения. Деревья решений с категориальной целевой переменной называются классифицирующими деревьями.
Многомерное дерево решений
Можно расширить этот пример на случай нескольких предикторных переменных. Рассмотрим время выхода и день недели. Начнем собирать данные с понедельника (день 1), тогда суббота = 6, воскресенье = 7. Исследуя данные, можно видеть, что в субботу и воскресенье зеленые точки смещены в левую сторону. Это означает, выход в 8:10 является достаточным, чтобы успеть на работу вовремя в будний день, но не достаточным в выходные.
Чтобы отобразить этот факт в дереве решений, можем начать также, как и в первом примере, установив границу решений как 8:15. Выход после 8:15 скорее всего приведет к опозданию. Выход из дома до 8:15 — не показательный фактор, хотя ранее мы предполагали, что это гарантирует прибытие вовремя. Теперь мы видим по данным, что это не является полной правдой.
Чтобы сделать более точную оценку для выходных, разделим левую ветвь на выходные и будние дни. Теперь выход из дома до 8:15 в будний день гарантирует своевременное прибытие на работу. Для выходного дня в большинстве случаев это тоже вовремя, но не всегда. Мы обновили дерево решений с помощью узла, который отражает новую решающую границу.
Можно еще сильнее уточнить оценку разделением ветки с отправлением до 8:15 в выходной день на отправление до 8:00 и после. Отправление до 8:00 скорее всего приведет к своевременному появлению на работе, а в интервале с 8:00 до 8:15 к опозданию с большой вероятностью. Получилось двумерное дерево решений, аккуратно поделенное на 4 различных региона. Два из них соответствуют прибытию вовремя, два — опозданию.
Это трехуровневое дерево. Отметим, что не обязательно все ветки должны простираться на одинаковое количество уровней.
Регрессионное дерево решений
Рассмотрим случай с непрерывной целевой переменной, а не категориальной. В случае использования модели для предсказания непрерывных количественных переменных дерево называется регрессионным. Мы посмотрели на одномерные и двумерные классификационные деревья, теперь настало время взглянуть на регрессионные.
Перед нами стоит задача оценки времени пробуждения в зависимости от возраста человека. Корень нашего регрессионного дерева — оценка всего датасета. В этом случае, если требуется оценка без знания возраста конкретного человека, разумным предположением будет 6:25. Это и будет корнем нашего дерева.
Разумное первое разбиение — возраст 25 лет. В среднем, люди моложе 25 лет просыпаются в 7:05, а старше 25 — в 6 часов.
Существует всё еще много вариаций разбиения на возрастные группы, поэтому мы можем разделить выборку еще раз. Теперь можно предположить, что люди младше 12 лет просыпаются в 7:45, а в возрасте от 12 до 25 лет — в 6:40.
Группа людей старше 25 лет тоже может быть разумно разделена. Люди в возрасте от 25 до 40 лет просыпаются в среднем в 6:10, а в возрасте от 40 до 70 — в 5:50.
Поскольку наблюдается большая неоднозначность для младшей группы, можем разделить её еще раз. Теперь границей решений будет возраст 8 лет, что позволит более точно подстроиться под данные. Также можно разделить возрастную группу в диапазоне от 40 до 70 лет на отметке 58 лет. Отметим, мы добиваемся того, чтобы в каждом листе дерева находилось только одно или два значения из данных. Но это условие опасно тем, что может приводить к переобучению, о котором мы поговорим в скором времени.
В результате необходимо получить численную оценку в зависимости от возраста. Если требуется оценить время пробуждения для 36-летнего человека, можно начать с самой верхушки дерева. Этот процесс описывается следующим образом:
Структура дерева решений позволяет сортировать людей разных возрастов на соответствующие им ячейки и делать оценки времени пробуждения.
Конечно, существует способ расширения регрессионного дерева на случай двух предсказательных переменных. Если рассматривать не только возраст человека, но также и месяц года, можно получить явный и информативный паттерн. В Северной Америке дни длиннее в летние месяцы, и становится светлее раньше по утрам. В нашем нереалистичном примере дети и подростки не обременены строгим расписанием работы или учебы в школе, а их время пробуждения зависит только от того, когда восходит солнце. С другой стороны, взрослым присущ более стабильный распорядок дня, лишь немного зависящий от сезона. Но даже так, для старшего поколения характерно чуть более раннее время пробуждения.
Разветвленное дерево
Мы создаем дерево решений почти таким же образом, как и прошлое. Начинаем с корня — единичная оценка, которая грубо описывает весь набор данных — 6:30. (Здесь представлен код для визуализации с помощью библиотеки matplotlib).
Далее ищем подходящее место для установления границы решений. Делим данные по возрасту на отметке 35 лет, создавая две части:
Повторяем этот процесс, разделяя более молодую популяцию на два уровня — событие произошло до середины сентября и событие произошло до середины марта, соответственно. Такое разделение изолирует зимние месяцы от летних. Время пробуждения в зимние месяцы — 7:30 для людей младше 35 лет, а для летних — 6:56.
Теперь можем вернуться в узел с популяцией старше 35 лет и разделить его еще раз с границей в 48 лет для более точного представления.
Таким же образом разделим группу младше 35 лет для зимних месяцев добавлением границы в 18 лет. Человек младше 18 в зимние месяцы просыпается в 7:54, в противном случае, в 6:48.
Можно увидеть, что на графике начинают появляться высокие угловые пики. При каждом дополнительном разделении форма модели дерева решений становится более похожа на оригинальные данные. Кроме того, можно заметить, что в верхнем правом углу графика решающая граница начинает делить датасет на регионы примерно одинакового цвета.
Следующее разделение продолжает этот тренд, фокусируясь на группе младше 35 в летние месяцы, устанавливает границу в возрасте 13 лет. Форма модели становится всё более похожа на форму данных.
Этот процесс продолжается до тех пор, пока модель не станет хорошо представлять плавные тренды, соответствующие данным. Каждый решающий регион постепенно должен становиться меньше, тогда как аппроксимация лежащей в основе данных функции улучшается.
В тоже время деревья решений не лишены недостатков, важнейший из которых — переобучение. Возвращаясь к примеру регрессионного дерева с одной переменной (предсказание времени пробуждения по данным о возрасте), представим, что мы продолжаем разделять ось возраста до тех пор, пока в каждой ячейке не окажется один или два объекта из данных.
Когда мы дошли до этой стадии, дерево объясняет и описывает данные очень хорошо. Даже слишком хорошо. Такая модель не только находит лежащие в основе данных тренды (гладкая кривая, по которой следуют данные), но также реагирует и на шумы (несмоделированные отклонения), характерные для исследуемых данных. Если будет необходимо применить эту модель и предсказать время пробуждения на новых данных, шум из тренировочного сета будет делать предсказание менее точным. В идеале мы хотим, чтобы дерево решений находило только тренды, но не реагировало на шумы. Один из способов защититься от переобучения — убедиться, что в каждом листе нашего дерева находится больше чем один или несколько объектов. Такой способ позволяет усреднением избавиться от шума.
Другая вещь, на которую стоит обратить внимание — большое количество переменных. Мы начали с одномерного регрессионного дерева, затем добавили данные о месяцах, чтобы трансформировать дерево в двумерное. Такой метод не придает значение количеству измерений, которые у нас есть. Можно, например, добавить широту, интенсивность физической нагрузки человека в определенный день, индекс массы тела или любые другие переменные, которые могут быть релевантны для нашей задачи.
Чтобы визуализировать многомерные данные, используем прием, предложенный Джеффри Хинтоном — исследователем в области искусственных нейронных сетей. Он рекомендует следующее: “Чтобы иметь дело с гиперплоскостью в четырнадцатимерном пространстве, представьте себе трехмерное пространстве и скажите самому себе очень громко “четырнадцать.”
Проблема, возникающая при работе с многими переменными, связана с решением о том, какая из переменных должна идти в ветку при построении решающего дерева. Если имеется много переменных, то требуется большое количество вычислений. Также, чем больше переменных мы добавляем, тем большее количество данных нам необходимо, чтобы достоверно выбирать между ними. Легко попасть в ситуацию, где количество объектов в данных сравнимо с количеством переменных. Если наш датасет представлен в виде таблицы, то такая ситуация соответствует совпадению количества строк и столбцов. Существуют методы для борьбы с такими ситуациями, например, случайный выбор переменной для разделения в каждой ветке, но это требует повышенного внимания.
Вы можете свободно пользоваться всеми преимуществами силы деревьев решений, пока следите за местами, где модель может терпеть неудачи. Деревья решений — фантастический инструмент, когда вы хотите сделать как можно меньше предположений о ваших данных. Они обобщают и могут находить нелинейные зависимости между предсказательной и целевой переменной также хорошо, как и влияние одной предсказательной переменной на другую. Если имеется достаточное количество данных для осуществления необходимых разбиений, деревья решений могут выявлять квадратичные, экспоненциальные, циклические и другие зависимости. Деревья могут также находить неплавное поведение, резкие прыжки и пики, которые другие модели, такие как линейная регрессия или искусственные нейронные сети, могут скрывать.
Поэтому в задачах с большим объемом данных деревья решений показывают более высокие результаты, чем другие методы.