26. Принятие решений методом «Дерево решений»

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

• Описание данных: Деревья решений позволяют хранить информацию о данных в компактной форме, вместо них мы можем хранить дерево решений, которое содержит точное описание объектов. 

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

• Регрессия: Если целевая переменная имеет непрерывные значения, деревья решений позволяют установить зависимость целевой переменной от независимых(входных) переменных. Например, к этому классу относятся задачи численного прогнозирования(предсказания значений целевой переменной).

 Другое определение: деревья решений - это способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение. Деревья решений разбивают данные на группы на основе значений переменных, в результате чего возникает иерархия операторов "ЕСЛИ - ТО", которые классифицируют данные.

Под правилом понимается логическая конструкция вида «если - то».

• Объект – некоторый пример, действие, шаблон, наблюдение.

• Атрибут – признак, свойство.

• Узел – внутренний узел дерева, узел проверки.

• Лист – конечный узел дерева, узел решения.

2 Построение деревьев Способ 1.

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

Пример 1. Компания рассматривает вопрос о строительстве завода. Возможны три варианта действий: а). Построить большой завод стоимостью Ст1 = 500 тысяч у.е. При этом варианте возможны большой спрос (годовой доход в размере Д1 = 200 тысяч у.е. в течение следующих 5 лет) с вероятностью p1 = 0,7 и низкий спрос (ежегодные убытки Д2 = 90 тысяч у.е.) с вероятностью р2 = 0,3. б). Построить маленький завод стоимостью Ст2 = 300 тысяч у.е. При этом варианте возможны большой спрос (годовой доход в размере Д3 = 100 тысяч у.е. в течение следующих 5 лет) с вероятностью p3 = 0,7 и низкий спрос (ежегодные убытки Д4 = 40 тысяч у.е.) с вероятностью р4 = 0,3. в). Отложить строительство завода на один год для сбора дополнительной информации, которая может быть позитивной или негативной с вероятностью p5 = 0,4 и p6 = 0,6 соответственно. В случае позитивной информации можно построить заводы по указанным выше расценкам, а вероятности большого и низкого спроса меняются на p7 = 0,8 и р8 = 0,2 соответственно. Доходы на последующие четыре года остаются прежними. В случае негативной информации компания заводы строить не будет. Нарисовав дерево решений, определим наиболее эффективную последовательность действий, основываясь на ожидаемых доходах. Решение. Строим дерево решений. Строим узел 1, из которого исходят три заявленные в условии варианты. Обозначаем эти ветви пунктиром, поскольку это – возможные решения. На концах ветвей ставим узлы-исходы, заключаем их в круг и обозначаем буквами А, В и т.д. Рисуем из этих узлов-исходов ветви с возможными исходами при выборе того или иного варианта из условия. Под каждой ветвью подписываем вероятности соответствующих исходов. На концах каждой ветви, не закрытой новым узлом, выставляем доходы и убытки, умноженные (исходя из условия) на время (годы из условия). На ветвях (возможные решения) ставим стоимость строительства со знаком «-», так как это расходы компании. Убытки на концах «открытых» ветвей также пишем со знаком «-». Рис.1 – Дерево решений для примера 1. Первый этап построения Далее считаем ожидаемые стоимостные оценки узлов. Ожидаемая стоимостная оценка узла А равна: ЕМV(А) = 0,8 х 1000 + 0,2 х (-450) -500 = 210. EMV( B) = 0,8 х 500 + 0,2 х (-200) - 300 = 60. EMV( D) = 0,9 x 800 + 0,1 x (-360) - 500 = 184. EMV(E) = 0,9 x 400 + 0,1 х (-160) - 300 = 44. Для узлов принятия решения 2 (второй уровень, условно) выбираем максимальную оценку: EMV(2) = max {EMV( D), EMV( E)} = max {184, 44} = 184 = EMV(D). Поэтому в узле 2 отбрасываем возможное решение «маленький завод». EMV(C) = 0,7 x 184 + 0,3 x 0 = 128,8. Для узла принятия решения 1 – узла принятия окончательного решения, аналогично выбираем максимальную оценку на других узлах. EMV(1) = max {ЕМV(A), EMV(B), EMV(C)} = max {210; 60; 128,8} = 210 = EMV(А). Поэтому в узле 1 выбираем решение «большой завод». Исследование проводить не нужно. Строим большой завод. Ожидаемая стоимостная оценка этого наилучшего решения равна 210 тысяч у.е. Ответ: наиболее подходящее решение – решение строить большой завод. Рис.2 – Дерево решений со стоимостными оценками В рассмотренном примере мы произвели отсечение ветвей в узле 2. И далее в задаче мы отсекаем те ветви и узлы, стоимостные оценки которых не приемлемы для принятия наиболее выгодного решения.