В этом блоге мы подробно разбираем алгоритм дерева решений ID3 с примером набора данных.
Дерево решений
Дерево решений — это контролируемые алгоритмы машинного обучения, используемые как для постановки задачи регрессии, так и для классификации. Он использует представление дерева для решения проблемы, в которой каждый узел представляет атрибут, каждая ссылка представляет правило принятия решения, а каждый лист представляет собой результат (категориальное или непрерывное значение).
Терминология дерева решений
Корневой узел. Это самый верхний узел в дереве, представляющий полный набор данных. Также можно сказать, что это отправная точка процесса принятия решений.
Решение/внутренний узел. Узлы решений — это не что иное, как результат разделения данных на несколько сегментов данных, и основная цель — получить дочерние узлы с максимальной однородностью или чистотой (означает, что все они одного типа). .
Листовой/терминальный узел. Этот узел представляет собой раздел данных, имеющий наивысшую однородность (означает, что все они одного типа).
Энтропия. Используется для проверки примесей или неопределенностей, присутствующих в данных. Энтропия используется для оценки качества разделения. Когда энтропия равна нулю, выборка полностью однородна, что означает, что каждый экземпляр принадлежит к одному и тому же классу, а энтропия равна единице, когда выборка поровну разделена между разными классами.
Формула энтропии -
Прирост информации. Прирост информации показывает, сколько информации конкретная функция/переменная дает нам о конечном результате.
Формула получения информации-
ID3 [Итеративный дихотомайзер 3]
(Это самые популярные алгоритмы, используемые для построения деревьев.)
ID3 расшифровывается как Iterative Dichotomizer3 и назван так потому, что алгоритм итеративно (повторно) дихотомизирует (делит) объекты на две или более групп на каждом этапе. ID3 — это алгоритм, изобретенный Россом Куинланом, используемый для создания дерева решений из набора данных, и самые популярные алгоритмы, используемые для построения деревьев.
ID3 — это основной алгоритм построения дерева решений. Он использует жадный поиск сверху вниз в пространстве всех возможных ветвей без возврата. Этот алгоритм использует прирост информации и энтропию для построения дерева решений классификации.
Характеристики алгоритма ID3
Основные характеристики алгоритма ID3 перечислены ниже:
- ID3 может переобучать обучающие данные (во избежание переобучения следует отдавать предпочтение меньшим деревьям решений, а не большим).
- Этот алгоритм обычно создает небольшие деревья, но не всегда создает наименьшее возможное дерево.
- ID3 сложнее использовать для непрерывных данных (если значения любого заданного атрибута непрерывны, то существует гораздо больше мест для разделения данных по этому атрибуту, и поиск наилучшего значения для разделения может занять много времени).
Преимущества и недостатки алгоритма ID3
Преимущества
- Недорогой в строительстве
- Чрезвычайно быстро классифицирует неизвестные записи. Легко интерпретируется для небольших деревьев.
- Устойчивость к шуму (особенно при использовании методов, позволяющих избежать переобучения).
- Может легко обрабатывать избыточные или нерелевантные атрибуты (если атрибуты не взаимодействуют).
Недостатки
- Пространство возможных деревьев решений экспоненциально велико. Жадные подходы часто не могут найти лучшее дерево.
- Не учитывает взаимодействия между атрибутами.
- Каждая граница решения включает только один атрибут.
Этапы построения дерева решений
а) Возьмите весь набор данных в качестве входных данных.
б) Рассчитать энтропию целевой переменной, а также атрибуты предиктора
c) Рассчитайте информационный прирост всех атрибутов.
г) Выберите атрибут с наибольшим приростом информации в качестве корневого узла.
e) Повторяйте ту же процедуру для каждой ветви, пока не будет завершен узел решения каждой ветви.
Пример-
Прогноз, будет ли матч сыгран или нет в зависимости от погодных условий. Здесь мы видим таблицу-
Сначала мы собираемся вычислить энтропию для атрибута «Решение», который является целевой переменной, а также вычислить энтропию для независимых атрибутов, таких как «Прогноз», «Температура». , «Влажность», «Ветер».
Повторяйте ту же процедуру для каждой ветви, пока узел решения каждой ветви не будет завершен.
Outlook=солнечно и temp=жарко.
Прогноз = Солнечно и темп = Мягкий
Outlook=солнечно и Temp=прохладно
Внешний вид=Солнечно |Влажность=Высокая
Внешний вид=Солнечно | Влажность=Нормальная
Внешний вид=Сильный | Ветер=Сильный
Внешний вид=Солнечно | Ветер=Слабый
Здесь решение всегда будет да, если кругозор был пасмурным. Так что нет необходимости рассчитывать энтропию и прирост информации.
Внешний вид=Дождь | Темп=Мягкий
Прогноз = Дождь | Температура = Прохладно
Внешний вид=Дождь | Влажность=Высокая
Внешний вид=Дождь | Влажность=Нормальная
Внешний вид=Дождь | Ветер=Сильный
Внешний вид=Дождь | Ветер=Слабый
Здесь мы видим, что прирост информации высок для (Outlook=Rain | Wind) , поэтому это будет узел принятия решения после Rain.
Построение дерева решений завершено. Здесь мы узнали, как дерево решений создается в бэкэнде с использованием этого алгоритма.
Заключение
Мы подробно рассмотрели процесс алгоритма ID3 и увидели, как легко было создать дерево решений с использованием этого алгоритма, используя только две метрики, то есть энтропию и прирост информации.
Надеюсь, вам понравилось, ребята!
Спасибо за прочтение .
