21
决策树的生长
贪婪搜索（greedy search） 选定作为测试的属性：分类能力最好的属 性被选作树的根节点的测试； 为根节点的属性的每个可能值产生一个Байду номын сангаас 支（离散情况），并依属性值划分样例；
重复该过程，用每个节点上的关联样例选 取该节点上的最佳测试属性。
22
关于决策树的修剪
针对过度拟合的情况： • 及早停止树的增长（直接，但难以衡量合适应停 止树的生长） • 后修剪法(post-pruning)—训练和验证集法 (training and validation set) 错误率降低修剪(reduced-error pruning)— 删除以某节点为根节点的子树，将和该节点相关 联训练样例的最常见分类赋给它。考查修剪后在 验证集上的精度。 规则后修剪(rule post-pruning)—将决策树转 化为等价的规则集合(区分决策节点使用的上下文 不同），删除不会导致估计精度下降的前件 (precondiction). 23
类样例的概率为
freq (C j ,T ) T
Cj
。
b) 可传达的信息为： log bits。
f req (C j ,T )
2
T
9
ID3: Gain Criterion（3）
c) 则 T 的熵为
info (T )
k
若样本集中所有成员属 于同一类，则熵为0
log
freq (C j ,T ) T
第二讲 机器学习的方法
第三章 决策树学习
1
3.2 决策树表示法
决策树的基本结构
N1 N2 N4 N5 N6
Internal node Leaf node
N3 N7
L1
L2
L3
L4
L5
L6
L7
L8
2
3.3 决策树学习的适用问题
• 实例由“属性-值”对(pair)表示 • 目标函数具有离散的输出值 • 可能需要析取的描述(disjunctive description) • 训练数据可以包含错误 (DT具有一定的鲁 棒性) • 训练数据可以包含缺少属性值的实例
gain ( X
H u mid it y
) 0 . 151
gain ( X Win d ) 0 . 048
gain ( X T e m p e r a t u r e ) 0 . 029
15
ID3: Gain Criterion（6）
f) 另外一种不期望的情况也会产生,那就是当测 试
X将样本集
Temperature Humidity Wind
Hot Hot Mild Cool Cool Mild High High High High Normal Normal Normal High Weak Strong Weak Weak Weak Strong Strong Weak
PlayTennis
此时信息增益达到最大值：
gain ( X ) info (T )
信息增益反映的是与分类相关的信息--随着 划分更符合目标分布情况而增长。
13
表3-2 目标概念PlayTennis的训练样例
gain
Gain ratio
Day D1 D2 D3 D4 D5 D6 D7 D8
Outlook
Sunny Sunny Rain Rain Rain Sunny
例: 若样本集被属性A彻底分割，则分裂信息 值为log2n。若属性B将样本集平分为两半， 则分裂信息为1。若属性A和B产生同样的 信息增益，那么B的信息增益率更高。
18
C4.5: Gain Ratio Criterion（2）
c) 当测试完全符合样本的分布时：
split _ info ( X ) info (T ) gain ( X )
表3-2
gain _ ratio ( X T e mp e r a t u r e ) 0 . 029
20
增益率的局限
• 当某个 T i 接近 T ( |T i | |T | )时分母可能为 0或非常小。 即若某个属性对于 T 的所有样例有几乎同样 的值，将导致增益比率未定义或增益比率 非常大。 • 解决的方法: 可以先计算每个属性的增益， 然后仅对那些增益高过平均值的属性应用 增益比率测试（Quinlan 1986）
7
ID3: Gain Criterion（1）
假设&条件： 样本集 T, 包含 k 类样本: C j , j 1,..., k 表示 T 中第 C j 类样例 的数目， |T | 表示 T 中包含的样本总数。
freq (C j ,T )
,
8
ID3: Gain Criterion（2）
a) 从样本中随机抽取一个样例 ，属于
gain _ ratio ( X
o u t lo o k
) gain ( X 0 . 156
o u t lo o k
) / split _ info ( X
o u t lo o k
)
gain _ ratio ( X
H u mid it y
) 0 . 151
gain _ ratio ( X Win d ) 0 . 049
inf o
X
(T )

n
Ti T
inf o (T i )
i 1
则 T 在测试 X 的划分下得到的信息增益为：
gain ( X ) info (T ) info X (T )
12
ID3: Gain Criterion（5）
e) 当测试 X 将 T 完全分类正确时，
info (T i ) 0
3
3.4 基本的决策树学习算法(1)
• 原型：concept learning systems(CLS)(实验归纳一书) [Hoveland, Hunt, 1950s; Hunt, Marin and Stone, 1966] • CART system [Friedman, 1977; Breiman et al., 1984] （由基尼系数-Gini Index—决定最佳的分割测试变量和阈 值） • ID3[J.R. Quilan, 1979,1983,1986]
C4.5的应用
采用构建的DT进行数据挖掘、分类、分析。 信息增益率准则可用于NNTree的构建： ENN的fitness function为每个ENN在 当前节点样本子集上划分的信息增益率。
24
3.7.4 处理缺少属性值的训练样 例
赋给它结点n的训练样例中该属性的最常
见值或赋给它结点n的被分类为c(x)的训练
样例中该属性的最常见值；
每个可能值赋与一个概率。
25
5
什么是C4.5 ?
• 一个基于Unix系统的应用软件 • 该应用软件的作用：通过C4.5设定的 算法/准则生成决策树，对数据分类、 分析 • 该设定的算法/准则：信息增益率准则 (information gain ratio criterion)
6
3.4.1哪个属性是最佳的分类属性
从ID3到C4.5共同之处： 通过自顶向下构造决策树进行学习； 构造过程的开始：哪一个属性将在树的根节点 被测试？ 区别：选择测试属性时的准则 ID3: 增益准则(Gain criterion )—衡量给 定属性区分训练样例的能力。 C4.5: 增益率准则(Gain ratio criterion)
No No Yes Yes Yes No Yes No
Overcast Hot
Overcast Cool
D9
D10 D11
Sunny
Rain Sunny
Cool
Mild Mild
Normal
Normal Normal
Weak
Weak Strong
Yes
Yes Yes
D12
D13 D14
Overcast Mild
分为很多小子集时也可 T
以使得信息增益增加。极端的情况：每一个 子集只包含一个样例。此时同样有：
gain ( X ) info (T )
信息增益准则的内在偏置：偏袒具有较多值 的属性。
16
C4.5: Gain Ratio Criterion（1）
a) 若测试 X 将 T 划分为 n 个子集，则其分裂 信息(split/potential information)为：
split _ info ( X )
n
Ti T
log
Ti
2
i 1
T
分裂信息用来衡量属性分裂数据的广度和均 匀性，实际上就是T关于测试属性X的各值的 熵。
17
C4.5: Gain Ratio Criterion（1）
b) 信息增益率（随着有用分割而得到的信息 增益比率）定义为：
gain _ ratio ( X ) gain ( X ) / split _ info ( X )
则
gain _ ratio ( X ) 1
当分得过细时将导致 split _ info ( X ) 变大，从而使 gain _ ratio ( X ) 减小， 避免了过分细分的可能。
19
C4.5: 各属性划分的信息增益率
split _ info ( X
o u t lo o k
) -5/14 log 2 (5/14) - 4/14 log 2 (4/14) - 5/14 log 2 (5/14)
关于信息论中熵的更详细的内容：[A mathematical theory of communication, C.E. Shannon,1948 ] 11
ID3: Gain Criterion（4）