【機器學習基礎】數學推導+純Python實作機器學習算法16：Adaboost

Python機器學習算法實作

Author：louwill

Machine Learning Lab

     上一講我們講到內建學習的核心算法GBDT，但早在GBDT之前，boosting理念的核心算法是一種被稱作為Adaboost的算法。Adaboost全稱為Adaptive boosting，可以翻譯為自适應提升算法。Adaboost是一種通過改變訓練樣本權重來學習多個弱分類器并進行線性組合的過程。本講我們一起來學習一下Adaboost算法原理并嘗試給出其基本實作方式。

Adaboost算法原理

     boosting方法的核心理念在于博采衆長，正所謂"三個臭皮匠，頂個諸葛亮"，這也使得boosting方法要好于大多數單模型算法。一般來說，boosting方法都要解答兩個關鍵問題：一是在訓練過程中如何改變訓練樣本的權重或者是機率分布，二是如何将多個弱分類器組合成一個強分類器。針對這兩個問題，Adaboost是做法非常樸素，第一個就是提高前一輪被弱分類器分類錯誤的樣本的權重、而降低分類正确的樣本權重；第二則是對多個弱分類器進行線性組合，提高分類效果好的弱分類器權重，減小分類誤差率大的弱分類器權重。

每個樣本由輸入執行個體和對應标簽組成，執行個體

，标簽

。我們來看Adaboost的具體算法流程，具體給出算法的每一步，這樣在後面做算法實作的時候可以一一對應起來。

(1) 初始化訓練樣本的權值分布，假設開始訓練時每個樣本都有相同大小的權值，即樣本權值是均勻分布的

，

，

(2) 對于

• 使用初始化均勻權值分布

  的資料集進行訓練，可得到弱分類器

• 計算弱分類器

  在訓練資料上的分類誤差率

• 計算弱分類器的權重

• 更新訓練樣本的權值分布其中

  為規範化因子：

(3) 建構多個弱分類器的線性組合

     最終Adaboost的分類器可表示為：

     從上述步驟可以看到，Adaboost的算法思想非常簡單和樸素，實際用起來也會非常高效。Adaboost是弱分類器通常使用決策樹樁(decision stump)，非常簡單且靈活。上述Adaboost算法流程可能看起來不夠顯式，甚至連損失函數和優化算法都找不到，針對于此，是以Adaboost又有了另外一種解釋。即Adaboost算法是以加法模型為模型，以指數函數為損失函數，訓練算法為前向分布算法的一種二分類算法。這裡不做過多展開，具體可參考統計學習方法一書。

Adaboost實作

     下面我們根據上述算法流程來編寫代碼進行實作。

     先定義一個決策樹樁，本質上就是一個帶有門檻值劃分的決策樹結點。

class DecisionStump():
    def __init__(self):
        # 基于劃分門檻值決定樣本分類為1還是-1
        self.polarity = 1
        # 特征索引
        self.feature_index = None
        # 特征劃分門檻值
        self.threshold = None
        # 訓示分類準确率的值
        self.alpha = None      

     然後直接定義一個Adaboost算法類，将上述算法流程在類中實作。

class Adaboost():
    # 弱分類器個數
    def __init__(self, n_estimators=5):
        self.n_estimators = n_estimators
    # Adaboost拟合算法
    def fit(self, X, y):
        n_samples, n_features = X.shape


        # (1) 初始化權重分布為均勻分布 1/N
        w = np.full(n_samples, (1/n_samples))
        
        self.estimators = []
        # (2) for m in (1,2,...,M)
        for _ in range(self.n_estimators):
            # (2.a) 訓練一個弱分類器：決策樹樁
            clf = DecisionStump()
            # 設定一個最小化誤差
            min_error = float('inf')
            # 周遊資料集特征，根據最小分類誤差率選擇最優劃分特征
            for feature_i in range(n_features):
                feature_values = np.expand_dims(X[:, feature_i], axis=1)
                unique_values = np.unique(feature_values)
                # 嘗試将每一個特征值作為分類門檻值
                for threshold in unique_values:
                    p = 1
                    # 初始化所有預測值為1
                    prediction = np.ones(np.shape(y))
                    # 小于分類門檻值的預測值為-1
                    prediction[X[:, feature_i] < threshold] = -1
                    # 2.b 計算誤差率
                    error = sum(w[y != prediction])
                    
                    # 如果分類誤差大于0.5，則進行正負預測翻轉
                    # E.g error = 0.8 => (1 - error) = 0.2
                    if error > 0.5:
                        error = 1 - error
                        p = -1


                    # 一旦獲得最小誤差則儲存相關參數配置
                    if error < min_error:
                        clf.polarity = p
                        clf.threshold = threshold
                        clf.feature_index = feature_i
                        min_error = error
                        
            # 2.c 計算基分類器的權重
            clf.alpha = 0.5 * math.log((1.0 - min_error) / (min_error + 1e-10))
            # 初始化所有預測值為1
            predictions = np.ones(np.shape(y))
            # 擷取所有小于門檻值的負類索引
            negative_idx = (clf.polarity * X[:, clf.feature_index] < clf.polarity * clf.threshold)
            # 将負類設為 '-1'
            predictions[negative_idx] = -1
            # 2.d 更新樣本權重
            w *= np.exp(-clf.alpha * y * predictions)
            w /= np.sum(w)


            # 儲存該弱分類器
            self.estimators.append(clf)
    
    # 定義預測函數
    def predict(self, X):
        n_samples = np.shape(X)[0]
        y_pred = np.zeros((n_samples, 1))
        # 計算每個弱分類器的預測值
        for clf in self.estimators:
            # 初始化所有預測值為1
            predictions = np.ones(np.shape(y_pred))
            # 擷取所有小于門檻值的負類索引
            negative_idx = (clf.polarity * X[:, clf.feature_index] < clf.polarity * clf.threshold)
            # 将負類設為 '-1'
            predictions[negative_idx] = -1
            # 2.e 對每個弱分類器的預測結果進行權重
            y_pred += clf.alpha * predictions


        # 傳回最終預測結果
        y_pred = np.sign(y_pred).flatten()
        return y_pred      

     這樣，一個完整Adaboost算法就搞定了。我們使用sklearn預設資料集來看一下算法效果。

from sklearn import datasetsfrom sklearn.metrics import accuracy_scorefrom sklearn.model_selection import train_test_split
data = datasets.load_digits()X = data.datay = data.target
digit1 = 1digit2 = 8idx = np.append(np.where(y==digit1)[0], np.where(y==digit2)[0])y = data.target[idx]# Change labels to {-1, 1}y[y == digit1] = -1y[y == digit2] = 1X = data.data[idx]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.7)
# 使用5個弱分類器clf = Adaboost(n_clf=5)clf.fit(X_train, y_train)y_pred = clf.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)print ("Accuracy:", accuracy)      

     驗證集分類精度接近達到0.94，可見我們編寫的Adaboost算法還比較成功。

Accuracy: 0.9397590361445783      

     sklearn也提供了Adaboost對應的api：

from sklearn.ensemble import AdaBoostClassifierclf_ = AdaBoostClassifier(n_estimators=5, random_state=0)# trainclf_.fit(X_train, y_train)# validy_pred_ = clf_.predict(X_test)accuracy = accuracy_score(y_test, y_pred_)print ("Accuracy:", accuracy)      

Accuracy: 0.8733734939759037      

     可以看到sklearn對于Adaboost的封裝使用起來非常便捷，實際工作中我們直接調包即可。

參考資料：

​​https://github.com/eriklindernoren/ML-From-Scratch​​

李航 統計學習方法