Реализация стохастического выбора на дереве решений

Реализация стохастического выбора на дереве решений

МИНОБРНАУКИРОССИИ

Федеральное государственное автономное образовательное

Учреждение высшего образования

«Южный федеральный университет»

Реферат

По дисциплине: Системный анализ и принятие решений

тема:«Реализация стохастического выбора на дереве решений»

Выполнил:

Студент группы3-2

Баев Андрей

Принял:

ЗолотаревА.А.

Ростов-на-Дону,2015г

Оглавление

1. Дерево решений

.1 Этапы построения деревьев решений

.1.1 Правило разбиения

.1.2 Правило остановки

.1.3 Правило отсечения

.2 Преимущества использования деревьев решений        

. Пример реализации дерева решений

.1 Постановка задачи многошагового стохастического выбора в предметной области

.2 Математическая постановка задачи

.2.1 Первый этап

.2.2 Второй этап

.2.3 Третий этап

Заключение

Список Использованных Источников

. Дерево решений

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

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

.1 Этапы построения деревьев решений

При построении деревьев решений особое внимание уделяется следующим вопросам: выбору критерия атрибута, по которому пойдет разбиение, остановки обучения и отсечения ветвей <#"880481.files/image001.gif">для периферийного региона.

для столичного региона.

Таблица3-Среднегодовые доходы при полной занятости

Известны также среднегодовые доходы Sijk-при работе в i-ом регионе ,j-ой сфере деятельности и k-ом показателе результатов успешности деятельности.

Введем также обозначения: dij-как математическое ожидание среднегодового дохода при выборе работы в i-ом регионе, в j-ой сфере деятельности.

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

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

Дерево решений ,соответствующее поставленной задаче отражено на рисунке

Узлы1;2;3 являются узлами управляемого выбора ЛПР,в которых реализуется выбор региона и сферы деятельности. Остальные узлы(4-7) относятся к классу неуправляемого выбора,в которых исход определяется стохастическим характером процессов достижения успешной или неуспешной деятельности с вероятными локальными потоковыми доходами Sijk=Cijk*Xijk.

Листьям дерева, пронумерованным с 8-го по 10-ый ,поставлены в соответствие заданные значения Xijk.-возможный среднегодовой доход при работе в i-ом регионе, j-ой сфере деятельности и k-ом показателе результатов успешности деятельности.

Для нахождения оптимального решения на основе критерия ожидаемого значения предварительно определим все возможные ожидаемые доходы dij, представимые на графе «дереворешений» как их математическое ожидание в виде сумм ожидаемых потоков, т.е.:=s111+s110=x111*C111+x110*(1-C111)=78*0.6+0.4*20=54.8;

d10=s101+s100=x101*C101+x100*(1-C101)=47*0.7+0.3*20=38.9;=s011+s010=x011*C011+x010*(1-C011)=21*0.9+0.1*20=20.9;

d00=s001+s000=x001*C001+x000*(1-C001)=37*0.95+0.05*20=36.15.

Далее получим условнооптимальные доходы (потоки) на уровне регионального выбора:

Откуда выводим значения максимального ожидаемого дохода

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

Таким образом, оптимальный путь на дереве решений необходимо проходит через узлы1→2→4 и соответствует единственному оптимальному плану выбора региона и сферы деятельности ЛПР,обеспечивающему максимальный ожидаемый доход в объёме 54.8ед. и реализуемому в столичном регионе в бизнес сфере деятельности.

стохастический выбор решение

Заключение

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

1.ЗолотаревА.А.Многошаговыйстохастическийвыборнаграфах.Учебноепособие-Ростов-на-Дону.Издательство Южного федерального университета,2015г.2. J. Ross Quinlan. C4.5: Programs for Machine learning <http://www.basegroup.ru/glossary_ajax/definitions/machine_learning>. Morgan Kaufmann Publishers 1993.

. S.Murthy. Automatic construction of decision trees <http://www.basegroup.ru/glossary_ajax/definitions/decision_trees> from data: A Multi-disciplinary survey.1997.

4. W. Buntine. A theory of classification rules.1992.

. Machine Learning, Neural <http://www.basegroup.ru/glossary_ajax/definitions/neuron> and Statistical Classification. Editors D. Mitchie et.al. 1994.

. К. Шеннон. Работы по теории информации <http://www.basegroup.ru/glossary_ajax/definitions/information_theory> и кибернетике <http://www.basegroup.ru/glossary_ajax/definitions/cybernetics>. М. Иностранная литература, 1963

. С.А. Айвазян, В.С Мхитарян Прикладная статистика и основы эконометрики, М. Юнити, 1998