文档介绍：
ID3算法
知识结构
决策树基础
信息论基础
2020/12/24
1
决策树信息论C45算法
决策树基础
女孩家长
安排相亲
女孩
不厌其烦
女孩
提出决策树
父母筛选
候选男士
2020/12/24
2
决策树信息论C45算法
决策树基础
有向无环 二叉/多叉树
父节点：没有子节点的节点
内部节点：有父节点、子节点的节点
叶节点：有父节点没有子节点的节点
父节点
内部节点
叶节点
分割属性+判断规则
类别标识
2020/12/24
3
决策树信息论C45算法
决策树基础
父节点
内部节点
叶节点
（类别标识）
（分割属性+判断规则）
2020/12/24
4
决策树信息论C45算法
决策树基础
训练集：数据的集合，用于生成树（模型）
测试集：用于测试树（模型）的性能
决策树作用：
通过训练集
算法指导下
生成决策树
新数据进行划分
否则是“三拍”决策
训练集
算法
决策树
新数据
决策
2020/12/24
5
决策树信息论C45算法
决策树基础
实例
No.
头痛
肌肉痛
体温
患流感
1
是(1)
是(1)
正常(0)
N(0)
2
是(1)
是(1)
高(1)
Y(1)
3
是(1)
是(1)
很高(2)
Y(1)
4
否(0)
是(1)
正常(0)
N(0)
5
否(0)
否(0)
高(1)
N(0)
6
否(0)
是(1)
很高(2)
N(1)
7
是(1)
否(0)
高(1)
Y(1)
决策树怎么做？谁是父节点？
谁是下一层子节点？为什么是它？
头-肌肉-体温
头-体温-肌肉
肌肉-头-体温
肌肉-体温-头
体温-头-肌肉
体温-肌肉-头
三 拍 决 策
2020/12/24
6
决策树信息论C45算法
决策树基础
……@）￥——JK)I*&^Fkl9*^&%*&UIDOFGJ
No.
天气
气温
湿度
风
类别
1
晴
热
高
无
N
2
晴
热
高
有
N
3
多云
热
高
无
P
4
雨
适中
高
无
P
5
雨
冷
正常
无
P
6
雨
冷
正常
有
N
7
多云
冷
正常
有
P
No.
天气
气温
湿度
风
类别
8
晴
适中
高
无
N
9
晴
冷
正常
无
P
10
雨
适中
正常
无
P
11
晴
适中
正常
有
P
12
多云
适中
高
有
P
13
多云
热
正常
无
P
14
雨
适中
高
有
N
2020/12/24
7
决策树信息论C45算法
怎么生成好的？
哪个好？
种决策树方案
决策树基础
N个分割属性的训练集
2020/12/24
8
决策树信息论C45算法
决策树基础
好的决策树：（MDL准则下为例）
Minimum Description Length
训练集中大多数数据符合这棵树
例外的数据单独编码
描述决策树用的bit
描述例外数据用bit
哪个好？
2020/12/24
9
决策树信息论C45算法
决策树基础（选择掌握）
如何描述决策树
体温
头痛
很高
正常
高
Y
N
Y
N
否
是
流感决策树
深度优先遍历决策树
用1标注父子节点
用0标注叶节点
记录分割属性
1,体温,0,Y,1,头疼,0,Y,0,N,0,N
层次少+分枝少
占用存储空间小
决策计算时间快
2020/12/24
10
决策树信息论C45算法