Алгоритм Бэггинг

Бэггинг

Здравствуйте и вновь добро пожаловать на занятия по теме «Машинное обучение с учителем на языке Python: ансамблевые методы».

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

Итак,работает это следующим образом. Мы запускаем цикл B раз, каждый раз создавая модель, выборку бутстрепа,обучая модель и затем добавляя её в список моделей:

# обучение

models = []

for b=1..B:

    model =Model()

    Xb, Yb =resample(X)

   model.fit(Xb, Yb)

   models.append(model)

Прогнозделается путём усреднения каждой модели в случае регрессии или путём«голосования» в случае классификации:

# регрессия

def predict(X):

    returnnp.mean([model.predict(X) for model in models], axis=1)

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

# классификация

def predict_one(x):

    votes = {}

    for model inmodels:

        k =model.predict(x)

       votes[k]++

    argmax = 0 # безсортировки, это O(NlogN)

    for k, vin votes.iteritems():

        if v> argmax:

           argmax = k

    return k

Другаявозможность состоит в том, чтобы создать матрицу NxK и накапливать прогнозы. Поскольку Numpy позволяет нам индексировать массивы, обеспечивмассив индексами, мы можем использовать их для накапливания голосов для каждойсоответствующей выборки и пары классов. В случае двоичной классификации можносделать ещё проще. Предположим, что имеется B моделей, тогда общее количество голосов будетвсегда между 0 и B.Сложив все голоса и поделив на B, получим число между 0 и 1, которое можно простоокруглить.

# классификация

def predict(X):

    output =np.zeros((N,K))

    for model inmodels:

       output[np.arrange(N), model.predict(X)] += 1

    return output.argmax(axis=1)

Бэггинг. Деревья регрессии

Итак,начнём с того, что импортируем Numpy, Matlotlib, DecisionTreeRegressor, а также shuffle.

import numpy as np

import matplotlib.pyplot as plt

from sklearn.tree import DecisionTreeRegressor

from sklearn.utils import shuffle

Итак,первый этап – создание данных. У нас будет 100 точек.

T = 100

x_axis = np.linspace(0, 2*np.pi, T)

y_axis = np.sin(x_axis)

Учебнымибудут 30 точек. Не забывайте перевести данные в формат NxD.

N = 30

idx = np.random.choice(T, size=N, replace=False)

Xtrain = x_axis[idx].reshape(N, 1)

Ytrain = y_axis[idx]

Вначалепопробуем одиночное дерево решений, чтобы можно было сравнить с ним результатдействия ансамбля.

model = DecisionTreeRegressor()

model.fit(Xtrain, Ytrain)

prediction = model.predict(x_axis.reshape(T, 1))

print “score for 1 tree:”, model.score(x_axis.reshape(T,1), y_axis)

Теперьможем вывести на экран прогноз одиночного дерева и действительной кривой.

plt.plot(x_axis, prediction)

plt.plot(x_axis, y_axis)

plt.show()

Этовсё, что касается одиночного дерева. Теперь попробуем бэггинг.

class BaggedTreeRegressor:

  def __init__(self, B):

    self.B = B

Сначала функция fit.

  def fit(self, X, Y):

    N = len(X)

    self.models= []

    for b in xrange(self.B):

      idx =np.random.choice(N, size=N, replace=True)

      Xb =X[idx]

      Yb =Y[idx]

      model =DecisionTreeRegressor()

     model.fit(Xb, Yb)

     self.models.append(model)

Теперь функция predict. Напоминаю, тут вычисляется лишь среднее значение.

  def predict(self,X):

    predictions= np.zeros(len(X))

    for model inself.models:

     predictions += model.predict(X)

    returnpredictions / self.B

Далее – функция score.

  def score(self, X, Y):

    d1 = Y –self.predict(X)

    d2 = Y –Y.mean()

    return 1 –d1.dot(d1) / d2.dot(d2)

Иследующее – просто испытать модель. B установим равным 200. Надо сказать, что значениямежду 200 и 500 являются общеупотребимыми при установлении значения B.

model = BaggedTreeRegressor(200)

model.fit(Xtrain, Ytrain)

print “score for bagged tree:”,model.score(x_axis.reshape(T, 1), y_axis)

prediction = model.predict(x_axis.reshape(T, 1))

Инаконец, выводим на экран графики.

plt.plot(x_axis, prediction)

plt.plot(x_axis, y_axis)

plt.show()

Запустими посмотрим, что у нас получится.

Вначалевидим собственно единичное дерево решений, поэтому оно не сглажено. А затем –дерево решений с применением бэггинга. Оно куда более сглаженное.

И, как видим, иногда у нас получается лучший результат, а иногда – нет.

Бэггинг. Деревья классификации

Напишем классификатор с применением бэггинга. Если вы не хотите писать код самостоятельно, а лишь запустить, то соответствующий файл курса в репозитарии называется bagging_classification.py.

Итак, начинаем с импорта Numpy, Matplotlib, DecisionTreeClassifier, а также функции shuffle и plot_decision_boundary.

import numpy as np

import matplotlib.pyplot as plt

from sklearn.tree import DecisionTreeClassifier

from sklearn.utils import shuffle

from util import plot_decision_boundary

np.random.seed(10)

Итак,первый этап – создание данных. У нас будет 500 точек и две размерности.Сгенерируем набор случайных чисел с гауссовым распределением.

N = 500

D = 2

X = np.random.randn(N, D)

Нашнабор данных будет представлять зашумленное XOR.

sep = 2

X[:125] += np.array([sep, sep])

X[125:250] += np.array([sep, -sep])

X[250:375] += np.array([-sep, -sep])

X[375:] += np.array([-sep, sep])

Y = np.array([0]*125 + [1]*125 + [0]*125 + [1]*125)

Ивыведем данные на экран, чтобы вы имели представление об их виде.

plt.scatter(X[:,0], X[:,1], s=100, c=Y, alpha=0.5)

plt.show()

Иможем наблюдать вид наших данных.

Продолжимнаписание кода и вновь-таки начнём с единичного дерева решений, чтобыпосмотреть, как оно справится с задачей.

model = DecisionTreeClassifier()

model.fit(X, Y)

print “score for 1 tree:”, model.score(X, Y)

Ивновь выводим данные на экран, но теперь – с границей принятия решения.

plt.scatter(X[:,0], X[:,1], s=100, c=Y, alpha=0.5)

plot_decision_boundary(X, model)

plt.show()

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

Продолжими создадим модель с бэггингом.

class BaggedTreeClassifier:

  def __init__(self, B):

    self.B = B

Напишем функцию fit. Она очень схожа на написанную ранее.

  def fit(self, X, Y):

    N = len(X)

    self.models= []

    for b in xrange(self.B):

      idx =np.random.choice(N, size=N, replace=True)

      Xb =X[idx]

      Yb =Y[idx]

Глубинудерева установим равной 2, чтобы граница принятия решения была болеесглаженной.

      model =DecisionTreeClassifier(max_depth=2)

     model.fit(Xb, Yb)

     self.models.append(model)

Следующей идёт функция predict.

  def predict(self, X):

    predictions= np.zeros(len(X))

    for model inself.models:

     predictions += model.predict(X)

    returnnp.round(predictions / self.B)

И функция score для вычисления точности прогноза.

  def score(self, X, Y):

    P =self.predict(X)

    returnnp.mean(Y == P)

Теперьсобственно модель.

model = BaggedTreeClassifier(200)

model.fit(X, Y)

print “score for bagged model:”,model.score(X, Y)

Точностьдолжна быть несколько ниже, чем в предыдущий раз, поскольку не будетпереобученности.

plt.scatter(X[:,0], X[:,1], s=100, c=Y, alpha=0.5)

plot_decision_boundary(X, model)

plt.show()

Запустими посмотрим, что у нас получится.

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

Пакетирование

В заключение давайте рассмотрим специальный метод объединения моделей, который называется пакетированием (stacking).

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

Возникаетважный вопрос – как найти эти весовые коэффициенты? Есть много способов найтиих, и мы обсудим по крайней мере два из них.

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

Возникаетважный вопрос – как найти эти весовые коэффициенты? Есть много способов найтиих, и мы обсудим по крайней мере два из них.

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

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

Однаконадо отметить, что мы не знаем действительного распределения генеральнойсовокупности, а следовательно, не можем вычислить это ожидаемое значение. Можетвозникнуть соблазн заменить учебные данные истинной совокупностью данных, новозникает как минимум один случай, когда это не помогает. Напомним, что вслучае линейной регрессии чем больше у нас столбцов, тем меньше коэффициентдетерминации R2. Скажем, если fm(x) – линейнаямодель с mвходных переменных, то последняя из них fM(x), имеющая наибольшее количество входныхпеременных, будет в любом случае лучшей моделью. В этом случае её весовойкоэффициент wMбудет равен 1, а весовые коэффициенты остальных будут равны 0, поскольку имеетсмысл использовать только линейную модель с максимальным количеством входныхпеременных.

Втаком случае следует оценить ожидаемое значение. Метод пакетированиязаключается в следующем: мы преобразуем ожидаемое значение в сумму N примеров синдексами i.При вычислении fm(x) для точки xi мы обучаем fm(x) на всём наборе данных, кроме xi. Обозначим эточерез верхний индекс: fmi(x). Тогда

Возникаетследующий очевидный вопрос: как решить это уравнение? Можно сделатьограничение, указав, что все wm должны быть больше нуля, а их суммадолжна равняться единице:

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

Можнозаметить, что этот метод очень похож на перекрёстную проверку с исключением.Напомню, при такой проверке обучение происходит на всех примерах, кроме одного,а проверка – на последнем примере, и это, как правило, затрагивает весь наборданных. Обычно при перекрёстной проверке нас интересует лучшая модель с лучшимизначениями гиперпараметров, а не объединение моделей. Но выбор лучшей моделиэквивалентен присвоению одного из wm значения 1 и присвоению остальным wm значения 0.Другими словами,  если в соответствии срезультатами перекрёстной проверки лучшей моделью является m*, тоустанавливаем wm* = 1, остальные wm = 0.

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

Можнозаметить, что этот метод очень похож на перекрёстную проверку с исключением.Напомню, при такой проверке обучение происходит на всех примерах, кроме одного,а проверка – на последнем примере, и это, как правило, затрагивает весь наборданных. Обычно при перекрёстной проверке нас интересует лучшая модель с лучшимизначениями гиперпараметров, а не объединение моделей. Но выбор лучшей моделиэквивалентен присвоению одного из wm значения 1 и присвоению остальным wm значения 0.Другими словами,  если в соответствии срезультатами перекрёстной проверки лучшей моделью является m*, тоустанавливаем wm* = 1, остальные wm = 0.

Андрей Никитенко
Андрей Никитенко
Задать вопрос эксперту
Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

Share via
Copy link