专栏名称: 新机器视觉

最前沿的机器视觉与计算机视觉技术

机器学习中各种树模型总结

新机器视觉 · 公众号 · 科技自媒体 · 2024-10-05 21:20

主要观点总结

文章总结了关于决策树、随机森林、GBDT和XGBoost等机器学习模型的知识，包括它们的原理、应用和优势。

关键观点总结

关键观点1: 决策树

是一种有监督分类模型，以信息增益为准则选择最优划分属性，分为ID3、C4.5和CART等算法。

关键观点2: 随机森林

是一个多决策树的组合分类器，通过构建多个决策树进行投票，具有处理过大或过小的数据集、处理多源异构数据的能力。

关键观点3: GBDT和XGBoost

都是以决策树为基学习器的集成学习算法。GBDT是迭代树，每一棵树学习的是之前所有树结论和的残差。XGBoost则通过二阶泰勒展开损失函数，并加入正则项控制模型复杂度，支持自定义代价函数，具有并行化处理、处理缺失值等特性。

正文

作者：ChrisCao@知乎
https://zhuanlan.zhihu.com/p/75468124

编辑：好奇心log

最近还在深化机器学习算法，所以分享一篇关于决策树的总结文章，从普通的决策树到集成学习随机森林、GBDT、XGBoost，总结的还是非常到位的。

一. 决策树

决策树是一个有监督分类模型，本质是选择一个最大信息增益的特征值进行树的分割，直到达到结束条件或叶子节点纯度达到阈值。下图是决策树的一个示例图：

根据分割指标和分割方法，可分为：ID3、C4.5、CART算法。

1.ID3算法：以信息增益为准则来选择最优划分属性

信息增益的计算是基于信息熵（度量样本集合纯度的指标）

信息熵越小，数据集

的纯度越大

假设基于数据集

上建立决策树，数据有

个类别：

公式(1)中：

表示第K类样本的总数占数据集D样本总数的比例。

公式(2)表示是以特征A作为分割的属性，得到的信息熵：Di表示的是以属性A为划分，分成n个分支，第i个分支的节点集合。因此，该公式求得的是以属性A为划分，n个分支的信息熵总和。

公式(3)是以A为属性划分前和划分后的信息熵差值，也就是信息增益，越大越好。

假设每个记录有一个属性'ID',若按照ID进行分割的话，在这个属性上，能够取得的特征值是样本数，特征数目太多，无论以哪一个ID进行划分，叶子节点的值只会有一个，纯度很大，得到的信息增益很大，这样划分出来的决策树没有意义，即， ID3偏向于取值较多的属性进行分割，存在一定的偏好 。为减少这一影响，有学者提出了C4.5算法。

2.C4.5基于信息增益率准则选择最有分割属性的算法

信息增益率通过引入一个被称为分裂信息(Split information)的惩罚项来惩罚取值较多的属性：

其中， IV(a)是由属性A的特征值个数决定的，个数越多，IV值越大 ，信息增益率越小，这样就可以避免模型偏好特征值多的属性，如果简单按这个规则分割，模型又会偏好特征值少的特征，因此C4.5决策树先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择增益率最高的。

对于连续值属性来说，可取值数目不再有限，因此可以采用离散化技术（如二分法）进行处理。将属性值从小到大排序，然后选择中间值作为分割点，数值比它小的点被划分到左子树，数值不小于它的点被分到右子树，计算分割的信息增益率，选择信息增益率最大的属性值进行分割。

3.CART:以基尼系数为准则选择最优划分属性，可用于分类和回归

CART是一棵二叉树，采用二元切分法，每次把数据分成两份，分别进入左子树、右子树。并且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子节点多一。相比于ID3和C4.5，CART的应用要多一些，既可以用于分类也可以用于回归。CART分类时，选择基尼指数（Gini）为最好的分类特征，gini描述的是纯度，与信息熵含义类似，CART中每次迭代都会降低基尼系数。

Gini(D)反映了数据集D的纯度，值越小，纯度越高。我们在候选集合中选择使得划分后基尼指数最小的属性作为最优化分属性。

分类树和回归树

先说分类树，ID3、C4.5在每一次分支时，是穷举每一个特征属性的每一个阈值，找到使得按照特征值<=阈值，和特征值>阈值分成的两个分支的熵最大的特征和阈值。按照该标准分支得到两个新节点，用同样的方法进行分支，直到所有人被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中性别不唯一，则以多数人的性别作为该叶子节点的性别。

回归树总体流程也是类似，不过在每个节点(不一定是叶子节点)都会得到预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分支时穷举每个特征的每个阈值，找最好的分割点，但衡量的标准变成了最小化均方误差，即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方误差越大，通过最小化均方误差找最靠谱的分支依据。分支直到每个叶子节点上的人的年龄都唯一(这太难了)，或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄作为该叶子节点的预测年龄。

二.随机森林

先补充 组合分类器 的概念，将多个分类器的结果进行多票表决或取平均值，以此作为最终的结果。

1.构建组合分类器的好处：

(1)提升模型精度 ：整合各个模型的分类结果，得到更合理的决策边界，减少整体错误呢，实现更好的分类效果：

(2)处理过大或过小的数据集 ：数据集较大时，可将数据集划分成多个子集，对子集构建分类器；当数据集较小时，通过自助采样(bootstrap)从原始数据集采样产生多组不同的数据集，构建分类器。

(3)若决策边界过于复杂，则线性模型不能很好地描述真实情况 。因此，先对于特定区域的数据集，训练多个线性分类器，再将他们集成。

(4)比较适合处理多源异构数据 （存储方式不同（关系型、非关系型），类别不同（时序型、离散型、连续型、网络结构数据））

随机森林是一个多决策树的组合分类器，随机主要体现在两个方面： 数据选取的随机性和特征选取的随机性。

(1)数据的随机选取

第一，从原始数据集中采取有放回的抽样(bootstrap),构造子数据集，子数据集扥数量和原始数据集的数量一样。不同的子数据集的元素可以重复，同一个子数据集中的元素也可以重复。

第二，利用子数据集构建子决策树，将这个数据放到每个子决策树中，每个子决策树输出一个结果。最后，如果有了新的数据需要通过随机森林得到分类结果，就可以通过子决策树的判断结果来投票，得到随机森林的输出结果。如下图，假设随机森林中有3棵子决策树，2棵子树的分类结果是A类，1棵子树的分类结果是B类，那么随机森林的分类结果就是A类。

(2)待选特征的随机选取

类似于数据集的随机选取，随机森林中的子树的每一个分裂过程并未用到所有的待选特征，而是从所有的待选特征中随机选取一定的特征，之后再在随机选取的特征中选择最优的特征。这样能使随机森林中的决策树能不同，提升系统的多样性，从而提升分类性能。

组合树示例图

三、GBDT和XGBoost

1.在讲GBDT和XGBoost之前先补充Bagging和Boosting的知识。

Bagging是并行的学习算法，思想很简单，即每一次 从原始数据中根据均匀概率分布有放回的抽取和原始数据集一样大小的数据集合。 样本点可以出现重复，然后对每一次产生的数据集构造一个分类器，再对分类器进行组合。

Boosting的每一次抽样的样本分布是不一样的 ，每一次迭代，都是根据上一次迭代的结果，增加被错误分类的样本的权重。使模型在之后的迭代中更加注重难以分类的样本。这是一个不断学习的过程，也是一个不断提升的过程，这就是Boosting思想的本质所在。迭代之后，将每次迭代的基分类器进行集成，那么如何进行样本权重的调整和分类器的集成是我们需要考虑的关键问题。

Boosting算法结构图

以著名的Adaboost算法举例：

有一个数据集，样本大小为N，每一个样本对应一个原始标签起初，我们初始化样本的权重为1/N

计算的是当前数据下，模型的分类误差率，模型的系数值是基于分类误差率的

根据模型的分类结果，更新原始数据中数据的分布，增加被错分的数据被抽中的概率，以便下一次迭代的时候能被模型重新训练

最终的分类器是各个基分类器的组合

2.GBDT

GBDT是以决策树(CART)为基学习器的GB算法，是迭代树而不是分类树， Boost是"提升"的意思，一般Boosting算法都是一个迭代的过程，每一次新的训练都是为了改进上一次的结果。有了前面Adaboost的铺垫，大家应该能很容易理解大体思想。

GBDT的核心是： 每一棵树学习的是之前所有树结论和的残差。这个残差就是一个加预测值后能得真实值的累加量。 比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学习。