决策树的 ID3 与 C4.5 生成算法

Reference

• 【机器学习】决策树（上）——ID3、C4.5、CART
• 决策树—ID3、C4.5、CART

【ID3 算法】

概述

ID3 相当于用极大似然估计进行概率模型的选择，其核心是在决策树各结点上使用信息增益作为量化标准来选择特征，递归地构建决策树

具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，再对子结点递归的调用以上方法，构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止

ID3 的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分，也就是说，如果一个特征有 3 种取值，那么数据将被切分成 3 份，一旦按照某特征切分后，该特征在之后的算法执行过程中将不会再起作用

归结来说，除上述探讨的问题外，ID3 存在以下问题：

• 无法直接处理连续型数据
• 采用信息增益作为特征选择的准则，可能对特征取值数较多的特征有偏好
• 没有考虑数据存在缺失值的情况
• 没有剪枝策略，生成的决策树结构可能过于复杂，容易发生过拟合现象

算法流程

ID3 的算法流程如下：

1. 初始化特征集合 $A$、数据集 $D$
2. 计算数据集 $D$ 的信息熵 $H(D)$ 与所有特征的条件熵 $H(D|A_i)$
3. 根据 $H(D)$ 与 $H(D|A_i)$ 计算信息增益 $g(D|A_i)$，选择信息增益最大的特征 $A_g$ 作为当前决策结点
4. 更新数据集 $D$ 和特征集 $A$，即删除上一步所使用的特征 $A_g$，并按 $A_g$ 的取值来划分不同的数据子集
5. 若数据子集包含单一特征，则为叶结点，否则，对新划分的数据子集重复第 2、3、4 步，直到所有特征的信息增益均很小或没有特征可以选择为止

实例

以 信息增益与信息增益比 中的实例为例，即对于下表：

各特征的信息增益如下：

$$\begin{matrix} g(D,A_1)=H(D)-H(D|A_1) = 0.083\\ g(D,A_2)=H(D)-H(D|A_2) = 0.324\\ g(D,A_3)=H(D)-H(D|A_3) = 0.420\\ g(D,A_4)=H(D)-H(D|A_4) = 0.363 \end{matrix}$$

选择信息增益最大的特征，是否有房子 $A_3$，作为根结点的特征，其有两个取值 是、否，据此将训练集 $D$ 划分为两个子集 $D_1$ 和 $D_2$

对于 $D_1$ 来说，其分类结果只有同一类 是 的样本点，因此其成为一个叶结点，该叶结点的类标记为 是

对于 $D_2$ 来说，要进一步从特征 $A_1$、$A_2$、$A_4$ 中选择新的特征，计算各特征的信息增益：

$$\begin{matrix} g(D_2,A_1)=H(D)-H(D|A_1) = 0.251\\ g(D_2,A_2)=H(D)-H(D|A_2) = 0.918\\ g(D_2,A_4)=H(D)-H(D|A_4) = 0.474 \end{matrix}$$

选择信息增益最大的特征，是否有工作 $A_2$，作为分支结点的特征，其有两个取值 是、否，据此将训练集 $D_2$ 划分为两个子集 $D_{21}$ 和 $D_{22}$

对于 $D_{21}$ 来说，其分类结果只有同一类 是 的样本点，因此其成为一个叶结点，该叶结点的类标记为 是

对于 $D_{22}$ 来说，其分类结果只有同一类 否 的样本点，因此其成为一个叶结点，该叶结点的类标记为 否

据此，生成一个如下图的决策树，其只用了两个特征

【C4.5 算法】

概述

对于 ID3 来说，其存在以下四点缺陷：

1. 无法直接处理连续型数据
2. 采用信息增益作为特征选择的准则，可能对特征取值数较多的特征有偏好
3. 没有考虑数据存在缺失值的情况
4. 没有剪枝策略，生成的决策树结构可能过于复杂，容易发生过拟合现象

C4.5 严格来说是 ID3 的改进算法，其通过对 ID3 的改进，一定程度上解决了上述的四个问题：

1. 采用了连续特征离散化的方法，将连续型特征转为离散型特征，但这种转换过程可能会破坏连续型变量的内在性质
2. 采用了信息增益比作为特征选择的标准，以校正信息增益偏向取值较多的特征的问题
3. 通过计算概率的方式，将信息增益的计算式进行了推广，从而解决缺失值处理的问题
4. 采用悲观剪枝策略对决策树进行后剪枝

C4.5 相较于 ID3 来说，准确率更高，实现也简单，但对数据进行了多次顺序扫描与排序，效率较低，仅适合小规模的数据集

连续特征离散化

C4.5 采用了连续特征离散化的策略，将连续型数据进行处理，最简单的离散化策略是利用二分法对连续特征进行处理

对于给定 $n$ 个样本的数据集 $D$ 和在 $D$ 上的连续型特征 $a$，假定 $a$ 在 $D$ 上出现 $m$ 个不同的取值，将这些值按照升序排序，记为 $\{a_1,a_2,…,a_m\}$

取相邻两样本值的平均值作为划分点，一共有 $m-1$ 个划分点，其中第 $i$ 个划分点记为：

$$T_i=\frac{a_i+a_{i+1}}{2}$$

对于这 $m-1$ 个划分点，分别计算以该点作为二元分类点时的信息增益，以信息增益最大的点作为该连续特征的二元离散分类点

简单来说，当取得信息增益最大的点为 $a_t$，则小于 $a_t$ 的值为 类别1，大于 $a_t$ 的值为 类别2，这样就做到了连续特征的离散化

要注意的是，与离散型数据不同的是，若当前结点为连续值，则该值还可参与子结点的特征选择过程

缺失值处理

在实际应用中，尤其是在样本特征数目众多的情况下，经常会遇到不完整的样本，即样本的某些特征值存在缺失

如果简单地放弃不完整的样本，仅使用无缺失的数据来学习，这无疑是对数据的极大浪费，为此，需要对缺失值进行处理

对于缺失值的处理可以分为两个子问题：

1. 在特征值缺失的情况下，如何进行特征选择，即如何计算特征的信息增益率
2. 给定划分特征后，对于缺失该特征值的样本如何处理，即将这个样本划分到哪个结点中

---

在给出上述两个问题答案前，先给出以下记号：

对于给定的分为 $K$ 类的具有 $|D|$ 个样本的训练集 $D$，存在一个具有 $n$ 个取值的特征 $A$

令 $\tilde{D}$ 表示 $D$ 中在特征 $A$ 上没有缺失值的样本子集，用 $\tilde{D_k}$ 表示在该子集上根据样本类别所划分的第 $k$ 个子集，用 $\tilde{D}^i$ 表示在 $\tilde{D}$ 上根据特征 $A$ 的取值 $A_i$ 所划分的第 $i$ 个子集

同时，为每一个样本 $\vec{x}$ 赋予一个权重 $w_\vec{x}$

用 $\rho$ 表示无缺失值样本所占的比例，即：

$$\rho=\frac{\sum\limits_{\vec{x}\in\tilde{D}}w_\vec{x}}{\sum\limits_{\vec{x}\in D}w_\vec{x}}$$

用 $\tilde{p_k}$ 表示无缺失值样本中第 $k$ 类所占的比例，即：

$$\tilde{p_k}=\frac{\sum\limits_{\vec{x}\in\tilde{D_k}}w_\vec{x}}{\sum\limits_{\vec{x}\in \tilde{D}}w_\vec{x}},\quad 1\leq k\leq K$$

用 $\tilde{r_i}$ 表示无缺失值样本中在特征 $A$ 上取值为 $A_i$ 的样本所占的比例，即：

$$\tilde{r_i}=\frac{\sum\limits_{\vec{x}\in\tilde{D}^i}w_\vec{x}}{\sum\limits_{\vec{x}\in \tilde{D}}w_\vec{x}},\quad 1\leq i\leq n$$

显然，有：

$$\sum\limits_{k=1}^K \tilde{p_k}=1,\quad \sum\limits_{i=1}^n \tilde{r_i}=1$$

---

对于第一个问题，显然可以利用 $\tilde{D}$ 来计算特征 $A$ 的信息增益率

基于上述定义，将信息增益的计算式进行推广，有：

$$\begin{align*} G(D,A) &= \rho\cdot G(\tilde{D},A) \\ &= \rho\cdot[H(\tilde{D})-\sum_{i=1}^n\tilde{r_i}H(\tilde{D}^i)] \\ &= \rho\cdot \bigl[ -\sum_{k=1}^K\tilde{p_k}\log_2\tilde{p_k} -\sum_{=1}^n\tilde{r_i}H(\tilde{D}^i) \bigr] \end{align*}$$

对于第二个问题，根据样本 $\vec{x}$ 在划分特征 $A$ 上的取值是否已知，分为两种情况：

• 已知：将 $\vec{x}$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_{\vec{x}}$
• 未知：将 $\vec{x}$ 同时划入所有子结点，且样本权值 $w_{\vec{x}}$ 在与特征值 $A_i$ 的对应的子结点中调整为 $\tilde{r_i}\cdot w_{\vec{x}}$

对于未知的情况，其本质就是让同一个样本以不同的概率划分到不同的子结点中

剪枝策略

C4.5 采用的悲观剪枝方法，用递归的方式按照树的后序遍历算法，从下向上针对每一个分支结点，评估用一个最佳叶结点去代替这棵子树是否有益

如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉，C4.5 通过训练集上的错误分类数量来估算未知样本上的错误率

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但同时其训练时间会大的多

关于悲观剪枝算法的详细介绍，见：决策树的剪枝策略