0x00 前言

本文是《GBDT源碼分析》系列的第三篇镀虐，主要關(guān)注和GBDT本身以及Ensemble算法在scikit-learn中的實(shí)現(xiàn)。

0x01 整體說(shuō)明

scikit-learn的ensemble模塊里包含許多各式各樣的集成模型帮非，所有源碼均在sklearn/ensemble文件夾里，代碼的文件結(jié)構(gòu)可以參考該系列的第一篇文章讹蘑。其中 GradientBoostingRegressor 和 GradientBoostingClassifier分別是基于grandient_boosting的回歸器和分類器末盔。

0x02 源碼結(jié)構(gòu)分析

BaseEnsemble

ensemble中的所有模型均基于基類BaseEnsemble，該基類在sklearn/ensemble/base.py里衔肢。BaseEnsemble繼承了兩個(gè)父類庄岖，分別是BaseEstimator和MetaEstimatorMixin。BaseEnsemble里有如下幾個(gè)方法角骤，基本都是私有方法：

• __init__: 初始化方法隅忿，共三個(gè)參數(shù)base_estimator, n_estimators, estimator_params心剥。
• _validate_estimator: 對(duì)n_estimators和base_estimator做檢查，其中base_enstimator指集成模型的基模型背桐。在GBDT中优烧，base_estimator（元算法/基模型）是決策樹(shù)。
• _make_estimator: 從base_estimator中復(fù)制參數(shù)链峭。
• __len__: 返回ensemble中estimator的個(gè)數(shù)畦娄。
• __getitem__: 返回ensemble中第i個(gè)estimator。
• __iter__: ensemble中所有estimator的迭代器弊仪。

gradient_boosting.py

GradientBoostingClassifier和GradientBoostingRegressor這兩個(gè)模型的實(shí)現(xiàn)均在gradient_boosting.py里熙卡。事實(shí)上，該腳本主要實(shí)現(xiàn)了一個(gè)集成回歸樹(shù)Gradient Boosted Regression Tree励饵，而分類器和回歸器都是基于該集成回歸樹(shù)的驳癌。

注意： 這里要先說(shuō)明一個(gè)問(wèn)題，GBDT本質(zhì)上比較適合回歸和二分類問(wèn)題役听，而并不特別適用于多分類問(wèn)題颓鲜。在scikit-learn中，處理具有K類的多分類問(wèn)題的GBDT算法實(shí)際上在每一次迭代里都構(gòu)建了K個(gè)決策樹(shù)典予，分別對(duì)應(yīng)于這K個(gè)類別甜滨。我們?cè)诶碚搶W(xué)習(xí)時(shí)并沒(méi)有怎么接觸過(guò)這個(gè)點(diǎn)，這里也并不對(duì)多分類問(wèn)題做闡述瘤袖。

實(shí)現(xiàn)Gradient Boosted Regression Tree的類是BaseGradientBoosting衣摩，它是GradientBoostingClassifier和GradientBoostingRegressor的基類。它實(shí)現(xiàn)了一個(gè)通用的fit方法孽椰，而回歸問(wèn)題和分類問(wèn)題的區(qū)別主要在于損失函數(shù)LossFunction上昭娩。

下面我們梳理一下gradient_boosting.py的內(nèi)容。

基本的estimator類

一些簡(jiǎn)單基本的estimator類黍匾，主要用于LossFunction中init_estimator的計(jì)算栏渺，即初始預(yù)測(cè)值的計(jì)算。舉例來(lái)說(shuō)：QuantileEstimator(alpha=0.5) 代表用中位數(shù)作為模型最初的預(yù)測(cè)值锐涯。

• QuantileEstimator: 預(yù)測(cè)訓(xùn)練集target的alpha-百分位的estimator磕诊。
• MeanEstimator: 預(yù)測(cè)訓(xùn)練集target的平均值的estimator。
• LogOddsEstimator: 預(yù)測(cè)訓(xùn)練集target的對(duì)數(shù)幾率的estimator（適合二分類問(wèn)題）纹腌。
• ScaledLogOddsEstimator: 縮放后的對(duì)數(shù)幾率（適用于指數(shù)損失函數(shù)）霎终。
• PriorProbabilityEstimator: 預(yù)測(cè)訓(xùn)練集中每個(gè)類別的概率。
• ZeroEstimator： 預(yù)測(cè)結(jié)果都是0的estimator升薯。

LossFunction

LossFunction: 損失函數(shù)的基類莱褒，有以下一些主要方法

• __init__: 輸入為n_classes。當(dāng)問(wèn)題是回歸或二分類問(wèn)題時(shí)涎劈，n_classes為1广凸；K類多分類為題時(shí)n_classes為K阅茶。
• init_estimator: LossFunction的初始estimator，對(duì)應(yīng)上述那些基本的estimator類谅海，用來(lái)計(jì)算模型初始的預(yù)測(cè)值脸哀。在基類中不實(shí)現(xiàn)，并拋出NotImplementedError扭吁。
• negative_gradient： 根據(jù)預(yù)測(cè)值和目標(biāo)值計(jì)算負(fù)梯度撞蜂。
• update_terminal_regions: 更新樹(shù)的葉子節(jié)點(diǎn)，更新模型的當(dāng)前預(yù)測(cè)值侥袜。
• _update_terminal_regions: 更新樹(shù)的葉子節(jié)點(diǎn)的方法模板蝌诡。

RegressionLossFunction

RegressionLossFunction: 繼承LossFunction類，是所有回歸損失函數(shù)的基類枫吧。

• LeastSquaresError: init_estimator是MeanEstimator送漠；負(fù)梯度是目標(biāo)值y和預(yù)測(cè)值pred的差；唯一一個(gè)在update_terminal_regions中不需要更新葉子節(jié)點(diǎn)value的LossFunction由蘑。
• LeastAbsoluteError: init_estimator是QuantileEstimator(alpha=0.5)；負(fù)梯度是目標(biāo)值y和預(yù)測(cè)值pred的差的符號(hào)代兵，適用于穩(wěn)健回歸尼酿。
• HuberLossFunction: 一種適用于穩(wěn)健回歸Robust Regression的損失函數(shù)，init_estimator是QuantileEstimator(alpha=0.5)植影。
• QuantileLossFunction: 分位數(shù)回歸的損失函數(shù)裳擎，分位數(shù)回歸允許估計(jì)目標(biāo)值條件分布的百分位值。

ClassificationLossFunction

ClassificationLossFunction: 繼承LossFunction思币，是所有分類損失函數(shù)的基類鹿响。有_score_to_proba（將分?jǐn)?shù)轉(zhuǎn)化為概率的方法模板）以及_score_to_decision（將分?jǐn)?shù)轉(zhuǎn)化為決定的方法模板）兩個(gè)抽象方法。

• BinomialDeviance: 二分類問(wèn)題的損失函數(shù)谷饿，init_estimator是LogOddsEstimator惶我。
• MultinomialDeviance: 多分類問(wèn)題的損失函數(shù)，init_estimator是PriorProbabilityEstimator博投。
• ExponentialLoss: 二分類問(wèn)題的指數(shù)損失绸贡，等同于AdaBoost的損失。init_estimator是ScaledLogOddsEstimator毅哗。

其它

gradient_boosting.py文件里還有以下幾個(gè)內(nèi)容听怕，再下一章里我們將對(duì)這些內(nèi)容做深入分析。

• VerboseReporter: 輸出設(shè)置虑绵。
• BaseGradientBoosting: Gradient Boosted Regression Tree的實(shí)現(xiàn)基類尿瞭。
• GradientBoostingClassifier: Gradient Boosting分類器。
• GradientBoostingRegressor: Gradient Boosting回歸器翅睛。

0x03 GDBT主要源碼分析

BaseGradientBoosting

下面我們具體看一下BaseGradientBoosting這個(gè)基類声搁，該類有幾個(gè)主要方法：

• __init__: 除了來(lái)自決策樹(shù)的參數(shù)外黑竞，還有n_estimators, learning_rate, loss, init, alpha, verbose, warm_start幾個(gè)新的參數(shù)。其中l(wèi)oss是損失函數(shù)LossFunction的選擇酥艳，learning_rate為學(xué)習(xí)率摊溶，n_estimators是boosting的次數(shù)（迭代次數(shù)或者Stage的個(gè)數(shù)）。通常learning_rate和n_estimators中需要做一個(gè)trade_off上的選擇充石。init參數(shù)指的是BaseEstimator莫换，即默認(rèn)為每個(gè)LossFunction里面的init_estimator，用來(lái)計(jì)算初始預(yù)測(cè)值骤铃。warm_start決定是否重用之前的結(jié)果并加入更多estimators拉岁，或者直接抹除之前的結(jié)果。
• _check_params: 檢查參數(shù)是否合法惰爬，以及初始化模型參數(shù)（包括所用的loss等）喊暖。
• _init_state: 初始化init_estimator以及model中的狀態(tài)（包括init_estimator、estimators_撕瞧、train_score_陵叽、oob_improvement_，后三個(gè)都是數(shù)組丛版，分別存儲(chǔ)每一個(gè)Stage對(duì)應(yīng)的estimator巩掺、訓(xùn)練集得分和outofbag評(píng)估的進(jìn)步）。
• _clear_state: 清除model的狀態(tài)页畦。
• _resize_state: 調(diào)整estimators的數(shù)量胖替。
• fit: 訓(xùn)練gradient boosting模型，會(huì)調(diào)用_fit_stages方法豫缨。
• _fit_stages: 迭代boosting訓(xùn)練的過(guò)程独令，會(huì)調(diào)用_fit_stage方法。
• _fit_stage: 單次stage訓(xùn)練過(guò)程好芭。
• _decision_function：略燃箭。
• _staged_decision_function：略。
• _apply：返回樣本在每個(gè)estimator落入的葉子節(jié)點(diǎn)編號(hào)舍败。

fit方法

# 如果不是warm_start遍膜，清除之前的model狀態(tài)
if not self.warm_start:
____self._clear_state()

# ......檢查輸入、參數(shù)是否合法
# ......如果模型沒(méi)有被初始化瓤湘，則初始化模型瓢颅，訓(xùn)練出初始模型以及預(yù)測(cè)值；
# ......如果模型已被初始化弛说，判斷n_estimators的大小并重新設(shè)置模型狀態(tài)挽懦。
# boosting訓(xùn)練過(guò)程，調(diào)用_fit_stages方法
n_stages = self._fit_stages(X, y, y_pred, sample_weight, random_state, begin_at_stage, monitor, X_idx_sorted)
# ......當(dāng)boosting訓(xùn)練次數(shù)與初始化的estimators_長(zhǎng)度不一致時(shí)木人，修正相關(guān)變量/狀態(tài)信柿，包括estimators_冀偶、train_score_、oob_improvement_
# fit方法返回self

_fit_stages方法

# 獲取樣本數(shù)（為什么每次都要獲取樣本數(shù)而不作為self.n_samples呢）
n_samples = X.shape[0]
# 判斷是否做oob（交叉驗(yàn)證）渔嚷，僅當(dāng)有抽樣時(shí)才做oob
do_oob = self.subsample < 1.0
# 初始化sample_mask进鸠，即標(biāo)注某一輪迭代每個(gè)樣本是否要被抽樣的數(shù)組
sample_mask = np.ones((n_samples, ), dtype=np.bool)
# 計(jì)算inbag（用來(lái)訓(xùn)練的樣本個(gè)數(shù)）
n_inbag = max(1, int(self.subsample * n_samples))
# 獲取loss對(duì)象
loss_ = self.loss_
# ......設(shè)置min_weight_leaf、verbose形病、sparsity等相關(guān)參數(shù)
# 開(kāi)始boosting迭代
# begin_at_stage是迭代初始次數(shù)客年，一般來(lái)說(shuō)是0，如果是warm_start則是之前模型結(jié)束的地方
i = begin_at_stage
# 開(kāi)始迭代
for i in range(begin_at_stage, self.n_estimators):
    # 如果subsample < 1漠吻，do_oob為真量瓜，做下采樣
    if do_oob:
        # _random_sample_mask是在_gradient_boosting.pyx里用cpython實(shí)現(xiàn)的一個(gè)方法，用來(lái)做隨機(jī)采樣途乃，生成inbag/outofbag樣本（inbag樣本為T(mén)rue）
        sample_mask = _random_sample_mask(n_samples, n_inbag, random_state)
        # 獲得之前的oob得分
        old_oob_score = loss_(y[~sample_mask], y_pred[~sample_mask], sample_weight[~sample_mask])

        # 調(diào)用_fit_stage來(lái)訓(xùn)練下一階段的數(shù)
        y_pred = self._fit_stage(i, X, y, y_pred, sample_weight, sample_mask, random_state, X_idx_sorted, X_csc, X_csr)

    # 跟蹤偏差/loss
    # 當(dāng)do_oob時(shí)绍傲，計(jì)算訓(xùn)練樣本的loss和oob_score的提升值
    if do_oob:
        # inbag訓(xùn)練樣本的loss
        self.train_score_[i] = loss_(y[sample_mask], y_pred[sample_mask], sample_weight[sample_mask])
        # outofbag樣本的loss提升
        self.oob_improvement_[i] = (old_oob_score - loss_(y[~sample_mask], y_pred[~sample_mask], sample_weight[~sample_mask]))
    # subsample為1時(shí)
    else:
        self.train_score_[i] = loss_(y, y_pred, sample_weight)

    # 若verbose大于0，更新標(biāo)準(zhǔn)輸出
    if self.verbose > 0:
        verbose_reporter.update(i, self)
    # ......若有monitor耍共，檢查是否需要early_stopping
# _fit_stages方法返回i+1烫饼，即迭代總次數(shù)（包括warm_start以前的迭代）

_fit_stage方法

# 判斷sample_mask的數(shù)據(jù)類型
assert sample_mask.dtype == np.bool
# 獲取損失函數(shù)
loss = self.loss_
# 獲取目標(biāo)值 
original_y = y
# 這里K針對(duì)的是多分類問(wèn)題，回歸和二分類時(shí)K為1
for k in range(loss.K):
    # 當(dāng)問(wèn)題是多分類問(wèn)題時(shí)试读，獲取針對(duì)該分類的y值
    if loss.is_multi_class:
        y = np.array(original_y == k, dtype=np.float64)
    # 計(jì)算當(dāng)前負(fù)梯度
    residual = loss.negative_gradient(y, y_pred, k=k, sample_weight=sample_weight)
    # 構(gòu)造決策回歸樹(shù)（事實(shí)上是對(duì)負(fù)梯度做決策樹(shù)模型）
    tree = DecisionTreeRegressor(
        criterion=self.criterion,
        splitter='best',
        max_depth=self.max_depth,
        min_samples_split=self.min_samples_split,
        min_samples_leaf=self.min_samples_leaf,
        min_weight_fraction_leaf=self.min_weight_fraction_leaf,
        min_impurity_split=self.min_impurity_split,
        max_features=self.max_features,
        max_leaf_nodes=self.max_leaf_nodes,
        random_state=random_state,
        presort=self.presort)
    # 如果做sabsample枫弟，重新計(jì)算sample_weight
    if self.subsample < 1.0:
        sample_weight = sample_weight * sample_mask.astype(np.float64)
    # 根據(jù)輸入X是否稀疏，采用不同的fit方法鹏往，針對(duì)負(fù)梯度訓(xùn)練決策樹(shù)
    if X_csc is not None:
        tree.fit(X_csc, residual, sample_weight=sample_weight, check_input=False, X_idx_sorted=X_idx_sorted)
    else:
        tree.fit(X, residual, sample_weight=sample_weight, check_input=False, X_idx_sorted=X_idx_sorted)
    # 根據(jù)輸入X是否稀疏，使用update_terminal_regions方法更新葉子節(jié)點(diǎn)（注意這是LossFunction里的一個(gè)方法）
    if X_csr is not None:
        loss.update_terminal_regions(tree.tree_, X_csr, y, residual, y_pred, sample_weight, sample_mask, self.learning_rate, k=k)
    else:
        loss.update_terminal_regions(tree.tree_, X, y, residual, y_pred, sample_weight, sample_mask, self.learning_rate, k=k)
    # 將新的樹(shù)加入到ensemble模型中
    self.estimators_[i, k] = tree
# _fit_stage方法返回新的預(yù)測(cè)值y_pred骇塘，注意這里y_pred是在loss.update_terminal_regions計(jì)算的

LossFunction中的update_terminal_regions方法

為了加深理解伊履，我么我們?cè)倏匆幌聈pdate_terminal_regions都做了什么。

# 計(jì)算每個(gè)樣本對(duì)應(yīng)到樹(shù)的哪一個(gè)葉子節(jié)點(diǎn)
terminal_regions = tree.apply(X)
# 將outofbag的樣本的結(jié)果都置為-1（不參與訓(xùn)練過(guò)程）
masked_terminal_regions = terminal_regions.copy()
masked_terminal_regions[~sample_mask] = -1
# 更新每個(gè)葉子節(jié)點(diǎn)上的value款违，tree.children_left == TREE_LEAF是判斷葉子節(jié)點(diǎn)的方法唐瀑。一個(gè)很關(guān)鍵的點(diǎn)是這里只更新了葉子節(jié)點(diǎn)，而只有LossFunction是LeastSquaresError時(shí)訓(xùn)練時(shí)生成的決策樹(shù)上的value和我們實(shí)際上想要的某個(gè)節(jié)點(diǎn)的預(yù)測(cè)值是一致的插爹。
for leaf in np.where(tree.children_left == TREE_LEAF)[0]:
    # _update_terminal_region由每個(gè)具體的損失函數(shù)具體實(shí)現(xiàn)哄辣，在LossFunction基類中只提供模板
    self._update_terminal_region(tree, masked_terminal_regions, leaf, X, y, residual, y_pred[:, k], sample_weight)
# 更新預(yù)測(cè)值，tree預(yù)測(cè)的是負(fù)梯度值赠尾，預(yù)測(cè)值通過(guò)加上學(xué)習(xí)率 * 負(fù)梯度來(lái)更新力穗，這里更新所有inbag和outofbag的預(yù)測(cè)值
y_pred[:, k] += (learning_rate * tree.value[:, 0, 0].take(terminal_regions, axis=0))

筆者之前使用GBDT做回歸模型時(shí)觀察每顆樹(shù)的可視化結(jié)果，發(fā)現(xiàn)對(duì)于損失函數(shù)是ls（LeastSquaresError）的情況气嫁，每棵樹(shù)的任意一個(gè)節(jié)點(diǎn)上的value都是當(dāng)前點(diǎn)的target預(yù)估值差（即residual当窗，所有樹(shù)葉子節(jié)點(diǎn)預(yù)測(cè)的都是residual，它們的和是最終的預(yù)測(cè)結(jié)果）寸宵；但使用lad損失函數(shù)時(shí)崖面，只有葉子節(jié)點(diǎn)的結(jié)果是收入預(yù)估值差元咙。原因應(yīng)該就在這里：

• ls對(duì)應(yīng)的LossFunction類是LeastSquaresError，每個(gè)節(jié)點(diǎn)的value就是當(dāng)前點(diǎn)的target預(yù)估值差巫员，葉子節(jié)點(diǎn)也不需要更新庶香。這是因?yàn)閘s的負(fù)梯度計(jì)算方法是預(yù)測(cè)值和目標(biāo)值的差，這本身就是residual的概念简识，所以所有節(jié)點(diǎn)的value都是我們想要的值赶掖。
• lad對(duì)應(yīng)的LossFunction類是LeastAbsoluteError，每個(gè)節(jié)點(diǎn)的value并不是當(dāng)前點(diǎn)的target預(yù)估值差财异，而最后代碼里也只更新了葉子節(jié)點(diǎn)倘零，所以可視化時(shí)會(huì)有一些問(wèn)題，也不能直接獲得每個(gè)節(jié)點(diǎn)的value作為target預(yù)估值差戳寸。事實(shí)上呈驶，lad在訓(xùn)練的時(shí)候有點(diǎn)像一個(gè)“二分類”問(wèn)題，它的負(fù)梯度只有兩種取值-1和1疫鹊，即預(yù)測(cè)值比目標(biāo)值大還是小袖瞻，然后根據(jù)這個(gè)標(biāo)準(zhǔn)進(jìn)行分裂。

所以如果沒(méi)有改源碼并重新訓(xùn)練模型的話拆吆，若不是ls聋迎，其它已有的GBDT模型沒(méi)有辦法直接獲取每個(gè)非葉子結(jié)點(diǎn)的target預(yù)估值差，這個(gè)在分析模型時(shí)會(huì)有一些不方便的地方枣耀。

feature_importances_的計(jì)算

# 初始化n_feautures_長(zhǎng)度的數(shù)組
total_sum = np.zeros((self.n_features_, ), dtype=np.float64)
# 對(duì)于boosting模型中的每一個(gè)estimator（實(shí)際上就是一棵樹(shù)霉晕，多分類是多棵樹(shù)的數(shù)組）
for stage in self.estimators_:
    # 當(dāng)前stage每個(gè)feature在各個(gè)樹(shù)內(nèi)的所有的importance平均（多分類時(shí)一個(gè)stage有多棵樹(shù)）
    stage_sum = sum(tree.feature_importances_ for tree in stage) / len(stage)
    # 累加各個(gè)stage的importance
    total_sum += stage_sum
# 做歸一化
importances = total_sum / len(self.estimators_)

GradientBoostingClassifier

GBDT分類器的loss可取deviance或exponential，分別對(duì)應(yīng)MultinomialDeviance和ExponentialLoss這兩個(gè)損失函數(shù)捞奕。分類器在predict時(shí)需要多加一步牺堰，把不同類別對(duì)應(yīng)的樹(shù)的打分綜合起來(lái)才能輸出結(jié)果。因此GBDT實(shí)際上不太適合做多分類問(wèn)題颅围。

GradientBoostingRegressor

GBDT回歸器的loss可取ls, lad, huber, quantile伟葫，分別對(duì)應(yīng)LeastSquaresError, LeastAbsoluteError, HuberLossFunction, QuantileLossFunction這幾個(gè)損失函數(shù)。

0xFF 總結(jié)

至此院促，該系列三篇文章已結(jié)筏养。

作者：cathyxlyl | 簡(jiǎn)書(shū) | GITHUB

個(gè)人主頁(yè)：http://cathyxlyl.github.io/
文章可以轉(zhuǎn)載, 但必須以超鏈接形式標(biāo)明文章原始出處和作者信息