学习内容：

CART树

算法原理

损失函数

分裂结点算法

正则化

对缺失值处理

优缺点

应用场景

sklearn参数

---

转自：https://zhuanlan.zhihu.com/p/58221959

CART树

　　算法分类与回归树的英文是Classfication And Regression Tree，缩写为CART。CART算法采用二分递归分割的技术将当前样本集分为两个子样本集，使得生成的每个非叶子节点都有两个分支。非叶子节点的特征取值为True和False，左分支取值为True，右分支取值为False，因此CART算法生成的决策树是结构简洁的二叉树。CART可以处理连续型变量和离散型变量，利用训练数据递归的划分特征空间进行建树，用验证数据进行剪枝。

• 如果待预测分类是离散型数据，则CART生成分类决策树。
• 如果待预测分类是连续性数据，则CART生成回归决策树。

　　CART分类树

　　算法详解

　　CART分类树预测分类离散型数据，采用基尼指数选择最优特征，同时决定该特征的最优二值切分点。分类过程中，假设有K个类，样本点属于第k个类的概率为Pk，则概率分布的基尼指数定义为

　　根据基尼指数定义，可以得到样本集合D的基尼指数，其中Ck表示数据集D中属于第k类的样本子集。

　　如果数据集D根据特征A在某一取值a上进行分割，得到D1,D2两部分后，那么在特征A下集合D的基尼系数如下所示。其中基尼系数Gini(D)表示集合D的不确定性，基尼系数Gini(D,A)表示A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性越大。

　　对于属性A，分别计算任意属性值将数据集划分为两部分之后的Gain_Gini，选取其中的最小值，作为属性A得到的最优二分方案。然后对于训练集S，计算所有属性的最优二分方案，选取其中的最小值，作为样本及S的最优二分方案。

　　实例详解

　　

　　针对上述离散型数据，按照体温为恒温和非恒温进行划分。其中恒温时包括哺乳类5个、鸟类2个，非恒温时包括爬行类3个、鱼类3个、两栖类2个，如下所示我们计算D1,D2的基尼指数。

　　然后计算得到特征体温下数据集的Gini指数，最后我们选择Gain_Gini最小的特征和相应的划分。

　　CART回归树

　　算法详解

　　CART回归树预测回归连续型数据，假设X与Y分别是输入和输出变量，并且Y是连续变量。在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树

　　选择最优切分变量j与切分点s：遍历变量j，对规定的切分变量j扫描切分点s，选择使下式得到最小值时的(j,s)对。其中Rm是被划分的输入空间，cm是空间Rm对应的固定输出值。

　　用选定的(j,s)对，划分区域并决定相应的输出值

　　继续对两个子区域调用上述步骤，将输入空间划分为M个区域R1,R2,…,Rm，生成决策树。

　　当输入空间划分确定时，可以用平方误差来表示回归树对于训练数据的预测方法，用平方误差最小的准则求解每个单元上的最优输出值。

　　实例详解

　　考虑如上所示的连续性变量，根据给定的数据点，考虑1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5切分点。对各切分点依次求出R1,R2,c1,c2及m(s)，例如当切分点s=1.5时，得到R1={1},R2={2,3,4,5,6,7,8,9,10}，其中c1,c2,m(s)如下所示。

　　依次改变(j,s)对，可以得到s及m(s)的计算结果，如下表所示。

　　当x=6.5时，此时R1={1,2,3,4,5,6},R2={7,8,9,10},c1=6.24,c2=8.9。回归树T1(x)为

　　然后我们利用f1(x)拟合训练数据的残差，如下表所示

　　用f1(x)拟合训练数据得到平方误差

　　第二步求T2(x)与求T1(x)方法相同，只是拟合的数据是上表的残差。可以得到

　　用f2(x)拟合训练数据的平方误差

　　继续求得T3(x)、T4(x)、T5(x)、T6(x)，如下所示

　　用f6(x)拟合训练数据的平方损失误差如下所示，假设此时已经满足误差要求，那么f(x)=f6(x)便是所求的回归树。

　　CART剪枝

此处我们介绍代价复杂度剪枝算法

　　我们将一颗充分生长的树称为T0 ，希望减少树的大小来防止过拟化。但同时去掉一些节点后预测的误差可能会增大，那么如何达到这两个变量之间的平衡则是问题的关键。因此我们用一个变量α 来平衡，定义损失函数如下

• T为任意子树，|T|为子树T的叶子节点个数。
• α是参数，权衡拟合程度与树的复杂度。
• C(T)为预测误差，可以是平方误差也可以是基尼指数，C(T)衡量训练数据的拟合程度。

　　那么我们如何找到这个合适的α来使拟合程度与复杂度之间达到最好的平衡呢？准确的方法就是将α从0取到正无穷，对于每一个固定的α，我们都可以找到使得Cα(T)最小的最优子树T(α)。

• 当α很小的时候，T0 是这样的最优子树.
• 当α很大的时候，单独一个根节点就是最优子树。

　　尽管α的取值无限多，但是T0的子树是有限个。Tn是最后剩下的根结点，子树生成是根据前一个子树Ti，剪掉某个内部节点后，生成Ti+1。然后对这样的子树序列分别用测试集进行交叉验证，找到最优的那个子树作为我们的决策树。子树序列如下

　　因此CART剪枝分为两部分，分别是生成子树序列和交叉验证，在此不再详细介绍。

　　XGB原理

　　1.刚开始有一群样本，第一个节点这时候T=1，w多少呢，不知道，是求出来的，这时候所有样本的预测值都是w（决策树的节点表示类别，回归树的节点表示预测值）。如果这里的l(w−yi)误差表示用的是平方误差，那么此函数就是一个关于w的二次函数，求函数最小值的点就是这个节点的预测值。（通过泰勒展开求最小损失函数）

　　2.枚举每一个特征的损失，取loss最小值的feature作为分裂点，求出w1；然后进行下一个特征枚举，求出w2......（重复循环m步；其中yi就是y，即所有待分样本都要进行loss计算）

　　3......可以求出所有的w，有人会问什么时候停止计算呢？这个和设置参数有关，比如最大迭代次数，树的深度等等。这个知识点相对也比较多，后续讲优化详细说一下。

　　引申：

　　在第二步枚举每一个特征求损失时，是相当耗时的。然后XGB很好的支持了并行化===在选择最佳分裂点，进行枚举feature的时候并行！

　　贪心算法（相当于先剪枝）：当引入的分裂带来的增益小于一个阀值的时候，迭代停止。后剪枝：树建完之后再剪枝

---

　　xgboost是在GBDT的基础上对boosting算法进行的改进，内部决策树使用的是回归树，简单回顾GBDT如下：

　　回归树的分裂结点对于平方损失函数，拟合的就是残差；对于一般损失函数（梯度下降），拟合的就是残差的近似值，分裂结点划分时枚举所有特征的值，选取划分点。

　　最后预测的结果是每棵树的预测结果相加。

　　xgboost算法原理知识

　　3.1 定义树的复杂度

　　把树拆分成结构部分q和叶子权重部分w。

　　树的复杂度函数和样例：

　　定义树的结构和复杂度的原因很简单，这样就可以衡量模型的复杂度了啊，从而可以有效控制过拟合。

　　xgboost中的boosting tree模型

　　和传统的boosting tree模型一样，xgboost的提升模型也是采用的残差（或梯度负方向），不同的是分裂结点选取的时候不一定是最小平方损失。

　　损失函数

　　最终的目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数。这么写的原因很明显，由于之前的目标函数求最优解的过程中只对平方损失函数时候方便求，对于其他的损失函数变得很复杂，通过二阶泰勒展开式的变换，这样求解其他损失函数变得可行了。很赞！

　　当定义了分裂候选集合的时候，可以进一步改目标函数。分裂结点的候选响集是很关键的一步，这是xgboost速度快的保证，怎么选出来这个集合，后面会介绍。

　　求解

　　分裂结点算法

　　3.1 基础精确的贪心算法

　　方程（7）的关键问题是找到合适的分割，精确的贪心算法通过列举所有特征的可能划分找到最优划分解，许多单机Tree算法使用这种方式找到划分点，例如 sklearn、Rs gbm、单机的XGBoost。精确的算法需要排序成连续的特征，之后计算每个可能划分的梯度统计值，如算法1：

　　3.2 近似算法

　　精确通过列举特征所有可能的划分，耗时，当数据量大的时候，几乎不可能将数据全部加载进内存，精确划分在分布式中也会有问题。我们总结了近似的策略，如算法二所示，算法首先根据特征分布的百分比提议候选划分点，之后按照候选划分点将特征映射到槽中，找到最好的划分百分点。全局划分需要尽可能详细的特征划分，局部划分初步就能达到要求。在分布式树中许多存在的近似算法都使用这个策略，也可以直接构造直方图近似（lightGBM直方图近似，速度更快，好像准确度有所降低），也可以使用其他的策略而不仅仅是分位法，分位策略便于分布式实现、计算方便。

　　3.3 加权分位法

　　近似计算中重要的一步是提出候选的分位点，特征百分比通常作为分布式划分的依据。考虑多重集合，key-value 为第样本的（样本点的第K维特征， 二阶导数），定义排序函数:

　　表示小于z的点的比例，目标是找到划分点，，这样的划分点满足式（9）

，这样尽量做到均匀划分，hi作为每个数据点的权重的原因，方程（3）整理成平方差的形式，hi为label gi/hi的加权平方损失，对于大数据找到满足基准的划分点时意义重大的。

　　在以往的分位法中，没有考虑权值，许多存在的近似方法中，或者通过排序或者通过启发式方法（没有理论保证）划分。文章的贡献是提供了理论保证的分布式加权分位法。

　　3.4 稀疏自适应分割策略

　　在实际应用中，稀疏数据是不可避免的，造成稀疏数据的原因主要有：1 ，数据缺失。 2 ， 统计上的0 。 3 ， 特征表示中的one-hot形式，以往经验表明当出现稀疏、缺失值时时，算法需要很好的稀疏自适应。

　　当出现特征值缺失时，实例被映射到默认的方向分支，关键是访问非缺失实体对Ik。现在的算法处理不存在的作为缺失值，学到处理缺失的最好方向，算法通过枚举一致性情况同样适用于用户指定的值。现有的树系统仅仅优化稠密的数据或者专注于处理有限的任务，例如：分类编码。XGBoost通过一种统一的方式处理所有的稀疏性情况。当出现稀疏情况的时候，稀疏性计算只有线性的计算复杂度。如图所示，稀疏自适应算法比基本的非稀疏数据算法快大约50倍。

　　正则化

　　正则化目标函数

　　对于一个含n个训练样本，m个features的结定数据集：D=(xi,yi)(|D|=n,xi∈Rm,yi∈R)D=(xi,yi)(|D|=n,xi∈Rm,yi∈R)，所使用的tree ensemble model使用K次求和函数来预测输出：

yi^=ϕ(xi)=∑k=1Kfk(xi),fk∈Fyi^=ϕ(xi)=∑k=1Kfk(xi),fk∈F

…… (1)

　　其中，F=f(x)=wq(x)，满足(q:Rm→T,w∈RT)F=f(x)=wq(x)，满足(q:Rm→T,w∈RT)，是回归树(CART)的空间。q表示每棵树的结构，它会将一个训练样本实例映射到相对应的叶子索引上。T是树中的叶子数。每个fkfk对应于一个独立的树结构q和叶子权重w。与决策树不同的是，每棵回归树包含了在每个叶子上的一个连续分值，我们使用wiwi来表示第i个叶子上的分值。对于一个给定样本实例，我们会使用树上的决策规则(由q给定)来将它分类到叶子上，并通过将相应叶子上的分值(由w给定)做求和，计算最终的预测值。为了在该模型中学到这些函数集合，我们会对下面的正则化目标函数做最小化：

L(ϕ)=∑il(yi^,yi)+∑iΩ(fk)L(ϕ)=∑il(yi^,yi)+∑iΩ(fk)

……(2)

其中：Ω(f)=γT+12λ||ω||2Ω(f)=γT+12λ||ω||2

　　其中，ll是一个可微凸loss函数（differentiable convex loss function），可以计算预测值yi^yi^与目标值yiyi间的微分。第二项ΩΩ会惩罚模型的复杂度。正则项可以对最终学到的权重进行平滑，避免overfitting。相类似的正则化技术也用在RGF模型(正则贪婪树)上。XGBoost的目标函数与相应的学习算法比RGF简单，更容易并行化。当正则参数设置为0时，目标函数就相当于传统的gradient tree boosting方法。

　　对缺失值处理

　　通常情况下，我们人为在处理缺失值的时候大多会选用中位数、均值或是二者的融合来对数值型特征进行填补，使用出现次数最多的类别来填补缺失的类别特征。
很多的机器学习算法都无法提供缺失值的自动处理，都需要人为地去处理，但是xgboost模型却能够处理缺失值，也就是说模型允许缺失值存在。

　　原是论文中关于缺失值的处理将其看与稀疏矩阵的处理看作一样。在寻找split point的时候，不会对该特征为missing的样本进行遍历统计，只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找split point的时间开销。在逻辑实现上，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向进行分裂即可。可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率。如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子树。

　　优缺点

　　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的实现也有这个功能，两种算法在这一点上是一致的。

　　缺点：发布时间短（2014），工业领域应用较少，待检验　　

　　应用场景

　　分类、回归

　　sklearn参数

　　xgboost 有很多可调参数，具有极大的自定义灵活性。比如说：

（1）objective [ default=reg:linear ] 定义学习任务及相应的学习目标，可选的目标函数如下：

　　“reg:linear” –线性回归。

　　“reg:logistic” –逻辑回归。

　　“binary:logistic” –二分类的逻辑回归问题，输出为概率。

　　“multi:softmax” –处理多分类问题，同时需要设置参数num_class（类别个数）

（2）’eval_metric’ The choices are listed below，评估指标:

　　“rmse”: root mean square error

　　“logloss”: negative log-likelihood

　　(3)max_depth [default=6] 数的最大深度。缺省值为6 ，取值范围为：[1,∞]