ch10决策树

ch10决策树内容摘要：

14 14 14 14 14I V ag e    2224 4 6 6 4 4( ) l og l og l og 1. 55 614 14 14 14 14 14I V inc om e    227 7 7 7( ) l og l og 1. 66 114 14 14 14I V stude nt   228 8 6 6( _ ) l og l og 0. 98 514 14 14 14I V c re dit ra ti ng   ()_ ( ) 56()G ain ag eG ain ratio ag eI V ag e()_ ( ) ()G ain inc om eG ain rati o inc om eI V inc om e( _ )_ ( _ ) 49( _ )G ain c re dit ratingG ain ratio c re dit ratingI V c re dit rating()_ ( ) 0 .0 9 1()G a in stud e n tG a in ra ti o stud e n tI V stud e n tGini不纯度 • ：节点 N上样本总个数 • ：其中属于 类的样本个数（ i=1,2, …, m ） • ：属性 A的第 j个取值（ j=1,2, …, v ） • 该节点处的 Gini不纯度 • 属性 A将 S划分为 v个子集 • 中属于 类的样本个数为 i21( ) 1miiSG ini SS iGini不纯度 • 以 A作为查询，生长出 v个分支的 Gini不纯度 • 选择 Gini不纯度差最大（即 Gini(A)最小）的属性作为 N节点的查询 21 1 1( ) ( ) 1v v mj j i jjj j i jS S SG i ni A G i ni SS S S          Gini不纯度 • 例子 2 2 2 2225 2 3 4 4 0( ) 1 114 5 5 14 4 45 3 21 14 5 5G i ni age                                                               ( ) ?G ini inc o m e ( ) ?G ini stu d e n t ( _ ) ?G in i c re d it ra tin g 分支停止准则 • 如果决策树持续生长，直到所有叶节点都达到最小不纯度为止，那么一般将出现“ 过拟合 ” • 极端情况：所有叶节点仅对应一个训练样本，这时，决策树退化为 查找表 • 如果分支停止过早，则对训练样本的拟合较差，导致分类性能较差 • 常用分支停止准则 • 交叉验证 • 预设一个不纯度下降差的阈值 • 监测每个节点代表的样本数目是否小于某个阈值 分支停止准则 • 最小化如下指标 • 不纯度下降的统计显著分析 • 如果一个划分不能显著降低不纯度，则停止分支 正则项 剪枝 • 剪枝 （ pruning） • 用于消除过拟合 • 预剪枝 （ prepruning）和 后剪枝 （ postpruning） • 预剪枝 即前面提到的分支停止技术，也就是在树生长到一定条件时停止继续划分 • 后剪枝 指 首先让树充分生长，直到叶节点具有最小不纯度为止，然后对树进行剪枝 • 可用交叉验证技术来确定剪掉哪些分支 • 剪掉使不纯度增长最小的分支 • 一般来讲，后剪枝性能较好，但需要更多计算量 叶节点的标记 • 如果叶节点对应的样本都来自同一类，则用该类别标记该叶节点 • 一般情况下，叶节点都具有正的不纯度，此时用占优势的样本类别标记该叶节点 ID3 • ID3: Interactive Dichotomizer3（交互式二分法第三版） • 仅仅适用于 标称（无序）数据 如果涉及实值数据，则需离散化，然后当做标称数据处理 • 每个划分的 分支。