AdaBoost梯度提升算法

項目鏈接：https://github.com/Wchenguang/gglearn/blob/master/AdaBoost/李航機器學習講解/AdaBoost.ipynb

算法步驟與原理

1. 訓練 $m$ 個弱學習分類器，分類器有相同的接口
   $$G_m(x):\mathcal{X}\to \{x_1,x_2\dots \}$$

2. 假設數據有均勻的權值分布，即每個樣本在分類器中作用相同，$ n $個實例的權重為
   $$D_1=\left(w_{11},?,w_{1i},?,w_{1N}\right),w_{1i}=\frac{1}{N},i=1,2,?,N$$
   對于 $m$ 個分類器而言，有$ m \times n $個權重

3. 進入迭代循環，在每一次循環中進行如下操作

   3.1 計算 $m$ 個分類器在加權數據集上的分類錯誤率
   $$e_m=P\left(G_m\left(x_i\right)?=y_i\right)=\sum _{C_n\left(x_i\right)?=y_i}{w}_{mi}$$
   3.2 計算每個分類器的權重 $alph{a}_m$ ，該權重表明，每個單獨分類器在最終分類器中的重要程度
   α m = 1 2 log ? 1 ? e m e m \alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}} α m ? = 2 1 ? lo g e m ? 1 ? e m ? ?

   • 由上式可知，隨著分類器的誤差率的減小，其權重值越大

   3.3 更新數據集的權重分布

   $$\begin{array}{c}{D}_{m+1}=\left(w_{m+1,1},?,w_{m+1,i},?,w_{m+1,N}\right)\\ w_{m+1,i}=\frac{w_{mi}}{Z_m}\exp \left(?{\alpha }_m(y_i==G_m\left(x_i)\right)\right),i=1,2,?,N\end{array}$$
   $$Z_m=\sum _{i=1}^N{w}_{mi}\exp \left(?{\alpha }_m{y}_i{G}_m\left(x_i\right)\right)$$

   • 由上式可知
     $$w_{m+1,i}=\{\begin{array}{ll}\frac{w_{mi}}{Z_m}{\mathrm{e}}^{?{\alpha }_m},& G_m\left(x_i\right)=y_i\\ \frac{w_{mi}}{Z_m}{\mathrm{e}}^{{\alpha }_m},& G_m\left(x_i\right)?=y_i\end{array}$$
     預測錯誤的實例，權重提升。預測正確的實例，權重下降。

            
              import numpy as np

class testClf:
    def __init__(self, thresold):
        self.thresold = thresold
        self.x = None
        self.y = None
    def fit(self, x, y):
        self.x = x
        self.y = y
        return self
    def predict(self, x):
        y = x.copy()
        less_index = np.where(y[:, 0] < self.thresold)
        greater_index = np.where(y[:, 0] > self.thresold)
        y[less_index] = 1
        y[greater_index] = -1
        return y
    def fit_predict(self, x, y):
        return self.fit(x, y).predict(x)
        
'''
test_x = np.arange(10).reshape(-1, 1)
test_y = np.array([1,1,1,-1,-1,-1,1,1,1,-1]).reshape(-1, 1)
tc = testClf(2.5)
print(tc.fit_predict(test_x, test_y))
'''
import numpy as np
import matplotlib.pyplot as plt

class AdaBoost:
    def __init__(self, clf_list, iteration_times):
        '''
        分類器需要有相同的fit，predict接口用于訓練及預測
        '''
        self.clf_list = clf_list
        self.iteration_times = iteration_times
        self.x_weight_matrix = None
        self.clf_weight = None
    def _em(self, y_predict, y, x_weight):
        y_predict_flag = (y_predict != y).astype(int)
        return np.multiply(y_predict_flag, x_weight).sum()
    def _am(self, em):
        return np.log((1- em) / em) * 0.5
    def _update_x_weight(self, y_predict, y, am, x_weight):
        y_predict_flag = (y_predict == y).astype(int)
        y_predict_flag[np.where(y_predict_flag[:, 0] == 0)] = -1
        zm_array = np.multiply(np.exp(y_predict_flag * am * -1),
                                    x_weight)
        zm_array = zm_array / zm_array.sum()
        return zm_array
    def _fit_once(self, x, y, x_weight, clf_weight):
        for index in range(len(self.clf_list)):
            clf = self.clf_list[index]
            y_predict = clf.fit_predict(x, y)
            em = self._em(y_predict, y, x_weight)
            am = self._am(em)
            x_weight = self._update_x_weight(y_predict, y, am, x_weight)
            clf_weight[index] = am
            print('em', em, 'am', am)
            print('更新后權重')
            print(x_weight)
    def fit(self, x, y):
        m = len(self.clf_list)
        n = x.shape[0]
        if(0 == n or 0 == m):
            return
        self.x_weight = np.full((n, 1), 1/n)
        self.clf_weight = np.full((m, 1), 1/m)
        for i in range(self.iteration_times):
            self._fit_once(x, y, self.x_weight, self.clf_weight)
    def transform(self, x):
        if(self.clf_list == None or 0 == len(self.clf_list)):
            return None
        res = self.clf_weight[0] * self.clf_list[0].predict(x)
        for index in range(1, len(self.clf_list)):
            res += (self.clf_weight[index] * 
                            self.clf_list[index].predict(x))
        return res
test_x = np.arange(10).reshape(-1, 1)
test_y = np.array([1,1,1,-1,-1,-1,1,1,1,-1]).reshape(-1, 1)
adaboost = AdaBoost([testClf(2.5), testClf(8.5), testClf(5.5), ], 1)
adaboost.fit(test_x, test_y)
predict = adaboost.transform(test_x)
predict[np.where(predict[:, 0] < 0)] = -1
predict[np.where(predict[:, 0] >= 0)] = 1
print('predict')
print(predict)
print('truth')
print(test_y)

            
          

• 與書中P140-P41結果相符
• 書中分類器G3計算應為錯誤