Учебная работа. Реализация стохастического выбора на дереве решений
Реализация стохастического выбора на дереве решений
МИНОБРНАУКИРОССИИ
Федеральное государственное автономное образовательное
Учреждение высшего образования
«Южный федеральный университет»
Реферат
По дисциплине: Системный анализ и принятие решений
тема:«Реализация стохастического выбора на дереве решений»
Выполнил:
Студент группы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.
. К. Шеннон. работы по теории информации
. С.А. Айвазян, В.С Мхитарян Прикладная статистика и основы эконометрики, М. Юнити, 1998