决策树DT：ID3、C4.5原理及python实现

本文主要是介绍决策树DT：ID3、C4.5原理及python实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

决策树模型与学习
特征选择
- 信息增益
- 信息增益比
ID3算法
- 决策树生成
- ID3算法的不足
C4.5算法
- 连续值处理
- 缺失值处理
- C4.5算法的不足
决策树剪枝
程序实现ID3

决策树模型与学习

决策树分类: 从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到对应子节点；若子节点为特征的一个取值，则递归的对实例进行测试并分配，直到到达叶节点（类别）。

决策树与条件概率分布（判别式模型） 特征空间被划分为互不相交的区域，每个区域定义一个类的概率分布，从而构成了一个条件概率分布。
各区域（叶节点）上的条件概率偏向于一个类，决策树分类时，强行将节点的实例划分为条件概率较大的一类。

特征选择

特征选择在于选取具有分类能力的特征，使得每次分割之后，各分支节点所含样本尽可能属于同一类别。这样可加快决策树的生成。

信息增益

信息熵（Information Entropy）是表示随机变量纯度/不确定性的指标。设 $X$ 为有限取值的随机变量（类别），其概率分布（类别比例）
$P(X=x_i)=p_i, \quad (i = 1, 2, \cdots, \mathcal{|Y|})$

则随机变量 $X$ 的信息熵记作 $H (X)$ ，即
$H(X)=-\sum_{i=1}^{\mathcal{|Y|}}p_i\log_2p_i$

熵的取值与随机变量取值无关，仅与其概率分布有关。熵值越小，不确定性越低、数据集纯度越高。 $\leq H(p) \leq \log \mathcal{|Y|}$ 。

设有随机变量 $(X, Y)$ ，其联合概率分布
$P(X = x_i, Y = y_i)=p_{ij}$

随机变量X和Y的条件熵
$\begin{aligned} H(Y|X) &= - \sum_{i=1}^n \sum_{j=1}^m p(x_i, y_i) \log_2 p(y_i | x_i) \\ & = - \sum_{i=1}^n \sum_{j=1}^m p(x_i)p(y_i|x_i) \log_2 p(y_i | x_i) \\ & = \sum_{i=1}^n p(x_i) H(Y|X=x_i) \end{aligned}$

条件熵 $H (Y ∣ X)$ 表示已知 $X$ 的条件下 $Y$ 的不确定性，上式为已知 $X$ 的条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望。当熵和条件熵由数据估计得到时，熵和条件熵分别称为经验熵和经验条件熵。

信息增益度量得知特征 $X$ 而使得类 $Y$ 不确定性减少的程度，定义为样本集 $D$ 的经验熵与已知特征 $a$ 条件下 $D$ 的经验条件熵之差，即
$g (D, a) = H (D) - H (D ∣ a)$

注：信息增益亦称为类与特征的互信息。

图1 联合熵、条件熵与互信息（信息增益）间的关系

最优划分属性应使划分后的样本信息增益/纯度最大（不确定性降低），即条件熵取最小
$a_{opt} = \arg \min_A \sum_{v=1}^Vp_vH(Y|X=x_v)$

可见，信息增益准则偏好于取值较多的属性（V较大）。

表1 西瓜数据集2.0

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	否
10	青绿	硬挺	清脆	清晰	平坦	软粘	否
11	浅白	硬挺	清脆	模糊	平坦	硬滑	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	否

由上表可知，类别 $\mathcal{|Y|}=2$ ，信息熵
$H(D)=-\frac{8}{17} \log_2\frac{8}{17} -\frac{9}{17} \log_2\frac{9}{17} = 0.998$

若选择色泽作为划分属性，色泽包含的属性值有{青绿，乌黑，浅白}，分别标记位 $D_1$ 、 $D_2$ 、 $D_3$ ，则
$\begin{aligned} g(D, 色泽) &= H(D) - \left(\frac{6}{17}H(D_1)+ \frac{6}{17}H(D_2) + \frac{5}{17}H(D_3)\right) \\ & = 0.998 - \frac{1}{17} \left[ 6\left( -\frac{3}{6} \log_2 \frac{3}{6} -\frac{3}{6} \log_2 \frac{3}{6} \right) + \left( -\frac{4}{6} \log_2 \frac{4}{6} -\frac{2}{6} \log_2 \frac{2}{6} \right) + \left( -\frac{4}{5} \log_2 \frac{4}{5} -\frac{1}{5} \log_2 \frac{1}{5} \right) \right] \\ & = 0.109 \end{aligned}$

同理，可计算出其他特征的信息增益，其中具有最大信息增益的属性为 $g (D, 纹理) = 0.381$ 。因此，使用纹理特征对样本集进行划分，所得样本的不确定性最小。

信息增益比

极端情况下，若样本集含n个样本，离散属性a含n个属性。若使用属性a分割样本集，则所得各分支节点的信息熵均为0，此时划分后的样本集纯度最大。但每个分支节点仅含1个样本，所得决策树无泛化能力。

定义增益率为特征 $a$ 的信息增益 $g (D, a)$ 与训练集 $D$ 关于特征 $a$ 的值的熵 $H_a(D)$ 之比，即
$g_R(D, a) = \frac{g(D, a)}{H_a(D)}$

其中分母项为特征a的信息熵 $H_a(D) = \sum_{i=v}^V\dfrac{|D_v}{|D|} \log_2\dfrac{D_v}{D}$ 。

属性a的取值越多，分母可能越大，增益率准则偏好于较少取值多的属性。因此，最优分割属性应同时具有较高信息增益和增益比，如C.5算法先选择信息增益高于平均值的属性，再从中选择增益率高的属性。

ID3算法

决策树生成

输入：训练集 $D$ ，特征集 $A$ ，阈值 $\varepsilon$
输出：决策树 $T$

递归生成决策树算法，如下：

若数据集 $D$ 中所有实例均属于同一类 $C_k$ ，则 $T$ 为单节点树（叶节点），将类别 $C_k$ 作为节点类标记，返回 $T$ ；
若特征集 $A$ 为空，则 $T$ 为单节点树，将 $D$ 中含样本最多的类别 $C_k$ 作为其类标记，返回 $T$ ；
计算 $A$ 中各特征的信息增益，选择信息增益最大的特征 $a_{opt}$ 对样本集 $D$ 进行划分；
若 $a_{opt}$ 的信息增益小于阈值 $\varepsilon$ ，则置 $T$ 为单节点树，将 $D$ 中含样本最多的类别 $C_k$ 作为其类标记，返回 $T$ ；
否则，使用 $a_{opt}$ 的 $V$ 个不同属性值将 $D$ 划分为 $V$ 个不同的子集 $D_v$ ，每个子集均为节点的一个分支；
对所有分支节点，令 $D=D_v$ 、 $A=A-a_{opt}$ ，递归调用上述步骤，得到分支树并返回；

ID3算法的不足

未考虑具有连续值的属性；
极端情况下选择信息增益最大的属性（完全随机性变量）会使模型失去泛化能力；
未考虑缺失值处理与过拟合问题；

C4.5算法

C4.5对ID3算法进行了改进，使用信息增益比选择每次划分数据集的最优特征，并对缺失值和过拟合问题进行了处理。

连续值处理

将连续值离散化，如m个样本的特征 $a$ 有 $m$ 个不同的属性值，将属性值升序排列为 $a_1,\cdots,a_m$ ；
取相邻属性值的均值作为划分点，共计 $m - 1$ 个，每个划分点 $t$ 可将 $D$ 分为子集 $D_t^-$ 和 $D_t^+$ ；
分别计算 $m - 1$ 个划分点作为二元分类的信息增益，取信息增益最大的点作为分类点；
$g_R(D, a) = \max_{t \in T_a} g_R(D, a, t) = \max_{t \in T_a} (H(D)- \sum_{\lambda \in \{-, +\}} \frac{|D_t^\lambda|}{|D|}H(D_t^\lambda))$
以连续属性划分的节点，连续属性还可作为其后代节点的划分属性；

缺失值处理

如何在属性值缺失的情况下选择最优划分属性？
给定训练集 $D$ 和属性 $a$ ，令 $\tilde D$ 表示 $D$ 在属性 $a$ 上没有缺失值的样本子集，每个样本 $x$ 的权重为 $w_x$ （初始为1），则
$\begin{aligned} \rho &= \frac{\sum_{x \in \tilde D} w_x}{\sum_{x \in D} w_x} \\ \,\\ \tilde p_k &= \frac{\sum_{x \in \tilde D_k} w_x}{\sum_{x \in \tilde D} w_x} \quad(1 \leq k \leq |\mathcal{Y}|) \\ \,\\ \tilde r_v &= \frac{\sum_{x \in \tilde D^v} w_x}{\sum_{x \in \tilde D} w_x} \quad (1 \leq v \leq V) \end{aligned}$

式中， $\rho$ 表示未缺失值比例、 $\tilde p_k$ 表示 $\tilde D$ 中类别为 $k$ 的样本比例、 $\tilde r_v$ 表示 $\tilde D$ 中属性 $a$ 取值为 $a_v$ 的样本比例。

因此缺失值属性a的信息增益推广为
$\rho \times g(\tilde D, a) = \rho \times \left(H(\tilde D) - \sum_{v=1}^V \tilde r_v H(\tilde D^v) \right), \quad H(\tilde D^v) =-\sum_{k=1}^{|\mathcal{Y}|} \tilde p_k \log_2 p_k$

给定划分属性，若样本在该属性上值缺失，如何对样本进行分配？

若样本 $x$ 在划分属性 $a$ 上取值已知，则将 $x$ 划入其取值对应的子节点，样本权值保持不变；若取值未知则将样本 $x$ 划分到所有分支节点，样本权值在 $a^v$ 的分支节点中调整为 $\tilde r_v \cdot w_x$ 。

直观上，同一样本以不同概率分配到不同的分支节点。

C4.5算法的不足

生成的决策树为多叉树（一个父节点含多个子节点），没有二叉树模型效率高；
只能用于分类，不能用于回归；
使用熵模型选取最优划分属性，计算复杂，尤其是处理连续值属性；

决策树剪枝

一般情况下递归产生的决策树对训练数据的分类很准确，但有可能对未知数据的分类表现很差。上述现象称为过拟合，一般通过简化决策树复杂度（剪枝）解决。

预剪枝
在划分之前，评估单节点树以及节点按属性值展开后的预测精度，若单节点树的预测精度不低于展开后树的预测精度，则将该节点作为叶节点。

后剪枝
定义决策树的损失函数如下：
$C_\alpha(T) = \sum_{t=1}^{|T|}N_tH_t(T)+\alpha |T| = C(T) + \alpha |T|, \quad H_t(T)=-\sum_k \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}$

式中， $∣ T ∣$ 为叶节点数目（模型的复杂度）， $t$ 是树 $T$ 的叶节点， $N_t$ 为节点 $t$ 所含样本数， $N_{tk}$ 为 $t$ 节点中类别为 $k$ 的样本数， $k=1,2,\cdots,K$ ， $H_t(T)$ 为 $t$ 节点的经验熵，可变参数 $\geq 0$ ， $C (T)$ 为模型对训练数据的预测误差。

参数 $\alpha$ 的值可平衡模型复杂度和训练误差。 $\alpha=0$ 时，表示不考虑模型复杂程度，只考虑训练误差。较大的 $\alpha$ 偏向于较简单的模型（ $T$ 小，训练误差大），较小的 $\alpha$ 偏向于较复杂的模型（ $T$ 大，训练误差小）。

决策树的生成只考虑拟合效果（局部模型），而决策树剪枝是通过优化损失函数。

程序实现ID3

from collections import Counter
from itertools import chain
from math import log2import numpy as npfrom_iterable = chain.from_iterabledef cal_entropy(array):"""计算信息熵"""total = 1. * len(array)ent = 0.0for value in Counter(array).values():prob = value / totalent -= prob * log2(prob)return entdef cal_gain(feat_values, categories):"""计算某特征的信息增益"""uniques = set(feat_values)nums = len(uniques)feat_dict = dict(zip(uniques, range(nums)))# 提取各特征值的子集sub_labels = [[] for _ in range(nums)]for value, category in zip(feat_values, categories):sub_labels[feat_dict[value]].append(category)# 计算条件熵cond_ent = 0.0total = len(categories)for array in sub_labels:cond_ent += cal_entropy(array) * len(array) / total# 返回信息增益return cal_entropy(categories) - cond_entdef tree_depth(tree):"""计算决策树深度，字典形式存储"""if isinstance(tree, dict):branches = [value for value in tree.values()][0]return max(tree_depth(node) for node in branches.values()) + 1else:return 1class DecisionTree_ID3:def __int__(self):self.tree = Nonepassdef train(self, X, y, names=None):self._feat_names = ['FEAT_{}'.format(i) for i inrange(len(X[0]))] if names is None else namesunique = list(set(y))category2num = dict((category, num) for category, num inzip(unique, range(len(unique))))self._names = uniquecategories = [category2num[i] for i in y]data_set = np.hstack((X, np.array([categories]).T))# 生成决策树self.tree = self._make_tree(data_set, self._feat_names)def _make_tree(self, data_set, feat_names):"""生成决策树"""categories = data_set[:, -1]# 当前节点包含的样本为同一类别category = categories[0]if np.all(categories == category):return self._names[int(category)]# 当前属性集为空，返回样本中频数最大的类别if len(data_set[0]) == 1:return Counter(categories).most_common(1)[0][0]best_num = self.best_feat(data_set)best_name = feat_names[best_num]# 以当前节点为根的树my_tree = {best_name: {}}node = my_tree[best_name]# 最优特征values = data_set[:, best_num]# 遍历各属性值data_set = np.delete(data_set, best_num, axis=1)feat_names = np.delete(feat_names, best_num)for value in set(values):sub_data_set = data_set[values == value]node[value] = self._make_tree(sub_data_set, feat_names)return my_treedef best_feat(self, data_set):"""计算最优特征，ID3算法每次选取信息增益最大的特征"""categories = data_set[:, -1]nums = len(data_set[0]) - 1gains = [cal_gain(data_set[:, i], categories) for i in range(nums)]# 找到最大信息增益特征的所在列位置num = 0max_gain = gains[0]for i, gain in enumerate(gains[1:]):if max_gain < gain:num = i + 1max_gain = gainreturn numif __name__ == '__main__':X = [['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑'],['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑'],['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘'],['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘'],['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑'],['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑'],['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘'],['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑'],['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘'],['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑'],['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑'],['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘'],['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑'],['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑']]y = ['好瓜', '好瓜', '好瓜', '好瓜', '好瓜', '好瓜', '好瓜', '好瓜', '坏瓜', '坏瓜', '坏瓜', '坏瓜','坏瓜', '坏瓜', '坏瓜', '坏瓜', '坏瓜']names = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']tree = DecisionTree_ID3()tree.train(X, y, names)print(tree.tree)    # print(tree_depth(tree.tree))