Виды ансамблей
Содержание
Ансамбль
Ансамбль алгоритмов (методов) — метод, который использует несколько обучающих алгоритмов с целью получения лучшей эффективности прогнозирования, чем можно было бы получить от каждого обучающего алгоритма по отдельности.
Рассмотрим задачу классификации на классов: .
Пусть имеется классификаторов ("экспертов"): .
.
Тогда давайте посмотрим новый классификатор на основе данных:
Простое голосование: .
Взвешенное голосование: .
Где
Теорема Кондорсе о присяжных
| Теорема: |
Если каждый член жюри присяжных имеет независимое мнение, и если вероятность правильного решения члена жюри больше 0.5, то тогда вероятность правильного решения присяжных в целом возрастает с увеличением количества членов жюри, и стремится к единице. Если же вероятность быть правым у каждого из членов жюри меньше 0.5, то вероятность принятия правильного решения присяжными в целом монотонно уменьшается и стремится к нулю с увеличением количества присяжных. |
Пусть — количество присяжных, — вероятность правильного решения одного эксперта, — вероятность правильного решения всего жюри, — минимальное большинство членов жюри .
Тогда
Бэггинг
Пусть имеется выборка размера . Количество классификаторов .
Алгоритм использует метод бутстрэпа (англ. bootstrap):
Из всего множества объектов равновероятно выберем N объектов с возвращением. Это значит, что после выбора каждого из объектов мы будем возращать его в множество для выбора. Отметим, что из-за возвращения некоторые объекты могут повторяться в выбранном множестве.
Обозначим новую выборку через . Повторяя процедуру раз, сгенерируем подвыборок . Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.
Шаги алгоритма бэггинг:
- Генерируется с помощью бутстрэпа M выборок размера N для каждого классификатора.
- Производится независимое обучения каждого элементарного классификатора (каждого алгоритма, определенного на своем подпространстве).
- Производится классификация основной выборки на каждом из подпространств (также независимо).
- Принимается окончательное решение о принадлежности объекта одному из классов. Это можно сделать несколькими разными способами, подробнее описано ниже.
Окончательное решение о принадлежности объекта классу может приниматься, например, одним из следующих методов:
- Консенсус: если все элементарные классификаторы присвоили объекту одну и ту же метку, то относим объект к выбранному классу.
- Простое большинство: консенсус достижим очень редко, поэтому чаще всего используют метод простого большинства. Здесь объекту присваивается метка того класса, который определило для него большинство элементарных классификаторов.
- Взвешивание классификаторов: если классификаторов четное количество, то голосов может получиться поровну, еще возможно, что для экспертов одна из групп параметров важна в большей степени, тогда прибегают к взвешиванию классификаторов. То есть при голосовании голос классификатора умножается на его вес.
Рассмотрим задачу регрессии с базовыми алгоритмами . Предположим, что существует истинная функция ответа для всех объектов y(x), а также задано распределение p(x) на объектах. В этом случае мы можем записать ошибку каждой функции регрессии:
и записать матожидание среднеквадратичной ошибки:
Средняя ошибка построенных функций регрессии имеет вид:
Предположим, что ошибки несмещены и некоррелированы:
Построим теперь новую функцию регрессии, усредняющую ответы уже построенных:
Найдем ее среднеквадратичную ошибку:
Таким образом, усреднение ответов позволило уменьшить средний квадрат ошибки в раз.
Бустинг
Бустинг (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов.
Пусть — базовый классификатор, где — вектор параметров.
Задача состоит в том, чтоб найти такой алгоритм где — коэффиценты, такие, чтобы минимизировать эмпирический риск , где — функция потерь.
Очевидно, что сложно найти сразу Основная идея в том, чтоб найти решение пошагово . Таким образом мы сможем постепенно оценивать изменение эмпирического риска .
Алгоритмы бустинга:
- AdaBoost — адаптивный алгоритм бустинга, усиливающий классификаторы, объединяя их в «комитет». Чувствителен к шуму.
- BrownBoost — алгоритм бустинга, эффективный на зашумленных наборах данных
- GradientBoost — алгоритм бустинга, использующий идеи линейной регресии
- LogitBoost — алгоритм бустинга, использующий идеи логистической регресси
Реализации и применения бустинга
Реализации бустинга:
- XGBoost — одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год.
- CatBoost — открытая программная библиотека, разработанная компанией Яндекс.
- LightGBM — библиотека для метода машинного обучения, основанная на градиентном бустинге (англ. gradient boosting).
Применение бустинга:
- поисковые системы
- ранжирования ленты рекомендаций
- прогноз погоды
- оптимизации расхода сырья
- предсказания дефектов при производстве.
- исследованиях на Большом адронном коллайдере (БАК) для объединения информации с различных частей детектора LHCb в максимально точное, агрегированное знание о частице.
Различия между алгоритмами
- Оба алгоритма используют N базовых классификаторов
- Бустинг использует последовательное обучение
- Бэггинг использует параллельное обучение
- Оба генерируют несколько наборов данных для обучения путем случайной выборки
- Бустинг определяет вес данных, чтоб утяжелить тяжелые случаи
- Бэггинг имеет невзвешенные данные
- Оба принимают окончательное решение, усредняя N классификаторов
- В бустинге определяются веса для них
- В бэггинге они равнозначны
- Оба уменьшают дисперсию и обеспечивают более высокую стабильность
- Бэггинг может решить проблему переобучения
- Бустинг пытается уменьшить смещение, но может увеличить проблему переобучения
Примеры кода
Инициализация
from pydataset import data #Считаем данные The Boston Housing Dataset[1] df = data('Housing')
#Проверим данные
df.head().values
array([[42000.0, 5850, 3, 1, 2, 'yes', 'no', 'yes', 'no', 'no', 1, 'no'],
[38500.0, 4000, 2, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'],
[49500.0, 3060, 3, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'], ...
# Создадим словарь для слов 'no', 'yes'
d = dict(zip(['no', 'yes'], range(0,2)))
for i in zip(df.dtypes.index, df.dtypes):
if str(i[1]) == 'object':
df[i[0]] = df[i[0]].map(d)
df[‘price’] = pd.qcut(df[‘price’], 3, labels=[‘0’, ‘1’, ‘2’]).cat.codes
# Разделим множество на два
y = df['price']
X = df.drop('price', 1)
Бэггинг
# Импорты классификаторов
from sklearn.model_selection import cross_val_score
from sklearn.ensemble import BaggingClassifier, ExtraTreesClassifier, RandomForestClassifier
from sklearn.neighbors import KNeighborsClassifier
from sklearn.linear_model import RidgeClassifier
from sklearn.svm import SVC
seed = 1075
np.random.seed(seed)
# Инициализуруем классификаторы
rf = RandomForestClassifier()
et = ExtraTreesClassifier()
knn = KNeighborsClassifier()
svc = SVC()
rg = RidgeClassifier()
clf_array = [rf, et, knn, svc, rg]
for clf in clf_array:
vanilla_scores = cross_val_score(clf, X, y, cv=10, n_jobs=-1)
bagging_clf = BaggingClassifier(clf, max_samples=0.4, max_features=10, random_state=seed)
bagging_scores = cross_val_score(bagging_clf, X, y, cv=10, n_jobs=-1)
print "Mean of: {1:.3f}, std: (+/-) {2:.3f [{0}]"
.format(clf.__class__.__name__,
vanilla_scores.mean(), vanilla_scores.std())
print "Mean of: {1:.3f}, std: (+/-) {2:.3f} [Bagging {0}]\n"
.format(clf.__class__.__name__,
bagging_scores.mean(), bagging_scores.std())
#Результат Mean of: 0.632, std: (+/-) 0.081 [RandomForestClassifier] Mean of: 0.639, std: (+/-) 0.069 [Bagging RandomForestClassifier] Mean of: 0.636, std: (+/-) 0.080 [ExtraTreesClassifier] Mean of: 0.654, std: (+/-) 0.073 [Bagging ExtraTreesClassifier] Mean of: 0.500, std: (+/-) 0.086 [KNeighborsClassifier] Mean of: 0.535, std: (+/-) 0.111 [Bagging KNeighborsClassifier] Mean of: 0.465, std: (+/-) 0.085 [SVC] Mean of: 0.535, std: (+/-) 0.083 [Bagging SVC] Mean of: 0.639, std: (+/-) 0.050 [RidgeClassifier] Mean of: 0.597, std: (+/-) 0.045 [Bagging RidgeClassifier]
Бустинг
ada_boost = AdaBoostClassifier()
grad_boost = GradientBoostingClassifier()
xgb_boost = XGBClassifier()
boost_array = [ada_boost, grad_boost, xgb_boost]
eclf = EnsembleVoteClassifier(clfs=[ada_boost, grad_boost, xgb_boost], voting='hard')
labels = ['Ada Boost', 'Grad Boost', 'XG Boost', 'Ensemble']
for clf, label in zip([ada_boost, grad_boost, xgb_boost, eclf], labels):
scores = cross_val_score(clf, X, y, cv=10, scoring='accuracy')
print("Mean: {0:.3f}, std: (+/-) {1:.3f} [{2}]".format(scores.mean(), scores.std(), label))
# Результат Mean: 0.641, std: (+/-) 0.082 [Ada Boost] Mean: 0.654, std: (+/-) 0.113 [Grad Boost] Mean: 0.663, std: (+/-) 0.101 [XG Boost] Mean: 0.667, std: (+/-) 0.105 [Ensemble]
