过拟合问题 此处剪枝 测试数据 训练数据 剪枝 决策树深度 避免过拟合 决策树泛化 6+6x 6+1x+B2x2+61x+2x2+3x3+4x ligh bia Just right High varia (underfit (overfit) 26
26 过拟合问题 训练数据 测试数据 此处剪枝 决策树深度 剪枝 ◼ 避免过拟合 ◼ 决策树泛化
Pruning Tree 目的: 消除决策树的过拟合 Over Fitting)间题 ■实质:消除训练集中的异常和噪声 两种方法: 先剪枝法( Public算法 后剪枝法( Sprint算法) 平 青缦 浅白 验证集精度 剪枝前:42.9% 青绿 浅自 剪枝后:57.1% 好 后剪枝决策:剪枝
27 Pruning Tree ◼ 目的： ◼ 消除决策树的过拟合(Over Fitting)问题 ◼ 实质：消除训练集中的异常和噪声 ◼ 两种方法： ◼ 先剪枝法(Public 算法) ◼ 后剪枝法(Sprint 算法)
误分类率 分类类别 C1 C2 C3 C10 2 13 米C2 rr0 23 C3 32 Cost (or loss)matrix 28
28 误分类率 C1 C2 C3 C1 0 r12 r13 C2 r21 0 r23 C3 r31 r 实际类别 32 0 分类类别 Cost (or loss) matrix
决策树算法的可伸缩性 D3、C4.5等算法对规模较小,可以一次放入内存的训练样本集很有效, 但实际上数以百万计样本的超大型训练集是常见的,大多数情况下无法把 训练样本集全部放入内存,导致这些算法的有效性降低。因此需要增加可 伸缩的方法以节省空间。 IBM的研究人员运用一些特殊数据结构,例如属性表和类表,在1996年提 出了一种快速的、可伸缩的sLIQ算法,可以处理离散属性和连续属性。 sLQ算法首先把训练样本集划分成若干子集,使每一个子样本集都能放入 内存,然后对每个子样本集分别构造一棵决策树,再把这些决策树综合 得到最终決策树。siQ算法可以处理大规模的训练样本集,具有较好的 伸缩性。与传统决策树算法相比,减少了运行时间。SLIQ算法在执行过程 需要随时修改类表,类表常驻内存,而类表的大小会随着训练样本集的 增大而增大,因此SIQ算法对内存容量有一定的要求
29 决策树算法的可伸缩性 ◼ ID3、C4.5等算法对规模较小，可以一次放入内存的训练样本集很有效， 但实际上数以百万计样本的超大型训练集是常见的，大多数情况下无法把 训练样本集全部放入内存，导致这些算法的有效性降低。因此需要增加可 伸缩的方法以节省空间。 ◼ IBM的研究人员运用一些特殊数据结构，例如属性表和类表，在1996年提 出了一种快速的、可伸缩的SLIQ算法，可以处理离散属性和连续属性。 SLIQ算法首先把训练样本集划分成若干子集，使每一个子样本集都能放入 内存，然后对每个子样本集分别构造一棵决策树，再把这些决策树综合， 得到最终决策树。SLIQ 算法可以处理大规模的训练样本集，具有较好的 伸缩性。与传统决策树算法相比，减少了运行时间。SLIQ算法在执行过程 中需要随时修改类表，类表常驻内存，而类表的大小会随着训练样本集的 增大而增大，因此SLIQ算法对内存容量有一定的要求
常用的决策树算法 ID3,c45,C50算法 CART(C&R)算法(可处理分类和回归问题) CHAID算法 QUEST算法
30 常用的决策树算法 ◼ ID3, C4.5, C5.0算法 ◼ CART （C&R)算法（可处理分类和回归问题） ◼ CHAID算法 ◼ QUEST算法