先导知识

1. 决策树

举个粗糙一点的例子：

给你一堆人的某些特征，如“性别”、“年龄”、“收入”等，然后让你预测这个人是否能购买得起一台车。

那么决策树就是挑一个特征，把所有样本按这个特征分为几拨，每拨样本根据一个规则为它们打一个标签作为输出。比如将所有样本按“性别”分为“男”和“女”，将所有性别是“男”的人放在一个叶子结点上，所有性别是“女”的人放在一个叶子结点上，“男”的叶子结点的输出结果就是男性实例中最多的类（买车的比没买车的多，就是“是”，否则就是“否”）。对性别是“女”的叶子结点做同样的操作。当然，如果觉得根据一个特征就进行预测了不够，可以对这两个叶子结点继续用其他的特征进行分裂，直到满意了为止。

因此，可以看出，决策树有以下的几个关键点：

• （特征选择）“挑一个特征”——先用什么特征分裂？为什么是“性别”？“收入”可以么？

  重要概念：熵、信息增益、信息增益比、Gini系数。

• （决策树生成）“几拨”——年龄有很多值，每个值都要分一个叶子结点？还是分成2段？或者3段？

  重要方法：ID3（信息增益、非二叉）、C4.5（信息增益比、非二叉）、CART*（二叉、分类回归树、Gini系数）

• （决策树剪枝）“满意了”——树越大越好么？分裂到什么时候结束？

2. Tree Ensemble 树集成

树集成就是用构建一堆决策树来进行预测。具体怎么利用这一大堆树，分为bagging和boosting两种方法：

• bagging：从多个决策树中选最好的结果，作为这堆树的代表。
• boosting：组合多个决策树的结果。

3. Boosting

Boosting的思想很简单。比如，我想跟朋友借一笔钱，不知怎么的，他手一抖，就给我了900。那我就不乐意了，就跟他说，“这不够1000啊”。他一看厚度，还真不够1000，然后就给我多掏了50。我又不乐意了，“还是不够”。这哥们又掏掏兜，掏出了一个皱皱巴巴的20。我看看他，他看看我，他羞涩的笑了，然后脱了鞋从鞋里拿出了20，味道清新又迷人。最后，在我的软磨硬泡之下，他又从他女朋友那借了10块给我，终于凑够了1000。

Boosting的思想类似，就是不断地添加分类器，让这个分类器的结果逼近最终目标。

XGBoost理论

XGBoost利用CART树进行树集成，每个叶子结点的输出权重代表其是某一类别的分值。预测时，对每个样本，将其映射到每个树的叶子结点，对这些叶子结点的权重加和作为输出。如下图：

XGBoost目标函数=损失函数+正则项：

$\mathcal{L} = \sum_il(\hat{y_i},y_i)+\sum_k\Omega(f_k)$L=i∑​l(yi​^​,yi​)+k∑​Ω(fk​)

$\Omega(f) = \gamma T+\frac{1}{2}\lambda||\omega||^2$Ω(f)=γT+21​λ∣∣ω∣∣2

优化目标函数，即加一个新树ft，使目标函数最小。即对于每一种可能的树，计算新树的结构和最终树结点的权值。具体的推导过程如下：（1）泰勒展开（2）消去常数（3）将正则项带入（4）换成对叶子结点迭代计算：

$\mathcal{L}^{(t)} \approx\sum^n_{i=1}l(y_i,\hat{y}^{(t-1)}+f_t(x_i))+\Omega(f_t)$L(t)≈i=1∑n​l(yi​,y^​(t−1)+ft​(xi​))+Ω(ft​)

$(1): \ \ = \sum^n_{i=1}[l(y_i,\hat{y}^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i))]+\Omega(f_t)$(1):  =i=1∑n​[l(yi​,y^​(t−1))+gi​ft​(xi​)+21​hi​ft2​(xi​))]+Ω(ft​)

$(2): \ \ = \sum^n_{i=1}[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i))]+\Omega(f_t)$(2):  =i=1∑n​[gi​ft​(xi​)+21​hi​ft2​(xi​))]+Ω(ft​)

$(3): \ \ = \sum^n_{i=1}[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i))]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}\omega_j^2$(3):  =i=1∑n​[gi​ft​(xi​)+21​hi​ft2​(xi​))]+γT+21​λj=1∑T​ωj2​

$(4): \ \ = \sum_{j=1}^{T}[(\sum_{i \in I_j}g_i)\omega_j+\frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)\omega_j^2]+\gamma T$(4):  =j=1∑T​[(i∈Ij​∑​gi​)ωj​+21​(i∈Ij​∑​hi​+λ)ωj2​]+γT

最终：

$w^*_j = -\frac{\sum_{i \in I_j}g_i}{\sum_{i \in I_j}h_i+\lambda}$wj∗​=−∑i∈Ij​​hi​+λ∑i∈Ij​​gi​​

$\hat{\mathcal{L}}^{(t)}(q) = -\frac{1}{2}\sum_{j=1}^T\frac{(\sum_{i \in I_j}g_i)^2}{\sum_{i \in I_j}h_i+\lambda}+\gamma T$L^(t)(q)=−21​j=1∑T​∑i∈Ij​​hi​+λ(∑i∈Ij​​gi​)2​+γT

计算过程举例如下：

由于对所有的树结构进行遍历不现实，因此，可以从单叶子结点进行迭代。具体的，从一个叶子结点出发，对这个叶子结点上每一个属性的所有样本进行排序，对每一个该属性下可能的分割点计算gain，最大的gain对应的属性和分割点对儿，作为本次分割的条件。gain的计算如下所示，小于γ的可以直接不看了。

$\mathcal{L}_{split} = \frac{1}{2}[\frac{(\sum_{i\in I_L}g_i)^2}{\sum_{i\in I_L}h_i+\lambda}+\frac{(\sum_{i\in I_R}g_i)^2}{\sum_{i\in I_R}h_i+\lambda}-\frac{(\sum_{i\in I}g_i)^2}{\sum_{i\in I}h_i+\lambda}]-\gamma$Lsplit​=21​[∑i∈IL​​hi​+λ(∑i∈IL​​gi​)2​+∑i∈IR​​hi​+λ(∑i∈IR​​gi​)2​−∑i∈I​hi​+λ(∑i∈I​gi​)2​]−γ

XGBoost重要参数

• General Parameters 一般参数
  • booster：gbtree, gblinear or dart;
  • silent：是否打印运行消息
  • nthread：并行线程数
• Booster parameters 提升器参数
  • Parameters for Tree Booster 树提升器参数
    • eta：学习率（越小越泛）
    • gamma：最小分割损失（越大越泛）
    • max_depth：最大深度（越小越泛）
    • min_child_weight：最小孩子权重（大越泛）
    • lambda：L2正则项（越大越泛）
    • tree_method：树算法（贪婪 or 近似）
  • Additional parameters for Dart Booster (booster=dart) dart树提升器参数
  • Parameters for Linear Booster (booster=gblinear) 线性提升器参数
  • Parameters for Tweedie Regression (objective=reg:tweedie) Tweedie回归提升器参数
• Learning Task Parameters 学习任务参数
  • objective：目标
  • eval_metric：评价矩阵
• Command Line Parameters 命令行参数