树模型以决策树为基本原型。
# DT
决策树是一种基本的分类和回归方法。和我们之前学过的逻辑斯特回归，线性回归等算法不同，他们要么只能做回归要么只能做分类，而决策树既可以做分类也可以做回归。主要包括：ID3，C4.5，CART。
物理含义：表示定义在特征空间上的条件概率分布，也就是把$$P(y)$$转化为$$P(y|X)$$。同时也可以理解为 if-then 规则的集合。如下图左图所示。
几何含义： “分而治之”的思想，即把特征空间划分为一系列的矩形区域，然后再每一个区域拟合一个简单的模型。如下图右图所示。本文将用决策树的几何含义对决策树进行讲解。
# 过拟合
原因：
在决策树构建的过程中，对决策树的生长没有进行合理的限制（剪枝）；
样本中有一些噪声数据，没有对噪声数据进行有效的剔除；
在构建决策树过程中使用了较多的输出变量，变量较多也容易产生过拟合。
解决办法：
选择合理的参数进行剪枝，可以分为预剪枝和后剪枝，我们一般采用后剪枝的方法；
利用K−folds交叉验证，将训练集分为K份，然后进行K次交叉验证，每次使用K−1份作为训练样本数据集，另外一份作为测试集；
减少特征，计算每一个特征和响应变量的相关性，常见得为皮尔逊相关系数，将相关性较小的变量剔除；当然还有一些其他的方法来进行特征筛选，比如基于决策树的特征筛选，通过正则化的方式来进行特征选取等（决策的正则化，例如，L1和L2正则，具体是对谁的正则呢？怎样正则的呢？）。
# 剪枝
预剪枝：在决策树生成初期就已经设置了决策树的参数，决策树构建过程中，满足参数条件就提前停止决策树的生成。
后剪枝：后剪枝是一种全局的优化方法，它是在决策树完全建立之后再返回去对决策树进行剪枝。
参数：树的高度、叶子节点的数目、最大叶子节点数、限制不纯度。
预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是，另一方面，因为预剪枝是基于“贪心”的，所以，虽然当前划分不能提升泛华性能，但是基于该划分的后续划分却有可能导致性能提升，因此预剪枝决策树有可能带来欠拟合的风险。
后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险小，泛华性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的，并且要自底向上的对树中的所有非叶结点进行逐一考察，因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。
后剪枝会减少欠拟合的风险，但训练时间相对于预剪枝会长很多。
REP方法是通过一个新的验证集来纠正树的过拟合问题。对于决策树中的每一个非叶子节点的子树，我们将它替换成一个叶子节点，该叶子节点的类别用大多数原则来确定，这样就产生了一个新的相对简化决策树，然后比较这两个决策树在验证集中的表现。如果新的决策树在验证集中的正确率较高，那么该子树就可以替换成叶子节点，从而达到决策树剪枝的目的。该算法是从下往上依次遍历所有的子树，直至没有任何子树可以替换使得在验证集上的表现得以改进时，算法就可以终止。
# 改进
ID3以信息增益作为特征划分依据。信息增益表示由于得知特征a的信息后儿时的数据集D的分类不确定性减少的程度，后面部分越小,减小的程度越小,增益越大。选择划分后信息增益大的作为划分特征，说明使用该特征后划分得到的子集纯度越高，即不确定性越小。因此我们总是选择当前使得信息增益最大的特征来划分数据集。缺点是信息增益偏向取值较多的特征（原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分后的熵更低，即不确定性更低，因此信息增益更大）
C4.5以信息增益率作为特征划分依据。可以利用连续特征，同时还增加了处理缺失值的方法和剪枝。需要注意的是，C4.5使用信息增益比对特征进行选择又会出现对特征取值较少的特征有偏好的问题。因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。C4.5处理连续特征方法是首先对连续特征进行排序，然后选择相邻值得中点作为分割点，需要注意的是，C4.5处理连续值是二分，并且该连续特征在接下来也可以继续使用。其余就和处理离散特征没有太大的区别了。
CART以基尼系数作为特征划分依据。无论是 ID3 还是 C4.5 都会涉及大量的对数运算。CART 分类树算法使用基尼系数，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。
如果是二类分类问题，计算就更加简单了，如果属于第一个样本输出的概率是 p，则基尼系数的表达式为：
对于个给定的样本D，假设有 K 个类别, 第 k 个类别的数量为 $$C_{k}$$ ,则样本 D 的基尼系数表达式为：
特别的，对于样本 D，如果根据特征 A 的某个值 a，把 D 分成 D1 和 D2 两部分，则在特征 A 的条件下，D 的基尼系数表达式为：
- 采用基尼系数可以降低计算量
- 连续值处理：其思想和 C4.5 是相同的，都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5 使用的是信息增益比，则 CART 分类树使用的是基尼系数。
- 采用二叉树：ID3 或者 C4.5采用的是多叉树；CART树采用的是二叉树。在 ID3 或者 C4.5 的一棵子树中，离散特征只会参与一层节点的建立；CART树中离散的特征可能参与多层节点的建立。
# Random Forest
随机森林是集成学习中的Bagging方法。提到随机森林，就不得不提Bagging，Bagging可以简单的理解为：放回抽样，多数表决（分类）或简单平均（回归）,同时Bagging的基学习器之间属于并列生成，不存在强依赖关系。
Random Forest（随机森林）是Bagging的扩展变体，它在以决策树 为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括RF包括四个部分：1、随机选择样本（放回抽样）；2、随机选择特征；3、构建决策树；4、随机森林投票（平均）。
RF和Bagging对比：RF的起始性能较差，特别当只有一个基学习器时，随着学习器数目增多，随机森林通常会收敛到更低的泛化误差。随机森林的训练效率也会高于Bagging，因为在单个决策树的构建中，Bagging使用的是‘确定性’决策树，在选择特征划分结点时，要对所有的特征进行考虑，而随机森林使用的是‘随机性’特征数，只需考虑特征的子集。
# GBDT
GBDT是集成学习中的Boosting方法。提GBDT之前，谈一下Boosting，Boosting是一种与Bagging很类似的技术。不论是Boosting还是Bagging，所使用的多个分类器类型都是一致的。但是在前者当中，不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练的分类器的性能来进行训练。Boosting是通过关注被已有分类器错分的那些数据来获得新的分类器。
GBDT与传统的Boosting区别较大，它的每一次计算都是为了减少上一次的残差，而为了消除残差，我们可以在残差减小的梯度方向上建立模型,所以说，在GradientBoost中，每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方法，与传统的Boosting中关注正确错误的样本加权有着很大的区别。
在GradientBoosting算法中，关键就是利用损失函数的负梯度方向在当前模型的值作为残差的近似值，进而拟合一棵CART回归树。
GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树（尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树）。
GBDT的性能在RF的基础上又有一步提升，因此其优点也很明显，1、它能灵活的处理各种类型的数据；2、在相对较少的调参时间下，预测的准确度较高。
当然由于它是Boosting，因此基学习器之前存在串行关系，难以并行训练数据。
# XGBoost
XGBoost的性能在GBDT上又有一步提升，而其性能也能通过各种比赛管窥一二。坊间对XGBoost最大的认知在于其能够自动地运用CPU的多线程进行并行计算，同时在算法精度上也进行了精度的提高。
由于GBDT在合理的参数设置下，往往要生成一定数量的树才能达到令人满意的准确率，在数据集较复杂时，模型可能需要几千次迭代运算。但是XGBoost利用并行的CPU更好的解决了这个问题。
其实XGBoost和GBDT的差别也较大，这一点也同样体现在其性能表现上，详见XGBoost与GBDT的区别。
- 与GBDT的区别
传统的GBDT以CART树作为基学习器，XGBoost还支持线性分类器，这个时候XGBoost相当于L1和L2正则化的逻辑斯蒂回归（分类）或者线性回归（回归）；传统的GBDT在优化的时候只用到一阶导数信息，XGBoost则对代价函数进行了二阶泰勒展开，得到一阶和二阶导数；
XGBoost在代价函数中加入了正则项，用于控制模型的复杂度。从权衡方差偏差来看，它降低了模型的方差，使学习出来的模型更加简单，放置过拟合，这也是XGBoost优于传统GBDT的一个特性；shrinkage（缩减），相当于学习速率（XGBoost中的eta）。XGBoost在进行完一次迭代时，会将叶子节点的权值乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。（GBDT也有学习速率）；
列抽样。XGBoost借鉴了随机森林的做法，支持列抽样，不仅防止过 拟合，还能减少计算；
对缺失值的处理。对于特征的值有缺失的样本，XGBoost还可以自动 学习出它的分裂方向；
XGBoost工具支持并行。Boosting不是一种串行的结构吗？怎么并行的？注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代 中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。