Дерево принятия решений

ФЕДЕРАЛЬНОЕ ГоСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

 

«Воронежский  государственный технический университет»

(ФГБОУВПО  «ВГТУ»)

 

Факультет радиотехники и  электроники

 

Кафедра системного анализа  и управления в медицинских системах

 

РЕФЕРАТ

 

по дисциплине: «Математическое моделирование»

 

тема: «Дерево принятия решений»

 

 

 

                                                                                          Выполнила: Пазий Т.Н.                                                                

                                                                                    Студентка группы: БМм-131

                                                                                          Проверила: к.т.н. Новикова Е.И.

 

 

 

 

 

Воронеж 2013

Содержание

 

Введение			3
1	Деревья классификации и  регрессии		4
2	Описание структуры деревьев решений		4
	2.1	Общие сведения о выборках данных	5
	2.2	Деревья решений	6
	2.3	Способы проверки условий	8
	2.4	Листовые узлы и переменные отклика	10
3	Классификация и регрессия		11
4	Формирование дерева		12
	4.1	Описание алгоритма рекурсивного секционирования	13
	4.2	Разбиение наборов данных	14
5	Процедура обучения		16
	5.1	Управление набором данных	17
	5.2	Отсечение ребер	18
	5.3	Конгломерация и усиление	19
Заключение			20
Список литературы			22

 

 

 

 

 

 

 

 

 

 

Введение

 

Дерево принятия решений (также могут назваться деревьями классификации или регрессионными деревьями) — используется в области статистики и анализа данных для прогнозных моделей. Структура дерева представляет собой следующее: «листья» и «ветки». На ребрах («ветках») дерева решения записаны атрибуты, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах — атрибуты, по которым различаются случаи. Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение. Подобные деревья решений широко используются в интеллектуальном анализе данных. Цель состоит в том, чтобы создать модель, которая предсказывает значение целевой переменной на основе нескольких переменных на входе.

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

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

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

1. описание данных: "деревья решений" позволяют хранить информацию о данных в компактной форме, вместо них мы можем хранить дерево решений, которое содержит точное описание объектов;
2. классификация: "деревья решений" отлично справляются с задачами классификации, т.е. отнесения объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные значения;
3. регрессия: если целевая переменная имеет непрерывные значения, "деревья решений" позволяют установить зависимость целевой переменной от независимых (входных) переменных. Например, к этому классу относятся задачи численного прогнозирования (предсказания значений целевой переменной).

 

1 Деревья классификации  и регрессии

 

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

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

 

2 Описание структуры деревьев решений

 

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

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

 

Таблица 1 - Различие между двумя типами деревьев решений

Тип дерева	Прогнозирование	Тип данных
Дерево классификации	Дискретное	Символы
Дерево регрессии	Непрерывное	Вещественные числа

 

2.1 Общие сведения о выборках данных

 

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

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

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

 

Таблица 2 - Четыре выборки данных с многочисленными атрибутами

Вес	Скорострельность, выстрелов/мин	Емкость, патроны	Дальность стрельбы, м	Тип	Ущерб, %
Легкий	47	10	40	Пистолет	5
Тяжелый	200	500	100	Автомат	10
Очень легкий	6	6	25	Пистолет	4
Очень тяжелый	280	1000	200	Автомат	13

 

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

 

2.2 Деревья решений

 

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

 

Рисунок 1 – Простое дерево решений

 

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

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

 

Рисунок 2 – Разбиение  выборки данных на взаимоисключающие  подмножества с использованием узла принятия решений

 

2.3 Способы проверки условий

 

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

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

2) Определение знака. При  выполнении такой проверки определяется  знак выражения. Результатом может быть либо положительное, либо отрицательное значение. Указанная проверка может рассматриваться как частный случай проверки булева значения.

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

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