决策树是一类常见的机器学习方法，利用决策树来进行决策的过程很像人类在面临决策问题时的一种思考模式。举个生活中的例子，假如我们要判断一个没剖开的西瓜是不是好瓜，有经验的瓜农可能会首先看看西瓜的颜色，再看看西瓜的根蒂形状，如果还没得出结论，可能还会敲打西瓜，听听是什么声音。上述过程用决策树表示如下。

那么我们的问题来了，给你一份带分类标签的数据，你怎么训练出一棵决策树。再次回顾我们是怎样利用决策树进行判定的，在决策过程中每提出的一个问题其实都是对某个属性的测试，然后沿着测试结果的分支继续测试，直到走到最终的分类结果。在每一步的测试中，我们都想通过这个测试就能得到最终的分类结果，一个极端的例子，如果能通过判断西瓜色泽是青绿色就得出是好瓜的结论最好。

所以我们的目标是尽可能进行少的属性测试就能得到分类结果，换句话说就是每次测试都选择最优的属性测试，最优的含义就是通过这个测试能把数据集中的样本结果尽多的确定。

这样问题就清晰了，在构建决策树的过程中就是每次都选择一个最优的属性。那么我们通过什么办法来确定一个属性是最优属性呢，下面就引入信息增益的概念。

首先什么是信息，信息能否度量？香农在他的著作《通信的数学原理》提出一个名词“信息熵”。信息熵是用来消除事件不确定性所需的信息量的度量，我们可以这么理解，一个事件越不确定，我们就需要越多的信息来确定它，它的信息熵就越大。比如我说明天会是世界末日，这个事件是真的还是假的，很难确定，所以它的信息熵很大。

回到我们的数据集上，如果我们的数据集的类别种类很多，我们要确定一个样本到底属于哪个类别，需要的信息量就越大，就表明这份数据集的信息熵就越大。数据集的信息熵计算公式如下：

其中D是数据集，y|是类别个数，Pk是第k类样本所占的比率。

前面我们说了，我们每次都是选择最优的属性进行测试，也就是利用数据样本在属性上的取值不同将数据集分为D1，D2，…，Dv，v为属性上不同值的个数，我们希望划分后的数据集的信息熵是较小的，也就是希望原数据集和划分后的数据集的信息熵的差值较大。这就是信息增益的含义，信息增益计算公式如下：

基于信息增益构建决策树的算法被称为ID3算法。但我们仔细想想，会发现信息增益有一个偏好，就是每次都倾向于选择可取值数目较多的属性，因为通常利用可取值数目较多的属性划分数据集后得到的信息增益较大。

但有时选择这个属性会带来不好的影响。举个简单的例子，在一个数据集中，假设每个数据样本都有唯一的ID，如果利用这个ID进行判断，当然能一步得出结论，但这并不是我们想要的，因为ID没有任何的实际含义，它只是一个数据样本的唯一标识。

为了解决这个问题，C4.5算法就在ID3算法的基础上进行了改进，C4.5算法对一个属性的信息增益利用属性的可取值数目进行了惩罚。C4.5算法利用增益率来选择最优属性，增益率的计算公式如下：

一般来说，属性a的可取值数目越多，IV(a)的值就越大。增益率就可以理解为在信息增益的基础对属性的可取值数目进行了惩罚。值得注意的一点是：C4.5算法并不是直接选择增益率最大的那个属性，而是先在候选属性中找出那些信息增益大于平均值的属性，再从这些属性中选择增益率最大的属性。

最后还有一个指标可以用来选择最优属性，那就