决策树

决策树模型

决策树(decision tree) 是一种基本的分类与回归算法。决策树呈树形结构，在分类问题中表示基于特征对实例进行分类的过程，它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用训练好的决策模型进行分类。

分类决策树模型是一种由结点(node)和有向边(directed edge) 组成的树形结构。结点有两种类型：内部节点(internal node)，表示一个特征或属性；叶结点(leaf node)，表示一个类。用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至到达叶结点。对吼将实例分到叶结点对应的类中。

决策树可以看成一个if-then规则的集合，满足互斥并且完备的性质。决策树根结点到叶结点的每一条路径中，路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。

决策树还表示给定特征条件下类的条件概率分布，这一分布定义在特征空间的一个划分(partition)上。将特征空间划分为互不相交的单元(cell)或区域(region)，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设$X$为表示特征的随机变量，$Y$为表示类的随机变量，那么该条件概率分布可以表示为$P(Y|X)$。$X$取值于给定划分下单元的集合，$Y$取值于类的集合。各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的一类去。

决策树学习的本质是从训练数据集中归纳出一组分类规则。与训练集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个，也可能一个都没有。我们需要的是一个与训练数据矛盾较小的，同时具有很好的泛化能力的决策树。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间的类的条件概率模型有无穷多个，我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。

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

开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，使树变得简单，从而使其具有更好的泛化能力。具体地，去掉过于细分的叶结点，使其退回到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。通常，层数越多即越深的决策树的复杂性越高，层数越少即越浅的决策树的复杂性越低。

特征选择

特征选择(feature selection) 是决定用哪个特征来划分特征空间。特征选择在于选取对训练数据具有分类能力的特征，以提高决策树的学习效率。通常特征选择的准则是信息增益或信息增益比。

信息增益

$$ H(X)=\sum_{i=1}^{n}p_i\log p_i $$$$ H(p)=\sum_{i=1}^{n}p_i \log p_i $$$$ P(X=x_{i}, Y=y_{j})=p_{ij},\ \ i=1,2,\cdots,n;\ \ j=i=1,2,\cdots,m $$$$ 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)。

$$ g(D,A)=H(D)-H(D|A) $$

一般地，熵$H(Y)$与条件熵$H(Y|X)$之差称为互信息(mutual information)，决策树中的信息增益等价于训练数据集中类与特征的互信息。

信息增益表示由于特征$A$使得对数据集$D$的分类的不确定性减少的程度。显然，对数据集$D$而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。根据信息增益准则的特征选择方法是：对训练数据集(或子集)$D$，计算其每个特征的信息增益，选择信息增益最大的特征。

设训练数据集为$D$，$|D|$表示其样本容量。设有$K$个类$C_k,k=1,2,\cdots,K$，$|C_k|$为术语类$C_k$的样本个数。设特征$A$有$n$个不同的取值${a_1,a_2,\cdots,a_n}$，根据特征$A$的取值将$D$划分为$n$个子集$D_1,D_2,\cdots,D_n$，$|D_i|$为$D_i$的样本个数记子集$D_i$中属于类$C_k$的样本集合为$D_{ik}$，即$D_{ik}=D_i \cap C_k$，$|D_{ik}|$为$D_{ik}$的样本个数。

信息增益算法如下：

输入：训练数据集$D$和$A$；

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

$$ H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}\log \frac{|C_k|}{|D|} $$$$ 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 \frac{|D_{ik}|}{|D_i|} $$$$ g(D,A)=H(D)-H(D|A) $$

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值角度的特征的问题。使用信息增益比(information gain ratio)可以对这一问题进行校正，这是特征选择的另一准则。

$$ 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|} $$

$n$是特征$A$取值的个数。

基尼指数

$$ Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2 $$$$ Gini(D)=1-\sum_{k=1}^{K}\left(\frac{|C_k|}{|D|}\right)^2 $$$$ 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$的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。

决策树的生成

ID3算法

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

输出：决策树$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$的信息增益小于阈值$\varepsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的标记，返回$T$；

(5) 否则，对$A_g$的每一可能值$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$。

C4.5算法

C4.5算法与ID3算法相似，改进的地方是C4.5采用信息增益比作为特征选择的标准，而ID3算法是使用信息增益作为特征选择标准。

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

输出：决策树$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$的信息增益小于阈值$\varepsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的标记，返回$T$；

(5) 否则，对$A_g$的每一可能值$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) 是决策树学习算法对付过拟合的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重读，有时会造成决策树分支过多，这时就可能因训练样本学得“太好”了，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致过拟合。

决策树剪枝的基本策略有预剪枝和后剪枝两种。**预剪枝(pre-pruning)是指在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝(post-pruning)**则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升(在验证集上准确率性能提高)，则将该子树替换为叶结点。

预剪枝通常在生成决策树的过程中使用一个验证集来决定每次划分，因此可以使得很多分支没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能，甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心”本质禁止一些分支的展开，带来了欠拟合的风险。

后剪枝先从训练集生成一棵完整的决策树，再自底向上遍历每个内部结点，若合并某个内部结点后能够带来在验证集上的精度提升，则合并该结点。以此类推，直至无法再合并为止。

一般来说，后剪枝决策树通常比预剪枝决策树保留了更多的分支，欠拟合风险更小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在完全生成决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

连续与缺失值

连续值处理

$$ 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) 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

给定训练集$D$和属性$a$，令$\tilde D$表示$D$中在属性$a$上没有缺失值的样本子集，并假定我们为每一个样本$x$赋予一个权重$w_x$。对问题(1)，显然我们仅可根据$\tilde D$来判断$a$的优劣。对问题(2)，若样本$x$在划分属性$a$上取值已知，则将$x$划入与其取值对应的子结点，且样本权在子结点中保持为$w_x$。若样本$x$在划分属性$a$上取值未知，则将$x$同时划入所有子结点，且对样本在属性$a$不同取值上的权值进行一定调整。

多变量决策树

若把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类意味着在这个做表空间中寻找不同样本之间的分类边界。决策树形成的分类边界有一个明显的特点：轴平行(axis-parallel)，即它的分类边界由若干个与坐标轴平行的分段组成。

这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值。但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，此时决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

多变量决策树(multivariate decision tree) 能够实现特征空间的“斜划分”甚至更复杂划分的决策树。以斜划分为例，在此类决策树中，非叶结点不再是针对某个属性，而是对属性的线性组合进行测试。

使用scikit-learn中的决策树算法对鸢尾花数据进行分类

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report


def plot_decision_boundary(model, axis):
    """
    在axis范围内绘制模型model的决策边界
    :param model: classification model which must have 'predict' function
    :param axis: [left, right, down, up]
    """
    x0, x1 = np.meshgrid(
        np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
        np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1),
    )
    X_new = np.c_[x0.ravel(), x1.ravel()]

    y_predict = model.predict(X_new)
    zz = y_predict.reshape(x0.shape)

    from matplotlib.colors import ListedColormap
    custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])

    plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)


X, y = load_iris(return_X_y=True)
X = X[:, :2]  # 仅选择前两个特征，便于绘制决策边界
X_train, X_test, y_train, y_test = train_test_split(X, y)
print(X_train.shape, X_test.shape, y_train.shape, y_test.shape)  # (112, 2) (38, 2) (112,) (38,)

# 尝试不同限定深度的决策树，并绘制其决策边界
dec_tree = DecisionTreeClassifier()
dec_tree.fit(X_train, y_train)

dec_tree_10 = DecisionTreeClassifier(max_depth=10)
dec_tree_10.fit(X_train, y_train)

dec_tree_6 = DecisionTreeClassifier(max_depth=6)
dec_tree_6.fit(X_train, y_train)

dec_tree_4 = DecisionTreeClassifier(max_depth=4)
dec_tree_4.fit(X_train, y_train)

plt.subplot(2, 2, 1)
plt.title('No max depth')
plot_decision_boundary(dec_tree, axis=[3, 8, 1, 5])
plt.scatter(X_test[y_test == 0, 0], X_test[y_test == 0, 1])
plt.scatter(X_test[y_test == 1, 0], X_test[y_test == 1, 1])
plt.scatter(X_test[y_test == 2, 0], X_test[y_test == 2, 1])

plt.subplot(2, 2, 2)
plt.title('Max depth = 10')
plot_decision_boundary(dec_tree_10, axis=[3, 8, 1, 5])
plt.scatter(X_test[y_test == 0, 0], X_test[y_test == 0, 1])
plt.scatter(X_test[y_test == 1, 0], X_test[y_test == 1, 1])
plt.scatter(X_test[y_test == 2, 0], X_test[y_test == 2, 1])

plt.subplot(2, 2, 3)
plt.title('Max depth = 6')
plot_decision_boundary(dec_tree_6, axis=[3, 8, 1, 5])
plt.scatter(X_test[y_test == 0, 0], X_test[y_test == 0, 1])
plt.scatter(X_test[y_test == 1, 0], X_test[y_test == 1, 1])
plt.scatter(X_test[y_test == 2, 0], X_test[y_test == 2, 1])

plt.subplot(2, 2, 4)
plt.title('Max depth = 4')
plot_decision_boundary(dec_tree_4, axis=[3, 8, 1, 5])
plt.scatter(X_test[y_test == 0, 0], X_test[y_test == 0, 1])
plt.scatter(X_test[y_test == 1, 0], X_test[y_test == 1, 1])
plt.scatter(X_test[y_test == 2, 0], X_test[y_test == 2, 1])

print('classification accuracy when max depth is with no limitation: ', dec_tree.score(X_test, y_test))
print('classification accuracy when max depth is 10: ', dec_tree_10.score(X_test, y_test))
print('classification accuracy when max depth is 6: ', dec_tree_6.score(X_test, y_test))
print('classification accuracy when max depth is 4: ', dec_tree_4.score(X_test, y_test))

plt.show()

参考资料

  • 周志华. 机器学习. 北京: 清华大学出版社, 2016.

  • 李航. 统计学习方法. 北京: 清华大学出版社, 2019.

  • 决策树维基百科：https://en.wikipedia.org/wiki/Decision_tree_learning