=================
树模型
=================

树模型基础
========================

决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，其中内部结点表示一个特征或属性，叶结点表示一个类。

决策树（Decision Tree）是一种基本的分类与回归方法，当决策树用于分类时称为分类树，用于回归时称为回归树。

分类树
------------

下图为分类树的可视化结果：

.. figure:: _static/分类树模型.png
    :align: center

- ID3

划分准则：信息增益

信息增益（information gain）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。特征a对训练数据集D
D的信息增益g(D,A)定义为集合D的经验熵H(D)与在给定特征A的条件下D的条件熵H(D∣A))之差，即：

.. math::
    g(D, A) = H(D) - H(D|A) \tag{1}

其中

.. math::
    H(D) = -\sum_{i=1}^{|D|} P(i)logP(i) \tag{2}

上式中 :math:`P(i)` 代表了类别标签为i的样本占总样本的比例。

.. math::
    H(D|A) = -\sum_{d=1}^{|D|} \sum_{a=1}^{|A|} p(d,a) log(p(d|a)) \tag{3}

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。
具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点。
之后，再对子结点递归地调用以上方法，构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止，最终得到一个决策树。

- C4.5

划分准则：信息增益率

如前文所说，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，
C4.5决策树算法不直接使用信息增益来选择划分属性，而是综合考虑了带划分属性的取值数量，使用信息增益率来选择最优划分属性，定义如下：

.. math::
    g_r(D, A) = \frac{g(D,A)}{H_A(D)} \tag{4}

其中

.. math::
    H_A(D) = -\sum_{i=1}^{|A|} P(i)logP(i) \tag{5}

P(i)为特征值为i的样本的比例。

- 基尼系数

数据集D的纯度还可用基尼值来度量，定义如下：

.. math::
    Gini(D) = \sum_{d=1}^{|D|} P(d)(1-P(i)) \tag{6}

当D为二分类时：

.. math::
    Gini(D) = 2P(1-P) \tag{7}

直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。

对于给定的特征A，Gini(D,A)定义如下：

.. math::
    Gini(D,A) = \sum_d^{|D|} \frac{|D_d|}{D} Gini(D_d) \tag{8}

- 连续值处理

连续属性离散化：

给定样本集D和连续属性a，a在D上的取值按大小排序为{a1,a2,.......,an}，我们可以定义划分点集合为：

.. math::
    T_a = \{\frac{a_i+a_{i+1}}{2} , 1 \ge i \le n-1\} \tag{9}

- 缺失值处理

a) 如何在属性值缺失的情况下进行划分属性的选择？

该问题即为如何计算属性有缺失值时的信息增益，定义如下：

.. math::
    g_m(D, A) = p*g(\widetilde{D}, A) \tag{10}

其中 :math:`\widetilde{D}` D中样本在属性A上有数值的样本，:math:`p` 为 :math:`\widetilde{D}` 在样本总数的比例。

b) 给定划分属性，若样本在该属性上的值是缺失的，那么该如何对这个样本进行划分？

初始情况下，样本的比例都为一。
若样本在给定属性下的值是缺失的，那么那就将该样本乘上权值划分到各个特征值节点中，
权值定义为 :math:`\widetilde{D}` 中对应不同特征值的样本的比例。

- 分类树的剪枝

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，有时会造成决策树分支过多，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。
因此，可通过主动去掉一些分支来降低过拟合的风险。决策树剪枝的基本策略有预剪枝和后剪枝。

a)预剪枝

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行以下估计，如能不能达到要求，则停止划分并将当前结点标记为叶结点。
停止决策树生长常用方法：

1. 定义一个高度，当决策树达到该高度时就停止决策树的生长。

2. 达到某个节点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。

3. 定义一个阈值，当达到某个节点的实例个数小于阈值时就可以停止决策树的生长。

4. 定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值大小来决定是否停止决策树的生长。

b)后剪枝

后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
相比于预剪枝，后剪枝更常用，因为在预剪枝中精确地估计何时停止树增长很困难。

1. 错误率降低剪枝

错误率降低剪枝方法是一种比较简单的后剪枝的方法。在该方法中，可用的数据被分成两个样例集合：首先是训练集，它被用来形成学习到的决策树，另一个是与训练集分离的验证集，它被用来评估修剪这个决策树的影响。

错误率降低剪枝方法是最简单的后剪枝方法之一，不过由于使用独立的测试集，原始决策树相比，修改后的决策树可能偏向于过度修剪。
这是因为一些不会再次在测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过程中往往会被剪枝。尽管错误率降低剪枝方法有这个缺点，不过错误率降低剪枝方法仍然作为一种基准来评价其它剪枝算法的性能。
同时验证集的选择也会具有一定程度的偏差，但是相对训练集与测试集的偏差要小很多，所以可以在一定程度上降低过拟合的情况。

2. 代价复杂度剪枝

代价复杂度剪枝综合考虑了剪枝后的错分类代价与模型复杂度的降低，对于节点T来讲，该系数定义如下：

剪枝前代价复杂度系数为：

.. math::
    C_{\alpha}(T) = C(T)+ \alpha|T| \tag{11}

其中C(T)定义如下：

.. math::
    C(T) = \sum_{t \in leaf} N_t·H(t) \tag{12}

其形式类似于数据在节点T的条件熵，只是系数由原来的样本比例变为现在的样本数量。

剪枝后代价复杂度系数为：

.. math::
    C_{\alpha}(t) = C(t)+ \alpha \tag{13}

则节点T对应的剪枝系数 :math:`\alpha` 定义如下：

.. math::
    \alpha_t = \frac{C_{\alpha}(t) - C_{\alpha}(T)}{|T|-1} \tag{14}

较大的 :math:`\alpha` 倾向于选择简单的模型，较小的 :math:`\alpha` 倾向于选择较复杂的模型，当 :math:`\alpha` 为零时，则不考虑模型的复杂性。

剪枝主要步骤如下：

对于给定的决策树T：

- 计算所有内部结点的剪枝系数；

- 查找最小剪枝系数的结点，剪枝得决策树Tk；

- 重复以上步骤，直到决策树Tk只有一个结点；

- 得到决策树序列T0,T1,T2...Tk;

- 使用验证样本集选择最优子树。

3. 悲观错误剪枝

对于一个叶子节点，有N个样本，其中E表示错误样本的数量，则该叶子结点的错误率定义为 :math:`\frac{E+0.5}{N}` ，
那么对于一个子树来讲，定义为 :math:`\frac{\sum E_i+0.5·|L|}{\sum N_i}`, 其中|L|为该子树下的叶子结点数量，:math:`N_i` 为节点i下的样本数量。

对于待剪枝子树，若该子树删除后形成的叶子结点的错误率小于该子树的错误率，则对该子树进行剪枝。


回归树
------------------

下图为回归树的可视化结果：

.. figure:: _static/回归树模型.png
    :align: center

1. 回归树的构建思想：在训练集的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值构建二叉决策树。

具体步骤为：

- 选择最优切分变量j和切分点s

.. math::
    min_{j,s}[\sum_{x_i \in c_1} (y_i - \hat{y_{c_1}})^2 + \sum_{x_j \in c_2} (y_j - \hat{y_{c_2}})^2] \tag{1}

上式中 :math:`c_1` 与 :math:`c_2` 表示根据切分点s划分的左右两个集合，遍历变量j，对固定的切分变量j扫描切分点s，选择满足上式的j、s对。

- 对切分区域计算两个区域的输出平均值，用于下面的步骤。

- 继续对两个子区域递归地调用上面两个步骤，直至满足停止条件。

- 将输入空间划分为M个区域 R1，R2，.......,RM，生成回归树如下：

.. math::
    f(x) = \sum_{m=1}^M \hat{c_m}I(x \in RM) \tag{2}

2. 回归树的剪枝

在回归树的剪枝中，我们常使用代价复杂度剪枝，定义如下：

.. math::
    \sum_{m=1}^|T| \sum_{x \in R_m} (y_i - \hat{y_{R_m}})^2 + \alpha|T| \tag{3}

其中 :math:`|T|` 为节点T下分支数，:math:`R_m` 为这些分支中对应下标为m的分支下的数据集。

接着进行与分类树的剪枝相同的操作，得到最优的剪枝回归树。

决策树的优缺点
------------------------------------

- 计算复杂度不高

- 对中间缺失值不敏感

- 解释性强，在解释性方面甚至比线性回归更强

- 与传统的回归和分类方法相比，决策树更接近人的决策模式

- 可以用图形表示，非专业人士也可以轻松理解

- 可以直接处理定性的预测变量而不需创建哑变量

- 决策树的预测准确性一般比回归和分类方法弱，但可以通过用集成学习方法组合大量决策树，显著提升树的预测效果


组合树模型
========================

组合树模型有两种组合方式，bagging与boosting，在偏差-方差方面，bagging更关注于解决方差问题，而boosting更关注于解决偏差问题。

bagging
########################

并行方式，将尽可能独立的基学习器集成在一起，提升模型的准确性和泛化能力。

随机森林
------------------------------

- 样本随机

- 特征随机

- 参数随机

- 模型随机

极端随机树
---------------------------------------------

- 分裂随机

- 特征随机

- 参数随机

- 模型随机


极端随机树树与随机森林的主要有以下几点区别：

1、随机森林应用的是Bagging模型，极端随机树使用所有的样本。

2、随机森林是在特征子集中选择最优的特征，而极端随机树的特征是随机选取的，相对随机森林来讲，更大程度上降低了方差，但是增大了偏差。

基于bagging的模型，自主采样过程会形成占样本数约36.8%的不在训练集出现的验证集，用作对模型的泛化性能进行包外估计（out-of-bag estimate）。

boosting
#########

串行方式，是一种可将弱学习器提升为强学习器的算法。

AdaBoost
---------------------------

AdaBoost 算法思想：

（1）初始化训练数据（每个样本）的权值分布：如果有N个样本，则每一个训练的样本点最开始时都被赋予相同的权重：1/N。

（2）训练弱分类器。具体训练过程中，如果某个样本已经被准确地分类，那么在构造下一个训练集中，它的权重就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。同时，得到弱分类器对应的话语权。然后，更新权值后的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。

（3）将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，分类误差率小的弱分类器的话语权较大，其在最终的分类函数中起着较大的决定作用，而分类误差率大的弱分类器的话语权较小，其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的比例较大，反之较小。

AdaBoost 迭代方式：

- 分类器权重更新公式：

.. math::
    \alpha_t = \frac{1}{2} ln(\frac{1-e_t}{e}) \tag{1}

其中e为当前分类器的错误率。

- 样本更新公式：

.. math::
    D_{t+1}(x) = \frac{D_t(x)·e^(-f(x) \alpha_th_t(x))}{Z_t}  \tag{2}

其中 :math:`Z_t` 为规范化因子，确保新生成的样本权值满足分布。

Gradient Tree Boosting
-----------------------

算法核心：针对上轮的模型，可以得到基于上轮模型输出结果的损失，我们便是要最小化这个损失，所以根据定义的损失函数对上轮模型的输出结果求偏导，进而在当前模型下拟合上述负梯度，最后将上轮结果与本轮拟合负梯度进行相加，则可以迭代的得到最后的模型。

xgboost
--------

树模型应用场景
========================