一. cart决策树简述
我们知道决策树算法有ID3、C4.5和cart三种，ID3和C4.5是基于信息增益和信息增益比率做特征选择的，存在大量的log对数运算，而且只支持分类，cart就不同了，既能用于分类也能用于回归，同时使用基尼指数（Gini）选择特征简化模型计算，基尼指数越小，代表数据的不确定性越小，与信息增益相反，某个特征对样本划分之后的信息增益大，说明划分前后的不确定性减少的较多。
cart是个二叉树，选择的特征可以将样本划分到2个子树中，ID3和从4.5是个多叉树，且对于特征使用上，cart可以多次使用特征。
- Cart分类
1.1. Gini计算
在分类任务中，计算Gini指数公式如下：
其中，D为训练样本集合，里面包括n个类别，pk为类别k的概率，Dk是类别k下的训练样本集合，|Dk|为Dk的元素个数，也就是说某个样本属于类别k的概率为类别k的样本数除以总样本数。
针对特征A将样本集划分为D1和D2（由于cart是二叉树，每个特征只能将样本划分成2部分）之后的Gini指数为：
1.2. 连续特征和离散特征的最佳切分点选择
1.2.1 离散特征（大于2个值的）
如果一个特征A的值是离散值，且存在多种（例如存在3个值：V1,V2和V3），那么，特征A有3种组合能够对样本集D进行划分：
- 特征A为V1的划分一边，为V2和V3的划分一边，记做V1|(V2,V3)；
- 特征A为V2的划分一边，为V1和V3的划分一边，记做V2|(V1,V3)；
- 特征A为V3的划分一边，为V1和V2的划分一边，记做V3|(V1,V2)；
计算上述每种划分方式的Gini(D,A)，选择最小的划分方式为特征A的最佳切分点。
1.2.2 连续特征
如果特征A是一个连续特征，比如特征A是年龄，那么取值范围则是0-200之间，此时需要将特征离散化，具体方式为：
- 将训练样本中A的值从小到大排序，排序之后的值为v1,v2,...,vn；
- 针对连续两个值如vi、vi+1，计算两个值的平均值，这样可以得到n-1个划分点，m1,m2,...,mn-1;
- 针对n-1个划分点，分别计算每个划分点划分样本的Gini值，如划分点mi，将特征A小于mi的划分到一边，大于等于mi的样本到另一边，计算当前划分的Gini(D,A)值；
- 选取最小划分点计算出的Gini(D,A)的最小值对应的划分点作为特征A的最佳切分点。
2. Cart回归树
回归树与分类树不同的地方在于选择每个特征的最佳切分点，采用的平方误差和(MSE)，
假设针对一个特征A，训练样本特征A的值为x1,x2,x3,...,xn，选择特征A的最佳切分点
- 首先根据1.2中的逻辑，获取特征A的切分点集合v1,v2,...,vn;
-
遍历每个切分点，计算当特征A选择该切分点的时候的MSE，如选择切分点vi，将特征A样本划分为2个集合（CART为二叉树）
R1 = {xj| xj <= vi} j取1-n
R2 = {xj| xj > vi} j取1-n
R1,R2的输出值分别为R1集合中样本y值的平均值，R2集合中样本y值的平均值：
image.png
当前划分的平方误差为：
image.png - 根据遍历的每个特征的每个切分点，计算MSE，选取MSE最小的特征对应的切分点，作为当前划分的最佳切分点；
- 针对每个子树，重复计算每个特征的每个切分点划分的时候对应的MSE，选取最小的作为划分依据；
- 直到满足结束条件（如达到树的最大深度，叶子节点对应的样本数达到最小的样本数等）。
二、随机森林分类模型
随机森林是决策树的集合，所谓随机，也就是对训练样本的行、列两个维度进行随机训练：
-
行随机：假设有n个训练样本，每次迭代有放回的随机选取n个，里面可能会有重复的样本；
有放回随机选取样本 列随机：每次迭代中，都会从M个特征中随机选择k个作为当前训练的特征集合，这样能够使得随机森林中的决策树都能够彼此不同，提升系统的多样性，从而提升分类性能。
上述两个随机性的引入，可以防止模型过拟合。每迭代一次会生成一颗决策树，最后采用对每颗树的预测结果做个投票法作为最终结果的生成。
2.1 bagging和boosting
在每次迭代中，随机选取n个样本的时候，有2种方式选取：
bagging：每次迭代选取到每个样本的概率都是相同，也就是都是1/n;
boosting：每次迭代生成决策树之后，会重点关注被分类错误的样本，将这些样本的概率调大，使得下次迭代，选取样本的时候，这些分类错误的样本能够以更大的概率被选中，不断学习不断优化模型，使得每次迭代都在优化上次迭代出的模型。
三、GBDT
GBDT是利用的CART回归树，每次迭代是对上次得到决策树的残差进行拟合，残差公式为：
ft-1(x)为上一颗树的学习器。
-
第0次迭代--初始化弱分类器
image.png
其中L函数为损失函数，即平方误差函数；
也就是c值为全部样本y值的均值的时候，才会使得损失函数最小。 - 第一次迭代
样本第一次迭代的y值= 原始y值 - 第0次迭代的c值
采用平方误差函数，构造第一颗树的决策树； - 第二次迭代
样本第二次迭代的y值= 样本第一次迭代的y值 - 第一颗树的预测值
采用平方误差函数，构造第二颗树的决策树；
依次类推，直到最大迭代次数M -
第M次迭代
样本第M次迭代的y值= 样本第M-1次迭代的y值 - 第M-1颗树的预测值
构建第M颗树的决策树
针对一个新样本，预测出回归结果，将每次迭代的预测值求和：
image.png
四、XGBoost（参考点2）
XGBoost相对于GBDT而言，不同之处在于目标函数的复杂性：
其中f为每次迭代的决策树，目标函数包括两个部分：
- 一个部分是损失函数，常用的为平方误差、Logistic误差；
- 一个部分是每次迭代的树的正则化项。
常见的正则化方法为L1正则化和L2正则化。
假设采用平方误差作为损失函数：
观察上面两个公式红框里面的元素，发现上述目标函数样式与泰勒展开式十分相像。因此将上述的目标函数转化成样式如下：
其中gi为
hi=2.
观察出gi为残差公式，即残差平方和的一阶导数，hi为残差平方和的二级导数
下面在看目标函数的第二部分，正则化项，即也是树的复杂度
T代表叶子几点数量，w代表每个叶子节点值；
wq(xi)代表样本xi在这颗树的预测值。
总结XGBoost相对于GBDT的优点如下：
- 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
- xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
Shrinkage（缩减），相当于学习速率（xgboost中的eta）。每次迭代，增加新的模型，在前面成上一个小于1的系数，降低优化的速度，每次走一小步逐步逼近最优模型比每次走一大步逼近更加容易避免过拟合现象；- 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样（即每次的输入特征不是全部特征），不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
- 忽略缺失值：在寻找splitpoint的时候，不会对该特征为missing的样本进行遍历统计，只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个工程技巧来减少了为稀疏离散特征寻找splitpoint的时间开销
指定缺失值的分隔方向：可以为缺失值或者指定的值指定分支的默认方向，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，分到那个子节点带来的增益大，默认的方向就是哪个子节点，这能大大提升算法的效率。- 并行化处理：在训练之前，预先对每个特征内部进行了排序找出候选切割点，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行，即在不同的特征属性上采用多线程并行方式寻找最佳分割点。
