7.2 决策树（上）在线视频

决策树算法自20世纪60年代提出以来

被广泛应用在规则提取

预测 分类等领域

自从Quinlan于1986年

提出ID3算法以后

决策树算法也被广泛应用到机器学习领域

例如

可以根据历史数据使用决策树做分类预测

决策树算法主要分为分类和预测两个方面

这里主要介绍在分类方面的应用

决策树算法的基础是二叉树

如图所示

但不是所有的决策树都是二叉树

还有可能是多叉树

决策树是一个自上而下的

由结点和有向边组成的树

其中圆形结点代表的是内部结点

（根结点和父结点）

每个内部结点表示在一个属性上的测试

每个分支代表一个测试输出

矩形代表叶结点

每个叶结点代表一种类别

也就是决策树的输出类别

决策树的向下分裂

采用的是if-then规则

简单来说

就是当条件满足分裂结点的某一种情况时

就朝着满足条件的那个方向向下生长

直到到达叶子结点

也就是类别

决策树分类器的本质

是利用训练数据构造一棵决策树

然后用这棵决策树

所提炼出来的规则进行预测

决策树的算法过程大体分为两步

首先利用训练数据构造决策树

然后利用构造的决策树进行预测

（1）构造决策树

决策树的构造是

采用自上而下递归方式贪心构造

也就是没有回溯

训练数据规模随着决策树的构造

会变得越来越小

这里需要注意的是

通常在构造决策树的过程中

已经使用过的作为分裂属性的特征

就不能再继续使用了

用自然语言描述决策树构造过程如下

①输入数据

主要包括训练集的特征和类标号

②选取一个属性

作为根结点的分裂属性进行分裂

③对于分裂的每个分支

如果已经属于同一类就不再分了

如果不是同一类

依次选取不同的特征

作为分裂属性进行分裂

同时删除已经选过的分裂属性

④不断的重复第三步

直到到达叶子结点

也就是决策树的最后一层

此时这个结点下的数据都属于一类了

⑤最后得到每个叶子结点对应的类标签

以及到达这个叶子结点的路径

（2）决策树的预测

得到由训练数据构造的决策树以后

就可以进行预测了

当待预测的数据输入决策树的时候

根据分裂属性以及分裂规则进行分裂

最后即可确定所属的类别

构造决策树过程中的关键问题是

如何确定分裂结点的分裂属性

根据分裂属性的选取标准的不同

决策树算法可以分为ID3 C4.5

下面将分别介绍这两种算法

设A是分裂属性

根据训练数据

A具有n个不同值

{aˇ1,aˇ2,…,aˇn}

选取A作为分裂属性进行分裂时

有如下三种情况

①A是离散值

对A的每个值aˇj创建一个分支

分区Dˇj是D中A上

取值为aˇj的类标号元组的子集

如图（a）所示

②A是连续的

产生两个分支

分别对应于A≤split_point

和A>split_point

其中split_point是分裂点

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

D1包含D中

A≤split_point

的类标号组成的子集

而D2包括其他元组

如图（b）所示

③A是离散值且必须产生二叉树

（由属性选择度量或所使用的算法指出）

结点的判定条件为“A∈SˇA?”

其中SA是A的分裂子集

根据A的值产生两个分支

左分支标记为yes

使得D1对应于D中

满足判定条件的类标记元组的子集

右分支标记为no

使得D2对应于D中

不满足判定条件的类标记元组的子集

如图（c）所示

构造出决策树后

可以由决策树提取分类规则

根据分类规则也可以预测新数据的类标号

决策树所表示的分类知识

可用if then形式表示

对从根到树叶的每条路径创建一个规则

沿着给定路径上的每个属性-值

对形成规则前件

（即“if”部分）的一个合取项

叶节点包含类预测

形成规则后键（即“then”部分）

if then规则易于理解

特别是当给定的树很大时

不同的是分裂结点的特征选择的标准

该算法在分裂结点处

将信息增益作为分裂准则进行特征选择

递归的地构建决策树

ID3算法的步骤如下

①输入数据

主要包括训练集的特征和类标号

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

则决策树是一个单结点树

否则执行③

③计算训练数据中每个特征的信息增益

④从根结点开始

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

依次类推

从上向下构建决策树

每次选择具有

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

选过的特征后面

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

⑤重复步骤④

直到没有特征可以选择

或者分裂后的所有元组

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

⑥决策树构建完成

进行预测

例 使用ID3算法进行分类预测

如下面两个表为训练数据和测试数据

其中“患病与否”是类标记

使用ID3算法

构建决策树然后进行分类预测

解

①连续型数据的离散化

ID3算法不能直接处理连续型数据

只有通过离散化

将连续型数据转化成

离散型数据再进行处理

此例采用等宽分箱法

对连续型特征“年龄”离散化

设定区域范围（设箱子数为3

箱子宽度为（68-23）/3=15）

分箱结果为

箱1

23 25 27 30

箱2

39 41 43 45 46 47

箱3

62 63 66 66 68

对特征“年龄”进行分箱

如图所示

离散化后训练数据集此表所示

可以看到

特征“年龄”的连续型数据离散化

②根据训练数据构造ID3算法的决策树

其中Z代表训练集

A、B、C、D分别代表特征

“年龄” “吸烟史”

“有无家族病史” “体重范围”

按照每个特征计算其分裂的信息增益

选择信息增益最大特征“体重范围”

作为根结点的分裂属性

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

Zˇ1 Zˇ2

Zˇ3 Zˇ4 和Zˇ5

对应的“体重范围”取值分别为

“低” “较低”

“中” “较高” “高”

由于Zˇ2 Zˇ3

和Zˇ4只有一类数据

所以它们各自成为一个叶结点

三个结点的类标签分别为

“否” “否” “是”

③对于Zˇ1继续进行分裂

选择剩余特征中信息增益最大的

作为分裂属性

选择信息增益最大特征

作为Zˇ1结点的分裂属性

由于三个属性的信息增益相同

随机挑选一个作为分裂属性

此处选取“有无家族病史”作为分裂属性

它将数据集Zˇ1分成2个子集

Zˇ21和Zˇ22

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

分别为“有”和“无”

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

于是就不需要再继续分裂

④对于Zˇ5继续进行分裂

选择剩余特征中信息增益最大的

作为分裂属性

选择信息增益最大特征“有无家族病史”

作为Zˇ5结点的分裂属性

将数据集Zˇ5分成2个子集

Zˇ51和Zˇ52

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

分别为“有”和“无”

“有”对应的Zˇ51中的数据

都属于同一类

不需要再继续分裂

“无”对应的Zˇ52中的数据

属于不同类

需要对其进行分裂

⑤对于Zˇ52继续进行分裂

选择剩余特征中信息增益最大的

作为分裂属性

由于两个属性的信息增益相同

随机挑选一个作为分裂属性

此处选取“吸烟史”

作为Zˇ52结点的分裂属性

将数据集Zˇ52分成2个子集

Zˇ521和Zˇ522

对应的“吸烟史”的取值

分别为“无”和“5年以上”

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

于是就不需要再继续分裂

决策树构造完毕

利用ID3算法构建的决策树如图所示

当构建好决策树之后

就可以对测试数据进行预测了

分别对编号1 2 3进行预测可以得到

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

正确率为100%

根据构建的决策树

可以提取分类规则如下

决策树的每一个分支

从根结点到叶结点的路径

构成一条关联规则

路径上的不同分支结点之间是与的关系

构成了关联规则的前件

叶洁点构成关联规则的后件

例如第一条路径生成的关联规则为

①IF “体重范围”=“低”

AND “有无家族病史”=“有”

THEN 患病

依次可以得到如下关联规则

②IF “体重范围”=“低”

AND “有无家族病史”=“无”

THEN 没有患病

③IF “体重范围”=“较低”

THEN 没有患病

④IF “体重范围”=“中”

THEN 没有患病

⑤IF “体重范围”=“较高”

THEN 患病

⑥IF “体重范围”=“高”

AND “有无家族病史”=“有”

THEN 患病

⑦IF “体重范围”=“高”

AND “有无家族病史”=“无”

AND “吸烟史”=“无”

THEN 没有患病

⑧IF “体重范围”=“高”

AND “有无家族病史”=“无”

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

THEN 患病