AdaBoost算法詳解以及代碼實現

原文連結：https://www.datalearner.com/blog/1051560309522503

AdaBoost，全稱是「Adaptive Boosting」，由Freund和Schapire在1995年首次提出，並在1996發布了一篇新的論文證明其在實際數據集中的效果。這篇博客主要解釋AdaBoost的算法詳情以及實現。它可以理解為是首個「boosting」方式的集成算法。是一個關注二分類的集成算法。

一、算法的總體情況

AdaBoost的目標是建立如下的最終的分類器：

其中，假設我們輸入的訓練數據總共有nn個，用(x_1,y_y),\cdots,(x_n,y_n)(x1,yy),⋯,(xn,yn)表示，其中xx是一個多為向量，而其對應的y=\{-1,1\}y={−1,1}。

1.1、sign函數

這裡的sign函數是符號函數。判斷實數的正負號。即如果輸入是正數，那麼輸出為1；輸入為負數，那麼輸出為-1；如果輸入是0的話，那麼輸出為0。因此，AdaBoost的目標是判斷\{-1,1\}

{−1,1}的二分類判別算法。其函數圖像如下所示

1.2、弱分類器f(x)

模型中的f_m(x)fm(x)是弱分類器。這裡假設一個AdaBoost是由MM個弱分類器家全球和得到。每一個弱分類器f_m(x)fm(x)都給出一個預測結果，然後根據其對應的權重\theta_mθm加權求和。因此，我們可以看到，AdaBoost的目標其實就是求出每個弱分類器的模型參數，以及其對應的權重。

二、AdaBoost的求解

前面可以看到AdaBoost的模型本身非常簡單。那麼，如何求解這個模型中弱分類器的權重及其參數呢？其步驟如下：

首先，根據前面所述，有nn個數據，我們初始化每個數據的權重都是一樣的：

接下來，我們對每一個弱分類器(1,\cdots,M)(1,⋯,M)都進行如下操作：

1) 訓練一個弱分類器，使得其分類誤差最小，此時計算該分類器的誤差計算如下公式：

這個公式的含義就是模型的誤差等於每一個錯分的樣本權重之和。

當該模型是第一個弱分類器（即第一次迭代的時候），該公式中的含義就是計算當前弱分類器分錯的樣本個數，除以總的樣本數量，得到該弱分類器的誤差（因為，此時每個樣本的誤差都是1/n）。同時注意，在後面的迭代中，每個錯分的樣本的權重是不同的，這裡的mm表示第mm次迭代時候，該樣本的權重。

2）根據當前弱分類器的誤差，計算該分類器的權重：

\theta_m = \frac{1}{2} \ln(\frac{1-\epsilon_m}{\epsilon_m})

該公式的含義就是，當該弱分類器的準確率（1-前面的誤差）大於0.5，那麼這個權重就是正值（因為此時\epsilon_m< 0.5ϵm<0.5，那麼對數內部就是大於1，那麼結果就是正數了）。否則該權重為負值。也就是說，只要這個分類器的準確率結果不是0.5（這個時候就相當於隨機猜測了），它總會給最終的分類器提供一些信息。

3）最後，我們根據模型權重更新數據的權重：

這裡的Z_mZm是正規化係數，確保所有的數據權重總和為1。

解釋一下這個公式的含義，指數內部-\theta_my_if_m(x_i)−θmyifm(xi)這個乘積的含義是如果弱分類器mm的分類結果和真實的結果一致，那麼結果是-\theta_m−θm，是一個負值，那麼\exp[-\theta_my_if_m(x_i)]exp[−θmyifm(xi)]結果小於1。也就是說該數據集的樣本權重降低。否則該數據樣本的權重增高。因此，通過這種計算就可以讓那些容易分錯的樣本的權重升高，容易分對的樣本權重降低。繼續迭代就會導致對難分的樣本能分對的模型的權重上漲。最終，達到一個強分類器的目的。

三、AdaBoost的Python實現

根據上述原理，AdaBoost的實現就很容易了。這裡的主要目標是訓練好每個弱分類器的同時，計算好分類器的權重。

x_train, y_train = ...y_train = ...M = 100models = getModel(100)n_train = x_train.shape[0]w = np.ones(n_train) / n_traintheta = np.zeros(n_train)for m in range(M):        models[m].fit(x_train,y_train)        pred_train = models[m].predict(x_train)    miss = [int(x) for x in (pred_train != y_train)]    error = np.dot(w, miss)        theta[m] = 0.5 * np.log((1-error)/error)        for i in n_train:        w[i] = w[i]*np.exp(-theta[m]*y_train[i]*pred_train[i])        for i in n_train:        w[i] /= np.sum(w[i])predict = np.dot(theta, [model[m].predict(x_test) for m in range(M)])
參考文獻：
https://towardsdatascience.com/boosting-algorithm-adaboost-b6737a9ee60c
https://towardsdatascience.com/boosting-and-adaboost-clearly-explained-856e21152d3e
https://github.com/jaimeps/adaboost-implementation/blob/master/adaboost.py