ID3树、C4.5树、CART树、RF、GBDT、XGBOOST模型

机器学习&深度学习

---

首发时间：2020.7.19
作者：zakexu（个人主页）

---

目录

---

一、ID3模型

（一）简介

1、决策树是一个树结构，可以是二叉树，也可以是非二叉树；每个非叶子节点代表样本的某个特征，每个叶子节点代表样本的标签，可以是分类问题中的类别（落到该叶子节点带标签样本的多数类别）也可以是回归问题中的预测值（落到该叶子节点带标签样本的平均值）。

2、决策树模型核心在于非叶子节点的构建，也就是特征的选择；核心目的在于每次特征划分之后，分支节点的纯度越来越高。

（二）模型

1、在ID3算法中，采用信息熵来表示节点的纯度（纯度越高，熵越小），采用信息增益来选择特征，而信息增益可以表示为信息熵跟条件熵的差值。

2、信息熵可以表示如下：

$$Ent(D)=-\sum_k{p_klogp_k}$$
其中$D$表示样本集，$p_k$表示第$k$类样本的概率。
条件熵可以表示如下：
$$Ent(D|A)=\sum_v{\frac{|D_v|}{|D|}}Ent(D_v)$$
其中$A$表示特征，$D_v$表示根据特征$A$的第$v$个取值划分出来的样本集。
那么信息增益可以表示为：
$$Gain(D,A)=Ent(D)-Ent(D|A)$$
由此可以看出，在特征选择过程中，优先选择信息增益大的。

3、基于信息增益的特征选择，会有一个问题，就是取值越多的特征，信息增益越高，比如ID类特征，每个样本都有唯一ID，那么根据特征取值，每个子节点都只会有一个样本，信息熵为0，也就是100%的增益；但这样是不合理的，得到的决策树模型泛化能力会很弱。

二、C4.5模型

（一）简介

1、为了解决ID3中信息增益的问题，C4.5模型引入了信息增益率作为特征选择的标准。信息增益率是在信息增益的基础上，引入约束多取值特征的因子。

（二）模型

1、信息增益率可以表示如下：

$$Gain\_ratio(D,A)=\frac{Gain(D,A)}{IV(A)}$$
$$IV(A)=-\sum_v{\frac{|D_v|}{|D|}}log\frac{|D_v|}{|D|}$$

2、在实际应用中，并不会直接使用信息增益率来做特征选择，因为该指标会偏向少取值特征；因此，一般都是先用信息增益来筛选部分top的特征，然后再基于信息增益率来做特征选择。

三、CART模型

（一）简介

1、CART（Classification And Regression Tree）模型是一种二叉树，既可以做分类也可以做回归。在分类任务上，采用的是基尼系数作为特征选择标准，在回归任务上，采用的是平方误差最小。

（二）模型

1、分类树

（1）在ID3算法中，采用的是信息增益，有2个方面可以优化：

• 对于不同特征，信息熵是一样的，所以可以采用条件信息熵来替代信息增益。
• 条件信息熵的计算中涉及log计算，较为复杂，可以做优化；因此，在CART中，采用基尼系数：

$$Gini(D)=1-\sum_k{p_k^2}$$

那么条件基尼系数可以表示为：

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

注：基尼系数除了用于特征的选择，还用于特征分割点的选择。（由于是二叉树，所以用于选择A=a跟A!=a）

（2）条件基尼系数越小，分支节点纯度越高。

注：二叉树不存在多值特征导致条件基尼系数较小的问题。

2、回归树

回归树的构建可以分为几个步骤：
（1）根据以下式子做特征选择以及特征切分点：

$$\min_{j,s}[\min_{c_1}\sum_{x \in R_1(j,s)}{(y-c_1)^2}+\min_{c_2}\sum_{x \in R_2(j,s)}{(y-c_2)^2}]$$
其中：
$$R_1(j,s)=\{x|x^j<=s\},R_2(j,s)=\{x|x^j>s\}$$

$$c_1=avg\{y|x \in R_1(j,s)\},c_2=avg\{y|x \in R_2(j,s)\}$$

依次遍历每个特征$j$，对于每个特征，依次遍历每一个特征取值$s$，从而找到是的平方误差最小的特征变量以及特征切分点。

（2）根据上述步骤，可以将特征空间划分为$m$个空间，那么最终的预测模型可以表示为：

$$f(x)=\sum_m{c_mI(x \in R_m)}$$
其中：
$$c_m=avg\{y|x \in R_m\}$$

注：ID3 vs C4.5 vs CART
（1）ID3采用信息增益做特征选择、C4.5采用信息增益率做特征选择、CART采用基尼系数（分类）或者损失函数（回归）做特征选择。
（2）ID3跟C4.5可以是多叉树，CART是二叉树。
（3）ID3跟C4.5一般是分类树，CART既可以是分类树，也可以是回归树。
（4）都是既支持连续值特征，也支持离散值特征，只不过对于连续值特征需要做切分点的选择。

四、RF模型

（一）简介

1、随机森林RF（Random Forests）是由很多决策树构成的，不同决策树之间没有关联。当我们进行分类任务时，新的输入样本进入，就让森林中的每一棵决策树分别进行判断和分类，每个决策树会得到一个自己的分类结果，决策树的分类结果中哪一个分类最多，那么随机森林就会把这个结果当做最终的结果。

（二）模型

1、RF模型存在两个随机采样的过程（行跟列的随机采样，为了保证方差）：行采样指的是样本的随机采样，每个决策树模型的训练样本都是有放回地随机采样部分样本进行训练（每棵子树的样本量跟原始样本数量一致，但可能采到重复的样本，这也是为了保证每棵子树之间具有一定的差异性，各自侧重学习样本分布中的不同区域，bagging结果才能保证偏差；除此之外，由于是有放回的抽样，会有一部分袋外样本没被用到，可以用来做测试）；列采样指的是特征的随机采样（$m<<M$，其中$m$表示采样的特征数，$M$表示原始特征数，在每个节点上，随机选择特征进行计算）；由于两个随机采样的过程，可以避免模型过拟合，因此在整体的训练过程中，每棵树都是完全分裂的方式，并不需要做剪枝。
注：假设有$m$个样本，那么每个样本不被抽到的概率就是$1-1/m$，那么连续$m$次都没有被抽到的概率是${(1-1/m)}^m$，当$m$趋于无穷时，概率会趋于$1/e$，也就是36.8%的概率。

2、随机森林有2个超参，一个是森林中树的数量，一般建议取很大；另一个是$m$的大小，推荐$m$的值为$M$的均方根。

五、GBDT模型

（一）简介

1、基于梯度提升算法的学习器叫做GBM(Gradient Boosting Machine)。理论上，GBM可以选择各种不同的学习算法作为基学习器。现实中，用得最多的基学习器是决策树，基于决策树的GBM算法叫做GBDT。

2、GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案，GBDT中的树是回归树（不是分类树）。

3、GBDT的学习过程可以看作是梯度下降的过程。训练的目的其实就是为了找到一个合适的模型来拟合训练样本，从而让损失函数最小；可以将这个合适的模型看成是一个参数，那么每一步的迭代其实就是在原先的模型基础上，新增一个负梯度，换句话讲，每一个新增的子模型，目标都是为了拟合负梯度。

（二）模型

1、GBDT算法可以看成是由$m$棵树组成的加法模型：

$$y=\sum_m{f_m(x)}$$

$$F_k(x)=\sum_kf_k(x)$$

训练第$k+1$棵树时，整体的损失函数表示如下：

$$obj^{(k+1)}=\sum_i{L(y_i，F_k(x_i)+f_{k+1}(x_i))}$$

其中$F_k(x_i)$表示第$i$个样本经过前$k$棵树之后的预测值；$f_{k+1}$表示第$k+1$棵树。直接优化上述函数一般较难，所以根据之前的思想，拟合的是负梯度：

$$f_{k+1}(x_i)=-\frac{\partial L(y_i，F_k(x_i))}{\partial F_k(x_i)}$$

也就是说对于第$k+1$棵树的训练样本对而言，$x$是特征输入，$y$是损失函数对于当前GBDT模型的负梯度，因此每棵树都是在拟合负梯度（叶子节点的输出就是落在该叶子节点上所有负梯度的均值）。但实际应用中，每棵新增的决策树都是需要乘上一个Shrinkage系数，即不完全信任每一棵残差树，认为每棵树只学到了真理的一部分，累加的时候只累加了一小部分，多学几棵树来弥补不足。 这个技巧类似于梯度下降里的学习率，也就是$F_k(x_i)+\lambda f_{k+1}(x_i)$。

2、假设损失函数采用的是平方损失函数，那么梯度可以表示为：

$$\frac{\partial L(y_i，F_k(x_i))}{\partial F_k(x_i)}=\frac{\partial \frac{1}{2}(y_i-F_k(x_i))^2}{\partial F_k(x_i)}=F_k(x_i)-y_i=-\delta$$

其中：

$$\delta = y_i-F_k(x_i)$$

也就是说当损失函数为平方损失时，拟合的负梯度刚好等于残差。

3、上面都是基于回归问题来分析的，对于分类问题也是类似，只不过需要在每个叶子节点的输出用sigmoid函数来将输出值压缩到0-1之间，代表概率值；那么损失函数就可以使用交叉墒了，通过推算可以发现，其负梯度就是样本真实标签与预测概率之差。

注：GBDT迭代过程中，同一棵树上同一个特征会不会重复出现？
会的，因为GBDT采用CART，是二叉树，也就是对多维空间的切分，那么优质的特征是会重复出现的。

注：如何计算决策树特征的重要性？
（1）特征分裂的累计次数。
（2）特征分裂的加权累计次数（越早被分裂权重越大）。
（3）特征分裂的累计信息增益。

注：RF vs GBDT
（1）两者都是cart树，前者可以是分类树也可以是回归树，后者是回归树（因为要拟合残差）。
（2）前者是并行生成，后者是串行生成。
（3）前者是bagging，更关注方差，提高泛化能力（generation）；后者是boosting，更关注偏差，提高记忆能力（memorization）。
（4）前者一般完全分裂所以较深（兼顾个体偏差，而方差是通过行列采样），后者一般深度较浅（兼顾方差，而偏差是通过boosting的方式）。
（5）样本上都是随机采样，前者是有放回地随机采样（有放回是为了整体偏差，每棵子树侧重学习样本分布的不同区域），后者是无放回地随机采样（每棵子树都是学习一样的样本分布，毕竟当前子树要学习的负梯度来自前面的子树，如果样本分布不一致，不容易学习）。
（6）特征上，前者是随机采样，后者不做特征采样（只不过会对特征做随机排序，这样子如果有2个特征信息增益一致，那么分裂时选到的特征是随机的）。

六、XGBoost模型

（一）模型

1、根据拟合残差的思想，可以将第$k+1$棵树的损失函数表示如下：

$$obj^{(k+1)}=\sum_i{L(y_i，F_k(x_i)+f_{k+1}(x_i))}+\Omega(f_{k+1})$$

其中$F_k(x_i)$表示第$i$个样本经过前$k$棵树之后的预测值；$f_{k+1}$表示第$k+1$棵树，$\Omega$表示模型的复杂度函数。

2、根据泰勒公式：

$$f(x+\Delta x)=f(x)+f'(x)\Delta x + \frac{1}{2}f''(x)\Delta x^2$$
假设$x=F_k(x_i),\Delta x=f_{k+1}(x_i)$，那么上述式子可以等价为：
$$obj^{(k+1)}=\sum_i{[L(y_i，F_k(x_i))+g_if_{k+1}(x_i)+\frac{1}{2}h_if_{k+1}^2(x_i)]}+\Omega(f_{k+1}) \\\approx \sum_i{[g_if_{k+1}(x_i)+\frac{1}{2}h_if_{k+1}^2(x_i)]}+\Omega(f_{k+1})$$
其中：
$$g_i=\frac{\partial L(y_i，F_k(x_i))}{\partial F_k(x_i)}$$

$$h_i=\frac{\partial L(y_i，F_k(x_i))}{\partial^2 F_k(x_i)}$$

注：二阶展开的目的有三个，首先是为了更准确地近似损失函数，减少信息损失；其次是为了具有扩展性，可以使用多种不同的损失函数，二阶泰勒展开可以近似任意的损失函数（一阶的话信息量少，三阶的话大部分loss函数不存在三阶梯度比如均方差loss）；最后是为了加速收敛，二阶展开后，每一棵子树拟合的负梯度可以参考adam的思想。

3、在XGBoost中，由于采用的是CART回归树，那么可以定义树为：$w_j, 1<j<T$，也就是说总共有$T$个叶子节点，每个叶子节点的输出或者说权重表示为$w_j$。那么上述损失函数可以表示为：

$$obj^{(k+1)}=\sum_j{[(\sum_{i \in I_j}g_i)w_j+ \frac{1}{2} (\sum_{i \in I_j} h_i)w_j^2]}+\gamma(T +\frac{1}{2}\sum_j w_j^2)\\ =\sum_j{[(\sum_{i \in I_j}g_i)w_j+ \frac{1}{2} (\sum_{i \in I_j} h_i + \gamma)w_j^2]}+\gamma T\\ \sum_j{[G_j w_j+ \frac{1}{2} (H_j + \gamma)w_j^2]}+\gamma T$$

其中$i \in I_j$表示第$i$个样本落在第$j$个叶子节点上。$G_j$跟$H_j$都是常数（这儿体现跟GBDT的思想一致性，GBDT是落在叶子节点上的所有一阶梯度的平均，而XGBoost是落在叶子节点上的所有一阶梯度累加和除以二阶梯度累加和），那么令loss最小的话，可得到（体现了拟合负梯度的味道，这儿有点类似adam的思路，既包含了一阶也包含了二阶）：

$$w_j=-\frac{G_j}{H_j+\gamma}$$ ，那么loss就可以表示为：

$$obj^{(k+1)}=-\frac{1}{2}\sum_j \frac{G_j^2}{H_j+\gamma}+\gamma T$$

该loss就作为特征分裂的选择依据（loss越小，叶子节点的输出越拟合负梯度），比如分裂前的loss可以表示为：$-\frac{1}{2} \frac{(G_L + G_R)^2}{H_L + H_R +\gamma} +\gamma$，分裂后的loss可以表示为：$-\frac{1}{2}[ \frac{G_L^2}{H_L +\gamma}+\frac{G_R^2}{H_R +\gamma}]+2\gamma$，那么信息增益就是loss差。

注：GBDT vs XGBoost
（1）前者泰勒展开只做了一阶，后者做了二阶展开；前者拟合一阶负梯度，后者拟合一阶除以二阶负梯度。
（2）后者还加入了正则化项（叶子节点跟叶子权重）。
（3）前者不对特征做随机采样，后者对特征做随机采样。
（4）后者做了工程上的优化：提前对特征做排序，加速分裂；不采用遍历的思路寻找最优切分点，而是用近似算法做提速。