Xgboost的建树过程

Xgboost是很多CART回归树集成

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

回归树是个啥呢?

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

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

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

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

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

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

是时候看看Xgboost了

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

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

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

先说答案：贪心策略+最优化(二次最优化，恩你没看错)

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

这里是怎么用贪心策略的呢，刚开始你有一群样本，放在第一个节点，这时候T=1，w多少呢，不知道，是求出来的，这时候所有样本的预测值都是w(这个地方自己好好理解，决策树的节点表示类别，回归树的节点表示预测值),带入样本的label数值，此时loss function变为

暂停下，这里你发现了没，二次函数最优化!

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

接着来，接下来要选个feature分裂成两个节点，变成一棵弱小的树苗，那么需要：

(1)确定分裂用的feature，how?最简单的是粗暴的枚举，选择loss function效果最好的那个(关于粗暴枚举，Xgboost的改良并行方式咱们后面看)

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

那么节奏是，选择一个feature分裂，计算loss function最小值，然后再选一个feature分裂，又得到一个loss function最小值…你枚举完，找一个效果最好的，把树给分裂，就得到了小树苗。

在分裂的时候，你可以注意到，每次节点分裂，loss function被影响的只有这个节点的样本，因而每次分裂，计算分裂的增益(loss function的降低量)只需要关注打算分裂的那个节点的样本。原论文这里会推导出一个优雅的公式，我不想敲latex公式了，

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

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

(1)当引入的分裂带来的增益小于一个阀值的时候，我们可以剪掉这个分裂，所以并不是每一次分裂loss function整体都会增加的，有点预剪枝的意思(其实我这里有点疑问的，一般后剪枝效果比预剪枝要好点吧，只不过复杂麻烦些，这里大神请指教，为啥这里使用的是预剪枝的思想，当然Xgboost支持后剪枝)，阈值参数为γ正则项里叶子节点数T的系数(大神请确认下);

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

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

看下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/ϵ个分裂点。

数学形式，我再偷懒下(可是latex敲这种公式真的很头疼)：

而且，有适用于分布式的算法设计;

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的意思，重点关注某些样本。

看下Xgboost的工程优化

这部分因为没有实战经验，都是论文、博客解读来的，所以也不十分确定，供参考。

Column Block for Parallel Learning 总的来说：按列切开，升序存放; 方便并行，同时解决一次性样本读入炸内存的情况

由于将数据按列存储，可以同时访问所有列，那么可以对所有属性同时执行split finding算法，从而并行化split finding(切分点寻找)-特征间并行 可以用多个block(Multiple blocks)分别存储不同的样本集，多个block可以并行计算-特征内并行

Blocks for Out-of-core Computation 数据大时分成多个block存在磁盘上，在计算过程中，用另外的线程读取数据，但是由于磁盘IO速度太慢，通常更不上计算的速度， 将block按列压缩，对于行索引，只保存第一个索引值，然后只保存该数据与第一个索引值之差(offset)，一共用16个bits来保存 offset，因此，一个block一般有2的16次方个样本。

与GDBT、深度学习对比下

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

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

Xgboost和深度学习的关系，陈天奇在Quora上的解答如下： 不同的机器学习模型适用于不同类型的任务。深度神经网络通过对时空位置建模，能够很好地捕获图像、语音、文本等高维数据。而基于树模型的XGBoost则能很好地处理表格数据，同时还拥有一些深度神经网络所没有的特性(如：模型的可解释性、输入数据的不变性、更易于调参等)。 这两类模型都很重要，并广泛用于数据科学竞赛和工业界。举例来说，几乎所有采用机器学习技术的公司都在使用tree boosting，同时XGBoost已经给业界带来了很大的影响。

xgboost算法原理与实战

之前一直有听说GBM，GBDT(Gradient Boost Decision Tree)渐进梯度决策树GBRT(Gradient Boost RegressionTree)渐进梯度回归树是GBDT的一种，因为GBDT核心是累加所有树的结果作为最终结果，而分类树的结果是没法累加的，所以GBDT中的树都是回归树，不是分类树。

XGBoost(eXtreme Gradient Boosting)是工业界逐渐风靡的基于GradientBoosting算法的一个优化的版本，可以给预测模型带来能力的提升。

回归树的分裂结点对于平方损失函数，拟合的就是残差;对于一般损失函数(梯度下降)，拟合的就是残差的近似值，分裂结点划分时枚举所有特征的值，选取划分点。 最后预测的结果是每棵树的预测结果相加。

xgboost算法的步骤和GB基本相同，都是首先初始化为一个常数，gb是根据一阶导数ri，xgboost是根据一阶导数gi和二阶导数hi，迭代生成基学习器，相加更新学习器。

xgboost的优化：

在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。

xgboost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper提到50倍.

特征列排序后以块的形式存储在内存中，在迭代中可以重复使用;虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。

按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer，然后再计算，提高算法的效率。

xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。

xgboost的优势：

1、正则化

标准GBM的实现没有像XGBoost这样的正则化步骤。正则化对减少过拟合也是有帮助的。

实际上，XGBoost以“正则化提升(regularized boosting)”技术而闻名。

2、并行处理

XGBoost可以实现并行处理，相比GBM有了速度的飞跃，LightGBM也是微软最新推出的一个速度提升的算法。 XGBoost也支持Hadoop实现。

3、高度的灵活性

XGBoost 允许用户定义自定义优化目标和评价标准 。

4、缺失值处理

XGBoost内置处理缺失值的规则。用户需要提供一个和其它样本不同的值，然后把它作为一个参数传进去，以此来作为缺失值的取值。XGBoost在不同节点遇到缺失值时采用不同的处理方法，并且会学习未来遇到缺失值时的处理方法。

5、剪枝

当分裂时遇到一个负损失时，GBM会停止分裂。因此GBM实际上是一个贪心算法。XGBoost会一直分裂到指定的最大深度(max_depth)，然后回过头来剪枝。如果某个节点之后不再有正值，它会去除这个分裂。

这种做法的优点，当一个负损失(如-2)后面有个正损失(如+10)的时候，就显现出来了。GBM会在-2处停下来，因为它遇到了一个负值。但是XGBoost会继续分裂，然后发现这两个分裂综合起来会得到+8，因此会保留这两个分裂。

6、内置交叉验证

XGBoost允许在每一轮boosting迭代中使用交叉验证。因此，可以方便地获得最优boosting迭代次数。

而GBM使用网格搜索，只能检测有限个值。

7、在已有的模型基础上继续

XGBoost可以在上一轮的结果上继续训练。

sklearn中的GBM的实现也有这个功能，两种算法在这一点上是一致的。

xgboost在kaggle上的实战：

Kaggle是一个数据分析的竞赛平台，企业或者研究者可以将数据、问题描述、期望的指标发布到Kaggle上，以竞赛的形式向广大的数据科学家征集解决方案，类似于KDD-CUP(国际知识发现和数据挖掘竞赛)。Kaggle上的参赛者将数据下载下来，分析数据，然后运用机器学习、数据挖掘等知识，建立算法模型，解决问题得出结果，最后将结果提交。

kaggle最近刚被google收购，感觉一大批Google赛题即将到达战场。kaggle上的很多预测模型都是基于xgboost，而且往往预测结果非常理想。下面是用法：

xgb_params = {

‘eta’: 0.05,

‘max_depth’: 5,

‘subsample’: 0.7,

‘colsample_bytree’: 0.7,

‘objective’: ‘reg:linear’,

‘eval_metric’: ‘rmse’,

‘silent’: 1

}

//xgboost加载数据为DMatrix对象

dtrain = xgb.DMatrix(x_train, y_train)

dtest = xgb.DMatrix(x_test)

//xgboost交叉验证并输出rmse

cv_output = xgb.cv(xgb_params, dtrain, num_boost_round=100, early_stopping_rounds=20,

verbose_eval=50, show_stdv=False)

cv_output[[‘train-rmse-mean’, ‘test-rmse-mean’]].plot()

这里写图片描述

//xgboost训练模型

num_boost_rounds = len(cv_output)

model = xgb.train(dict(xgb_params, silent=0), dtrain, num_boost_round= num_boost_rounds)

//xgboost参数设置

params 这是一个字典，里面包含着训练中的参数关键字和对应的值，形式是params =

{‘booster’:’gbtree’,’eta’:0.1}

dtrain 训练的数据

num_boost_round 这是指提升迭代的个数

evals 这是一个列表形式是evals = [(dtrain,’train’),(dval,’val’)]或者是evals =

[(dtrain,’train’)],对于第一种情况，它使得我们可以在训练过程中观察验证集的效果

obj,自定义目的函数

feval,自定义评估函数

maximize ,是否对评估函数进行最大化

early_stopping_rounds,早期停止次数假设为100，验证集的误差迭代到一定程度在100次内不能再继续降低，就停止迭代

verbose_eval ,如果为True,则evals中元素的评估结果会输出在结果中;如果输入数字，假设为5，则每隔5个迭代输出一次。

learning_rates 每一次提升的学习率

xgb_model ,在训练之前用于加载的xgb model

//显示xgboost模型中比较重要的几个feature

featureImportance = model.get_fscore()

features = pd.DataFrame()

features[‘features’] = featureImportance.keys()

features[‘importance’] = featureImportance.values()

features.sort_values(by=[‘importance’],ascending=False,inplace=True)

fig,ax= plt.subplots()

fig.set_size_inches(20,10)

plt.xticks(rotation=60)

sn.barplot(data=features.head(30),x=”features”,y=”importance”,ax=ax,orient=”v”)