1.1 Boost

    Boosting是機器學習的三大框架之一，其特點是，訓練過程中的諸多弱模型，彼此之間有著強依賴關(guān)系。Boost也被稱為增強學習或提升法。典型的代表算法是AdaBoost算法。集成學習中有兩個重要概念，分別為Bagging和Boost。其中Boost也被稱為增強學習或提升法，是一種重要的集成學習方法，它能夠?qū)㈩A測精度僅僅比隨機猜測略高的弱學習器增強為預測精度很高的強學習器。這是在直接構(gòu)造強學習器較為困難的情況下，為學習算法提供了一種有效的新思路和新方法。其中較為成功的是上個世紀90年代Yoav Freund和Robert Schapire提出的AdaBoost算法。

可以將上圖過程總結(jié)為：

對原始數(shù)據(jù)集初始化權(quán)重

用帶權(quán)值數(shù)據(jù)集訓練弱學習器

根據(jù)弱學習器的誤差計算弱學習器的權(quán)重

調(diào)整數(shù)據(jù)集的權(quán)重

重復第2-4步K-1次

將K-1個弱學習器的結(jié)果進行加權(quán)組合

1.2 AdaBoost

1.2.1. 概要介紹

    AdaBoost是Adaptive Boosting（自適應增強）的縮寫，它的自適應在于：被前一個基本分類器誤分類的樣本的權(quán)值會增大，而正確分類的樣本的權(quán)值會減小，并再次用來訓練下一個基本分類器。同時，在每一輪迭代中，加入一個新的弱分類器，直到達到某個預定的足夠小的錯誤率或預先指定的最大迭代次數(shù)再確定最后的強分類器。

從上圖來看，AdaBoost算法可以簡化為3個步驟：

(1)首先，是初始化訓練數(shù)據(jù)的權(quán)值分布D1。假設有N個訓練樣本數(shù)據(jù)，則每一個訓練樣本最開始時，都會被賦予相同的權(quán)值：w1 = 1/N。

(2)訓練弱分類器Ci。具體訓練過程：如果某個訓練樣本點，被弱分類器Ci準確地分類，那么再構(gòu)造下一個訓練集中，它對應的權(quán)值要減?。幌喾?，如果某個訓練樣本點被錯誤分類，那么它的權(quán)值就應該增大。權(quán)值的更新過的樣本被用于訓練下一個弱分類器，整個過程如此迭代下去。

(3)最后，將各個訓練得到的弱分類器組合成一個強分類器。各個弱分類器的訓練過程結(jié)束后，加大分類誤差率小的弱分類器的權(quán)重，使其在最終的分類函數(shù)中起著較大的決定作用，而降低分類誤差率大的弱分類器的權(quán)重，使其在最終的分類函數(shù)中起著較小的決定作用。換而言之，誤差率低的弱分類器在最終分類器中占的權(quán)重較大，否則較小。

1.2.2. AdaBoost算法過程

給定訓練數(shù)據(jù)集：（x1,y1）,(x2,y2)···(xn,yn)，其中yi屬于{1，-1}用于表示訓練樣本的類別標簽，i=1,...,N。Adaboost的目的就是從訓練數(shù)據(jù)中學習一系列弱分類器或基本分類器，然后將這些弱分類器組合成一個強分類器。

相關(guān)符號定義：

Adaboost的算法流程如下：

相關(guān)說明：

綜合上面的推導，可得樣本分錯與分對時，其權(quán)值更新的公式為：

1.2.3. AdaBoost實例講解

    例：給定如圖所示的訓練樣本，弱分類器采用平行于坐標軸的直線，用Adaboost算法的實現(xiàn)強分類過程。

數(shù)據(jù)分析：

    將這10個樣本作為訓練數(shù)據(jù)，根據(jù) X 和Y 的對應關(guān)系，可把這10個數(shù)據(jù)分為兩類，圖中用“+”表示類別1，用“O”表示類別-1。本例使用水平或者垂直的直線作為分類器，圖中已經(jīng)給出了三個弱分類器，即：

初始化：

    首先需要初始化訓練樣本數(shù)據(jù)的權(quán)值分布，每一個訓練樣本最開始時都被賦予相同的權(quán)值：wi=1/N，這樣訓練樣本集的初始權(quán)值分布D1(i)：

令每個權(quán)值w1i = 1/N = 0.1，其中，N = 10，i = 1,2, ..., 10，然后分別對于t= 1,2,3, ...等值進行迭代（t表示迭代次數(shù)，表示第t輪），下表已經(jīng)給出訓練樣本的權(quán)值分布情況：

第1次迭代t=1：

    初試的權(quán)值分布D1為1/N（10個數(shù)據(jù)，每個數(shù)據(jù)的權(quán)值皆初始化為0.1），

D1=[0.1, 0.1, 0.1, 0.1, 0.1, 0.1,0.1, 0.1, 0.1, 0.1]

在權(quán)值分布D1的情況下，取已知的三個弱分類器h1、h2和h3中誤差率最小的分類器作為第1個基本分類器H1(x)（三個弱分類器的誤差率都是0.3，那就取第1個吧）

    在分類器H1(x)=h1情況下，樣本點“5 7 8”被錯分，因此基本分類器H1(x)的誤差率為：

    可見，被誤分類樣本的權(quán)值之和影響誤差率e，誤差率e影響基本分類器在最終分類器中所占的權(quán)重α。

    然后，更新訓練樣本數(shù)據(jù)的權(quán)值分布，用于下一輪迭代，對于正確分類的訓練樣本“1 2 3 4 6 9 10”（共7個）的權(quán)值更新為：

    這樣，第1輪迭代后，最后得到各個樣本數(shù)據(jù)新的權(quán)值分布：

D2=[1/14,1/14,1/14,1/14,1/6,1/14,1/6,1/6,1/14,1/14]

由于樣本數(shù)據(jù)“5 7 8”被H1(x)分錯了，所以它們的權(quán)值由之前的0.1增大到1/6；反之，其它數(shù)據(jù)皆被分正確，所以它們的權(quán)值皆由之前的0.1減小到1/14，下表給出了權(quán)值分布的變換情況：

    可得分類函數(shù)：f1(x)= α1H1(x) = 0.4236H1(x)。此時，組合一個基本分類器sign(f1(x))作為強分類器在訓練數(shù)據(jù)集上有3個誤分類點（即5 7 8），此時強分類器的訓練錯誤為：0.3

第二次迭代t=2：

    在權(quán)值分布D2的情況下，再取三個弱分類器h1、h2和h3中誤差率最小的分類器作為第2個基本分類器H2(x)：

① 當取弱分類器h1=X1=2.5時，此時被錯分的樣本點為“5 7 8”：

誤差率e=1/6+1/6+1/6=3/6=1/2；

② 當取弱分類器h2=X1=8.5時，此時被錯分的樣本點為“3 4 6”：

誤差率e=1/14+1/14+1/14=3/14；

③ 當取弱分類器h3=X2=6.5時，此時被錯分的樣本點為“1 2 9”：

誤差率e=1/14+1/14+1/14=3/14；

    因此，取當前最小的分類器h2作為第2個基本分類器H2(x)

    顯然，H2(x)把樣本“3 4 6”分錯了，根據(jù)D2可知它們的權(quán)值為D2(3)=1/14，D2(4)=1/14， D2(6)=1/14，所以H2(x)在訓練數(shù)據(jù)集上的誤差率：

    這樣，第2輪迭代后，最后得到各個樣本數(shù)據(jù)新的權(quán)值分布：

D3=[1/22,1/22,1/6,1/6,7/66,1/6,7/66,7/66,1/22,1/22]

下表給出了權(quán)值分布的變換情況：

    可得分類函數(shù)：f2(x)=0.4236H1(x) + 0.6496H2(x)。此時，組合兩個基本分類器sign(f2(x))作為強分類器在訓練數(shù)據(jù)集上有3個誤分類點（即3 4 6），此時強分類器的訓練錯誤為：0.3

第三次迭代t=3:

    在權(quán)值分布D3的情況下，再取三個弱分類器h1、h2和h3中誤差率最小的分類器作為第3個基本分類器H3(x)：

① 當取弱分類器h1=X1=2.5時，此時被錯分的樣本點為“5 7 8”：

誤差率e=7/66+7/66+7/66=7/22；

② 當取弱分類器h2=X1=8.5時，此時被錯分的樣本點為“3 4 6”：

誤差率e=1/6+1/6+1/6=1/2=0.5；

③ 當取弱分類器h3=X2=6.5時，此時被錯分的樣本點為“1 2 9”：

誤差率e=1/22+1/22+1/22=3/22；

因此，取當前最小的分類器h3作為第3個基本分類器H3(x)：

    這樣，第3輪迭代后，得到各個樣本數(shù)據(jù)新的權(quán)值分布為：

D4=[1/6,1/6,11/114,11/114,7/114,11/114,7/114,7/114,1/6,1/38]

    下表給出了權(quán)值分布的變換情況：

    可得分類函數(shù)：f3(x)=0.4236H1(x) + 0.6496H2(x)+0.9229H3(x)。此時，組合三個基本分類器sign(f3(x))作為強分類器，在訓練數(shù)據(jù)集上有0個誤分類點。至此，整個訓練過程結(jié)束。

整合所有分類器，可得最終的強分類器為：

    這個強分類器Hfinal對訓練樣本的錯誤率為0！

1.2.4. AdaBoost的優(yōu)點和缺點

優(yōu)點

（1）Adaboost提供一種框架，在框架內(nèi)可以使用各種方法構(gòu)建子分類器?？梢允褂煤唵蔚娜醴诸惼?，不用對特征進行篩選，也不存在過擬合的現(xiàn)象。

（2）Adaboost算法不需要弱分類器的先驗知識，最后得到的強分類器的分類精度依賴于所有弱分類器。無論是應用于人造數(shù)據(jù)還是真實數(shù)據(jù)，Adaboost都能顯著的提高學習精度。

（3）Adaboost算法不需要預先知道弱分類器的錯誤率上限，且最后得到的強分類器的分類精度依賴于所有弱分類器的分類精度，可以深挖分類器的能力。Adaboost可以根據(jù)弱分類器的反饋，自適應地調(diào)整假定的錯誤率，執(zhí)行的效率高。

（4）Adaboost對同一個訓練樣本集訓練不同的弱分類器，按照一定的方法把這些弱分類器集合起來，構(gòu)造一個分類能力很強的強分類器，即“三個臭皮匠賽過一個諸葛亮”。

缺點：

在Adaboost訓練過程中，Adaboost會使得難于分類樣本的權(quán)值呈指數(shù)增長，訓練將會過于偏向這類困難的樣本，導致Adaboost算法易受噪聲干擾。此外，Adaboost依賴于弱分類器，而弱分類器的訓練時間往往很長。

### 定義決策樹樁類作為Adaboost弱分類器

### 定義決策樹樁類### 作為Adaboost弱分類器class DecisionStump():    def __init__(self):        # 基于劃分閾值決定樣本分類為1還是-1        self.label = 1        # 特征索引        self.feature_index = None        # 特征劃分閾值        self.threshold = None        # 指示分類準確率的值        self.alpha = None

### 定義AdaBoost算法類class Adaboost:    # 弱分類器個數(shù)    def __init__(self, n_estimators=5):        self.n_estimators = n_estimators            # Adaboost擬合算法    def fit(self, X, y):        m, n = X.shape        # (1) 初始化權(quán)重分布為均勻分布 1/N        w = np.full(m, (1/m))        # 處初始化基分類器列表        self.estimators = []        # (2) for m in (1,2,...,M)        for _ in range(self.n_estimators):            # (2.a) 訓練一個弱分類器：決策樹樁            estimator = DecisionStump()            # 設定一個最小化誤差            min_error = float('inf')            # 遍歷數(shù)據(jù)集特征，根據(jù)最小分類誤差率選擇最優(yōu)劃分特征            for i in range(n):                # 獲取特征值                values = np.expand_dims(X[:, i], axis=1)                # 特征取值去重                unique_values = np.unique(values)                # 嘗試將每一個特征值作為分類閾值                for threshold in unique_values:                    p = 1                    # 初始化所有預測值為1                    pred = np.ones(np.shape(y))                    # 小于分類閾值的預測值為-1                    pred[X[:, i] < threshold] = -1                    # 2.b 計算誤差率                    error = sum(w[y != pred])                                        # 如果分類誤差大于0.5，則進行正負預測翻轉(zhuǎn)                    # 例如 error = 0.6 => (1 - error) = 0.4                    if error > 0.5:                        error = 1 - error                        p = -1
                    # 一旦獲得最小誤差則保存相關(guān)參數(shù)配置                    if error < min_error:                        estimator.label = p                        estimator.threshold = threshold                        estimator.feature_index = i                        min_error = error                                    # 2.c 計算基分類器的權(quán)重            estimator.alpha = 0.5 * np.log((1.0 - min_error) / (min_error + 1e-9))            # 初始化所有預測值為1            preds = np.ones(np.shape(y))            # 獲取所有小于閾值的負類索引            negative_idx = (estimator.label * X[:, estimator.feature_index] < estimator.label * estimator.threshold)            # 將負類設為 '-1'            preds[negative_idx] = -1            # 2.d 更新樣本權(quán)重            w *= np.exp(-estimator.alpha * y * preds)            w /= np.sum(w)
            # 保存該弱分類器            self.estimators.append(estimator)        # 定義預測函數(shù)    def predict(self, X):        m = len(X)        y_pred = np.zeros((m, 1))        # 計算每個弱分類器的預測值        for estimator in self.estimators:            # 初始化所有預測值為1            predictions = np.ones(np.shape(y_pred))            # 獲取所有小于閾值的負類索引            negative_idx = (estimator.label * X[:, estimator.feature_index] < estimator.label * estimator.threshold)            # 將負類設為 '-1'            predictions[negative_idx] = -1            # 2.e 對每個弱分類器的預測結(jié)果進行加權(quán)            y_pred += estimator.alpha * predictions
        # 返回最終預測結(jié)果        y_pred = np.sign(y_pred).flatten()        return y_pred

導入sklearn adaboost分類器
from sklearn.ensemble import AdaBoostClassifier創(chuàng)建Adaboost模型實例clf_ = AdaBoostClassifier(n_estimators=5, random_state=0)模型擬合clf_.fit(X_train, y_train)模型預測y_pred_ = clf_.predict(X_test)計算模型預測準確率accuracy = accuracy_score(y_test, y_pred_)

print('Accuracy of AdaBoost by sklearn:', accuracy)

3.1 回歸器：

參數(shù)介紹：

base_estimator:

    object,optional(default=DecisionTreeRegressor)。 基估計器，理論上可以選擇任何回歸器，但是這個地方需要支持樣本加權(quán)重，as well as proper classes_ and n_classes_ attributes.（這個地方不過會翻譯）。常用的是CART回歸樹和神經(jīng)網(wǎng)絡，默認CART回歸樹，即AdaBoostRegressor默認使用CART回歸樹DecisionTreeRegressor。

n_estimators :

    integer, optional (default=50)。基估計器的個數(shù)。

ν的取值范圍為0<ν≤1。對于同樣的訓練集擬合效果，較小的ν意味著我們需要更多的弱學習器的迭代次數(shù)。通常我們用步長和迭代最大次數(shù)一起來決定算法的擬合效果。所以這兩個參數(shù)n_estimators和learning_rate要一起調(diào)參。一般來說，可以從一個小一點的ν開始調(diào)參，默認是1。

loss : 

 {'linear’, 'square’, 'exponential’}, optional (default=’linear’)。Adaboost.R2算法需要用到。有線性'linear’, 平方'square’和指數(shù) 'exponential’三種選擇, 默認是線性，一般使用線性就足夠了，除非你懷疑這個參數(shù)導致擬合程度不好。這個值的意義，它對應了我們對第k個弱分類器的中第i個樣本的誤差的處理，即：

如果是線性誤差，則

如果是平方誤差，則

如果是指數(shù)誤差，則

，式中Ek為訓練集上的最大誤差Ek=max|yi?Gk(xi)|i=1,2...m

random_state : 

    int, RandomState instance or None, optional (default=None)

屬性介紹：

estimators_ : list of classifiers

estimator_weights_ : array of floats

estimator_errors_ : array of floats

feature_importances_ : array of shape = [n_features]

方法介紹：

3.2 分類器

class sklearn.ensemble.AdaBoostClassifier(base_estimator=None, *, n_estimators=50, learning_rate=1.0, algorithm='SAMME.R', random_state=None)

參數(shù)介紹：

base_estimator :

    object, optional (default=DecisionTreeClassifier)?；烙嬈鳎碚撋峡梢赃x擇任何分類器，但是這個地方需要支持樣本加權(quán)重，as well as proper classes_ and n_classes_ attributes.（這個地方不過會翻譯）。常用的是CART決策樹和神經(jīng)網(wǎng)絡，默認CART決策樹，即AdaBoostClassifier默認使用CART決策樹DecisionTreeClassifier。

n_estimators :

    integer, optional (default=50)?；烙嬈鞯膫€數(shù)。

learning_rate : 

    float, optional (default=1.)。通過這個參數(shù)縮減每個分類器的貢獻，learning_rate和n_estimators 兩個參數(shù)之間存在權(quán)衡。

algorithm : 

    {'SAMME’, 'SAMME.R’}, optional (default=’SAMME.R’)。如果'SAMME.R'則使用SAMME.R （Real Boosting） 算法。base_estimator必須支持類概率的計算。如果'SAMME'則使用SAMME （discrete boosting） 算法。SAMME.R算法通常收斂速度高于SAMME，通過較少的升壓迭代實現(xiàn)較低的測試誤差。（老哥們有好的翻譯理解記得評論下?。?/p>

    如果我們選擇的AdaBoostClassifier算法是SAMME.R，則我們的弱分類學習器還需要支持概率預測，也就是在scikit-learn中弱分類學習器對應的預測方法除了predict還需要有predict_proba。

    兩者的主要區(qū)別是弱學習器權(quán)重的度量，SAMME使用了和我們的原理篇里二元分類Adaboost算法的擴展，即用對樣本集分類效果作為弱學習器權(quán)重，而SAMME.R使用了對樣本集分類的預測概率大小來作為弱學習器權(quán)重。由于SAMME.R使用了概率度量的連續(xù)值，迭代一般比SAMME快，因此AdaBoostClassifier的默認算法algorithm的值也是SAMME.R。我們一般使用默認的SAMME.R就夠了，但是要注意的是使用了SAMME.R， 則弱分類學習器參數(shù)base_estimator必須限制使用支持概率預測的分類器。SAMME算法則沒有這個限制。

random_state :

    int, RandomState instance or None, optional (default=None)。如果int，random_state是隨機數(shù)生成器使用的種子; 如果RandomState的實例，random_state是隨機數(shù)生成器; 如果None，則隨機數(shù)生成器是由np.random使用的RandomState實例。

屬性介紹：

estimators_ : 

    list of classifiers 子估計器

classes_ : 

    array of shape = [n_classes] 類別的標簽信息

n_classes_ : 

    int 類別的數(shù)量

estimator_weights_ :

    array of floats 每個基估計器的權(quán)重

estimator_errors_ : 

    array of floats 每個基估計器的錯誤率

feature_importances_ :

    array of shape = [n_features] 如果基估計器支持的話