Метод построения дерева решений

Размещено на http://www.allbest.ru/

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

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Чувашский государственный университет имени И.Н. Ульянова»

Факультет дизайна и компьютерных технологий

Кафедра компьютерных технологий

РЕФЕРАТ

по дисциплине Теория принятия решений

на тему Метод построения дерева решений

Выполнила: студентка гр. ДиКТ-41-12

Краснова О.И.

Проверила: Егорова Ю.Н.

Чебоксары 2014

Содержание

Введение

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

1.1 Дерево решений и область его применения

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

2. Методы построения дерева решений

2.1 Методика "Разделяй и властвуй"

2.2 Алгоритм C4.5

2.3 Алгоритм покрытия

3. Практическая часть. Построение дерева решений на примере

Заключение

Список используемой литературы

Введение

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

Актуальность темы исследования определяется тем, что метод дерева решений имеет большое значение для разработки эффективных управленческих решений. Метод деревьев решений является одним из наиболее популярных методов, используемых на этапе выбора альтернатив.

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

Объектом исследования служит метод дерева решений как процесс выбора альтернативного решения. Предметом исследования являются теоретические и методологические аспекты применения метода дерева решений.

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

1.1 Дерево решений и область его применения

Одним из популярных методов принятия решений являются деревья решений. С помощью этого метода можно принимать решения:

- по социальным и макроэкономическим вопросам;

- по развитию фирмы или в банковской сфере.

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

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

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

Под правилом понимается логическая конструкция, представленная в виде "если... то...".

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

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

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

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

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

- определение состава и продолжительности фаз жизненного цикла проекта;

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

- определение времени наступления ключевых событий;

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

- определение вероятности принятия каждого решения;

- определение стоимости каждого этапа осуществления проекта (стоимости работ между ключевыми событиями) в текущих ценах.

На основании полученных данных строится «дерево решений», структура которого содержит узлы, представляющие собой ключевые события (точки принятия решений), и ветви, соединяющие узлы, - работы по реализации проекта.

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

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

Рис. 1 «Дерево решений»

На данном рисунке представлено решение задачи: в случае, если книга имеет успех, прибыль равняется 8 млн. долл., а при провале -- соответственно --8 млн. долл. Поскольку менеджеры в случае провала книги фильм снимать не будут, то худший возможный результат по-прежнему составляет потерю не 8 млн. долл., а 0 долл. По причине того, что менеджеры в случае провала книги примут решение не продолжать работу над проектом, ожидаемая величина прибыли через год, считая с сегодняшней даты, возрастает с 2 млн. долл. до 4 млн. долл. Таким образом, ожидаемая величина прибыли от проекта, вследствие увеличения в два раза разброса возможных в будущем результатов, удваивается. С такой точки зрения увеличение неопределенности в возможных в будущем доходах по проекту приводит к росту его стоимости.

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

Деревья решений успешно применяются для решения практических задач в следующих областях:

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

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

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

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

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

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

Деревья решений дают возможность извлекать правила из базы данных на естественном языке. Пример правила: Если Возраст > 35 и Доход > 200, то выдать кредит.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Остановка - такой момент в процессе построения дерева, когда следует прекратить дальнейшие ветвления.

Один из вариантов правил остановки - "ранняя остановка", она определяет целесообразность разбиения узла. Преимущество использования такого варианта - уменьшение времени на обучение модели. Однако здесь возникает риск снижения точности классификации. Поэтому рекомендуется "вместо остановки использовать отсечение".

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

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

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

Сокращение дерева или отсечение ветвей. Решением проблемы слишком ветвистого дерева является его сокращение путем отсечения некоторых ветвей.

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

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

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

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

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

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

2. Методы построения дерева решений

2.1 Методика "Разделяй и властвуй"

Методика основана на рекурсивном разбиении множества объектов из обучающей выборки на подмножества, содержащие объекты, относящиеся к одинаковым классам.

Сперва выбирается независимая переменная, которая помещается в корень дерева.

Из вершины строятся ветви, соответствующие всем возможным значениям выбранной независимой переменной.

Множество объектов из обучающей выборки разбивается на несколько подмножеств в соответствии со значением выбранной независимой переменной.

Таким образом, в каждом подмножестве будут находиться объекты, у которых значение выбранной независимой переменной будет одно и то же.

Относительно обучающей выборки T и множества классов C возможны три ситуации:

множество Т содержит один или более объектов, относящихся к одному классу cr. Тогда дерево решений для T - это лист, определяющий класс cr;

множество Т не содержит ни одного объекта (пустое множество). Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества, отличного от Т, например из множества, ассоциированного с родителем;

Множество Т содержит объекты, относящиеся к разным классам. В этом случае следует разбить множество Т на некоторые подмножества. Для этого выбирается одна из независимых переменных xh, имеющая два и более отличных друг от друга значений ; Множество Т разбивается на подмножества T1,T2,...,Tn, где каждое подмножество Ti содержит все объекты, у которых значение выбранной зависимой переменной равно. Далее процесс продолжается рекурсивно для каждого подмножества до тех пор, пока значение зависимой переменной во вновь образованном подмножестве не будет одинаковым (когда объекты принадлежат одному классу). В этом случае процесс для данной ветви дерева прекращается.

При использовании данной методики построение дерева решений будет происходить сверху вниз. Большинство алгоритмов, которые её используют, являются "жадными алгоритмами". Это значит, что если один раз переменная была выбрана и по ней было произведено разбиение, то алгоритм не может вернуться назад и выбрать другую переменную, которая дала бы лучшее разбиение.

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

Общее правило для выбора переменной для разбиения: выбранная переменная должны разбить множество так, чтобы получаемые в итоге подмножества состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому, т.е. чтобы количество объектов из других классов ("примесей") в каждом из этих множеств было минимальным.

Другой проблемой при построении дерева является проблема остановки его разбиения. Методы её решения:

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

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

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

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

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

2.2 Алгоритм C4.5

Представляет собой усовершенствованный вариант алгоритма ID3. Среди улучшений стоит отметить следующие:

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

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

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

Алгоритм C4.5 решает эту проблему путём введения нормализации.

Оценивается не количество объектов того или иного класса после разбиения, а число подмножеств и их мощность (число элементов).

Выражение оценивает потенциальную информацию, получаемую при разбиении множества Т на m подмножеств.

Критерием выбора переменной для разбиения будет выражение: или.

При условии, что имеется k классов и n - число объектов в обучающей выборке и одновременно количество значений переменных, тогда числитель максимально будет равен log2k, а знаменатель максимально равен log2n. Если предположить, что количество объектов знаведомо больше количества классов, то знаменатель растёт быстрее, чем числитель и, соответственно, значение выражения будет небольшим.

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

2.3 Алгоритм покрытия

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

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

Для выбора независимой переменной и её значения, которое разделяет множество, выполняются следующие действия:

Из построенного на предыдущем этапе подмножества (для первого этапа это вся обучающая выборка), включающего объекты, относящиеся к выбранному классу для каждой независимой переменной, выбираются все значения, встречающиеся в этом подмножестве.

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

Выбираются условия, покрывающие наибольшее количество объектов выбранного класса.

Выбранное условие является условием разбиения подмножества на два новых.

После построения дерева для одного класса таким же образом строятся деревья для других классов.

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

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

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

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

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

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

3. Практическая часть. Построение дерева решений на примере

дерево решение методика банк

Для финансирования проекта построения нового торгового зала предпринимателю требуется занять сроком на 1 год 150000 рублей. Банк может одолжить ему эти деньги под 20% годовых или вложить в дело со 100% возвратом, но под 10% годовых. Из прошлого опыта банку известно,что 5% таких клиентов сумму не возвращают. Встает вопрос: давать ли заём?

Решение:

Максимизируем ожидаемый в конце года чистый доход, который представляет собой разность суммы, полученной в конце года, и. инвестированной в его начале. Таким образом, если заем был выдан и возвращен, то чистый доход составит: Чистый доход =((150000+(150000/100%)*20%)-150000)=30000(руб.)

Таблица 1

Чистый доход в конце года (руб.)

Возможные исходы	Возможные решения	Вероятность
	Выдавать заём	Не выдавать заём
Заём возвращён	30000	15000	0,95
Заём не возвращён	-150000	15000	0,05
Ожидаемый чистый доход	21000	15000	-

Если банк решает выдать заем, то максимальный ожидаемый чистый доход равен 21000

По дереву решений:

21000

Заём уплачен 20% годовых(-150000)

0,95

0,05

Не давать заём

Инвестирование под 10% годовых

Расчёт ведётся аналогично расчёту по таблице доходов. Ожидаемый чистый доход в кружках А и Б вычисляется следующим образом:

В кружке А:(давать заём)=(180000*0,95+0*0,5)-150000=171000-150000=21000(руб.)

В кружке Б: (не давать заём)=(165000*1,0-15000)=150000

Вывод:Поскольку ожидаемый чистый доход в кружке А, то принимается решение выдать заём.

Заключение

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

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

Список используемой литературы

1. Базаров Т. Ю. Управление персоналом. Практикум/Т.Ю. Базаров. М.: Юнити-Дана, 2009. 240 с.

2. Бухалков М.И. Управленческие решения: развитие трудового потенциала: учебное пособие для студентов вузов / М. И. Бухалков. М.: ИНФРА-М, 2009. 192 с.

3. Веснин В.Р. Практический менеджмент персонала: пособие по кадровой работе / В. Р. Веснин. М.: Юристъ, 2010. 495 с.

4. Виханский О.С. Стратегическое управление: учебник для студ. вузов / О. С. Виханский. 2-е изд., перераб. и доп. М.: Экономистъ, 2010. 296 с.

5. Волкова О.Н. Управленческий анализ: учебник [для студ. вузов] / О. Н. Волкова. М.: Велби: Проспект, 2010. 304 с.

6. Егоршин А.П. Основы управления персоналом: учебное пособие для студентов вузов / А. П. Егоршин. 3-е изд., перераб. и доп. М.: ИНФРА-М, 2011. 352 с.

7. Е. В. Пирогова,Управленческие решения: Учебное пособие. Ульяновск: УлГТУ, 2010(электронное пособие). 17 с.

8. Одегов Ю.Г. Аудит и контроллинг персонала: учебник для студентов вузов / Ю. Г. Одегов, Т. В. Никонова ; Рос. экон. акад. им. Г. В. Плеханова. 2-е изд.,перераб. и доп. М.: Альфа-Пресс, 2010. 672 с.

9. Травин В.В. Подготовка и реализация управленческих решений: [учебно-практическое пособие] / В. В. Травин, М. И. Магура, М. Б. Курбатова. М.: Дело, 2009. 80 с.

10. Управление персоналом: энциклопедия / [авт. кол.: А. Я. Кибанов, И. А. Баткаева, В. В. Водянова и др.] ; под ред. А. Я. Кибанова. М.: ИНФРА-М, 2010. VI, 554 с.

Размещено на Allbest.ru

...