基础知识

一、决策树

1. 决策树的定义

 分类决策树模型是一种描述对实例进行分类的树形结构，决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。

2.决策树是怎么工作的

 决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个都没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。

3.决策树的构建方法

决策树学习的策略是以损失函数为目标函数的最小化。

(1) 构建根结点，将所有的训练数据都放在根结点。
(2) 选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个当前条件下最好的分类。
(3) 如果这些子集已经能够被基本正确分类，那么构建 叶结点，并将这些子集分到所对应的叶结点去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。
(4) 如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一颗决策树。

4. 常见的决策树构建算法

• ID3使用信息增益作为选择特征的准则；
• C4.5使用信息增益比作为选择特征的准则
• CART使用Gini指数作为选择特征的准则

5. 决策树生成的三个重要问题

• 如何选择分裂的特征
• 数据如何分割
• 什么时候停止分裂

6. 特征选择问题

直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益（information gain)可以很好地表示这一直观的准则。

(1) 熵—随机变量不确定性的度量

 设X是一个取有限值的离散随机变量，其概率分布为：
$$P(X=x_i)=p_i$$
则随机变量X的熵定义为：
$$H(X)=-\sum _{i=1}^n{p}_{i}log{p}_i$$
熵越大，随机变量的不确定性就越大
由定义可知，熵只依赖于X的分布，而与X的取值无关，则可将X的熵记作$H(p)$,即
$$H(p)=-\sum _{i=1}^n{p}_{i}log{p}_i$$

(2) 条件熵

表示在已知随机变量X的条件下随机变量Y的不确定性。

随机变量X给定的条件下随机变量Y的条件熵（conditional entropy）$H(Y|X)$,定义为X给定条件下Y的条件概率分布的熵对X的数学期望。
$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i)$$

(3) 信息增益

表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

定义：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
$$g(D,A)=H(D)-H(D|A)$$
一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息

(4) 信息增益的算法

基于信息增益准则 的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

设训练数据集为D，|D|表示其样本个数。设有K个类$C_k,k=1,2,...,K,C_k为属于类C_k的样本个数，{\sum }_{k=1}^K{C}_k=|D|.$

$设特征A有n个不同的取值a_1,a_2,...,a_n，$$根据特征A的取值将D划分为n个子集D_1,D_2,...,D_n,|D_i|为D_i的样本个数，{\sum }_{i=1}^n$
$记子集D_i中属于类C_k的样本集合为D_{ik},即D_{i}k=D_i\cap C_k,|D_{i}k|为D_{ik}的样本个数。$
输入：训练数据集D和特征A
输出：特征A对训练数据集D的信息增益g(D,A)

(1) 计算数据集D的经验熵H(D)
$$H(D)=-\sum _{k=1}^K\frac{|C_k|}{|D|}lo{g}_2\frac{|C_k|}{|D|}$$
(2) 计算特征A对数据集D的经验条件熵H(D|A)

$$H(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{|D_i|}lo{g}_2\frac{|D_{ik}|}{|D_i|}$$
(3) 计算信息增益
$$g(D,A)=H(D)-H(D|A)$$

• 一个例子（统计学习方法缩减版）

贷款申请样本数据表

ID	年龄	有工作	信贷情况	类别
1	青年	否	一般	否
2	青年	是	好	否
3	青年	是	好	是
4	中年	否	好	是
5	青年	是	一般	否
6	中年	否	一般	否
7	老年	是	一般	否
8	老年	是	一般	是

解： 首先计算经验熵H(D)
$$H(D)=-\frac{5}{8}lo{g}_2\frac{5}{8}-\frac{3}{8}lo{g}_2\frac{3}{8}=0.9544$$
然后计算各特征对数据集D的信息增益。分别以$A_1$,$A_2$,$A_2$,$A_3$表示年龄、有工作、信贷情况3个特征，则

(1)
$$\begin{gathered} g(D,A_1)=H(D)-[\frac{4}{8}H(D_1)+\frac{2}{8}H(D_2)+\frac{2}{8}H(D_3)] \\ =H(D)-[\frac{4}{8}(-\frac{3}{4}lo{g}_2\frac{3}{4}-\frac{1}{4}lo{g}_2\frac{1}{4})+ \\ \frac{2}{8}(-\frac{1}{2}lo{g}_2\frac{1}{2}-\frac{1}{2}lo{g}_2\frac{1}{2})+ \\ \frac{2}{8}(-\frac{1}{2}lo{g}_2\frac{1}{2}-\frac{1}{2}lo{g}_2\frac{1}{2})]=0.0871 \end{gathered}$$
这里$D_1,D_2,D_3$分别是D中$A_1$（年龄）取值为青年、中年和老年的样本子集。

(2)
$$\begin{gathered} g(D,A_2)=H(D)-[\frac{3}{8}H(D_1)+\frac{5}{8}H(D_2)] \\ =H(D)-[\frac{3}{8}(-\frac{1}{3}lo{g}_2\frac{1}{3}-\frac{2}{3}lo{g}_2\frac{2}{3})+ \\ \frac{5}{8}(-\frac{3}{5}lo{g}_2\frac{3}{5}-\frac{2}{5}lo{g}_2\frac{2}{5})]= \\ 0.0880 \end{gathered}$$

(3)
$$\begin{gathered} g(D,A_3)=H(D)-[\frac{5}{8}H(D_1)+\frac{3}{8}H(D_2)] \\ =H(D)-[\frac{5}{8}(-\frac{1}{5}lo{g}_2\frac{1}{5}-\frac{4}{5}lo{g}_2\frac{4}{5})+ \\ \frac{3}{8}(-\frac{2}{3}lo{g}_2\frac{2}{3}-\frac{1}{3}lo{g}_2\frac{1}{3})]= \\ 0.2037 \end{gathered}$$
最后，比较各特征的信息增益值。由于特征$A_3$(信贷情况)的信息增益值最大，所以选择特征$A_3$作为最优特征。

(4) 信息增益比

  以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比(information gain ratio)可以对这一问题进行校正。这是特征选择的另一准则。

特征A对训练数据集D的信息增益比$g_R(D,A)$ 定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵$H_A(D)$ 之比，即

$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$
其中，$H_A(D)=-{\sum }_{i=1}^n\frac{|D_i|}{|D|}lo{g}_2\frac{|D_i|}{|D|}$,n是特征A取值的个数。

7. 决策树的生成

(1) ID3算法思想

 算法核心思想：在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法， 构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一颗决策树。ID3相当于用极大似然法进行概率模型的选择。

(2) ID3算法

输入：训练数据集D,特征集A阈值 $ϵ$
输出： 决策树T

(1) 若D中所有实例属于同一类$C_k$,则T为单结点树，并将类$C_k$作为该结点的类标记，返回T。

(2) 若A=$\varnothing$,则T为单结点树，并将D中实例数最大的类$C_k$作为该结点的类标记，返回T。

(3) 否则，计算A中各特征对D的信息增益，选择信息增益最大的特征$A_g$。

(4) 如果$A_g$的信息增益小于阈值 $\epsilon$,则置T为单结点树，并将D中实例数最大的类$C_k$作为该结点的类标记，返回T;

(5) 否则，对$A_g$的每一可能值$a_i$,依$A_g=a_i$将D分割为若干非空子集$D_i$,将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T,返回T;

(6) 对$i$个子结点，以$D_i$为训练集，以$A-A_g$ 为特征集，递归地调用步(1)~步(5)，得到子树$T_i$,返回$T_i$
由于ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。

8. C4.5的生成算法

输入： 训练数据集D,特征集A阈值 $\epsilon$;

输出： 决策树T

(1) 如果D中所有实例属于同一类$C_k$,则置T为单结点树，并将$C_k$作为该结点的类，返回T;

(2) 如果$A=\varnothing$,则置T为单结点树，并将D中实例数最大的类 $C_k$作为该结点的类，返回T;

(3) 否则，计算A中各特征对D的信息增益比，选择信息增益比最大的类 $C_k$ 作为该结点的类，返回T；

(4) 如果$A_g$的信息增益比小于阈值 $\epsilon$, 则置T为单结点树，并将D中实例数最大的类 $C_k$ 作为该结点的类，返回T

(5) 否则，对$A_g$的每一可能值$a_i$,依$A_g=a_i$将D分割为子集若干非空$D_i$,将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T,返回T

(6) 对结点i,以$D_i$为训练集，以$A-A_g$ 为特征集，递归地调用步(1)~(5),得到子树 $T_i$

9. 决策树过拟合的避免—剪枝算法

决策树的剪枝通过极小化决策树整体的损失函数或代价函数来实现。设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有$N_t$个样本点，其中$k$类的样本点有$N_{tk}$ 个，$k=1,2,...,K,H_t(T)$ 为叶结点t上的经验熵, $\alpha \ge 0$为参数，则决策树学习的损失函数可以定义为

$$C_{\alpha }(T)=\sum _{i=1}^{|T|}{N}_t{H}_t(T)+\alpha |T|$$
其中经验熵为
$$H_t(T)=-\sum _K\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$$

10. XGBoost: A Scalable Tree Boosting System

Abstract

1. XGBoost算法：一种新的稀疏感知算法，用于稀疏数据和用于近似数学习的加权分位数草图。
2. 比当时流行解决方案快十倍以上，在分布式或内存有限的设置下可以扩展到数十亿个示例。

Introduction

1. Innovation

• 新的树学习算法用于处理稀疏数据
• 理论上合理的加权分位草图过程使得能够在近似树学习中处理实例权重
• 并行和分布式计算

2. Contribution

• 设计并构建了一个高度可扩展的端到端树增强系统
• 提出了一种理论上合理的加权分位数略图，用于高效的建议的计算
• 提出了一种有效的基于缓存感知的核外树学习块结构

3. Regularized Learning Objective
   (1) 对于含有m个特征n个样例的数据集 D={(xi,yi)}(∣D∣=n,xi∈Rm,yi∈R)\mathcal{D}=\{(x_i, y_i)\} (|\mathcal{D}| = n, x_i \in \mathbb{R}^m, y_i \in \mathbb{R})D={(xi​,yi​)}(∣D∣=n,xi​∈Rm,yi​∈R), 集成模型使用K个加法函数以预测输出。
   $\widehat{y_i}=\varphi (x_i)={\sum }_{k=1}^K{f}_k(X_i),f_k\in \mathcal{F}$
   F={f(x)=w(q(x))}(q:Rm)→T,ω∈RT\mathcal{F} = \{f(x) = w_(q(x))\}(q: \mathbb{R}^m)\rightarrow T, \omega \in \mathbb{R}^TF={f(x)=w(​q(x))}(q:Rm)→T,ω∈RT. q表示将示例映射到相应叶索引的每个树的结构。 T是树中叶子结点的数量。每一个$f_k$对应于一个独立的树结构q和叶子权重$\omega$。使用$w_i$表示第i个叶子结点的分数。
   （2） 目标函数
   $\mathcal{L}(\varphi )={\sum }_{i}l({\hat{y}}_i,y_i)+{\sum }_k\Omega (f_k)$
   其中 $\Omega (f)=\gamma T+\frac{1}{2}\lambda ||\omega |{|}^2$
   其中，$l$测量预测${\hat{y}}_i$和目的$y_i$之间的差的可微凸损失函数。第二个为惩罚项。

XGBoost算法详解

1.与GBDT算法不同—目标函数

$Ob{j}^{(t)}={\sum }_{i=1}^{n}l(y_i,{\hat{y}}_i^{(t-1)}+f_t(x_i))+\Omega (f_t)+constant$
用泰勒展开式来近似我们原来的目标：
$f(x+\Delta x)\simeq f(x)+f^{\prime }(x)\Delta x+\frac{1}{2}{f}^{\prime \prime }(x)\Delta x^2$
$define:g_i={\partial }_{{\hat{y}}^{(t-1)}}l(y_i,{\hat{y}}^{(t-1)}),h_i={\partial }_{{\hat{y}}^{(t-1)}}^{2}l(y_i,{\hat{y}}^{(t-1)})$
$Ob{j}^{(t)}\simeq {\sum }_{i=1}^n[l(y_i,{\hat{y}}_i^{(t-1)})+g_i{f}_t^2(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\Omega (f_t)+constant$

2. XGBoost的核心算法思想

(1) 不断添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数f(x)，去拟合上次预测的残差。
(2) 当我们训练完成得到k颗树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数。
(3) 最后只需要将每棵树对应的分数加起来就就是该样本的预测值。
XGBoost需要将多棵树的得分累加得到最终的预测得分（每次迭代，都在现有树的基础上，增加一棵树去拟合前面树的预测结果与真实值之间的残差）

那么接下来，选取一个f使得我们的目标函数尽量最大地降低，f可以使用泰勒展开公式近似。

实质是把样本分配到叶子结点会对应一个obj，优化过程就是obj优化。也就是分裂节点到叶子不同的组合，不同的组合对应不同obj，所有的优化围绕这个思想展开。
(4) 树该怎么生长？
一棵树的生成是由一个结点一分为二，然后不断分裂最终形成整棵树，那么树是怎么分裂的呢？
枚举所有不同树结构的贪心法：不断地枚举不同树的结构，然后利用打分函数来寻找一个最优结构的树，接着加入到模型中，不断重复这样的操作。这个寻找的过程就是使用的贪心算法，选择一个feature分裂，计算loss function最小值，然后再选一个feature分类，又得到一个loss function最小值，枚举完，找一个效果最好的，把树给分裂，就得到了小树苗。
总而言之，XGBoost使用了和CART回归树一样的想法，利用贪婪算法，遍历所有特征的所有特征划分点，不同的是使用的目标函数不一样。具体做法就是分裂后的目标函数值比单子叶子节点的目标函数的增益，同时为了限制树生长过深，还加了个阈值，只有当增益大于该阈值才进行分裂。从而继续分裂，形成一棵树，再形成一棵树，每次在上一次的预测基础上取最优进一步分裂/建树。
(4) 如何停止树的循环生成
凡是这种循环迭代的方式必定有停止条件，设置树的最大深度，当样本权重和小于阈值时停止生长以防止过拟合。

• 当引入的分裂带来的增益小于设定阀值的时候，我们可以忽略掉这个分裂，所以并不是每一次分裂loss function整体都会增加的，有点预剪枝的意思，阈值参数为（即正则项里叶子节点数T的系数）；
• 当树达到最大深度时则停止建立决策树，设置一个超参数max_depth，避免树太深导致学习局部样本，从而过拟合；
• 样本权重和小于设定阈值时则停止建树。什么意思呢，即涉及到一个超参数-最小的样本权重和min_child_weight，和GBM的 min_child_leaf 参数类似，但不完全一样。大意就是一个叶子节点样本太少了，也终止同样是防止过拟合；

3. XGBoost与GBDT有什么不同

除了算法上与传统的GBDT有一些不同外，XGBoost还在工程实现上做了大量的优化。总的来说，两者之间的区别和联系可以总结成以下几个方面。

1. GBDT是机器学习算法，XGBoost是该算法的工程实现。
2. 在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模 型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
3. GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代 价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。
4. 传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类 器，比如线性分类器。
5. 传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机 森林相似的策略，支持对数据进行采样。
6. 传统的GBDT没有设计对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。

4. 为什么XGBoost要用泰勒展开，优势在哪里？

XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了XGBoost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。

References

[1] 终于有人说清楚了–XGBoost算法 - mantch - 博客园 (cnblogs.com)
[2] XGBoost: A Scalable Tree Boosting System.