决策树

概述

决策树(Decision Tree)是一种常用的机器学习方法，是一种对实例进行分类的树形结构。以二分类问题为例，假设我们要对是否买西瓜进行决策。
定义决策树结构包括：

内部结点：属性
分支：属性值
叶子结点：分类结果

于是，学习过程就是通过对训练样本的训练来确定“划分属性”（即内部结点对应的属性）；预测过程则是将测试用例从根节点开始，沿着树形结构下行，直到叶结点。
具体结构举例：

图片.png

从代码角度，决策树可以看成一段嵌套的if-else语句，示例中的决策树完全可以看成如下代码：

if is_red:
    if is_cold:
        if has_seed:
            print("buy")
        else:
            print("don't buy")
    else:
        if is_cheap:
            print("buy")
        else:
            print("don't buy")
else:
    print("don't buy")

决策树的根节点(root node)到叶结点(leaf node)的每一条路径构成一条规则：路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。其基本策略是“分而治之”（divide-and-conquer），即在自根至叶的递归过程中，在每个中间结点寻找一个“划分”(split or test)属性

决策树学习时，利用训练数据，根据损失函数最小化原则建立决策树模型，通常包括三个步骤：特征选择、决策树的生成和决策树的修剪。主要的决策树算法包括ID3算法、C4.5算法和CART算法。

特征选择

特征选择在于选取对训练数据具有分类能力的特征，一个合适的特征可以极大提高决策树的学习效率。相反，如果利用一个特征进行分类的结果与随机分类的结果没有很大的差别，则认为该特征没有分类能力。特征选择的标准一般有三类：信息增益、信息增益比和基尼指数。

熵

熵（entropy）表示随机变量的不确定性。假设 $X$ 是一个有限离散随机变量，其概率分布为
$P(X = x_i) = p_i, \quad i = 1, 2, \cdots, n$
则随机变量 $X$ 的熵为：
$H(x) = - \sum_{i=1}^n p_i \log p_i$

条件熵

设有随机变量 $(X, Y)$ ，其联合概率分布为：
$P(X=x_i, Y=y_i) = p_{ij}, \quad i = 1, 2, \cdots, n; \quad j = 1, 2, \cdots, m$
随机变量 $X$ 给定的条件下随机变量 $Y$ 的条件熵（conditional entropy） $H(Y \mid X)$ ，定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望：
$H(Y \mid X) = \sum_{i=1}^n p_i H(Y \mid X = x_i)$ 其中， $p_i = P(X = x_i), \quad i = 1, 2, \cdots, n$

信息增益

信息增益（information gain）表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。定义特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ 为：
$g(D,A) = H(D) - H(D \mid A)$ 熵 $H(Y)$ 与条件熵 $H(Y \mid X)$ 之差称为互信息（mutual information），于是决策树学习中的信息增益等价于训练数据集中类和特征的互信息。
此外，当熵和条件熵中的概率有数据估计得到时，所对应的熵和条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。

信息增益算法

输入：训练数据集 $D$ 和特征 $A$
输出：特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$

计算数据集 $D$ 的经验熵 $H(D)$
$H(D) = - \sum_{k=1}^K \frac {\mid C_k \mid} {\mid D \mid} \log_2 \frac {\mid C_k \mid} {\mid D \mid}$
计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D \mid A)$
$H(D \mid A) = \sum_{i=1}^n \frac {\mid D_i \mid}{\mid D \mid} H(D_i) = - \sum_{i=1}^n \frac {\mid D_i \mid}{\mid D \mid} \sum_{k=1}^K \frac {\mid C_k \mid} {\mid D \mid} \log_2 \frac {\mid C_k \mid} {\mid D \mid}$
计算信息增益
$g(D,A) = H(D) - H(D \mid A)$

信息增益比

信息增益值的大小是相对于训练数据集而言的，并没有绝对意义，比如在训练数据集的经验熵大的时候，信息增益值会偏大。利用信息增益比（information gain ratio）对这一问题进行校正，定义特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D,A)$ 为：
$g_R(D,A) = \frac {g(D,A)} {H(D)}$

基尼指数

CART决策树使用基尼指数（Gini index）来选择划分属性，基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini(D,A)$ 则表示经 $A = a$ 分割后集合 $D$ 的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。
分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为
$Gini(p) = \sum_{k=1}^K p_k (1 - p_k) = 1 - \sum_{k=1}^K p_k^2$ 对于给定的样本集合 $D$ ，其基尼指数为
$Gini(D) = 1 - \sum_{k=1}^K (\frac {\mid C_k \mid} {\mid D \mid})^2$
其中， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集， $K$ 是类的个数。
如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为
$Gini(D, A) = \frac {\mid D_1 \mid} {\mid D \mid} Gini (D_1) + \frac {\mid D_2 \mid} {\mid D \mid}Gini (D_2)$

决策树的生成

ID3算法

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

具体流程

输入：训练数据集 $D$ ，特征集 $A$ ，阈值 $\varepsilon$
输出：决策树 $T$

若 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；
若 $A = \varnothing$ ，则 $T$ 为单结点树，并将 $T$ 中实例数量最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
否则，计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$ ；
如果 $A_g$ 的信息增益小于阈值 $\varepsilon$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
否则，对 $A_g$ 的每一个可能指 $a_i$ ，依照 $A_g = a_i$ 将 $D$ 分割为若干非空自己 $D_i$ ，将 $D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $T$ ，返回 $T$ ；
对第 $i$ 个子节点，以 $D_i$ 为训练集，以 $A - \{ A_g \}$ 为特征集，递归地调用前5步，得到子树 $T_i$ ，返回 $T_i$

C4.5算法

C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成过程中选择用信息增益比来选择特征。

具体流程

输入：训练数据集 $D$ ，特征集 $A$ ，阈值 $\varepsilon$
输出：决策树 $T$

若 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；
若 $A = \varnothing$ ，则 $T$ 为单结点树，并将 $T$ 中实例数量最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
否则，计算 $A$ 中各特征对 $D$ 的信息增益比，选择信息增益比最大的特征 $A_g$ ；
如果 $A_g$ 的信息增益比小于阈值 $\varepsilon$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
否则，对 $A_g$ 的每一个可能指 $a_i$ ，依照 $A_g = a_i$ 将 $D$ 分割为若干非空自己 $D_i$ ，将 $D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $T$ ，返回 $T$ ；
对第 $i$ 个子节点，以 $D_i$ 为训练集，以 $A - \{ A_g \}$ 为特征集，递归地调用前5步，得到子树 $T_i$ ，返回 $T_i$

CART算法

CART是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为"是"和"否"，这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测地概率分布，也就是在给定地条件下输出地条件概率分布。
CART算法由以下两步组成：

决策树生成：基于训练数据集生成决策树，生成地决策树要尽量大
决策树剪枝：用验证数据集对已生成地树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝地标准

CART生成算法

输入：训练数据集 $D$ ，停止计算的条件；
输出：CART决策树

假设结点的训练数据集为 $D$ ，计算现有特征对该数据集的基尼指数。此时，对每一个特征 $A$ ，对其可能取的每个值 $a$ ，更具样本点对 $A=a$ 的测试为"是"或"否"将分割成 $D_1$ 和 $D_2$ 两部分，利用公式计算 $A=a$ 时的基尼指数。
在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
对两个子结点调用前两步，直至满足停止条件。
生成CART决策树。算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。

CART剪枝算法

输入：CART算法生成的决策树 $T_0$ ；
输出：最优决策树 $T_\alpha$

设 $k=0$ ， $T=T_0$
设 $\alpha = +\infty$
自下而上地对各内部结点 $t$ 计算 $C(T_t)$ ， $\mid T_t \mid$ 以及
$g(t) = \frac {C(t) - C(T_t)} {\mid T_t \mid -1}$ $\alpha = \min(\alpha, g(t))$ 这里， $T_t$ 表示以 $t$ 为根结点的子树， $C(T_t)$ 是对训练数据的预测误差， $\mid T_t \mid$ 是 $T_t$ 的叶结点个数。
自上而下地访问内部结点 $t$ ，如果 $g(t) = \alpha$ ，进行剪枝，并对叶结点 $t$ 以多数表决法决定其类，得到树 $T$
设 $k = k + 1$ ， $\alpha_k = \alpha$ ， $T_k = T$
如果 $T$ 不是根结点单独构成的树，则返回步骤4
采用交叉验证法在子树序列 $T_0, T_1, \cdots, T_n$ 中选取最优子树 $T_\alpha$

决策树的修剪

概述

剪枝（pruning）是决策树学习算法处理过拟合问题地主要手段。决策树剪枝地基本策略有"预剪枝"（prepruning）和"后剪枝"（postpruning）。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点地划分不能带来决策树泛化性能的提升，则停止划分；后剪枝则是先从训练集生成一颗完整地决策树，人后自下而上对非叶结点进行考察，若该结点对应地子树替换为叶结点能带来泛化性能地提升，则将该子树替换成叶结点.

预剪枝

预剪枝就是在决策树生成过程中，在没有划分时，考虑能否带来决策树性能的提升。若可以提升决策树的性能则会进行划分，若不能则停止生长。
常用的方法如下：

当树的深度达到一定规模时，停止生长
当前结点的数量达到特定阈值时，停止生长
计算每次分裂对于测试集性能的提升，当小于指定阈值，甚至有所下降时，停止生长
当信息增益，信息增益比或基尼指数小于指定阈值时，停止生长

预剪枝优点：思想简单，算法高效，采用了贪心策略，适合大规模问题
预剪枝缺点：提前停止生长，存在欠拟合的风险

后剪枝

后剪枝的主要分类包括：

错误率降低剪枝（Reduce Error Pruning, REP）
悲观剪枝（Pressimistic Error Pruning, PEP）
代价复杂度剪枝（Cost Complexity Pruning, CCP）
最小误差剪枝（Minimum Error Pruning, MEP）
CVP（Critical Value Pruning）
OPP（Optimal Pruning）

其中，最小误差剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现。设树 $T$ 的叶结点个数为 $\mid T \mid$ ， $t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个， $k = 1, 2, \cdots, K$ ， $H_t (T)$ 为 $t$ 上的经验熵， $\alpha \geq 0$ 为参数，则决策树学习中的损失函数可以定义为：
$C_\alpha (T) = \sum_{t=1}^{\mid T \mid} N_t H_t (T) + \alpha \mid T \mid$ 输入：生成算法产生的整个树 $T$ ，参数 $\alpha$ ；
输出：修剪后的子树 $T_\alpha$

计算每个结点的经验熵
递归地从树的叶结点向上回缩
设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 与 $T_A$ ，其对应的损失函数分别是 $C_\alpha (T_B)$ 与 $C_\alpha (T_A)$ ，如果
$C_\alpha (T_B) \leq C_\alpha (T_A)$ 则进行剪枝，即将父节点变成新的叶结点。
返回步骤2，直至不能继续为止，得到损失函数最小的子树 $T_\alpha$