machine_learning_with_code_trees

决策树。

# 序

决策树是机器学习中非常重要的算法，未来会在学术界占据相当大的比重。我说的。

本贴将介绍决策树的基本思想，只有学习了决策树的基本思想，才能掌握决策树的进阶算法——随机森林、梯度提升树等。而这些进阶算法未来将在学术界大放光彩。

# 术语

决策树组成部分如下：

根节点：最上层的起始节点，选取某个特征为根节点。
决策节点：也称子节点。选取不同特征为子节点。
叶节点：没有子节点的最终节点。预测样本的最终分类。通常用方框表示。

深度 Depth ：从根节点到最深层叶节点的路径长度。
纯度 Purity ：节点分支所包含样本的纯净程度。如全为同类样本，则纯度为1。该指标在决策树确定节点以及进行拆分时至关重要。
预剪枝 Pre-puring ：是一种在构建决策树模型时在分裂节点之前进行限制和控制的策略。它旨在防止决策树过度拟合训练数据，从而提高模型的泛化能力和性能。预剪枝通过在决策树生长过程中应用各种条件来限制节点的划分，从而限制树的深度和宽度，以避免生成过于复杂的模型。也称为early stopping。
后剪枝 Post-puring ：是一种优化决策树模型的方法，它在构建完整的决策树之后，通过修剪掉部分节点和子树来提高模型的泛化性能和效果。后剪枝的目标是减少过拟合，使得决策树更能适应新的未见数据。

# 学习过程

1.决定以哪个特征为根节点、以哪个特征为子节点

决策树会以最大化纯度为目的来选择根节点和子节点。从结果上看决策树会尽可能使得左侧分支有更多正例，而右侧分支有更多负例。当分支内全为某一类样本时，则纯度为1。然而实际上更多情况是正负例混杂，因此需要引入熵 Entropy 来度量不纯度。

通过最大信息增益来选择特征。

2.重复上述过程，直到达到停止标准时停止拆分

当节点上所有样本为同一类(全是猫)时停止拆分。
再拆分会导致决策树超过最大深度时停止拆分,如决定深度最大为3，则在 Depth 3 或之前将输出结果。限制决策树深度的原因是不想它变得太大、笨重，保持决策树较小会使得它不太容易过拟合。一般来说开源库算法帮用户选择的深度效果会不错，但用户也可以自己使用交叉验证集来选择深度。
再拆分后对纯度的改善太小(信息增益小于阈值)、信息增益带来的效益不及深度增加带来的损失，这时也会停止拆分，以降低过拟合风险。
当节点上的样本量小于某个阈值时(如节点上仅有3个样本)，停止拆分。这使得决策树较小进而降低过拟合的风险。

# 通过信息增益选择节点

在决策树的节点选择当中遵从的是最大化纯度原则。也就是说选取的特征应最大化减少不纯度 Inpurity (熵)。熵的减少称为信息增益，应选取最大化信息增益的特征作为节点。

度量(不)纯度

节点所含样本类别的一致性程度称为纯度 Purity ，不一致性称为不纯度 Inpurity 。不纯度越小意为纯度越高，度量不纯度时需要引入熵 Entropy ，其计算公式如下图所示：

其中， p₁ 为正例个数占节点所含样本量的比例； p₀ 为负例个数占节点所含样本量的比例；熵 H(p₁) 表示不纯度。

注：虽然算法取自然数为底也能正常运行，但是结果会不好解释；按照熵计算的惯例定义 0log₂(0)=0 ；除 Entropy 外，基尼系数也是被广泛运用的衡量不纯度的标准之一，参考此处。

度量信息增益

结合熵来计算信息增益，从而选取使得信息增益最大化的特征作为根节点或子节点。较高的信息增益将使得自己纯度更大。信息增益的公式如下所示：

其中， p₁^root 为上一个节点所含样本内正例的占比。若当前步骤在确定根节点，那么该值为训练样本中正例的占比； p₁^left 是以该特征为节点后，左侧分支正例占该分支样本的比例； p₁^right 是以该特征为节点后，右侧分支正例占该分支样本的比例； w^left 是以该特征为节点后，从该节点流入左侧分支的样本量占比； w^right 是以该特征为节点后，从该节点流入右侧分支的样本量占比； H() 为熵的计算函数。

注：左右分支熵的加权和为选取该特征作为节点后取得的熵值。

# 独热编码

当特征涉及三个及以上的特征值时，需要使用独热编码 One-hot encoding 将每一个可能的特征值拆分成新的特征。

如耳朵形状特征有三个可能的特征值：点状、垂状、卵状。使用独热编码将它转换为三个新的特征——耳形是否为点状、耳形是否为垂状、耳形是否为卵状，这三个新特征可能的取值均为0或1。这样使得决策树模型能够识别拥有三个特征值的特征所带来的信息。

# 连续型变量

特征值为连续型变量

当特征值为连续型变量时，依旧采用最大化信息增益原则作为选取节点的根本原则。然而，额外的遍历需要被使用在计算信息增益的过程中。如下图所示，需要遍历完该特征上每一个值，以找到使得信息增益最大化的值作为阈值，以此作为分割点来将样本分流至左右分支。

目标变量为连续型变量时节点的选择

最大化信息增益依旧是决策树的构建、节点选择的原则，然而，不再使用熵 Entropy 来度量信息增益，而是使用方差的变化来度量信息增益。具体如下图所示：

其中，Weights是该情形连续型目标变量的名称，意为体重； Variance^root 为上一个节点所含样本目标变量(体重)的方差。若当前步骤在确定根节点，那么该值为训练样本中目标变量的方差； Variance^left 是以该特征为节点后，左侧分支所含样本的目标变量的方差； Variance^right 是以该特征为节点后，右侧分支所含样本的目标变量的方差； w^left 是以该特征为节点后，从该节点流入左侧分支的样本量占比； w^right 是以该特征为节点后，从该节点流入右侧分支的样本量占比。

目标变量为连续型变量时的输出

与目标为离散型变量时输出为某一类型不同，连续型目标变量的决策树输出的是叶节点所含样本目标变量的平均值。这是在最小化决策树损失值时求导推理出来的数学公式。

式中， m 为训练集总样本量； c_l 为第l个叶节点的输出值； I() 函数判定是否为输出叶节点，若是，返回1，否则返回〇； y_i 为第i个样本的目标变量； L 为所有叶节点的数量； LeafNode_l 为第l个叶节点； M_l 为第l个叶节点上的样本量。

# 决策树优缺点

参考 scikit-learn 的官方文档，在此处列举决策树的优缺点。

优点如下：

容易理解与解释，决策树可以被可视化呈现。

仅需较少的数据预处理，不需要做数据标准化处理，不需要创建哑变量，不需要删除空白值。不过该模型不支持缺失值处理。

使用决策树预测数据的成本与用于训练的数据量成对数关系。

既能处理离散值又能处理连续值。很多模型仅专注于处理某一类(连续或离散)数据。

支持多输出。多输出指给定输入，输出多个值。如给定输入，输出经纬度(X/Y)。

使用白箱模型，相对于使用黑箱模型的模型(如神经网络)，更好使用布尔逻辑来解释。

可以通过统计检验来验证模型。这样就可以说明(量化)模型的可靠性。

即使其假设在一定程度上违反了生成数据的真实模型，也能表现良好。换句话说，对于异常点的容错能力好，鲁棒性(健壮性)高。

缺点如下：

过于复杂的决策树容易导致过拟合，需要采用预剪枝和后剪枝等方法来改进。

决策树会因为训练样本的微小变化而使得树结构发生剧烈改变。可以通过集成学习改善。

决策树的预测结果既不平滑也不连续，而是分段近似。因此，决策树模型不擅长外推(泛化效果欠佳)。

决策树的学习存在NP完全问题，因此决策树的学习算法都基于启发式算法(如贪婪算法)，即在每个节点上做出局部最优决策。这种算法不能保证结果为全局最优解，因此，需要通过集成学习来改善。因为集成学习中特征和样本都是随机抽样替换的。

有些概念很难学习，因为决策树不容易表达这些概念，例如 XOR、奇偶校验或多路复用器问题。

使用偏斜数据集训练的决策树通常也是有偏的，因此训练之前需要平衡一下样本。

# CART决策树

在决策树领域，CART Classification And Regression Tree 决策树运用得更为广泛。上述内容除了以熵度量不纯度以及以最大化信息增益为原则选取节点的思想来自ID3、C4.5决策树，其他内容均适用于CART决策树。

在CART决策树中，使用基尼系数度量不纯度，而不是熵；以最小化基尼系数为原则选取节点，而不是最大化信息增益。决策树中基尼系数公式如下所示：

其中， w^left 是以该特征为节点后，从该节点流入左侧分支的样本量占比； w^right 是以该特征为节点后，从该节点流入右侧分支的样本量占比； p₁^left 是以该特征为节点后，左侧分支正例占该分支样本的比例； p₀^left 是以该特征为节点后，左侧分支负例占该分支样本的比例，可表示为(1-p₁^left)； p₁^right 是以该特征为节点后，右侧分支正例占该分支样本的比例； p₀^right 是以该特征为节点后，右侧分支负例占该分支样本的比例，可表示为(1-p₁^right)。

以数学公式表达CART决策树的输出：

式中， l 为每个叶节点的编号； L 为所有叶节点的数量； c_l 为第l个叶节点的输出，若是回归树，则为样本目标变量的均值，若是分类树，则是类别； I() 函数判定是否为输出叶节点，若是，返回1，否则返回〇； LeafNode_l 为第l个叶节点。CART回归树是后续强大的提升树算法的基础。

以上是决策树基本思想，以下决策树进阶用法，也是目前广泛使用的方法。

# 集成学习

对于上述决策树的缺点，很多改善方法都是使用集成学习 Ensemble learning 。集成方法有以下几种：

Bagging ：使用不同的训练数据集来训练多个基本模型，然后对其预测结果进行投票或平均，以减小模型的方差。适用于高方差的模型，如决策树。
Boosting ：顺序训练多个基本模型，每个模型都试图修复前一个模型的错误。最终将所有模型的预测结果进行加权组合。适用于弱模型，降低偏差，通过提升准确率以改进其性能，因此叫Boosting。
Stacking ：将多个不同类型的基本模型的预测结果作为输入，再使用另一个模型（元模型）来融合这些预测结果。适用于多样性强的模型组合。然而需要仔细设计和调整，避免过拟合。
Voting ：将多个基本模型的预测结果进行投票，选择获得最多票数的类别或平均预测结果。适用于多个相对独立的模型组合。基本模型之间应有一定差异，以确保投票的效果。
Blending ：将训练数据划分为多个部分，用不同的基本模型在这些部分上训练，然后在另一个独立的验证集上训练元模型。适用于数据量充足的情况，可用于解决过拟合问题。

其中，前两者方法有一系列优秀的例子在竞赛中特别常见。如随机森林 Bagging ，GBDT Boosting ，XGBoost Boosting ，LightGBM Boosting ，AdaBoost Boosting 等。

装袋法 Bagging 与提升法 Boosting 的比较：

	Bagging	Boosting
弱学习器	相互独立，并行构建	相互关联，按顺序构建先建立的弱学习器预测效果影响后续模型的建立
抽样方式	样本有放回抽样特征无放回抽样	样本有放回抽样特征无放回抽样先建的弱学习器预测效果可能影响抽样细节
集成结果	回归：取平均值分类：树投票	每个算法不同，一般来说： (1)表现为某种分数的加权平均 (2)使用输出函数，如softmax, sigmoid
目标	降低方差提高泛化能力，本质是从“平均”这一数学行为中获利	降低偏差提高准确度以提升泛化能力众多弱学习器关联起来后等同于强学习器
单个学习器过拟合时	具有一定抗过拟合的能力	具有一定抗过拟合的能力
单个学习器效力较弱时	可能失效	大概率提升模型表现
代表算法	随机森林	GBDT, XGBoost, CATBoost, LightGBM

来自菜菜TsaiTsai

构建多棵决策树

所谓集成树模型，就是构建多棵树，以实现降方差或降偏差的效果。

如决策树缺点二中提到，单棵决策树会因为训练样本的微小变化而使得树结构发生剧烈改变。该缺点可以通过构建多棵决策树来改善(构建不同决策树的训练集从何而来？请参考重置抽样)。每一棵树会输出一个结果，通过这些树的结果来投票以获得更可靠的结果，进而提升模型的健壮性。

如上图所示，三个决策树输出的结果为两个1，一个0。由于1的结果比0多，因此投票得最终结果为1。

重置抽样

该抽样方法也被称为有放回的抽样 Sampling With Replacement ，是集成树算法的关键技术之一。

在样本量为m的训练集中重置抽样 B 次，每次抽m个样本，这样最多可以获得 B 个样本量为m的似是而非的不同训练集。每个训练集中包含部分重复的样本并且没有包括原始训练集中的所有样本是正常的。

注：重置抽样的次数越多，算法效果越好，先抽100次构建100棵树。然而高于某阈值时再扩大重置抽样规模带来的效益将不及算法耗时增长带来的损失。

# 随机森林

重置抽样以构建多棵决策树并选取最多次输出的结果作为最终结果的思想 Bagging decision trees 固然很好，然而在实践过程中，构建的多棵决策树的根节点以及根节点附近的节点可能几乎一致，这对算法的效果并无益处。接下来介绍的本帖中第一个集成算法——随机森林 Random Forest 将很好地避免这一问题。

随机森林之于前者的改进是，每次选择节点时仅在 n 个特征中的子集—— k 个随机特征中进行选择，其中 k<n 。对于 n>10 时，推荐取 k=sqrt(n) 。

因此，综上所述，随机森林的随机不仅体现在随机样本组成的训练集，更体现在每次决定节点时只选取 k, k<n 个特征而不是全部特征。这使得随机森林更健壮，因为算法探索并平均数据的微小更改带来的影响。

# Boosting

本章节主要目的是介绍 XGBoost ，然而该算法的思想与之前的装袋法大相径庭，因此对基础思想的介绍必不可少。本章节顺序：Boosting -> AdaBoost -> 提升树 -> GBDT -> XGBoost

上文提到在 Boosting 中每个模型都试图修复前一个模型的错误。通过实践理解，这句话的意思是第一次通过训练集中所有样本构建一棵树，然后在该样本中进行预测，找到错误分类的样本。之后的含有m个随机样本的训练集通过重置抽样获得，而重置抽样时会提高上一次错误分类的样本的概率(或是提高权重)。就像人类刻意学习某个不熟悉的地方。

降低偏差、按顺序构建弱学习器、以独特规则输出结果是Boosting算法的三大基本元素：

加法模型的损失函数 L(y, H(x)) : 衡量模型单个预测结果与真实结果之间的差异，在回归任务中可以考虑MSE均方误损失函数；在分类任务中，二分类可以考虑指数损失函数(常用)、交叉熵损失等，多分类任务可以考虑使用Softmax Loss(网上查询定义)。也可以自定义损失函数
弱学习器 h(x) : 可以为任意算法，但一般为决策树。不同Boosting算法拥有不同建树流程。每个弱学习器有自己的训练方法，比如LR模型结合交叉熵损失与梯度下降来训练。
综合集成结果 H(x) : 即集成算法具体如何输出集成结果，也是自适应提升算法的假设函数(加法模型)，有自己的优化方法——前向分步算法或梯度下降算法等

以上三者元素将贯穿所有Boosting算法，算法基于这三者按以下流程建模：①依据上一个弱学习器 h(x)_t-1 的结果，计算代价函数 Cost(y, H(x)) ；②代价函数自适应地影响下一个弱学习器的 h(x)_t 构建；③集成模型的输出结果受所有弱学习器 h(x)₁~h(x)_T 的影响。

# AdaBoost

自适应提升 Adaptive Boosting 是将Boosting发扬光大的第一个算法，后续梯度提升等算法的思想均来自于此。它的主要贡献在于：①首次实现根据之前弱学习器的结果自适应影响后续建模过程；②在Boosting算法中，首次实现考虑全部弱学习器结果的输出方式。 H(x) 输出所有弱学习器的加权平均值，边建树边计算。加权值指树的权重，在建树过程中被自动计算。

上文中，“第一次通过训练集中所有样本构建一棵树，然后在该样本中进行预测，找到错误分类的样本。之后的含有m个随机样本的训练集通过重置抽样获得，而重置抽样时会提高上一次错误分类的样本的概率”——这一思想就来自 AdaBoost 。

该算法属于加法模型

AdaBoost 属于加法模型。根据加法模型的一般形式，得到AdaBoost的假设函数：

其中， T 是所有弱学习器的个数； α_t 是第t个弱学习器的权重； h_t() 是第t个弱学习器； γ_t 是第t个弱学习器的参数。

对于该假设函数，优化算法一般采取前向分步算法最小化损失值(损失函数按任务或目标变量类型确定)并更新弱学习器权重与弱学习器参数(每个弱学习器通过自身的训练方法得到参数)，而不是梯度下降算法，因为树模型函数不连续，求导没有意义。结合前向分步算法最小化加法模型损失值并更新参数的过程如下：

(1)初始化 H₀(x)=0

(2)经过t=1,2,3,…,T次迭代，每一次都最小化代价函数，得到第t个模型的权重 α_t 和第t个模型的参数 γ_t (通过拟合训练样本最小化误差得)，并将计算得到的损失值用于下一次循环的训练样本权重的计算：

其中， α_t 是计算得第t个弱学习器的权重Amount of Say； h_t-1() 是第t-1个弱学习器； γ_t 是计算得第t个弱学习器的参数； m 为训练样本量。

(3)每次迭代均更新假设函数：

以上是 AdaBoost 算法的假设函数和优化方法。接下里将在算法完整流程中讲解如何更新样本权重与计算弱学习器权重。

算法流程-分类任务

1.获得数据集

算法的原始思想仅用于处理二元分类，因此明确训练样本中目标变量仅含1与-1，分别代表正例与负例。训练集中共m个样本。

2.定义弱学习器

可以为任意算法，但一般为决策树。每个弱学习器(假设函数)有自己的训练方法，比如LR模型结合交叉熵损失与梯度下降来训练。

3.循环T次

3.1 第一次时，初始化当前数据的权重：

第一次将每一个样本的权重 w₁₁ , w₁₂ … w_1m 赋值为 1/m ，m为样本量，即初始化样本权重。

3.2 训练当前循环次数的弱学习器：

不同弱学习器有不同训练方法，如LR结合均方误差与梯度下降进行训练。总之使得每个弱学习器效果最佳，误差率最小。

3.3 计算当前循环次数(t次)的弱学习器的权重 α_t ：

式中， e_t 为第t个弱学习器在训练集上的分类误差率； w_ti 是第t次循环中第i个训练样本的权重。

3.4 将本次(第t次)循环得到的弱学习器及其权重添加到假设函数中：

3.5 判断是否退出循环：

弱学习器个数达到预设值，则停止；该算法误差率小于设定值，如误差率〇，则停止(更常用)。

3.6 本次为第t次循环，若进行下一次循环(t+1)，则更新训练样本的权重 w_t+1,i ：将损失函数视为训练样本的权重 w_ti=exp(-y_iH_t-1(x_i)) 推导得以下权重更新公式。

式中， w_t,i 为第t次(本次)第i个训练样本的权重； w_t+1,i 为第t+1次(下一次)第i个训练样本的权重； Z_t 用于归一化； m 为总训练样本量。

算法流程-回归任务

在回归任务上AdaBoost有诸多变种，本节采用 sklearn 实现的AdaBoost.R2为例，讲解该算法在回归任务上的运用。

1.获得数据集

训练集中共m个样本，目标变量为连续值。

2.定义弱学习器

可以为任意算法，但一般为决策树。每个弱学习器(假设函数)有自己的训练方法，比如线性回归结合均方误与梯度下降来训练。

3.循环T次

3.1 第一次时，初始化当前数据的权重：

第一次将每一个样本的权重 w₁₁ , w₁₂ … w_1m 赋值为 1/m ，m为样本量，即初始化样本权重。

3.2 训练当前循环次数的弱学习器：

不同弱学习器有不同训练方法。

3.3 计算当前循环次数(t次)的弱学习器的权重 α_t ：

式中， e_ti 为第t次循环第i个样本的相对误差； E_t 为第t次循环训练集上最大的误差； e_t 为第t个学习器的误差； a_t 为第t个弱学习器的权重。

3.4 更新下一次循环的样本权重：

式中， w_t+1,i 为第t+1次(下一次)循环第i个样本的权重； e_ti 为第t次循环第i个样本的相对误差； a_t 为第t个弱学习器的权重； w_t,i 为第t次(该次)循环第i个样本的权重。

3.5 得到最终的强学习器：

式中， T 为总循环次数，也为总弱学习器个数； h_t() 为第t个弱学习器函数。

由于 h_t() 为回归树，原论文指出，AdaBoost.R2的回归树(弱学习器)输出的是叶节点的中位数，而不是平均数。这是作者较为主观的选择。

代码实现

在 sklearn 中，相关代码如下：

# 分类
sklearn.ensemble.AdaBoostClassifier(estimator=None, *, n_estimators=50, learning_rate=1.0, algorithm='SAMME.R', random_state=None, base_estimator='deprecated')
# 回归
sklearn.ensemble.AdaBoostRegressor(estimator=None, *, n_estimators=50, learning_rate=1.0, loss='linear', random_state=None, base_estimator='deprecated')
参数详查https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostRegressor.html
# 查看学习器类型
adaboost_classifier = sklearn.ensemble.AdaBoostClassifier(estimator=None, *, n_estimators=50, learning_rate=1.0, algorithm='SAMME.R', random_state=None, base_estimator='deprecated')
adaboost_classifier.base_estimator_
adaboost_classifier.estimators_
# 自建弱学习器
base_est = sklearn.tree.DecisionTreeClassifier(max_depth=10, max_features=30)

在estimator方面，分类时为默认深度为1的决策树，回归时为默认深度为3的决策树(原算法也默认为1，然而回归更复杂，因此在sklearn中默认为3)。因为Boosting算法集成多个弱学习器成为一个强学习器。显然深度这么低的决策树无法在Bagging算法中作为基础弱学习器。

注：AdaBoost执行分类任务时弱学习器为分类树，执行回归任务时弱学习器为回归树。而之后的GBDT、XGBoost的弱学习器均为回归树。

# GBDT

一般提升树

基于集成学习提升法的集合树称为提升树，AdaBoost、GBDT、XGBoost等均为提升树。然而AdaBoost注重于错分类的样本并改变样本权重与弱学习器权重以获得最小加法模型的损失；GBDT是更通用的模型，其中包括AdaBoost作为特例，其思想是第一次使用回归树拟合所有样本，第一次之后的弱学习器拟合上一次迭代后整体提升树(加法模型)损失函数的负梯度(可以理解为残差Residual)，在该模型中弱学习器权重均为1；而XGBoost是GBDT的改进版本，保留了GBDT的思想，引入了一系列改进，如权重不再固定为1，加入正则化项和特征选择等。

结合提升法的内容来看，提升树的假设函数为加法模型：

其损失函数视具体应用而定，具体而言：回归任务选择均方误损失函数；分类任务选择指数损失函数、交叉熵损失函数、Softmax Loss函数；一般性决策任务可以选择自定义损失函数。提升树的优化方法为前向分步算法：

实际上是通过最小化决策树拟合训练样本时的误差来确定参数 γ_t ，这一步在最小化加法模型的损失时进行。并且，得到的损失值将用于下一次循环训练样本权重的计算。

分类任务下的提升树

在分类任务下，提升树的弱学习器为深度为1的分类树；损失函数选取指数损失函数。分类任务下的提升树除了弱学习器权重全设为1并且不更新弱学习器权重外(照样更新样本权重)，其算法流程几乎与AdaBoost分类流程一致。

注：只要损失函数使用的是指数损失函数，就可以按AdaBoost分类提到的方法更新样本的权重。

回归任务下的提升树

在回归任务下，提升树的弱学习器为回归树；损失函数选取均方误差损失函数。提升树在回归任务下清楚地展示了为什么弱学习器拟合的是上一次迭代后加法模型拟合数据的残差。

回归任务下提升树的假设函数如下所示：

其中，弱学习器为CART回归树，弱学习器的公式如下所示：

假设函数的损失函数与优化目标如下所示：

再将新的弱学习器与假设函数相加得到提升树的假设函数。再用新的假设函数计算残差进行下一轮拟合。

GBDT为一般任务下的提升树的实现方式

在梯度提升树 Gradient Boosting Decision Tree 中，提升指的是提升树：在GBDT中每一次弱学习器拟合的是上一次迭代后加法模型拟合数据的残差；梯度指加法模型损失函数的负梯度： 用该负梯度代替加法模型拟合数据的残差 (原因)。因此，在GBDT初始化假设函数之后，之后每一次的弱学习器拟合的都是前一次迭代后加法模型损失函数在每个数据点的负梯度。后者由泰勒展开得来。

GBDT不更新样本的权重，因为每一次拟合的都是上一次迭代后加法模型的损失函数在每个数据点的负梯度。此外，当GBDT不健壮时，可以在建树时允许像随机森林一样对样本与特征进行抽样，以降低算法方差；为防止过拟合，GBDT内每个弱学习器带有学习率。

算法流程-回归任务

以下范式基于Friedman提出的改进算法TreeBoost。

1.获得数据集

训练集有m个训练样本，目标变量为连续型变量。

2.定义弱学习器

在GBDT中弱学习器为CART回归树。

3.初始化假设函数

首先将GBDT的假设函数初始化为一个常数，这与AdaBoost中初始化为〇不同。式中， m 是训练样本量。L是均方误损失函数。初始化会得到训练样本目标变量的均值作为初始化常数，因为该值会使得整体代价函数最小。

4.循环T次

(a)中伪残差是第t-1次循环后得到的假设函数的损失函数在每个数据点的负梯度，下一个弱学习器将拟合该负梯度；每个弱学习器还有一个超参数学习率 ν ，学习率通常设为0.1再微调。值得注意的是，在最后一步更新加性模型时才给新的弱学习器赋上学习率，在拟合弱学习器时不需要赋学习率； c_tj 为弱学习器回归树的叶节点输出值，在回归任务中为该叶节点中样本目标变量的平均值，看这里更好理解。

算法流程-分类任务-二分类

由于每个弱学习器均为回归树，而训练样本的目标变量为离散型变量，因此算法初始化及残差的计算需要引入 log(odds) 。

1.获得数据集

训练集有m个训练样本，目标变量为离散型变量。

2.定义弱学习器

在GBDT中弱学习器为CART回归树。

3.初始化假设函数

首先将GBDT的假设函数初始化为一个常数。式中， m 是训练样本量。L是交叉熵损失函数。log(odds)为对数优势比，是正例的占比除以负例的占比取对数。初始化时该对数优势比为训练样本中正例的占比除以负例的占比取对数。

4.循环T次

假设函数输出的是对数优势比，若想得到预测为正例的概率，还应进行以下计算：

初始化假设函数对所有样本的预测为正例的概率为p，以此得到第一次循环拟合的残差：真实值概率(正例为1负例为0)与预测概率的残差residual。新的回归树遵从回归树建树原则拟合这些残差。每个叶节点会包含一个及以上的残差，此时，回归树的输出不再是取叶节点的平均值，而是以下述公式进行输出：

式中， c_tj 是第t棵树第j个叶节点的输出值；分子为第t棵树第j个叶节点中所有样本的残差和； p_t-1,i 是第i个样本上一次迭代后预测为正例的概率。

按照以下公式更新第t+1次的训练样本：

然后按照上述步骤继续循环。虽然直观感受伪残差通过观测值(0或1)与预测值(正例的概率)相减获得，实际上这一步也是通过回归任务中的(a)步骤推导而来。每一次迭代时，获取将要拟合的残差作为新的训练样本实际上为第一步。

# XGBoost

在诸多提升树里，极限梯度提升树 XGBoost 最为常用。 XGBoost 在竞赛获奖名单中比随机森林更常见，近年来也在学术界也得到了广泛地运用。

尽管按照惯例，XGBoost不会仅在一部分随机特征中选择节点，然而可以通过设置参数来调整。

以下代码实现通过 XGBoost 进行分类：

from xgboost import XGBClassifier
model = XGBClassifier()
model.fit(X_train, y_train)
y_pred = model.predict(X_test)

以下代码实现通过 XGBoost 进行回归：

from xgboost import XGBRegressor
model = XGBRegressor()
model.fit(X_train, y_train)
y_pred = model.predict(X_test)

注：极限梯度提升树 XGBoost 是梯度提升决策树 GBDT 算法的改进版本。它通过引入一些优化和功能来增强GBDT方法，例如更高效的并行计算框架、正则化技术以及更有效地处理缺失数据。这通常会比传统的GBDT产生更好的预测性能和更快的训练时间。

# 决策树(及集成树)vs神经网络

决策树对结构化(表格)数据非常擅长，而神经网络不仅擅长结构化数据，还擅长非结构化数据(图像、文本、语音)。
决策树训练得很快，神经网络训练得慢。
人类可以理解小型决策树的决策过程。
通过迁移学习或其他方法，能够把多个大型神经网络串起来。这比串联决策树更容易。

决策树的优缺点参考上文。

# GBDT中负梯度为什么能代替残差

在梯度提升树中，负梯度实际上是在代表残差的方向上进行优化的一种方法。虽然我们通常称之为负梯度，但在这个上下文中，它实际上代表了目标函数的负梯度，或者说是损失函数的负梯度。

损失函数最小化：GBDT 是一种迭代集成学习方法，旨在通过将弱学习器（决策树）顺序拟合到损失函数的负梯度来构建加性模型。损失函数的负梯度指向最速下降的方向，这意味着它引导算法向减少损失函数的方向移动。通过拟合负梯度，GBDT 有效地最小化了残差。
残差解释：负梯度代表损失函数下降最快的方向。由于损失函数量化的是预测值和实际值（残差）之间的差异，因此使用负梯度符合减少这些差异的目标。实质上，负梯度表示预测值需要调整多少才能更接近真实目标值，这与调整残差类似。
方向性：负梯度的方向与残差的方向是一致的。当我们在某个点计算损失函数的负梯度时，实际上是在该点计算了损失函数的局部下降方向。这个方向告诉我们如果希望减小损失，应该朝着负梯度的方向调整预测值。由于残差也是预测值与实际值之间的差异，因此负梯度的方向也与残差方向一致。
提升过程：在GBDT中，提升过程涉及在每次迭代中将新的决策树拟合到损失函数的负梯度上。这个决策树被称为弱学习器，它被构建来预测前一次迭代的负梯度（或等效地，残差）。随着每棵新树的添加，整个集成逐渐减小了先前集成所产生的误差，从而有效地降低了残差误差。
迭代优化：GBDT的迭代过程涉及逐步改进模型的预测。通过关注负梯度，算法有系统地纠正了前一轮树没有很好捕捉到的残差。这导致了一个累加模型，每个后续的弱学习器都处理剩余的误差，实际上是用负梯度取代了残差。