深入理解XGBoost

Introduction

XGBoost知识点

XGBoost相对于传统GBDT的优点

1）将正则项加入目标函数中，控制模型的复杂度，防止过拟合。
2）对目标函数进行二阶泰勒展开，同时用到了一阶导数和二阶导数。
3）实现了可并行的近似直方图算法。
4）实现了缩减和列采样（借鉴了GBDT和随机森林）。
5）实现了快速直方图算法，引入了基于loss-guide的树构建方法（借鉴了LightGBM）。
6）实现了求解带权值的分位数近似算法（weighted quantile sketch）。
7）可根据样本自动学习缺失值的分裂方向，进行缺失值处理。
8）数据预先排序，并以块（block）的形式保存，有利于并行计算。
9）采用缓存感知访问、外存块计算等方式提高数据访问和计算效率。
10）基于Rabit实现分布式计算，并集成于主流大数据平台中。
11）除CART作为基分类器外，XGBoost还支持线性分类器及LambdaMART排序模型等算法。
12）实现了DART，引入Dropout技术。

Cart实现原理

分类树的生成
基尼指数：

分类树生成的步骤：
1）从根节点开始分裂。
2）节点分裂之前，计算所有可能的特征及它们所有可能的切分点分裂后的基尼指数。
3）选出基尼指数最小的特征及其切分点作为最优特征和最优切分点。通过最优特征和最优切分点对节点进行分裂，生成两个子节点。
4）对新生成的子节点递归步骤2、3，直至满足停止条件。
5）生成分类树。

回归树的生成
回归树是预测值为连续值的决策树，一般将叶子节点所有样本的平均值作为该节点的预测值。CART算法生成回归树的方法与生成分类树的不同，不再通过基尼指数进行特征选择，而是采用平方误差最小化。平方误差的定义如下：

回归树的生成步骤如下:
1）从根节点开始分裂。
2）节点分裂之前，计算所有可能的特征及它们所有可能的切分点分裂后的平方误差。
3）如果所有的平方误差均相同或减小值小于某一阈值，或者节点包含的样本数小于某一阈值，则分裂停止；否则，选择使平方误差最小的特征和切分点作为最优特征和最优切分点进行分裂，生成两个子节点。
4）对于每一个生成的新节点，递归执行步骤2、步骤3，直至满足停止条件。XGBoost中采用的决策树（即回归树），因而决策树的生成过程与上述过程类似.

Gradient Boosting

Gradient Tree Boosting

XGBoost Gradient Boosting Tree

目标函数近似：

公式中： 为第s-1轮样本的模型预测值,为第s轮训练的新子模型。

XGBoost引入泰勒公式来近似和简化目标函数。首先来看一下泰勒公式的定义。泰勒公式是一个用函数某点的信息描述其附近取值的公式，如果函数曲线足够平滑，则可通过某一点的各阶导数值构建一个多项式来近似表示函数在该点邻域的值。此处只取泰勒展开式的两阶，定义如下：



最优目标函数和叶子权重



简要概括

Summary

还是要多复习