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

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

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

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

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

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

Реферат

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

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

Выполнил:

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

Баев Андрей

Принял:

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

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

Оглавление

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

При построении деревьев решений особое внимание уделяется следующим вопросам: выбору критерия атрибута, по которому пойдет разбиение, остановки обучения и отсечения ветвей <#"justify">1.1.2 Правило остановки

В дополнение к основному методу построения деревьев решений были предложены следующие правила:

Использование статистических методов для оценки целесообразности дальнейшего разбиения, так называемая «ранняя остановка <#"justify">1.2 Преимущества использования деревьев решений

Рассмотрев основные проблемы, возникающие при построении деревьев, было бы несправедливо не упомянуть об их достоинствах:

быстрый процесс обучения;

генерация правил в областях, где эксперту трудно формализовать свои знания;

извлечение правил на естественном языке;

интуитивно понятная классификационная модель;

Для более наглядного представления описанного процесса выбора оптимальной альтернативы на дереве решений рассмотрим пример задачи для конкретного числового набора параметров.

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

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

Для удобства идентификации результатов выбора введем следующее правило индексации отмеченного двумерного бинарного выбора ЛПР.

Таблица1-Индексации вариантов управляемого выбора ЛПР

Выбор: iРегиона Выбор: jСферы деятель0периферийный0бюджетная1столичный1бизнес

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

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

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

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

(i=0-перефирийный,i=1-столичный регион)

(j=0-бюджетнаясфера,j=1-бизнес деятельность)

(k=0-неуспешный,k=1-успешный результат трудоустройства)

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

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

Известна статистика успешной деятель (и неуспешной 1-Cij1), результаты которой возможно описать на основе следующей таблицей:

Таблица2-Вероятности реализации успешной и неуспешной деятельности

РегионСферадеятельностиСтатистикауспехауспех:Cij1неуспех:Cij0столичныйбизнесC111=PбзC110=1-C111бюджетC101=PбдC100=1-C101периферийныйбизнесC011=PбзC010=1-C011бюджетC001=PбдC000=1-C001РегионСфера деятельностиСтатистика успехауспех:Cij1неуспех:Cij0=1-Cij1столичныйбизнесC111=0,6C110=0,4бюджетC101=0,7C100=0,3периферийныйбизнесC011=0,9C010=0,1бюджетC001=0,95C000=0,05

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

Обозначим через Xijk-среднегодовые доходы при полной занятости при работе в i-ом регионе, j-ой сфере деятель и k-ом показателе результатов успешности деятельности (Xij1-в случае успеха и Xij0-неудачи),т.е.систематизируем реализацию уровней дохода выпускника в зависимости от реализованных им выборов альтернатив трудоустройства.

Среднегодовые доходы при полной занятости заданы в программе MicrosoftExcel.

для периферийного региона.

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

X001X011X101X11137214778

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

РегионСфера деятельностиСреднегодовые доходыуспех:Xij1неуспех:Xij0столичныйбизнесX111=78X110=20бюджетX101=47X100=20периферийныйбизнесX011=21X010=20бюджетX001=37X000=20

Известны также среднегодовые доходы 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/cybernetics>. М. иностранная литература, 1963

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

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