Что такое дерево решений и как его создать?

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

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

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

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

Фигура	Название	Значение
	Узел решения	Решение, которое необходимо принять
	Узел вероятности	Указывает несколько возможных результатов
	Ветви альтернативы	Каждая ветвь символизирует возможный результат или действие
	Отклоненная альтернатива	Вариант, который не был выбран
	Конечный узел	Символизирует конечный результат

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

1.

Начните с основного решения

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

2.

Добавьте узлы принятия решений и узлы вероятности

, соблюдая следующие правила:

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

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

3.

Продолжайте выращивать дерево, пока каждая ветвь не дойдет до конечной точки

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

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

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

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

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

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

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

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

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

Эти правила (их также называют правилами принятия решений) могут выражаться в условии «если-то», причем это условие формируется по каждому решению или значению данных, например, «если удовлетворены условия 1, 2 и 3, то это приведет к результату X с вероятностью Y».

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

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

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

• Бэггинг

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

• Метод случайного леса

  : применение нескольких деревьев с целью повысить количество успешно классифицированных объектов;

• Бустинг

  : применяется в отношении регрессионных и классификационных деревьев;

• Ротационный лес

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

Принято считать, что идеальное дерево решений должно передавать максимум информации при минимальном количестве вопросов или уровней. Среди алгоритмов для создания оптимизированных деревьев решений можно выделить CART, ASSISTANT, CLS и ID3/4/5. Дерево решений также можно выстроить при помощи набора ассоциативных правил и целевой переменной, которая помещается в правой части схемы.

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

Использование деревьев решений в машинном обучении имеет следующие преимущества:

• затраты на их применение снижаются с каждой дополнительной точкой данных;
• подходят как для категориальных, так и для числовых данных;
• позволяют моделировать вопросы с несколькими выходными результатами;
• опираются на метод «белого ящика» (проще объяснять результаты);
• их надежность можно протестировать и замерить в численном виде;
• дают точные результаты даже при нарушении предпосылок исходных данных.

Тем не менее, у деревьев решений есть и недостатки:

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

Пустое дерево решений

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

Шаблон дерева решений с формулами

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

Шаблон дерева решений с данными

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

Шаблон вертикального дерева решений

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