Недостаток метода дерева решений

8.10. Метод «дерево решений»

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

1. Первоначально обозначают ключевую проблему. Это будет вершина дерева.
2. Для каждого момента определяют все возможные варианты дальнейших событий, которые могут оказать влияние на ключевую проблему. Это будут исходящие от вершины дуги дерева.
3. Обозначают время наступления событий.
4. Каждой дуге прописывают денежную и вероятностную характеристики.
5. Проводят анализ полученных результатов.

Основа наиболее простой структуры дерева решений – ответы на вопросы «да» и «нет». Пример 1. Рассмотрим пример дерева решений, задача которого – ответить на вопрос «Пойти ли гулять?». Чтобы решить эту задачу, необходимо ответить на ряд вопросов, которые находятся в узлах дерева (рис. 8.1). Вершина дерева «На улице солнечно» является узлом проверки. Если на этот вопрос получен положительный ответ, то переходим к левой ветви дерева, если отрицательный – то к правой. Движение продолжается до тех пор, пока не будет получен окончательный ответ. Рис. 8.1. Дерево решений «пойти ли гулять» Для каждой дуги дерева могут быть определены числовые характеристики, например величина прибыли по проекту и вероятность ее получения. В этом случае оно помогает учесть все возможные варианты действия и соотнести с ними финансовые результаты. Для формулирования сценариев развития проекта необходимо располагать достоверной информацией с учетом вероятности и времени наступления событий. Затем переходят к сравнению альтернатив. Пример 2. Компания «Конфетти» в настоящее время выпускает плитки молочного шоколада. Директор по развитию считает, что на рынке повысился спрос на молочный шоколад с наполнителями. Перед компанией стоит вопрос: переходить ли на производство молочного шоколада с наполнителем или не стоит этого делать? Если производить шоколад обоих типов, то потребуется увеличить производственные мощности. Информация об ожидаемых выигрышах и вероятности событий в случае того или иного решения представлена на дереве решений (рис. 8.2). Используя дерево решений, руководитель находит наиболее предпочтительное решение – увеличить производственные мощности. Это обусловлено ожидаемой прибылью – 2 млн руб., которая превышает прибыль 1 млн руб. при отказе от такого наращивания, если в точке «а» будет низкий спрос. Руководитель, двигаясь к первой точке принятия решения, рассчитывает предполагаемую прибыль в случае альтернативных действий. Рис. 8.2. Дерево решений «какой шоколад производить» Для производства только молочного шоколада с наполнителем она составит 4,4 млн руб. (5 × 0,8 + 0,2 × 2). Аналогично рассчитывается ожидаемое значение для варианта выпуска только молочного шоколада без наполнителя, которое равно всего 2,55. Таким образом, наращивание производственных мощностей является наиболее желательным решением и приносит наибольший выигрыш. Пример 3. Руководителю отдела нужно принять решение относительно закупки станков. Второй станок более экономичный, но и в то же время более дорогой и требует больших накладных расходов (рис. 8.3). Руководителю нужно выбрать тот станок, который обеспечит максимизацию прибыли.

Оборудование	Постоянные расходы	Операционный расход на единицу техники
Станок 1	500 000	670
Станок 2	700 000	940

Рис. 8.3. Дерево решений Руководитель оценивает вероятность спроса на продукцию, производимую на станках:

• 2 000 ед. с вероятностью 0,4;
• 3 000 ед. с вероятностью 0,6.

Станок 1: 840 000 × 0,4 + 1 510 000 × 0,6 = 1 242 000. Станок 2: 1 180 000 × 0,4 + 2 120 000 × 0,6 = 1 744 000. Таким образом, приобретение второго станка более экономично. Недостатками дерева решений является ограниченное число вариантов решения проблемы. В процессе построения дерева решений необходимо обращать внимание на его размер. Оно не должно быть слишком перегруженным, т. к. это уменьшает способность к обобщению и способность давать верные ответы.

Источник

Как создать идеальное дерево решений: для начинающих аналитиков данных и не только

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

Статья подготовлена на основе перевода: How to Create a Perfect Decision Tree by Upasana Priyadarshiny.

Основные задачи, которые дерево решений решает в машинном обучении, анализе данных и статистике:

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

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

Что такое дерево решений

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

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

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

В дереве решений могут быть три разных типа узлов:

• Decision nodes — узлы решения, они показывают решение, которое нужно принять.
• Chance nodes — вероятностные узлы, демонстрируют вероятность определенных результатов.
• End nodes — замыкающие узлы, показывают конечный результат пути решения.

Преимущества и недостатки методики дерева решений

Преимущества метода:

1. Деревья решений создаются по понятным правилам, они просты в применении и интерпретации.
2. Можно обрабатывать как непрерывные, так и качественные (дискретные) переменные.
3. Можно работать с пропусками в данных, деревья решений позволяют заполнить пустое поле наиболее вероятным значением.
4. Помогают определить, какие поля больше важны для прогнозирования или классификации.

Недостатки метода:

1. Есть вероятность ошибок в задачах классификации с большим количеством классов и относительно небольшим числом примеров для обучения.
2. Нестабильность процесса: изменение в одном узле может привести к построению совсем другого дерева, что связано с иерархичностью его структуры.
3. Процесс «выращивания» дерева решений может быть довольно затратным с точки зрения вычислений, ведь в каждом узле каждый атрибут должен раскладываться до тех пор, пока не будет найден наилучший вариант решения или разветвления. В некоторых алгоритмах используются комбинации полей, в таком случае приходится искать оптимальную комбинацию по «весу» коэффициентов. Алгоритм отсечения (или «обрезки») также дорогостоящий, так как необходимо сформировать и сравнить большое количество потенциальных ветвей.

Как создать дерево решений

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

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

Задачу будем исследовать через дерево решений.

Таким образом, у нас получилось завершенное дерево решений.

Правила классификации

Сначала определимся с терминами и их значениями.

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

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

Вот правила классификации из примера дерева решений про исследование новой планеты:

1. Если температура не находится в диапазоне от -0,15 °C до 99,85 °C, то выживание затруднительно.
2. Если температура находится в диапазоне от -0,15 °C до 99,85 °C, но нет воды, то выживание затруднительно.
3. Если температура находится в диапазоне от -0,15 °C до 99,85 °C, есть вода, но нет флоры и фауны, то выживание затруднительно.
4. Если температура находится в диапазоне от -0,15 °C до 99,85 °C, есть вода, есть флора и фауна, поверхность не подвержена штормам, то выживание возможно.
5. Если температура находится в диапазоне от -0,15 °C до 99,85 °C, есть вода, есть флора и фауна, но поверхность подвержена штормам, то выживание затруднительно.

Почему сложно построить идеальное дерево решений

В структуре дерева решений выделяют следующие компоненты:

1. Root Node, или корневой узел — тот, с которого начинается дерево, в нашем примере в качестве корня рассматривается фактор «температура».
2. Internal Node, или внутренний узел — узлы с одним входящим и двумя или более исходящими соединениями.
3. Leaf Node, или листовой узел — это заключительный элемент без исходящих соединений.

Когда создается дерево решений, мы начинаем от корневого узла, проверяем условия тестирования и присваиваем элемент управления одному из исходящих соединений. Затем снова тестируем условия и назначаем следующий узел. Чтобы считать дерево законченным, нужно все условия привести к листовому узлу (Leaf Node). Листовой узел будет содержать все метки класса, которые влияют на «за» и «против» в принятии решения.

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

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

Как использовать жадный алгоритм для построения дерева решений

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

Упрощенно алгоритм можно объяснить так:

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

Главный вопрос: «Как выбрать начальные условия для проверки?». Ответ заключается в значениях энтропии и прироста информации (информационном усилении). Рассказываем, что это и как они влияют на создание нашего дерева:

1. Энтропия — в дереве решений это означает однородность. Если данные полностью однородны, она равна 0; в противном случае, если данные разделены (50-50%), энтропия равна 1. Проще этот термин можно объяснить так — это то, как много информации, значимой для принятия решения, мы не знаем.
2. Прирост информации — величина обратная энтропии, чем выше прирост информации, тем меньше энтропия, меньше неучтенных данных и лучше решение.

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

Смотрите на примере. У нас есть большое количество таких данных:

Номер	Возраст (Age)	Уровень дохода (Income)	Студент (Student)	Кредитный рейтинг (CR)	Покупка компьютера (Buys Computer)
1		низкий (Low)	да	средний (Fair)	да
2	30-40	высокий (High)	нет	прекрасный (Excellent)	да
3	40	высокий (High)	нет	прекрасный (Excellent)	нет
4		средний (Medium)	нет	средний (Fair)	нет

Здесь может быть n деревьев решений, которые формируются из этого набора атрибутов.

Источник