7.2 决策树（下）在线视频

C4.5算法也是决策树算法的一种

它是对ID3算法的改进

因为ID3算法在分裂属性的选择上

使用的是最大信息增益

这会造成倾向于选择数值较多的特征

例如考虑唯一标识符的属性

product_ID

因其每个值只有一个元组

在product_ID的划分

会产生元组总数个分区

且每个分区都是纯的

即该分区的元组属于同一个类

基于该划分对数据集D分类的

Info(D|product_ID)=0

则g(D|product_ID)最大

选择product_ID作为分裂属性

不是一个好的策略

属性取值最多的属性并不一定最优

再如上例中使用ID3算法构造的决策树

第一个分裂属性选择的是“体重范围”

很大程度是因为其数值较多

但在实际情况中

“体重范围”不一定是决定性属性

C4.5算法在构建决策树的时候

分类属性选择的是

具有最大信息增益率的特征

即对信息增益规范化

能够在一定程度上

避免由于特征值太分散而造成的误差

另外

ID3算法形成的决策树

对于每个属性均为离散值属性

如果是连续值属性需先离散化

而C4.5算法能够处理连续属性

C4.5算法过程如下

①如果所有实例都属于一个类别

则决策树是一个单结点树

否则执行步骤②

②从根结点开始选择

最大信息增益率的特征进行分裂

③依次类推

从上向下构建决策树

每次选择具有

最大信息增益率的特征进行分裂

选过的特征后面

就不能继续进行选择使用了

④重复步骤③

直至没有特征可以选择

或者分裂后的所有元组

属于同一类别时候停止构建

⑤决策树构建完成 进行预测

C4.5算法能够处理连续属性

根据连续属性值进行排序

用不同的值对数据集进行动态划分

把数据集分为两部分

一部分大于某值

一部分小于某值

然后根据划分进行信息增益计算

最大的那个值作为最后的划分

假设属性A是连续值

必须确定A的“最佳”分裂点

其中分裂点是A上的阈值

将A的值按递增序排序

每对相邻值的中点被看做可能的分裂点

当A具有n个值时

需要计算n-1个可能的划分

对于A的每个可能分裂点

计算信息增益

具有信息增益最大的点

选做A的分裂点split_point

产生两个分支

分别对应于A≤split_point

和A>split_point

数据集D被划分为两个分区

D1包含D中

A≤split_point的

类标号组成的子集

而D2包括

A>split_point元组

例 使用C4.5算法进行分类预测

使用上例训练数据和测试数据

使用C4.5算法构建决策树

然后进行分类预测

解

①首先计算按照每个特征

进行分裂的信息增益率

i.特征中“年龄”为连续型属性

C4.5算法可以解决ID3算法

无法处理连续属性的缺点

先将特征“年龄”的值进行升序排序

用每对相邻值的中值对数据集

进行动态划分（一部分大于中值

另一部分小于等于中值）

此例中“年龄”有15个值

有14个可能的分裂点

分别为24,26,28.5,34.5

40,42,44,45.5,46.5

54.5,62.5,64.5

66,67

其中中值为66的相邻值都是66

该中值划分无意义

根据不同的划分进行信息增益计算

能够使信息增益最大的划分

即为最后的划分策略

下面给出其中一个可能的分裂点

44的信息增益的计算式

其他可能分裂点的信息增益计算结果

如表所示

从表中可以看到

分裂点44的信息增益最大

即为最优划分点

选择此值作为分裂点

将“年龄”属性分为2组

（≤44岁和＞44岁）

ii. 计算各特征的分裂信息

根据计算公式

分别计算年龄、吸烟史、有无家族病史

和体重范围特征的分裂信息如下所示

iii.计算各特征的信息增益率

计算如下

选择信息增益率最大的特征

“有无家族病史”作为根结点的分类属性

将训练集Z划分为2个子集

Zˇ1和Zˇ2

对应的“有无家族病史”的取值

分别为“有”和“无”

在Zˇ1子集中的数据都属于同一类

不需要再继续分裂

在Zˇ2子集中的数据属于不同类

需要再继续分裂

对数据集Zˇ2进行分裂

其数据如表所示

根据Zˇ2计算其他属性的分裂信息

计算式如下

计算各属性的信息增益率

通过计算可知

属性“吸烟史”的信息增益率最大

选择“吸烟史”属性继续进行分裂

将训练集Zˇ2划分为3个子集

Zˇ21、Zˇ22和Zˇ23

对应的“吸烟史”的取值分别为

“无” “0-5年”以及“5年以上”

在这3个子集中的数据都各自属于同一类

所以不再分裂

决策树构建完毕

通过C4.5算法所构建的决策树

如图所示

C4.5算法构建的决策树高度为3层

而ID3算法构建的决策树高度为4层

可见C4.5算法构建的决策树

比ID3算法构建的决策树

在结构上更为高效

另外

C4.5算法并没有像ID3算法那样

选择多值属性“体重范围”

作为根结点的分类属性

在ID3算法构建的决策树中

根结点“体重范围”为“高”的分支子树

与C4.5算法构建的决策树相同

因此ID3算法将“体重范围”

作为根结点的分裂属性是多余的

当构建好决策树之后对测试数据进行预测

分别对编号1 2 3测试数据

进行预测可以得到

它们的类别分别“否” “否” “是”

正确率为100%

根据构建的决策树

可以提取分类规则如下

①IF “有无家族病史”=“有”

THEN 患病

②IF “有无家族病史”=“无”

AND “吸烟史”=“无”

THEN 没有患病

③IF “有无家族病史”=“无”

AND “吸烟史”=“0-5年”

THEN 没有患病

④IF “有无家族病史”=“无”

AND “吸烟史”=“5年以上”

THEN患病

决策树使用递归的方法

从上向下构建决策树

产生的决策树是

最大限度的拟合训练数据的

但是对测试数据进行预测的时候

可能不是很准确

即常说的过拟合

过拟合的原因主要有

1 样本问题

（1）样本里的噪声数据干扰过大

达到模型过分记住了噪声特征

反而忽略了真实的输入输出间的关系

（2）样本抽取错误

包括（但不限于）样本数量太少

抽样方法错误

抽样是没有足够正确

考虑业务场景或业务特点等

导致抽出的样本数据

不能有效足够代表业务逻辑或业务场景

（3）建模时

使用了样本中太多无关的输入变量

2. 构建决策树的方法问题

在决策树模型构建中使用的算法

对决策树的生长没有合理的限制和修剪

决策树的自由生长有可能

使得每个叶子结点里

只包含单纯的事件数据或非事件数据

这种决策树可以很好地拟合训练数据

但对于新的业务真实数据的效果却很差

主要解决方法

1 样本问题

合理 有效地抽样

用相对能够反映业务逻辑的

训练数据构建决策树

2 构建决策树的方法问题

主要方法是剪枝

即提前停止树的增长

或者对已经生成的树

按照一定的规则进行剪枝

常见的决策树剪枝操作分为

先剪枝和后剪枝

先剪枝就是在构建决策树的过程中

进行剪枝

当决策树高度达到最大高度

或达到某个结点的实例具有相同的特征向量

或达到某个结点的实例个数阈值

或达到信息增益阈值等条件

即停止决策树的生长

以ID3算法构建决策树为例

就是当信息增益达到预先设定的阈值时候

就不再进行分裂

直接将这个结点作为叶子结点

取叶子结点中出现频率最多的类别

作为此叶子结点的类标签

先剪枝方法相对简单

效率高

而且不需要生成整个决策树

适合于解决大规模问题

但要精确估计决策树生长的停止阈值

比较困难

高阈值可能导致过分简化的树

而低阈值可能使得树的简化较少

因此常用后剪枝

后剪枝就是决策树建好之后

再对整个树进行剪枝操作

具体方法就是计算每个内部的结点

剪枝前和剪枝后的损失函数

按照最小化损失函数的原则进行剪枝

即用叶子结点代替该分支结点

该叶子结点的类标号

为该结点子树中最频繁的类标记

或者保留此内部结点