C4.5 算法

在ID3 算法中若以“编号”这种属性作为属性划分，每个样本都有一个编号，将产生 17 个分支，纯度将达到最大，其信息增益为

$编号$ 但是这样得到的模型不具备泛化能力，无法预测新样本。

这是因为信息增益准则对于可取数目较多的属性有所偏好，不能公平地对待每个属性。由此引入了「增益率」（Gain Ratio），定义为

其中

称为属性的「固有值」。属性的可能取值越多，即越大，则的值通常会越大。因此上式加入，用以惩罚取值数目多的属性。

此时决策树结合了信息增益与增益率进行属性划分，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性。这种算法称为「C4.5 算法」。C4.5 算法即可以处理离散型描述属性，又可以处理连续性描述属性。

当处理离散型属性时，C4.5算法与 ID3 算法相同。当处理连续型属性时，C4.5算法需要先将连续型属性转换成离散型属性。

对于连续值属性，假设在某个结点上的样本数量为 total，则 C4.5 算法将进行如下操作

在某些情况下，可能需要确定多个最佳分割点。可以按照上述过程获得一次信息增益比最大的分割点、次大的分割点。

例题

age	income	student	credit_rating	buy_computer
32	high	no	fair	no
25	high	no	excellent	no
46	high	no	fair	yes
56	medium	no	fair	yes
60	low	yes	fair	yes
52	low	yes	excellent	no
42	low	yes	excellent	yes
36	medium	no	fair	no
23	low	yes	fair	yes
51	medium	yes	fair	yes
38	medium	yes	excellent	yes
43	medium	no	excellent	yes
41	high	yes	fair	yes
65	medium	no	excellent	no

解：

对年龄从小到大排序，序列为

然后对新的年龄序列生成分割点。由于样本数量为 14，因此可生成 13 个分割点。例如第一个分割点为，它可将数据集划分为年龄在的样本和的样本

然后选择最佳分割点，根据不同的分割点，计算对应的信息增益比，并从中选出具有最大信息增益比的分割点。

在有些情况下，可能需要确定多个最佳分割点。可以按上述过程获得依次信息增益比最大的分割点、次大的分割点等等。