Технология графического построения дерева решений
Добавил пользователь Alex Обновлено: 18.09.2024
Нужно тщательно взвесить сложное решение? Попробуйте воспользоваться программой для создания деревьев решений. Читайте, как они устроены, где и как используются, как их создавать, и другую полезную информацию.
Читается за 8 мин.
Хотите создать собственную диаграмму? Попробуйте Lucidchart. Это быстро, легко и совершенно бесплатно.
Что такое дерево решений?
Дерево решений — разновидность схемы, где показаны возможные последствия принятия серии связанных между собой решений. Такой подход позволяет отдельным лицам и целым организациям взвесить разные варианты действий, принимая во внимание вовлеченные затраты, преимущества и уровни вероятности. Деревья решений применяются как в неформальных дискуссиях, так и в разработке алгоритмов для прогнозирования оптимального варианта действий математическим способом.
Дерево решений, как правило, начинается с одного узла, от которого ответвляются возможные варианты. Каждый из них затем ведет к дополнительным узлам, которые разветвляются на новые варианты. В итоге, вся схема приобретает форму дерева.
Узлы дерева решений символизируют одно из трех — вероятность, решение или конечный результат. Узел вероятности изображается в виде круга и сопровождается пометками с вероятностью того или иного результата. Узел решения отображается в виде квадрата и символизирует решение, которое необходимо принять. Ну а конечный узел указывает финальный результат, к которому ведет ветвь решений.
Деревья решений также можно составлять из символов для блок-схем, которые иногда удобнее воспринимать и усваивать.
Символы дерева решений
| Фигура | Название | Значение |
|---|---|---|
| Узел решения | Решение, которое необходимо принять | |
| Узел вероятности | Указывает несколько возможных результатов | |
| Ветви альтернативы | Каждая ветвь символизирует возможный результат или действие | |
| Отклоненная альтернатива | Вариант, который не был выбран | |
| Конечный узел | Символизирует конечный результат |
Как составить дерево решений
Прежде всего, определитесь, как вы планируете создавать дерево решений. Вы можете нарисовать его вручную на бумаге или доске либо воспользоваться специальной программой. В любом случае процедура создания дерева такова:
1. Начните с основного решения. Представьте его в виде небольшого квадрата и проведите вправо линии, каждая из которых символизирует возможное решение или действие. Подпишите каждую линию соответствующим образом.
2. Добавьте узлы принятия решений и узлы вероятности, соблюдая следующие правила:
- если требуется принять еще одно решение, нарисуйте новый прямоугольник;
- если точный результат неизвестен, нарисуйте круг (круги символизируют узлы вероятности);
- если вопрос решен, ничего не добавляйте (пока что).
От каждого узла принятия решения проведите линии к возможным способам решения. От каждого узла вероятности проедите линии с возможными результатами. Если вы планируете анализировать доступные варианты в цифрах, укажите уровень вероятности каждого результата и стоимость каждого действия.
Завершив составление дерева, вы сможете приступить к анализу стоящего перед вами решения.
Создание диаграмм быстро и легко с Lucidchart. Начните бесплатную пробную версию сегодня, чтобы начать создавать и сотрудничать.
Пример анализа дерева решений
Подсчитав предполагаемую пользу или ценность каждого варианта действий, вы тем самым сможете свести к минимуму риски и максимально повысить свои шансы на достижение желаемого результата.
Чтобы подсчитать предполагаемую пользу от варианта действия, нужно просто вычесть стоимость этого решения из его потенциальной выгоды. Потенциальная выгода представляет собой сумму значений всех результатов данного решения, причем каждое значение должно быть помножено на вероятность возникновения соответствующего результата. Как подсчитывалась потенциальная выгода в нашем примере:
При выявлении наиболее привлекательного результата важно учитывать предпочтения того, кто принимает решения. Например, одни стараются рисковать как можно меньше, тогда как другие готовы пойти на риск ради более высокой выгоды.
Если ваше дерево решений сопровождается вероятностной моделью, вы можете применить ее для подсчета условной вероятности события, то есть вероятности того, что оно произойдет при условии, что сначала случится некое другое событие. Для этого следуйте логической цепочке от исходного до целевого события и помножьте вероятности возникновения обоих событий.
Таким образом, вы сможете использовать дерево решений в качестве традиционной древовидной схемы, где представлены вероятности определенного события, например, того, что подброшенная монета дважды упадет на одну и ту же сторону.
Деревья решений в машинном обучении и добыче данных
Каждый дополнительный фрагмент данных позволяет модели более точно предсказать, какое значение из заданного набора соответствует нашему субъекту. Эта информация, в свою очередь, может использоваться в качестве входных данных в еще более масштабной модели принятия решений.
Иногда прогнозируемое значение выражается конкретным числом, например, если речь идет о цене. Деревья решений с непрерывным бесконечным количеством возможных результатов называют регрессионными.
Для большей точности иногда применяют сразу несколько деревьев решений сразу. Вот примеры таких методов:
- Бэггинг: предполагает создание нескольких деревьев на основе повторной выборки исходных данных, после чего эти деревья используются для достижения совместного решения;
- Метод случайного леса: применение нескольких деревьев с целью повысить количество успешно классифицированных объектов;
- Бустинг: применяется в отношении регрессионных и классификационных деревьев;
- Ротационный лес: деревья сперва обучаются методом анализа главных компонент (PCA) на случайной выборке данных.
Принято считать, что идеальное дерево решений должно передавать максимум информации при минимальном количестве вопросов или уровней. Среди алгоритмов для создания оптимизированных деревьев решений можно выделить CART, ASSISTANT, CLS и ID3/4/5. Дерево решений также можно выстроить при помощи набора ассоциативных правил и целевой переменной, которая помещается в правой части схемы.
Задача каждого метода — установить наиболее эффективный способ разбивки информации по уровням. Для этого часто применяются такие способы, как коэффициент Джини, прирост информации и понижение дисперсии.
Использование деревьев решений в машинном обучении имеет следующие преимущества:
Тем не менее, у деревьев решений есть и недостатки:
Шаблоны и примеры деревьев решений
Пустое дерево решений
Шаблон дерева решений с формулами
Это дерево решений поможет вам: схематично изобразить возможные последствия принятия серии связанных между собой решений; взвесить разные варианты действий с учетом их затрат, вероятности и преимуществ; быстро визуализировать информацию при помощи формул.
Шаблон дерева решений с данными
На этом примере вы также увидите, как пользоваться привязкой данных и слоями для удобной визуализации оптимального решения. Настройте этот шаблон под свой проект, добавив необходимые данные, узлы и результаты.
Шаблон вертикального дерева решений
Вертикальное дерево решений схематично показывает возможные последствия принятия серии связанных между собой решений. Данный шаблон построен по принципу нисходящей иерархии.
Даже если перед вами стоят сложные вопросы, найти подходящую схему для их решения просто. Используйте Lucidchart для наглядного анализа сложных решений прямо онлайн!
Хотите создать собственную диаграмму? Попробуйте Lucidchart. Это быстро, легко и совершенно бесплатно.
Не можете принять решение или просчитать риски в бизнесе? Invme расскажет, как это сделать. Читайте нашу статью о дереве решений и узнайте, как его создать и как с ним работать.
Дерево решений можно представить как карту возможных результатов из ряда взаимосвязанных выборов
Что такое дерево решений
Дерево решений – это способ для принятия решений. Он используется не только в аналитике и в бизнесе, но он может быть применен и в жизни, когда нужно рассмотреть ту или иную проблему с разных сторон и принять правильное решение.
Дерево решений можно представить как карту возможных результатов из ряда взаимосвязанных выборов. Это помогает сопоставить возможные действия, основываясь на их стоимости вероятности и выгоде. Для этого используют модель принятия решений в виде дерева, что может быть полезно и в процессе обсуждения чего-либо, и для составления алгоритма, который математически определяет наилучший выбор.
Обычно дерево решений начинается с одного узла, который разветвляется на возможные результаты. Каждый из них продолжает схему и создает дополнительные узлы, которые продолжают развиваться по тому же признаку. Это придает модели древовидную форму: то есть переход от верхушки дерева - к веткам и множеству листьев.
Дерево решений обычно состоит из трёх типов узлов:
- Узлы решения — обычно представлены квадратами
- Вероятностные узлы — представляются в виде круга
- Замыкающие узлы — представляются в виде треугольника
Кто придумал дерево решений
Развитие дерева решений началось в 1950-х годах. Тогда были предложены основные идеи в области исследований моделирования человеческого поведения с помощью компьютерных систем.
Дальнейшее развитие деревьев решений как самообучающихся моделей для анализа данных связано с математиками Джоном Р. Куинленом и Лео Брейманом, предложившим алгоритм CART и метод случайного леса.
Почему такое название
Метод получил такое название из-за своей структуры, включающей в себя элементы двух типов — узлов (node) и листьев (leaf). Лист определяет решение для каждого попавшего в него примера, в нем содержится не правило, а подмножество объектов, удовлетворяющих всем правилам ветви, которая заканчивается этим листом. К каждому листу есть только один путь, поэтому пример или утверждение могут попасть только в один лист, что обеспечивает единственность решения.
Деревья решений представляют собой последовательные иерархические структуры, состоящие из узлов, которые содержат правила, т.е. логические конструкции вида "если … то …". Конечными узлами дерева являются "листья", соответствующие найденным решениям и объединяющие некоторое количество объектов классифицируемой выборки. Это похоже на то, как положение листа на дереве можно задать, указав ведущую к нему последовательность ветвей, начиная от корня и кончая самой последней веточкой, на которой лист растет.
Где используют дерево решений
В целом дерево решений можно применить практически к любой сфере (включая личные решения того или иного вопроса). Но все-таки чаще всего он используется в следующих областях:
- банковское дело – оценка кредитоспособности клиентов банка при выдаче кредитов;
- промышленность – контроль качества продукции (выявление дефектов), испытания без разрушений (например, проверка качества сварки) и т.д.;
- медицина – диагностика различных заболеваний;
- маркетинг – предсказание выбора покупателя, сегментация клиентской базы;
- молекулярная биология – анализ строения аминокислот и другие области.
В целом дерево решений можно применить практически к любой сфере
Дерево решений: пример
Например, вы решили задаться вопросом, как вам иметь больше денег к концу года, не влезая в долги. Это главный вопрос, от которого будут отходить все остальные.
Итак, главный вопрос разветвляется на две части: Доходы и Расходы. Доходы нужно повышать, расходы понижать. Как это сделать? От доходов идут разветвления: случайный выигрыш и работа. Выигрыш может быть легальным и нелегальным. Это может быть, скажем, выигрыш в лотерею или наследство.
Работа имеет еще больше разветвлений. Либо увеличение рабочих часов, либо больший заработок за час. Дальше это выливается в сверхурочные, вторую работу, переход в более высокооплачиваемую отрасль и др.
Расходы разветвляются на стоимость и количество покупок. Стоимость можно понижать за счет, например, распродаж. А количество покупок понижать в каждой из сфер: еда, одежда, развлечения, путешествия, другое.
Таким образом можно разобрать практически любую проблему и прийти к определенному решению. Структурированный вид помогает смотреть на все шире и брать во внимание множество нюансов, которые не всегда понятны в другом виде.
Обыкновенное дерево состоит из корня, ветвей, узлов (мест разветвления), листьев. Точно также дерево решений состоит из узлов (называемых также вершинами), обозначаемых окружностями; ветвей, обозначаемых отрезками, соединяющими узлы. Для удобства дерево решений изображают обычно слева направо или сверху вниз. Самая первая (левая или верхняя) вершина называется корнем. Цепочка "корень - ветвь - вершина - . - вершина" заканчивается вершиной, которую называют "листом". Из каждой внутренней вершины (т.е. не листа) может выходить две или более ветвей. Каждому такому узлу сопоставлена некоторая характеристика, а ветвям - области значения этой характеристики, причем эти области дают разбиение множества значений данной характеристики.
Плюсы и минусы дерева решений
Плюсы:
- Формирует четкие и понятные правила классификации. То есть деревья решений хорошо и быстро интерпретируются
- Деревья способны генерировать правила в областях, где специалисту трудно формализовать свои знания
- Быстро обучаются и прогнозируют
- Не требуется много параметров модели
- Поддерживают как числовые, так и категориальные признаки
- Быстро приводят к результату и решению проблемы
Минусы:
- Деревья решений очень чувствительны. Небольшие изменения обучающей выборки могут привести к глобальным корректировкам модели.
- Разделяющая граница имеет определенные ограничения, из-за чего дерево решений по качеству классификации уступает другим методам.
Дерево решений - это метод, который применяется для принятия решений в условиях неопределенности и риска. Данный метод используется в случае, когда нужно принимать ряд последовательных решений. Дерево решений является графическим методом, который позволяет скоординировать элементы принятия решения, вероятные стратегии (Аi), их последствия (Ei,j) с вероятностными условиями и факторами внешней среды воздействия.
Начинается построение дерева решений с наиболее раннего решения, после разрабатываются возможные результаты и последствия каждого из действий (событий), после вновь определяется выбор направления действия (принимается решение) и так далее до тех пор, пока все последствия результатов решений не будут определены.
Дерево решений составляется на основании 5 последовательных элементов (рисунок 1):
Рисунок 1 – Элементы дерева решений
Простейшее решение
Простейшим решением является выбор из двух вариантов: "нет" или "да". (рисунок 2).
Рисунок 2 - Простейшее дерево решений
Последовательности решений можно смоделировать следующим образом (рисунок 3):
Рисунок 3 - Дерево (последовательность) принимаемых решений
1) решение: необходимо выбрать между тем, чтобы "Спать допоздна" или "Вставать рано"– простой выбор;
2) решение: необходимо выбрать между тем, чтобы "Работать спустя рукава" или "Работать усердно"– простой выбор;
3) событие: "Найдешь нефть" или нет случается с определенной вероятностью, которая зависит от принимаемых решений.
Поставленные задачи и варианты их решений приведены в таблицах 1 и 2, и отражены на рисунке 4 в виде дерева решений.
Жирным курсивом обозначен путь на дереве, являющийся самым предпочтительным (EV = 820000 долларов) и соответствующий решению, состоящему из элементов "Вставай рано" и "Работай усердно".
Таблица 1 - Вычисление ожидаемых результатов поиска нефти взвешенных по вероятности
| Решение: "Вставай рано" + "Работай усердно" | Возможное событие | |
| Не найти нефть | Найти нефть | |
| Событие: прибыль (убыток), долларов | -200 000 | 10000 000 |
| Событие: вероятность наступления события | 0,90 | 0,10 |
| Риск = Прибыль (убыток) × Вероятность, долларов | -180 000 | 1000 000 |
| Ожидаемое значение результата (EV), долларов | 1000000-180000 = 820 000 | |
Таблица 2 - Ожидаемые результаты решения "Когда встать и как работать"
Вероятность (найти нефть) = 5% (1- Вероятность) (не найти нефть) = 95%
Ожидаемое значение результатов решения: ( 0 , 05 × 10 000 000 ) + 0 , 95 × ( - 200 000 ) = 310000 долларов
Вероятность (найти нефть) = 10% (1- Вероятность) (не найти нефть) = 90%
Ожидаемое значение результатов решения: ( 0 , 1 × 10 000 000 ) + 0 , 9 × ( - 200 000 ) = 820 000 долларов
Вероятность (найти нефть) = 0% (1- Вероятность) (не найти нефть) = 100%
Ожидаемое значение результатов решения: ( 0 - 10 000 000 ) + 1 × ( - 200 000 ) = - 200 000 долларов
Вероятность (найти нефть) = 1% (1- Вероятность) (не найти нефть) = 99%
Ожидаемое значение результатов решения: ( 0 , 01 × 10 000 000 ) + ( 0 , 99 × ( - 200 000 ) = - 98 000 долларов
Рисунок 4 - Дерево решений с ожидаемыми значениями результатов(EV), долларов
Дополнительно учтем в примере, приведенном выше, изменение в зависимости от срока окупаемости стоимости проекта.
Установим, что сумма средств, необходимых для поиска нефти, расходуется сразу же. Если находим нефть, то все средства, вложенные в нефтеразведку покрываются сразу же, а доходы от продаж добытой нефти поступают через два года. Чтобы корректно учитывать все данные платежи и поступления, разбросанные во времени, необходимо привести все суммы денежных средств к текущей стоимости.
Установим, что ставка дисконтирования будет принимать значение, равное 20 процентов, тогда таблица 2 будет представлена в следующем виде (таблица 3), а дерево решений (рисунок 4) – в виде, показанном на рисунке 5.
Таблица 3 - Ожидаемая приведенная стоимость и результаты решения "Когда вставать и как работать" с учетом коэффициента дисконтирования
Вероятность (найти нефть) = 5% (1 – Вероятность) (не найти нефть) = 95%
Ожидаемая стоимость: 310000 долл.
Ожидаемая приведенная стоимость: ( 0 , 05 × 10 000 000 ) / 1 , 22 + 0 , 95 × ( - 200000 ) = 157 222 долл.
Вероятность (найти нефть) =10% (1 – Вероятность) (не найти нефть) = 90%
Ожидаемая стоимость: 820 000 долл.
Ожидаемая приведенная стоимость: ( 0 , 1 × 10 000 000 ) / 1 , 22 + 0 , 9 × ( - 200 000 ) = 514 444 долл.
Вероятность (найти нефть) = 0% (1 - Вероятность) (не найти нефть) = 100%
Ожидаемая стоимость: – 200000 долл.
Ожидаемая приведенная стоимость: ( 0 × 10 000 000 ) / 1 , 22 + 1 × ( - 200 000 ) = - 200 000 долл.
Вероятность (найти нефть) =1% (1 - Вероятность) (не найти нефть) = 99%
Ожидаемая стоимость: – 98000 долл.
Ожидаемая приведенная стоимость: ( 0 , 01 × 10 000 000 ) / 1 , 22 + 0 , 99 × ( - 200 000 ) = - 128 555 долл.
Самая эффективная последовательность решений та же (отображен жирной линией путь, который совпадает с решением "Вставай рано" + "Работай усердно", однако изменилось значение ожидаемого выигрыша (514444 долларов), в связи с тем, что учитывалась ставка дисконтирования.
Руководитель организации, выпускающего в настоящее время продукцию X1 в объеме V1тек. = 1000 единиц, считает, что необходимо расширять рынок продукции Х2.
Проведенные маркетинговые исследования определили вилки спроса на продукцию Х2 (V1max = 1000 единиц; V1min = 5000 единиц; V2max = 8000 единиц; V2min = 4000 единиц), а также вероятности низкого и высокого спроса (D1max = 0,7; D1min = 1 -D1max = 0,3; D2max = 0,6; D2min = 1-D2max = 0,4).
Выявлено, что даже минимальный уровень спроса намного превышает имеющиеся мощности организации, которые необходимо использовать для производства обоих видов продукции.
Определен уровень прибыли на единицу продукции каждого из видов (P1 = 1 денежных единиц; Р2 = 0,9 денежных единиц).
Рассчитаны затраты (К = 0,4 * 103 денежных единиц) на удвоение мощности организации (для одновременного производства продукта Х1 в существующем объеме и производства продукции Х2 в эквивалентном объеме) V1тек = 1000 единиц и V2экв = 900 единиц, на увеличение мощности организации под минимальный и максимальный спрос на текущую продукцию (K1min= = 1,4 * 103 денежных единиц и K1max = 2 * 103 денежных единиц) и под минимальный и максимальный уровень спроса на продукцию Х2 (К2 min = 0,8 * 103 денежных единиц и К1max = 1,2 * 103 денежных единиц соответственно).
Необходимо определить рациональность замены продукции и расширения мощностей, под одновременный выпуск продукции в том числе.
Дерево решений и рассчитанные последствия решения отображены на рисунке 5.
Рисунок 5 - Дерево решений с ожидаемыми значениями приведенных результатов (EV), долларов
Определив результаты решений при производстве продукции одного их видов (Х1 или Х2), выявим эффективные действия во второй точке решений.
Отбросим для этого иррациональные действия по расширению мощностей и данные об ожидаемом выигрыше перенесем в 4 графу. С учетом вероятности существующего спроса на продукты, проведем расчет средней эффективности действий в местах разветвления событий (3 графа). Выявлено, что продолжение производства продукта Х1, при параллельном расширении мощностей является более выгодным вариантом, чем переход на производство продукции Х2 вместо продукции X1.
Однако нами не учитывалась возможность параллельного производства продукции X1 и Х2 при расширении мощностей организации под максимальный уровень спроса. Поэтому проведем еще одно ответвление из первой точки принятия решения, соответствующее этому варианту решения. Эффективность этого варианта состоит из эффективности первого варианта и второго варианта (Э1 и Э2) за минусом вложений на первоначальное удвоение мощностей организации. Эффективность этого варианта самая высокая, поэтому варианты 1 и 2 необходимо вычеркнуть.
Вывод. Необходимо существенно развивать мощности и одновременно выпускать два вида продукции.
Рисунок 6 - Дерево принятия решений при определении стратегии организации
Представленная схема решения немного упрощена, так как мы не рассматривали варианты привлечения резервов по выпуску продукта одного вида при минимальном уровне спроса для производства продукции другого вида, лимиты по вложениям денежных средств (в условиях задачи для этого недостаточно данных).
В последние десятилетия одними из самых популярных методов решения задач прогнозной аналитики являются методы построения деревьев решений. Эти методы универсальны, используют эффективную процедуру вычислений, позволяют найти достаточно качественное решение задачи. Именно об этих методах я расскажу в данной статье.
Дерево решений
Мы рассмотрим алгоритм, позволяющий построить такое дерево решений для оценивания и предсказания значений интересующего нас категориального атрибута анализируемого набора данных на основе значений других атрибутов (задача классификации).
Алгоритм построения дерева решений
Главный вопрос – как выбирать атрибуты. В соответствии с идеей подхода, когда в концевых узлах дерева (листьях) будет искомый нами класс целевого атрибута, необходимо, чтобы при разбиении набора данных в каждом узле получавшиеся наборы данных были все более однородны в плане значений классов (например, большинство объектов в наборе принадлежало бы к классу Арбуз). И необходимо определить количественный критерий, чтобы оценить однородность разбиения.
Энтропия
Рассмотрим набор вероятностей pi, описывающий вероятность соответствия строки данных в нашем наборе (обозначим его X) классу i. Вычислим следующую величину:
Далее, для выбора атрибута, для каждого атрибута A вычисляется так называемый прирост информации:
Где values(A) – все принимаемые значения атрибута A, Xa – подмножество набора данных, где A = a, |X| – количество элементов во множестве. Данная величина описывает ожидаемое уменьшение энтропии после разбиения набора данных по выбранному атрибуту. Второе слагаемое – это сумма энтропий для каждого подмножества, взятая со своим весом. Общая разница описывает, как уменьшится энтропия, сколько мы сэкономим бит для кодирования класса случайного объекта из набора X, если мы знаем значения атрибута A и разобьем набор данных на подмножества по данному атрибуту.
Алгоритм выбирает атрибут, соответствующий максимальному значению прироста информации.
Когда атрибут выбран, исходный набор разбивается на подмножества в соответствии с его значениями, исходный атрибут исключается из анализа, процесс повторяется рекурсивно.
Процесс останавливается, когда созданные подмножества стали достаточно однородны (преобладает один класс), а именно когда max(Gain(X,A)) становится меньше некоторого заданного параметра Θ (величина, близкая к 0). Как альтернативный вариант, можно контролировать само множество X, и когда оно стало достаточно мало или стало полностью однородным (только один класс), останавливать процесс.
Вы скорее всего уже использовали деревья решений для того, чтобы сделать какой-нибудь выбор в своей жизни. Например, нужно решить, чем вы займетесь на предстоящих выходных. Итог может зависеть от того, хотите ли вы пойти куда-то с друзьями или провести выходные в одиночестве. В обоих случаях решение зависит также и от погоды. Если она будет солнечной и друзья будут свободны, вы можете сходить поиграть в футбол. Если пойдет дождь, вы пойдете в кино. Если друзья будут заняты, то вы останетесь дома играть в видео игры, даже несмотря на хорошую погоду.
Этот пример хорошо демонстрирует дерево решений в реальной жизни. Мы построили дерево и смоделировали ряд последовательных, иерархических решений, которые, в конечном итоге, приводят к некоторому результату. Обратите внимание, что мы выбрали максимально общие варианты решения, чтобы дерево было маленьким. Дерево будет просто огромным, если мы установить много возможных вариантов погоды, например: 25 градусов, солнечно; 25 градусов, дождливо; 26 градусов, солнечно; 26 градусов, дождливо; 27 градусов, солнечно; 27 градусов, дождливо и т.д. Конкретная температура не важна. Нам нужно лишь знать, будет ли погода хорошей или нет.
В машинном обучении концепция деревьев решений такая же. Нам нужно построить дерево с набором иерархических решений, которые в конце приведут нас к результату, то есть к нашей классификации или прогнозу регрессии. Решения выбираются таким образом, чтобы дерево было максимально маленьким, но при этом сохраняло точность классификации или регрессии.
Модели дерева решений строятся в два этапа: индукция и отсечение. Индукция — это то, где мы строим дерево, то есть устанавливаем все границы иерархического решения, основываясь на наших данных. Из-за своего характера обучаемые деревья решений могут быть подвержены значительному переобучению. Отсечение — это процесс удаления ненужной структуры из дерева решений, эффективно упрощая его для понимания и избежания переобучения.
Индукция
Индукция дерева решений проходит 4 главных этапа построения:
Первый этап простой. Просто соберите свой набор данных!
На втором этапе выбор признака и определенного разбиения обычно осуществляется с помощью жадного алгоритма для уменьшения функции стоимости. Если подумать, разбиение при построении дерева решений эквивалентно разбиению признакового пространства. Мы будем несколько раз пробовать разные точки разбиения, а в конце выберем ту, которая имеет наименьшую стоимость. Конечно, можно проделать пару умных вещей, таких как разбиение только в диапазоне значений в нашем наборе данных. Это позволит сократить количество вычислений для тестирования точек разбиений, которые являются заведомо бесполезными.
Для дерева регрессии можно использовать простой квадрат ошибки в качестве функции стоимости:
Где Y — это достоверные данные, а Y с шапкой — это прогнозируемое значение. Мы суммируем по всем выборкам в нашем наборе данных, чтобы получить общую ошибку. Для классификации мы используем функцию коэффициента Джини:
Где pk — это доля обучающих примеров класса k в определенном узле прогнозирования. В идеале узел должен иметь значение ошибки, равное нулю, означающее, что каждое разбиение выводит один класс 100% времени. Это именно то, что нам нужно, так как добравшись до конкретно этого узла принятия решения, мы будем знать, каким будет вывод в зависимости от того, на какой стороне границы мы находимся.
Если бы нам пришлось выбрать разбиение, на котором каждый выход имеет разные классы в зависимости от входных данных, тогда бы мы не добыли никакой информации. Мы не узнали бы больше о том, влияет ли конкретный узел, то есть функция, на классификацию данных! С другой стороны, если наше разбиение имеет высокий процент каждого класса для каждого выхода, то мы добыли информацию о том, что разбиение таким конкретным образом на эту конкретную переменную дает нам конкретный выход!
Теперь мы могли бы продолжить разбиение до тех пор, пока у нашего дерева не появятся тысячи ветвей… Но это плохая идея! Наше дерево решений было бы огромным, медленным и переобученным для нашего обучающего набора данных. Поэтому мы установим некоторые заранее определенные критерии остановки, чтобы прекратить построение дерева.
Наиболее распространенным методом остановки является использование минимального расчета по количеству обучающих примеров, назначенных для каждой вершины дерева. Если число меньше некоторого минимального значения, то разбиение не считается и узел назначается конечной вершиной дерева. Если все вершины дерева становятся конечными, то обучение прекращается. Чем меньше минимальное число, тем точнее будет разбиение и, соответственно, вы получите больше информации. Но в таком случае минимальное число склонно к переобучению обучающими данными. Слишком большое количество минимальных чисел приведет к остановке обучения слишком рано. Таким образом, минимальное значение обычно устанавливается на основе данных в зависимости от того, сколько примеров ожидается в каждом классе.
Отсечение
Из-за своего характера обучающие деревья решений могут быть подвержены значительному переобучению. Выбор правильного значения для минимального количества примеров на узел может оказаться сложной задачей. Во многих случаях можно было бы просто пойти по безопасному пути и сделать этот минимум очень маленьким. Но в таком случае, у нас было бы огромное количество разбиений и, соответственно, сложное дерево. Дело в том, что многие из получившихся разбиений окажутся лишними и не помогут увеличить точность модели.
Отсечение ветвей дерева — это метод, сокращающий количество разбиений с помощью удаления, т.е. отсечения, ненужных разбиений дерева. Отсечение обобщает границы решений, эффективно уменьшая сложность дерева. Сложность дерева решений определяется количеством разбиений.
Простой, но очень эффективный метод отсечения происходит снизу вверх через узлы, оценивая необходимость удаления определенного узла. Если узел не влияет на результат, то он отсекается.
Деревья решений как для классификации, так и для регрессии удобно использовать в библиотеке Scikit-learn со встроенным классом! Сначала загружаем набор данных и инициализируем дерево решений для классификации. Провести обучение будет очень просто!
Scikit-learn также позволяет визуализировать дерево с помощью библиотеки graphviz, в которой есть несколько очень полезных опций для визуализации узлов решений и разбиений, выученных моделью. Ниже обозначим узлы разными цветами, отталкиваясь от признаков имен, и отобразим класс и признак каждого узла.
Кроме того, в Scikit-learn можно указать несколько параметров для модели дерева решений. Ниже приведем некоторые из таких параметров, позволяющих получить лучший результат:
- max_depth: максимальная глубина дерева — точка, на которой останавливается разбиение узлов. Это похоже на выбор максимального количества слоев в глубокой нейронной сети. Меньшее количество сделает модель быстрой, но не точной. Большее количество увеличивает точность, но создает риски переобучения и замедляет процесс.
- min_samples_split: необходимое минимальное количество выборок для разбиения узлов. Мы уже обсуждали это выше вместе с тем, как настроить высокое значение, чтобы минимизировать переобучение.
- max_features: число признаков для поиска лучшей точки для разбиения. Чем больше число, тем лучше результат. Но в этом случае обучение займет больше времени.
- min_impurity_split: порог для ранней остановки роста дерева. Узел разобьется только в том случае, если его точность будет выше указанного порога. Такой метод может служить в качестве компромисса между минимизацией переобучения (высокое значение, маленькое дерево) и высокой точностью (низкое значение, большое дерево).
- presort: выбор того, нужно ли предварительно сортировать данные для ускорения поиска наилучшего разбиения при подборе. Если данные заранее отсортируются по каждому признаку, то алгоритму обучения будет гораздо проще найти хорошие значения для разбиения.
Ниже опишем все плюсы и минусы деревьев решений, которые помогут вам понять, нужно ли строить такую модель для решения определенной задачи или нет. Также дадим некоторые советы о том, как их можно эффективно использовать.
Читайте также: