决策树

决策树是一个非常常见并且优秀的机器学习算法，它易于理解、可解释性强，其可作为分类算法，也可用于回归模型。

1. ID3

ID3 算法是建立在奥卡姆剃刀（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树。

1.1 思想

从信息论的知识中我们知道：信息熵越大，从而样本纯度越低，。ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：

1. 初始化特征集合和数据集合；
2. 计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3. 更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4. 重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。

1.2 划分标准

ID3 使用的分类标准是信息增益，它表示得知特征 $A$ 的信息而使得样本集合不确定性减少的程度。

数据集的信息熵：

$$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|} \$$

其中 $C_k$ 表示集合 $D$ 中属于第 $k$ 类样本的样本子集。

针对某个特征 $A$，对于数据集 $D$ 的条件熵 $H(D|A)$ 为：

$$\begin{aligned} H(D|A) & = \sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i) \ & =- \sum_{i=1}^{n}\frac{|D_i|}{|D|}(\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}) \ \end{aligned} \$$

其中 $D_i$ 表示 $D$ 中特征 $A$ 取第 $i$ 个值的样本子集， $D_{ik}$ 表示 $D_i$ 中属于第 $k$ 类的样本子集。

信息增益 = 信息熵 - 条件熵：

$$Gain(D,A)=H(D)-H(D|A) \$$

信息增益越大表示使用特征 $A$ 来划分所获得的“纯度提升越大”。

1.3 缺点

• ID3 没有剪枝策略，容易过拟合；
• 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
• 只能用于处理离散分布的特征；
• 没有考虑缺失值。

2. C4.5

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。

2.1 思想

C4.5 相对于 ID3 的缺点对应有以下改进方式：

• 引入悲观剪枝策略进行后剪枝；
• 引入信息增益率作为划分标准；
• 将连续特征离散化，假设 $n$ 个样本的连续特征 $A$ 有 $m$ 个取值，C4.5 将其排序并取相邻两样本值的平均数共 $m$ -1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
• 对于缺失值的处理可以分为两个子问题：
• 问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
• 问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
• 针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
• 针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

2.2 划分标准

利用信息增益率可以克服信息增益的缺点，其公式为

$$\begin{aligned} Gain_{ratio}(D,A)&=\frac{Gain(D,A)}{H_A(D)} \ H_A(D) &=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|} \end{aligned} \$$

$H_A(D) $ 称为特征 $A$ 的固有值。

这里需要注意，信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。

2.3 剪枝策略

为什么要剪枝：过拟合的树在泛化能力的表现非常差。

2.3.1 预剪枝

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

• 节点内数据样本低于某一阈值；
• 所有节点特征都已分裂；
• 节点划分前准确率比划分后准确率高。

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

2.3.2 后剪枝

在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

2.4 缺点

• 剪枝策略可以再优化；
• C4.5 用的是多叉树，用二叉树效率更高；
• C4.5 只能用于分类；
• C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
• C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

3. CART

ID3 和 C4.5 虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但是其生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。

3.1 思想

CART 包含的基本过程有分裂，剪枝和树选择。

• **分裂：**分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
• 剪枝：采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
• **树选择：**用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

CART 在 C4.5 的基础上进行了很多提升。

• C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
• C4.5 只能分类，CART 既可以分类也可以回归；
• CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
• CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
• CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

3.2 划分标准

熵模型拥有大量耗时的对数运算，基尼指数在简化模型的同时还保留了熵模型的优点。基尼指数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（率）正好相反。

$$\begin{aligned} Gini(D)&=\sum_{k=1}^{K}\frac{|C_k|}{|D|}(1-\frac{|C_k|}{|D|}) \ &=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2 \ Gini(D|A) &= \sum_{i=1}^{n}\frac{|D_i|}{|D|}Gini(D_i) \end{aligned} \$$

其中 $k$ 代表类别。

基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越小，则数据集纯度越高。基尼指数偏向于特征值较多的特征，类似信息增益。基尼指数可以用来度量任何不均匀分布，是介于 0~1 之间的数，0 是完全相等，1 是完全不相等，

此外，当 CART 为二分类，其表达式为：

$$Gini(D|A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) \$$

我们可以看到在平方运算和二分类的情况下，其运算更加简单。当然其性能也与熵模型非常接近。

那么问题来了：基尼指数与熵模型性能接近，但到底与熵模型的差距有多大呢？

我们知道 $ln(x) = -1+x +o(x)$ ，所以

$$\begin{aligned} H(X)&=-\sum_{k=1}^{K} p_{k} \ln p_{k}\&\approx \sum_{k=1}^{K} p_{k}\left(1-p_{k}\right) \end{aligned} \$$

我们可以看到，基尼指数可以理解为熵模型的一阶泰勒展开。这边在放上一张很经典的图：

3.3 缺失值处理

上文说到，模型对于缺失值的处理会分为两个子问题：

1. 如何在特征值缺失的情况下进行划分特征的选择？
2. 选定该划分特征，模型对于缺失该特征值的样本该进行怎样处理？

对于问题 1，CART 一开始严格要求分裂特征评估时只能使用在该特征上没有缺失值的那部分数据，在后续版本中，CART 算法使用了一种惩罚机制来抑制提升值，从而反映出缺失值的影响（例如，如果一个特征在节点的 20% 的记录是缺失的，那么这个特征就会减少 20% 或者其他数值）。

对于问题 2，CART 算法的机制是为树的每个节点都找到代理分裂器，无论在训练数据上得到的树是否有缺失值都会这样做。在代理分裂器中，特征的分值必须超过默认规则的性能才有资格作为代理（即代理就是代替缺失值特征作为划分特征的特征），当 CART 树中遇到缺失值时，这个实例划分到左边还是右边是决定于其排名最高的代理，如果这个代理的值也缺失了，那么就使用排名第二的代理，以此类推，如果所有代理值都缺失，那么默认规则就是把样本划分到较大的那个子节点。代理分裂器可以确保无缺失训练数据上得到的树可以用来处理包含确实值的新数据。

3.4 剪枝策略

采用一种“基于代价复杂度的剪枝”方法进行后剪枝，这种方法会生成一系列树，每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的，这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。这种方法需要使用一个单独的测试数据集来评估所有的树，根据它们在测试数据集熵的分类性能选出最佳的树。

我们来看具体看一下代价复杂度剪枝算法：

首先我们将最大树称为 $T_0$ ，我们希望减少树的大小来防止过拟合，但又担心去掉节点后预测误差会增大，所以我们定义了一个损失函数来达到这两个变量之间的平衡。损失函数定义如下：

$$C_\alpha(T)=C(T)+\alpha|T| \$$

$T$ 为任意子树， $C(T)$ 为预测误差， $|T|$ 为子树 $T$ 的叶子节点个数， $\alpha$ 是参数， $C(T)$ 衡量训练数据的拟合程度， $|T|$ 衡量树的复杂度， $\alpha$ 权衡拟合程度与树的复杂度。

那么如何找到合适的 $\alpha$ 来使得复杂度和拟合度达到最好的平衡点呢，最好的办法就是另 $\alpha$ 从 0 取到正无穷，对于每一个固定的 $\alpha$ ，我们都可以找到使得 $C_\alpha(T)$ 最小的最优子树 $T(\alpha)$ 。当 $\alpha $ 很小的时候， $T_0$ 是最优子树；当 $\alpha$ 最大时，单独的根节点是这样的最优子树。随着 $\alpha$ 增大，我们可以得到一个这样的子树序列： $T_0, T_1, T_2, T_3, … ,T_n$ ，这里的子树 $T_{i+1}$ 生成是根据前一个子树 $T_i$ 剪掉某一个内部节点生成的。

Breiman 证明：将 $\alpha$ 从小增大， $0=\alpha_0<\alpha_0<…<\alpha_n<\infty$ ，在每个区间 $[\alpha_i,\alpha_{i+1})$ 中，子树 $T_i$ 是这个区间里最优的。

这是代价复杂度剪枝的核心思想。

我们每次剪枝都是针对某个非叶节点，其他节点不变，所以我们只需要计算该节点剪枝前和剪枝后的损失函数即可。

对于任意内部节点 t，剪枝前的状态，有 $|T_t|$ 个叶子节点，预测误差是 $C(T_t)$ ；剪枝后的状态：只有本身一个叶子节点，预测误差是 $C(t)$ 。

因此剪枝前以 t 节点为根节点的子树的损失函数是：

$$C_\alpha(T)=C(T_t)+\alpha|T| \$$

剪枝后的损失函数是

$$C_\alpha(t) = C(t)+\alpha \$$

通过 Breiman 证明我们知道一定存在一个 $\alpha$ 使得 $C_\alpha(T)=C_\alpha(t)$ ，使得这个值为：

$$\alpha = \frac{C(t)-C(T_t)}{|T_t|-1} \$$

$\alpha$ 的意义在于， $[\alpha_i,\alpha_{i+1})$ 中，子树 $T_i$ 是这个区间里最优的。当 $\alpha$ 大于这个值是，一定有 $C_\alpha(T)>C_\alpha(t)$ ，也就是剪掉这个节点后都比不剪掉要更优。所以每个最优子树对应的是一个区间，在这个区间内都是最优的。

然后我们对 $T_i$ 中的每个内部节点 t 都计算：

$$g(t) = \frac{C(t)-C(T_t)}{|T_t|-1} \$$

$g(t)$ 表示阈值，故我们每次都会减去最小的 $T_t$ 。

3.5 类别不平衡

CART 的一大优势在于：无论训练数据集有多失衡，它都可以将其子冻消除不需要建模人员采取其他操作。

CART 使用了一种先验机制，其作用相当于对类别进行加权。这种先验机制嵌入于 CART 算法判断分裂优劣的运算里，在 CART 默认的分类模式中，总是要计算每个节点关于根节点的类别频率的比值，这就相当于对数据自动重加权，对类别进行均衡。

对于一个二分类问题，节点 $n$ ode 被分成类别 1 当且仅当：

$$\frac{N_1(node)}{N_1(root)} > \frac{N_0(node)}{N_0(root)} \$$

比如二分类，根节点属于 1 类和 0 类的分别有 20 和 80 个。在子节点上有 30 个样本，其中属于 1 类和 0 类的分别是 10 和 20 个。如果 10/20>20/80，该节点就属于 1 类。

通过这种计算方式就无需管理数据真实的类别分布。假设有 $k$ 个目标类别，就可以确保根节点中每个类别的概率都是 1/K。这种默认的模式被称为“先验相等”。

先验设置和加权不同之处在于先验不影响每个节点中的各类别样本的数量或者份额。先验影响的是每个节点的类别赋值和树生长过程中分裂的选择。

3.6 回归树

CART（Classification and Regression Tree，分类回归树），从名字就可以看出其不仅可以用于分类，也可以应用于回归。其回归树的建立算法上与分类树部分相似，这里简单介绍下不同之处。

3.6.1 连续值处理

对于连续值的处理，CART 分类树采用基尼系数的大小来度量特征的各个划分点。在回归模型中，我们使用常见的和方差度量方式，对于任意划分特征 A，对应的任意划分点 s 两边划分成的数据集 $D_1$ 和 $D_2$ ，求出使 $D_1$ 和 $D_2$ 各自集合的均方差最小，同时 $D_1$ 和 $D_2$ 的均方差之和最小所对应的特征和特征值划分点。表达式为：

$$ \min\limits_{a,s}\Bigg[\min\limits_{c_1}\sum\limits_{x_i \in D_1}(y_i - c_1)^2 + \min\limits_{c_2}\sum\limits_{x_i \in D_2}(y_i - c_2)^2\Bigg] \$$

其中， $c_1$ 为 $D_1$ 数据集的样本输出均值， $c_2$ 为 $D_2$ 数据集的样本输出均值。

3.6.2 预测方式

对于决策树建立后做预测的方式，上面讲到了 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

4. 随机森林

随机森林（Random Forest），用随机的方式建立一个森林。RF 算法由很多决策树组成，每一棵决策树之间没有关联。建立完森林后，当有新样本进入时，每棵决策树都会分别进行判断，然后基于投票法给出分类结果。

4.1 思想

随机森林是 Bagging 的扩展变体，它在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括 RF 包括四个部分：

1. 随机选择样本（放回抽样）:如果训练集大小为 $N$，对于每棵树而言，随机且有放回地从训练集中的抽取 $N$ 个训练样本（这种采样方式称为bootstrap sample方法），作为该树的训练集；

每棵树的训练集都是不同的，而且里面包含重复的训练样本。

• 为什么要随机抽样训练集：如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；
• 为什么要有放回地抽样：如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是”有偏的”，都是绝对”片面的”，也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是”求同”，所以说使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是”盲人摸象”。

2. 随机选择特征: 如果每个样本的特征维度为 $M$，指定一个常数 $m<<M$，随机地从 $M$ 个特征中选取 $m$ 个特征子集，每次树进行分裂时，从这 $m$ 个特征中选择最优的；

减小特征选择个数 $m$，树的相关性和分类能力也会相应的降低；增大 $m$ ，两者也会随之增大。所以关键是如何选择最优的 $m$（或者是范围），这也是随机森林唯一的一个参数。

3. 构建决策树: 每棵树都尽最大程度的生长，并且没有剪枝过程

4. 随机森林投票（平均）。

随机森林分类效果（错误率）与两个因素有关：

• 森林中任意两棵树的相关性：相关性越大，则错误率越大；
• 森林中每棵树的分类能力：每棵树的分类能力越强，则整个森林的错误率就越低。

4.2 优缺点

优点

1. 在数据集上表现良好，相对于其他算法有较大的优势
2. 易于并行化，在大数据集上有很大的优势；
3. 能够处理高维度数据，不用做特征选择。

5 Adaboost

AdaBoost（Adaptive Boosting，自适应增强），其自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

5.1 思想

Adaboost 迭代算法有三步：

1. 初始化训练样本的权值分布，每个样本具有相同权重；
2. 训练弱分类器，如果样本分类正确，则在构造下一个训练集中，它的权值就会被降低；反之提高。用更新过的样本集去训练下一个分类器；
3. 将所有弱分类组合成强分类器，各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，降低分类误差率大的弱分类器的权重。

5.2 细节

5.2.1 损失函数

Adaboost 模型是加法模型，学习算法为前向分步学习算法，损失函数为指数函数的分类问题。

加法模型：最终的强分类器是由若干个弱分类器加权平均得到的。

前向分布学习算法：算法是通过一轮轮的弱学习器学习，利用前一个弱学习器的结果来更新后一个弱学习器的训练集权重。第 k 轮的强学习器为：

$$ F_{k}(x)=\sum_{i=1}^{k}\alpha_i f_i(x)=F_{k-1}(x)+\alpha_{k}f_k(x) \$$

定义损失函数为 n 个样本的指数损失函数：

$$L(y,F) = \sum_\limits{i=1}^{n}exp(-y_iF_{k}(x_i)) \$$

利用前向分布学习算法的关系可以得到：

$$\begin{align} L(y, F) &= \sum_\limits{i=1}^{m}exp[(-y_i) (F_{k-1}(x_i) + \alpha_k f_k(x_i))] \ &= \sum_\limits{i=1}^{m}exp[-y_i F_{k-1}(x_i) -y_i \alpha_k f_k(x_i)] \ &= \sum_\limits{i=1}^{m}exp[-y_i F_{k-1}(x_i) ] exp[-y_i \alpha_k f_k(x_i)] \end{align} \$$

因为 $F_{k-1}(x)$ 已知，所以令 $w_{k,i} = exp(-y_iF_{k-1}(x_i))$ ，随着每一轮迭代而将这个式子带入损失函数，损失函数转化为：

$$L(y, F(x)) =\sum_\limits{i=1}^{m}w_{k,i}exp[-y_i\alpha_k f_k(x_i)] \$$

我们求 $f_k(x)$ ，可以得到：

$$f_k(x) =argmin; \sum_\limits{i=1}^{m}w_{k,i}I(y_i \neq f_k(x_i)) \$$

将 $f_k(x)$ 带入损失函数，并对 $\alpha$ 求导，使其等于 0，则就得到了：

$$ \alpha_k = \frac{1}{2}log\frac{1-e_k}{e_k} \$$

其中， $e_k$ 即为我们前面的分类误差率。

$$ e_k = \frac{\sum\limits_{i=1}^{m}w_{ki}^{’}I(y_i \neq f_k(x_i))}{\sum\limits_{i=1}^{m}w_{ki}^{’}} = \sum\limits_{i=1}^{m}w_{ki}I(y_i \neq f_k(x_i)) \$$

最后看样本权重的更新。利用 $F_{k}(x) = F_{k-1}(x) + \alpha_kf_k(x)$ 和 $w_{k+1,i}=w_{k,i}exp[-y_i\alpha_kf_k(x,i)]$ ，即可得：

$$w_{k+1,i} = w_{ki}exp[-y_i\alpha_kf_k(x_i)] \$$

这样就得到了样本权重更新公式。

5.2.2 正则化

为了防止 Adaboost 过拟合，我们通常也会加入正则化项，这个正则化项我们通常称为步长（learning rate）。对于前面的弱学习器的迭代

$$F_{k}(x) = F_{k-1}(x) + \alpha_kf_k(x) \$$

加上正则化项 $\mu $ 我们有：

$$F_{k}(x) = F_{k-1}(x) + \mu\alpha_kf_k(x) \$$

$\mu$ 的取值范围为 $0<\mu\leq1$ 。对于同样的训练集学习效果，较小的 $\mu$ 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

5.3 优缺点

5.3.1 优点

1. 分类精度高；
2. 可以用各种回归分类模型来构建弱学习器，非常灵活；
3. 不容易发生过拟合。

5.3.2 缺点

1. 对异常点敏感，异常点会获得较高权重。

6. GBDT

GBDT（Gradient Boosting Decision Tree）是一种迭代的决策树算法，该算法由多棵决策树组成，从名字中我们可以看出来它是属于 Boosting 策略。GBDT 是被公认的泛化能力较强的算法。

6.1 思想

GBDT 由三个概念组成：Regression Decision Tree（即 DT）、Gradient Boosting（即 GB），和 Shrinkage（一个重要演变）

6.1.1 回归树（Regression Decision Tree）

如果认为 GBDT 由很多分类树那就大错特错了（虽然调整后也可以分类）。对于分类树而言，其值加减无意义（如性别），而对于回归树而言，其值加减才是有意义的（如说年龄）。GBDT 的核心在于累加所有树的结果作为最终结果，所以 GBDT 中的树都是回归树，不是分类树，这一点相当重要。

回归树在分枝时会穷举每一个特征的每个阈值以找到最好的分割点，衡量标准是最小化均方误差。

6.1.2 梯度迭代（Gradient Boosting）

上面说到 GBDT 的核心在于累加所有树的结果作为最终结果，GBDT 的每一棵树都是以之前树得到的残差来更新目标值，这样每一棵树的值加起来即为 GBDT 的预测值。

模型的预测值可以表示为：

$$ F_k(x) = \sum_{i=1}^{k}f_{i}(x) \$$

$f_{i}(x) $ 为基模型与其权重的乘积，模型的训练目标是使预测值 $F_k(x)$ 逼近真实值 y，也就是说要让每个基模型的预测值逼近各自要预测的部分真实值。由于要同时考虑所有基模型，导致了整体模型的训练变成了一个非常复杂的问题。所以研究者们想到了一个贪心的解决手段：每次只训练一个基模型。那么，现在改写整体模型为迭代式：

$$F_k(x) = F_{k-1}(x)+f_{k}(x)\$$

这样一来，每一轮迭代中，只要集中解决一个基模型的训练问题：使 $F_k(x)$ 逼近真实值 $y$ 。

举个例子：比如说 A 用户年龄 20 岁，第一棵树预测 12 岁，那么残差就是 8，第二棵树用 8 来学习，假设其预测为 5，那么其残差即为 3，如此继续学习即可。

那么 Gradient 从何体现？其实很简单，其残差其实是最小均方损失函数关于预测值的反向梯度(划重点)：

$$ -\frac{\partial (\frac{1}{2}(y-F_{k}(x))^2)}{\partial F_k(x)} = y-F_{k}(x) \$$

也就是说，预测值和实际值的残差与损失函数的负梯度相同。

但要注意，基于残差 GBDT 容易对异常值敏感，举例：

很明显后续的模型会对第 4 个值关注过多，这不是一种好的现象，所以一般回归类的损失函数会用绝对损失或者 Huber 损失函数来代替平方损失函数。

GBDT 的 Boosting 不同于 Adaboost 的 Boosting，GBDT 的每一步残差计算其实变相地增大了被分错样本的权重，而对与分对样本的权重趋于 0，这样后面的树就能专注于那些被分错的样本。

6.1.3 缩减（Shrinkage）

Shrinkage 的思想认为，每走一小步逐渐逼近结果的效果要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它并不是完全信任每一棵残差树。

$$F_i(x)=F_{i-1}(x)+\mu f_i(x) \quad (0<\mu \leq 1) \$$

Shrinkage 不直接用残差修复误差，而是只修复一点点，把大步切成小步。本质上 Shrinkage 为每棵树设置了一个 weight，累加时要乘以这个 weight，当 weight 降低时，基模型数会配合增大。

6.2 优缺点

6.2.1 优点

1. 可以自动进行特征组合，拟合非线性数据；
2. 可以灵活处理各种类型的数据。

6.2.2 缺点

1. 对异常点敏感。

6.3 与 Adaboost 的对比

6.3.1 相同：

1. 都是 Boosting 家族成员，使用弱分类器；
2. 都使用前向分布算法；

6.3.2 不同：

1. 迭代思路不同：Adaboost 是通过提升错分数据点的权重来弥补模型的不足（利用错分样本），而 GBDT 是通过算梯度来弥补模型的不足（利用残差）；
2. 损失函数不同：AdaBoost 采用的是指数损失，GBDT 使用的是绝对损失或者 Huber 损失函数；

7. 总结

最后通过总结的方式对比下 ID3、C4.5 和 CART 三者之间的差异。

除了之前列出来的划分标准、剪枝策略、连续值确实值处理方式等之外，我再介绍一些其他差异：

• **划分标准的差异：**ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
• **使用场景的差异：**ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
• **样本数据的差异：**ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大 ；
• **样本特征的差异：**ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征；
• **剪枝策略的差异：**ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

参考

1. 《机器学习》周志华
2. 《数据挖掘十大算法》吴信东
3. CART 树怎么进行剪枝?
4. 机器学习算法中 GBDT 与 Adaboost 的区别与联系是什么？ - Frankenstein 的回答 - 知乎
5. 为什么说bagging是减少variance，而boosting是减少bias
6. Ensemble Learning - 周志华
7. 使用sklearn进行集成学习——理论
8. 【机器学习】决策树（上）——ID3、C4.5、CART（非常详细）
9. 【机器学习】决策树（中）——Random Forest、Adaboost、GBDT （非常详细）