当树的结构确定的时候，我们可以得到最优的叶子点分数以及对应的最小损失值，问题在于如何确定树结构？
1、暴力穷举所有可能的结构，选择损失值最小的；(很难求解)
2、贪心法，每次尝试选择一个分裂点进行分裂，计算操作前后的增益，选择增益最大的方式进行分。
决策树相关算法计算指标：
1、ID3算法：信息增益
2、C4.5算法：信息增益率
3、CART算法：Gini系数
XGBoost目标函数
从目标函数中，我们希望损失函数越小越好，那就是 G2/(H+λ) 越大越好；从而，
对于一个叶子节点的分裂的分裂，分裂前后的信息增益定义为:
Gain值越大，分裂后减少的损失值越大。所以对于一个叶子节点分割时，计算
所有候选的(feature,value)对应的gain，选择gain最大特征进行分割。
树节点分裂方法
__精确算法：__遍历所有特征的所有可能的分割点，计算gain值，选择最大的gain值对应的(feature,value)进行分割。
近似算法： 对于每个特征，只考虑分位点，减少计算复杂度。
近似算法案例：三分位数
XGBoost不是简单的按照样本个数进行分位的，而是按照二阶导数值作为权重
来进行划分的：
XGBoost的其它特性
1、列采样(column subsampling)：借鉴随机森林的做法，支持列抽样，不仅可以降低过拟合，还可以减少计算量。
2、支持对缺失值的自动处理。对于特征的值有缺失的样本，XGBoost可以自动学习分裂方向；
3、XGBoost支持并行。XGBoost的并行是特征粒度上的，在计算特征的Gain的时候，会并行执行，但是在树的构建过程中，还是串行构建的。
4、XGBoost算法中加入正则项，用于控制模型的复杂度，最终模型更加不容易过拟合。
5、XGBoost基学习器支持CART、线性回归、逻辑回归。
6、XGBoost支持自定义损失函数(要求损失函数二阶可导)。
