决策树之二-ID3与C4.5

决策树生成的过程是一个树的先根序遍历。在每个内部节点上选择一种特征属性，根据特征属性所有可能的取值种类K，把样本划分为K个集合，我们期望的是划分后各个子集合中的样本”不纯度“尽量低，也就是每个子集合中尽量是同一种类别的样本。那么我们既然希望划分之后结点的“不纯度”越来越低，那么如何度量不纯度呢？

ID3 算法度量“不纯度”的尺度是信息熵，分次分类让各个子树的加权信息熵更低。其实也就是选择一个是信息增益最大的特征属性。那么信息增益又是什么概念呢？接下来要回顾几个概念：信息熵、条件熵和信息增益。

信息熵、条件熵和信息增益

信息熵定义： 假设随机变量$X$的可能取值有$x_1,x_2,…,x_n$，对于每一个可能的取值$x_i$，其概率为 $P(X=x_i)，随机变量$X$的熵$H(X)$计算公式如下：

\[H(X) = -\sum_{i=1}^{n}P(X=x_i)\log P(X=x_i)\]

熵的定义是用来衡量随机变量不确定性大小的。熵越大说明随机变量不确定性越大。

条件熵定义： 假设随机变量$X$的可能取值有$x_1,x_2,…,x_m$,假设随机变量$Y$的可能取值有$y_1,y_2,…,x_n$，对于(X,Y)每一个可能的取值$(x_i,y_j)$，其概率为 $P(X=x_i,Y=y_j)$，那么以$X$为的条件变量的条件熵$H(Y

X)$计算公式如下：

\[H(Y|X) = -\sum_{i=1}^{m}P(X=x_i)\sum_{j=1}^{n}P(Y=y_j|X=x_i)\log P(Y=y_j|X=x_i)\]

可以看到条件熵实际是一个随机变量在另外一个随机变量取值条件下信息熵的加权平均值。

信息增益定义： ：信息增益是熵和条件熵的差：

\[IG(X,Y)=H(X) - H(X|Y)\]

怎么理解信息增益呢？其实就是我已知一个随机变量Y后，目标随机变量X的不确定性下降的程度。怎么理解呢？比如说是否阴天和是否下雨是两个随机变量，假设阴天必然下雨，否则必然不下雨。那么我们知道了是否阴天后，那么能推理出来是否下雨，所以是否阴天这个变量对于是否下雨这个变量来说的信息增益很大，因为已知是否阴天后是否下雨成为了必然事件，随机性为0。

ID3 算法

ID3 特征属性选择

那么我们现在也很好理解了，在决策树算法中，我们的关键就是每次选择一个特征，特征有多个，那么到底按照什么标准来选择哪一个特征。

这个问题就可以用信息增益来度量。如果选择一个特征后，信息增益最大（信息不确定性减少的程度最大），那么我们就选取这个特征。可以很简单写一个递归算法来实现这个过程~，其实就是一个先根序遍历！！

ID3 决策树生成

ID3算法的核心是根据信息增益最大的准则，递归地构造决策树；算法流程如下：

如果节点满足停止分裂条件（所有记录属同一类别 or 最大信息增益小于阈值），将其置为叶子节点；

选择信息增益最大的特征进行分裂；

重复步骤1-2，直至分类完成。

那么是不是大功告成了呢？结果是：不是的！

我们从上面求解信息增益的公式中，其实可以看出，信息增益准则其实是对可取值数目较多的属性有所偏好！也就是说一个特征属性的取值可能越多，越容易被选为分裂特征属性。举个直观的例子：

假如我们把数据集中的每个样本赋予一个“编号”，这个“编号”也作为一个候选划分属性。我们可以算出“编号”的信息增益是约等于1！因为每一个样本的编号都是不同的（由于编号独特唯一，条件熵为0了，每一个结点中只有一类，纯度非常高啊），也就是说，来了一个预测样本，你只要告诉我编号，其它特征就没有用了，这样生成的决策树显然不具有泛化能力。

因此 ID3 算法是很容易过拟合的。

C4.5 算法

C4.5 特征属性选择

C4.5算法流程与ID3相类似，只不过将信息增益改为信息增益比。信息增益比的公式如下

\[GainRatio(D,a)=\frac{Gain(D, a)}{IV(a)}\]

其中 Gain(D, a) 这一项表示当前节点属性 a 的信息增益，IV(a)表示当前节点的所有子节点样本占比的信息熵。

信息增益在前面分析了并不是很好，因为其对取值多的特征有所偏好。IV(a)越大隐含着特征取值较多，以它作为分母这样可以避免信息增益的缺点。

那么信息增益率就是完美无瑕的吗？当然不是，有了这个分母之后，我们可以看到增益率准则其实对可取类别数目较少的特征有所偏好！毕竟分母越小，整体越大。

于是C4.5算法不直接选择增益率最大的候选划分属性，候选划分属性中找出信息增益高于平均水平的属性（这样保证了大部分好的的特征），再从中选择增益率最高的（又保证了不会出现编号特征这种极端的情况）希望对大家有帮助~

决策树剪枝

生成的决策树对训练数据会有很好的分类效果，却可能对未知数据的预测不准确，即决策树模型发生过拟合（overfitting）——训练误差（training error）很小、泛化误差（generalization error，亦可看作为test error）较大。下图给出训练误差、测试误差（test error）随决策树节点数的变化情况：

可以观察到，当节点数较小时，训练误差与测试误差均较大，即发生了欠拟合（underfitting）。当节点数较大时，训练误差较小，测试误差却很大，即发生了过拟合。只有当节点数适中是，训练误差居中，测试误差较小；对训练数据有较好的拟合，同时对未知数据有很好的分类准确率。

发生过拟合的根本原因是分类模型过于复杂，可能的原因如下：

训练数据集中有噪音样本点，对训练数据拟合的同时也对噪音进行拟合，从而影响了分类的效果；
决策树的叶子节点中缺乏有分类价值的样本记录，也就是说此叶子节点应被剪掉。

为了解决过拟合，C4.5通过剪枝以减少模型的复杂度。通过极小化决策树的整体损失函数（loss function）或代价函数（cost function）来实现，决策树T的损失函数为：

\[L_{\alpha}(T)=C(T)+\alpha|T|\]

其中，$C(T)$表示决策树的训练误差，$\alpha$为调节参数，$

$为模型的复杂度。当模型越复杂时，训练的误差就越小。上述定义的损失正好做了两者之间的权衡。

如果剪枝后损失函数减少了，即说明这是有效剪枝。具体剪枝算法可以由动态规划等来实现。

决策树之二-ID3与C4.5