Сравнительный анализ эффективности алгоритмов построения дерева принятия решений

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

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

Сравнительный анализ эффективности алгоритмов построения дерева принятия решений

Симченко Н.Н.

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

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

В рамках данного исследования была поставлена задача проанализировать зависимость уровня подготовки учителя от места проживания, категории, стажа работы и образования. Для этого была спроектирована структура данных, основанная на результатах тестирования, которое было проведено для определения уровня предметной составляющей профессиональной компетенции учителя информатики. Для контроля знаний в тест были включены вопросы двух уровней сложности: низкий и высокий. Содержание тестовых вопросов отражало все содержательные линии школьного предмета «Информатика» в полном соответствии с ФГОС полного (среднего) образования. В качестве выходного определен атрибут -Уровень, показывающий уровень подготовки учителя, принимающий значение «высокий», если учитель, верно ответил на вопросы высокого уровня сложности и значение «низкий», если учитель ответил верно на вопросы на распознавание, которые представлены тестами с выборочными ответами [3].

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

Таблица 1 - Хранилище данных

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

1) Выбирается очередной атрибут и помещается в корень.

2) Для всех значений выбранного атрибута делается следующее:

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

- в этом потомке, при помощи рекурсии, строится дерево.

Основной задачей является задача выбора основного атрибута. Есть различные способы выбора атрибута. В рамках данного исследования рассмотрены два алгоритма построения дерева принятия решений: алгоритм ID3 и алгоритм C4.5.

Алгоритм ID3, где выбор атрибута происходит на основании прироста информации (англ. Gain), либо на основании индекса Гини. Алгоритм C4.5 (улучшенная версия ID3), где выбор атрибута происходит на основании нормализованного прироста информации. Алгоритм ID3 строит решающее дерево, в котором с каждым узлом ассоциирован атрибут, являющийся наиболее информативным среди всех атрибутов, еще не рассмотренных на пути от корня дерева [1].

В исследовании была разработана программная реализация алгоритма ID3, выбран язык программирования С#, среда разработки Microsoft Visual Studio 2012. Для хранения информации об атрибутах в программе описана структура attributes:

struct attributes

{

public string name;

public string[] values;

}

Для хранения дерева принятия решений в программе описан класс item_tree:

class item_tree

{

public attributes a;

public int num_attr;

public int obuch = 0;

public string res;

public item_tree[] children;

public bool[] enter=new bool[count];

}

Для того, чтобы получить более оптимальное дерево принятия решений, нужно на каждом шаге выбирать атрибуты, которые «лучше всего» характеризуют целевую функцию. Это требование формализуется посредством понятия энтропии. На основании программной реализации алгоритма ID3 было построено дерево решений. По окончании построения дерева принятия решений, можно спрогнозировать Уровень подготовки, определив образование (профильное/непрофильное), категорию (высшая, первая, нет) и стаж. Результаты такого прогноза представлены на рисунке 2.

Рисунок 2 - Результат прогноза

Еще одним методом построения дерева принятия решения, является алгоритм C4.5, который представляет собой усовершенствованный вариант алгоритма ID3. Он дает возможность работать не только с категориальными атрибутами, но также с числовыми [3].

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

Построенное дерево, фрагмент которого показан на рисунке 3, содержит 26 листьев (правил) и 34 узла.

алгоритм дерево принятие решение

Рисунок 3- Дерево решений

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

Рисунок 4 - Таблица сопряженности для построенного дерева решений

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

Рисунок 5 - Классификационные правила

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

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

Рисунок 6 - Значимость атрибутов

Анализ построенного дерева принятия решений, показывает, что на уровень подготовки учителя наибольшее влияние оказывает образование (профильное/непрофильное). Проанализировав ветвь «Профильное», было выявлено, что наиболее информативным является атрибут «Стаж», если категория «Высшая», то «Уровень» - «Высокий», если «Вторая», то «Низкий».

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

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

1) число листьев дерева;

2) глубина дерева;

3) средняя глубина листьев дерева;

4) взвешенная глубина распределения описаний обучающих объектов по листьям дерева;

5) «оптимальность» распределения обучающих объектов по листьям дерева (абсолютная разница между средней глубиной листьев дерева и взвешенной глубиной распределения описаний обучающих объектов по листьям дерева);

6) оценка качества дерева с помощью метода «leave-one-out».

Первые два свойства указывают на то, что:

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

- оценка вероятности ошибки решающего правила уменьшается с уменьшением глубины дерева;

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

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

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

Определим перечисленные характеристики для деревьев принятия решений, построенных в рамках проводимого исследования, с помощью алгоритмов ID3 и С4.5. Назовем дерево, построенное с помощью алгоритма ID3 первым, а дерево, построенное с помощью алгоритма C4.5 - вторым. Соответственно, характеристики первого дерева будем записывать с верхним индексом 1, а второго - с верхним индексом 2.

(1)

(2)

где - глубина дерева,

- глубина i-го листа дерева,

1) Вычислим среднюю глубину листьев первого и второго деревьев

(3)

(4)

где - средняя глубина листьев дерева;

- число листьев дерева: , .

Тогда

- средняя глубина листьев первого дерева

- средняя глубина листьев второго дерева.

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

(5)

(6)

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

- число обучающих объектов, описание которых принадлежит интервалу истинности конъюнкции, приписанной листу i;

Тогда

;

.

Тогда

- глубина распределения описаний обучающих объектов по листьям первого дерева.

- глубина распределения описаний обучающих объектов по листьям второго дерева.

3) Обозначим через - «оптимальность» распределения обучающих объектов по листьям дерева:

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

Таблица 2 - Сравнение структурных характеристик решающих деревьев

Из таблицы 2 видно, что дерево, полученное с помощью алгоритма C4.5 имеет более оптимальную структуру.

Оценим качество построенных деревьев с помощью метода LOO («leave-one-out»). Для этого вычислим величину:

, (7)

где q_i - процент правильно классифицированных объектов класса M_i,

l - число классов в обучающей выборке.

В нашей базе данных выходной атрибут имел два возможных значения, поэтому l = 2. При построении дерева принятия решений с помощью алгоритма ID3 правильно классифицировались 68 объектов из 99, причем на принадлежность первому классу правильно классифицировались 32 объекта из 45, а на принадлежность второму классу - 36 объектов из 54, то есть

При построении дерева принятия решений с помощью алгоритма С4.5 правильно классифицировались 94 объектов из 99, причем на принадлежность первому классу правильно классифицировались 42 объекта из 54, а на принадлежность второму классу - 49 объектов из 54, то есть

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

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

В результате исследования был сделан вывод: для того, чтобы уровень подготовки учителя был высоким необходим соответствующий уровень образования. Учитель постоянно находится между практикой и теорией, наращивая свой опыт преимущественно практическими умениями. Любая педагогическая работа - это практическая деятельность. Часто бывает так, что между теоретическими знаниями и практическими умениями продолжает сохраняться серьёзный разрыв. Преодолеть этот разрыв в современной школе можно средствами профессиональной переподготовки. Повышение квалификации помогает учителю избавиться от устаревших взглядов, делает его более восприимчивым к внешним изменениям, что в конечном итоге повышает его конкурентоспособность [3].

Список литературы

1. Вагин, В. Н. Достоверный и правдоподобный вывод в интеллектуальных системах / В. Н. Вагин., Е. Ю. Головина, А. А. Загорянская, М. В. Фомина // Москва.: ФИЗМАТЛИТ, 2004. - 704 с.

2. Гиглавый, А. В. Долгосрочные тренды развития сектора информационно-коммуникационных технологий / А. В. Гиглавый, А. В. Соколов, Г. И. Абдрахманова, А. А. Чулок, В. В. Буров; Форсайт - FORESIGHT-RUSSIA Т. 7. № 3 - 2013.

3. Симченко, Н. Н. Использование алгоритмов предсказательного моделирования для прогнозирования уровня подготовки учителя информатики [Электронный ресурс] / Н. Н. Симченко // Университетский комплекс как региональный центр образования, науки и культуры: материалы Всерос. науч.-метод. конф, 31 января-02 февраля 2018 г, Оренбург / / Оренбург. гос. ун-т. - Электрон. дан. - Оренбург, 2018. - С. 1859-1865.

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