NO.42.tip： 经典决策树算法

背景

决策树是一种流行而强大的机器学习算法。它是一种非参数化的有监督学习方法，可用于分类和回归任务。它通过学习样本数据集创建一个模型，获得一些决策规则来预测目标变量的值。对于分类模型来说，目标值在本质上是离散的；而对于回归模型来说，目标值由连续值表示。与人工神经网络等算法不同，决策树相对来说更容易理解和解释，因为它共享内部决策逻辑。尽管许多数据科学家认为这是一个老方法，而且由于过拟合问题，他们可能对其准确性有一些怀疑，但最近的基于树的模型，特别是随机森林、梯度提升和 XGBoost 等建立在决策树算法之上的机器学习模型获得了巨大的成功，使古老的决策树模型焕发新春！因此，决策树背后的概念和算法是非常值得了解的。本章首先介绍一些经典的决策树算法，包括 CART、ID3 和 C4.5 算法。

经典决策树应用的一般流程

经典决策树算法诞生在 20 世纪 90 年代之前，那时网络环境还不发达，所处理的样本数据集主要是小规模数据，特征数并不多，因此数据的特征工程并不必要。当时的主要任务是处理一些特征数据的缺失，针对分类数据和连续数据进行区别化处理以及相互转换，包括连续数据的离散化等。

获得规整的样本数据集之后，就需要利用各类决策树算法进行决策树模型的构建。决策树算法的差异主要体现在：

1. 选择特征属性的策略；
2. 选择属性分割点策略；
3. 不同类型特征属性的处理方法；
4. 如何终止决策树的构建过程；
5. 如何优化模型以避免过拟合；
6. 如何降低决策树模型的复杂度等方面。

获得决策树模型之后，接下来要利用这些模型对未知样本数据进行推理和预测。在这个过程中，为降低模型复杂度或提高模型泛化能力，需要进行剪枝优化等处理。

源与流

CART算法

CART（Classification And Regression Trees）即分类和回归树，是第一种比较经典的决策树算法，由 Leo Breiman、Jerome Friedman、Richard Olshen 和 Charles Stone 于 1984 年正式提出，可用于分类或回归预测建模问题。

CART 算法总是创建一棵二元树（二叉树），这意味着每个非终端节点有两个子节点。CART 的构建过程与人类的决策方式非常相似，因此，人们很容易理解和接受 CART 决策过程得出的结果。这种直观的可解释能力是 CART 以及决策树方法非常重要的一个原因。CART 另一个非常吸引人的地方是，它允许多样化的输入数据类型，这与许多线性组合方法（如逻辑回归或支持向量机）不同。可以混合连续数值变量，如价格或面积，也可以混合标称分类或枚举变量，如房屋类型或位置。这种灵活性使得 CART 成为各种应用中的首选工具。CART 使用代价复杂度剪枝（Cost Complexness Pruning，CCP）方法，将不可靠的分支从决策树移除，以提高准确率。

从 CART 算法的名字中可以看出，它支持构建分类（决策）树和回归（决策）树。所谓分类树，是指目标变量是标称分类或枚举值数据类型，用于确定目标变量可能属于的“类别”。所谓回归树，是指目标变量是连续的数值数据类型，用来预测目标变量的值。

基尼不纯度、基尼增益与基尼指数

训练决策树模型包括迭代地将当前数据分成两个分支。如何分割以及如何定量评估分割的优劣是待解决的核心问题。

因此，更高的基尼增益等价于更好的分割，更低的基尼指数等价于更好的分割。例如，很容易验证，在上述数据集中：

$$G(A=a_i)=\frac{|D_1|}{|D|}G(D_1)+\frac{|D_2|}{|D|}G(D_2)\text{\hspace{1em}(1)}$$

这就是 CART 决策树中用来挑选最佳分割的度量。例如，很低的数据集。完美分割的基尼增益为 0.5 而基尼指数为 0.333 而基尼指数选取最佳分割。

CART 分类决策树的原理

CART 分类决策树的算法流程

1. 输入
   输入为训练数据集 $D$ 和停止计算的条件。其中，训练数据集 $D$ 包含多条记录，每个记录由多个属性构成。每个属性的数据类型均为离散的，例如二值类型、标称值或枚举值类型等。停止计算的条件可以是节点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或没有更多特征属性等。

2. 输出
   输出为 CART 分类树。

3. CART 分类决策树的生成流程
   CART 算法从根节点开始，用训练集递归地建立 CART 分类决策树。

   1. 设训练数据集为 $D$，计算数据集现有的所有属性特征对该训练集的基尼增益。对每一个属性特征 $F$，对其所有可能取值的每个值 $f$，根据 $D$ 中的样本实例对 $F=f$ 的测试为“是”或“否”，将数据集 $D$ 分割成 $D_1$ 和 $D_2$ 两个子集。利用基尼增益公式计算 $F=f$ 时的基尼增益。
   2. 假设有 $N_F$ 个属性特征，对于每一个属性特征 $i$，可能取值数量为 $N_i$，则总共需要计算的基尼指数次数为

   $$\sum _{i=1}^{N_F}{N}_i+1$$

   2. 在所有可能的属性特征 $F$ 以及它们所有可能的切分点 $f_i$ 中，选择基尼增益最大的特征 $D$ 及其对应的切分点作为最优切分点，依据该最优切分点切割，生成两个子节点，左子节点为 $D_1$，右子节点为 $D_2$。
   3. 对两个子节点递归调用步骤 1～2，直至满足停止条件。
   4. 生成一棵完整的二叉 CART 分类决策树。

4. CART 分类决策树的优化
   使用决策树模型拟合数据时容易产生过拟合，解决办法是对决策树进行剪枝处理。剪枝有两种思路：预剪枝（pre-pruning）和后剪枝（post-pruning）。

5. CART 分类决策树模型的使用 决策树算法是一种通过对历史样本数据进行测算实现对新数据的分类和预测的算法。整个决策过程从根节点开始，从上到下进行，根据数据的分类在每个决策节点给出不同的结果。使用决策树的过程和人眼比对的过程类似：先比对根节点，根据比对结果走向决策树的不同子节点；再再子节点处进行比对，直到比对到叶子节点，即得到结果。对生成的CART分类决策树做预测的时候，如果测试集里的某个样本A落到了某个叶子节点，且该叶子节点里存在多个类别的训练样本，则概率最大的训练样本是样本A的类别。

决策树回归

决策树回归（regression tree），顾名思义，就是用树模型做回归问题，每一个叶子节点都输出一个预测值。预测值一般是该叶子节点所含训练集样本的输出的均值。决策树也可以应用于回归。

回归树中，CART 使用均方误差或者平均绝对误差作为选择特征及其分割点的依据。在回归问题中，CART 使用均方误差或者平均绝对误差作为选择特征及其分割点的依据；在回归问题中，CART 使用均方误差或者平均绝对误差作为选择特征及其分割点的依据；CART 算法是第一个同时支持分类和回归的决策树算法。在分类问题中，CART 使用基尼指数或基尼增益作为选择特征及其分割点的依据；在回归问题中，CART 使用均方误差或者平均绝对误差作为选择特征及其分割点的依据。

除了 CART 算法外，随机森林、GBDT、XGBoost、LightGBM 等都支持对回归问题的处理。与构建决策树类似，构建回归树时需要考虑的问题是，选择哪一个属性对当前的数据集进行划分。与分类决策树不一样的地方在于，需要预测的属性是连续的，因而在叶子节点选择什么样的预测模型也很关键。

CART 回归决策树的特征和分割点选择准则

CART 分类树采用基尼指数最小化准则或基尼增益最大化原则，而 CART 回归树采用均方误差（Mean Squared Error，MSE 或 L2）最小化准则作为特征和分割点的选择方法。

事实上，对于回归树来说，常见的三种不纯度测量方法是：最小二乘法、中位数为 median（$y_m$）〕。

• 均方误差最小化方法，即最小二乘法。这种方法类似于线性模型中的最小二乘法。分割的选择是为了最小化每个节点中观测值和平均值之间的误差平方和。该方法将节点的预测值设置为 ${\bar{y}}_m$。

$${\bar{y}}_m=\frac{1}{N_m}\sum _{y\in Q_m}y$$

$$H(Q_m)=\frac{1}{N_m}\sum _{y_m\in Q_m}(y-{\bar{y}}_m{)}^2\text{\hspace{1em}(2)}$$

• 最小平均绝对误差（Mean Absolute Error，MAE 或 L1）。这种方法最小化一个节点内平均数与中位数的绝对偏差。与最小二乘法相比，它的优点是对离群值不那么敏感，并提供一个更稳健的模型。缺点是在处理包含大量零值的数据集时不敏感。该方法将节点的预测值设置为 median（$y_m$）。

$$H(Q_m)=\frac{1}{N_m}\sum _{y_m\in Q_m}|y-\text{median}(y_m)|\text{\hspace{1em}(3)}$$

• 最小半泊松偏差（half Poisson deviance）。该方法将节点的预测值设置为 ${\bar{y}}_m$。

$$H(Q_m)=\frac{1}{N_m}\sum _{y_m\in Q_m}\left(y\log \frac{y}{{\bar{y}}_m}-y+{\bar{y}}_m\right)\text{\hspace{1em}(4)}$$

CART 回归决策树的原理

CART 回归树和 CART 分类树最大的区别在于输出：如果输出的是离散值，则它是一棵分类树；如果输出的是连续值，则它是一棵回归树。

对于回归树，每一个节点都可以被认为是一个回归值。一个节点有回归值，也有分割选择的属性。最底层的节点回归值可能才是最理想的回归值。这样给定一组特征，就知道最终怎么去回归以及回归得到的值是多少了。

在本章中，介绍 CART 回归决策树时，使用最小二乘法。直觉上，回归树构建过程中，分割是为了最小化每个节点中样本实际观测值和平均值之间的残差平方和。

给定一个数据集 $D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_i,y_i),\dots ,(x_n,y_n)\}$，其中 $x_i$ 是一个 $m$ 维的向量，即 $x_i$ 含有 $k$ 个特征，记为变量 $X$，是自变量，每个特征记为 $x^j(j=1,2,\dots ,k)$，$y$ 是因变量。回归问题的目标就是构造一个函数 $f(X)$ 以拟合数据集 $D$ 中的样本，使得该函数的预测值与样本因变量实际值的均方误差最小，即

$$\min \frac{1}{n}\sum _{i=1}^n(f(x_i)-y_i{)}^2\text{\hspace{1em}(5)}$$

用 CART 进行回归，目标也是一样的，即最小化均方误差。假设一棵构建好的 CART 回归树有 $M$ 个叶子节点，这意味着 CART 将 $m$ 维输入空间 $X$ 划分成了 $M$ 个单元 $R_1,R_2,\dots ,R_M$，同时意味着 CART 至多会有 $M$ 个不同的预测值。CART 最小化均方误差公式如下：

$$\min \frac{1}{n}\sum _{m=1}^M\sum _{x_i\in R_m}(c_m-y_i{)}^2\text{\hspace{1em}(6)}$$

其中，$c_m$ 表示第 $m$ 个叶子节点的预测值。

想要最小化 CART 回归树总体的均方误差，只需要最小化每一个叶子节点的均方误差即可，而最小化一个叶子节点的均方误差，只需要将预测值设定为叶子中含有的训练集元素的均值，即

$$c_m=\text{ave}(y_i\mid x_i\in {\text{leaf}}_m)\text{\hspace{1em}(7)}$$

所以，在每一次分割时，需要选择分割特征变量（splitting variable）和分割点（splitting point），使得模型在训练集上的均方误差最小。

这里采用启发式的方法，遍历所有的分割特征变量和分割点，然后选出叶子节点均方误差之和最小的那种情况作为划分。选择第 $j$ 个特征变量 $x^j$ 和它的取值 $s$，作为分割变量和分割点，则分割变量和分割点将父节点的输入空间一分为二：

$$\{\begin{array}{ll}{R}_1(j,s)=\{x\mid x^{(j)}\le s\}& \\ R_2(j,s)=\{x\mid x^{(j)}& gt;s\}\end{array}$$

CART 选择分割特征变量 $x^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]\text{\hspace{1em}(8)}$$

采取遍历的方式，我们可以求出 $j$ 和 $s$。先任意选择一个特征变量 $x^j$，再选出在该特征下的最佳划分 $s$；对每一个特征变量都这样做，得到 $k$ 个特征的最佳分割点，从这 $k$ 个值中取最小值即可得到令全局最优的 $(j,s)$。上式中，第一项 ${\min }_{c_1}{\sum }_{x_i\in R_1(j,s)}(y_i-c_1{)}^2$ 得到的 $c_1$ 值就是 $\text{ave}(y_i\mid x_i\in R_1(j,s))$，同理，第二项中 $c_2=\text{ave}(y_i\mid x_i\in R_2(j,s))$。根据这个 $(j,s)$ 就可以创建一个节点，然后形成两个子区间。之后分别对这两个子区间继续上述过程，就可以继续创建回归树的节点，直到满足结束条件才停止对区间的划分。

最小二乘回归树生成算法的主要思路为在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定两个子区域上的输出值，构建二叉决策树。其输入为训练数据集 $D$，输出为回归树 $f(x)$。具体的算法流程如下：

1. 选择最优切分变量 $j$ 与切分点 $s$，求解式 (8)。遍历变量 $j$，对固定的切分变量 $j$ 扫描切分点 $s$，选择使式 (8) 达到最小值的对 $(j,s)$。
2. 用选定的对 $(j,s)$ 划分区域并决定相应的输出值。
3. 继续对两个子区域调用步骤 1 和 2 直至满足停止条件。
4. 将输入空间划分为 $M$ 个区域 $R_1,R_2,\dots ,R_M$，生成决策树：

$$f(x)=\sum _{m=1}^M{\hat{c}}_{m}I(x\in R_m)$$

其中

$${\hat{c}}_m=\frac{1}{N_m}\sum _{x_i\in R_m(j,s)}{y}_i,x\in R_m,m=1,2$$

ID3算法

在决策树学习中，ID3（Iterative Dichotomiser 3）是由 Ross Quinlan 发明的一种算法，以 Hunt 算法为基础，用于从数据集生成决策树。ID3 是 C4.5 算法的前身。ID3 算法只能处理特征属性均为离散数据类型的数据集且不支持剪枝。

ID3 算法以原始集合 $S$ 为根节点。在算法的每次迭代中，根据集合 $S$ 的每一个未使用的特征属性进行遍历，根据该属性的所有取值，计算按该属性分割后的熵 $H(S)$ 或信息增益 $IG(S)$。然后，从中选择熵值最小（或信息增益最大）的属性。之后，根据该属性的所有取值对集合 $S$ 进行分割，以产生数据的子集。需要指出的是，ID3 算法生成的树可能是多元树，即一个节点的子节点可能会多于两个，具体数量依赖于该节点所对应的属性的所有可能的取值。该算法继续对每个子集进行递归，只考虑以前从未选择过的属性，因为此时每个子集中，已经选择过的属性的数据都是纯的。

ID3 算法与 CART 算法的不同之处主要表现在：

• ID3 只能处理特征属性为离散数据类型的数据集；
• ID3 不支持剪枝；
• ID3 生成的树是一个多元树，集合 $S$ 按照属性 $A$ 进行分割后，子集的数量（子节点的数量）与属性 $A$ 的取值有关。所有属性 $A$ 的取值都是分割点，因此，每个子集里的样本数据的属性 $A$ 的取值都是相同的。因此，针对子集的后续分割将不再考虑已经选择过的属性。
• 选择特征属性依据信息熵和信息增益。

ID3 算法主要用于分类决策树。ID3 不保证最优解，它可能收敛于局部最优解。它采用贪心的策略，在每次迭代中选择局部最佳属性来分割数据集。在搜索最优决策树的过程中，可以通过使用回溯来提高算法的效率，但代价是可能需要更长的时间。

ID3 对训练数据可能会出现过拟合。为了避免过拟合，应该优先选择较小的决策树，而不是较大的决策树。ID3 在连续数据上比在离散数据上更难使用。如果任何一个给定属性的值是连续的，那么在这个属性上有更多的地方可以拆分数据，寻找最佳的拆分值会很耗时。

信息熵与信息增益

在信息论中，随机变量的熵是指该变量的可能结果中固有的“信息”或“不确定性”的平均水平。信息熵的概念是由克劳德·香农（Claude Shannon）在 1948 年发表的论文《通信的数学理论》中提出的，为了纪念他，有时也称为香农熵。熵衡量的是数据集 $S$ 的不确定性的水平。信息熵的概念是由克劳德·香农（Claude Shannon）提出的。

给定一个离散随机变量 $X$ 和样本数据集合 $S$，$X$ 有 $N$ 个取值，可能的取值为 $x_1,\dots ,x_n$，各自发生的概率分别为 $p(x_1),\dots ,p(x_n)$，则 $S$ 的熵正式定义为：

$$H(S)=-\sum _{x_i\in X,i=1}^{N}p(x_i){\log }_{2}p(x_i)\text{\hspace{1em}(9)}$$

在信息理论和机器学习中，信息增益是 KL 散度（Kullback-Leibler divergence）的同义词，即一个变量的单变量概率分布与这个变量基于给定的另一个变量的条件分布的 KL 散度的条件期望值。然而，在决策树的上下文中，它与互信息（mutual information）同义，即一个随机变量或信号的信息量。

对于离散随机变量 $X$ 和样本数据集合 $S$，给定另一个随机变量 $A$，它代表样本数据集合 $S$ 的另一个属性，它的取值可能是 $\{a_1,a_2,a_3,\dots ,a_w\}$，这样根据随机变量 $A$ 的取值，样本集合 $S$ 被划分为 $w$ 个子集合

$$S_A(a_i)=\{v\in S\mid v_A=a_i\},a_i\in \{a_1,a_2,a_3,\dots ,a_w\}$$

由此得到的信息增益由如下公式计算：

$$IG(S,A)=H(S)-H(S\mid A)\text{\hspace{1em}(10)}$$

其中 $H(S\mid A)$ 是给定取值 $a$ 时 $S$ 的条件熵：

$$H(S\mid A)=\sum _{a_i\in A}\frac{|S_A(a_i)|}{|S|}H(S_A(a_i))\text{\hspace{1em}(11)}$$

C4.5 算法

C4.5 是由 Ross Quinlan 开发的，是对他的早期的 ID3 算法的扩展。C4.5 生成的也是分类决策树。2011 年，Weka 机器学习软件的作者将 C4.5 算法描述为“一个具有里程碑意义的决策树程序，可能是迄今为止在实践中应用最广泛的机器学习主力算法”。C4.5 算法在 2008 年的论文《数据挖掘十大算法》（Springer LNCS）中排名第一。

C4.5 是 ID3 的继承者，相对于 ID3 算法，C4.5 算法的改进主要有：

• 增加了对连续特征属性的处理，通过排序连续属性值并挑选阈值，将连续特征属性划分为高于阈值的属性和小于或等于阈值的属性；
• 增加了对属性值缺失的训练数据的处理；
• 挑选特征属性依据信息增益率，而不是信息增益；
• 创建树后进行修剪，试图通过用叶子节点进行替换来删除那些没有帮助的分支。

信息增益率

使用信息增益其实有一个缺点，那就是它偏向于具有大量取值的特征属性。也就是说在训练集中，如果某个特征属性所取的不同值的个数越多，那么越有可能拿它作为分割属性。

例如一个训练集 $S$ 中有 10 个样本，某一个特征属性 $A$ 分别取 1～10 这十个数，如果用 $A$ 进行分割将会分成 10 个子集合，那么对于每一个类，根据如下的信息增益公式：

$$IG(S,A)=H(S)-H(S\mid A)\text{\hspace{1em}(12)}$$

$$H(S\mid A)=\sum _{a_i\in A}\frac{|S_A(a_i)|}{|S|}H(S_A(a_i))\text{\hspace{1em}(13)}$$

由于 $\frac{|S_A(a_i)|}{|S|}=\frac{1}{10}$，$H(S_A(a_i))=0$，因此，$IG(S,A)=H(S)$，该属性划分所得到的信息增益最大，但是很显然，这种划分没有意义。极端的情况下，如果特征属性 $A$ 是连续值，也会出现类似情况。因此，选择信息增益最大的属性作为分割点，存在明显的不足。正是基于此，C4.5 采用了信息增益率这样一个概念。

对于离散随机变量 $X$ 和样本数据集合 $S$，给定另一个随机变量 $A$，它代表样本数据集合 $S$ 的另一个属性，它的取值可能是 $\{a_1,a_2,a_3,\dots ,a_w\}$，这样根据随机变量 $A$ 的取值，样本集合 $S$ 被划分为 $w$ 个子集合 $S_A(a_i)$，$a_i\in \{a_1,a_2,a_3,\dots ,a_w\}$。其中，

$$S_A(a_i)=\{v\in S\mid v_A=a_i\}$$

则信息增益率定义如下：

$$IGR(S,A)=\frac{IG(S,A)}{H_A(S)}\text{\hspace{1em}(14)}$$

$$H_A(S)=-\sum _{i=1}^w\frac{|S_A(v_i)|}{|S|}{\log }_2\frac{|S_A(v_i)|}{|S|}\text{\hspace{1em}(15)}$$

采用信息增益率替代信息增益来寻找最优分割特征。信息增益率的定义是信息增益 $IG(S,A)$ 和特征熵 $H_A(S)$ 的比值。对于特征熵，特征的取值越多，特征熵就倾向于越大。

连续属性的处理

对于连续值的问题，需要将连续值离散化。在这里只做二类划分，即将连续值划分到两个区间，分割点取两个临近值之间的任意值。给定样本集 $S$ 和连续属性 $A$，假定 $A$ 在 $S$ 上出现了 $w$ 个不同的取值，将这些值从小到大排序，记为 $\{a_1,a_2,\dots ,a_w\}$。$a_i$ 和 $a_{i+1}$ 是相邻的取值，则 $t$ 在区间 $[a_i,a_{i+1})$ 中取任意值所产生的划分结果相同，通常取 $\frac{a_i+a_{i+1}}{2}$。因此，对连续属性 $A$，我们可考察包含 $w-1$ 个候选分割点的集合。然后就可以像离散属性那样来考察这些分割点，选取最优的分割点进行样本集合的划分。

当决策树的节点数量比较多、连续型属性数量比较多、连续型属性中任一属性取值又比较多时，算法的计算量是相当大的，这将会在很大程度上影响决策树的生成效率。这是 C4.5 算法的缺点。

缺失值的处理

对于缺失值的问题，我们需要解决三个问题：第一是在有缺失值的情况下如何选择划分的属性，也就是如何得到一个合适的信息增益率；第二是选定划分属性后，如何处理该属性缺失特征的样本；第三是决策树构造完成后，如果测试样本的某些属性值出现缺失，该如何确定该测试样本的类别。Ross Quinlan 在 C4.5: Programs for Machine Learning 中提供了解决方案。

选择特征属性时

在 C4.5 算法中，选择信息增益率最大的属性作为最优的划分属性。当样本存在属性值缺失时，这些样本不会产生任何信息增益。因此，当计算该属性的信息增益时，其信息增益等于无缺失值样本所占的比例乘以无缺失值样本子集的信息增益。具体定义如下：

$$IG(S,A)=\alpha IG(S^{\prime },A)\text{\hspace{1em}(16)}$$

$$IG(S^{\prime },A)=H(S^{\prime })-H(S^{\prime }\mid A)\text{\hspace{1em}(17)}$$

其中 $\alpha$ 表示无缺失值样本所占的比例，$S$ 表示原数据集，$S^{\prime }$ 表示不含缺失值的数据子集。

我们以天气与打网球的数据集为例来具体讲述缺失值属性的信息增益的计算过程，如表所示。

表 存在缺失值的天气数据

• 天气 = ?
  • 晴朗：1,2,7,8,9,10,11，$w=4/11$
  • 阴天：1,3,7,10,12,13，$w=3/11$
  • 下雨：1,4,5,6,7,10,14，$w=4/11$

策树的构造。与以上第一步计算的不同之处有以下两点：

• 在计算样本中的正负样本比例时，未缺失的样本为 1，缺失值的样本为 $w$。
• 在计算某类样本所占比例时，每个未缺失样本数量为 1，每个缺失值样本数量为 $w$。

由此我们可以继续向下选择划分属性，构造出最终的决策树。

待预测样本出现缺失值的处理

利用决策树进行预测时，如果遇到测试特征属性 $A$ 的节点，而对于该预测样本，其特征属性 $A$ 出现缺失，那么所有的可能性都会被探讨。因此，对于每个可能的子节点都要进行预测。我们保留每个子节点的分布，并将其加入。最后，选择用于预测的类是具有最大概率值的类。

我们将具有“天气”属性缺失值的测试样本 $s(15)=\{-,热,高,弱,Yes\}$ 代入决策树节点中进行测试。其中，子节点中的灰色数字代表预测为正类的样本，黑色数字代表预测为负类的样本。在将 $s(15)$ 加入各个子节点后，统计其概率分布，依次为 $1/2$、$1$、$1/2$，因此标记“阴天”的分支连接的子节点概率最大，故 $s(15)$ 应该路由到“阴天”分支对应的子节点。

以上即为 C4.5 中对缺失值的完整处理过程。

决策树的评估

决策树作为一种有监督的无参数机器学习算法，有着与一般机器学习应用一样的流程和评价指标，这里做一些必要的介绍。

决策树模型被构建出来之后，需要建立对应的评估方法来衡量决策树模型的优劣。一般来说，决策树算法将数据集分为两部分：训练集用来建立模型，测试集用来评估模型。

对于二分类问题，我们可以将样本分为正样本（positive）和负样本（negative）两大类。同时，引入 TP、TN、FP、FN 四个计算指标来进行模型评估指标的计算。这四个计算指标中，第一个字母代表模型判断结果是否正确（T 为正确，F 为错误），第二个字母代表模型判断的结果（P 代表正类，N 代表负类）。那么，它们的概念可以归纳如下：

• TP：模型判断的结果正确，且样本为正样本的数量；
• TN：模型判断的结果正确，且样本为负样本的数量；
• FP：模型判断的结果错误，且样本为负样本的数量；
• FN：模型预测的结果错误，且样本为正样本的数量。

接下来，我们介绍混淆矩阵（confusion matrix）的概念。混淆矩阵是用来进行模型评估的一种规范格式，其形式为 $n\times n$ 大小的矩阵。它的每个元素（第 $i$ 行第 $j$ 列）代表第 $j$ 列对应的真实类别被预测为第 $i$ 行对应的预测类别的样本数量。二分类模型对应的混淆矩阵如表所示。

表 混淆矩阵

建立在二分类混淆矩阵的基础上。

• 准确率（accuracy）：模型所有预测正确的样本数占总样本数量的比重。公式表示为：

$$accuracy=\frac{TP+TN}{TP+FP+FN+TN}\text{\hspace{1em}(18)}$$

• 精确度（precision）：模型所有正确预测为正类的样本占所有预测为正类样本数量的比重。公式表示为：

$$precision=\frac{TP}{TP+FP}\text{\hspace{1em}(19)}$$

• 召回率（recall）：模型所有正确预测为正类的样本占所有真实为正类样本数量的比重。公式表示为：

$$recall=\frac{TP}{TP+FN}\text{\hspace{1em}(20)}$$

对于准确率指标，它的值代表了总的预测正确率，但它对于样本分布不均衡的情况却并不能体现出效果。举个例子，数据集中含有 95% 的正类样本，5% 的负类样本，我们将所有样本预测为正类样本，也可以得到 95% 的准确率。此时，准确率就失去了意义，需要考虑其他更合适的评估指标。对于精确度指标，它解决了总体数据不均衡造成的问题。精确度代表同一类别中预测正确的数量占预测为该类别的比重，体现了各类别的预测精度。对于召回率，它的计算主要是针对原数据集中各类样本而言的。同时，召回率与精确度互相影响：一般召回率高，精确度越低；精确度高，召回率就会低。在实践中，我们可以通过观察它们的分布情况尽量同时得到较高的精确度和召回率。