Decision Tree -(Bagging)-> Random Forest -(Boosting)-> Gradient Boosting->XGBoost
【1】 https://zhuanlan.zhihu.com/p/34534004
【2】 https://www.zhihu.com/question/41354392/answer/545973472
决策树是一个有监督的分类模型，本质是选择一个能带来最大信息增益的特征值进行分裂，直到到达结束条件或者叶子节点纯度到达一定阈值。
决策树的每个非叶子节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出。叶子节点存放一个类别，将存放的类别作为决策结果。
按照分裂指标不同，决策树分为ID3，C4.5，和CART。
1. ID3：以信息增益为划分标准
信息增益的计算基于信息熵（度量样本集合纯度指标）
ID3的缺陷：
假设每个记录有一个属性“ID”，若按照ID来进行分割的话，由于ID是唯一的，因此在这一个属性上，能够取得的特征值等于样本的数目，也就是说ID的特征值很多。那么无论以哪个ID为划分，叶子结点的值只会有一个，纯度很大，得到的信息增益会很大，但这样划分出来的决策树是没意义的。由此可见，ID3决策树偏向于取值较多的属性进行分割，存在一定的偏好。为减小这一影响，有学者提出C4.5的分类算法。
2. C4.5：基于信息增益率准则选择最优分割属性算法
信息增益率通过引入一个被称作分裂信息（Split information）的项来惩罚取值较多的属性。
分子即ID3中计算的信息增益。分母由属性a的特征值个数决定，IV值越大，信息增益率越小，这样就可以避免模型偏好特征值多的属性。
但是，如果使用这个公式，模型又会偏向特征数少的特征。因此，C4.5决策树先从候选分裂属性中找出信息增益高于平均水平的属性，从中选择增益率最高的。
对于连续值属性来说，可取值数目不再有限，因此可以采用离散化技术（如二分法）进行处理。将属性值从小到大排序，然后选择中间值作为分割点，数值比它小的点被划分到左子树，数值不小于它的点被分到右子树，计算分割的信息增益率，选择信息增益率最大的属性值进行分割。
3. CART：以基尼系数为准则选择最优划分属性，可以应用于分类和回归
CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。
Gini(D)反映了数据集D的纯度，值越小，纯度越高。我们在候选集合中选择使得划分后基尼指数最小的属性作为最优化分属性。
分类与回归树具有两点特征：
回归树优点：
组合分类器是将多个分类器的结果进行多票表决或者取平均值，以此作为最终结果。
Bagging的思想是每一次从原始数据中根据均匀概率分布有放回的抽取和原始数据大小相同的样本集合，样本点可能出现重复，然后对每一次产生的训练集构造一个分类器，再对分类器进行组合。
构建组合分类器的好处：
随机森林是一个多棵决策树的组合分类器。主要包括两方面：数据的随机选取，以及待选特征的随机选取。
1.数据的随机选取
第一，从原始的数据集中采取有放回的抽样（bootstrap），构造子数据集，子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复，同一个子数据集中的元素也可以重复。
第二，利用子数据集来构建子决策树，将这个数据放到每个子决策树中，每个子决策树输出一个结果。最后，如果有了新的数据需要通过随机森林得到分类结果，就可以通过对子决策树的判断结果的投票，得到随机森林的输出结果了。如下图，假设随机森林中有3棵子决策树，2棵子树的分类结果是A类，1棵子树的分类结果是B类，那么随机森林的分类结果就是A类。
与数据集的随机选取类似，随机森林中的子树的每一个分裂过程并未用到所有的待选特征，而是从所有的待选特征中随机选取一定的特征，之后再在随机选取的特征中选取最优的特征。这样能够使得随机森林中的决策树都能够彼此不同，提升系统的多样性，从而提升分类性能。
Boosting的每一次抽样的样本分布都是不一样的。每一次迭代，都根据上一次迭代的结果，增加被错误分类的样本的权重，使得模型能在之后的迭代中更加注意到难以分类的样本，这是一个不断学习的过程，也是一个不断提升的过程，这也就是boosting思想的本质所在。迭代之后，将每次迭代的基分类器进行集成。那么如何进行样本权重的调整和分类器的集成是我们需要考虑的关键问题。
Gradient Boosting(GB)模型
思想就是迭代生成多个弱模型，将每个弱模型的结果相加。
Grandient Boosting模型算法具有相似的步骤：
（1）初始化模型为常数值
（2）迭代生成基学习器（计算伪残差-> 生成基学习器 -> 目标函数优化 -> 更新模型）
1. GBDT推导
GBDT是以决策树CART为基学习器的GB算法，是迭代树。
如前面所述，gbdt模型可以认为是是由k个基模型组成的一个加法运算式：
其中F是指所有基模型组成的函数空间。
那么一般化的损失函数是预测值 y^与 真实值y之间的关系，如我们前面的平方损失函数，那么对于n个样本来说，则可以写成：
更一般的，我们知道一个好的模型，在偏差和方差上有一个较好的平衡，而算法的损失函数正是代表了模型的偏差面，最小化损失函数，就相当于最小化模型的偏差，但同时我们也需要兼顾模型的方差，所以目标函数还包括抑制模型复杂度的正则项，因此目标函数可以写成：
好的模型需要具备两个基本要素：一是要有好的精度（即好的拟合程度），二是模型要尽可能的简单（复杂的模型容易出现过拟合，并且更加不稳定）因此，我们构建的目标函数右边第一项是模型的误差项，第二项是正则化项（也就是模型复杂度的惩罚项）
常用的误差项有平方误差和逻辑斯蒂误差，常见的惩罚项有l1，l2正则，l1正则是将模型各个元素进行求和，l2正则是对元素求平方。
每一次迭代，都在现有树的基础上，增加一棵树去拟合前面树的预测结果与真实值之间的残差
目标函数如上图，最后一行画圈部分实际上就是预测值和真实值之间的残差
先对训练误差进行展开：
xgboost则对代价函数进行了二阶泰勒展开，同时用到了残差平方和的一阶和二阶导数
再研究目标函数中的正则项：
树的复杂度可以用树的分支数目来衡量，树的分支我们可以用叶子结点的数量来表示
那么树的复杂度式子：右边第一项是叶子结点的数量T，第二项是树的叶子结点权重w的l2正则化，正则化是为了防止叶子结点过多
此时，每一次迭代，相当于在原有模型中增加一棵树，目标函数中，我们用wq（x）表示一棵树，包括了树的结构以及叶子结点的权重，w表示权重（反映预测的概率），q表示样本所在的索引号（反映树的结构）
将最终得到的目标函数对参数w求导，带回目标函数，可知目标函数值由红色方框部分决定：
因此，xgboost的迭代是以下图中gain式子定义的指标选择最优分割点的：
那么如何得到优秀的组合树呢？
一种办法是贪心算法，遍历一个节点内的所有特征，按照公式计算出按照每一个特征分割的信息增益，找到信息增益最大的点进行树的分割。增加的新叶子惩罚项对应了树的剪枝，当gain小于某个阈值的时候，我们可以剪掉这个分割。但是这种办法不适用于数据量大的时候，因此，我们需要运用近似算法。
另一种方法：XGBoost在寻找splitpoint的时候，不会枚举所有的特征值，而会对特征值进行聚合统计，按照 特征值的密度分布 ，构造直方图计算特征值分布的面积，然后划分分布形成若干个bucket(桶)，每个bucket的面积相同，将 bucket边界上的特征值 作为splitpoint的候选， 遍历所有的候选分裂点 来找到最佳分裂点。
上图近似算法公式的解释：将特征k的特征值进行排序，计算特征值分布，rk（z）表示的是对于特征k而言，其特征值小于z的权重之和占总权重的比例，代表了这些特征值的重要程度，我们按照这个比例计算公式，将特征值分成若干个bucket，每个bucket的比例相同，选取这几类特征值的边界作为划分候选点，构成候选集；选择候选集的条件是要使得相邻的两个候选分裂节点差值小于某个阈值。
综合以上所述，我们可以得到xgboost相比于GBDT的创新之处：