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

МИНОБРНАУКИРОССИИ Федеральное государственное автономное образовательное Учреждение высшего образования

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

Реферат По дисциплине: Системный анализ и принятие решений тема:"Реализация стохастического выбора на дереве решений"

Выполнил:

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

Баев Андрей Принял:

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

Ростов-на-Дону, 2015 г Оглавление

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

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

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

1.1.2 Правило остановки

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

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

1.3 Области применения деревьев решений

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

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

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

2.2.1 Первый этап

2.2.2 Второй этап

2.2.3 Третий этап Заключение Список Использованных Источников

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

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

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

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

Были разработаны различные критерии: теоретико-информационный критерий, статистический критерийи др.

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

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

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

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

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

1.1.3 Правило отсечения Очень часто алгоритмы построения деревьев решений дают сложные деревья, которые «переполнены данными», имеют много узлов и ветвей. Такие «ветвистые» деревья очень трудно понять. К тому же ветвистое дерево, имеющее много узлов, разбивает обучающее множество на все большее количество подмножеств, состоящих извсе меньшего количества объектов.

Для решения вышеописанной проблемы часто применяется так называемое отсечение ветвей (pruning).

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

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

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

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

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

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

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

высокая точность прогноза, сопоставимая с другими методами (статистика, нейронные сети);

построение непараметрических моделей.

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

1.3 Области применения деревьев решений Деревья решений являются прекрасным инструментом в системах поддержки принятия решений, интеллектуального анализа данных (datamining).

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

Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.

Промышленность.Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например проверка качества сварки) и т. д.

Медицина.Диагностика различных заболеваний.

Молекулярная биология. Анализ строения аминокислот.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Известны среднегодовые доходы при полной занятости (в случае успешной или неуспешной деятельности).

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

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

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

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

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

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

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

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

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

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

d11=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;

d01=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. Morgan Kaufmann Publishers 1993.

3. S.Murthy. Automatic construction of decision trees from data: A Multi-disciplinary survey.1997.

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

5. Machine Learning, Neural and Statistical Classification. Editors D. Mitchie et.al. 1994.

6. К. Шеннон. Работы по теории информации и кибернетике. М. Иностранная литература, 1963

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