Деревья решений - одни из самых популярных алгоритмов машинного обучения, используемых в промышленности, поскольку они достаточно интерпретируемы и интуитивно понятны. Более того, они имитируют логические рассуждения людей.
Базовый рецепт любого дерева решений очень прост: мы начинаем выбирать в качестве корневого одну функцию, разделяем ее на разные ветви, которые заканчиваются на узлы, а затем, если необходимо, продолжаем дальнейшее разбиение на другие функции. Наконец, мы возвращаемся и «обрезаем листья», чтобы уменьшить переоснащение.
В этой статье я не собираюсь подробно останавливаться на последней процедуре «обрезки листьев», так как я хочу сосредоточиться на критериях разделения: как ваш алгоритм может решить, какая функция должна быть выбрана корневой? На этот вопрос есть разные ответы в зависимости от алгоритма дерева решений, который вы собираетесь использовать. Здесь я объясню типичный критерий дерева решений ID3, то есть критерий получения информации.
Следовательно, нам нужно сначала ввести понятие информации.
Информация определяется путем наблюдения за возникновением события. А именно, учитывая случайную переменную X с возможными исходами x1, ……., Xn и их соответствующие вероятности появления p1, ……., Pn , информация, которую мы хотим получить, - это значение этой переменной X.
Размер или количество информации, которую мы предоставляем, измеряется битами, и есть очень интуитивно понятная формула для вычисления этого количества.
Действительно, учитывая случайную переменную X и один из ее возможных выходных значений xi с вероятностью p i, тогда информационное содержание сообщения, определяющего X = xi - это:
Если мы остановимся на этой формуле, мы поймем, что она имеет интуитивный смысл. Рассмотрим некое событие, вероятность наступления которого равна 1.
Это означает, что количество информации, которое вам нужно, чтобы узнать ценность нашего определенного события, равно нулю, и это имеет смысл, поскольку это определенное событие!
Если бы у нас было много событий x1, ……., Xn с вероятностью p1, ……., Pn, какова их средняя информация? Это просто среднее значение информационного содержания каждого наблюдения, взвешенное по вероятности его появления:
Теперь, когда мы ввели понятие энтропии, мы можем определить критерий расщепления нашего дерева. Обратите внимание, что есть разные стратегии, по которым вы можете построить свое дерево, в зависимости от алгоритма, который вы собираетесь использовать. Однако здесь я объясню типичный критерий дерева решений ID3, то есть критерий получения информации (IG), поскольку он, на мой взгляд, является наиболее интуитивно понятным.
Идея критерия получения информации заключается в том, что мы начинаем разделять наше дерево с той характеристики, которая возвращает наибольший прирост информации (то есть, короче говоря, разницу в энтропии до и после процедуры разделения).
Давайте посмотрим на пример со следующим набором данных:
Мы хотим классифицировать получаемое электронное письмо как спам или не как спам, в зависимости от их объекта, времени отправки и длины сообщения. Чтобы решить, какой атрибут мы должны выбрать в качестве корня нашего дерева, мы должны выполнить следующие шаги:
- Вычислите энтропию нашей целевой переменной:
- Вычислите энтропию по каждой функции / атрибуту:
- Вычислите прирост информации (IG) для каждой функции:
Что ж, теперь мы можем использовать наш набор данных, чтобы показать полную процедуру. Я остановлюсь на каждом шаге только для первой функции, «Объект», а для остальных я покажу только результаты. Однако учтите, что процедура точно такая же.
Итак, первое, что нужно сделать, это создать таблицу относительной частоты для нашей функции:
Затем мы вычисляем энтропию для значений нашего атрибута «работа» и «публичность»:
Двигаясь дальше, мы вычисляем энтропию по отношению к нашему объекту:
Наконец, мы вычисляем информационный прирост нашей функции:
Итак, если мы выберем в качестве корня нашего дерева функцию «Объект», мы получим 0,04 бита информации. Если мы повторим эту процедуру также для «Время отправки» и «Длина сообщения», мы получим соответственно 0,01 и 0,11. Следовательно, теперь мы знаем, что наше дерево должно быть разбито, начиная с «длины сообщения». Мы можем визуализировать этот первый этап нашего дерева, а также два новых набора данных, которые мы получаем после разделения нашей функции:
Как видите, у нас теперь две ветки. Ветвь с энтропией, равной 0, должна быть преобразована в листовой узел: в этом случае дальнейшее разделение не требуется. Напротив, ветвь с энтропией больше 0 требует дальнейшего расщепления. Затем те же рассуждения повторяются для новых узлов, пока мы не достигнем окончательного результата. А именно, это привело к тому, что для «короткой» ветви разделение функции «Объект» гарантирует больший IG, чем «Время отправки» (0,025 против 0,015).
То же самое рассуждение справедливо для каждого узла принятия решения, поэтому вы можете продолжить свои вычисления получения информации и соответствующим образом разделить их.
Теперь давайте применим эту концепцию при построении нашего алгоритма дерева решений на нашем хорошо известном наборе данных Iris:
data(iris) names(iris) table(iris$Species) head(iris)
install.packages("psych")
library(psych)
describe(iris)
Теперь давайте установим пакет древовидного классификатора и обучим нашу модель нашим данным:
library(rpart) library(rpart.plot) tree<- rpart(Species~., data = data_train, method = 'class') rpart.plot(tree)
Как видите, наша модель решила выбрать в качестве корневого объект petal.Length: потому что это объект, разделение которого гарантирует максимальный объем информации. Действительно, при использовании в качестве порога значения 2,5 одна ветвь (‹2,5) уже стала листом, и дальнейшее разбиение не требуется. С другой стороны, другая ветвь (›2.5) по-прежнему требует дальнейшего разделения на функцию Petal.Width: после этого модель смогла классифицировать все данные в наших трех классах.
Как я и ожидал, информационное усиление - не единственный критерий разделения, который вы можете установить для своего дерева решений (чтобы процитировать некоторые другие критерии, у нас есть коэффициент Джини, критерий хи-квадрат и критерии сокращения дисперсии). Кроме того, после построения ваше дерево необходимо оптимизировать, чтобы уменьшить переоснащение (так называемая фаза «обрезки листьев»).
Тем не менее, получение информации определенно является действительным критерием и, вероятно, наиболее интуитивно понятным.
