【机器学习-监督学习】决策树

本文主要是介绍【机器学习-监督学习】决策树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【作者主页】Francek Chen
【专栏介绍】$\lceil$Python机器学习$\rfloor$ 机器学习是一门人工智能的分支学科，通过算法和模型让计算机从数据中学习，进行模型训练和优化，做出预测、分类和决策支持。Python成为机器学习的首选语言，依赖于强大的开源库如Scikit-learn、TensorFlow和PyTorch。本专栏介绍机器学习的相关算法以及基于Python的算法实现。
【GitCode】专栏资源保存在我的GitCode仓库：https://gitcode.com/Morse_Chen/Python_machine_learning。

---

  本文开始，我们将介绍机器学习中与神经网络并行的另一大类模型——决策树（decision tree）模型及其变种。决策树模型是非参数化模型。决策树模型简称树模型，顾名思义，它采用了和树类似的结构。图1展示了现实中的树与计算机中的树的异同。现实中的树是根在下、从下向上生长的，计算机中的树却是根在上、从上向下生长的。但是，两者都有根、枝干的分叉与叶子。在计算机的树中，最上面的节点称为根节点，最下面没有分叉的节点称为叶节点。其中，根节点和内部节点都有一些边指向其他节点，这些被指向的节点就称为它的子节点。叶节点是树的最末端，没有指向其他节点的边。而除了根节点之外，每个内部节点和叶节点都有唯一的节点指向它，该节点称为其父节点。

图1 现实中的树和决策树中的结构

  如果对数据结构中的树有一些了解的话，应该很容易理解其构造。不过决策树并不需要用到数据结构的相关知识，我们可以简单地将这棵树看作一张流程图。在一棵决策树中，根节点和内部节点的作用是相同的，后面我们将其统称为内部节点。设输入样本为$x$，树上的每个内部节点都包含一个关于$x$的表达式$u(x)$，其每个分支对应表达式的一种取值。例如，某个节点的表达式为 $x>0$，它有两个分支，分别对应 $x>0$ 的情况和 $x\le 0$ 的情况。叶节点不包含判断条件，而是包含该决策树对样本的预测。比如在二分类任务中，叶节点的取值就可以是1或-1。这样，样本$x$从根节点出发，按照每个遇到的内部节点上的表达式和分支的判断条件，走到相应的子节点上。反复执行这个过程，直到样本来到叶节点为止。这时，叶节点的值就是决策树的输出。

  决策树由于其分支离散的特性，通常用来完成分类任务。在直角坐标系中，其分类的边界是与坐标轴平行的直线。图2展示了一棵简单的二分类决策树和其对应的分类边界，其输入是平面上的点$(x_1,x_2)$，图2(a)给出了决策树的结构，图2(b)中的蓝色和橙色虚线是决策树对应的分类边界。可以看出，决策树通过对数据空间多次进行平行于坐标轴的线性分割，最终可以组合出非线性分类的效果。

图2 用决策树分类的示例

一、决策树的构造

  那么，该如何为每个内部节点选择合适的表达式呢？我们的目标是使最终构造的决策树复杂度尽可能低，换句话说，判断一个样本的类别需要的期望次数尽可能少。我们来看下面的例子，表1是过去一段时间内小明是否外出活动和天气条件的关系。天气条件共有4个特征，其中天气和温度分别有3种取值，湿度和风力分别有2种取值。

表1 外出活动与天气条件的关系表

  我们来考虑从该表格中的数据构造决策树时，如何选择根节点上用来分类的特征。直观上，为了使整体复杂度最低，我们希望每一次分类都可以把不同类的样本尽可能分开，因此应当首先将有3种取值的特征放在根节点上。我们尝试用天气或温度作为根节点对数据进行一次分类，得到的两种决策树如图3所示。图中的每个圆点对应表格中的一个样本，红色表示没有外出活动，绿色表示外出活动。

图3 用天气和温度进行一次分类的结果

  两种分类方式得到的一次分类结果并不相同。可以看出，以天气作为特征，一次就可以将所有阴天的情况分好，接下来再分别考虑晴天和雨天；而以温度为特征，3种取值都需要进一步选择其他特征进行分类。换句话说，当我们知道了样本中的天气时，所获得的信息增益（information gain）比知道样本中的温度要大。而一个数据集总体的信息量是恒定的，因此，我们在每一步都应当选择能获得更多信息的特征作为分类标准。

  在逻辑斯谛回归中，我们已经介绍了信息量与信息熵的概念，这里再直接从随机变量的角度回顾一下。设离散随机变量$X$和$Y$的取值范围都是 $1,\cdots ,n$，那么$X$的熵为$$H(X)=-\sum _{i=1}^{n}P(X=i)\log P(X=i)$$

  如果将随机变量$X$取值为$i$看作事件$X_i$的话，那么其分布就是 $p(X_i)=P(X=i)$，这样上式和逻辑斯谛回归一文中给出的公式是相同的。因此，下面直接将$X$取值为$i$简写为$X_i$，$Y$的取值与$X$相同，简写为$Y_i$。随机变量$X$与$Y$的交叉熵为$$H(X,Y)=-\sum _{i=1}^{n}P(X_i)\log P(Y_i)$$

  我们通常用概率分布的熵的变化来作为信息的度量。当我们为一个分布引入额外信息时，其不确定度会减小，所以熵会降低。为此，我们引入条件熵的概念。在给定 $Y=j$ 的条件下，随机变量$X$的熵为$$H(X|Y_j)=-\sum _{i=1}^{n}P(X_i|Y_j)\log P(X_i|Y_j)$$

  如果随机变量$X$与$Y$独立，那么对于任意$i$，有条件概率 $P(X_i|Y_j)=P(X_i)$，对于任意$j$，有条件熵 $H(X|Y_j)=H(X)$，说明$Y$的取值对$X$的分布没有影响。如果随机变量$X$与$Y$始终相同，那么 $P(X_i|Y_j)=\mathbb{I}(i=j)$，条件熵 $H(X|Y_j)=0$，说明$Y$的取值确定后$X$的取值也唯一确定，其随机性消失，分布的熵变为0。进一步，如果给出的条件是$Y$的分布，那么条件熵$H(X|Y)$为$$H(X|Y_j)=E_Y[H(X|Y_j)]=-\sum _{j=1}^{n}P(Y_j)H(X|Y_j)=-\sum _{i=1}^n\sum _{j=1}^{n}P(X_i,Y_j)\log P(X_i|Y_j)$$

  在决策树中，记数据集中样本的类别是$X$，我们引入的分类特征是$Y$。由于数据集已知，$X$的分布和熵也是已知的。我们需要考虑的是加入特征$Y$后的信息增益。我们以上面表1的天气和温度两个特征为例，用推导出的公式分别计算用该特征分类获得的信息增益。

• 原始数据：共有14个样本，未外出活动 $X=0$ 的样本与外出活动 $X=1$ 的样本各占一半，从而有$$H(X)=-\frac{1}{2}\log \frac{1}{2}-\frac{1}{2}\log \frac{1}{2}=0.5+0.5=1$$

• 用天气分类：记晴天为$Y_{\mathrm{S}}$，阴天为$Y_{\mathrm{O}}$，雨天为$Y_{\mathrm{R}}$。

  • 晴天样本5个，其中外出2个，未外出3个，得$$H(X|Y_{\mathrm{S}})=-\frac{3}{5}\log \frac{3}{5}-\frac{2}{5}\log \frac{2}{5}\approx 0.9710$$
  • 阴天样本4个，其中外出4个，未外出0个，得$$H(X|Y_{\mathrm{O}})=-\frac{4}{4}\log \frac{4}{4}=0$$
  • 雨天样本5个，其中外出1个，未外出4个，得$$H(X|Y_{\mathrm{R}})=-\frac{4}{5}\log \frac{4}{5}-\frac{1}{5}\log \frac{1}{5}\approx 0.7219$$
  • 条件熵$$H(X|Y)\approx \frac{5}{14}\times 0.9710+\frac{4}{14}\times 0+\frac{5}{14}\times 0.7219\approx 0.6046$$
  • 获得信息增益$$I(X,Y)=H(X)-H(X|Y)\approx 1-0.6046\approx 0.3954$$

• 用温度分类：记热为$Y_{\mathrm{H}}$，适中为$Y_{\mathrm{M}}$，冷为$Y_{\mathrm{C}}$。类似可得
  $$\begin{array}{rl}H(X|Y_{\mathrm{H}})& =-\frac{2}{4}\log \frac{2}{4}-\frac{2}{4}\log \frac{2}{4}=1\\ H(X|Y_{\mathrm{M}})& =-\frac{1}{4}\log \frac{1}{4}-\frac{3}{4}\log \frac{3}{4}\approx 0.8113\\ H(X|Y_{\mathrm{C}})& =-\frac{4}{6}\log \frac{4}{6}-\frac{2}{6}\log \frac{2}{6}\approx 0.9183\\ H(X|Y)& \approx \frac{4}{14}\times 1+\frac{4}{14}\times 0.8113+\frac{6}{14}\times 0.9183\approx 0.9111\\ I(X,Y)& =H(X)-H(X|Y)\approx 1-0.9111\approx 0.0889\end{array}$$

  通过计算可以直观地看出，用天气进行分类所获得的信息大于用温度分类所获得的信息。但是，引入某个特征$Y$所获得的信息较多可能只是因为$Y$本身包含的信息就很多。例如，假设数据集中包含“样本编号”这一特征，每个样本的编号都是唯一的。那么，虽然用样本标号可以直接将所有数据都分类好，但是我们会得到一个只有一层、但有14个分支的决策树，这无非将进一步分类的复杂度转移到了判断该走哪个分支上。即使从直觉上来说，这样的分类方式也是没有意义的。因此，我们引入信息增益率（information gain rate）$I_R(X,Y)$的概念，定义为获得的信息增益与$Y$关于$X$复杂度的比值：$$I_R(X,Y)=\frac{I(X,Y)}{H_Y(X)}=\frac{H(X)-H(X|Y)}{H_Y(X)}$$ 其中，$H_Y(X)$表示用特征$Y$对$X$做划分得到分布的熵。设$\mathcal{Y}$是$Y$可能的取值集合，$H_Y(X)$定义为$$H_Y(X)=-\sum _{y\in \mathcal{Y}}\frac{|X_{Y=y}|}{|X|}\log \frac{|X_{Y=y}|}{|X|}$$ 式中，$|X|$表示样本的总数量，$|X_{Y=y}|$表示样本中特征 $Y=y$ 的数量。注意该式和条件熵$H(X|Y)$含义的区别。在决策树中，$H_Y(X)$可以用来衡量为节点进行更精细分类（划分）的价值。我们再以同样的例子计算用天气、温度或所有特征一起分类的信息增益率。

• 用天气分类：统计数量得 $|X_{Y=\mathrm{S}}|=5,|X_{Y=\mathrm{O}}|=4,|X_{Y=\mathrm{R}}|=5$，于是有
  $$\begin{array}{rl}{H}_Y(X)& =-\frac{5}{14}\log \frac{5}{14}-\frac{4}{14}\log \frac{4}{14}-\frac{5}{14}\log \frac{5}{14}\approx 1.5774\\ I_R(X,Y)& =\frac{I(X,Y)}{H_Y(X)}\approx \frac{0.3954}{1.5774}\approx 0.2507\end{array}$$

• 用温度分类：统计数量得 $|X_{Y=\mathrm{H}}|=4,|X_{Y=\mathrm{M}}|=4,|X_{Y=\mathrm{C}}|=6$，于是有
  $$\begin{array}{rl}{H}_Y(X)& =-\frac{4}{14}\log \frac{4}{14}-\frac{4}{14}\log \frac{4}{14}-\frac{6}{14}\log \frac{6}{14}\approx 1.5567\\ I_R(X,Y)& =\frac{I(X,Y)}{H_Y(X)}\approx \frac{0.0889}{1.5567}\approx 0.0571\end{array}$$

  比较信息增益率的大小，我们发现用天气作为分类特征确实是最优的选择。可以自行验算，取湿度或风力作为分类特征的信息增益率都比用天气分类要小。综上所述，我们可以通过在每个节点上选取信息增益率最大的分类特征来构建决策树，从而使其整体复杂度较低。

二、ID3算法与C4.5算法

  由Ross Quinlan在1986年提出的ID3（iterative dichotomiser 3）算法是最早的根据信息增益进行决策树构造的算法之一，同时也是后续大多数决策树算法的基础。ID3算法的流程与我们上面所说的基本相同，从根节点开始，每次选取使信息增益$I(X,Y)$最大的特征进行分类，并对产生的子节点递归进行特征选取和分裂，直到所有节点上的数据都属于同一类为止。

  由于ID3算法倾向于无限精细划分，它存在两个较为严重的问题。第一个问题是，如果用于划分的特征本身就较为复杂，就会出现上文提到的复杂度转移现象。一方面，继续分类的复杂度只是转移到了分支选择上；另一方面，这样的精细分类极有可能只对当前的训练集适用，容易出现过拟合现象。因此，我们可以将选取特征的标准由信息增益$I(X,Y)$改为信息增益率$I_R(X,Y)$来抑制这一现象，得到ID3算法的改进之一——C4.5算法。

  第二个问题是，ID3算法直到将所有数据分类完成才会停止，如果数据集中包含较多相似的数据，ID3算法构造的决策树就会出现非常长的分支，大大增加算法的复杂度。我们需要在分类准确率和决策树的复杂度之间寻找平衡。例如服装厂生产的衣服尺寸，以身高来说，如果只生产尺寸为170cm的衣服显然无法满足需求；而如果为每个不同身高的人都生产相应身高的衣服，成本显然又太高。因此，服装厂可能会将身高以5cm分为一档，生产160cm、165cm、170cm 等等尺寸的衣服。为了解决这一问题，我们仿照正则化约束的思想，引入决策树$T$的代价函数$C(T)$。设决策树的叶节点数量为$|T|$，我们给每个叶节点编号 $t=1,\cdots ,|T|$。对于叶节点$t$，记其上的样本数为$N_t$，其中类别为$k$的样本数为$N_{tk}$。那么，该叶节点上数据的熵为$$H_t(T)=-\sum _k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$$ 该式可以用来衡量该叶节点分类的精度。利用这一函数，我们将代价函数$C(T)$定义为$$C(T)=\sum _{t=1}^{|T|}{N}_t{H}_t(T)+\lambda |T|$$ 其中，$\lambda \ge 0$ 是正则化系数。上式的第一项表示所有叶节点的熵的总和，决策树分类越精确，这一项就越小。当决策树完全精确时，所有叶节点的熵都为0，该项就取到了最小值。上式的第二项用来约束决策树中叶节点的个数，当决策树为了追求精度而产生更多的叶节点时，这一项就会增大。因此，上式在决策树的精度和复杂度之间取得了平衡。我们在构造决策树时，可以以最小化$C(T)$为目标，对于每个待分裂的节点计算分裂前后的$C(T)$，只在分裂会使代价减小的情况下执行分裂操作。

三、CART算法

  在前两节中，我们介绍的ID3算法和其改进算法C4.5算法都只能解决分类问题。决策树中每个节点的分叉在将整个空间不断划分，最后得到的每个叶子节点对应空间中的一块区域，而模型就认为该区域中的样本都属于同一类别。对于回归问题来说，这一思路同样适用。我们可以将同一叶节点内样本标签值的平均来作为模型对该区域的预测。但是，ID3和C4.5的节点划分是以离散随机变量的熵为基础的，并不能很好衡量回归问题下划分带来的收益。因此，分类和回归树（classification and regression tree，CART）采用了误差的平方和作为回归问题下寻找最优特征的标准。下面，我们就来介绍用CART算法构建回归树和分类树模型的方法。

  假设样本 $\mathbf{x}\in {\mathbb{R}}^d$，标签 $y\in \mathbb{R}$。模型有$T$个叶节点，将空间分成了$T$个区域 ${\mathcal{R}}_1,\cdots ,{\mathcal{R}}_T$，其中区域${\mathcal{R}}_t$上模型的预测值是$c_t$，那么整个模型$f$表示的函数可以写为$$f(x)=\sum _{t=1}^T{c}_t\mathbb{I}(\mathbf{x}\in {\mathcal{R}}_t)$$

  对于回归问题，我们可以用最经典的MSE损失当作优化目标：$$J(f)=\frac{1}{2N}\sum _{i=1}^N(y_i-f(x_i){)}^2$$

  容易计算出，当模型在区域上的预测值${\hat{c}}_t$是该区域所有样本标签值的平均时，MSE损失最小。记叶节点$t$中的样本数量为$N_t$，那么$${\hat{c}}_t=\frac{1}{N_t}\sum _{x_i\in {\mathcal{R}}_t}{y}_i$$

  注意，CART算法的回归树不仅需要处理离散特征，还需要处理连续取值的特征。因此，我们在节点划分时不仅需要找到最优特征，还需要判断最优的划分阈值。假设我们选择了特征$j$和阈值$s$，那么当前节点会被分成两个子节点，分别代表区域 R 1 ( j , s ) = { x ∣ x j ≤ s } \mathcal R_1(j,s)=\{\boldsymbol x|x_j\le s\} R1​(j,s)={x∣xj​≤s} 和 R 2 ( j , s ) = { x ∣ x j > s } \mathcal R_2(j,s)=\{\boldsymbol x|x_j>s\} R2​(j,s)={x∣xj​>s}。我们在每次划分时，需要选择使两个区域的平方误差和最小的特征$j$和阈值$s$：$$\underset{j,s}{\min }\sum _{x_i\in {\mathcal{R}}_1(j,s)}(x_i-{\hat{c}}_1{)}^2+\sum _{x_i\in {\mathcal{R}}_2(j,s)}(x_i-{\hat{c}}_2{)}^2$$ 其中，$\hat{c}$是区域内所有样本标签值的平均值。求解这一优化问题中的特征$j$没有太好的办法，只能对每个特征依次枚举。而对阈值$s$来说，我们应当先把当前节点上的样本按该特征的值由小到大排序，记为$j_1,\cdots ,j_r$，并让$s$对数据进行遍历，再不断计算两边的误差平方和，选择使两个区域误差平方和最小的点作为最优的$s$。我们以 $r=6$ 个样本为例演示求解$s$的过程。如图4(a)所示，初始时我们让$s$在6个样本的最中间，即 $j_3<s<j_4$。这时，两边的平方误差和为
$$\begin{array}{rl}{l}_{3,4}(s,j)& =\sum _{k=1}^3(j_k-{\hat{c}}_1{)}^2+\sum _{k=4}^6(j_k-{\hat{c}}_2{)}^2\\ & =\sum _{k=1}^3{j}_k^2-2{\hat{c}}_1\sum _{k=1}^3{j}_k+{\hat{c}}_1^2+\sum _{k=4}^6{j}_k^2-2{\hat{c}}_2\sum _{k=4}^6{j}_k+{\hat{c}}_2^2\\ & =\sum _{k=1}^6{j}_k^2-\frac{2}{3}{\left(\sum _{k=1}^3{j}_k\right)}^2-\frac{2}{3}{\left(\sum _{k=4}^6{j}_k\right)}^2+\frac{1}{9}{\left(\sum _{k=1}^3{j}_k\right)}^2+\frac{1}{9}{\left(\sum _{k=4}^6{j}_k\right)}^2\\ & =-\frac{1}{3}{\left(\sum _{k=1}^3{j}_k\right)}^2-\frac{1}{3}{\left(\sum _{k=4}^6{j}_k\right)}^2+C\end{array}$$ 其中，$C$是与$s$无关的常数。假如我们把$s$从$j_3$与$j_4$中间向右移动一个样本，到$j_4$与$j_5$之间，如图4(b)所示，那么平方误差和可以类似计算得$$l_{4,5}(s,j)=-\frac{1}{4}{\left(\sum _{k=1}^4{j}_k\right)}^2-\frac{1}{2}{\left(\sum _{k=5}^6{j}_k\right)}^2+C$$

图4 CART算法的回归树的划分阈值求解

  可以看出，为了快速计算$s$在不同位置时的误差，我们只需要提前计算出 $S_m=\sum _{k=1}^m{j}_k$，就可以将上式写成$$l_{3,4}(s,j)=-\frac{1}{3}{S}_3^2-\frac{1}{3}(S_6-S_3{)}^2+C,l_{4,5}(s,j)=-\frac{1}{4}{S}_4^2-\frac{1}{2}(S_6-S_4{)}^2+C$$ 这样，无论$s$在哪个位置，我们都可以在$O(1)$的时间内算出$l(s,j)$，无须每次再分别求和。此外，容易发现$s$的位置应当使左右两边的误差尽可能平衡。因此，如果左边的误差比右边大，应当将$s$向右调整，反之则向左调整，最后找到最优的$s$的位置。

  除了回归树之外，CART算法同样可以用来构建分类树，只不过它使用的节点划分指标从信息增益率变为了计算更简单的基尼不纯度（Gini impurity）。设$p(k)$是有$K$种取值的离散随机变量$X$的概率分布，$p(k)$表示 $X=k$ 的概率，那么$p$的基尼不纯度定义为$$\text{Gini}(p)=\sum _{k=1}^{K}p(k)(1-p(k))=1-\sum _{k=1}^{K}p(k{)}^2$$

  上式是关于$X$的各个不同取值概率的二次函数，当所有概率的值相等时该函数取得最大值 $1-\frac{1}{K}$，当$X$的值完全确定，即取某个值的概率为1时，该函数取得最小值0。因此，分布$p$越随机，基尼不纯度越大；$p$越确定，基尼不纯度越小，这一性质和$p$的熵非常相似，因此在这里也可以用来当作划分节点的依据。

  在实际应用时，我们假设数据是对同一随机变量做多次观测得到的，从而可以用数据集对该变量的概率分布进行估计。设分类问题共有$K$个类别，集合$\mathcal{D}$中样本总数是$|\mathcal{D}|$，属于类别$k$的样本总数是$|{\mathcal{D}}^k|$，我们可以用不同类别的样本占总数的比例当作概率，得到集合$\mathcal{D}$的基尼不纯度为$$\text{Gini}(\mathcal{D})=1-\sum _{k=1}^K{\left(\frac{|{\mathcal{D}}^k|}{|\mathcal{D}|}\right)}^2$$

  与回归树类似，假设我们选择的特征$j$和阈值$s$把当前叶节点上的样本集合$\mathcal{D}$划分成两个子集：$${\mathcal{D}}_1(j,s)=\{(\mathbf{x},y)|x_j\le s\},{\mathcal{D}}_2(j,s)=\{(\mathbf{x},y)|x_j>s\}$$ 上式是对于连续特征而言的。在实际问题中，常常还有离散有限取值的特征，例如图3所示。这时，设选择的取值为$s$，我们以该特征等于$s$和不等于$s$划分出两个子集：$${\mathcal{D}}_1(j,s)=\{(\mathbf{x},y)|x_j=s\},{\mathcal{D}}_2(j,s)\{(\mathbf{x},y)|x_j\ne s\}$$

  最后，我们把两个子集的基尼不纯度按子集大小为比例相加，作为以特征$j$和阈值或取值$s$划分的总基尼不纯度：$$\text{Gini}(\mathcal{D},j,s)=\frac{|{\mathcal{D}}_1(j,s)|}{|\mathcal{D}|}\text{Gini}({\mathcal{D}}_1(j,s))+\frac{|{\mathcal{D}}_2(j,s)|}{|\mathcal{D}|}\text{Gini}({\mathcal{D}}_2(j,s))$$

  在每次划分时，我们选择使基尼不纯度最小的$j$和$s$，这使得划分出的两个集合内的样本类别尽可能统一，以达到最佳划分效果。

四、动手实现C4.5算法的决策树

  本节我们来动手实现ID3算法的改进版本C4.5算法的决策树。虽然C4.5算法只能解决离散的分类问题，但是在实践中，我们仍然可能在分类问题中遇到连续取值的特征。在下面的数据处理过程中，我们会介绍一种在决策树中常用的把连续特征离散化的方法，该方法在C4.5和CART算法的决策树中都有使用。由于CART算法的分类树与C4.5的整体结构没有太大差别，只是划分标准不同，我们在这里只实现C4.5算法的决策树。

（一）数据集处理

  这里用到的数据集是泰坦尼克号的生存预测数据集，它包含了许多泰坦尼克号上的乘客的特征信息，以及该乘客最后是否生还。表2按顺序列出了每一行包含的信息及其格式。

表2 泰坦尼克生存数据集中的样本特征

列编号	特征名称	含义	取值
0	PassengerId	编号，从1开始	整数
1	Survived	是否生还，1代表生还，0代表遇难	0、1
2	Pclass	舱位等级	0、1、2
3	Name	姓名	字符串
4	Sex	性别	‘male’、‘female’
5	Age	年龄	浮点数
6	SibSp	登船的兄弟姐妹数量	整数
7	Parch	登船的父母和子女数量	整数
8	Ticket	船票编号	字符串
9	Fare	船票价格	浮点数
10	Cabin	所在船舱编号	字符串
11	Embarked	登船港口，C代表瑟堡，S代表南安普敦，Q代表昆斯敦	‘C’、‘S’、‘Q’

其中，部分乘客的信息中部分字段有可能缺失。对这些特征进行一些初步的分析可以发现，乘客的编号、姓名、船票编号都是唯一的，船舱编号也较为零散，对建立模型帮助较小。因此，我们在预处理时直接将这3个字段删去。原始的数据集中包含训练集和测试集，但测试集中不包含乘客是否生还的标签，我们无法验证决策树的分类精度。所以本节中将原本的训练集按8:2的比例划分为训练集和测试集，以此来代替原本的测试集。

  由于数据集的不同字段类型不同，直接用NumPy读取和处理不太方便，我们采用另一个专门为数据分析和处理而设计的工具库Pandas来完成数据预处理工作，它可以自动识别字段的数据类型，并将不同字段用不同的数据类型存储。由Pandas读入的数据存储在pandas.DataFrame实例中，我们可以将其看作是扩展的numpy.ndarray，其许多操作都和ndarray相同。

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd# 读取数据
data = pd.read_csv('titanic/train.csv')
# 查看数据集信息和前5行具体内容，其中NaN代表数据缺失
print(data.info())
print(data[:5])# 删去编号、姓名、船票编号3列
data.drop(columns=['PassengerId', 'Name', 'Ticket'], inplace=True)

  在上面的算法介绍中，我们只考虑了特征取离散值的情况。在实践中，还有许多特征的取值是连续的，例如本数据集中的年龄和船票价格两项。对于这样的特征，我们可以根据数据的范围划出几个分类点，按照取值与分类点的大小关系进行分类。假设有$K$个分类点 $x_1,\cdots ,x_K$，我们可以用这些分类点，将数据分成 $(-\infty ,x_1],(x_1,x_2],\cdots ,(x_K,+\infty )$ 共 $K+1$ 类。这样，我们就把连续的数据转化成了离散的取值。

feat_ranges = {}
cont_feat = ['Age', 'Fare'] # 连续特征
bins = 10 # 分类点数for feat in cont_feat:# 数据集中存在缺省值nan，需要用np.nanmin和np.nanmaxmin_val = np.nanmin(data[feat]) max_val = np.nanmax(data[feat])feat_ranges[feat] = np.linspace(min_val, max_val, bins).tolist()print(feat, '：') # 查看分类点for spt in feat_ranges[feat]:print(f'{spt:.4f}')

  对于只有有限个取值的离散特征，我们将其转化为整数。

# 只有有限取值的离散特征
cat_feat = ['Sex', 'Pclass', 'SibSp', 'Parch', 'Cabin', 'Embarked'] 
for feat in cat_feat:data[feat] = data[feat].astype('category') # 数据格式转为分类格式print(f'{feat}：{data[feat].cat.categories}') # 查看类别data[feat] = data[feat].cat.codes.tolist() # 将类别按顺序转换为整数ranges = list(set(data[feat]))ranges.sort()feat_ranges[feat] = ranges

  由于数据中存在缺省值，我们将所有缺省值填充为-1，并为所有特征的分类点添加最小值-1。这一做法是处理缺省值的最简单的方式。如果要更合理地填充缺省值，我们可以通过数据集中其他相似的样本对缺省值进行推断，感兴趣的可以自行查阅相关资料。此外，我们再统计标签的可能取值，在计算熵时使用。

# 将所有缺省值替换为-1
data.fillna(-1, inplace=True)
for feat in feat_ranges.keys():feat_ranges[feat] = [-1] + feat_ranges[feat]

  最后，我们按8:2的比例划分训练集与测试集，并将数据从pandas.DataFrame转换为更通用的numpy.ndarray，完成整个数据处理过程。

# 划分训练集与测试集
np.random.seed(0)
feat_names = data.columns[1:]
label_name = data.columns[0]
# 重排下标之后，按新的下标索引数据
data = data.reindex(np.random.permutation(data.index))
ratio = 0.8
split = int(ratio * len(data))
train_x = data[:split].drop(columns=['Survived']).to_numpy()
train_y = data['Survived'][:split].to_numpy()
test_x = data[split:].drop(columns=['Survived']).to_numpy()
test_y = data['Survived'][split:].to_numpy()
print('训练集大小：', len(train_x))
print('测试集大小：', len(test_x))
print('特征数：', train_x.shape[1])

（二）C4.5算法的实现

  下面我们实现C4.5算法的主体部分。在上面的算法介绍中，我们在按特征划分节点时，为特征的每种可能取值都分裂出一个新节点。然而在实践中，为了控制算法的复杂度，提升最后的准确率，我们通常采用二分类法。与CART算法类似，对于数据的某个特征$X_F$，我们枚举其所有可能的取值或分类点 $x_1,\cdots ,x_{K_F}$，选择使信息增益率最大的分类点$x_b$，将数据按 $X_F\le x_b$ 和 $X_F>x_b$ 分为两类。这种做法相比于多分类要更加精细，也更方便我们用正则化控制决策树的复杂度。

  对于决策树模型来说，最基础的单元就是树的节点，所以我们先来定义节点类。节点中存储分类特征、分类点的值和子节点列表。

class Node:def __init__(self):# 内部结点的feat表示用来分类的特征编号，其数字与数据中的顺序对应# 叶结点的feat表示该结点对应的分类结果self.feat = None# 分类值列表，表示按照其中的值向子结点分类self.split = None# 子结点列表，叶结点的child为空self.child = []

  考虑到代码整体的结构和可读性，我们将决策树也定义成类，将具体的实现细节以注释的形式标注在类中。对照我们前面的讲解，该类应当能计算熵、信息增益、信息增益率等值，可以从根节点开始用C4.5算法生成决策树，还可以用建立好的决策树预测新样本的分类。下面，我们就按照这一思路，依次实现决策树的各个部分。

class DecisionTree:def __init__(self, X, Y, feat_ranges, lbd):self.root = Node()self.X = Xself.Y = Yself.feat_ranges = feat_ranges # 特征取值范围self.lbd = lbd # 正则化系数self.eps = 1e-8 # 防止数学错误log(0)和除以0self.T = 0 # 记录叶结点个数self.ID3(self.root, self.X, self.Y)# 工具函数，计算 a * log adef aloga(self, a):return a * np.log2(a + self.eps)# 计算某个子数据集的熵def entropy(self, Y):cnt = np.unique(Y, return_counts=True)[1] # 统计每个类别出现的次数N = len(Y)ent = -np.sum([self.aloga(Ni / N) for Ni in cnt])return ent# 计算用feat <= val划分数据集的信息增益def info_gain(self, X, Y, feat, val):# 划分前的熵N = len(Y)if N == 0:return 0HX = self.entropy(Y)HXY = 0 # H(X|Y)# 分别计算H(X|X_F<=val)和H(X|X_F>val)Y_l = Y[X[:, feat] <= val]HXY += len(Y_l) / len(Y) * self.entropy(Y_l)Y_r = Y[X[:, feat] > val]HXY += len(Y_r) / len(Y) * self.entropy(Y_r)return HX - HXY# 计算特征feat <= val本身的复杂度H_Y(X)def entropy_YX(self, X, Y, feat, val):HYX = 0N = len(Y)if N == 0:return 0Y_l = Y[X[:, feat] <= val]HYX += -self.aloga(len(Y_l) / N)Y_r = Y[X[:, feat] > val]HYX += -self.aloga(len(Y_r) / N)return HYX# 计算用feat <= val划分数据集的信息增益率def info_gain_ratio(self, X, Y, feat, val):IG = self.info_gain(X, Y, feat, val)HYX = self.entropy_YX(X, Y, feat, val)return IG / HYX# 用ID3算法递归分裂结点，构造决策树def ID3(self, node, X, Y):# 判断是否已经分类完成if len(np.unique(Y)) == 1:node.feat = Y[0]self.T += 1return# 寻找最优分类特征和分类点best_IGR = 0best_feat = Nonebest_val = Nonefor feat in range(len(feat_names)):for val in self.feat_ranges[feat_names[feat]]:IGR = self.info_gain_ratio(X, Y, feat, val)if IGR > best_IGR:best_IGR = IGRbest_feat = featbest_val = val# 计算用best_feat <= best_val分类带来的代价函数变化# 由于分裂叶结点只涉及该局部，我们只需要计算分裂前后该结点的代价函数# 当前代价cur_cost = len(Y) * self.entropy(Y) + self.lbd# 分裂后的代价，按best_feat的取值分类统计# 如果best_feat为None，说明最优的信息增益率为0，# 再分类也无法增加信息了，因此将new_cost设置为无穷大if best_feat is None:new_cost = np.infelse:new_cost = 0X_feat = X[:, best_feat]# 获取划分后的两部分，计算新的熵new_Y_l = Y[X_feat <= best_val]new_cost += len(new_Y_l) * self.entropy(new_Y_l)new_Y_r = Y[X_feat > best_val]new_cost += len(new_Y_r) * self.entropy(new_Y_r)# 分裂后会有两个叶结点new_cost += 2 * self.lbdif new_cost <= cur_cost:# 如果分裂后代价更小，那么执行分裂node.feat = best_featnode.split = best_vall_child = Node()l_X = X[X_feat <= best_val]l_Y = Y[X_feat <= best_val]self.ID3(l_child, l_X, l_Y)r_child = Node()r_X = X[X_feat > best_val]r_Y = Y[X_feat > best_val]self.ID3(r_child, r_X, r_Y)node.child = [l_child, r_child]else:# 否则将当前结点上最多的类别作为该结点的类别vals, cnt = np.unique(Y, return_counts=True)node.feat = vals[np.argmax(cnt)]self.T += 1# 预测新样本的分类def predict(self, x):node = self.root# 从根结点开始向下寻找，到叶结点结束while node.split is not None:# 判断x应该处于哪个子结点if x[node.feat] <= node.split:node = node.child[0]else:node = node.child[1]# 到达叶结点，返回类别return node.feat# 计算在样本X，标签Y上的准确率def accuracy(self, X, Y):correct = 0for x, y in zip(X, Y):pred = self.predict(x)if pred == y:correct += 1return correct / len(Y)

  最后，我们用训练集构造决策树，并在测试集上检测决策树的分类效果。可以通过调节正则化强度系数$\lambda$的值来观察叶节点数量和分类准确率的变化。

DT = DecisionTree(train_x, train_y, feat_ranges, lbd=1.0)
print('叶结点数量：', DT.T)# 计算在训练集和测试集上的准确率
print('训练集准确率：', DT.accuracy(train_x, train_y))
print('测试集准确率：', DT.accuracy(test_x, test_y))

五、Sklearn中的决策树

  Sklearn中也提供了决策树工具，包括分类型决策树DecisionTreeClassifier和回归型决策树DecisionTreeRegressor，这两种决策树都内置了不同的节点划分标准，可以通过参数来调整。下面，我们直接使用分类型决策树在我们处理好的数据集上进行训练。

DecisionTreeClassifier类的基本语法格式和参数说明如下。

class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

参数名称	说明
criterion	接收str。表示节点（特征）选择的准则，使用信息增益“entropy”的是C4.5算法；使用基尼系数“gini”的CART算法。默认为“gini”。
splitter	接收str，可选参数为“best”或“random”。表示特征划分点选择标准，“best”在特征的所有划分点中找出最优的划分点；“random”在随机的部分划分点中找出局部最优划分点。默认为“best”。
max_depth	接收int。表示决策树的最大深度。默认为None。
min_samples_split	接收int或float。表示子数据集再切分需要的最小样本量。默认为2。
min_samples_leaf	接收int或float。表示叶节点所需的最小样本数，若低于设定值，则该叶节点和其兄弟节点都会被剪枝。默认为1。
min_weight_fraction_leaf	接收int、float、str或None。表示在叶节点处的所有输入样本权重总和的最小加权分数。默认为None。
max_features	接收float。表示特征切分时考虑的最大特征数量，默认是对所有特征进行切分。传入int类型的值，表示具体的特征个数；浮点数表示特征个数的百分比；sqrt表示总特征数的平方根；log2表示总特征数求log2后的个数的特征。默认为None。
random_state	接收int、RandomState实例或None。表示随机种子的数量，若设置了随机种子，则最后的准确率都是一样的；若接收int，则指定随机数生成器的种子；若接收RandomState，则指定随机数生成器；若为None，则指定使用默认的随机数生成器。默认为None。
max_leaf_nodes	接收int或None。表示最大叶节点数。默认为None，即无限制。
min_impurity_decrease	接收float。表示切分点不纯度最小减少的程度，若某节点的不纯度减少小于或等于这个值，则切分点就会被移除。默认为0.0。
min_impurity_split	接收float。表示切分点最小不纯度，它用来限制数据集的继续切分（决策树的生成）。若某个节点的不纯度（分类错误率）小于这个阈值，则该点的数据将不再进行切分。无默认，但该参数将被移除，可使用min_impurity_decrease参数代替。
class_weight	接收dict、dict列表、balanced或None。表示分类模型中各种类别的权重，在出现样本不平衡时，可以考虑调整class_weight系数去调整，防止算法对训练样本多的类别偏倚。默认为None。
presort	接收bool。表示是否提前对特征进行排序。默认为False。

  由于sklearn中进行了大量优化，其最终的预测精度要比本文手动实现的高一些。但是，sklearn的决策树也含有大量的超参数，想要达到最优的结果往往需要复杂的调参过程。下面我们只展示了max_depth一个超参数，它表示决策树的最大深度，即从根到任意一个叶节点的最长路径的长度。该参数与我们的正则化类似，也能起到控制决策树复杂度的效果。

from sklearn import tree# criterion表示分类依据，max_depth表示树的最大深度
# entropy生成的是C4.5分类树
c45 = tree.DecisionTreeClassifier(criterion='entropy', max_depth=6)
c45.fit(train_x, train_y)
# gini生成的是CART分类树
cart = tree.DecisionTreeClassifier(criterion='gini', max_depth=6)
cart.fit(train_x, train_y)c45_train_pred = c45.predict(train_x)
c45_test_pred = c45.predict(test_x)
cart_train_pred = cart.predict(train_x)
cart_test_pred = cart.predict(test_x)
print(f'训练集准确率：C4.5：{np.mean(c45_train_pred == train_y)}，' \f'CART：{np.mean(cart_train_pred == train_y)}')
print(f'测试集准确率：C4.5：{np.mean(c45_test_pred == test_y)}，' \f'CART：{np.mean(cart_test_pred == test_y)}')

  PyDotPlus库提供了将sklearn生成的决策树可视化的工具。我们可以将训练得到的决策树做可视化，观察在每个节点上决策树选择了哪个特征进行分类。由于生成的图像较宽，无法完全清晰展示，我们将决策树的左右子树分开放在图5中。大家可以自行运行代码，查看完整的生成图像。

!pip install pydotplusfrom six import StringIO
import pydotplusdot_data = StringIO()
tree.export_graphviz( # 导出sklearn的决策树的可视化数据c45,out_file=dot_data,feature_names=feat_names,class_names=['non-survival', 'survival'],filled=True, rounded=True,impurity=False
)
# 用pydotplus生成图像
graph = pydotplus.graph_from_dot_data(dot_data.getvalue().replace('\n', '')) 
graph.write_png('tree.png')

(a)左子树

(b)右子树

图5 算法最终生成的决策树示意图  

附：以上文中的数据集及相关资源下载地址：
链接：https://pan.quark.cn/s/c579f6644a8b
提取码：RgxC

这篇关于【机器学习-监督学习】决策树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---