Методы деревья решений (лекция 4)

1.

Методы деревья решений
1.
2.
3.
Характеристика метода ДР
Принципы построения ДР
Оценка альтернатив

2.

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

3.

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

4.

Метод дерева решений
Цена
фирмы
Цена
конкурента
высокая
Средняя
10
170
высокая
Средняя
50
Средняя
низкая
Конкуренция
Низкая
(0,8)
Сбыт
170
Отсутствие
конкуренции
Средняя
низкая
(0,2)
Цена фирмы
650
35
высокая
- 10
Депозит
0,4
150
0,5
0,1
-50
-250
0,1
200
0,6
100
0,3
-100
0,1
150
0,2
50
0,7
-50
низкая
Высокая
50
Отдача
(в тыс.руб.)
Средняя
высокая
650
450
низкая
250

5.

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

6.

ПРИМЕР Метода дерева решений
Фирма должна принять решение, израсходовать ли ей
350000 руб.
на новый проект (сбыт новой продукции) или
инвестировать средства куда-либо еще с 10процентной прибылью.
Если брать последовательность слева направо, то первое
решение (квадрат) состоит в том, заниматься ли
сбытом продукции или нет.
Если решение – нет, то отдача решения составит 35000 руб.
(10%) от альтернативных инвестиций (банковский
депозит).
Если решение – да (заниматься сбытом), то следующим
событием (большой кружок) будет неконтролируемая
ситуация: наличие или отсутствие конкуренции на
рынке.
Вероятность каждой альтернативы (указана в скобках) –
соответственно (0,8) и (0,2).

7.

ПРИМЕР Метода дерева решений
Обозначения:
- ответвления, обозначенные квадратами
представляют стратегии;
- ответвления, обозначенные кружками – внешние
условия.
Поскольку ЛПР осуществляет полный контроль над
тем, какую стратегию выбрать, ответвления из
квадратов не имеют вероятностей.
В то же время ответвления из кружков имеют
вероятность, т.к. внешние условия не
контролируются фирмой. Сумма вероятностей
всех ответвлений из одного кружка равна
единице (1,0).

8.

Продолжение ПРИМЕРА
Если конкуренция отсутствует, то единственное оставшееся
решение должно состоять в следующем:
какую назначить цену за продукцию:
• (высокую,
• среднюю
• или низкую).
Эти три ответвления имеют каждое – свою отдачу
(обозначены в конце ответвления: 650 тыс. руб., 450 и
250 тыс. руб.).
Далее каждое ответвление вновь подразделяется на три,
обозначая намерения конкурента назначить высокую,
среднюю или низкую цену.
Дерево решения представляет графическую форму
ожидания того, что цена, которую назначит конкурент,
будет зависеть от цены, которую устанавливает фирма.
А последующая прибыль фирмы зависит от того, какую
цену назначит конкурент.

9.

Продолжение ПРИМЕРА
Поскольку каждое решение зависит от оценки
событий, которые будут происходить позднее,
анализ дерева решения начинается с конца
последовательности и продвигается в обратном
направлении.
Начиная с верхней правой части рисунка , вычисляем
предполагаемую стоимость варианта, если цена
фирмы высокая и если имеет место конкуренция:
(150*0,4) + (-50*0,5) + (-250*0,1) = 10
Аналогично исчисляется предполагаемая стоимость
средней и низкой цены.
Выбирается альтернатива с наибольшей стоимостью:
50 тыс.руб. – соответствует альтернативе со
средней ценой. Она обозначается в блоке
решения, а другие два ответвления
прочеркиваются: //.
При альтернативном состоянии отсутствия
конкуренции (нижнее ответвление) назначаем
высокую цену.
Теперь находим предполагаемую стоимость для
первого события: (50*0,8)+(650*0,2)=170 тыс.руб.
Теперь фирма готова принять решение: выбрать
проект связанный с реализацией товаров.

10.

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

11.

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

12.

Методологии логического анализа систем
Суть логического анализа - поиск причинно-следственных
связей между проблемами и их причинами (или
следствиями), между целями и средствами их достижения.
В его основе лежит модель типа слоев.
Анализу при этом подвергается не проблемосодержащая
система, а непосредственно проблема — каковы логические
причины ее возникновения, к каким последствиям она
может привести, каковы пути ее устранения.
При проектировании проблеморазрешающей системы
анализу подвергается не воображаемая проектируемая
система, а цель системы — с помощью каких средств она
может быть достигнута, какие решения могут привести к
цели и к разрешению проблемы.

13.

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

14.

Обобщенная схема построения дерева
целей

15.

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

16.

3. Выбор формальной модели. Из набора типовых оснований
декомпозиции, являющихся формальными моделями системы,
эксперт выбирает наиболее подходящее основание.
Примеры формальных моделей: «Жизненный цикл»,
«Структурные элементы деятельности», «Управленческий цикл».
Нужно уточнить, что система, с которой связан объект анализа, и
система, по модели которой проводится декомпозиция, не
обязательно совпадают. Например, одна из этих систем может
являться подсистемой или надсистемой для другой.
4. Детализация основания декомпозиции. Формальную модель
необходимо наполнить содержанием с учетом выбранной
области анализа и целевой системы. Например, необходимо
конкретизировать этапы жизненного цикла производства
продукта или цикла управления, составить конкретные
классификаторы структурных элементов для рассматриваемого
вида деятельности.

17.

5. Операция декомпозиции. Для каждой подсистемы,
выделяемой в соответствии с выбранным основанием
декомпозиции, формулируется подцель, связанная с
данной подсистемой и обеспечивающая достижение
декомпозируемой цели.
6. Проверка. Полученные подцели нижнего уровня
проверяются на элементарность. Если все «листья»
дерева можно считать элементарными (простыми,
понятными, реализуемыми), то построение дерева
целей заканчивается.

18.

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

19.

Последовательность уровней дерева:
«глобальная цель» — «конечные продукты» —
«целеполагающие системы» — «жизненный цикл
производства» — «состав системы (ресурсы)» —
«управленческий цикл»

20.

Пример дерева целей

21.

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

22.

Использование методологии для поиска
причин возникновения проблемы

23.

Причинно-следственная диаграмма
("рыбий скелет")