Введение 7
1 История возникновения и анализ дерева решений 9
1.1 История возникновения метода 9
1.2 Анализ дерева решений 12
1.3 Выразительность деревьев решений 19
2 Методы и алгоритмы решения задач с помощью дерева решений 23
2.1 Деревья решений: общие принципы 23
2.2 Алгоритм CART 32
2.3 Алгоритм ID3 35
2.4 Алгоритм C4.5 36
3 Реализация и тестирование алгоритмов построения дерева решений 39
Заключение 45
Список используемой литературы 46
Приложение А Программный код
В выпускной квалификационной работе рассматривается процесс анализа и реализации алгоритмов построения дерева решений.
Актуальность работы заключается в том, что методы деревьев решений популярны в аналитике данных и машинном обучении с практическим применением в различных секторах, от здравоохранения до финансов и технологий. Деревья принятия решений проще, чем нейронные сети, в связи с тем, что их правила формируются на естественном языке. Эти правила генерируются за счет обобщения множества отдельных наблюдений, которые служат обучающими примерами и описывают предметную область. Поэтому их называют индуктивными правилами, а сам процесс обучения — индукцией деревьев решений.
Объектом выпускной квалификационной работы являются задачи оптимизации, решаемые на основе метода дерева решений.
Предметом выпускной квалификационной работы являются следующие алгоритмы генерации дерева решений:
- алгоритм ID3,
- алгоритм C4.5,
- алгоритм CART.
Целью работы является анализ и реализация алгоритма ID3, алгоритма C4.5 и алгоритма CART.
Для достижения поставленных целей необходимо решить следующие задачи:
- проанализировать алгоритмы построения дерева решений для исследования их эффективности,
- выбрать технологии для проектирования алгоритмов построения дерева решений,
- исследовать математические модели алгоритмов построения дерева решений,
- реализовать алгоритмы построения дерева решений,
- протестировать реализованные алгоритмы построения дерева решений,
- проанализировать эффективность алгоритмов построения дерева решений.
Результатом работы является реализация алгоритма ID3, алгоритма C4.5 и алгоритма CART, а также анализ их эффективности.
В первой главе рассматривается история возникновения метода «дерева решений», а также задачи, решаемые с помощью данного метода.
Во второй главе рассматриваются методы и алгоритмы решения задач с помощью дерева решений.
В третьей главе рассматриваются современные архитектурные решения; реализуются и тестируются алгоритмы построения дерева решений с использованием выбранной ранее технологии.
В ходе выполнения дипломной работы на тему «Анализ и реализация алгоритмов построения дерева решений» был рассмотрен процесс осуществления алгоритмов построения дерева решений и их последующий анализ.
Цель работы заключалась в анализе и реализации алгоритма ID3, алгоритма C4.5, а также алгоритма CART.
Для достижения поставленной цели проанализированы основные принципы дерева решений, включающие в себя подробное изложение этапов построения.
С помощью существующих математических моделей реализованы алгоритм ID3, алгоритм C4.5, а также алгоритм CART для построения дерева решений. Алгоритмы разработаны на функциональном языке программирования Python в интегрированной свободной среде для создания приложений PyCharm.
Для работы с реализованными алгоритмами и анализа их эффективности использовалась операционная система Windows.
Как показал анализ трёх реализованных алгоритмов построения дерева решений - каждый из рассмотренных алгоритмов походит для определенных типов задач.
Так алгоритм ID3 подходит для наборов данных с категориальными признаками. Алгоритм С4.5 подходит как для наборов данных с категориальными признаками, так и для наборов данных с числовыми признаками. А алгоритм CART в свою очередь подходит как для работы с категориальными, так и с числовыми признаками, но может строить только бинарные деревья.
