Введение
В этом блоге мы поговорим об алгоритме дерева решений. Да, вы правильно прочитали. Это дерево или оно похоже на дерево (перевернутое дерево), которое помогает принять решение. Почему дерево помогает нам принимать решения?
Так как же нам принять какое-либо решение? Предположим, перед нами несколько вариантов. Что дальше? Соберите как можно больше информации по каждому из вариантов. Проанализируйте все «за» и «против», а затем решите. Много работы правильно. А теперь представьте, что у вас есть тонны и тонны информации, которую нужно обработать, и вы упускаете некоторые моменты. Ошибка !!! Желаю, чтобы кто-то еще проделал всю эту тяжелую работу, и мы просто могли сосредоточиться на результате.
Итак, вот и Спаситель. Машинное обучение!!
В машинном обучении у нас есть много разных алгоритмов для решения такого рода проблем. Дерево решений. Алгоритм принадлежит к семейству алгоритмов машинного обучения с учителем. Его можно использовать как для классификации, так и для решения задачи регрессии.
Дерево решений похоже на оператор if-else. Если условие истинно, примите одно решение или проверьте следующее условие, если условие ложно, примите другое решение или проверьте следующее условие.
Некоторые термины
1. Корневые узлы: это узел, находящийся на вершине дерева решений от этого узла, другие узлы начинают появляться в соответствии с различными функциями.
2. Узлы принятия решений: узлы, которые мы получаем после разделения корневых узлов, называются узлами принятия решений.
3. Концевые узлы: узлы, которые мы не можем разделить дальше, называются конечными узлами или конечными узлами.
4. Поддерево: подсекция этого дерева решений называется поддеревом.
5. Обрезка: обрезка некоторых узлов для предотвращения переобучения называется обрезкой.
Пример дерева решений
В приведенном ниже примере у нас есть только одна функция, уровень сахара в крови и 3 разных класса - Нормальный, Преддиабет, Диабет.
Методы выбора атрибутов:
При реализации дерева решений мы должны определить атрибуты, которые будут использоваться в качестве корневого узла и узлов решений. Этот процесс называется выбором атрибута. Два самых популярных метода выбора атрибутов:
· Получение информации
· Индекс Джини
Прирост информации показывает, сколько информации содержит каждый атрибут. Чтобы вычислить прирост информации, сначала мы должны вычислить энтропию.
Что такое энтропия?
Энтропия измеряет примеси в каждом наборе данных. В физике и математике энтропия называется случайностью или неопределенностью случайной величины X. В теории информации это относится к примеси в группе примеров.
Что такое получение информации?
Прирост информации - это уменьшение энтропии. Прирост информации вычисляет разницу между энтропией до разделения и средней энтропией после разделения набора данных на основе заданных значений атрибутов.
Формула энтропии: здесь c - количество классов, а pi - вероятность, связанная с i-м классом.
Прирост информации - это энтропия полного набора данных - энтропия набора данных с учетом некоторой характеристики.
Дерево решений ID3 (Итеративный дихотомизатор) использует метод получения информации для выбора атрибута. Вычисляя уменьшение меры энтропии каждого атрибута, мы можем вычислить их информационную ценность. Атрибут с наибольшим информационным выигрышем выбирается в качестве атрибута разделения в узле.
Индекс Джини
Еще одна мера выбора атрибутов, которую использует CART ( деревья по категориям и регрессии) , - это индекс Джини.
Индекс Джини можно представить следующей формулой. здесь c - количество классов, а pi - вероятность, связанная с i-м классом.
Расчет энтропии
Энтропия для родителя:
- (9/14) log2 (9/14) - (5/14) log2 (5/14)
=-(.64) *(-0.64) — (0.36) * (-1.49)
=0.41+0.54
=0.95
Энтропия для функции 2:
- (2/6) log2 (2/6) - (4/6) log2 (4/6)
=-(0.33 * (-1.585)) — (.66 * (-0.585))
= -(-0.52) — (-0.39))
= 0.91
Энтропия для функции 3:
- (7/8) log2 (7/8) - (1/8) log2 (1/8)
=-(.875 * (-0.19)) — (0.125 * (-3))
=-(-0.166) +0.38)
= 0.55
Чтобы увидеть средневзвешенное значение энтропии каждого узла, сделаем следующее:
E (Родитель | Характеристика1) = (8/14) * 0,55 + (6/14) * 0,91 = 0,31 + 0,39 = 0,7
Информационное усиление = E (Родитель) - E (Родитель | Характеристика1) = 0,95–0,7 = 0,25
Точно так же мы можем сделать это для других узлов.
Теперь мы знаем, как вырастить наше дерево. Итак, следующий вопрос - когда остановить рост. Как будто есть много функций, это приводит к множеству узлов, что делает дерево очень сложным. Более сложное дерево может привести к переобучению.
Способы остановить переоснащение или чрезмерный рост деревьев
1. Установите минимальное количество обучающих входов для использования на каждом листе. Итак, как только лист достигнет минимального числа, он перестанет расщепляться.
2. Установите максимальную глубину. Максимальная глубина относится к длине самого длинного пути от корня до листа.
3. Обрезка: это включает в себя удаление ветвей, которые используют функции, не имеющие особой важности. Таким образом, мы уменьшаем сложность дерева и, таким образом, увеличиваем его прогнозирующую способность за счет уменьшения переобучения.
Вот пример кода
До сих пор мы много говорили о дереве решений. Но он не будет полным, пока мы не узнаем, как его реализовать. Хорошая новость в том, что нам не нужно писать код с нуля для его реализации. Доступно много хороших библиотек. Здесь я использовал библиотеку Scikit-Learn. Пожалуйста, найдите полный код с набором данных в моем аккаунте GitHub.
Вывод
В этой статье я подробно рассмотрел дерево решений. Я описал математику, лежащую в основе этого. Также мы изучили меры выбора атрибутов, такие как энтропия, получение информации, индекс Джини, с их формулами. Надеюсь, это будет полезно для вас. Пожалуйста, оставьте свои комментарии.