【预估排序】Xgboost、GBDT、CART等树模型联系和区别(超级详细)
写在系列文章之前
本专栏对我在广告算法业务中落地过的预估排序、Embedding、NLP等领域的模型进行梳理介绍。感兴趣的同学可以关注+收藏哟~
前言
基于树的模型在统计机器学习时代大行其道,由于其有出色的可解释性及对缺失值不敏感的特性,广泛用于广告及风控场景。比如在广告场景可以通过决策树来进行组合特征抽取,风控场景可以评估是否能借贷给目标人。
通过本文,你会了解到如下内容:
- 决策树
- ID3算法介绍
- C4.5算法介绍
- CART算法介绍
- Bagging算法和Boosting算法
- 随机森林算法介绍
- GBDT算法介绍
- Xgboost算法介绍
- 一点总结和使用建议
1.决策树
什么是决策树呢?决策树是一种监督学习方法,既可以用来处理分类问题也可以处理回归问题。
以相亲为例,你判断自己要不要去见相亲对象的标准,首先考虑白不白,发现一点也不白,然后看富不富,结果一点也不富,这时候你就有点郁闷了,那总得美吧。很遗憾,姑娘也不美。那结果就是不去见了。
决策树的学习过程包括:特征选择、决策树生成、决策树剪枝。
下面我分别从思想、决策树生成方法、决策树剪枝、优缺点四个方面来分别介绍ID3、C4.5、CART。
1.1 ID3算法
1.1.1 思想
ID3使用信息增益作为特征选择的度量,使用自顶向下的贪心算法遍历决策树空间。具体的:
- 计算数据集合的信息熵,以及各个特征的条件熵。选择信息增益最大的作为本次划分节点。
- 删除上一步使用的特征,更新各个分支的数据集和特征集。
- 重复1,2步,知道子集包含单一特征,则为分支叶结点。
1.1.2 决策树生成方法
我们需要按照什么标准构造一颗树呢?由于决策树是自顶向下递归方式,每一步使用贪心算法采用当前状态下最优选择。所以我们构造决策树的关键就是选择一个好的分裂标准。
ID3使用信息增益作为特征选择的度量。那么什么是信息增益呢?信息增益表示得知特征 A 的信息而使得样本集合不确定性减少的程度。
要明白信息增益,首先需要知道信息熵。
信息熵
类似于物理上的熵,信息熵越大,意味着信息越是无序。一般来说,对于一堆未处理的数据,信息量大,这堆数据的看起来就非常的杂乱,那么信息熵也就越大。
假设随机变量X的取值为{
},对应出现的概率为{
}。那么X的信息熵表示为:
对应的训练样本上,
可以表示为
。其中
表示集合 D 中属于第 k 类样本的样本子集。既信息熵可以表示为:
针对某个特征 A,对于数据集 D 的条件熵
为:
其中
表示 D 中特征 A 取第 i 个值的样本子集,
表示
中属于第 k 类的样本子集。
信息增益 = 信息熵 - 条件熵:
如果信息增益越大,那么就是指分完之后的信息熵越小,那也就意味着分完之后的数据趋向于有序,而越有序的数据,意味着我们能更好地预测数据。
1.1.3 ID3优缺点
- ID3算法没有进行决策树剪枝,容易发生过拟合
- ID3算法没有给出处理连续数据的方法,只能处理离散特征
- ID3算法不能处理带有缺失值的数据集,需对数据集中的缺失值进行预处理
- 信息增益准则对可取值数目较多的特征有所偏好(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大)
1.2 C4.5算法
C4.5主要是克服ID3使用信息增益进行特征划分对取值数据较多特征有偏好的缺点。使用信息增益率进行特征划分。
C4.5相比ID3进行的改进有如下4点:
- 引入剪枝策略,使用悲观剪枝策略进行后剪枝
- 使用信息增益率代替信息增益,作为特征划分标准
- 连续特征离散化
- 需要处理的样本或样本子集按照连续变量的大小从小到大进行排序
- 假设该属性对应的不同的属性值一共有N个,那么总共有N−1个可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点,根据这个分割点把原来连续的属性分成两类
- 缺失值处理
- 对于具有缺失值的特征,用没有缺失的样本子集所占比重来折算信息增益率,选择划分特征
- 选定该划分特征,对于缺失该特征值的样本,将样本以不同的概率划分到不同子节点
1.2.1 决策树生成方法
使用信息增益率,信息增益率表示如下:
称为特征 A 的固有值。
信息增益率对可取值较少的特征有所偏好(分母越小,整体越大),因此 C4.5 并不是直接用增益率最大的特征进行划分,而是使用一个启发式方法:先从候选划分特征中找到信息增益高于平均值的特征,再从中选择增益率最高的。
1.2.2 决策树剪枝
决策树剪枝的目的是为了防止过拟合。
C4.5采用后剪枝对决策树进行剪枝。具体方法为:
在决策树构造完成后,自底向上对非叶节点进行评估,如果将其换成叶节点能提升泛化性能,则将该子树换成叶节点。后剪枝决策树欠拟合风险很小,泛化性能往往优于预剪枝决策树。但训练时间会大很多。
1.2.3 C4.5优缺点
- C4.5只能用于分类
- C4.5 在构造树的过程中,对数值属性值需要按照其大小进行排序,从中选择一个分割点,所以只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时,程序无法运行。
- 在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,算法低效。
1.3 CART算法
相比ID3和C4.5算法,CART算法使用二叉树简化决策树规模,提高生成决策树效率。
1.3.1 思想
CART树在C4.5基础上进行了如下改进:
- CART使用二叉树来代替C4.5的多叉树,提高了生成决策树效率
- C4.5只能用于分类,CART树可用于分类和回归
- CART 使用 Gini 系数作为变量的不纯度量,减少了大量的对数运算
- CART 采用代理测试来估计缺失值,而 C4.5 以不同概率划分到不同节点中
- CART 采用“基于代价复杂度剪枝”方法进行剪枝,而 C4.5 采用悲观剪枝方法
- ID3 和 C4.5 层级之间只使用一次特征,CART 可多次重复使用特征
1.3.2 决策树生成
CART决策树生成分为 分类树和回归树两种场景。生成方式有一定的区别。
1.3.2.1 分类树
首先介绍CART作为分类树的情况。CART作为分类树时,特征属性可以是连续类型也可以是离散类型,但观察属性(即标签属性或者分类属性)必须是离散类型。
CART分类树在节点分裂时使用GINI指数。基尼指数代表了模型的不纯度,基尼系数越小,不纯度越低,特征越好。这和信息增益(率)正好相反。
其中 k 代表类别。
离散值和连续值处理
对于离散属性,可能会出现属性取值数N>=3的情况,因为CART是二叉树,此时需要考虑将N>=3个取值的离散特征的处理时也只能有两个分支,这就要通过组合人为的创建二取值序列并取GiniGain最小者作为树分叉决策点。
对于连续值,CART 分类树采用基尼系数的大小来度量特征的各个划分点。
缺失值处理
CART 算法使用一种惩罚机制来抑制提升值,从而反映缺失值的影响。为树的每个节点都找到代理分裂器,当 CART 树中遇到缺失值时,这个实例划分到左边还是右边是决定于其排名最高的代理,如果这个代理的值也缺失了,那么就使用排名第二的代理,以此类推,如果所有代理值都缺失,那么默认规则就是把样本划分到较大的那个子节点。
1.3.2.2 回归树
回归树要求观察属性是连续类型,由于节点分裂选择特征属性时通常使用最小绝对偏差(LAD)或者最小二乘偏差(LSD)法,因此通常特征属性也是连续类型。
对于任意划分特征 A,对应的任意划分点 s 两边划分成的数据集
和
,求出使
和
各自集合的均方差最小,同时
和
的均方差之和最小所对应的特征和特征值划分点。表达式为:
其中,
为
数据集的样本输出均值,
为
数据集的样本输出均值。
对于决策树建立后做预测的方式,CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别,它采用的是用最终叶子的均值或者中位数来预测输出结果。
剪枝策略
采用一种“基于代价复杂度的剪枝”方法进行后剪枝。具体做法为:
我们将一颗充分生长的树称为T0 ,希望减少树的大小来防止过拟化。但同时去掉一些节点后预测的误差可能会增大,那么如何达到这两个变量之间的平衡则是问题的关键。因此我们用一个变量α 来平衡,定义损失函数如下:
为任意子树,
为预测误差,
为子树
的叶子节点个数,
是参数,
衡量训练数据的拟合程度,
衡量树的复杂度,
权衡拟合程度与树的复杂度。
那么我们如何找到这个合适的α来使拟合程度与复杂度之间达到最好的平衡呢?准确的方法就是将α从0取到正无穷,对于每一个固定的α,我们都可以找到使得Cα(T)最小的最优子树T(α)
- 当α很小的时候,T0 是这样的最优子树
- 当α很大的时候,单独一个根节点就是最优子树
尽管α的取值无限多,但是T0的子树是有限个。Tn是最后剩下的根结点,子树生成是根据前一个子树Ti,剪掉某个内部节点后,生成Ti+1。然后对这样的子树序列分别用测试集进行交叉验证,找到最优的那个子树作为我们的决策树。因此CART剪枝分为两部分,分别是生成子树序列和交叉验证。
2. Bagging算法和Boosting算法
2.1 Bagging和Boosting区别
Bagging算法和Boosting都属于集成算法,最重要的假设是:当弱模型被正确组合时,我们可以得到更精确和/或更鲁棒的模型。
- bagging算法通常考虑的是同质弱学习器,相互独立地并行学习这些弱学习器,并按照某种确定性的平均过程将它们组合起来。
- boosting算法通常考虑的也是同质弱学习器。它以一种高度自适应的方法顺序地学习这些弱学习器(每个基础模型都依赖于前面的模型),并按照某种确定性的策略将它们组合起来。
bagging 的重点在于获得一个方差比其组成部分更小的集成模型,而 boosting 和 stacking 则将主要生成偏差比其组成部分更低的强模型(即使方差也可以被减小)
Bagging和Boosting 的主要区别
- Bagging采取Bootstraping的是随机有放回的取样,Boosting的每一轮训练的样本是固定的,改变的是每个样本的权重。
- Bagging采取的是均匀取样,每个样本的权重相同,Boosting根据错误率调整样本权重,错误率越大的样本权重越大
- Bagging所有预测函数权值相同,Boosting中误差越小的预测函数权值越大。
- Bagging 的各个预测函数可以并行生成;Boosting的各个预测函数必须按照顺序迭代生成
将Bagging和Boosting分别和树模型结合分别生成:
- Bagging+决策树=随机森林
- Boosting+决策树=GBDT
下面分别对随机森林,GBDT,以及GBDT的高效实现Xgboost进行介绍
2.2 随机森林
随机森林本质上就是构建很多弱决策树,然后整合成森林,来确定最终的预估结果。
2.2.1 思想
随机森林的主要特点可以总结为如下2点:数据随机性选取,待选特征的随机选取。主要是为了消除过拟合问题。随机森林使用CART树作为弱学习器,生成树的过程中不进行剪枝,确定最终结果时,分类使用投票机制,回归问题使用平方误差最小化。
随机森林根据下面步骤来构建:
- M来表示训练样本的个数,N表示特征数目
- 输入特征数目n,用于确定决策树一个节点的决策结果;其中n应远小于N
- M个训练样本中,有放回抽样的方式,取样k次,形成训练集,并用未抽到样本做预测,评估误差。
- 随机选择n个特征,每棵决策树上每个节点的决策基于这些特征确定。根据这n个特征,计算其最佳的分裂方式
- 最后根据每棵树,以多胜少方式决定分类
2.2.2 随机森林优缺点
优点:
- 很容易查看模型的输入特征的相对重要性
- 可以处理高维数据
- 超参数的数量不多,而且它们所代表的含义直观易懂
- 随机森林有足够多的树,分类器就不会产生过度拟合模型
缺点:
- 使用大量的树会使算法变得很慢,无法做到实时预测
- 对于回归问题,精准度不够
- 抗噪声干扰能力弱,无法自动处理异常样本
- 模型越深越容易过拟合
2.3 GBDT
GBDT (Gradient Boosting Decision Tree) 梯度提升迭代决策树,是Boosting算法的一种。
GBDT使用的弱学习器必须是CART,且必须是回归树。GBDT用来做回归预测,当然,通过设置阈值也能用于分类任务。在模型训练时,模型预测样本损失尽可能小。
2.3.1 GBDT相关问题
GBDT的直观理解是:模型的每一轮预测都和真实值有gap,这个gap称为残差。下一轮对残差进行预测,最后将所有预测结果想加,得到最终结果。GBDT每一棵树学习的是前面所有树结论和的残差。
残差和负梯度什么关系?
我们每次计算都是为了减少上次的残差,那我们在残差减少的梯度上建立新模型是不是就可以了呢?GBDT就是这么来做的。
那么负梯度和残差是什么关系呢?假设现在你有样本集
,然后你用一个模型
去拟合这些数据,
被称为残差,也就是前一模型(
)未能完全拟合的部分。假如,我们损失函数使用平方损失
,这里额外提一句,平方损失一般用于回归问题,分类问题一般使用交叉熵等熵类损失。这时候,你会发现平方损失的负梯度就是残差。
损失函数为:
代价函数为:
损失函数的一阶导:
残差刚好就是负梯度:
那我们是不是就可以用负梯度来代替残差,推广到所有可导损失函数上了呢。
shrinkage是啥?
同时,GBDT认为每棵残差树只学到了真实情况的一小部分,希望通过每次走一小步的方式逐渐逼近真实结果,认为这样比每次迈一大步的方式更容易避免过拟合,这就是shrinkage的思想,shrinkage详细思想可以参考我之前的回答xgboost为什么要用shrinkage来削弱每棵树的影响。
2.3.2 GBDT思想
GBDT树的学习过程为:计算伪残差-> 生成基学习器 -> 目标函数优化 -> 更新模型
拿我之前分享的ppt偷下懒~
关键就在负梯度和shrinkage上。
2.3.3 GBDT缺点
- 基于残差的gbdt在解决回归问题上不算好的选择,对异常值过于敏感
- 不适合高纬稀疏特征
- 不好并行计算
2. 4 Xgboost算法
XGBoost 是大规模并行 boosting tree 的工具,它是目前最快最好的开源 boosting tree 工具包。
2.4.1 Xgboost和GBDT差异
Xgboost和GBDT都属于Grandient Boosting。Xgboost相比GBDT在如下方面做了改进:
- GBDT将目标函数泰勒展开到一阶,而xgboost将目标函数泰勒展开到了二阶,Xgboost保留更多有关目标函数的信息
- GBDT是给新的基模型寻找新的拟合标签(前面加法模型的负梯度),而xgboost是给新的基模型寻找新的目标函数(目标函数关于新的基模型的二阶泰勒展开)
- xgboost加入了和叶子权重的L2正则化项,有利于模型获得更低的方差。
- xgboost增加了自动处理缺失值特征的策略。通过把带缺失值样本分别划分到左子树或者右子树,比较两种方案下目标函数的优劣,从而自动对有缺失值的样本进行划分,无需对缺失特征进行填充预处理。
2.4.2 Xgboost思想
XGBoost 是由
个基模型组成的一个加法运算式:
其中
为第
个基模型,
为第
个样本的预测值。
损失函数可由预测值
与真实值
进行表示:
其中
为样本数量。
目标函数由模型的损失函数
与抑制模型复杂度的正则项
组成(偏差和方差权衡):
为模型的正则项。
第t步的模型拟合为例,在这一步,模型对第
个样本
的预测为:
其中
就是我们这次需要加入的新模型,即需要拟合的模型,此时,目标函数就可以写成:
即此时最优化目标函数,就相当于求得了
。
之后将目标函数进行二阶泰勒展开,得到新的目标函数:
其中
为损失函数的一阶导,
为损失函数的二阶导,注意这里的导是对
求导。
那什么是二阶泰勒展开呢?
二阶泰勒展开可以表示为:
由于在第t步
其实是一个已知的值,所以
是一个常数,其对函数优化不会产生影响,因此,等式(2)可以写成:
故,我们只要求出每一步损失函数的一阶和二阶导的值代入等式4,然后最优化目标函数,就可以得到每一步的
,最后根据加法模型得到一个整体模型。
决策树来表示目标函数
我们用
则代表了哪个叶子结点取什么
值,
代表每个样本在哪个叶子结点上,所以
就代表了每个样本的预测值
。那么
就可以转成
。
正则项表示
首先,我们用正则项来定义
来定义决策树的复杂度,即决策树模型的复杂度由生成的树的叶子节点数量和叶子节点对应的值向量的L2范数决定。
我们假设
为第
个叶子节点的样本集合,则等式4根据上面的一些变换可以写成:
即将我们之前样本的集合,都改写成叶子结点的集合。
定义
,
,则等式5可以写成:
如果我们已经知道了每个叶子结点有哪些样本,所以
和
是确定的,我们需要预测的值
不确定,令目标函数一阶导为0,则可以求得叶子结点
对应的值:
目标函数的值可以化简为:
2.4.3 贪心法求解树
可以根据训练好的树预先计算好,枚举所有可能的新树的结构,选择目标函数最小的那棵树,同时使用
求得该树每个叶子节点的输出值,不断求解下去,就可以训练出一组最优树。但是,枚举所有的树是不现实的,因为样本特征值可能是连续的,树的结构可能是无穷的。
在Xgboost中是使用贪心法来求解树。具体的:
- 初始化树深度 0(即只有一个叶子节点,所有样本都落在该节点)
- 对于每个叶子节点,尝试分裂该节点,在分裂后得到的增益定义如下:
- 该公式定义了,分裂后左右子树的新增得分减去不分裂时候节点得分,再减去因为新增一个节点,增加的复杂度。
之后,我们按照Gain来定义最佳分裂。
- 对于每个叶子节点,枚举所有的特征
- 对每个特征,把映射到该叶节点的样本按照该特征值排序
- 使用线性扫描来决定最佳分裂点
- 在所有枚举的特征中,选择最优的分裂
Xgboost的具体算法流程如下:
- 迭代初始,对每个样本计算
,该计算只依赖于训练好的树 - 使用
为目标函数,采用贪心法求得树 - 新增树后,模型表示为
,实践中使用
替代上面的迭代公式,
被称为步长(steps-size)或收缩率(shrinkage),通常设置为 0.1 附近的值。设置它的目的在于,不期望模型每一次迭代学习到所有残差,防止过拟合。
总结
本文介绍了决策树(ID3、C4.5、CART),以及决策树在Bagging和boosting上的应用(随机森林、GBDT、Xgboost)。
在具体业务中,GBDT一般不直接使用,因为容易出现过拟合问题。比较好的方法是LR+GBDT,FTRL+GBDT来处理,会得到比较好的表现。具体的融合和特征工程不是本次介绍的重点,后续我会专门写一篇建模技巧的文章。
希望大家能有些收获。
欢迎大家关注我的微信公众号:机器鼓励猴