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

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

Учреждение образования

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Факультет Информационных Технологий

Лабораторная работа по теме:

“ Деревья решений”

Выполнил:

Студент: Белькевич Р.И.

ФИТ 3 курс 2 группа

Проверил: Колесников В.Л.

Минск 2016

Оглавление

Введение

1. Построение дерева

2. Постановка задачи

3. Организация сбора информации

3.1 JMP

3.2 Надстройка для Microsoft Exсel «Интеллектуальный анализ данных»

4. Анализ результатов

Вывод

Введение

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

Рисунок 1. - Пример дерева

С помощью деревьев можно решить следующие задачи:

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

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

На сегодняшний день существует значительное число алгоритмов, реализующих деревья решений CART, C4.5, ID3. Но наибольшее распространение и популярность получили следующие три:

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

· C4.5 - алгоритм построения дерева решений, количество потомков у узла не ограничено. Не умеет работать с непрерывным целевым полем, поэтому решает только задачи классификации.Алгоритм C4.5 использует теоретико-информационный подход. Для выбора наиболее подходящего атрибута, предлагается следующий критерий:

Множества T₁, T₂, ... Tn получены при разбиении исходного множества T по проверке X. Выбирается атрибут, дающий максимальное значение по критерию(1).

· CART (Classification and Regression Tree) - это алгоритм построения бинарного дерева решений - дихотомической классификационной модели. Каждый узел дерева при разбиении имеет только двух потомков. Как видно из названия алгоритма, решает задачи классификации и регрессии.Алгоритм CART использует так называемый индекс Gini, который оценивает "расстояние" между распределениями классов.

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

1. Построение дерева

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

Пусть через {C₁, C₂, ... C_k} обозначены классы, тогда если множество T содержит примеры, относящиеся к разным классам, следует разбить множество T на некоторые подмножества. Для этого выбирается один из признаков, имеющий два и более отличных друг от друга значений O₁, O₂, ... O_n. T разбивается на подмножества T₁, T₂, ... T_n, где каждое подмножество T_i содержит все примеры, имеющие значение O_i для выбранного признака. Это процедура будет рекурсивно продолжаться до тех пор, пока конечное множество не будет состоять из примеров, относящихся к одному и тому же классу.Вышеописанная процедура лежит в основе многих современных алгоритмов построения деревьев решений.

Рассмотрим изложенное выше на примере.

Для этого попробуем решить идти гулять или нет. Входные данные будут представлены в виде таблицы.

Таблица 1. - Входные данные

Определим понятие энтропии Н множества А по отношению к свойству S:

,

где А - множество из n элементов, mкоторых обладают свойством S.

Так же определим понятие прирост информации:

,

Где A - множество элементов,Q - атрибут, S - свойство,q - возможные значения Q,A_i- множество элементов у которых Q равно i.

1. Рассчитаем исходную энтропию:

Судя по таблице 1 из 5 случаев в 2-х мы идём гулять, значит

0,528+0,44=0,968

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

3.

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

дерево решение интеллектуальный анализ

2. Постановка задачи

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

3. Организация сбора информации

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

3.1 JMP

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

Рисунок 2. - Данные в программе JMP

После этого начинаем строить деревья. Сначала выберем, что от чего зависит. Это делается в окне, представленном на рисунке 3.

Рисунок 3. - Определение зависимостей для прочности

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

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

Рисунок 4. - Корень дерева параметра «Прочность»

Перед исследованием зависимостей факторов от параметров я решил установить диапазон значений прочности, что бы знать, когда остановиться. А именно от 3,5 до 5(значения по умолчанию в виртуальном комплексе) для прочности, от 10 до 30 для влагопрочности и от 15 до 45 для пластичности. Далее по полю Mean мы выбираем ветку со значением, наиболее подходящим под установленный интервал. На выбранном листе жмём красную стрелку и выбираем Splitbest. Повторяем, пока есть возможность разделить лист. В итоге были получены деревья для всех параметров производства приведённые на рисунках ниже.

Рисунок 5. - Дерево параметра «Прочность»

Рисунок 6. - Дерево для параметра «Пластичность»

Рисунок 7. - Дерево для параметра «Влагопрочность»

3.2 Надстройка для Microsoft Exсel «Интеллектуальный анализ данных»

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

Рисунок 8. - Мастер задач надстройки

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

Рисунок 9. - Выбор зависимостей

Нажав кнопку «Далее» ещё раз, мы попадаем на последнюю страницу мастера, на которой надо подтвердить свой выбор.

Рисунок 10. - Завершение работы мастера задачи

После нажатия кнопки «Готово» мы получим дерево, построенное по нашим параметрам.

Рисунок 11. - Дерево для параметра «Влагопрочность»

Повторив всё то же для двух оставшихся параметров были получены все три дерева.

Рисунок 12. - Дерево для параметра «Прочность»

Рисунок 13. - Дерево для параметра «Пластичность»

4. Анализ результатов

Используя полученные деревья, попробуем проанализировать то, как различные факторы влияют на параметры производства. Первыми будут деревья, полученные в JMP.

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

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

В случае с пластичностью проследив путь от корня дерева до листа со значением 43.44, можно сделать выводы касательно связи факторов:

увеличение концентрации при отливе потребует увеличения уровня допустимых сульфатов AL, после чего концентрация при отливе будет установлена меньше 1.505, но больше 1.48.

В дереве влагопрочности проследив путь от корня дерева до листа со значением 17.18, можно сделать выводы касательно связи факторов:

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

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

Улучшение значения пластичности требует увеличения расхода волокна.

В случае влагопрочности улучшение значения требует уменьшения расхода полимера.

Вывод

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

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