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

Дерево решений рисуется слева на право. По сути, это граф, который включает в себя узлы, вершины и ветви, но незаконченный. При его построении используются такие фигуры, как прямоугольник, который означает решение, принимаемое нами (ЛПР), и окружность, где решение зависит от случая.

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

Двигаясь от самого первого прямоугольника, выбираем 2 пути – либо A1, либо A2. Внутри каждого прямоугольника и окружности – результат. На лучах необходимо писать вероятность события (A3, A4, A5, A6, A7), после этого посчитать m_0.

Если X3>X4, то в прямоугольник запишем X3. А если X2>X3, то в самом начальном прямоугольнике запишем X2.

= m₀⁵*p₅+X6*p₆+m₀⁷*p₇ – данная операция называется «свёртка». Процедуры свертки в рамках метода дерева решений реализуются именно для вершин «круглого» типа, для которых, напомним, особенности дальнейшей траектории реализации конечного экономического результата проекта зависят не от ЛПР, а от случая. При этом указанные процедуры сначала реализуются для концевых вершин «круглого» типа соответствующего дерева решений, а также для «круглых» вершин, за которыми следуют концевые «черные» вершины с указанным конкретным численным результатом в рамках анализируемых логистических процессов.

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

Можно предложить следующую последовательность сбора данных для построения "дерева решений":

• определение состава и продолжительности фаз жизненного цикла проекта;

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

• определение времени наступления ключевых событий;

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

• определение вероятности принятия каждого решения;

• определение стоимости каждого этапа осуществления проекта (стоимости работ между ключевыми событиями) в текущих ценах.

На основании полученных данных строится "дерево решений", структура которого содержит узлы, представляющие собой ключевые события (точки принятия решений), и ветви, соединяющие узлы, – работы по реализации проекта.

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

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

На данном рисунке представлено решение задачи: в случае, если книга имеет успех, прибыль равняется 8 млн. долл., а при провале -- соответственно --8 млн. долл. Поскольку менеджеры в случае провала книги фильм снимать не будут, то худший возможный результат по-прежнему составляет потерю не 8 млн. долл., а 0 долл. По причине того, что менеджеры в случае провала книги примут решение не продолжать работу над проектом, ожидаемая величина прибыли через год, считая с сегодняшней даты, возрастает с 2 млн. долл. до 4 млн. долл. Таким образом, ожидаемая величина прибыли от проекта, вследствие увеличения в два раза разброса возможных в будущем результатов, удваивается. С такой точки зрения увеличение неопределенности в возможных в будущем доходах по проекту приводит к росту его стоимости.

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

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

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

Рассмотрим для наглядности пример использования данного метода.

Пусть необходимо выбрать лучший из трех возможных инвестиционных проектов: ИП1, ИП2, ИПЗ. Допустим, что для своего осуществления упомянутые проекты требуют вложения средств в размерах 200, 300 и 500 млн руб. и могут дать прибыль в размере 100, 200 и 300 млн руб. Риск потери средств по этим проектам характеризуется вероятностями на уровне 10, 5 и 20% соответственно. Какой проект лучше?

Ответить на вопрос чисто математическими средствами трудно. С помощью "дерева решений" этот ответ найти очень просто. "Дерево решений" для условий данного примера представлено на рис. 2.

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

Эти математические ожидания и поставлены нами в кружки, изображающие узлы возникновения неопределенностей.

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

Рассмотрим другой пример применения метода дерева решений и решим следующую задачу.

Пример 1. Решить методом дерева решений, какую сумму вы потратите на продукты в определённый день.

Решение. Альтернативные события на первом этапе: гости придут и гости не придут. Отображаем эти события в дереве решений в виде вершин событий (кружочков). Примем, что, если гости придут, на продукты придётся потратить крупную сумму. Это один из исходов (конечных узлов в дереве решений) в данной задаче.

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

Дерево решений для этой задачи будет следующим:

Но даже для этой только что рассмотренной задачи альтернативные события могут быть связаны с некоторыми вероятностями. В частности, вы можете по своему опыту или же от одного из возможных гостей знать вероятность того, что гости к вам придут. Предположим, вероятность этого события равна 0,3. Тогда от единицы отнимем 0,3 и получим 0,7 - вероятность того, что гости не придут. События, следующие из этого события, также могут быть связаны с вероятностями.

Предположим, вы находитесь не дома и не имеете возможности посмотреть в холодильник и кухонные шкафы. Или вообще, все эти события произойдут только через несколько дней. Но вы эксперт по своему домашнему хозяйству, а это значит, что вы перед походом в магазин уже оцениваете вероятности этих двух альтернативных событий. Предположим, вероятность того, что в доме много продуктов, равна 0,4. Тогда 1 - 0,4 = 0,6 - вероятность того, что в доме мало продуктов. Итак, имея оценки вероятностей альтернативных событий, мы, решая ту или иную задачу методом дерева решений, можем прогнозировать исходы.

Методика "Разделяй и властвуй"

Методика основана на рекурсивном разбиении множества объектов из обучающей выборки на подмножества, содержащие объекты, относящиеся к одинаковым классам.

Сперва выбирается независимая переменная, которая помещается в корень дерева.

Из вершины строятся ветви, соответствующие всем возможным значениям выбранной независимой переменной.

Множество объектов из обучающей выборки разбивается на несколько подмножеств в соответствии со значением выбранной независимой переменной.

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

Относительно обучающей выборки T и множества классов C возможны три ситуации:

множество Т содержит один или более объектов, относящихся к одному классу cr. Тогда дерево решений для T - это лист, определяющий класс cr;

множество Т не содержит ни одного объекта (пустое множество). Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества, отличного от Т, например из множества, ассоциированного с родителем;

Множество Т содержит объекты, относящиеся к разным классам. В этом случае следует разбить множество Т на некоторые подмножества. Для этого выбирается одна из независимых переменных xh, имеющая два и более отличных друг от друга значений ; Множество Т разбивается на подмножества T1,T2,...,Tn, где каждое подмножество Ti содержит все объекты, у которых значение выбранной зависимой переменной равно . Далее процесс продолжается рекурсивно для каждого подмножества до тех пор, пока значение зависимой переменной во вновь образованном подмножестве не будет одинаковым (когда объекты принадлежат одному классу). В этом случае процесс для данной ветви дерева прекращается.

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

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

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

Другой проблемой при построении дерева является проблема остановки его разбиения. Методы её решения:

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

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

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

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

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