W wielu przypadakch skuteczność rozpatrywanych klasyfikatorów nie jest dla nas satsfakcjonująca lub też okazuje się, że są one bardzo podatne na drobne zmiany. Szczególnie dotyczy to drzew. Jedną z metodą, która pozwala omijać te mankamenty jest tworzenie zespołów klasyfikatorów. Ogólna idea jest związana z prostym faktem: jeśli będziemy dysponowali zestawem M słabych klasyfikatorów (np. o ułamku błędnych klasyfikacji err=0.45), to dla dużej wartości M decyzja podjęta przez większość będzie prawie na pewno prawdziwa. Oczywiście, tego typu twierdzenie dotyczy jedynie zespołu nieskorelowanych klasyfikatorów. Na dziesiejszych zajęciach poznamy trzy najpoularniejsze metody: bagging, boosting oraz lasy losowe.
Bagging
Metoda agregacji bootstrapowej, czyli bagging, została szerzej omówiona na wykładzie 6. W tym miejscu przypomnimy jedynie sam algorytm:
- dla każdego \(m=1,...M\) wylosuj pseudopróbę \(P_m\) z oryginalnej \(N\)-elementowej próby uczącej,
- na każdej pseudopróbie \(P_m\) naucz klasyfikator (np. drzewo) \(T_m\).
W efekcie posiadamy rodzinę \(M\) klasyfikatorów, każdy wyuczone na oddzielnej \(N\)-elementowej próbie powstałej poprzez metodę repróbkowania (bootstrap). Aby zaklasyfikować nową obserwację sprawdzamy jaka jest odpowiedź każdego z klasyfikatorów i wybieramy taką klasę, która została przypisana przez większość (tu mamy dwie możliwości: hard-voting, czyli faktycznie wybór większości oraz soft-voting, w którym liczymy prawdopodobieństwa dla poszczególnych drzew, a potem tworzymy średnią po tych wartościach i wg niej wybiramy klasę). To jest element agregacji wyników i stąd też nazwa: Boostrap AGGregation, w skrócie bagging
Tym razem skorzystamy z okręslonego zbioru danych, pochodzącego z książki Hastie, Tibshirani, Friedman “The Elements of Statistical Learning”, wzór (10.2) - wektor obserwacji ma 10 składowch - każda a nich to niezależnie losowany 1D Gauss, a klasa jest wyznaczana jako “1” jeśli suma kwadratów składowych przekracza wartość 9.34 (mediana zmiennej losowej pochodzącej z rozkładu \(\xi^2\) o 10 stopniach swobody) i “-1” w przeciwnym razie.
from sklearn import datasets
X, y = datasets.make_hastie_10_2(n_samples=1_000, random_state=1)Zobaczmy jak na takim zbiorze radzi sobie drzewo, a dokładniej jego pień oraz pełne:
from sklearn import model_selection
from sklearn import tree
import numpy as np
X_train, X_test, y_train, y_test = model_selection.train_test_split(X, y)
clf = tree.DecisionTreeClassifier(max_leaf_nodes=2)
clf.fit(X_train, y_train);
stump_train = clf.score(X_train, y_train)
stump_test = clf.score(X_test, y_test)
print("Pień (2 węzły) PU:", np.round(stump_train,3))## Pień (2 węzły) PU: 0.563print("Pień PT:", np.round(stump_test, 3))## Pień PT: 0.512clf_full = tree.DecisionTreeClassifier()
clf_full.fit(X_train, y_train);
full_test = clf_full.score(X_test, y_test)
print("Pełne drzewo:", np.round(full_test,3))## Pełne drzewo: 0.716print("Liczba liści pełnego drzewa:", clf_full.tree_.n_leaves)## Liczba liści pełnego drzewa: 107Jak widac pełne drzewo jest dość pokaźne; możemy więc spróbować wykonać drzewo optymalne:
from sklearn.model_selection import GridSearchCV
import matplotlib.pyplot as plt
path = clf_full.cost_complexity_pruning_path(X, y)
param_grid = {'ccp_alpha': path['ccp_alphas']}
clf_grid = GridSearchCV(clf_full, param_grid)
clf_grid.fit(X, y);
plt.plot(param_grid["ccp_alpha"], clf_grid.cv_results_["mean_test_score"], marker="o", drawstyle="steps-post", c = "#0000ff55")
plt.errorbar(param_grid["ccp_alpha"], clf_grid.cv_results_["mean_test_score"], clf_grid.cv_results_["std_test_score"], fmt="o", capsize=4, c = "#0000ff");
plt.xlabel(r"$\alpha$ - współczynnik złożoności")
plt.ylabel("dokładnośc klasyfikatora");
plt.show()
Dla prostoty uznajmy, że drzewo optymalne to takie, dla którego \(\alpha\) wynosi około 0.012. Wtedy
clf_opt = tree.DecisionTreeClassifier(ccp_alpha = 0.012)
clf_opt.fit(X_train, y_train);
opt_test = clf_opt.score(X_test, y_test)
print("Drzewo optymalne:", opt_test, "liczba liści: ", clf_opt.tree_.n_leaves)## Drzewo optymalne: 0.712 liczba liści: 11W tym momencie zaimplementujemy wreszcie same funkcje do metody
bagging: create_bag_class() oraz
bagging.own.pred()create_bag_class(). Pierwsza z nich służy do trenowania klasyfikatora, druga - do dokonywania przewidywania. Wreszcie trzecia funkcjatest_bag_class()`
wykonuje najpierw jedną a potem drugą i wyznacza dokładność
import numpy as np
import pandas as pd
from sklearn.utils import resample
from sklearn import metrics
def create_bag_class(N, X, y):
clf_xx = []
for i in range(N):
clf_xx.append(tree.DecisionTreeClassifier(max_leaf_nodes=2))
Xs, ys = resample(X, y)
clf_xx[i].fit(Xs, ys)
return clf_xx
def predict_bag_class(clf, X, N):
Z = np.array([clf[i].predict_proba(X)[:,0] for i in range(N)])
return np.apply_along_axis(lambda x: -1 if np.mean(x) >= 0.5 else 1, 0, Z)
def test_bag_class(X_tr, y_tr, X_te, y_te, N):
clf_xx = create_bag_class(N, X_tr, y_tr)
return metrics.accuracy_score(y_te, predict_bag_class(clf_xx, X_te, N))Przetestujmy teraz działanie zarówno dla zbioru treningowego jaki i testowego
n_clf = [1, 2, 5, 10, 20, 30, 50, 60, 80, 100]
out_train = np.array([[test_bag_class(X_train, y_train, X_train, y_train, n) for i in range(5)] for n in n_clf])
out_test = np.array([[test_bag_class(X_train, y_train, X_test, y_test, n) for i in range(5)] for n in n_clf])
out_train_f = np.apply_along_axis(lambda x: [np.mean(x), np.std(x)], 1, out_train)
out_test_f = np.apply_along_axis(lambda x: [np.mean(x), np.std(x)], 1, out_test)i porównajmy z wartościami dla pojednyczych drzew:
plt.errorbar(n_clf, out_train_f[:,0], out_train_f[:,1], fmt="o", capsize=4, label = "trening");
plt.errorbar(n_clf, out_test_f[:,0], out_test_f[:,1], fmt="o", capsize=4, label = "test");
plt.axhline(stump_train, ls = "--", label = "pień trening")
plt.axhline(stump_test, ls = "--", color = "orange", label = "pień test")
plt.axhline(full_test, ls = "--", color = "red", label = "drzewo pełne")
plt.axhline(opt_test, ls = "--", color = "green", label = "drzewo optymalne")
plt.xlabel("liczba klasyfikatorów")
plt.ylabel("dokładność klasyfikatora")
plt.legend()
plt.show()
Zobserowaliśmy podstawowe cechę zespołów klasyfikatorów: (1) większa liczba klasyfikatorów działa lepiej niż pojednyczy, (2) wraz ze wzrostem liczby klasyfikatorów wzrasta tez ich dokładnośc (choć szybko hrzywa się wypłaszcza). Sprawdźmy co się będzie działo, gdy jako pojedynczy klasyfiktaor użyjemy drzewa optymalnego - widac, że efekt jest dużo lepszy.
Boosting
Metoda boosting, choć w swojej konstrukcji podobna do baggingu, jest oparta na trochę innym pomyśle: kolejne klasyfikatory są uczone na zbiorze danych, w których prawdopodobieństwo wylosowania obserwacji jest zwiększane, jeśli w poprzednim kroku została ona źle zaklasyfikowana. Początkowo wszystkie wagi \(w_i\) \(i=1,...,N\) są ustawione jako \(1/N\) (\(N\) - liczba elementów PU). W każdym kroku \(m=1,..,M\) na danych trenowany jest przy użyciu wag \(w\) klasyfikator \(f_m\), a następnie zaś jest obliczana dla niego ważona ilość błędów
\(\mathrm{err}_m = \sum\limits_{i=1}^{i=N}w_i \mathrm{I}[y_i \ne f_m(\mathbf{x}_i)])\),
które są wykorzystywane do zmiany wag
\(w_i = w_i \exp(\gamma_m \mathbf{I}[y_i \ne f_m(\mathbf{x}_i)])\),
gdzie \(\gamma_m = \frac{1-\mathrm{err}_m}{\mathrm{err}_m}\); wagi są w międzyczasie normowane do jedności. Na końcu co do każdej obserwacji podejmowana jest decyzja zgodnie z regułą
\(\mathrm{sgn}\left[ \sum\limits_{m=1}^M \gamma_m f_m(\mathbf{x})\right]\).
Zobaczy teraz jak radzi sobie algorytm AdaBoost:
from sklearn.ensemble import AdaBoostClassifier
def get_clf_res(clf, X_train, y_train, X_test, y_test):
clf.fit(X_train, y_train)
return clf.score(X_test, y_test)
res_agg_boost = pd.DataFrame(columns = ["n", "train", "test"])
n_clf = [2, 5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
for n in n_clf:
clf_boost = AdaBoostClassifier(n_estimators = n, estimator = tree.DecisionTreeClassifier(max_leaf_nodes=2))
res_train_boost = get_clf_res(clf_boost, X_train, y_train, X_train, y_train)
res_test_boost = get_clf_res(clf_boost, X_train, y_train, X_test, y_test)
res_agg_boost.loc[len(res_agg_boost)] = {'n': n, 'train': res_train_boost, 'test': res_test_boost}
plt.plot(n_clf, res_agg_boost.train, "-o", label = "trening")
plt.plot(n_clf, res_agg_boost.test, "-o", label = "test")
plt.ylim(0, 1.05);
plt.axhline(stump_train, ls = "--", label = "pień trening")
plt.axhline(stump_test, ls = "--", color = "orange", label = "pień test")
plt.axhline(full_test, ls = "--", color = "red", label = "drzewo pełne")
plt.axhline(opt_test, ls = "--", color = "green", label = "drzewo optymalne")
plt.xlabel("liczba klasyfikatorów")
plt.ylabel("dokładność klasyfikatora")
plt.legend()
plt.show()
i porówanajmy go z implementacją poprzedniego na poziomie kroswalidacji
from sklearn.ensemble import BaggingClassifier
grid_params = {"n_estimators": [2, 5, 10, 20, 30, 50, 80, 100, 120, 150, 180, 200, 220, 250]}
clf_boost = AdaBoostClassifier(tree.DecisionTreeClassifier(max_leaf_nodes=2))
clf_bag = BaggingClassifier(tree.DecisionTreeClassifier(max_leaf_nodes=2))
clf_boost_grid = GridSearchCV(clf_boost, grid_params)
clf_bag_grid = GridSearchCV(clf_bag, grid_params)
clf_boost_grid.fit(X, y);
clf_bag_grid.fit(X, y);
plt.errorbar(grid_params["n_estimators"], clf_bag_grid.cv_results_["mean_test_score"], clf_bag_grid.cv_results_["std_test_score"], fmt="o", capsize=4, label = "bagging CV");
plt.errorbar(grid_params["n_estimators"], clf_boost_grid.cv_results_["mean_test_score"], clf_boost_grid.cv_results_["std_test_score"], fmt="o", capsize=4, label = "boosting CV");
plt.ylim(0, 1.05);
plt.axhline(stump_train, ls = "--", label = "pień trening")
plt.axhline(stump_test, ls = "--", color = "orange", label = "pień test")
plt.axhline(full_test, ls = "--", color = "red", label = "drzewo pełne")
plt.axhline(opt_test, ls = "--", color = "green", label = "drzewo optymalne")
plt.xlabel("liczba klasyfikatorów")
plt.ylabel("dokładność klasyfikatora")
plt.legend()
plt.show()
Lasy losowe
Ostatnim opisywanym algorytmem są lasy losowe. Tu także za każdym razem dokonujemy bootstrapingu, losując elemnty z PU do pseudopróby. Różnica polega na tym, że w każdym węźle drzewa wybiermay jedynie \(r\) spośród \(p\) składowych, na których dokonywany jest podział, przy czym sugeruje się \(r=\sqrt{p}\). Na koniec znów dokonujemy ostatecznej klasyfikacji zgodnie z większością głosów.
Choć suheruje się tworzyć pełne drzewo, my ograniczymy się trochę ze względu na jego wielkość.
from sklearn.ensemble import RandomForestClassifier
clf_rf = RandomForestClassifier(max_depth=6)
clf_rf_grid = GridSearchCV(clf_rf, grid_params)
clf_rf_grid.fit(X, y);
plt.errorbar(grid_params["n_estimators"], clf_bag_grid.cv_results_["mean_test_score"], clf_bag_grid.cv_results_["std_test_score"], fmt="o", capsize=4, label = "bagging CV");
plt.errorbar(grid_params["n_estimators"], clf_boost_grid.cv_results_["mean_test_score"], clf_boost_grid.cv_results_["std_test_score"], fmt="o", capsize=4, label = "boosting CV");
plt.errorbar(grid_params["n_estimators"], clf_rf_grid.cv_results_["mean_test_score"], clf_rf_grid.cv_results_["std_test_score"], fmt="o", capsize=4, label = "las CV");
plt.axhline(stump_train, ls = "--", label = "pień trening")
plt.axhline(stump_test, ls = "--", color = "orange", label = "pień test")
plt.axhline(full_test, ls = "--", color = "red", label = "drzewo pełne")
plt.axhline(opt_test, ls = "--", color = "green", label = "drzewo optymalne")
plt.xlabel("liczba klasyfikatorów")
plt.ylabel("dokładność klasyfikatora")
plt.legend()
plt.show()