纯干货|Boosting家族之XGBoost算法

一、概念

XGBoost全名叫(eXtreme Gradient Boosting)极端梯度提升,经常被用在一些比赛中,其效果显著。它是大规模并行boosted tree的工具,它是目前最快最好的开源boosted tree工具包。XGBoost 所应用的算法就是 GBDT(gradient boosting decision tree)的改进,既可以用于分类也可以用于回归问题中。

1、回归树与决策树

事实上,分类与回归是一个型号的东西,只不过分类的结果是离散值,回归是连续的,本质是一样的,都是特征(feature)到结果/标签(label)之间的映射。说说决策树和回归树,在上面决策树的讲解中相信决策树分类已经很好理解了。

分类树的样本输出(即响应值)是类的形式,如判断蘑菇是有毒还是无毒,周末去看电影还是不去。而回归树的样本输出是数值的形式,比如给某人发放房屋贷款的数额就是具体的数值,可以是0到120万元之间的任意值。

那么,这时候你就没法用上述的信息增益、信息增益率、基尼系数来判定树的节点分裂了,你就会采用新的方式,预测误差,常用的有均方误差、对数误差等。而且节点不再是类别,是数值(预测值),那么怎么确定呢,有的是节点内样本均值,有的是最优化算出来的比如Xgboost。

2、boosting集成学习

boosting集成学习,由多个相关联的决策树联合决策,什么叫相关联,举个例子,有一个样本[数据->标签]是[(2,4,5)-> 4],第一棵决策树用这个样本训练得预测为3.3,那么第二棵决策树训练时的输入,这个样本就变成了[(2,4,5)-> 0.7],也就是说,下一棵决策树输入样本会与前面决策树的训练和预测相关。

与之对比的是random foreast(随机森林)算法,各个决策树是独立的、每个决策树在样本堆里随机选一批样本,随机选一批特征进行独立训练,各个决策树之间没有啥毛线关系。

所以首先Xgboost首先是一个boosting的集成学习,这样应该很通俗了

3、这个时候大家就能感觉到一个回归树形成的关键点:(1)分裂点依据什么来划分(如前面说的均方误差最小,loss);(2)分类后的节点预测值是多少(如前面说,有一种是将叶子节点下各样本实际值得均值作为叶子节点预测误差,或者计算所得)

二、集成思想

在学习XGBoost之前,我们得需要先明白集成思想。集成学习方法是指将多个学习模型组合,以获得更好的效果,使组合后的模型具有更强的泛化能力。另外XGBoost是以分类回归树(CART树)进行组合。故在此之前,我们先看下CART树(CART树具体原理请自行复习,或者可以留言)。如下,通过输入用户年龄、性别进行判断用户是否喜欢玩游戏的得分值。由此得到一颗CART树模型。

纯干货|Boosting家族之XGBoost算法

我们知道对于单个的决策树模型容易出现过拟合,并且不能在实际中有效应用。所以出现了集成学习方法。如下图,通过两棵树组合进行玩游戏得分值预测。其中tree1中对小男生的预测分值为2,tree2对小男生的预测分值为0.9。则该小男生的最后得分值为2.9。

纯干货|Boosting家族之XGBoost算法

将上面集成学习方法推广到一般情况,可知其预测模型为:

纯干货|Boosting家族之XGBoost算法

其中

纯干货|Boosting家族之XGBoost算法

为树的总个数,

纯干货|Boosting家族之XGBoost算法

表示第

纯干货|Boosting家族之XGBoost算法

颗树,

纯干货|Boosting家族之XGBoost算法

表示样本

纯干货|Boosting家族之XGBoost算法

的预测结果。

损失函数为:

纯干货|Boosting家族之XGBoost算法

三、分析XGboost思路

首先明确下我们的目标,希望建立K个回归树,使得树群的预测值尽量接近真实值(准确率)而且有尽量大的泛化能力(更为本质的东西),从数学角度看这是一个泛函最优化,多目标,看下目标函数:

纯干货|Boosting家族之XGBoost算法

其中i表示第i个样本,

纯干货|Boosting家族之XGBoost算法

表示第i个样本的预测误差,误差越小越好,不然你算得上预测么?后面

纯干货|Boosting家族之XGBoost算法

表示树的复杂度的函数,越小复杂度越低,泛化能力越强,这意味着啥不用我多说。表达式为

纯干货|Boosting家族之XGBoost算法

T表示叶子节点的个数,w表示节点的数值(这是回归树的东西,分类树对应的是类别)

直观上看,目标要求预测误差尽量小,叶子节点尽量少,节点数值尽量不极端(这个怎么看,如果某个样本label数值为4,那么第一个回归树预测3,第二个预测为1;另外一组回归树,一个预测2,一个预测2,那么倾向后一种,为什么呢?前一种情况,第一棵树学的太多,太接近4,也就意味着有较大的过拟合的风险)

ok,听起来很美好,可是怎么实现呢,上面这个目标函数跟实际的参数怎么联系起来,记得我们说过,回归树的参数:(1)选取哪个feature分裂节点呢;(2)节点的预测值(总不能靠取平均值这么粗暴不讲道理的方式吧,好歹高级一点)。上述形而上的公式并没有“直接”解决这两个,那么是如何间接解决的呢?

先说答案:贪心策略+最优化(二次最优化)

通俗解释贪心策略:就是决策时刻按照当前目标最优化决定,说白了就是眼前利益最大化决定,“目光短浅”策略,他的优缺点细节大家自己去了解,经典背包问题等等。

这里是怎么用贪心策略的呢,刚开始你有一群样本,放在第一个节点,这时候T=1

T=1,w

w多少呢,不知道,是求出来的,这时候所有样本的预测值都是w

w(这个地方自己好好理解,决策树的节点表示类别,回归树的节点表示预测值),带入样本的label数值,此时loss function变为

纯干货|Boosting家族之XGBoost算法

如果这里的l(w−yi)误差表示用的是平方误差,那么上述函数就是一个关于w的二次函数求最小值,取最小值的点就是这个节点的预测值,最小的函数值为最小损失函数。

这里处理的就是二次函数最优化!

要是损失函数不是二次函数咋办,哦,泰勒展开式会否?,不是二次的想办法近似为二次。

接着来,接下来要选个feature分裂成两个节点,变成一棵弱小的树苗,那么需要:(1)确定分裂用的feature,how?最简单的是粗暴的枚举,选择loss function效果最好的那个(关于粗暴枚举,Xgboost的改良并行方式咱们后面看);(2)如何确立节点的w

w以及最小的loss function,大声告诉我怎么做?对,二次函数的求最值(细节的会注意到,计算二次最值是不是有固定套路,导数=0的点,ok)

那么节奏是,选择一个feature分裂,计算loss function最小值,然后再选一个feature分裂,又得到一个loss function最小值…你枚举完,找一个效果最好的,把树给分裂,就得到了小树苗。在分裂的时候,你可以注意到,每次节点分裂,loss function被影响的只有这个节点的样本,因而每次分裂,计算分裂的增益(loss function的降低量)只需要关注打算分裂的那个节点的样本。

接下来,继续分裂,按照上述的方式,形成一棵树,再形成一棵树,每次在上一次的预测基础上取最优进一步分裂/建树,是不是贪心策略?!

凡是这种循环迭代的方式必定有停止条件,什么时候停止呢:

(1)当引入的分裂带来的增益小于一个阀值的时候,我们可以剪掉这个分裂,所以并不是每一次分裂loss function整体都会增加的,有点预剪枝的意思,阈值参数为 γ 正则项里叶子节点数 T 的系数;

(2)当树达到最大深度时则停止建立决策树,设置一个超参数max_depth,这个好理解吧,树太深很容易出现的情况学习局部样本,过拟合;

(3)当样本权重和小于设定阈值时则停止建树,这个解释一下,涉及到一个超参数-最小的样本权重和min_child_weight,和GBM的 min_child_leaf 参数类似,但不完全一样,大意就是一个叶子节点样本太少了,也终止同样是过拟合;

(4)貌似看到过有树的最大数量的…这个不确定

那节点分裂的时候是按照哪个顺序来的,比如第一次分裂后有两个叶子节点,先裂哪一个?答:同一层级的(多机)并行,确立如何分裂或者不分裂成为叶子节点

四、原理推导

上面一部分我们知道了集成学习方法的预测模型,因为XGBoost也是集成学习方法的一种。对于XGBoost的预测模型同样可以表示为:

纯干货|Boosting家族之XGBoost算法

其中

纯干货|Boosting家族之XGBoost算法

为树的总个数,

纯干货|Boosting家族之XGBoost算法

表示第

纯干货|Boosting家族之XGBoost算法

颗树,

纯干货|Boosting家族之XGBoost算法

表示样本

纯干货|Boosting家族之XGBoost算法

的预测结果。

其中损失函数也同样表示为:

纯干货|Boosting家族之XGBoost算法

其中

纯干货|Boosting家族之XGBoost算法

为样本

纯干货|Boosting家族之XGBoost算法

的训练误差,

纯干货|Boosting家族之XGBoost算法

表示第

纯干货|Boosting家族之XGBoost算法

棵树的正则项。

看到了这里,我们可能会想到,现在知道了模型预测函数和损失函数,那我们是不是直接就能求出其预测模型了呢?答案肯定不是,我们首先需要明确知道优化和求解的参数是什么呢?由上面的预测模型中,我们可以看到对于每棵树的预测值

纯干货|Boosting家族之XGBoost算法

是如何计算的?想到这里,你就已经知道了需要做的事了,我需要求解和优化的就是每个叶子节点的得分值,也就是

纯干货|Boosting家族之XGBoost算法

的值。另外我们知道XGBoost是以CART树中的回归树作为基分类器,在给定训练数据后,其单个树的结构(叶子节点个数、树深度等等)基本可以确定了。但XGBoost并不是简单重复的将几个CART树进行组合。它是一种加法模型,将模型上次预测(由t-1棵树组合而成的模型)产生的误差作为参考进行下一棵树(第t棵树)的建立。以此,每加入一棵树,将其损失函数不断降低。如下图就为加法模型案例,它将模型预测值与实际值残差作为下一颗树的输入数据。

纯干货|Boosting家族之XGBoost算法

对于加法策略可以表示如下:

初始化(模型中没有树时,其预测结果为0):

纯干货|Boosting家族之XGBoost算法

往模型中加入第一棵树:

纯干货|Boosting家族之XGBoost算法

往模型中加入第二棵树:

纯干货|Boosting家族之XGBoost算法

往模型中加入第t棵树:

纯干货|Boosting家族之XGBoost算法

其中

纯干货|Boosting家族之XGBoost算法

表示第

纯干货|Boosting家族之XGBoost算法

棵树,

纯干货|Boosting家族之XGBoost算法

表示组合

纯干货|Boosting家族之XGBoost算法

棵树模型对样本

纯干货|Boosting家族之XGBoost算法

的预测结果。

我们知道,每次往模型中加入一棵树,其损失函数便会发生变化。另外在加入第t棵树时,则前面第t-1棵树已经训练完成,此时前面t-1棵树的正则项和训练误差都成已知常数项。对于每棵树的正则项部分,我们将在后面再细说。

纯干货|Boosting家族之XGBoost算法

如果损失函数采用均方误差时,其目标损失函数变为:

纯干货|Boosting家族之XGBoost算法

另外对于目标损失函数中的正则项(复杂度)部分,我们从单一的树来考虑。对于其中每一棵回归树,其模型可以写成:

纯干货|Boosting家族之XGBoost算法

其中

纯干货|Boosting家族之XGBoost算法

为叶子节点的得分值,

纯干货|Boosting家族之XGBoost算法

表示样本

纯干货|Boosting家族之XGBoost算法

对应的叶子节点。

纯干货|Boosting家族之XGBoost算法

为该树的叶子节点个数。

因此,在这里。我们将该树的复杂度写成:

纯干货|Boosting家族之XGBoost算法

复杂度计算例子如下:

纯干货|Boosting家族之XGBoost算法

此时,对于XGBoost的目标函数我们可以写为:

纯干货|Boosting家族之XGBoost算法

现在我们只需要找到f(t)来优化上式目标。

纯干货|Boosting家族之XGBoost算法

在推导之前,我们先介绍下泰勒展开式:

纯干货|Boosting家族之XGBoost算法

这里我们用泰勒展开式来近似原来的目标函数,将

纯干货|Boosting家族之XGBoost算法

看作

纯干货|Boosting家族之XGBoost算法

。则原目标函数可以写成:

纯干货|Boosting家族之XGBoost算法

纯干货|Boosting家族之XGBoost算法

纯干货|Boosting家族之XGBoost算法

,同时对于第t棵树时,

纯干货|Boosting家族之XGBoost算法

为常数。同时去除所有常数项。故目标损失函数可以写成:

纯干货|Boosting家族之XGBoost算法

由上面介绍书的复杂度时,我们知道:

纯干货|Boosting家族之XGBoost算法

,同时我们将目标函数全部转换成在第t棵树叶子节点的形式。因为目前对于

纯干货|Boosting家族之XGBoost算法

可以看做是每个样本在第t棵树的叶子节点得分值相关函数的结果之和,所以我们也能从第t棵树的叶子节点上来表示。

纯干货|Boosting家族之XGBoost算法

上式中,前两行 i=1~n 求和为在样本中遍历,后两行 j = 1~T求和为在叶子节点上遍历,其中

纯干货|Boosting家族之XGBoost算法

为第t棵树中总叶子节点的个数,

纯干货|Boosting家族之XGBoost算法

表示在第

纯干货|Boosting家族之XGBoost算法

个叶子节点上的样本,

纯干货|Boosting家族之XGBoost算法

为第

纯干货|Boosting家族之XGBoost算法

个叶子节点的得分值。

在这里,令

纯干货|Boosting家族之XGBoost算法

纯干货|Boosting家族之XGBoost算法

则:

纯干货|Boosting家族之XGBoost算法

纯干货|Boosting家族之XGBoost算法

求偏导,并使其导函数等于0,则有:

纯干货|Boosting家族之XGBoost算法

求解得:

纯干货|Boosting家族之XGBoost算法

其目标函数可以为:

纯干货|Boosting家族之XGBoost算法

根据目标函数,如何分裂样本数据呢

纯干货|Boosting家族之XGBoost算法

纯干货|Boosting家族之XGBoost算法

五、总结

1、Xgboost的一些重点

  • w是最优化求出来的,不是啥平均值或规则指定的,这个算是一个思路上的新颖吧;
  • 正则化防止过拟合的技术,上述看到了,直接loss function里面就有;
  • 支持自定义loss function,只要能泰勒展开(能求一阶导和二阶导)就行;
  • 支持并行化,这个地方有必要说明下,因为这是xgboost的闪光点,直接的效果是训练速度快,boosting技术中下一棵树依赖上述树的训练和预测,所以树与树之间应该是只能串行!那么大家想想,哪里可以并行?! 没错,在选择最佳分裂点,进行枚举的时候并行!(据说恰好这个也是树形成最耗时的阶段)

Attention:同层级节点可并行。具体的对于某个节点,节点内选择最佳分裂点,候选分裂点计算增益用多线程并行。—–

较少的离散值作为分割点倒是很简单,比如“是否是单身”来分裂节点计算增益是很easy,但是“月收入”这种feature,取值很多,从5k~50k都有,总不可能每个分割点都来试一下计算分裂增益吧?(比如月收入feature有1000个取值,难道你把这1000个用作分割候选?缺点1:计算量,缺点2:出现叶子节点样本过少,过拟合)我们常用的习惯就是划分区间,那么问题来了,这个区间分割点如何确定(难道平均分割),作者是这么做的:

方法名字:Weighted Quantile Sketch

大家还记得每个样本在节点(将要分裂的节点)处的loss function一阶导数gi和二阶导数hi,衡量预测值变化带来的loss function变化,举例来说,将样本“月收入”进行升序排列,5k、5.2k、5.3k、…、52k,分割线为“收入1”、“收入2”、…、“收入j”,满足(每个间隔的样本的hi之和/总样本的hi之和)为某个百分比ϵ(我这个是近似的说法),那么可以一共分成大约1/ϵ个分裂点。

  • XGBoost还特别设计了针对稀疏数据的算法

假设样本的第i个特征缺失时,无法利用该特征对样本进行划分,这里的做法是将该样本默认地分到指定的子节点,至于具体地分到哪个节点还需要某算法来计算,

算法的主要思想是,分别假设特征缺失的样本属于右子树和左子树,而且只在不缺失的样本上迭代,分别计算缺失样本属于右子树和左子树的增益,选择增益最大的方向为缺失数据的默认方向(咋一看如果缺失情况为3个样本,那么划分的组合方式岂不是有8种?指数级可能性啊,仔细一看,应该是在不缺失样本情况下分裂后,把第一个缺失样本放左边计算下loss function和放右边进行比较,同样对付第二个、第三个…缺失样本,这么看来又是可以并行的??)(答:论文中“枚举”指的不是枚举每个缺失样本在左边还是在右边,而是枚举缺失样本整体在左边,还是在右边两种情况。 分裂点还是只评估特征不缺失的样本。);

  • 可实现后剪枝
  • 交叉验证,方便选择最好的参数,early stop,比如你发现30棵树预测已经很好了,不用进一步学习残差了,那么停止建树。
  • 行采样、列采样,随机森林的套路(防止过拟合)
  • Shrinkage,你可以是几个回归树的叶子节点之和为预测值,也可以是加权,比如第一棵树预测值为3.3,label为4.0,第二棵树才学0.7,….再后面的树还学个鬼,所以给他打个折扣,比如3折,那么第二棵树训练的残差为4.0-3.3*0.3=3.01,这就可以发挥了啦,以此类推,作用是啥,防止过拟合,如果对于“伪残差”学习,那更像梯度下降里面的学习率;
  • xgboost还支持设置样本权重,这个权重体现在梯度g和二阶梯度h上,是不是有点adaboost的意思,重点关注某些样本

2、与GDBT、深度学习对比下 

Xgboost第一感觉就是防止过拟合+各种支持分布式/并行,所以一般传言这种大杀器效果好(集成学习的高配)+训练效率高(分布式),与深度学习相比,对样本量和特征数据类型要求没那么苛刻,适用范围广。

说下GBDT:有两种描述版本,把GBDT说成一个迭代残差树,认为每一棵迭代树都在学习前N-1棵树的残差;把GBDT说成一个梯度迭代树,使用梯度迭代下降法求解,认为每一棵迭代树都在学习前N-1棵树的梯度下降值。有说法说前者是后者在loss function为平方误差下的特殊情况。这里说下我的理解,仍然举个例子:第一棵树形成之后,有预测值ŷ i

y^i,真实值(label)为yi

yi,前者版本表示下一棵回归树根据样本(xi,yi−ŷ i)

(xi,yi−y^i)进行学习,后者的意思是计算loss function在第一棵树预测值附近的梯度负值作为新的label,也就是对应xgboost中的−gi

−gi

Xgboost和深度学习的关系,陈天奇在Quora上的解答如下:

不同的机器学习模型适用于不同类型的任务。深度神经网络通过对时空位置建模,能够很好地捕获图像、语音、文本等高维数据。而基于树模型的XGBoost则能很好地处理表格数据,同时还拥有一些深度神经网络所没有的特性(如:模型的可解释性、输入数据的不变性、更易于调参等)。

这两类模型都很重要,并广泛用于数据科学竞赛和工业界。举例来说,几乎所有采用机器学习技术的公司都在使用tree boosting,同时XGBoost已经给业界带来了很大的影响。

、XGboost参数解析

XGBoost 参数

在运行XGBoost程序之前,必须设置三种类型的参数:通用类型参数(general parameters)、booster参数和学习任务参数(task parameters)。

一般类型参数general parameters –参数决定在提升的过程中用哪种booster,常见的booster有树模型和线性模型。

Booster参数-该参数的设置依赖于我们选择哪一种booster模型。

学习任务参数task parameters-参数的设置决定着哪一种学习场景,例如,回归任务会使用不同的参数来控制着排序任务。

命令行参数-一般和xgboost的CL版本相关。

Booster参数:

1. eta[默认是0.3] 和GBM中的learning rate参数类似。通过减少每一步的权重,可以提高模型的鲁棒性。典型值0.01-0.2

2. min_child_weight[默认是1] 决定最小叶子节点样本权重和。当它的值较大时,可以避免模型学习到局部的特殊样本。但如果这个值过高,会导致欠拟合。这个参数需要用cv来调整

3. max_depth [默认是6] 树的最大深度,这个值也是用来避免过拟合的3-10

4. max_leaf_nodes 树上最大的节点或叶子的数量,可以代替max_depth的作用,应为如果生成的是二叉树,一个深度为n的树最多生成2n个叶子,如果定义了这个参数max_depth会被忽略

5. gamma[默认是0] 在节点分裂时,只有在分裂后损失函数的值下降了,才会分裂这个节点。Gamma指定了节点分裂所需的最小损失函数下降值。这个参数值越大,算法越保守。

6. max_delta_step[默认是0] 这参数限制每颗树权重改变的最大步长。如果是0意味着没有约束。如果是正值那么这个算法会更保守,通常不需要设置。

7. subsample[默认是1] 这个参数控制对于每棵树,随机采样的比例。减小这个参数的值算法会更加保守,避免过拟合。但是这个值设置的过小,它可能会导致欠拟合。典型值:0.5-1

8. colsample_bytree[默认是1] 用来控制每颗树随机采样的列数的占比每一列是一个特征0.5-1

9. colsample_bylevel[默认是1] 用来控制的每一级的每一次分裂,对列数的采样的占比。

10. lambda[默认是1] 权重的L2正则化项

11. alpha[默认是1] 权重的L1正则化项

12. scale_pos_weight[默认是1] 各类样本十分不平衡时,把这个参数设置为一个正数,可以使算法更快收敛。

通用参数:

1. booster[默认是gbtree]

选择每次迭代的模型,有两种选择:gbtree基于树的模型、gbliner线性模型

2. silent[默认是0]

当这个参数值为1的时候,静默模式开启,不会输出任何信息。一般这个参数保持默认的0,这样可以帮我们更好的理解模型。

3. nthread[默认值为最大可能的线程数]

这个参数用来进行多线程控制,应当输入系统的核数,如果你希望使用cpu全部的核,就不要输入这个参数,算法会自动检测。

学习目标参数:

1. objective[默认是reg:linear]

这个参数定义需要被最小化的损失函数。最常用的值有:binary:logistic二分类的逻辑回归,返回预测的概率非类别。multi:softmax使用softmax的多分类器,返回预测的类别。在这种情况下,你还要多设置一个参数:num_class类别数目。

2. eval_metric[默认值取决于objective参数的取之]

对于有效数据的度量方法。对于回归问题,默认值是rmse,对于分类问题,默认是error。典型值有:rmse均方根误差;mae平均绝对误差;logloss负对数似然函数值;error二分类错误率;merror多分类错误率;mlogloss多分类损失函数;auc曲线下面积。

3. seed[默认是0]

随机数的种子,设置它可以复现随机数据的结果,也可以用于调整参数。

文章参考:

1、https://blog.csdn.net/huibeng7187/article/details/77588001

2、https://blog.csdn.net/github_38414650/article/details/76061893

相关推荐