Понимание AdaBoost для дерева решений

Реализация с R

Деревья решений - популярные алгоритмы машинного обучения, используемые как для задач регрессии, так и для классификации. Их популярность в основном связана с их интерпретируемостью и репрезентативностью, поскольку они имитируют способ принятия решений человеческим мозгом.

В моей предыдущей статье я представил несколько ансамблевых методов для деревьев решений, цель которых - преобразовать набор слабых классификаторов в более сильный. Здесь я собираюсь подробнее остановиться на методе Boosting, в котором алгоритм учится на своей ошибке на каждой итерации. Более конкретно, я собираюсь шаг за шагом объяснить идею, лежащую в основе Adaboost, и то, как реализовать ее с помощью R.

Идея Adaboost

Основное различие между Adaboost и методами упаковки (включая случайные леса) заключается в том, что в конце процесса, когда всем классификаторам, созданным во время итераций, будет предложено проголосовать за цель нового наблюдения, появятся деревья с голосование тяжелее, чем у других. Это деревья, которые показали наилучшие результаты на всех итерациях (поэтому они показали очень мало ошибок в классификации). Допустим, в конце концов, одни деревья скажут больше, чем другие. Эта «важность слова» измеряется (и обновляется) на протяжении всей итерационной процедуры.

Помимо этого, другой важной особенностью Adaboost, как и ожидалось, является его способность учиться на прошлых ошибках, поскольку на каждой итерации следующий классификатор строится на основе ошибочной классификации прошлой ошибки.

Давайте теперь посмотрим, как конкретно работает алгоритм.

Алгоритм

Представьте, что у нас есть набор данных с N наблюдениями, P ковариатами и одной двоичной целевой переменной y = 1, -1. Это будет наш поезд.

С помощью этого фреймворка вы можете разработать любую интересующую вас задачу (а именно, является ли электронное письмо спамом или нет, будет ли завтра погода солнечной или нет…).

Первое, что мы делаем, это присваиваем каждой строке вес, который показывает, насколько важно для этого наблюдения быть хорошо классифицированным. Мы инициализируем эти веса равными 1 / N, чтобы на первой итерации при обучении первого классификатора они не имели значения.

Теперь мы обучаем наш первый классификатор G (x) на нашем наборе данных, а затем проверяем, какие из наблюдений неправильно классифицированы, поскольку мы хотим вычислить общую ошибку, которая отличается от стандартной ошибки неправильной классификации, поскольку это взвешенное суммирование:

Как видите, у нас есть самонормированное суммирование взвешенных ошибок (когда целевое значение отличается от установленного). Обратите внимание, что из-за способа построения общая ошибка всегда будет ограничена от 0 до 1. С помощью этой величины мы можем вычислить то, что мы назвали «важностью слова»:

Как видите, чем выше ошибка, тем менее важным будет голос этого дерева в конце дня. Мы также можем визуализировать это графически:

error = seq(0,1,0.001)
alpha = log((1-error)/error)
plot(error,alpha, type='line')

С помощью этой метрики альфа мы теперь можем обновлять веса таким образом, чтобы веса, соответствующие неверно классифицированным наблюдениям, были выше на следующей итерации. Таким образом, когда мы поместим следующее дерево в новый взвешенный набор данных, стоимость неправильной классификации этих наблюдений будет выше, и дерево будет очень осторожно, чтобы не ошибочно классифицировать их снова (поскольку это повлечет за собой более высокую стоимость). Итак, для всех наблюдений i = 1,2, .., N мы обновляем i-й вес следующим образом.

Если мы повторим эту процедуру для M итераций, в конце дня у нас будет M классификаторов, каждый с взвешенным голосом, и, если мы хотим предсказать цель нового наблюдения x *, формула будет следующей:

Таким образом, будут некоторые деревья, результат которых будет сильно определяющим в окончательном решении (-1 или 1), в то время как другими можно будет пренебречь.

Давайте теперь посмотрим очень краткую реализацию этой процедуры с помощью R:

data = data.frame( X=c(rnorm(100,0,1),rnorm(100,1,1)), Y=c(rep(0,100),rep(1,100) ) )
data$Y =factor(data$Y)
model =adaboost(Y~X, data, 10)
pred =predict( model ,newdata=data)

Давайте посмотрим на сводку модели и ее ошибку прогноза (которая равна ошибке неправильной классификации в наборе поездов):

print(pred$error)
print(model)

Мы также можем получить окончательные значения "важности сказанного":

model$weights

Как видите, есть некоторые деревья (например, первое), окончательное голосование которых очень важно, в то время как другие (например, последнее) менее важны.

Наконец, мы можем сравнить его ошибку с ошибкой одного дерева:

single_model=tree(Y∼X, data)
summary(single_model)

Как видите, наш усиленный классификатор сильнее классификатора одного дерева.

Заключение

Ансамблевые методы - это мощные методы, которые могут в значительной степени повысить точность прогнозирования деревьев решений. Однако предостережение в том, что они несколько затрудняют представление и интерпретацию окончательных результатов. В самом деле, как мы сказали в самом начале, наиболее заметной особенностью деревьев решений является их интерпретируемость и легкость понимания, что в мире алгоритмов, которые выглядят как «черный ящик», является важной ценностью. Тем не менее, доступны некоторые визуальные альтернативные варианты, и, если объединение нескольких деревьев повысит точность, оно того стоит.

Понимание AdaBoost для дерева решений