8.3 决策树生成之ID3与C4.5#
在正式介绍决策树的生成算法前，我们先将8.1.1节中介绍的几个概念重新梳理一下，同时再通过一个例子来理解整个计算过程，以便于后续更好地掌握决策树的生成算法。
8.3.1 基本概念与定义#
1. 信息熵
设$X$是一个取值有限的离散型随机变量（例如8.1.1节中可能夺冠的16支球队），其概率分布为$P(X=x_i)=p_i,i=1,2,...,n$（每支球队可能夺冠的概率），则随机变量$X$的信息熵定义为
$$ H(X)=-\sum\limits_{i=1}^{n}{{{p}_{i}}}\log {{p}_{i}}\tag{8-5} $$其中，若$p_i=0$，定义$0\log_20=0$，并且通常$\log$取$2$为底或$e$为底时，其熵的单位分别称为比特（Bit）或纳特（Nat）。如无特殊说明，默认以$2$为底。
2. 条件熵
设有随机变量$(X,Y)$，其联合概率分布$P(X={{x}_{i}},Y={{y}_{j}})={{p}_{ij}}$，其中$i=1,2,...,n，j=1,2,...,m$，条件熵$H(Y|X)$表示在已知随机变量$X$的条件下，随机变量$Y$的不确定性，其定义为
$$ H(Y|X)=\sum\limits_{i=1}^{n}{{{p}_{i}}}H(Y|X={{x}_{i}})\tag{8-6} $$其中，$p_i=P(X=x_i),i=1,2,...,n$。
同时，当信息熵和条件熵中的概率由样本数据估计（特别是极大似然估计）得到时，所对应的信息熵与条件熵分别称为经验熵（Empirical Entropy）和经验条件熵（Empirical Conditional Entropy）。这里暂时看不懂也没关系，可结合后续计算示例来理解。
3. 信息增益
根据8.1.1节的内容可知，所谓信息增益指的就是事物$U$的信息熵$H(U)$，在引入外部信息$I$以后后的变化量为$H(U)-H(U|I)$，因此，可以将特征$A$对训练数据集$D$的信息增益$g(D,A)$定义为集合$D$的信息熵$H(D)$与在给定特征$A$下$D$的条件熵$H(D|A)$之差，即
$$ g(D,A)=H(D)-H(D|A)\tag{8-7} $$设训练集为$D$，$|D|$表示所有训练样本总数，同时$D$有$K$个类别$C_k,k=1,2,...,K$。$|C_k|$为属于类$C_k$的样本总数，即$\sum\nolimits_{k=1}^{K}{|{{C}_{k}}|}=|D|$ 。设特征$A$有$n$个不同的取值$a_1,a_2,...,a_n$，根据特征$A$的取值将$D$划分为$n$个子集$D_1,D_2,...,D_n$，$|D_i|$为子集$D_i$中的样本个数，即$\sum\nolimits_{i=1}^{n}{|{{D}_{i}}|=|D|}$。同时此子集$D_i$中，属于类$C_k$的样本集合为$D_{ik}$，即${{D}_{ik}}={{D}_{i}}\bigcap {{C}_{k}}$，$|D_{ik}|$为$D_{ik}$的样本个数。此时有如下定义[2]
(1) 数据集$D$的经验熵$H(D)$为
$$ H(D)=-\sum\limits_{k=1}^{K}{\frac{|{{C}_{k}}|}{|D|}}{{\log }_{2}}\frac{|{{C}_{k}}|}{|D|}\tag{8-8} $$从式(8-8)可以看出，它计算的是“任意样本属于其中一个类别”这句话所包含的信息量。
(2) 数据集$D$在特征值$A$下的经验条件熵$H(D|A)$为
$$ H(D|A)=\sum\limits_{i=1}^{n}{\frac{|{{D}_{i}}|}{|D|}}H({{D}_{i}})=-\sum\limits_{i=1}^{n}{\frac{|{{D}_{i}}|}{|D|}}\sum\limits_{k=1}^{K}{\frac{|{{D}_{ik}}|}{|{{D}_{i}}|}}{{\log }_{2}}\frac{|{{D}_{ik}}|}{|{D}_{i}|}\tag{8-9} $$从式(8-9)可以看出，它计算的是特征$A$在各个取值条件下“任意样本属于其中一个类别”这句话所包含的信息量。
(3) 信息增益为
$$ g(D,A)=H(D)-H(D|A)\tag{8-10} $$8.3.2 计算示例#
如果仅看上面的公式肯定不那么容易理解，下面我们再进行举例说明。这里建议各位读者将上面的公式同下面的计算过程对比观看进行理解。表8-1同样是7.1.3节中用过的一个信用卡审批数据集，其一共包含15个样本和3个特征维度。其中特征$X^{(1)}\in A_1=\{1,0\}$表示有无工作，特征$X^{(2)}\in A_2=\{1,0\}$表示是否有房，特征${{X}^{(3)}}\in {{A}_{3}}=\{D,S,T\}$表示学历等级，$Y\in C=\{1,0\}$表示是否审批通过的类标记。
1. 计算信息熵$H(D)$
根据式(8-8)可得
$$ H(D)=-\left( \frac{5}{15}{{\log }_{2}}\frac{5}{15}+\frac{10}{15}{{\log }_{2}}\frac{10}{15} \right)\approx 0.918\tag{8-11} $$2. 计算条件熵
由表8-1可知，数据集有3个特征（工作、房子、学历）$A_1$、$A_2$、$A_3$，接下来根据式(8-9)来计算$D$分别在3个特征取值条件下的条件熵$H(D|A_i)$。
(1) 已知外部信息“工作”的情况下有
$$ \begin{aligned} & H(D|{{A}_{1}})=\left[ \frac{7}{15}H({{D}_{1}})+\frac{8}{15}H({{D}_{2}}) \right] \\[2ex] & =-\frac{7}{15}\left( \frac{3}{7}{{\log }_{2}}\frac{3}{7}+\frac{4}{7}{{\log }_{2}}\frac{4}{7} \right)-\frac{8}{15}\left( \frac{7}{8}{{\log }_{2}}\frac{7}{8}+\frac{1}{8}{{\log }_{2}}\frac{1}{8} \right)\approx 0.75 \end{aligned}\tag{8-12} $$式(8-12)中，$D_1$和$D_2$分别是$A_1$取值为“无工作”和“有工作”时，训练样本划分后对应的子集。
(2) 已知外部信息“房子”的情况下有
$$ \begin{aligned} & H(D|{{A}_{2}})=\left[ \frac{8}{15}H({{D}_{1}})+\frac{7}{15}H({{D}_{2}}) \right] \\[2ex] & =-\frac{8}{15}\left( \frac{4}{8}{{\log }_{2}}\frac{4}{8}+\frac{4}{8}{{\log }_{2}}\frac{4}{8} \right)-\frac{7}{15}\left( \frac{1}{7}{{\log }_{2}}\frac{1}{7}+\frac{6}{7}{{\log }_{2}}\frac{6}{7} \right)\approx 0.81 \end{aligned}\tag{8-13} $$式(8-13)中，$D_1$和$D_2$分别是$A_2$取值为“无房”和“有房”时，训练样本划分后对应的子集。
(3) 已知外部信息“学历”的情况下有
$$ \begin{aligned} & H(D|{{A}_{3}})=\left[ \frac{3}{15}H({{D}_{1}})+\frac{4}{15}H({{D}_{2}})+\frac{8}{15}H({{D}_{3}}) \right] \\[2ex] & =-\frac{3}{15}\left( \frac{1}{3}{{\log }_{2}}\frac{1}{3}+\frac{2}{3}{{\log }_{2}}\frac{2}{3} \right)-\frac{4}{15}\left( \frac{1}{4}{{\log }_{2}}\frac{1}{4}+\frac{3}{4}{{\log }_{2}}\frac{3}{4} \right) \\[2ex] & -\frac{8}{15}\left( \frac{3}{8}{{\log }_{2}}\frac{3}{8}+\frac{5}{8}{{\log }_{2}}\frac{5}{8} \right)\approx 0.91 \\ \end{aligned}\tag{8-14} $$式(8-14)中，$D_1$、$D_2$、$D_3$分别是$A_3$取值为D、S和T时，训练样本划分后对应的子集。
3. 计算信息增益
根据上面的计算结果便可以得到各特征划分下的信息增益为
$$ \begin{cases} g(D,{{A}_{1}})=0.918-0.75=0.168 \\[1ex] g(D,{{A}_{2}})=0.918-0.81=0.108 \\[1ex] g(D,{{A}_{3}})=0.918-0.91=0.08 \\[1ex] \end{cases}\tag{8-15} $$到目前为止，我们已经知道了在生成决策树的过程中所需要计算的关键步骤信息增益，接下来，我们就开始正式介绍如何生成一棵决策树。
8.3.3 ID3生成算法#
在8.1节的末尾我们总结到，构建决策树的核心思想就是： 每次划分时，要选择使信息增益最大的划分方式，以此来递归构建决策树。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征没有分类能力，因此，对于决策树生成的一个关键步骤就是选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率，而通常对于特征选择的准则就是8.1节讲到的信息增益。
ID3（Interactive Dichotomizer3）算法的核心思想是在选择决策树的各个节点时，采用信息增益来作为特征选择的标准，从而递归地构建决策树。其过程可以概括为，从根节点开始计算所有可能划分情况下的信息增益，然后选择信息增益最大的特征作为划分特征，由该特征的不同取值建立子节点，最后对子节点递归地调用以上方法，构建决策树，直到所有特征的信息增益均很小或没有可以选择为止。例如根据8.3.2节最后的计算结果可知，首先应该将数据样本以特征$A_1$（有无工作）作为划分方式对数据集进行第1次划分。下面开始介绍通过ID3来生成决策树的步骤及示例。
1. 生成步骤
输入： 训练数据集$D$，特征集$A$，阈值$\varepsilon$。
输出： 决策树[2]。
(1) 若$D$中所有样本属于同一类$C_k$（此时只有一个类别），则$T$为单节点树，将$C_k$作为该节点的类标记，返回$T$。
(2) 若$A=\emptyset$，则$T$为单节点树，并将$D$中样本数最多的类$C_k$作为该节点的类标记，并返回$T$。
(3) 否则，计算$A$中各特征对$D$的信息增益，选择信息增益最大的特征$A_g$。
(4) 如果$A_g$的信息增益小于阈值$\varepsilon$，则将$T$置为单节点树，并将$D$中样本数最多的类$C_k$作为该节点的类标记，返回$T$。
(5) 否则，对$A_g$的每个可能值$a_i$，以$A_g=a_i$将$D$分割为若干非空子集，并建立为子节点。
(6) 对于第$i$个子节点，以$D_i$为训练集，以$A-\{A_g\}$为特征集，递归地调用步骤(1)~步骤(5)，得到子树$T_i$，返回$T_i$。
2. 生成示例
下面就用ID3算法来对表8-1中的数据样本进行决策树生成示例。易知该数据集不满足步骤(1)和步骤(2)中的条件，所以开始执行步骤(3)。同时，根据8.3.2节最后的计算结果可知，对于特征$A_1$、$A_2$、$A_3$来讲，在$A_1$条件下信息增益最大，所以应该选择特征$A_1$作为决策树的根节点。
由于本例中未设置阈值，所以接着执行步骤(5)并按照$A_1$的取值将训练集$D$划分为两个子集$D_1$和$D_2$，如表8-2所示。
接着开始执行步骤(6)，由于$D_1$和$D_2$均不满足步骤(1)和步骤(2)中的条件，所以两部分需要分别继续执行后续步骤，此时生成的决策树如图8-5所示。
此时，对于子集$D_1$ 来讲，需要从特征$A-\{A_g\}$中即$A_2$和$A_3$中选择新的特征，并计算信息增益。
1. 计算信息熵$H(D_1)$
$$ H({{D}_{1}})=-\left( \frac{3}{7}{{\log }_{2}}\frac{3}{7}+\frac{4}{7}{{\log }_{2}}\frac{4}{7} \right)\approx 0.985\tag{8-16} $$2. 计算条件熵
$$ H({{D}_{1}}|{{A}_{2}})=-\frac{3}{7}\left( \frac{3}{3}{{\log }_{2}}\frac{3}{3}+0 \right)-\frac{4}{7}\left( \frac{1}{4}{{\log }_{2}}\frac{1}{4}+\frac{3}{4}{{\log }_{2}}\frac{3}{4} \right)\approx 0.464\tag{8-17} $$$$ H({{D}_{1}}|{{A}_{3}})=-\frac{1}{7}\left( 0+0 \right)-\frac{2}{7}\left( 0+0 \right)-\frac{4}{7}\left( \frac{3}{4}{{\log }_{2}}\frac{3}{4}+\frac{1}{4}{{\log }_{2}}\frac{1}{4} \right)\approx 0.464\tag{8-18} $$根据式(8-17)和式(8-18)的结果可知，对于子集$D_1$来讲，无论其采用$A_2$和$A_3$中的哪一个特征进行划分，最后计算得到的信息增益都是相等的，所以这里不妨就以特征$A_2$进行划分。
同理，对于子集$D_2$来讲，也需要从特征$A-\{A_g\}$中（$A_2$和$A_3$中）选择新的特征，并计算信息增益。
1. 计算信息熵$H(D_2)$
$$ H({{D}_{2}})=-\left( \frac{1}{8}{{\log }_{2}}\frac{1}{8}+\frac{7}{8}{{\log }_{2}}\frac{7}{8} \right)\approx 0.544\tag{8-19} $$2. 计算条件熵
$$ H({{D}_{2}}|{{A}_{2}})=-\frac{5}{8}\left( \frac{1}{5}{{\log }_{2}}\frac{1}{5}+\frac{4}{5}{{\log }_{2}}\frac{4}{5} \right)-\frac{3}{8}\left( 0+0 \right)\approx 0.451\tag{8-20} $$$$ H({{D}_{2}}|{{A}_{3}})=-\frac{2}{8}\left( 0+0 \right)-\frac{2}{8}\left( \frac{1}{2}{{\log }_{2}}\frac{1}{2}+\frac{1}{2}{{\log }_{2}}\frac{1}{2} \right)-\frac{4}{8}\left( 0+0 \right)=0.25\tag{8-21} $$3. 信息增益
$$ \begin{cases} g({{D}_{2}}|{{A}_{2}})=0.544-0.451=0.093 \\[1ex] g({{D}_{2}}|{{A}_{3}})=0.544-0.25=0.294 \\[1ex] \end{cases}\tag{8-22} $$根据式(8-22)的计算结果可知，对于子集$D_2$来讲，采用特征$A_3$来对其进行划分时所产生的信息增益最大，因此应该选择特征$A_3$来作为子集$D_2$的根节点。
至此，根据上述计算过程，便可以得到第二次划分后的结果，如表8-3所示。
从表8-3中的结果可知，$D_{11}$、$D_{21}$、$D_{23}$这3个子集中样本均只有一个类别，即满足生成步骤中的第(1)步，故此时可以得到第2次划分后的决策树，如图8-6所示。
由于子集$D_{12}$和$D_{22}$均不满足终止条件(2)和(4)，并且此时两个子集中均只有一个特征可以选择，所以并不需要再进行比较，此时直接划分即可，如表8-4所示。
根据表8-4中的结果可知，子集$D_{121}$满足生成步骤中的第(1)步，故此时可以得到第3次划分后的决策树，如图8-7所示。
此时，由于子集$D_{122}$和$D_{221}$满足生成步骤中第(2)步的终止条件，即再无特征可以进行划分，需要选择样本数最多的类别作为该节点的类别进行返回，但巧合的是子集$D_{122}$和$D_{221}$中不同类别均只有一个样本，因此随机选择一个类别即可。不过在实际过程中很少会出现这种情况，因为一般当节点的样本数小于某个阈值时也会停止继续划分。这样便可以得到最终生成的决策树，如图8-8所示。
如上就是通过ID3算法生成整个决策树的详细过程。根据生成步骤可以发现，如果单纯以$g(D,A)$作为标准，会存在模型倾向于选择取值较多的特征进行划分（例如上面的$A_3$）。虽然在上面这个例子中不存在，但是我们仍可以从直观上理解为什么ID3会倾向于选取特征值取值较多的特征。由于$g(D,A)$的直观意义是$D$被$A$划分后不确定性的减少量，因此可想而知当$A$的取值情况越多，那么$D$会被划分得到的子集就越多，于是其不确定性自然会减少得越多，从而ID3算法会倾向于选择取值较多的特征进行划分。可以想象，在这样的情况下最终得到的决策树将会是一棵很胖很矮的决策树，进而导致最后生成的决策树容易出现过拟合现象。
8.3.4 C4.5生成算法#
为了解决ID3算法的弊端，进而产生了C4.5算法。C4.5算法与ID3算法相似，不同之处仅在于C4.5算法在选择特征的时候采用了信息增益比作为标准，即选择信息增益比最大的特征作为当前节点的划分方式。具体为，特征$A$对训练集D的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与其训练集$D$关于特征$A$的信息熵$H_A(D)$之比，即
$$ {{g}_{R}}(D,A)=\frac{g(D,A)}{{{H}_{A}}(D)}\tag{8-23} $$其中，$H_A(D)=-\displaystyle\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2{\frac{|D_i|}{|D|}}$，$n$是特征$A$取值的个数。 因此，在8.3.3节的例子中，对于选取根节点时其增益比计算如下：
1. 计算得到信息增益
$$ \begin{cases} g(D,{{A}_{1}})=0.918-0.75=0.168 \\[1ex] g(D,{{A}_{2}})=0.918-0.81=0.108 \\[1ex] g(D,{{A}_{3}})=0.918-0.91=0.008 \\[1ex] \end{cases}\tag{8-24} $$2. 计算各特征的信息熵
$$ \begin{cases} {{H}_{{{A}_{1}}}}(D)=-\sum_{i=1}^2\frac{|{{D}_{i}}|}{|D|}=-(\frac{7}{15}{{\log }_{2}}\frac{7}{15}+\frac{8}{15}{{\log }_{2}}\frac{8}{15})\approx 0.997 \\[1ex] {{H}_{{{A}_{2}}}}(D)=-(\frac{8}{15}{{\log }_{2}}\frac{8}{15}+\frac{7}{15}{{\log }_{2}}\frac{7}{15})\approx 0.997 \\[1ex] {{H}_{{{A}_{3}}}}(D)=-(\frac{3}{15}{{\log }_{2}}\frac{3}{15}+\frac{4}{15}{{\log }_{2}}\frac{4}{15}+\frac{8}{15}{{\log }_{2}}\frac{8}{15})\approx 1.456 \\ \end{cases}\tag{8-25} $$3. 计算信息增益比
$$ \begin{cases} {{g}_{R}}(D,{{A}_{1}})=\frac{0.168}{0.997}=0.169 \\[1ex] {{g}_{R}}(D,{{A}_{2}})=\frac{0.108}{0.997}=0.108 \\[1ex] {{g}_{R}}(D,{{A}_{3}})=\frac{0.008}{1.456}=0.005 \\[1ex] \end{cases}\tag{8-26} $$根据式(8-26)的计算结果，此时应该以特征$A_1$的各个取值对样本集合$D$进行划分。
由此，可以将利用C4.5算法生成决策树的过程总结如下。
输入： 训练数据集$D$，特征集$A$，阈值$\varepsilon$。
输出： 决策树[2]。
(1) 若$D$中所有样本属于同一类$C_k$，则$T$为单节点树，将$C_k$作为该节点的类标记，返回$T$。
(2) 若$A=\emptyset$，则$T$为单节点树，并将$D$中样本数最多的类$C_k$作为该节点的类标记，并返回$T$。
(3) 否则，计算$A$中各特征对$D$的信息增益比，选择信息增益比最大的特征$A_g$。
(4) 如果$A_g$的信息增益比小于阈值$\varepsilon$，则将$T$置为单节点树，并将$D$中样本数最多的类$C_k$作为该节点的类标记，返回$T$。
(5) 否则，对$A_g$的每个可能值$a_i$，以$A_g=a_i$将$D$分割为若干非空子集，并建立为子节点。
(6) 对于第$i$个子节点，以$D_i$为训练集，以$A-\{A_g\}$为特征集，递归地调用步骤(1)~步骤(5)，得到子树$T_i$，返回$T_i$。
从以上生成步骤可以看出，C4.5算法与ID3算法的唯一区别就是选择的标准不同，而其他的步骤均一样。到此为止，我们就学习完了决策树中的ID3与C4.5生成算法。
8.3.5 特征划分#
在经过上述两节的介绍之后，相信读者对于如何通过ID3和C4.5算法构造一棵简单的决策树已经有了基本的了解。不过细心的读者可能会有这样一个疑问，那就是如何来处理连续型的特征变量。
从上面的示例数据集可以看出，工作、房子、学历这3个属性都属于离散型的特征变量（Discrete Variable），即每个特征的取值都属于某一个类别，而通常在实际建模过程中，更多的会是连续型的特征变量（Continuous Variable），例如年龄、身高等。因此，对于这种连续型的特征变量，其具体做法便是先对其进行排序处理，然后取所有连续两个值的均值来离散化整个连续型特征变量[3]。
假设现在某数据集中的一个特征维度为
$$ [0.5,0.2,0.8,0.9,1.2,2.1,3.2,4.5] $$则首先需要对其进行排序处理，排序后的结果为
$$ [0.2,0.5,0.8,0.9,1.2,2.1,3.2,4.5] $$接着计算所有连续两个值之间的平均值
$$ [0.35,0.65,0.85,1.05,1.65,2.65,3.85] $$这样，便得到了该特征离散化后的结果。最后在构造决策树时，只需使用平均值中离散化后的特征进行划分指标的计算。同时，值得一提的地方是目前sklearn在实际处理时，是把所有的特征均看作连续型变量在进行处理。
8.3.6 小结#
在本节中，我们首先回顾了决策树中几个重要的基本概念，并同时进行了相关示例计算，接着介绍了如何通过信息增益这一划分标准（ID3算法）来构造生成决策树，并以一个真实的例子进行了计算示例，然后介绍了通过引入信息增益比（C4.5算法）这一划分标准来解决ID3算法在生成决策树时所存在的弊端，最后介绍了在决策树生成时，如何处理连续型特征变量的一种常用方法。