Алгоритм AdaBoost

Продолжаем разбор алгоритмов в рамках «Топ-10 data mining алгоритмов» и рассмотрим алгоритм AdaBoost.

Что он делает? AdaBoost – это алгоритм усиления классификаторов.

Как вы помните, классификатор пытается предсказать по уже известным ему данным, к какому классу будут относиться новые данные.

Что такое усиление? Усиление – это ансамблевый алгоритм обучения, который берет множество алгоритмов обучения, например, деревья решений, и объединяет их. Целью является взять набор или группу слабых классификаторов и объединить их в один сильный.

В чем разница между сильным и слабым классификатором? Слабый классификатор производит классификацию с точностью чуть выше шанса. Популярный пример слабого классификатора – это так называемый «решающий пень» – одноуровневое дерево решений.

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

Какие есть примеры AdaBoost? Давайте начнем с трех слабых классификаторов. Мы обучим их за 10 итераций на тренировочном наборе данных о пациентах. Набор данных содержит детали медицинских записей пациента.

Вопрос в том…

Как нам предсказать, заболеет ли человек раком?

Вот как AdaBoost отвечает на этот вопрос:

Раунд 1: AdaBoost берет часть данных тренировочного набора и проверяет, насколько точен каждый классификатор. В результате выбирается наилучший из них.
Дополнительно те примеры, которые были классифицированы неверно, приобретают больший вес в следующей итерации.

Еще одна вещь – лучшему классификатору также присваивается вес в зависимости от его точности, а сам классификатор включается в ансамбль (на первом шаге ансамбль состоит из одного классификатора).

Раунд 2: AdaBoost повторно пытается выявить лучший классификатор.
И здесь возникает загвоздка:

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

Почему?

Это – словно переходить на следующий уровень в видеоигре и не начинать все заново, если персонаж погибает. Вместо этого вы начинаете с уровня 2, и всеми силами стараетесь перейти на третий уровень.

Точно так же первый классификатор, вероятно, классифицировал некоторых пациентов верно. Вместо того, чтобы пытаться классифицировать их повторно, давайте сфокусируемся на тех, кого классифицировать не удалось.

Лучший классификатор снова взвешен и включен в ансамбль – неверно классифицированные пациенты также взвешены и получают больший шанс быть выбранными повторно.

После 10 раундов: Мы получаем ансамбль взвешенных классификаторов, натренированных и перетренированных на неправильно классифицированных данных из предыдущих итераций.

Требует ли этот метод обучения или он самообучающийся? Этот метод требует обучения, поскольку на каждой итерации по размеченному набору данных тренируются более слабые классификаторы.

Почему именно AdaBoost? AdaBoost – это просто. Алгоритм относительно легок в программировании.

Кроме того он очень быстрый! Слабые классификаторы обычно проще, чем сильные. Простота означает высокую скорость исполнения.

Еще кое-что…

Это супер-элегантный способ автоматической настройки классификатора, поскольку каждая успешная итерация AdaBoost корректирует вес лучшего классификатора. Вам нужно только указать количество итераций.

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

Где он используется? AdaBoost имеет тонну вариаций и реализаций. Вот некоторые из них:

scikit-learn
ICSIBoost
Обобщенная усиленная регрессионная модель gbm (Generalized Boosted Regression Models)

Источник

Алгоритм AdaBoost (видео)

Дополнительно: Презентация по алгоритму и псевдокод

Реализация AdaBoost в R

Пример 1. Пакет «fastAdaboost»

install.packages("fastAdaboost")
library("fastAdaboost")
set.seed(9999)

num_each <- 1000
fakedata <- data.frame( X=c(rnorm(num_each,0,1),rnorm(num_each,1.5,1)), Y=c(rep(0,num_each),rep(1,num_each) ) )
fakedata$Y <- factor(fakedata$Y)
#run adaboost
test_adaboost <- adaboost(Y~X, fakedata, 10)
#print(A)
pred <- predict( test_adaboost, newdata=fakedata)
print(paste("Adaboost Error on fakedata:",pred$error))
#> [1] "Adaboost Error on fakedata: 0.1225"
print(table(pred$class,fakedata$Y))
#>    
#>       0   1
#>   0 848  93
#>   1 152 907

test_real_adaboost <- real_adaboost(Y~X, fakedata, 10)
pred_real <- predict(test_real_adaboost,newdata=fakedata)
print(paste("Real Adaboost Error on fakedata:", pred_real$error))
#> [1] "Real Adaboost Error on fakedata: 0.1105"
print(table(pred_real$class,fakedata$Y))
#>    
#>       0   1
#>   0 906 127
#>   1  94 873

install.packages("fastAdaboost")

library("fastAdaboost")

set.seed(9999)

num_each <- 1000

fakedata <- data.frame( X=c(rnorm(num_each,0,1),rnorm(num_each,1.5,1)), Y=c(rep(0,num_each),rep(1,num_each) ) )

fakedata$Y <- factor(fakedata$Y)

#run adaboost

test_adaboost <- adaboost(Y~X, fakedata, 10)

#print(A)

pred <- predict( test_adaboost, newdata=fakedata)

print(paste("Adaboost Error on fakedata:",pred$error))

#> [1] "Adaboost Error on fakedata: 0.1225"

print(table(pred$class,fakedata$Y))

#> 0 1

#> 0 848 93

#> 1 152 907

test_real_adaboost <- real_adaboost(Y~X, fakedata, 10)

pred_real <- predict(test_real_adaboost,newdata=fakedata)

print(paste("Real Adaboost Error on fakedata:", pred_real$error))

#> [1] "Real Adaboost Error on fakedata: 0.1105"

print(table(pred_real$class,fakedata$Y))

#> 0 1

#> 0 906 127

#> 1 94 873

Источник и документация

Пример 2. Пакет «adabag»

## rpart library should be loaded
data(iris)
iris.adaboost <- boosting(Species~., data=iris, boos=TRUE, mfinal=5)
iris.adaboost
## Data Vehicle (four classes)
data(Vehicle)
l <- length(Vehicle[,1])
sub <- sample(1:l,2*l/3)
mfinal <- 10
maxdepth <- 5
Vehicle.rpart <- rpart(Class~.,data=Vehicle[sub,],maxdepth=maxdepth)
Vehicle.rpart.pred <- predict(Vehicle.rpart,newdata=Vehicle[-sub, ],type="class")
tb <- table(Vehicle.rpart.pred,Vehicle$Class[-sub])
error.rpart <- 1-(sum(diag(tb))/sum(tb))
tb
error.rpart
Vehicle.adaboost <- boosting(Class ~.,data=Vehicle[sub, ],mfinal=mfinal, coeflearn="Zhu",
control=rpart.control(maxdepth=maxdepth))
Vehicle.adaboost.pred <- predict.boosting(Vehicle.adaboost,newdata=Vehicle[-sub, ])
Vehicle.adaboost.pred$confusion
Vehicle.adaboost.pred$error
#comparing error evolution in training and test set
errorevol(Vehicle.adaboost,newdata=Vehicle[sub, ])->evol.train
errorevol(Vehicle.adaboost,newdata=Vehicle[-sub, ])->evol.test
plot.errorevol(evol.test,evol.train)

## rpart library should be loaded

data(iris)

iris.adaboost <- boosting(Species~., data=iris, boos=TRUE, mfinal=5)

iris.adaboost

## Data Vehicle (four classes)

data(Vehicle)

l <- length(Vehicle[,1])

sub <- sample(1:l,2*l/3)

mfinal <- 10

maxdepth <- 5

Vehicle.rpart <- rpart(Class~.,data=Vehicle[sub,],maxdepth=maxdepth)

Vehicle.rpart.pred <- predict(Vehicle.rpart,newdata=Vehicle[-sub, ],type="class")

tb <- table(Vehicle.rpart.pred,Vehicle$Class[-sub])

error.rpart <- 1-(sum(diag(tb))/sum(tb))

error.rpart

Vehicle.adaboost <- boosting(Class ~.,data=Vehicle[sub, ],mfinal=mfinal, coeflearn="Zhu",

control=rpart.control(maxdepth=maxdepth))

Vehicle.adaboost.pred <- predict.boosting(Vehicle.adaboost,newdata=Vehicle[-sub, ])

Vehicle.adaboost.pred$confusion

Vehicle.adaboost.pred$error

#comparing error evolution in training and test set

errorevol(Vehicle.adaboost,newdata=Vehicle[sub, ])->evol.train

errorevol(Vehicle.adaboost,newdata=Vehicle[-sub, ])->evol.test

plot.errorevol(evol.test,evol.train)

Больше примеров и документация

Реализация AdaBoost в Python

Пример 1. Two-class AdaBoost

print(__doc__)

# Author: Noel Dawe <noel.dawe@gmail.com>
#
# License: BSD 3 clause

import numpy as np
import matplotlib.pyplot as plt

from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_gaussian_quantiles


# Construct dataset
X1, y1 = make_gaussian_quantiles(cov=2.,
                                 n_samples=200, n_features=2,
                                 n_classes=2, random_state=1)
X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,
                                 n_samples=300, n_features=2,
                                 n_classes=2, random_state=1)
X = np.concatenate((X1, X2))
y = np.concatenate((y1, - y2 + 1))

# Create and fit an AdaBoosted decision tree
bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1),
                         algorithm="SAMME",
                         n_estimators=200)

bdt.fit(X, y)

plot_colors = "br"
plot_step = 0.02
class_names = "AB"

plt.figure(figsize=(10, 5))

# Plot the decision boundaries
plt.subplot(121)
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
                     np.arange(y_min, y_max, plot_step))

Z = bdt.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)
plt.axis("tight")

# Plot the training points
for i, n, c in zip(range(2), class_names, plot_colors):
    idx = np.where(y == i)
    plt.scatter(X[idx, 0], X[idx, 1],
                c=c, cmap=plt.cm.Paired,
                label="Class %s" % n)
plt.xlim(x_min, x_max)
plt.ylim(y_min, y_max)
plt.legend(loc='upper right')
plt.xlabel('x')
plt.ylabel('y')
plt.title('Decision Boundary')

# Plot the two-class decision scores
twoclass_output = bdt.decision_function(X)
plot_range = (twoclass_output.min(), twoclass_output.max())
plt.subplot(122)
for i, n, c in zip(range(2), class_names, plot_colors):
    plt.hist(twoclass_output[y == i],
             bins=10,
             range=plot_range,
             facecolor=c,
             label='Class %s' % n,
             alpha=.5)
x1, x2, y1, y2 = plt.axis()
plt.axis((x1, x2, y1, y2 * 1.2))
plt.legend(loc='upper right')
plt.ylabel('Samples')
plt.xlabel('Score')
plt.title('Decision Scores')

plt.tight_layout()
plt.subplots_adjust(wspace=0.35)
plt.show()

print(__doc__)

# Author: Noel Dawe <noel.dawe@gmail.com>

# License: BSD 3 clause

import numpy as np

import matplotlib.pyplot as plt

from sklearn.ensemble import AdaBoostClassifier

from sklearn.tree import DecisionTreeClassifier

from sklearn.datasets import make_gaussian_quantiles

# Construct dataset

X1, y1 = make_gaussian_quantiles(cov=2.,

n_samples=200, n_features=2,

n_classes=2, random_state=1)

X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,

n_samples=300, n_features=2,

n_classes=2, random_state=1)

X = np.concatenate((X1, X2))

y = np.concatenate((y1, - y2 + 1))

# Create and fit an AdaBoosted decision tree

bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1),

algorithm="SAMME",

n_estimators=200)

bdt.fit(X, y)

plot_colors = "br"

plot_step = 0.02

class_names = "AB"

plt.figure(figsize=(10, 5))

# Plot the decision boundaries

plt.subplot(121)

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1

y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1

xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),

np.arange(y_min, y_max, plot_step))

Z = bdt.predict(np.c_[xx.ravel(), yy.ravel()])

Z = Z.reshape(xx.shape)

cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)

plt.axis("tight")

# Plot the training points

for i, n, c in zip(range(2), class_names, plot_colors):

idx = np.where(y == i)

plt.scatter(X[idx, 0], X[idx, 1],

c=c, cmap=plt.cm.Paired,

label="Class %s" % n)

plt.xlim(x_min, x_max)

plt.ylim(y_min, y_max)

plt.legend(loc='upper right')

plt.xlabel('x')

plt.ylabel('y')

plt.title('Decision Boundary')

# Plot the two-class decision scores

twoclass_output = bdt.decision_function(X)

plot_range = (twoclass_output.min(), twoclass_output.max())

plt.subplot(122)

for i, n, c in zip(range(2), class_names, plot_colors):

plt.hist(twoclass_output[y == i],

bins=10,

range=plot_range,

facecolor=c,

label='Class %s' % n,

alpha=.5)

x1, x2, y1, y2 = plt.axis()

plt.axis((x1, x2, y1, y2 * 1.2))

plt.legend(loc='upper right')

plt.ylabel('Samples')

plt.xlabel('Score')

plt.title('Decision Scores')

plt.tight_layout()

plt.subplots_adjust(wspace=0.35)

plt.show()

Источник примера 1

Пример 2. Multi-class AdaBoosted Decision Trees

print(__doc__)

# Author: Noel Dawe <noel.dawe@gmail.com>
#
# License: BSD 3 clause

from sklearn.externals.six.moves import zip

import matplotlib.pyplot as plt

from sklearn.datasets import make_gaussian_quantiles
from sklearn.ensemble import AdaBoostClassifier
from sklearn.metrics import accuracy_score
from sklearn.tree import DecisionTreeClassifier


X, y = make_gaussian_quantiles(n_samples=13000, n_features=10,
                               n_classes=3, random_state=1)

n_split = 3000

X_train, X_test = X[:n_split], X[n_split:]
y_train, y_test = y[:n_split], y[n_split:]

bdt_real = AdaBoostClassifier(
    DecisionTreeClassifier(max_depth=2),
    n_estimators=600,
    learning_rate=1)

bdt_discrete = AdaBoostClassifier(
    DecisionTreeClassifier(max_depth=2),
    n_estimators=600,
    learning_rate=1.5,
    algorithm="SAMME")

bdt_real.fit(X_train, y_train)
bdt_discrete.fit(X_train, y_train)

real_test_errors = []
discrete_test_errors = []

for real_test_predict, discrete_train_predict in zip(
        bdt_real.staged_predict(X_test), bdt_discrete.staged_predict(X_test)):
    real_test_errors.append(
        1. - accuracy_score(real_test_predict, y_test))
    discrete_test_errors.append(
        1. - accuracy_score(discrete_train_predict, y_test))

n_trees_discrete = len(bdt_discrete)
n_trees_real = len(bdt_real)

# Boosting might terminate early, but the following arrays are always
# n_estimators long. We crop them to the actual number of trees here:
discrete_estimator_errors = bdt_discrete.estimator_errors_[:n_trees_discrete]
real_estimator_errors = bdt_real.estimator_errors_[:n_trees_real]
discrete_estimator_weights = bdt_discrete.estimator_weights_[:n_trees_discrete]

plt.figure(figsize=(15, 5))

plt.subplot(131)
plt.plot(range(1, n_trees_discrete + 1),
         discrete_test_errors, c='black', label='SAMME')
plt.plot(range(1, n_trees_real + 1),
         real_test_errors, c='black',
         linestyle='dashed', label='SAMME.R')
plt.legend()
plt.ylim(0.18, 0.62)
plt.ylabel('Test Error')
plt.xlabel('Number of Trees')

plt.subplot(132)
plt.plot(range(1, n_trees_discrete + 1), discrete_estimator_errors,
         "b", label='SAMME', alpha=.5)
plt.plot(range(1, n_trees_real + 1), real_estimator_errors,
         "r", label='SAMME.R', alpha=.5)
plt.legend()
plt.ylabel('Error')
plt.xlabel('Number of Trees')
plt.ylim((.2,
         max(real_estimator_errors.max(),
             discrete_estimator_errors.max()) * 1.2))
plt.xlim((-20, len(bdt_discrete) + 20))

plt.subplot(133)
plt.plot(range(1, n_trees_discrete + 1), discrete_estimator_weights,
         "b", label='SAMME')
plt.legend()
plt.ylabel('Weight')
plt.xlabel('Number of Trees')
plt.ylim((0, discrete_estimator_weights.max() * 1.2))
plt.xlim((-20, n_trees_discrete + 20))

# prevent overlapping y-axis labels
plt.subplots_adjust(wspace=0.25)
plt.show()

print(__doc__)

# Author: Noel Dawe <noel.dawe@gmail.com>

# License: BSD 3 clause

from sklearn.externals.six.moves import zip

import matplotlib.pyplot as plt

from sklearn.datasets import make_gaussian_quantiles

from sklearn.ensemble import AdaBoostClassifier

from sklearn.metrics import accuracy_score

from sklearn.tree import DecisionTreeClassifier

X, y = make_gaussian_quantiles(n_samples=13000, n_features=10,

n_classes=3, random_state=1)

n_split = 3000

X_train, X_test = X[:n_split], X[n_split:]

y_train, y_test = y[:n_split], y[n_split:]

bdt_real = AdaBoostClassifier(

DecisionTreeClassifier(max_depth=2),

n_estimators=600,

learning_rate=1)

bdt_discrete = AdaBoostClassifier(

DecisionTreeClassifier(max_depth=2),

n_estimators=600,

learning_rate=1.5,

algorithm="SAMME")

bdt_real.fit(X_train, y_train)

bdt_discrete.fit(X_train, y_train)

real_test_errors = []

discrete_test_errors = []

for real_test_predict, discrete_train_predict in zip(

bdt_real.staged_predict(X_test), bdt_discrete.staged_predict(X_test)):

real_test_errors.append(

1. - accuracy_score(real_test_predict, y_test))

discrete_test_errors.append(

1. - accuracy_score(discrete_train_predict, y_test))

n_trees_discrete = len(bdt_discrete)

n_trees_real = len(bdt_real)

# Boosting might terminate early, but the following arrays are always

# n_estimators long. We crop them to the actual number of trees here:

discrete_estimator_errors = bdt_discrete.estimator_errors_[:n_trees_discrete]

real_estimator_errors = bdt_real.estimator_errors_[:n_trees_real]

discrete_estimator_weights = bdt_discrete.estimator_weights_[:n_trees_discrete]

plt.figure(figsize=(15, 5))

plt.subplot(131)

plt.plot(range(1, n_trees_discrete + 1),

discrete_test_errors, c='black', label='SAMME')

plt.plot(range(1, n_trees_real + 1),

real_test_errors, c='black',

linestyle='dashed', label='SAMME.R')

plt.legend()

plt.ylim(0.18, 0.62)

plt.ylabel('Test Error')

plt.xlabel('Number of Trees')

plt.subplot(132)

plt.plot(range(1, n_trees_discrete + 1), discrete_estimator_errors,

"b", label='SAMME', alpha=.5)

plt.plot(range(1, n_trees_real + 1), real_estimator_errors,

"r", label='SAMME.R', alpha=.5)

plt.legend()

plt.ylabel('Error')

plt.xlabel('Number of Trees')

plt.ylim((.2,

max(real_estimator_errors.max(),

discrete_estimator_errors.max()) * 1.2))

plt.xlim((-20, len(bdt_discrete) + 20))

plt.subplot(133)

plt.plot(range(1, n_trees_discrete + 1), discrete_estimator_weights,

"b", label='SAMME')

plt.legend()

plt.ylabel('Weight')

plt.xlabel('Number of Trees')

plt.ylim((0, discrete_estimator_weights.max() * 1.2))

plt.xlim((-20, n_trees_discrete + 20))

# prevent overlapping y-axis labels

plt.subplots_adjust(wspace=0.25)

plt.show()

Источник примера 2

Немного документации и больше примеров на Питоне

Алгоритм AdaBoost

Алгоритм AdaBoost (видео)

Реализация AdaBoost в R

Реализация AdaBoost в Python

Искать

Недавнее

Тематика

Data Scientist # 1

Данные — новый актив!

Войдите в свой аккаунт