一、C4.5算法介绍

C4.5算法是对ID3决策树算法的改进，之所以要改进ID3算法，主要有以下原因：$g(D,A)=H(D)-H(D|A)$，信息增益倾向于选择取值多的特征，当特征取值多时，D被划分为多个子数据集，每个子数据集中的样本数可能比较少，里面只包含单一类别样本的可能性就比较大，这样就会导致条件熵比较小，从而使得信息增益比较大，在极限情况下，特征A的取值特别多，以至于每个样本都有一个不同的取值，这样每个子数据集就只含有一个样本，每个子数据集的类别都是确定的。比如：以毫米为单位的发长特征。（本质上还是数据量不足）

改进思想：

1. 相对信息增益，即：信息增益率
2. 用信息增益率代替信息增益选择特征

分离信息：

1. 分离信息也是一种熵，按照特征取值计算概率，不是按照分类结果计算概率：

$SI(D,A)=-\sum_{i=1}^{n}{P_i}·log(P_i)=-\sum_{i=1}^{n}{\frac{D中特征A取第i个值的样本数}{D中的样本数}·log(\frac{D中特征A取第i个值的样本数}{D中的样本数})}$

信息增益率：

$g_r(D,A)=\frac{g(D,A)}{SI(D,A)}=\frac{H(D)-H(D|A)}{SI(D,A)}$

二、计算举例

三、C4.5算法改进

C4.5算法不仅通过引入信息增益率改进了决策树特征选取的方法，而且引入连续特征（允许特征取值连续）。

处理方法：

1. 按照特征A的取值对数据集D中的样本从小到大排序，第i个样本特征A的取值为$a_i$

$b_i=\frac{a_i+a_{i+1}}{2}$

2. 按照$b_i$值将D划分为2部分
3. 计算信息增益率
4. 最大的信息增益率为特征A的信息增益率

注意：特征取连续值时，并不是只能使用一次。

C4.5算法也存在不足，它倾向于取值不平衡的特征。改进方法为：从n个信息增益大的特征中选择信息增益率最大的特征，n的确定是根据信息增益大于平均值的特征。