Следующим мощным алгоритмом машинного обучения является AdaBoost (adaptive boosting), в основе которого лежит концепция бустинга, когда слабые базовые модели последовательно объединяются в одну сильную, исправляя ошибки предшественников.
В AdaBoost в качестве базовой модели используется пень решений (могут использоваться другие модели) — дерево с небольшой глубиной, которому присваивается вектор весов размера N, каждое значение которого соответствует определённому значению y_train и изначально равно 1 / N, где N — количество образцов в обучающей выборке. Каждый следующий пень обучается с учётом весов, рассчитанных на основе ошибок предыдущего прогноза. Также для каждого обученного пня отдельно рассчитывается вес, используемый для оценки важности итоговых прогнозов.
Ноутбук с данными алгоритмами можно загрузить на Kaggle (eng) и GitHub (rus)
Принцип работы адаптивного бустинга для классификации
SAMME (Stagewise Additive Modeling using а Multiclass Exponential loss function) — версия AdaBoost для многоклассовой классификации. Если же базовые модели оценивают вероятности классов, то такая версия называется SAMME.R, где R (Real) — вещественный и, в целом, обладает более высокой точностью.
Алгоритм строится следующим образом:
каждому значению y_train присваивается одинаковый вес;
пень глубиной 1 обучается на X_train и вычисляется доля неверных прогнозов, на основе которой рассчитывается взвешенная частота ошибки;
на основе взвешенной частоты ошибки рассчитывается вес пня;
для неверных прогнозов обновляются (увеличиваются) и нормализуются веса с учётом веса пня;
следующий пень обучается на X_train с учётом обновлённых весов: строится новая выборка того же размера, в которой чаще будут встречаться неправильно классифицированн��е образцы (те, у которых больше веса);
шаги 2-5 повторяются для каждого пня;
каждый обученный пень делает прогноз 1 образца X_test;
далее для каждого предсказанного класса суммируются веса пней;
класс с максимальной суммой весов и будет конечным прогнозом;
данная процедура повторяется для всех образцов в тестовом наборе данных.
Формулы для расчётов
Взвешенная частота ошибок j-го пня:
Вес пня:
Установить вес пня как (после чего нормализовать):
Итоговый прогноз:
j-й прогноз i-го образца: 
скорость обучения: 
число уникальных классов 
.
Принцип работы адаптивного бустинга для регрессии
В случае регрессии AdaBoost.R2 работает похожим образом за исключением некоторых особенностей: для оценки качества прогнозов пней используется абсолютная ошибка, а конечный прогноз выполняется с помощью взвешенной медианы, суть которой заключается в присвоении весов отсортированным элементам списка и выборе того, чья кумулятивная сумма больше половины от общей.
Алгоритм строится следующим образом:
каждому значению y_train присваивается одинаковый вес;
пень глубиной 3 обучается на X_train и вычисляется абсолютная ошибка для каждого спрогнозированного образца;
после рассчитываются скорректированные ошибки для образов и пня, а также коэффициент β на их основе;
на основе коэффициента β находится вес пня;
далее для всех образцов обновляются и нормализуются веса с учётом веса пня;
следующий пень обучается на X_train с учётом обновлённых весов: строится новая выборка того же размера, в которой чаще будут встречаться образцы с большими весами;
шаги 2-6 повторяются для каждого пня;
производится прогноз всех образцов X_test на каждом обученном пне;
производится поиск индекса медианного прогноза для каждого образца;
прогнозы из шага 8 на основе индексов медианного прогноза для каждого образца и будут конечными прогнозами.
Формулы для расчётов
Абсолютная ошибка для спрогнозированного образца:
Скорректированная ошибка для спрогнозированного образца:
Скорректированная ошибка для пня:
Коэффициент β:
Вес пня:
Обновить вес пня по следующем правилу (а затем нормализовать):
Итоговый прогноз:
j-й прогноз i-го образца:
Cкорость обучения: .
Импорт необходимых библиотек
import numpy as np import pandas as pd import matplotlib.pyplot as plt from sklearn.preprocessing import LabelEncoder from sklearn.model_selection import train_test_split from sklearn.metrics import accuracy_score, mean_absolute_percentage_error from sklearn.datasets import load_diabetes from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor from sklearn.ensemble import AdaBoostClassifier, AdaBoostRegressor from mlxtend.plotting import plot_decision_regions
Реализация на Python с нуля
class AdaBoost: def __init__(self, regression=False, n_estimators=50, learning_rate=1.0, random_state=0): self.regression = regression self.n_estimators = n_estimators self.learning_rate = learning_rate self.random_state = random_state self.stumps = [] self.weights = [] def _update_weights(self, args): if self.regression: weights, beta, loss_function = args weights *= beta ** (1 - loss_function) else: weights, wrong_predictions, stump_weight = args weights[wrong_predictions] *= np.exp(stump_weight) return weights @staticmethod def _normalize(weights: np.ndarray): return weights / sum(weights) def fit(self, X, y): n_samples = len(y) self.K = len(np.unique(y.values)) # num unique classes weights = np.ones(n_samples) / n_samples for _ in range(self.n_estimators): if self.regression: stump = DecisionTreeRegressor(max_depth=3, random_state=self.random_state) stump_predictions = stump.fit(X, y, sample_weight=weights).predict(X) abs_instance_errors = abs(stump_predictions - y) adjusted_instance_errors = abs_instance_errors / max(abs_instance_errors) adjusted_stump_error = sum(weights * adjusted_instance_errors) if adjusted_stump_error >= 0.5: self.stumps.pop(-1) break beta = adjusted_stump_error / (1 - adjusted_stump_error) stump_weight = self.learning_rate * np.log(1 / beta) args = [weights, beta, adjusted_instance_errors] else: stump = DecisionTreeClassifier(max_depth=1, random_state=self.random_state) stump_predictions = stump.fit(X, y, sample_weight=weights).predict(X) wrong_predictions = stump_predictions != y r = sum(weights[wrong_predictions]) # weighted_error_rate stump_weight = self.learning_rate * np.log((1 - r) / r) + np.log(self.K - 1) args = [weights, wrong_predictions, stump_weight] self.stumps.append(stump) self.weights.append(stump_weight) weights= self._update_weights(args) weights = self._normalize(weights) def _max_weighted_votes(self, samples): n_samples = len(samples) sample_indexes = np.array(range(n_samples)) prediction_weights = np.zeros((n_samples, self.K)) for i in range(self.n_estimators): stump_prediction = self.stumps[i].predict(samples) prediction_weights[sample_indexes, stump_prediction] += self.weights[i] return np.argmax(prediction_weights, axis=1) def _weighted_median_prediction(self, samples): n_samples = len(samples) sample_indexes = np.arange(n_samples) predictions = np.array([stump.predict(samples) for stump in self.stumps]).T sorted_pred_indexes = np.argsort(predictions, axis=1) # Find index of median prediction for each sample cumsum_weights = np.array(self.weights)[sorted_pred_indexes].cumsum(axis=1) is_over_median = cumsum_weights >= 0.5 * sum(self.weights) # True/False matrix median_indexes = is_over_median.argmax(axis=1) median_prediction_indexes = sorted_pred_indexes[sample_indexes, median_indexes] return predictions[sample_indexes, median_prediction_indexes] def predict(self, samples): if self.regression: return self._weighted_median_prediction(samples) else: return self._max_weighted_votes(samples)
Код для отрисовки графика
def decision_boundary_plot(X, y, X_train, y_train, clf, feature_indexes, title=None): feature1_name, feature2_name = X.columns[feature_indexes] X_feature_columns = X.values[:, feature_indexes] X_train_feature_columns = X_train.values[:, feature_indexes] clf.fit(X_train_feature_columns, y_train.values) plot_decision_regions(X=X_feature_columns, y=y.values, clf=clf) plt.xlabel(feature1_name) plt.ylabel(feature2_name) plt.title(title)
Загрузка датасетов
Для обучения моделей будет использован Glass Classification датасет, где необходимо верно определить тип стекла по его признакам. В случае регрессии используется Diabetes датасет из scikit-learn.
df_path = "/content/drive/MyDrive/glass.csv" glass_df = pd.read_csv(df_path) X1, y1 = glass_df.iloc[:, :-1], glass_df.iloc[:, -1] y1 = pd.Series(LabelEncoder().fit_transform(y1)) X1_train, X1_test, y1_train, y1_test = train_test_split(X1, y1, random_state=0) print(glass_df) RI Na Mg Al Si K Ca Ba Fe Type 0 1.52101 13.64 4.49 1.10 71.78 0.06 8.75 0.00 0.0 1 1 1.51761 13.89 3.60 1.36 72.73 0.48 7.83 0.00 0.0 1 2 1.51618 13.53 3.55 1.54 72.99 0.39 7.78 0.00 0.0 1 3 1.51766 13.21 3.69 1.29 72.61 0.57 8.22 0.00 0.0 1 4 1.51742 13.27 3.62 1.24 73.08 0.55 8.07 0.00 0.0 1 .. ... ... ... ... ... ... ... ... ... ... 209 1.51623 14.14 0.00 2.88 72.61 0.08 9.18 1.06 0.0 7 210 1.51685 14.92 0.00 1.99 73.06 0.00 8.40 1.59 0.0 7 211 1.52065 14.36 0.00 2.02 73.42 0.00 8.44 1.64 0.0 7 212 1.51651 14.38 0.00 1.94 73.61 0.00 8.48 1.57 0.0 7 213 1.51711 14.23 0.00 2.08 73.36 0.00 8.62 1.67 0.0 7
X2, y2 = load_diabetes(return_X_y=True, as_frame=True) X2_train, X2_test, y2_train, y2_test = train_test_split(X2, y2, random_state=0) print(X2, y2, sep='\n') age sex bmi bp s1 s2 s3 \ 0 0.038076 0.050680 0.061696 0.021872 -0.044223 -0.034821 -0.043401 1 -0.001882 -0.044642 -0.051474 -0.026328 -0.008449 -0.019163 0.074412 2 0.085299 0.050680 0.044451 -0.005670 -0.045599 -0.034194 -0.032356 3 -0.089063 -0.044642 -0.011595 -0.036656 0.012191 0.024991 -0.036038 4 0.005383 -0.044642 -0.036385 0.021872 0.003935 0.015596 0.008142 .. ... ... ... ... ... ... ... 437 0.041708 0.050680 0.019662 0.059744 -0.005697 -0.002566 -0.028674 438 -0.005515 0.050680 -0.015906 -0.067642 0.049341 0.079165 -0.028674 439 0.041708 0.050680 -0.015906 0.017293 -0.037344 -0.013840 -0.024993 440 -0.045472 -0.044642 0.039062 0.001215 0.016318 0.015283 -0.028674 441 -0.045472 -0.044642 -0.073030 -0.081413 0.083740 0.027809 0.173816 s4 s5 s6 0 -0.002592 0.019907 -0.017646 1 -0.039493 -0.068332 -0.092204 2 -0.002592 0.002861 -0.025930 3 0.034309 0.022688 -0.009362 4 -0.002592 -0.031988 -0.046641 .. ... ... ... 437 -0.002592 0.031193 0.007207 438 0.034309 -0.018114 0.044485 439 -0.011080 -0.046883 0.015491 440 0.026560 0.044529 -0.025930 441 -0.039493 -0.004222 0.003064 [442 rows x 10 columns] 0 151.0 1 75.0 2 141.0 3 206.0 4 135.0 ... 437 178.0 438 104.0 439 132.0 440 220.0 441 57.0 Name: target, Length: 442, dtype: float64
Обучение моделей и оценка полученных результатов
В случае классификации низкая точность обусловлена тем, что AdaBoost плохо работает с несбалансированными данными, стараясь минимизировать ошибку на объектах из меньшего класса, что часто приводит к переобучению на этих объектах и к снижению точности модели в целом.
В случае регрессии ошибка немного меньше, чем в алгоритме случайного леса, что может быть связано с тем, что в используемых данных наблюдается высокая степень корреляции между некоторыми признаками, с которой AdaBoost справляется чуть лучше. Следует отметить, что в большинстве случаев, при хорошей подготовке данных AdaBoost будет справляться лучше своих предшественников как в задачах регрессии, так и классификации.
Данный пример хорошо показывает, что более сильные алгоритмы способны далеко не всегда показывать лучшие результаты "из коробки".
Полученные результаты приведены ниже.
Классификация
adaboost_clf = AdaBoost(random_state=0) adaboost_clf.fit(X1_train, y1_train) adaboost_clf_pred_res = adaboost_clf.predict(X1_test) adaboost_clf_accuracy = accuracy_score(y1_test, adaboost_clf_pred_res) print(f'adaboost_clf_accuracy: {adaboost_clf_accuracy}') print(adaboost_clf_pred_res, '', sep='\n') sk_adaboost_clf = AdaBoostClassifier(random_state=0, algorithm='SAMME') sk_adaboost_clf.fit(X1_train, y1_train) sk_adaboost_clf_pred_res = sk_adaboost_clf.predict(X1_test) sk_adaboost_clf_accuracy = accuracy_score(y1_test, sk_adaboost_clf_pred_res) print(f'sk_adaboost_clf_accuracy: {sk_adaboost_clf_accuracy}') print(sk_adaboost_clf_pred_res) feature_indexes = [1, 3] title1 = 'AdaBoostClassifier surface' decision_boundary_plot(X1, y1, X1_train, y1_train, sk_adaboost_clf, feature_indexes, title1) adaboost_clf_accuracy: 0.46296296296296297 [5 0 0 3 1 0 0 0 0 0 1 0 1 1 0 5 0 0 0 0 1 0 5 5 1 0 5 0 0 0 0 4 0 1 0 0 0 0 0 5 1 4 0 0 0 0 0 0 0 0 0 1 5 0] sk_adaboost_clf_accuracy: 0.46296296296296297 [5 0 0 3 1 0 0 0 0 0 1 0 1 1 0 5 0 0 0 0 1 0 5 5 1 0 5 0 0 0 0 4 0 1 0 0 0 0 0 5 1 4 0 0 0 0 0 0 0 0 0 1 5 0]
Регрессия
adaboost_reg = AdaBoost(regression=True, random_state=0) adaboost_reg.fit(X2_train, y2_train) adaboost_reg_pred_res = adaboost_reg.predict(X2_test) mape = mean_absolute_percentage_error(y2_test, adaboost_reg_pred_res) print(f'adaboost_mape {mape}') print(adaboost_reg_pred_res, '', sep='\n') sk_adaboost_reg = AdaBoostRegressor(random_state=0, loss='linear') sk_adaboost_reg.fit(X2_train, y2_train) sk_adaboost_reg_pred_res = sk_adaboost_reg.predict(X2_test) sk_mape = mean_absolute_percentage_error(y2_test, sk_adaboost_reg_pred_res) print(f'sk_adaboost_mape {sk_mape}') print(sk_adaboost_reg_pred_res) adaboost_mape 0.408360140181123 [239.42353344 230.0610339 167.83786364 109.90928178 184.64646203 239.42353344 101.90476455 212.98494882 140.80423233 234.56903421 149.26846999 194.19445742 117.43386255 108.94790608 242.1290679 113.80597432 154.09826483 98.94335581 115.9061429 215.42377993 174.95712248 153.4188609 156.40651525 101.90476455 212.98494882 167.10327877 124.65270476 101.84145017 192.87682861 155.83747832 199.62919177 101.90476455 117.43386255 149.26846999 149.26846999 154.09826483 153.4188609 154.49247636 101.3830624 209.29518647 109.90928178 161.72545559 157.26677336 164.34687775 194.42677031 101.84145017 121.14501461 138.47917841 118.20881026 221.76239616 142.75885825 106.54153274 115.59244578 156.73838581 228.18233286 159.23529268 188.06281057 115.59244578 136.36747076 179.90046612 235.54909423 136.36747076 146.94594595 117.30376558 235.54909423 156.55259315 109.14947399 222.75 216.80587827 117.30376558 101.3830624 149.26846999 124.65270476 138.47917841 121.14501461 164.34687775 129.01990679 215.42377993 237.65169877 173.94597477 140.80423233 210.13587296 101.3830624 222.95089406 126.1623703 102.63869452 155.06486638 198.82203583 109.90928178 153.9068871 113.80597432 115.9061429 101.85242259 155.83747832 113.80597432 102.63869452 216.80587827 211.45665899 109.90928178 160.62212018 153.4188609 109.65526344 163.575 106.94547559 230.1457969 140.80423233 215.42377993 234.56903421 109.65526344 115.9061429 216.80587827] sk_adaboost_mape 0.396029115194888 [258.32911392 227.87142857 176.77325581 112.12676056 189.65263158 240.23529412 97.56934307 215.65217391 131.52777778 228.77894737 148.55223881 161.68085106 115.83916084 106.13636364 259.90697674 117.94565217 147.52941176 95.01538462 117.94565217 229.88429752 175.55696203 133.24277457 174.94444444 113. 213.70093458 169.35955056 133.24277457 95.67142857 195.7173913 156.20253165 206.96875 101.32330827 117.94565217 148.55223881 148.55223881 155.86893204 149.32352941 149.32352941 96.05932203 200.54545455 115.83916084 171. 143.02857143 169.8 196.54054054 99.05617978 123.4375 112.12676056 117.17213115 227.87142857 148.09195402 99.05617978 121.2826087 167.92592593 227.87142857 150.0106383 169.35955056 104.71794872 133.24277457 200.54545455 231.56934307 121.2826087 139.78205128 113.08602151 234.00735294 131.52777778 106.92380952 218.64705882 215.3 113.69172932 97.56934307 147.29166667 126.87591241 113.69172932 118.26470588 168.76 123.16037736 200.89473684 234.00735294 189.65263158 133.24277457 226.15686275 95.03703704 233.25 134.91428571 101.32330827 133.24277457 200.54545455 113.08602151 149.32352941 113.08602151 117.94565217 95.03703704 154.67532468 113.69172932 97.56934307 227.43037975 221.58433735 126.87591241 155.86893204 148.09195402 102.25714286 169.52147239 104.71794872 227.87142857 142.38461538 218.64705882 247.9122807 112.12676056 117.94565217 226.15686275]
Преимущества и недостатки AdaBoost
Преимущества:
высокая точность при правильной подготовке данных;
работа со сложными, нелинейными зависимостями в данных;
высокая обобщающая способность.
Недостатки:
низкая скорость обучения при работе с большими датасетами;
склонен к переобучени�� при большом числе базовых моделей;
нестабильность при работе с несбалансированными данными, а также чувствительность к шуму и выбросам.
Другие модификации адаптивного бустинга
Поскольку при работе с зашумленными данными обобщающая способность AdaBoost может заметно снизиться, были разработаны другие, более стабильные модификации. Среди наиболее интересных можно выделить следующие:
L2-Boost — модификация, которая использует L2-регуляризацию для функции потерь для штрафов менее важных признаков, что делает его более подходящим вариантом в задачах регрессии;
LogitBoost — улучшение, которое применяется в задачах классификации на основе логистической функции потерь, что ускоряет обучение и в ряде случаев делает алгоритм более устойчивым;
BrownBoost — более продвинутая модификация, в основе которой лежит использование лимита на обучение по данным с неверными прогнозами, то есть модель старается штрафовать сильнее трудно классифицируемые объекты.
Дополнительные источники
Статьи:
«Multi-class AdaBoost», Ji Zhu, Hui Zou, Saharon Rosset and Trevor Hastie;
«Boosting for Regression Transfer», David Pardoe and Peter Stone;
«L2 Boosting for Economic Applications», Ye Luo and Martin Spindler;
«Robust LogitBoost and Adaptive Base Class (ABC) LogitBoost», Ping Li;
«An adaptive version of the boost by majority algorithm», Yoav Freund.
Документация:
🡄 Бэггинг и случайный лес | Градиентный бустинг и его модификации 🡆
