XGBoost原理

决策树

决策树可以分为3类，采用不同的分裂标准，(1)采用信息增益，ID3算法。(2)采用信息增益率，c4.5算法。(3)采用基尼指数CART树。

CART树

XGBoost使用CART(Classification And Regression Tree, 分类回归树)作为基分类器。

基尼指数公式：

$$\operatorname { Gini } ( D ) = \sum _ { k = 1 } ^ { K } p _ { k } \left( 1 - p _ { k } \right)$$

基尼指数增益公式：

$$\operatorname { Gini } ( D , A ) = \frac { \left| D _ { 1 } \right| } { | D | } \operatorname { Gini } \left( D _ { 1 } \right) + \frac { \left| D _ { 2 } \right| } { | D | } \operatorname { Gini } \left( D _ { 2 } \right)$$

GBDT

XGBoost

目标函数，目标函数如下

$$\operatorname { Obj } ( t ) = \sum _ { i = 1 } ^ { n } L \left( y _ { i } , \hat { y } ^ { t - 1 } + f _ { t } \left( x _ { i } \right) \right) + \Omega \left( f _ { t } \right) + \text { constant }$$

其中constant是一个常数，$\Omega \left( f _ { t } \right)$为正则项。

正则项如下：

$$\Omega \left( f _ { t } \right) = \gamma T + \frac { 1 } { 2 } \lambda \sum _ { i = 1 } ^ { T } w _ { j } ^ { 2 }$$

优化目标函数是为了计算每个叶子节点的权重。

附录

• XGBoost比GradientBoost好的原因：
  1. 增加正则项，树越复杂，惩罚越大，防止over-fitting, 而GB没有惩罚项。
  2. 在迭代更新的时候，XGBoost采用了二阶导数(海瑟矩阵)，而GB只用了一阶导数(梯度)。
  3. XGBoost采用了并行计算，块处理，稀疏矩阵等技术。
  4. 节点分裂方式不同，gbdt使用gini指数，XGBoost是经过优化推导后的。

• XGBoost进化历程：

  决策树 -> 对样本重抽样，多棵树平均-> Tree Bagging -> 对特征进行随机挑选 -> 随机森林 -> 对随机森林中的树进行加权平均，而非简单平均 -> Boosting -> 对Boosting中的树进行正则化 -> XGBoost

对比模型：MART, DART(DART:Dropouts meet Multiple Additive Regression Trees), LightGBM, CatBoost