Application of decision tree method to classification and prediction problems

Full Text

Введение Искусственный интеллект является обширной областью науки, алгоритмы которой используются при решении задач, для которых часто сложно и невозможно создать явный алгоритм решения. В настоящее время известно достаточно много алгоритмов, предназначенных для решения задач классификации или прогнозирования: метод опорных векторов, метод k ближайших соседей, нейронные сети и деревья решений [1]. Деревья решений - это способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение [2]. На ребрах дерева записываются атрибуты, от которых зависит целевая функция. Данная статья посвящена одному из классических методов интеллектуального анализа данных- построению деревьев решений. Наиболее общее определение дерева решений - это средство поддержки принятия решений при прогнозировании, которое широко применяется в статистике и анализе данных. Цель процесса построения дерева принятия решений - создать модель, по которой можно было бы классифицировать случаи и решать, какие значения может принимать целевая функция, имея на входе несколько переменных. Применения метода дерева решений для решения задач классификации и прогнозирования Приведем пример построения дерева решений, решив задачу классификации сотрудников магазина. В качестве исходных данных выберем небольшой набор данных - сотрудники магазина, представленный в таблице 1. Таблица 1. Сотрудники магазина department status age, years salary, thousand rubles sales senior 31 46 sales junior 26 28 sales junior 31 33 marketing senior 36 46 marketing junior 31 41 systems senior 31 66 systems junior 26 46 systems senior 41 66 secretary senior 46 36 secretary junior 26 28 В качестве целевой переменной возьмем переменную status; 5 записей из 11 целевая переменная имеет значение senior, а оставшиеся 6 записей - junior. Энтропия исходного множества до разбиения составит [3]: Произведем разбиение по атрибуту department. Три записи данного атрибута имеют значение sales, четыре - systems, два - marketing, два - secretary. Соответствующие вероятности будут равны: Одна из трех записей, содержащих значение sales, указывает на senior, а две - на junior. Тогда при случайном выборе из этих трех записей вероятность появления senior составит 1/3, а junior - 2/3. Вычислим энтропию для значения sales: Две записи из четырех, содержащих значение systems, указывают на senior, а две - на junior. Вычислим энтропию: Одна из двух записей, содержащих значение marketing, указывает на senior, а другая - на junior. Вычислим энтропию: Одна из двух записей, содержащих значение secretary, указывает на senior, а другая - на junior. Вычислим энтропию: На основе полученных данных можно рассчитать полную энтропию разбиения: Прирост информации, полученный в результате разбиения по атрибуту department, будет равен: Аналогичным образом находим и получаем прирост информации по остальным атрибутам: Таким образом, прирост информации в результате разбиения по атрибуту age больше по сравнению с другими атрибутами, поэтому выбирается в качестве начального разбиения в корневом узле дерева. Схема начального разбиения представлена на рис. 1. Рис. 1. Результат первого шага построения дерева Для значения 31 год получен узел, содержащий две записи со значением целевой переменно senior и две со значением junior. Далее производим поиск оптимального разбиения данного подмножества (подмножество N1) данного узла. Таблица 2. Множество N1 department status age, years salary, thousand rubles sales senior 31 46 sales junior 31 33 systems senior 31 66 marketing junior 31 41 В качестве целевой переменной возьмем переменную status. В двух записях из четырех целевая переменная принимает значение senior, и в двух - junior. Поэтому энтропия исходного множества до разбиения составит: Находим прирост информации по каждому нецелевому атрибуту: Разбиение по атрибуту salary обеспечивает наибольший прирост информации, поэтому выбирается в качестве дальнейшего разбиения дерева. Полное дерево, полученное в результате разбиения представлена на рис. 2 [4]. Рис. 2. Полное дерево решений Распространенный способ реализации деревьев решений - это построение дерева на языке программирования Python. Чтобы оценить, насколько хорош выбранный атрибут, алгоритм сначала вычисляет энтропию всей группы. Затем он пытается разбить группу по возможным значениям каждого атрибута и вычисляет энтропию двух новых групп. Для определения того, какой атрибут дает наилучшее разбиение, вычисляется информационный выигрыш, то есть разность между текущей энтропией и средневзвешенной энтропией двух новых групп. Он вычисляется для каждого атрибута, после чего выбирается тот, для которого информационный выигрыш максимален. Вычисляя для каждого узла наилучший атрибут и расщепляя ветви, алгоритм создает дерево [5]. На рис. 3 представлен результат построения дерева решений с помощью интерпретатора языка программирования Python 2.7.6 [6]. Риc. 3. Результат построения дерева решений с помощью Python 2.7 Рассмотрим следующий пример построения дерева решений. В качестве исходных данных выберем классический набор данных - ирисы Фишера. В отличие от предыдущего примера данный набор содержит 150 экземпляров ирисов, принадлежащих к трем видам (setosa, versicolor, virginica). Для каждого экземпляра ириса известны четыре величины: длина и ширина чашелистика, длина и ширина лепестка [7]. Наша задача выработать критерии, по которым можно различить три вида. В качестве целевой переменной возьмем переменную Class; 50 записей из 150 принадлежат атрибуту Iris-setosa, 50 записей - Iris-versicolor, 50 записей - Iris-verginica. Энтропия исходного множества до разбиения составит: Прирост информации по атрибутам: Прирост информации в результате разбиения по атрибуту petal-length больше по сравнению с другими атрибутами, поэтому выбирается в качестве начального разбиения в корневом узле дерева. Рис. 4. Полное дерево решений После этого производим дальнейшее разбиение, пока не получим оптимальное разбиение полного множества. Полное дерево, полученное в результате разбиения представлена на рис. 4. Чем больше набор данных содержит записей, тем более сложным и трудоемким становится процесс построения дерева решений вручную. Он занимает огромное количество времени, и вероятность ошибок возрастает. Для решения данной проблемы существуют программные продукты, предназначенные для анализа данных и содержащие алгоритм построения деревьев решений. Одними из самых распространенных программ на сегодняшний день являются Deductor[8] и Orange Canvas [9]. На рис. 6 представлен результат построения дерева решений в Deductor. На рис. 7 представлен результат построения дерева решений в Orange Canvas [10]. Как видно из рис. 6-7, результаты, полученные с помощью программ Deductor и Orange Canvas, соответствуют результатам формульных вычислений. Поэтому можно сделать вывод о том, что задачи (наборы данных) с относительно небольшим числом атрибутов могут решаться вручную, в то время как задачи (наборы данных) с большим числом атрибутов легче и целесообразнее решать с помощью программных систем. Чем больше набор данных, тем дольше и сложнее становится расчет по формулам. Могут затрачиваться часы, дни и даже месяцы, а программы производит расчеты в течение нескольких секунд. Программа сама отсекает несущественные факторы, выявляет степень влияния тех или иных факторов на результат, а также выдает информацию о достоверности правил дерева решений. Кроме того, полученные результаты, представленные в программах, являются более простыми для восприятия и понимания. Рис. 6. Результат построения дерева решений в Deductor Рис. 7. Результат построения дерева решений в Orange Canvas Результаты, полученные с помощью Orange Canvas и Deductor обладают примерно равными возможностями. Однако работа с деревьями решений в Deductor реализована заметно удобнее. Программа имеет несколько визуализаторов дерева решений. Пользователь может выбрать наиболее удобный для понимания. Один из визуализаторов Deductor - правила «если-то» - удобное представление построенного дерева в виде правил. Таблица 3. Достоверность работы для разных методов № Условие Следствие Достоверность, % Deductor Orange Canvas Ручной расчет 1 petal_length < 2,45 Iris-setosa 100 100 100 2 petal_length >= 2,45 petal_width < 1,75 petal_length < 4,95 Iris-versicolor 97,9 97,9 97 3 petal_length >= 2,45 petal_width < 1,75 petal_length >= 4,95 petal_width < 1,55 Iris-virginica 100 100 98 4 petal_length >= 2,45 petal_width < 1,75 petal_length >= 4,95 petal_width >= 1,55 Iris-versicolor 66,6 66,6 66 5 petal_length >= 2,45 petal_width >= 1,55 petal_width < 1,75 Iris-virginica 97,7 97,8 97,5 Заключение В статье рассмотрены несколько вариантов реализации алгоритма деревьев решений на конкретных примерах решения задач. Качество работы метода деревьев решений зависит как от выбора метода, так и от набора исследуемых данных.

About the authors

Alfiya Ashatovna Miftakhova

Povolzhsky State University of Telecommunications and Informatics

Email: miftaxovaa@mail.ru

References

Supplementary files