在工业界，决策树（Decision Tree）是一类常见的机器学习方法。决策树综合可解释性、表征能力（线性模型 < 树模型 < 神经网络）、可操作性（调参）等优点，目前它是工业界应用最广的模型，很多基于树模型的开源的框架可供选择，比如Random Forest、GBDT、XGBoost、LightGBM 这些工业界最为常用的框架都是以决策树模型为基础的。
决策树是一种基本的分类与回归方法。这篇笔记主要介绍决策树的基本流程；其次介绍决策树的特征选择；再介绍决策树的剪枝；然后介绍一个历史上非常经典的决策树CART树；最后再介绍决策树模型的其它要点。
决策树的基本流程
决策树学习本质上是从训练数据集中归纳出一组分类规则。从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法（即贪心策略），近似求解这一最优化问题。这样得到的决策树是次最优的。
决策树的基本流程伪代码如下图所示（摘自《西瓜书》P74）。
决策树的生成是一个递归过程。在决策树基本算法中，有三种情形会导致递归返回：
情形1： 当前结点包含的样本全属于同一类别，无需划分；
情形2： 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
情形3： 当前结点包含的样本集合为空，不能划分；
在情形2中，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在情形3中，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。注意这两种情形的处理实质不同：情形2是在利用当前结点的后验分布，而情形3则是把父结点的样本分布为当前结点的先验分布。
上图是决策树学习基本算法的流程，基本算法流程中重点在第8行，如何选择最优的划分特征，所以决策树学习算法生成过程包括特征选择。
决策树特征选择
决策树学习基本算法的关键是第8行，即特征选择，也就是如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。
树结点分叉后“纯度”变化的数学描述通常有信息增益、信息增益比和基尼指数，下面对这三者分别进行介绍。
信息增益
在讲信息增益之前必须要提“信息熵”。”信息熵”（information entropy）是度量样本集合纯度最常用的一种指标，假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k (k=1,2,...,|Y|)$ ，则 $D$ 的信息熵定义为 $Ent(D)=-\sum_{k=1}^{|Y|} p_k \cdot log_2 p_k$ ， $Ent(D)$ 的值越小，则 $D$ 的纯度越高。
假定离散属性 $a$ 有 $V$ 个可能的取值 $\{a^1, a^2, ..., a^V\}$ ， 若使用 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本记为 $D^v$ 。可以根据信息熵的定义计算出 $D^v$ 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $|D^v|/|D|$ ，即样本数越多的分支结点的影响越大，于是可计算出可用属生 $a$ 对样本集 $D$ 进行划分所获得的“信息增益”（information gain），即 $Gain(D, a)=Ent(D)-\sum_{v=1}^{V} \frac{D^v}{D} Ent(D^v)$ 。
一般而言，信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的特征选择，即在决策树学习基本算法中第8行特征选择 $a_* = \mathop{\arg\max}_{ a \in A} Gain(D,a)$ 。ID3（Iterative Dichotomiser，即迭代二分器）决策树学习算法就是以信息增益为准则来进行特征选择的。信息增益是作为特征选择的经典方法之一。
直接看文字叙述会比较抽象，建议看例子，关于“信息增益”的举例说明可以参考《统计学习方法 第二版》P72-78 页 或 《西瓜书》 P75-77 页。
信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。然而使用信息增益比（information gain ratio）可以对这一问题进行校正。信息增益比定义为 $Gain\_ratio(D, a) = \frac{Gain(D,a)}{IV(a)}$ ，其中 $IV(a) = - \sum_{v=1}^{V} \frac{|D^v|}{D} log_2 \frac{|D^v|}{|D|}$ 称为属性 $a$ 的“固有值”（intrinsic value）。属性 $a$ 的可能取值数目越多（即 $V$ 越大），则 $IV(a)$ 的值通常会越大。
C4.5（1993年提出）算法是使用“信息增益比”来选择最优划分属性的。需注意的是，信息增益比准则对可取值数目较少的属性有所偏好。因此，实际C4.5算法并不是直接选择增益比最大的候选划分属性，而是使用了一个启发式：先从侯选划分属性中找出信息增益高于平均水平的属性，再从中选择增益比最高的。
基尼指数
“基尼指数”（Gini index）也是一个较常用的特征选择策略，CART（Classification and Regression Tree）决策树就是应用”基尼指数”来做特征选择的。
具体地，数据集 $D$ 的纯度可用基尼值来度量：$Gini(D)=\sum_{k=1}^{|Y|} (\sum_{k' \neq k} p_k p_{k'}) = 1 - \sum_{k=1}^{|Y|}p_k^2$ ，其中 $p_k$ 代表样本点属于第 $k$ 类的概率。
同样对于给定的样本集合 $D$ ，其基尼指数为 $Gini(D) = 1 - \sum_{k=1}^{K} \left ( \frac{|C_k|}{|D|} \right ) ^2$ ，其中 $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集， $K$ 是类的个数。
直观来看，$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$ 越小，则数据集 $D$ 的纯度越高，这一点与熵相似。
下图显示二分类问题中基尼指数 $Gini(p)$ 、熵（单位比特）之半 $Ent(p)/2$ 和分类误差率的关系，其中 $p$ 代表数据集 $D$ 中正例的概率。横坐标表示概率 $p$ ，纵坐标表示损失。可以看出基尼指数和熵之半的曲线很接近，都可以近似地代表分类误差率。
属性 $a$ 的基尼指数定义为 $Gini\_index(D,a) = \sum_{v=1}^{V} ( \frac{|D^v|}{|D|} \cdot Gini(D^v ))$ ，于是，我们在候选属性集合 $A$ 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $a_* = \mathop{\arg\min}_{ a \in A} Gini\_index(D,a)$ 。
决策树剪枝
剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。决策树剪树的基本策略有“预剪枝”（prepruning）和“后剪枝”（postpruning），预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性成提升，则将该子树替换为叶结点。
预剪枝(prepruning)
预留一份验证集，在决策树启发式分裂的过程中，对分裂前后的精度进行比较，若分裂后效果变好则进行分裂，否则停止分裂。优点：这可以降低过拟合的风险和减少决策树的训练时间开销；缺点：有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高，最终导致欠拟合。
预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。随着硬件性能的提升，往往不追求训练时间开销而使用预剪枝，同时它有很大的欠拟合风险，现在工业界框架更多地使用的是后剪枝。关于预剪枝例子可以参考《西瓜书》P79-82 。
后剪枝(postpruning)
工业界框架更多地是采用后剪枝的方式。后剪枝等待训练生成一棵完整决策树完成后，然后再自底向上递归地进行剪枝，是否剪枝的依据是根据在验证集上的效果决定。
后剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销较大。但随着计算机性能的提升，往往选择牺牲训练时间开销来提升精度，现在工业界框架更多地使用的是后剪枝策略。 关于后剪枝直观的例子可以参考《西瓜书》P82-83 ，关于后剪枝的数学推导可参考《统计学习方法第二版》P78-80 。
CART树
CART树（classification and regression tree, CART）在1984年提出，是经典的决策树学习方法。CART树既可以用于分类也可以用于回归。
CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值是“是”的分支，右分支是取为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测概率分布。CART树由决策树的生成和后剪枝组成，其中决策树的生成包含特征选择的策略。
CART树生成
决策树的生成就是递归地构建二叉决策树的过程。在特征选择的策略层面：对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则。
回归树的生成
假设 $X$ 与 $Y$ 分别为输入和输出变量，并且 $Y$ 是连续变量，给定训练数据集 $D=\{(x_1, y_1), (x_2, y_2), ..., (x_N,y_N)\}$ 。
一棵回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为 $M$ 个单元 $R_1,R_2,...,R_M$ ，并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$ ，于是回归树模型可表示为
$f(x) = \sum_{m=1}^{M} c_m \cdot I(x \in R_m)$ ，当输入空间的划分确定时，可以用平方误差 $\sum_{X_i \in R_m} (y_i - f(x_i))^2$ 来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元 $R_m$ 上的 $c_m$ 的最优值 $\overline{c}_m$ 是 $R_m$ 上的所有输入实例 $x_i$ 对应的输出 $y_i$ 的均值，即 $\overline{c}_m = ave(y_i|x_i \in R_m)$ 。
问题是怎样对输入空间进行划分。这里采用启发式的方法，选择第 $j$ 个变量 $x^{(j)}$ 和它取的值 $s$ ，作为切分变量和切分点，并定义两个区域： $R_1(j,s) = \{ x|x^{(j)} \leqslant s \}$ 和 $R_2(j,s) = \{ x|x^{(j)} > s \}$ 。然后寻找最优切分变量 $j$ 和最优切分点 $s$ 。具体地，求解下式对固定输入变量 $j$ 可以找到最优切分点 $s$ 。
$min_{j,s} \left [ min_{c_1} \sum_{x_i \in R_1(j,s) } (y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 \right ]$
其中 $\overline{c}_1 = ave(y_i|x_i \in R_1(j,s))$ 和 $\overline{c}_2 = ave(y_i|x_i \in R_2(j,s))$ 。遍历所有输入变量，找到最优的切分变量 $j$ ，构成一个对 $(j,s)$ 。依次将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成一棵回归树。这样的回归树通常称为最小二乘回归树（least squares regression tree）。
回归树生成算法描述如下
输入：训练数据集 $D$ ；
输出：回归树 $f(x)$ 。
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
（1）选择最优切分变量 $j$ 扫描切分点 $s$ 。具体地，求解下式，遍历变量 $j$ ，对固定的切分变量 $j$ 扫描切分点 $s$ ，选择使下式达到最小值的 $(j,s)$ 。
$min_{j,s} \left [ min_{c_1} \sum_{x_i \in R_1(j,s) } (y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 \right ]$
（2）用选定的对 $(j,s)$ 划分区域并决定相应的输出值：
$R_1(j,s) = \{ x|x^{(j)} \leqslant s \}$ ， $R_2(j,s) = \{ x|x^{(j)} > s \}$
$\overline{c}_m = \frac{1}{N_m} \sum_{x_i \in R_m(j,s)} y_i \ , \ \ x \in R_m \ , m = 1,2$
（3）继续对两个子区域调用步骤（1），（2），直至满足停止条件。
（4）将输入空间划分为 $M$ 个区域 $R_1, R_2, ..., R_M$ ，生成决策树： $f(x) = \sum_{m=1}^{m} \overline{c}_m \cdot I(x \in R_m)$ 。
分类树的生成
分类树是用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
对于二分类问题，如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分，即 $D_1 = \{ (x,y) \in D | A(x)=a \}$ ， $D_2 = D - D_1$ ，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为 $Gini(D,A) = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2)$ ，其中基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini(D,A)$ 表示经 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数值越大，样本集合的不确定性也就越大。
分类树生成算法描述如下
输入： 训练数据集 $D$ ，停止计算的条件；
输出： CART决策树
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：
（1）设结点的训练数据集为 $D$ ，计算现有特征对该数据集的基尼指数。此时，对每一个特征 $A$ ，对其可能取的每个值 $a$ ，根据样本点对 $A=a$ 的测试为“是”或“否”将 $D$ 分割成 $D_1$ 和 $D_2$ 两部分，计算 $A=a$ 的基尼指数。
（2）在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
（3）对两个子结点递归地调用（1），（2），直至满足停止条件（停止条件是结点中的样本个数小于预定阈值、或样本集的基尼指数小于预定阈值、或样本基本属于同一类、或无更多特征）。
（4）生成CART决策树。
以上便是分类树生成的流程，关于分类树生成算法的例子可参考《统计学习方法第二版》P84-85 。
CART树后剪枝
CART剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小（模型变简单），从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成：首先从生成算法产生的决策树 $T_0$ 底端开始不断剪枝，直到 $T_0$ 的根结点，形成一个子树序列 $\{T_0,T_1,...,T_n\}$ ；然后通过交叉验证在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
CART剪枝过程叙述
1.剪枝，形成一个子树序列
在剪枝过程中，计算子树的损失函数： $C_a(T) = C(T) + a|T|$ ，其中， $T$ 为任意子树， $C(T)$ 为对训练数据的预测误差（如基尼指数）， $|T|$ 为子树的叶结点个数， $a \geqslant 0$ 为参数， $C_a(T)$ 为参数是 $a$ 时的子树 $T$ 的整体损失。参数 $a$ 权衡训练数据的拟合程度与模型的复杂度。
对固定的 $a$ ，一定存在使损失函数 $C_a(T)$ 最小的子树，将其表示为 $T_a$ 。 $T_a$ 在损失函数 $C_a(T)$ 最小的意义下最优的。Breiman等人证明：可以用递归的方法对树进行剪枝。将 $a$ 从小增大， $0 = a_0 < a_1 < ... < a_n < +\infty$ ，产生一系列的区间 $[a_i,a_{i+1}]$ ，$i=0,1,...,n$ ；剪枝得到的子树序列对应着区间 $a \in [a_i, a_{i+1})$ ，$i=0,1,...,n$ 的最优子树序列 $\{ T_0, T_1, ..., T_n \}$ ，序列中的子树是嵌套的。
具体地，从整体树 $T_0$ 开始剪枝。对 $T_0$ 的任意内部结点 $t$ ，以 $t$ 为单结点树的损失函数是 $C_a(t) = C(t) + a$
以 $t$ 为根结点的子树 $T_t$ 的损失函数是 $C_a(T_t) = C(T_t) + a |T_t|$
当 $a=0$ 及 $a$ 充分小时，有不等式 $C_a(T_t) < C_a(t)$
当 $a$ 增大时，在某一 $a$ 有 $C_a(T_t) = C_a(t)$
当 $a$ 再增大时，不等式则会反向。只要 $a=\frac{C(t) - C(T_t)}{|T_t| - 1}$ ， $T_t$ 与 $t$ 有相同的损失函数值，而 $t$ 的结点少，因此 $t$ 比 $T_t$ 更可取，对 $T_t$ 进行剪枝。
为此，对 $T_0$ 中每一内部结点 $t$ ，计算 $g(t) = \frac{C(t)-C(T_t)}{|T_t| - 1}$ ，它表示剪枝的程度 。在 $T_0$ 中剪去 $g(t)$ 最小的 $T_t$ ，将得到的子树作为 $T_1$ ，同时将最小的 $g(t)$ 设为 $a_1$ 。$T_1$为区间$[a_1,a_2)$` 的最优子树。
如此剪枝下去，直至得到根结点。在这一过程中，不断地增加 $a$ 的值，产生新的区间。
2.在剪枝得到的子树序列 $T_0,T_1,...,T_n$ 中通过交叉验证选取最优子树 $T_a$
具体地，利用独立的验证数据集，测试子树序列 $T_0,T_1,...,T_n$ 中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树 $T_1,T_2,...,T_n$ 都对应于一个参数 $a_1,a_2,...,a_n$ 。所以，当最优子树 $T_k$ 确定时，对应的 $a_k$ 也确定了，即得到最优决策树 $T_a$ 。
CART剪枝算法
输入：CART算法生成的决策树 $T_0$ ；
输出：最优决策树 $T_a$ 。
（1）设 $k=0,T=T_0$ 。
（2）设 $a=+\infty$ 。
（3）自下而上地对各内部结点 $t$ 计算 $C(T_t)$ ，$|T_t|$ 以及 $g(t)=\frac{C(t) - C(T_t)}{|T_t| - 1}$ ， $a=min(a,g(t))$ 。其中， $T_t$ 表示以 $t$ 为根结点的子树，$C(T_t)$ 是对训练数据的预测误差，$|T_t|$ 是 $T_t$ 的叶结点个数。
（4）对 $g(t)=a$ 的内部结点 $t$ 进行剪枝，并对叶结点 $t$ 以多数表决法决定其类，得到树 $T$ 。
（5）设 $k=k+1, a_k=a, T_k=T$ 。
（6）如果 $T_k$ 不是由根结点及两个叶结点构成的树，则回到步骤（2）；否则令 $T_k=T_n$ 。
（7）采用交叉验证法在子树序列 $T_0,T_1,...,T_n$ 中选取最优子树 $T_a$ 。
决策树其它要点
连续值处理
由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分。此时，连续属性离散化技术可派上用场，最简单的策略是采用二分法（bi-partition）对连续属性进行处理，C4.5决策树算法正是采用这样的机制。
具体地，给定样本集 $D$ 和连续属性 $a$ ，假定 $a$ 在 $D$ 上出现了 $n$ 个不同的取值，将这些值从小到大进行排序，记为 $\{a^1, a^2, ..., a^n\}$ ，基于划分点 $t$ 可将 $D$ 分为子集 $D_t^-$ 和 $D_t^+$ ，其中 $D_t^-$ 包含那些在属性 $a$ 上取值不大于 $t$ 的样本，而 $D_t^+$ 则包含那些在属性 $a$ 上取值大于 $t$ 的样本。显然，对相邻的属性取值 $a^i$ 与 $a^{i+1}$ 来说，$t$ 在区间 $[a^i, a^{i+1})$ 中取任意值所产生的划分结果相同。因此，对连续属性 $a$ ，我们可考察包含 $n-1$ 个元素的候选划分点集合
$T_a = \left \{ \frac{a^i+a^{i+1}}{2} \ \ | 1 \leqslant i \leqslant n-1 \right \}$ ，
即把区间 $[a^i,a^{i+1}]$ 的中位点 $\frac{a^i+a^{i+1}}{2}$ 作为假选划分点。然后，我们就可像离散属性值一样来考虑这些划分点，选取最优的划分点进行样本集合的划分。需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。
缺失值处理
现实任务中常会遇到不完整样本，即样本的某些属性值缺失。对于缺失样本的处理，在工业界，我们会选择中位数、均值来填充缺失值。
在模型层面，很多决策树模型也支持对缺失值的处理。在决策树模型层面需解决两个问题：（1）如何在属性值缺失的情况下进行划分属性选择；（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分。
对于第1个问题：推广Gain，同时考虑无缺失样本比例和无缺失属性的比例，在信息增益中即考虑这两者的缺失比例的系数；对于第2个问题：让同一个样本以不同的概率划入到不同的子结点中。C4.5算法使用了这种解决方案，关于处理缺失值的例子可参考《西瓜书》P87-88 。
分类边界
若我们不考虑多变量决策树的情况。那么对一般决策树而言，我们把每个属性视为坐标空间中的一个坐标轴，则 $d$ 个属性描述的样本就对应了 $d$ 维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策对所形成的分类边界有一个明显的特点：轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。
如下图如示：其中左图表示所学得的决策树，右图为所对应的分类边界。显然，分类边界的每一段都是与坐标轴平行的。
总结
在工业界，决策树的变体的应用非常广泛，所以这篇笔记结合《统计学习方法》和《西瓜书》两本资料详细介绍了决策树的基本原理。首先给出了决策树的基本流程；其次介绍决策树在进行特征选择的经典方法（信息增益、信息增益比和基尼指数）；再介绍了决策树的剪枝，分为预剪枝和后剪枝；然后介绍了历史上经典的决策树CART树，分别给出回归树和分类树的生成过程，和它的剪枝策略；最后介绍了决策树模型其它的要点，分别是对于连续值的处理、缺失值的处理和它的分类边界形态。
参考文献
- 李航 《统计学习方法》第二版 P67-89
- 周志华 《机器学习》P73-95