决策树模型与学习

决策树模型

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。

用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点，这时，每一个子结点对应该特征的一个取值。如此递归地对实例进行测试并分配，直至到达叶结点。最后将实例分到叶结点的类中。

决策树与 if-then 规则

可以将决策树看成一个 if-then 规则的集合。将决策树转换成 if-then 规则的过程如下：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应规则的条件，而叶结点的类对应规则的结论。

决策树的路径或其对应的 if-then 规则集合具有一个重要性质：互斥且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。

下面的例子中，决策树通过 if-then-else 的决策规则来学习数据从而估测一个正弦图像。决策树越深入，决策规则就越复杂且对数据的拟合越好，但也有可能过拟合，学到噪声数据。

import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))

regr_1 = DecisionTreeRegressor(max_depth=2)
regr_2 = DecisionTreeRegressor(max_depth=5)
regr_1.fit(X, y)
regr_2.fit(X, y)

X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
y_1 = regr_1.predict(X_test)
y_2 = regr_2.predict(X_test)

plt.figure()
plt.scatter(X, y, s=20, edgecolors="black", c="darkorange", label="data")
plt.plot(X_test, y_1, color="cornflowerblue", label="max_depth=2", linewidth=2)
plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

决策树学习

假定给定训练数据集
$$D=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$$
其中，$x_i=(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)})$ 为输入实例的特征向量，$n$ 为特征个数， y i ∈ { 1 , 2 , ⋯   , K } y_i \in \{1, 2, \cdots, K\} yi​∈{1,2,⋯,K} 为类标记。

决策树学习本质上是从训练数据集中归纳出一组分类规则。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。我们选择的决策树模型不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。决策树学习用损失函数表示这一目标，损失函数通常是正则化的极大似然函数。

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应特征空间的划分，也对应决策树的构建。

首先构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；

如果还有子集不能够被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。

以上生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据未必有很好的分类能力，即有可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单。具体来说，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。

如果特征数量很多，也可以在决策树学习开始的时候对特征进行选择，只留下对训练数据有足够分类能力的特征。

特征选择

特征选择在于选取对训练数据具有分类能力的特征，通常特征选择的准则是信息增益或信息增益比。为了便于说明，先给出熵与条件熵的定义。

熵（entropy）是表示随机变量不确定性的度量。设 $X$ 是一个取有限个值的离散随机变量，其概率分布为
$$P(X=x_i)=p_i,i=1,2,\cdots ,n$$则随机变量 $X$ 的熵定义为
$$H(X)=-\sum _{i=1}^n{p}_i\log p_i$$由定义可知，熵只依赖于 $X$ 的分布，而与 $X$ 的取值无关，所以也可以将 $X$ 的熵记作 $H(p)$. 熵越大，随机变量的不确定性就越大。从定义可验证
$$0\le H(p)\le \log n$$

设有随机变量 $(X,Y)$，其联合概率分布为
$$P(X=x_i,Y=y_j)=p_{ij},i=1,2,\cdots ,n,j=1,2,\cdots ,m$$条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性：
$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i),p_i=P(X=x_i),i=1,2,\cdots ,n$$当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。

信息增益（information gain）表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。

特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ 定义为集合 $D$ 的经验熵与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即$$g(D,A)=H(D)-H(D|A)$$

决策树学习应用信息增益准则选择特征。给定训练数据集 $D$ 和特征 $A$，经验熵 $H(D)$ 表示对数据集 $D$ 进行分类的不确定性，而经验条件熵 $H(D|A)$ 表示在特征 $A$ 给定的条件下对数据集 $D$ 进行分类的不确定性。那么它们的差就表示由于特征 $A$ 而使得对数据集 $D$ 的分类的不确定性减少的程度。

设训练数据集为 $D$，$|D|$ 表示其样本容量，即样本个数。

设有 $K$ 个类 $C_k,k=1,2,\cdots ,K$，$|C_k|$ 为属于类 $C_k$ 的样本个数。

设特征 $A$ 有 $n$ 个不同的取值 { a 1 , a 2 , ⋯   , a n } \{a_1,a_2,\cdots,a_n\} {a1​,a2​,⋯,an​}，根据特征 $A$ 的取值将 $D$ 划分为 $n$ 个子集 $D_1,\cdots ,D_n$，$|D_i|$ 为 $D_i$ 的样本个数。

记子集 $D_i$ 中属于类 $C_k$ 的样本的集合为 $D_{ik}$，信息增益的算法如下：

输入：训练数据集 $D$ 和特征 $A$。

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

1. 计算数据集 $D$ 的经验熵 $H(D)$ $$H(D)=-\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}$$
2. 计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$ $$H(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{|D_i|}{\log }_2\frac{|D_{ik}|}{|D_i|}$$
3. 计算信息增益 $$g(D,A)=H(D)-H(D|A)$$

使用信息增益作为划分训练数据集的特征的依据，存在偏向于选择取值较多的特征的问题。使用信息增益比 $g_R(D,A)$ 可以对这一问题进行校正。
$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$其中，$H_A(D)=-{\sum }_{i=1}^n\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}$.

决策树的生成

ID3 算法

ID3 算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是，从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。ID3 相当于用极大似然法进行概率模型的选择。

输入：训练数据集 $D$，特征集 $A$，阈值 $ϵ$。

输出：决策树 $T$。

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

以下表所示的数据集（贷款申请样本）为例，利用 ID3 算法构建决策树。

首先由之前的信息增益算法计算出特征 $A_3$ （有自己的房子）信息增益值最大（步骤省略），所以选择特征 $A_3$ 作为根结点的特征。它将训练集划分为两个子集 $D_1$（$A_3$ 取值为“是”）和 $D_2$（$A_3$ 取值为“否”）。由于 $D_1$ 只有同一类的样本点，所以它成为一个叶结点。

对 $D_2$ 则需要从 $A_1$（年龄），$A_2$（有工作）和 $A_4$（信贷情况）中选择新的特征。计算各个特征对数据集 $D_2$ 的信息增益，得到信息增益最大的特征 $A_2$（有工作）。从这一结点引出两个子结点，一个对应“有工作”的子结点，包含 3 个样本，属于同一个类（“是”），成为叶结点；另一个对应“无工作”的结点，包含 6 个样本，也都属于同一类（“否”），成为叶结点。

生成的决策树如下图所示：

我们构建一个决策树来对鸢尾花数据集进行分类，经过训练，我们可以使用 export_graphviz 导出器以 Graphviz 格式导出决策树：

from sklearn.datasets import load_iris
from sklearn import tree
import graphviz
iris = load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data, iris.target)

dot_data = tree.export_graphviz(clf, out_file=None, feature_names=iris.feature_names,
                                class_names=iris.target_names, filled=True,
                                rounded=True, special_characters=True)
graph = graphviz.Source(dot_data)
graph

该决策树决策过程涉及到 CART 算法，我们稍后会详细介绍。

C4.5 算法

C4.5 算法在生成的过程中，用信息增益比来选择特征。

输入：训练数据集 $D$，特征集 $A$，阈值 $ϵ$。

输出：决策树 $T$。

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

决策树的剪枝

决策树生成算法生成的树往往会出现过拟合现象，对已生成的树进行简化的过程称为剪枝（pruning）。决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树 $T$ 的叶结点个数为 $|T|$，$t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中属于 $k$ 类的样本点有 $N_{tk}$ 个，$H_t(T)$ 为叶结点 $t$ 上的经验熵，则决策树学习的损失函数可以定义为
$$C_{\alpha }(T)=\sum _{t=1}^{|T|}{N}_t{H}_t(T)+\alpha |T|$$其中经验熵为$$H_t(T)=-\sum _k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$$令 $$C(T)=\sum _{t=1}^{|T|}{N}_t{H}_t(T)=-\sum _{t=1}^{|T|}\sum _{k=1}^K{N}_{tk}\log \frac{N_{tk}}{N_t}$$ 则损失函数为 $$C_{\alpha }(T)=C(T)+\alpha |T|$$

$C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，$|T|$ 表示模型复杂度，参数 $\alpha \ge 0$ 控制两者之间的影响。较大的 $\alpha$ 促使选择较简单的模型，较小的 $\alpha$ 促使选择较复杂的模型。

决策树生成只考虑了通过提高信息增益对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

下面介绍一种简单的决策树学习的剪枝算法：

输入：生成算法产生的整个树 $T$，参数$\alpha$。

输出：修剪后的子树 $T_{\alpha }$。

1. 计算每个结点的经验熵；

2. 递归地从树的叶结点向上回缩；
   
   设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 与 $T_A$，其对应的损失函数值分别是 $C_{\alpha }(T_B)$ 与 $C_{\alpha }(T_A)$，如果$$C_{\alpha }(T_B)\ge C_{\alpha }(T_A)$$则进行剪枝，即将父结点变为新的叶结点。上式只需考虑两个树的损失函数的差，其计算可以在局部进行，可由一种动态规划的算法实现。

3. 返回步骤 2，直至不能继续为止，得到损失函数最小的子树 $T_{\alpha }$。

CART 算法

分类与回归树（classification and regression tree，CART）是广泛使用的决策树学习方法。CART 是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。CART 算法由以下两步组成：
(1) 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
(2) 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

CART 生成

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。

回归树的生成

给定训练数据集 $D=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$，考虑如何生成回归树。

一颗回归树对应着输入空间的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为 $M$ 个单元 $R_1,R_2,\cdots ,R_M$，并且在每个单元上有一个固定的输出值 $c_m$，于是回归树模型可表示为
$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$
当输入空间的划分确定时，可用平方误差 ${\sum }_{x_i\in R_m}(y_i-f(x_i){)}^2$ 来表示回归树对训练数据的预测误差。单元 $R_m$ 上的最优输出值 ${\hat{c}}_m$ 是 $R_m$ 上的所有输入实例 $x_i$ 对应的输出 $y_i$ 的均值，即
$${\hat{c}}_m=\text{avg}(y_i|x_i\in R_m)$$
问题是怎样对输入空间进行划分。这里采用启发式的方法，选择第 $j$ 个变量 $x^{(j)}$ 和它取的值 $s$ 作为切分变量和切分点，并定义两个区域：
R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } ,    R 2 ( j , s ) = { x ∣ x ( j ) > s } R_1(j,s)=\{x|x^{(j)}\le s\},\ \ R_2(j,s)=\{x|x^{(j)} > s\} R1​(j,s)={x∣x(j)≤s},  R2​(j,s)={x∣x(j)>s}
然后寻找最优切分变量 $j$ 和最优切分点 $s$。具体地，求解
$$\underset{j,s}{\min }\left[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2\right]$$
对固定输入变量 $j$，可以找到最优切分点 $s$，遍历所有输入变量，找到最优的切分变量 $j$，构成一个对 $(j,s)$。依次将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这样的回归树通常称为最小二乘回归树。

分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$，则概率分布的基尼指数定义为
$$\text{Gini}(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$

对于给定的样本集合 $D$，其基尼指数为
$$\text{Gini}(D)=1-\sum _{k=1}^K{\left(\frac{|C_k|}{|D|}\right)}^2$$ 其中，$C_k$ 是 $D$ 中属于第 $k$ 类的样本子集。

如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_1$ 两部分，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为
$$\text{Gini}(D,A)=\frac{|D_1|}{|D|}\text{Gini}(D_1)+\frac{|D_2|}{|D|}\text{Gini}(D_2)$$

基尼指数 $\text{Gini}(D)$ 表示集合 $D$ 的不确定性，基尼指数越大，样本集合的不确定性也就越大，这一点与熵相似。

分类树生成算法：

输入：训练数据集 $D$，停止计算的条件

输出：CART 决策树

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

1. 设结点的训练数据集为 $D$，计算现有特征对该数据集的基尼指数。此时，对每一个特征 $A$，对其可能取的每个值 $a$，将 $D$ 划分成 $D_1$ 和 $D_1$ 两部分，计算 $A=a$ 时的 $\text{Gini}(D,A)$;
2. 在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的最优切分点。按照最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去；
3. 对两个子结点递归地调用步骤 1 和步骤 2，直至满足停止条件；
4. 生成 CART 决策树。

算法停止计算的条件是结点中的样本个数小于预定阈值或样本集的基尼指数小于预定阈值，或者没有更多特征。

CART 剪枝

CART 剪枝算法由两步组成：首先从生成算法产生的决策树 $T_0$ 底端开始不断剪枝，直到 $T_0$ 的根结点，形成一个子树序列 { T 0 , T 1 , ⋯   , T n } \{T_0,T_1,\cdots, T_n\} {T0​,T1​,⋯,Tn​}；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。

1. 剪枝，形成一个子树序列
   
   在剪枝过程中，计算子树的损失函数 $$C_{\alpha }(T)=C(T)+\alpha |T|$$ 对于固定的 $\alpha$，一定存在使损失函数 $C_{\alpha }(T)$ 最小的子树 $T_{\alpha }$。Breiman 等人证明：可以用递归的方法对树进行剪枝：
   
   将 $\alpha$ 从小增大，$0={\alpha }_0<{\alpha }_1<...<{\alpha }_n<+\infty$，产生一系列区间 $[{\alpha }_i,{\alpha }_{i+1})$，剪枝得到的子树序列对应着区间 $\alpha \in [{\alpha }_i,{\alpha }_{i+1}),i=0,1,...,n$ 的最优子树序列 { T 0 , T 1 , ⋯   , T n } \{T_0,T_1,\cdots, T_n\} {T0​,T1​,⋯,Tn​}，序列中的子树是嵌套的。
   
   具体地，从整体树 $T_0$ 开始剪枝，对 $T_0$ 的任意内部结点 $t$，以 $t$ 为单结点树的损失函数是$$C_{\alpha }(t)=C(t)+\alpha$$ 以 $t$ 为根结点的子树 $T_t$ 的损失函数是 $$C_{\alpha }(T_t)=C(T_t)+\alpha |T_t|$$ 当 $\alpha =0$ 及 $\alpha$ 充分小时，有不等式 $$C_{\alpha }(T_t)<C_{\alpha }(t)$$ 当 $\alpha$ 增大时，在某一 $\alpha$ 有 $$C_{\alpha }(T_t)=C_{\alpha }(t)$$ 当 $\alpha$ 再增大时，不等式反向。只要 $\alpha =\frac{C(t)-C(T_t)}{|T_t|-1}$ ，$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)$ 设为 ${\alpha }_1$。$T_1$ 为区间 $[{\alpha }_1,{\alpha }_2)$ 的最优子树。
   
   如此剪枝下去，直至得到根结点。在这一过程中，不断地增加 $\alpha$ 的值，产生新的区间。

2. 在剪枝得到的子树序列中通过交叉验证选取最优子树 $T_{\alpha }$

References

[1] 《机器学习方法》，李航，清华大学出版社。
[2] sklearn 中文文档，https://www.sklearncn.cn/11/。