关于决策树，你一定要知道的知识点！-技术圈

👆关注“博文视点Broadview”，获取更多书讯

在现实生活中，我们每天都会面对各种抉择，例如根据商品的特征和价格决定是否购买。

不同于逻辑回归把所有因素加权求和然后通过Sigmoid函数转换成概率进行决策，我们会依次判断各个特征是否满足预设条件，得到最终的决策结果。例如，在购物时，我们会依次判断价格、品牌、口碑等是否满足要求，从而决定是否购买。

决策的流程，如图1所示。

图1

可以看到，决策过程组成了一棵树，这棵树就称为决策树。

在决策树中，非叶子节点选择一个特征进行决策，这个特征称为决策点，叶子节点则表示最终的决策结果。

在上例中，我们只是根据经验主观建立了一棵决策树，这棵决策树在数据量和特征维度较小且逻辑简单时是可以使用的。

然而，在数据量和特征维度较大时，仅凭主观观察建立决策树显然是不可行的。在实际应用中，训练集中的样本往往有上万个，样本的特征通常有上百维，该怎么处理呢？

在实际建立决策树的过程中，每次选择特征都有一套科学的方法。下面就详细讲解如何科学地建立决策树。

不难发现，建立决策树的关键在于选取决策点时使用的判断条件是否合理。每个决策点都要有区分类别的能力。例如，在电商场景中，将发货的快递公司作为决策点的选取条件就是一个很差的选择，其原因在于快递公司和购买行为没有必然联系，而将商品价格作为决策点的选取条件就是合理的，毕竟大部分消费者对商品价格比较敏感。

一个好的决策点可以把所有数据（例如商品）分为两部分（左子树和右子树），各部分数据所对应的类别应尽可能相同（例如购买或不购买），即两棵子树中的数据类别应尽可能“纯”（这种决策点有较高的区分度）。

和逻辑回归类似，用已知数据（例如用户的购买记录、商品信息）求解决策树的形状和每个决策点使用的划分条件，就是决策树的训练过程。

首先看一下如何量化数据的纯度。假设在一组数据中有P和N两类样本，它们的数量分别为 $n_{1}$ 个和 $n_{2}$ 个。P类样本出现的概率为

$P(y=\mathrm{P} \text { 类 })=\frac{n_{1}}{n_{1}+n_{2}}$

N类样本出现的概率为

$P(y=\mathrm{N} \text { 类 })=\frac{n_{1}}{n_{1}+n_{2}}$

我们可以直观地发现：当数据只有一个类别（ $P(y=\mathrm{P} \text { 类 })= 1$ 或 $P(y=\mathrm{N} \text { 类 })= 1$ ）时，数据最纯；当两类数据“平分秋色”（ $P(y=\mathrm{N} \text { 类 })= P(y=\mathrm{P} \text { 类 })= 0.5$ ）时，数据最混乱。

可以使用基尼（Gini）系数来量化数据的混乱程度。基尼系数的计算公式如下。

$\text { Gini }=1-P(y=\mathrm{N} \text { 类 })^{2}-P(y=\mathrm{P} \text { 类 })^{2}$

可见，基尼系数越小，数据就越纯（ $P(y=\mathrm{N} \text { 类 })= 1$ ， $\text { Gini }=1$ ）。当数据最混乱时， $P(y=\mathrm{N} \text { 类 })= P(y=\mathrm{P} \text { 类 })= 0.5$ ，也就是说，基尼系数的最大值为0.5。

基尼系数和概率 $P(y=\mathrm{N} \text { 类 })$ 的关系，如图2所示。

图2

决策树有一些常用的构建方法，在这里我们详细讲解一下最为流行的CART树。

CART树是一棵二叉树，它不仅能完成分类任务，还能完成数值预测类的回归任务。

下面先介绍分类树，再介绍回归树。在构建CART树时，可以使用基尼系数来度量决策条件的合理性。

假设有 $N$ 个训练样本，特征一共有 $m$ 维，即 $\boldsymbol{x}=\left[\begin{array}{c} x_{1} \\ \vdots \\ x_{m} \end{array}\right]$ 。和逻辑回归中特征 $x_{i}$ 是连续值不同，在这里， $x_{i}$ 既可以是连续值（例如价格、好评数、销量等， $x_{i} \in(-\infty,+\infty)$ ），也可以从集合中“多选一”（例如学历， $x_{i} \in\{\text { 专科, 本科, 硕士, 博士, 其他 }\}$ ）。

决策树的构建（训练）过程是一个不断生成决策点的过程，每次生成的决策点都要尽可能把训练样本中的两类数据分开。

例如， $x_{1}$ 为价格，划分条件为 $x_{i}>500$ ，将训练数据分成两类（如果某个样本在划分条件上有特征缺失，就随机分配该样本），如图3所示。

图3

$\operatorname{Data} 1$ 中有 $M_{1}$ 个样本，它们对应于不同的类别，基尼系数为 $\operatorname{Gini} 1$ 。Data1中的数据越纯（类别越单一），Gini1就越小。同理， $\operatorname{Data} 1$ 中有 $M_{2}$ 个样本，基尼系数为 $\operatorname{Gini} 2$ 。

此次划分的基尼系数为

$\operatorname{Gini}\left(x_{1}>500\right)=\frac{M_{1}}{M_{1}+M_{2}} \operatorname{Gini} 1+\frac{M_{2}}{M_{1}+M_{2}} \text { Gini2 }$

$\operatorname{Gini}\left(x_{1}>500\right)$ 为 $\operatorname{Gini} 1$ 和 $\operatorname{Gini} 2$ 加权求和（权重为两堆数据的数量占比）的结果，用于度量划分条件 $x_{1}>500$ 的合理性。 $\operatorname{Gini}\left(x_{1}>500\right)$ 越小，说明度量划分越合理。

若 $x_{2} \in\{\text { 专科, 本科, 硕士, 博士, 其他 }\}$ ，则可将“ $x_{2} = \text{本科}$ ”作为划分条件，将数据划分为“ $x_{2} = \text{本科}$ ”“ $x_{2} \not= \text{本科}$ ”两部分，并计算基尼系数 $\operatorname{Gini}\left(x_{2} = \text{本科}\right)$ 。

遍历所有维度（ $i=1,2,3, \cdots, m$ ）中可能的划分条件，对每种划分方法均可计算相应的基尼系数，例如 $\operatorname{Gini}\left(x_{1}>500\right)$ 、 $\operatorname{Gini}\left(x_{1}>600\right)$ 、 $\operatorname{Gini}\left(x_{1}>400\right)$ 、 $\operatorname{Gini}\left(x_{2} = \text{本科}\right)$ 、 $\operatorname{Gini}\left(x_{2} = \text{博士}\right)$ 、 $\operatorname{Gini}\left(x_{3}>5\right)$ 。以最小基尼系数所对应的特征和划分条件为决策点，数据将被划分为两堆。

但是，决策树是不停生长的，仅划分一次是不够的，需要再使用同样的方法对每个子堆（Data 1、Data 2）进行划分，最终生成CART树，步骤如下。

算法的输入为训练集 $D$ 、基尼系数的阈值、样本数量的阈值，输出为决策树 $T$ 。算法从根节点开始，用训练集递归建立CART树。

1. 当前节点的数据集为 $D$ 。如果样本数量小于阈值、基尼系数小于阈值或没有特征，则返回决策子树，当前节点停止递归。
2. 在当前节点的数据上计算各个特征的各个划分条件对划分后的数据的基尼系数。当维度过高且每维所对应的可取值比较多时（例如，价格的值为 1~10000的整数，将有10000种划分方式；如果为浮点数，划分方式更多），可以随机选取一些特征和划分条件，不再强制要求全部遍历。
3. 在计算出来的各个特征的各个特征值对数据集 $D$ 的基尼系数中，选择基尼系数最小的特征 $x_{i}$ 和对应的划分条件，例如“ $x_{i}>10$ ”或“ $x_{i}=\text{本科}$ ”。通过划分条件把数据集划分成 $\operatorname{Data} 1$ 和 $\operatorname{Data} 2$ 两部分，同时分别建立当前节点的左节点和右节点，左节点的数据集为 $\operatorname{Data} 1$ ，右节点的数据集为 $\operatorname{Data} 2$ 。
4. 对 $\operatorname{Data} 1$ 和 $\operatorname{Data} 2$ 递归调用以上步骤，生成决策树。

这就是决策树的训练过程。

在第1步中，判断样本数量和基尼系数是为了控制生成的决策树的深度，避免不停地递归。不停地递归会导致划分条件过细，从而造成过拟合。

决策树建立后，每个叶子节点里都有一堆数据。可以将这堆数据的类别比例作为叶子节点的输出。

决策树在复杂度上和其他模型有所不同。例如，在逻辑回归中，当特征维度不变时，模型的复杂度就确定了。但是，在决策树中，模型会根据训练数据不断分裂，决策树越深，模型就越复杂。

可以看出，数据决定了决策树的复杂度，且当数据本身线性不可分时，决策树会非常深，模型会非常复杂。

所以，在决策树中，需要设置终止条件，以防模型被数据带到极端复杂的情况中。在决策树中，终止条件的严格程度相当于逻辑回归中正则项的强度。

训练完成后，我们可以得到一棵决策树，如图4所示。

图4

在使用决策树时，用数据 $\boldsymbol{x}$ 在决策树上找到对应的叶子节点作为分类结果。例如，当 $\boldsymbol{x}=\left[\begin{array}{c} 35\\ 1\\ 2\\ \end{array}\right]$ 时，对应的分类结果为 $P(\mathrm{P} \text { 类 })= 0.9，P(\mathrm{N} \text { 类 })=0.1$ 。决策树对输入 $\boldsymbol{x}$ 的预测结果常写为 $h(\boldsymbol{x})$ ， $h$ 表示决策树的决策过程。

决策树理解起来比较简单，其本质就是以基尼系数来量化划分条件的分类效果，自动探寻最佳划分条件。

下面我们把决策树和逻辑回归进行对比。为了方便对比，假设决策树的特征为2维且均为连续特征。决策树的分类效果图可以理解为如图5所示的形式。

图5

可见，决策树分类的几何意义和逻辑回归一样，都是在平面上画直线。相比逻辑回归的分类线是一条直线，决策树的分类线是平面上与坐标轴平行的多条直线（一个判断条件对应于一条直线，这些直线共同组成了分类线）。多条直线可以组合成非线性的形式，以处理线性不可分的情况，如图6所示。

图6

虽然决策树在训练时需要遍历所有可能的类别划分方法，速度比较慢，但是在预测阶段，决策树只需进行一些逻辑判断和比较，速度非常快，故适合在对时间要求较高的场景中使用。

决策树不仅可以用在分类中，还可以用在回归中（预测连续的值而非类别概率）。用在分类中的决策树称为分类树，用在回归的中决策树称为回归树。在回归任务中，学习目标不再是分类，而是一个连续值 $y_{i} \in(-\infty,+\infty)$ 。此时，基尼系数不再适用于衡量数据的混乱程度，一般使用方差来衡量数据的混乱程度。

例如，当 $x_{1}>20$ 时，将它作为划分条件，把数据划分为 $\operatorname{Data} 1$ 和 $\operatorname{Data} 2$ 两部分， $\operatorname{Data} 1$ 中有 $M_{1}$ 个样本， $\operatorname{Data} 2$ 中有 $M_{2}$ 个样本。