Дерево решений — это метод, который применяется для принятия решений в условиях неопределенности и риска. Данный метод используется в случае, когда нужно принимать ряд последовательных решений. Дерево решений является графическим методом, который позволяет скоординировать элементы принятия решения, вероятные стратегии (А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%
Рисунок 4 — Дерево решений с ожидаемыми значениями результатов(EV), долларов
Дополнительно учтем в примере, приведенном выше, изменение в зависимости от срока окупаемости стоимости проекта.
Установим, что сумма средств, необходимых для поиска нефти, расходуется сразу же. Если находим нефть, то все средства, вложенные в нефтеразведку покрываются сразу же, а доходы от продаж добытой нефти поступают через два года. Чтобы корректно учитывать все данные платежи и поступления, разбросанные во времени, необходимо привести все суммы денежных средств к текущей стоимости.
Установим, что ставка дисконтирования будет принимать значение, равное 20 процентов, тогда таблица 2 будет представлена в следующем виде (таблица 3), а дерево решений (рисунок 4) – в виде, показанном на рисунке 5.
Таблица 3 — Ожидаемая приведенная стоимость и результаты решения «Когда вставать и как работать» с учетом коэффициента дисконтирования
Решение
Спать допоздна
Вставать рано
Работать усердно
Вероятность (найти нефть) = 5% (1 – Вероятность) (не найти нефть) = 95%
Самая эффективная последовательность решений та же (отображен жирной линией путь, который совпадает с решением «Вставай рано» + «Работай усердно», однако изменилось значение ожидаемого выигрыша (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 — Дерево принятия решений при определении стратегии организации
Представленная схема решения немного упрощена, так как мы не рассматривали варианты привлечения резервов по выпуску продукта одного вида при минимальном уровне спроса для производства продукции другого вида, лимиты по вложениям денежных средств (в условиях задачи для этого недостаточно данных).
Источник
Методы классификации и прогнозирования. Деревья решений
Метод деревьев решений ( decision trees ) является одним из наиболее популярных методов решения задач классификации и прогнозирования. Иногда этот метод Data Mining также называют деревьями решающих правил , деревьями классификации и регрессии.
Как видно из последнего названия, при помощи данного метода решаются задачи классификации и прогнозирования.
Если зависимая, т.е. целевая переменная принимает дискретные значения, при помощи метода дерева решений решается задача классификации.
Если же зависимая переменная принимает непрерывные значения, то дерево решений устанавливает зависимость этой переменной от независимых переменных, т.е. решает задачу численного прогнозирования.
Впервые деревья решений были предложены Ховилендом и Хантом (Hoveland, Hunt) в конце 50-х годов прошлого века. Самая ранняя и известная работа Ханта и др., в которой излагается суть деревьев решений — «Эксперименты в индукции» («Experiments in Induction «) — была опубликована в 1966 году.
В наиболее простом виде дерево решений — это способ представления правил в иерархической, последовательной структуре. Основа такой структуры — ответы «Да» или «Нет» на ряд вопросов.
На рис. 9.1 приведен пример дерева решений, задача которого — ответить на вопрос: «Играть ли в гольф?» Чтобы решить задачу, т.е. принять решение, играть ли в гольф, следует отнести текущую ситуацию к одному из известных классов (в данном случае — «играть» или «не играть»). Для этого требуется ответить на ряд вопросов, которые находятся в узлах этого дерева, начиная с его корня.
Первый узел нашего дерева «Солнечно?» является узлом проверки , т.е. условием. При положительном ответе на вопрос осуществляется переход к левой части дерева, называемой левой ветвью , при отрицательном — к правой части дерева. Таким образом, внутренний узел дерева является узлом проверки определенного условия. Далее идет следующий вопрос и т.д., пока не будет достигнут конечный узел дерева, являющийся узлом решения . Для нашего дерева существует два типа конечного узла : «играть» и «не играть» в гольф.
В результате прохождения от корня дерева (иногда называемого корневой вершиной) до его вершины решается задача классификации, т.е. выбирается один из классов — «играть» и «не играть» в гольф.
Целью построения дерева решения в нашем случае является определение значения категориальной зависимой переменной.
Итак, для нашей задачи основными элементами дерева решений являются:
Корень дерева: «Солнечно?»
Внутренний узел дерева или узел проверки : «Температура воздуха высокая?», «Идет ли дождь?»
Лист , конечный узел дерева, узел решения или вершина : «Играть», «Не играть»
Ветвь дерева (случаи ответа): «Да», «Нет».
В рассмотренном примере решается задача бинарной классификации , т.е. создается дихотомическая классификационная модель. Пример демонстрирует работу так называемых бинарных деревьев.
В узлах бинарных деревьев ветвление может вестись только в двух направлениях, т.е. существует возможность только двух ответов на поставленный вопрос («да» и «нет»).
Бинарные деревья являются самым простым, частным случаем деревьев решений. В остальных случаях, ответов и, соответственно, ветвей дерева, выходящих из его внутреннего узла , может быть больше двух.
Рассмотрим более сложный пример. База данных , на основе которой должно осуществляться прогнозирование, содержит следующие ретроспективные данные о клиентах банка, являющиеся ее атрибутами: возраст, наличие недвижимости, образование, среднемесячный доход, вернул ли клиент вовремя кредит . Задача состоит в том, чтобы на основании перечисленных выше данных (кроме последнего атрибута) определить, стоит ли выдавать кредит новому клиенту.
Как мы уже рассматривали в лекции, посвященной задаче классификации, такая задача решается в два этапа: построение классификационной модели и ее использование.
На этапе построения модели, собственно, и строится дерево классификации или создается набор неких правил . На этапе использования модели построенное дерево , или путь от его корня к одной из вершин, являющийся набором правил для конкретного клиента, используется для ответа на поставленный вопрос «Выдавать ли кредит ?»
Правилом является логическая конструкция, представленная в виде «если : то :».
На рис. 9.2. приведен пример дерева классификации, с помощью которого решается задача «Выдавать ли кредит клиенту?». Она является типичной задачей классификации, и при помощи деревьев решений получают достаточно хорошие варианты ее решения.
Как мы видим, внутренние узлы дерева (возраст, наличие недвижимости, доход и образование) являются атрибутами описанной выше базы данных . Эти атрибуты называют прогнозирующими, или атрибутами расщепления (splitting attribute ). Конечные узлы дерева, или листы, именуются метками класса, являющимися значениями зависимой категориальной переменной «выдавать» или «не выдавать» кредит .
Каждая ветвь дерева, идущая от внутреннего узла , отмечена предикатом расщепления . Последний может относиться лишь к одному атрибуту расщепления данного узла. Характерная особенность предикатов расщепления : каждая запись использует уникальный путь от корня дерева только к одному узлу-решению. Объединенная информация об атрибутах расщепления и предикатах расщепления в узле называется критерием расщепления (splitting criterion ) [33].
На рис. 9.2. изображено одно из возможных деревьев решений для рассматриваемой базы данных . Например, критерий расщепления «Какое образование?», мог бы иметь два предиката расщепления и выглядеть иначе: образование «высшее» и «не высшее». Тогда дерево решений имело бы другой вид.
Таким образом, для данной задачи (как и для любой другой) может быть построено множество деревьев решений различного качества, с различной прогнозирующей точностью.
Качество построенного дерева решения весьма зависит от правильного выбора критерия расщепления . Над разработкой и усовершенствованием критериев работают многие исследователи.
Метод деревьев решений часто называют «наивным» подходом [34]. Но благодаря целому ряду преимуществ, данный метод является одним из наиболее популярных для решения задач классификации.
