决策树之ID3和C4.5原理与实战

各位客官大家好，欢迎来到月来客栈，我是掌柜空字符。

经过前面几个章节的介绍，我们已经学习过了3个分类算法模型，包括逻辑回归、K近邻和朴素贝叶斯。今天掌柜将开始介绍下一个分类算法模型决策树（Decision Tree）。

1 决策树的基本思想

一说到决策树其实很读者或多或少都已经使用过，只是自己还不知道罢了。例如最简单的决策树就是通过输入年龄，判读其是否为成年人，即if age >= 18 return True，想想自己是不是经常用到这样的语句?

1.1 冠军球队

关于什么是决策树，我们先来看这么一个例子。假如掌柜错过了某次世界杯比赛，赛后掌柜问一个知道比赛结果的人“哪支球队是冠军”？但是对方并不愿意直接说出结果，而是让掌柜自己猜，且每猜一次对方都要收一元钱才肯告诉掌柜是否猜对了。那现在的问题是要掏多少钱才能知道谁是冠军球队呢[1]？

现在我可以把球队从1到16编上号，然后提问：“冠军球队在1-8号中吗？”。假如对方告诉我猜对了，掌柜就会接着问：“冠军在1-4号中吗？”。假如对方告诉我猜错了，那么掌柜也就自然知道冠军在5-8号中。这样只需要4次，掌柜就能知道哪支球队是冠军。上述过程背后所隐藏着的其实就是决策树的基本思想，并且还可以用更为直观的图来展示上述的过程，如图8-1所示。

由此可以得出，决策树每一步的决策过程就是降低信息不确定性的过程，甚至还可以将这些决策看成是一个if-then的规则集合。如图8-1所示，冠军球队一开始有16种可能性，经过一次决策后变成了8种。这意味着每次决策都能得到更多确定的信息，而减少更多的不确定性。

不过现在的问题是，为什么要像图8-1这样来划分球队？对于熟悉足球的读者来说，这样的决策树似乎略显多余。因为事实上只有少数几支球队才有夺冠的希望，而大多数是没有的。因此，一种改进做法就是在一开始的时候就将几个热门的可能夺冠的球队分在一边，将剩余的放在另一边，这样就可以大大提高整个决策过程的效率。

例如最有可能夺冠的是1,2,3,4这4个球队，而其余球队夺冠的可能性远远小于这4个。那么一开始就可以将球队分成1-4和5-16。如果冠军是在1-4中，那么后面很快就能知道谁是冠军。退一万步，假如冠军真的是在5-16，那么接下来你同样可以按照类似的思路将剩余的球队划分成最有可能夺冠和最不可能夺冠这两个部分。这样也能快速的找出谁是冠军球队。

于是这时候可以发现，如何划分球队变成了建立这棵决策树的关键。如果存在一种划分，能够使得数据的“不确定性”减少得越多（谁不可能夺冠），也就意味着该划分能获取更多的信息，而我们也就更倾向于采取这样的划分。因此采用不同的划分就会得到不同的决策树。所以，现在的问题就变成了如何构建一棵“好”的决策树呢？要想回答这个问题，先来解决如何描述“信息”这个问题。

1.2 信息的度量

关于如何定量的来描述信息，几千年来都没有人给出很好的解答。直到1948年，香农在他著名的论文“通信的数学原理”中提出了信息熵（Information Entropy）的概念，这才解决了信息的度量问题，并且还量化出了信息的作用。

1) 信息熵

一条信息的信息量与其不确定性有着直接的关系。比如说，要搞清楚一件非常非常不确定的事，就需要了解大量的信息。相反，如果已经对某件事了解较多，则不需要太多的信息就能把它搞清楚。所以从这个角度来看可以认为，信息量就等于不确定性的多少。我们经常说，一句话包含有多少信息，其实就是指它不确定性的多与少。

于是，8.1.1节中第一种划分方式的不确定性（信息量）就等于“4块钱”，因为掌柜花4块钱就可以解决这个不确定性。当然，香农用的不是钱，而是用“比特”（Bit）这个概念来度量信息量，一个字节就是8比特。在上面的第一种情况中，“谁是冠军”这条消息的信息量就是4比特。那4比特是怎么计算来的呢？第二种情况的信息量又是多少呢？

香农指出，它的准确信息量应该是

其中$\log$$\log$表示以2为底的对数，$p_1,p_2,...,p_{16}$$p_1,p_2,...,p_{16}$分别是这16支球队夺冠的概率。香农把式$(8.1)$$(8.1)$的结果称为“信息熵（Entropy），一般用符号$\mathrm{H}$$\mathrm{H}$表示，单位是比特。由于在第一种情况中，默认条件是16支球队夺冠概率相同，因此对应的信息熵就是4比特。

对于任意一个随机变量$X$$X$（比如得冠军的球队），它的熵定义如下[2]

其中$\log$$\log$表示以2为底的对数 。

例如在二分类问题中：设$P(y=0)=p,P(y=1)=1-p,0\le p\le 1$$P(y=0)=p,P(y=1)=1-p,\;0\leq p\leq1$，那么此时的信息熵$H(y)$$H(y)$即为：

根据式还$(8.3)$$(8.3)$能画出其对应的函数图像，如图8-2所示。

从图8-2可以发现，当两种情况发生的概率均等（$p=1-p=0.5$$p=1-p=0.5$）时信息熵最大，也就是说此时的不确定性最大，要把这件事搞清楚所需要的信息量也就越大。并且这也很符合我们的常识，例如“明天下雨和不下雨的概率都是50%”，那么这一描述所存在的不确定性是最大的。

2) 条件熵

在谈条件熵（Condition Entropy）之前，我们先来看看信息的作用。一个事物（那只球队会得冠），其内部会存有随机性也就是不确定性，假定其为$U$$U$。从外部消除这个不确定性的唯一办法就是引入信息$I$$I$（我来猜，另一个人给我反馈）。并且需要引入的信息量取决于这个不确定性的大小，即$I>U$$I>U$才能完全消除这一不确定性。当$I<U$$I<U$时，外部信息可以消除一部分不确定性，也就是说新的不确定性$U^{\prime }=U-I$$U^{\prime}=U-I$。反之，如果没有信息的引入，那么任何人都无法消除原有的不确定性[1]。而所谓条件熵，说得简单点就是在给定某种条件（有用信息）$I$$I$下，事物$U$$U$的熵，即$H(U|I)$$H(U|I)$。

到此，对于条件熵相信读者朋友们在感性上已经有了一定的认识。至于具体的数学定义将在决策树生成部分进行介绍。

3) 信息增益

在8.1.1节中掌柜介绍到，若一种划分能使数据的“不确定性”减少得越多，也就意味着该种划分能获取更多的信息，而我们也就更倾向于采取这样的划分。也是就说，存在某个事物$I$$I$，当引入事物$I$$I$的信息后$U$$U$的熵变小了。而我们要选的就是那个最能使得$U$$U$的信息熵变小的$I$$I$，即需要得到最大的信息增益（Information Gain）

综上所述，采用不同的划分就会得到不同的决策树，而我们所希望得到的就是在每一次划分的时候都采取最优的方式，即局部最优解。这样每一步划分都能够使得当前的信息增益达到最大。因此可以得出，构建决策树的核心思想就是每次划分时，要选择使得信息增益达到最大时的划分方式，以此来递归构建决策树。

1.3 小结

在本节中，掌柜首先介绍了决策树的核心思想，即决策树的本质就是降低信息不确定性的过程；然后总结出构建一棵决策树的关键在于找到一种合适的划分，使得信息的“不确定性”能够降低得最多；最后掌柜介绍了如何以量化的方式来对信息进行度量。

2 决策树的生成之ID3与C4.5

在正式介绍决策树的生成算法前，掌柜先将8.1.1节中介绍的几个概念重新梳理一下；并且同时再通过一个例子来熟悉一下计算过程，以便于后续更好的理解决策树的生成算法。

2.1 基本概念与定义

1) 信息熵

设$X$$X$是一个取值有限的离散型随机变量（例如上一小节中可能夺冠的16只球队），其概率分布为$P(X=x_i)=p_i,i=1,2,...,n$$P(X=x_i)=p_i,\;i=1,2,...,n$（每个球队可能夺冠的概率），则随机变量$X$$X$的信息熵定义为

其中，若$p_i=0$$p_i=0$，则定义$0\log 0=0$$0\log0=0$；且通常$\log$$\log$取2为底或$e$$e$为底时，其熵的单位分别称为比特（Bit）或纳特（Nat）。如无特殊说明，默认以2为底。

2) 条件熵

设有随机变量$(X,Y)$$(X,Y)$，其联合概率分布分$P(X=x_i,Y=y_i)=p_{ij}$$P(X={{x}_{i}},Y={{y}_{i}})={{p}_{ij}}$，其中$i=1,2,...,n$$\ i=1,2,...,n$，$P(X=x_i,Y=y_i)=p_{ij},$$P(X=x_i,Y=y_i)=p_{ij},$ $i=1,2,...,n;$$i=1,2,...,n;$$j=1,2,...,m$$j=1,2,...,m$；条件熵$H(Y|X)$$H(Y|X)$表示在已知随机变量$X$$X$的条件下，随机变量$Y$$Y$的不确定性，其定义为

其中，$p_i=P(X=x_i),i=1,2,...,n$$p_i=P(X=x_i),i=1,2,...,n$

同时，当信息熵和条件熵中的概率由样本数据估计（特别是极大似然估计）得到时，所对应的信息熵与条件熵分别称之为经验熵（Empirical Entropy）和经验条件熵（Empirical Conditional Entropy）。这里暂时看不懂没关系，请结合后续计算示例。

3) 信息增益

从8.1.1节的内容可知，所谓信息增益指的就是事物$U$$U$的信息熵$H(U)$$H(U)$，在引入外部信息$I$$I$后的变化量$H(U)-H(U|I)$$H(U)-H(U|I)$。因此，可以将特征$A$$A$对训练数据集$D$$D$的信息增益$d(D,A)$$d(D,A)$定义为集合$D$$D$信息熵$H(D)$$H(D)$与特征$A$$A$给定条件下$D$$D$的条件熵$H(D|A)$$H(D|A)$之差，即

定义：设训练集为$D$$D$，$\left|D\right|$$\left| D \right|$表示所有训练样本总数；同时$D$$D$有$K$$K$个类别$C_k,k=1,2,...,K;|C_k|$$C_k,k=1,2,...,K;\;|C_k|$为属于类$C_k$$C_k$的样本总数，即${\sum }_{k=1}^K|C_k|=|D|$$\sum\nolimits_{k=1}^{K}{|{{C}_{k}}|}=|D|$；设特征$A$$A$有$n$$n$个不同的取值$a_1,a_2,...,a_n$${a_1,a_2,...,a_n}$，根据特征$A$$A$的取值将$D$$D$划分为$n$$n$个子集$D_1,D_2,...,D_n$$D_1,D_2,...,D_n$，$|D_i|$$|D_i|$为子集$D_i$$D_i$中的样本个数，即${\sum }_{i=1}^n|D_i|=|D|$$\sum\nolimits_{i=1}^{n}{|{{D}_{i}}|=|D|}$；同时记子集$D_i$$D_i$中，属于类$C_k$$C_k$的样本集合为$D_{ik}$$D_{ik}$，即$D_{ik}=D_i\bigcap C_k$${{D}_{ik}}={{D}_{i}}\bigcap {{C}_{k}}$，$|D_{ik}|$$|D_{ik}|$为$D_{ik}$$D_{ik}$的样本个数。此时如下定义[2]

• 数据集$D$$D$的经验熵$H(D)$$H(D)$为

  $$H(D)=-\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}(8.8)$$

  从式$(8.8)$$(8.8)$可以看出，它计算的是“任意样本属于其中一个类别”这句话所包含的信息量。

• 数据集$D$$D$在特征值$A$$A$下的经验条件熵$H(D|A)$$H(D|A)$为

  $$H(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{|D_i|}{\log }_2\frac{|D_{ik}|}{|D_i|}(8.9)$$

  从式$(8.9)$$(8.9)$可以看出，它计算的是特征$A$$A$在各个取值条件下“任意样本属于其中一个类别”这句话所包含的信息量。

• 信息增益为

  $$g(D,A)=H(D)-H(D|A)(8.10)$$

2.2 计算示例

如果仅看上面的公式肯定会不那么容易理解，下面掌柜再进行举例说明（将上面的公式同下面的计算过程对比看会更容易理解）。下表8-1同样是6.1.3节中用过的一个信用卡审批数据集，其一共包含15个样本和3个特征维度。其中特征$X^{(1)}\in A_1=\{0,1\}$$X^{(1)}\in A_1=\{0,1\}$表示有无工作，特征$X^{(2)}\in A_2=\{0,1\}$$X^{(2)}\in A_2=\{0,1\}$表示是否有房，特征$X^{(3)}\in A_3=\{D,S,T\}$${{X}^{(3)}}\in {{A}_{3}}=\{D,S,T\}$表示学历等级，$Y\in C=\{0,1\}$$Y\in C=\{0,1\}$表示是否审批通过的类标记。

1) 计算信息熵

根据式$(8.8)$$(8.8)$可得

2) 计算条件熵

由表8-1可知，数据集有3个特征（工作、房子、学历）$A_1,A_2,A_3$$A_1,A_2,A_3$；接下来根据式来计算$D$$D$分别在3个特征取值条件下的条件熵$H(D|A_i)$$H(D|A_i)$。

• 已知外部信息“工作”的情况下有

  $$\begin{array}{rl}& H(D|A_1)=[\frac{7}{15}H(D_1)+\frac{8}{15}H(D_2)]\\ & =-\frac{7}{15}(\frac{3}{7}{\log }_2\frac{3}{7}+\frac{4}{7}{\log }_2\frac{4}{7})-\frac{8}{15}(\frac{7}{8}{\log }_2\frac{7}{8}+\frac{1}{8}{\log }_2\frac{1}{8})\approx 0.75\end{array}(8.12)$$

  式$(8.12)$$(8.12)$中，$D_1,D_2$$D_1,D_2$分别是$A_1$$A_1$取值为“无工作”和“有工作”时，训练样本划分后对应的子集。

• 已知外部信息“房子”的情况下有

  $$\begin{array}{rl}& H(D|A_2)=[\frac{8}{15}H(D_1)+\frac{7}{15}H(D_2)]\\ & =-\frac{8}{15}(\frac{4}{8}{\log }_2\frac{4}{8}+\frac{4}{8}{\log }_2\frac{4}{8})-\frac{7}{15}(\frac{1}{7}{\log }_2\frac{1}{7}+\frac{6}{7}{\log }_2\frac{6}{7})\approx 0.81\end{array}(8.13)$$

  式$(8,13)$$(8,13)$中，$D_1,D_2$$D_1,D_2$分别是$A_2$$A_2$取值为“无房”和“有房”时，训练样本划分后对应的子集。

• 已知外部信息“学历”的情况下有

  $$\begin{array}{rl}& H(D|A_3)=[\frac{3}{15}H(D_1)+\frac{4}{15}H(D_2)+\frac{8}{15}H(D_3)]\\ & =-\frac{3}{15}(\frac{1}{3}{\log }_2\frac{1}{3}+\frac{2}{3}{\log }_2\frac{2}{3})-\frac{4}{15}(\frac{1}{4}{\log }_2\frac{1}{4}+\frac{3}{4}{\log }_2\frac{3}{4})\\ & -\frac{8}{15}(\frac{3}{8}{\log }_2\frac{3}{8}+\frac{5}{8}{\log }_2\frac{5}{8})\approx 0.91\end{array}(8.14)$$

  式$(8.14)$$(8.14)$中，$D_1,D_2,D_3$${{D}_{1}},{{D}_{2}},{{D}_{3}}$分别是$A_3$${{A}_{3}}$取值为“D”、“S”和“T”时，训练样本划分后对应的子集。

3) 计算信息增益

根据上面的计算结果便可以计算得到各特征划分下的信息增益为

到目前为止，我们已经知道了在生成决策树的过程中所需要计算的关键步骤信息增益，接下来，掌柜就开始正式介绍如何生成一棵决策树。

2.3 ID3生成算法

在8.1节的末尾掌柜总结到，构建决策树的核心思想就是：每次划分时，要选择使得信息增益最大的划分方式，以此来递归构建决策树。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征没有分类能力。因此，对于决策树生成的一个关键步骤就是选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率，而通常对于特征选择的准则就是8.1节谈到的信息增益。

ID3（Interactive Dichotomizer-3）算法的核心思想是在选择决策树的各个节点时，采用信息增益来作为特征选择的标准，从而递归地构建决策树。其过程可以概括为，从根节点开始计算所有可能划分情况下的信息增益；然后选择信息增益最大的特征作为划分特征，由该特征的不同取值建立子节点；最后对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有可以选择为止。例如根据8.2.2节最后的计算结果可知，首先应该将数据样本以特征$A_1$$A_1$有无工作）作为划分方式对数据集进行第一次划分。下面开始介绍通过ID3来生成决策树的步骤及示例。

• 生成步骤

  输入：训练数据集$D$$D$，特征集$A$$A$，阈值$\epsilon$$\varepsilon$;

  输出：决策树[2]。

  (1) 若$D$$D$中所有样本属于同一类$C_k$$C_k$（即此时只有一个类别）则T为单节点树，将$C_k$$C_k$作为该节点的类标记，返回T;

  (2) 若$A=\mathrm{\varnothing }$$A=\emptyset$，则T为单节点树，并将$D$$D$中样本数最多的类$C_k$$C_k$作为该节点的类标记，并返回T；

  (3) 否则，计算$A$$A$中各特征对$D$$D$的信息增益，选择信息增益最大的特征$A_g$$A_g$；

  (4) 如果$A_g$$A_g$的信息增益小于阈值$\epsilon$$\varepsilon$，则置T为单节点树，并将$D$$D$中样本数最多的类$C_k$$C_k$作为该节点的类标记，返回T；

  (5) 否则，对$A_g$$A_g$的每一个可能值$a_i$$a_i$，以$A_g=a_i$$A_g=a_i$将$D$$D$分割为若干非空子集，并建立为子节点；

  (6) 对于第$i$$i$个子节点，以$D_i$$D_i$为训练集，以$A-\{A_g\}$$A-\{A_g\}$为特征集，递归地调用(1)-(5)，得到子树$T_i$$T_i$，返回$T_i$$T_i$。

• 生成示例

  下面就用ID3算法来对表8-1中的数据样本进行决策树生成示例。易知该数据集不满足步骤(1)(2)中的条件，所以开始执行步骤(3)。同时，根据8.2.2小节最后的计算结果可知，对于特征$A_1,A_2,A_3$$A_1,A_2,A_3$来说，在$A_1$$A_1$条件下信息增益最大，所以应该选择特征$A_1$$A_1$作为决策树的根节点。

  由于本例中未设置阈值，所以接着执行步骤(5)按照$A_1$$A_1$的取值将训练集$D$$D$划分为两个子集$D_1,D_2$$D_1,D_2$，如表8-2所示。

  表8-2 第一次划分表

  

  接着开始执行步骤(6)，由于$D_1,D_2$$D_1,D_2$均不满足步骤(1)(2)中的条件，所以两部分需要分别继续执行后续步骤，此时生成的决策树如图8-3所示。

  

  图8-3 第一次划分

  此时，对于子集$D_1$$D_1$来说，需要从特征$A-\{A_g\}$$A-\{A_g\}$中即$A_2,A_3$$A_2,A_3$中选择新的特征，并计算信息增益。

  1) 计算信息熵$H(D_1)$$H(D_1)$

  $$H(D_1)=-(\frac{3}{7}{\log }_2\frac{3}{7}+\frac{4}{7}{\log }_2\frac{4}{7})\approx 0.985(8.16)$$

  2) 计算条件熵

  $$H(D_1|A_2)=-\frac{3}{7}(\frac{3}{3}{\log }_2\frac{3}{3}+0)-\frac{4}{7}(\frac{1}{4}{\log }_2\frac{1}{4}+\frac{3}{4}{\log }_2\frac{3}{4})\approx 0.464(8.17)$$
  $$H(D_1|A_3)=-\frac{1}{7}(0+0)-\frac{2}{7}(0+0)-\frac{4}{7}(\frac{3}{4}{\log }_2\frac{3}{4}+\frac{1}{4}{\log }_2\frac{1}{4})\approx 0.464(8.18)$$

  根据式$(8.17)$$(8.17)$和$(8.18)$$(8.18)$的结果可知，对于子集$D_1$$D_1$来说，无论其采用$A_2,A_3$$A_2,A_3$中的哪一个特征进行划分，最后计算得到的信息增益都是相等的，所以这里不妨就以特征$A_2$$A_2$进行划分。

  同理，对于子集$D_2$${{D}_{2}}$来说，也需要从特征$A-\{A_g\}$$A-\{A_g\}$中即$A_2,A_3$$A_2,A_3$中选择新的特征，并计算信息增益。

  1) 计算信息熵

  $$H(D_2)=-(\frac{1}{8}{\log }_2\frac{1}{8}+\frac{7}{8}{\log }_2\frac{7}{8})\approx 0.544(8.19)$$

  2) 计算条件熵

  $$H(D_2|A_2)=-\frac{5}{8}(\frac{1}{5}{\log }_2\frac{1}{5}+\frac{4}{5}{\log }_2\frac{4}{5})-\frac{3}{8}(0+0)\approx 0.451(8.20)$$
  $$H(D_2|A_3)=-\frac{2}{8}(0+0)-\frac{2}{8}(\frac{1}{2}{\log }_2\frac{1}{2}+\frac{1}{2}{\log }_2\frac{1}{2})-\frac{4}{8}(0+0)=0.25(8.21)$$

  3) 信息增益

  $$\begin{array}{rl}& g(D_2|A_2)=0.544-0.451=0.093\\ & g(D_2|A_3)=0.544-0.25=0.294\end{array}(8.22)$$

  根据式$(8.22)$$(8.22)$的计算结果可知，对于子集$D_2$$D_2$来说，采用特征$A_3$$A_3$来对其进行划分时所产生的信息增益最大，因此应该选择特征$A_3$$A_3$来作为子集$D_2$${{D}_{2}}$的根节点。

  到此，根据上述计算过程，便可以得到第二次划分后的结果，如表8-3所示。

  表8-3 第二次划分表

  

  从表8-3中的结果可知，$D_{11},D_{21},D_{23}$$D_{11},D_{21},D_{23}$这三个子集中样本均只有一个类别，既满足生成步骤中的第(1)步，故此时可以得到第二次划分后的决策树，如图8-4所示。

  

  图8-4 第二次划分

  由于子集$D_{12},D_{22}$$D_{12},D_{22}$均不满足终止条件(2)(4)，且此时两个子集中均只有一个特征可以选择，所以并不需要再进行比较直接划分即可得，如表8-4所示。

  表8-4 第三次划分表

  

  根据表8-4中的结果可知，子集$D_{121}$$D_{121}$满足生成步骤中的第(1)步，故此时可以得到第三次划分后的决策树，如图8-5所示。

  

  图8-5 第三次划分

  此时，由于子集$D_{122},D_{221}$$D_{122},D_{221}$满足生成步骤中第 (2)步的终止条件，即再无特征可以进行划分，需要选择样本数最多的类别作为该节点的类别进行返回。但巧合的是子集$D_{122},D_{221}$$D_{122},D_{221}$中不同类别均只有一个样本，因此随机选择一个类别即可。不过在实际过程中很少会出现这样的情况，因为一般当节点的样本数小于某个阈值时也会停止继续划分。这样便能得到最终生成的决策树，如图8-6所示。

  

如上就是通过ID3算法生成整个决策树的详细过程。根据生成步骤可以发现，如果单纯以$g(D,A)$$g(D,A)$作为标准的话，会存在模型倾向于选择取值较多的特征进行划分（比如上面的$A_2$$A_2$）。虽然在上面这个例子中不存在，但是我们仍可以从直观上理解为什么ID3会倾向于选取特征值取值较多的特征。由于$g(D,A)$$g(D,A)$的直观意义是$D$$D$被$A$$A$划分后不确定性的减少量，因此可想而知当$A$$A$的取值情况越多，那么$D$$D$会被划分得到的子集就越多，于是其不确定性自然会减少得越多，从而ID3算法会倾向于选择取值较多的特征进行划分。可以想象，在这样的情况下最终得到的决策树将会是一颗很胖很矮的决策树，进而导致最后生成的决策树容易出现过拟合现象。

2.4 C4.5生成算法

为了解决ID3算法的弊端，进而产生了C4.5算法。C4.5算法与ID3算法相似，不同之处仅在于C4.5算法在选择特征的时候采用了信息增益比作为标准，即选择信息增益比最大的特征作为当前样本集合的根节点。具体为，特征$A$$A$对训练集$D$$D$的信息增益比$g_R(D,A)$$g_R(D,A)$定义为其信息增益$g(D,A)$$g(D,A)$与其训练集$D$$D$关于特征$A$$A$的信息熵$H_A(D)$$H_A(D)$之比，即

其中，$H_A(D)=-{\displaystyle \sum _{i=1}^n\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}}$$H_A(D)=-\displaystyle\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2{\frac{|D_i|}{|D|}}$，$n$$n$是特征$A$$A$取值的个数。

因此，8.2.3节的例子中，对于选取根节点时其增益比计算如下：

1. 计算得到信息增益

2. 计算各特征的信息熵