百度网站是怎么建设的,建筑模型网站有哪些,做网站的视频教程,龙口网站建设公司1. 为什么要进行剪枝 横轴表示在决策树创建过程中树的结点总数#xff0c;纵轴表示决策树的预测精度。 实线显示的是决策树
在训练集上的精度#xff0c;虚线显示的则是在⼀个独⽴的测试集上测量出来的精度。 随着树的增⻓#xff0c;在
训练样集上的精度是单调上升的纵轴表示决策树的预测精度。 实线显示的是决策树
在训练集上的精度虚线显示的则是在⼀个独⽴的测试集上测量出来的精度。 随着树的增⻓在
训练样集上的精度是单调上升的 然⽽在独⽴的测试样例上测出的精度先上升后下降。
出现这种情况的原因
噪声、样本冲突即错误的样本数据特征即属性不能完全作为分类标准巧合的规律性数据量
不够⼤。
剪枝 (pruning)是决策树学习算法对付过拟合的主要⼿段。 在决策树学习中为了尽可能正确分
类训练样本结点划分过程将不断重复有时会造成决策树分⽀过多这时就可能因训练样本学
得太好了以致于把训练集⾃身的⼀些特点当作所有数据都具有的⼀般性质⽽导致过拟合。因
此可通过主动去掉⼀些分⽀来降低过拟合的⻛险。
如何判断决策树泛化性能是否提升呢 可使⽤留出法即预留⼀部分数据⽤作验证集以进⾏性
能评估。例如对下表的⻄⽠数据集将其随机划分为两部分其中编号为 {1236 7 10
14 15 16 17} 的样例组成训练集编号为 {4 5 8 9 11 12 13} 的样例组成验证
集。 假定采⽤信息增益准则来划分属性选择则上表中训练集将会⽣成⼀棵下⾯决策树。 接下来将对这⼀棵树进⾏剪枝。
2. 预剪枝
决策树剪枝的基本策略有预剪枝 (pre-pruning)和后剪枝(post- pruning) 。
预剪枝是指在决策树⽣成过程中对每个结点在划分前先进⾏估计若当前结点的划分不能带来决
策树泛化性能提升则停⽌划分并将当前结点标记为叶结点后剪枝则是先从训练集⽣成⼀棵完
整的决策树然后⾃底向上地对⾮叶结点进⾏考察若将该结点对应的⼦树替换为叶结点能带来决
策树泛化性能提升则将该⼦树替换为叶结点。
有多种不同的方式可以让决策树停止生长下面介绍几种停止决策树生长的方法
①定义一个高度当决策树达到该高度时就可以停止决策树的生长 这是一种最为简单的方法
②达到某个结点的实例具有相同的特征向量即使这些实例不属于同一类也可以停止决策树的生
长。这种方法对于处理数据中的数据冲突问题非常有效
③定义一个阈值当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长
④定义一个阈值通过计算每次扩张对系统性能的增益并比较增益值与该阈值的大小来决定是否
停止决策树的生长。
预剪枝方法不但相对简单效率很高而且不需要生成整个决策树 适合于解决大规模问题。该
方法看起来很直接但要精确地估计决策树生长的停止时间并不容易即选取一个恰当的阈值是非
常困难的。高阈值可能导致过分简化的树而低阈值可能使得树的简化太少。
在测试集上定义损失函数C目标是通过剪枝使得在测试集上C的值下降。 例如通过剪枝使在测试
集上误差率降低。 首先自底向上的遍历每一个非叶节点(除了根节点)将当前的非叶节点从树
中剪去其下所有的叶节点合并成一个节点代替原来被剪掉的节点。 然后计算剪去节点前后
的损失函数如果剪去节点之后损失函数变小了则说明该节点是可以剪去的并将其剪去如果
发现损失函数并没有减少 说明该节点不可剪去则将树还原成未剪去之前的状态。 最后重复
上述过程直到所有的非叶节点(除了根节点)都被尝试了。
对于上例⾸先基于信息增益准则会选取属性脐部来对训练集进⾏划分并产⽣ 3 个分⽀
如下图所示。然⽽是否应该进⾏这个划分呢预剪枝要对划分前后的泛化性能进⾏估计。在划分
之前所有样例集中在根结点。 若不进⾏划分该结点将被标记为叶结点其类别标记为训练样例数最多的类别假设将这个叶结
点标记 为好⽠。 ⽤前⾯表的验证集对这个单结点决策树进⾏评估。则编号为 {458} 的样例
被分类正确。另外 4个样例分类错误于是验证集精度为3 / 7 ∗ 100% 42.9%。
在⽤属性脐部划分之后上图中的结点2、3、4分别包含编号为 {123 14}、 {67 15
17}、 {10 16} 的训练样例因此这 3 个结点分别被标记为叶结点好⽠、 好⽠、 坏⽠。 此时验证集中编号为 {4 5 811 12} 的样例被分类正确验证集精度为5 / 7 ∗ 100%
71.4% 42.9%。于是⽤脐部进⾏划分得以确定。
然后决策树算法应该对结点2进⾏划分基于信息增益准则将挑选出划分属性⾊泽。然⽽在
使⽤⾊泽划分后编号为 {5} 的验证集样本分类结果会由正确转为错误使得验证集精度下降为
57.1%。于是预剪枝策略将禁⽌结点2被划分。 对结点3最优划分属性为根蒂划分后验证集
精度仍为 71.4%. 这个划分不能提升验证集精度于是预剪枝策略禁⽌结点3被划分。 对结点4
其所含训练样例已属于同⼀类不再进⾏划分。于是基于预剪枝策略从上表数据所⽣成的决策树
如上图所示其验证集精度为 71.4%。这是⼀棵仅有⼀层划分的决策树也称决策树桩 (decision
stump)。
3. 后剪枝
后剪枝先从训练集⽣成⼀棵完整决策树继续使⽤上⾯的案例从前⾯计算了解到前⾯构造的决
策树的验证集精度为 42.9%。 后剪枝⾸先考察结点6若将其领衔的分⽀剪除则相当于把6替换为叶结点。替换后的叶结点包含编
号为 {7 15} 的训练样本于是该叶结点的类别标记为好⽠此时决策树的验证集精度提高至
57.1%。于是后剪枝策略决定剪枝如下图所示。 然后考察结点5若将其领衔的⼦树替换为叶结点则替换后的叶结点包含编号为 {6715}的训
练样例叶结点类别标记为好⽠此时决策树验证集精度仍为 57.1%. 于是可以不进⾏剪枝。
对结点2若将其领衔的⼦树替换为叶结点则替换后的叶结点包含编号为 {1 2 3 14} 的训
练样例叶结点标记为好⽠此时决策树的验证集精度提高至 71.4%。于是后剪枝策略决定剪
枝。对结点3和1若将其领衔的子树替换为叶结点则所得决策树的验证集精度分别为 71.4% 与
42.9%均未得到提高于是它们被保留。 最终基于后剪枝策略所⽣成的决策树就如上图所示
其验证集精度为 71.4%。
对⽐两种剪枝⽅法
后剪枝决策树通常⽐预剪枝决策树保留了更多的分⽀。
⼀般情形下后剪枝决策树的⽋拟合⻛险很小泛化性能往往优于预剪枝决策树。 但后剪枝过程
是在⽣成完全决策树之后进⾏的。 并且要自底向上地对树中的所有非叶结点进行逐⼀考察因此
其训练时间开销比未剪枝决策树和预剪枝决策树都要⼤得多。
4. 剪枝的方法
Reduced-Error Pruning(REP错误率降低剪枝
REP方法是一种比较简单的后剪枝的方法在该方法中可用的数据被分成两个样例集合一个训
练集用来形成学习到的决策树一个分离的验证集用来评估这个决策树在后续数据上的精度确切
地说是用来评估修剪这个决策树的影响。 这个方法的动机是即使学习器可能会被训练集中的随
机错误和巧合规律所误导但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过
度拟合训练集中的虚假特征提供防护检验。
该剪枝方法考虑将树上的每个节点作为修剪的候选对象决定是否修剪这个结点由如下步骤组成
①删除以此结点为根的子树
②使其成为叶子结点
③赋予该结点关联的训练数据的最常见分类
④当修剪后的树对于验证集合的性能不会比原来的树差时才真正删除该结点
训练集合可能过拟合使用验证集合数据能够对其进行修正反复进行上面的操作从底向上的处
理结点删除那些能够最大限度的提高验证集合的精度的结点直到进一步修剪有害为止(有害是
指修剪会减低验证集合的精度)。
Pesimistic-Error Pruning(PEP悲观错误剪枝
悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概
念弥补REP中的缺陷在评价子树的训练错误公式中添加了一个常数假定每个叶子结点都自动对
实例的某个部分进行错误的分类。 把一棵子树具有多个叶子节点的分类用一个叶子节点来替
代的话在训练集上的误判率肯定是上升的但是在新数据上不一定。于是需要把子树的误判计
算加上一个经验性的惩罚因子。
对于一个叶子节点它覆盖了N个样本其中有E个错误那么该叶子节点的错误率为
E0.5/N。这个0.5就是惩罚因子那么一棵子树它有L个叶子节点那么该子树的误判率估
计为
这样的话可以看到一棵子树虽然具有多个子节点但由于加上了惩罚因子所以子树的误判率计
算未必占到便宜。剪枝后内部节点变成了叶子节点其误判个数J也需要加上一个惩罚因子变成
J0.5 。那么子树是否可以被剪枝就取决于剪枝后的错误J0.5在
的标准误差内。对于样本的误差率e可以根据经验把它估计成各种各样的分布模型比如是二项
式分布比如是正态分布。 那么一棵树错误分类一个样本值为1正确分类一个样本值为0该树
错误分类的概率误判率为ee为分布的固有属性可以通过 统计出来那么树的误判次数就是伯努利分布就可以估计出该树的误判次数均值和标准差 把子树替换成叶子节点后该叶子的误判次数也是一个伯努利分布其概率误判率e为(E0.5)/N
因此叶子节点的误判次数均值为
使用训练数据子树总是比替换为一个叶节点后产生的误差小 但是使用校正后有误差计算方法
却并非如此当子树的误判个数大过对应叶节点的误判个数一个标准差之后就决定剪枝 这个条件就是剪枝的标准。当然并不一定非要大一个标准差可以给定任意的置信区间设定一定
的显著性因子就可以估算出误判次数的上下界。
比如 T4这棵子树的误差率(70.5*3)/160.53125
子树误判次数的标准误差
子树替换为一个叶节点后其误判个数为70.57.5
因为8.51.9967.5所以决定将子树T4替换这一个叶子节点。
Cost-Complexity PruningCCP代价复杂度剪枝)
该算法为子树 Tt 定义了代价cost和复杂度complexity以及一个可由用户设置的衡量代价
与复杂度之间关系的参数α其中代价指在剪枝过程中因子树 Tt 被叶节点替代而增加的错分样
本复杂度表示剪枝后子树 Tt 减少的叶结点数α则表示剪枝后树的复杂度降低程度与代价间的关
系定义为
其中 |N1|子树 Tt 中的叶节点数
Rt结点 t 的错误代价计算公式为Rt rt*pt rt为结点 t 的错分样本率
pt为落入结点 t 的样本占所有样本的比例
RTt子树 Tt 错误代价计算公式为RTt∑R(i)i为子树 Tt 的叶节点。
比如 我们以非叶结点 T4 为例假设已有的数据有60条那么 R(t)r(t)*p(t)(7/16)*(16/60)7/60
RTt∑R(i)(2/5)*(5/60)(0/2)*(2/60)(3/9)*(9/60)5/60
αR(t)-RTt)/(|N1|-1)1/60
CCP剪枝算法分为两个步骤
①对于完全决策树 T 的每个非叶结点计算 α 值循环剪掉具有最小 α 值的子树直到剩下根节
点。在该步可得到一系列的剪枝树T0 T1T2......Tm。其中 T0 为原有的完全决策树Tm为
根结点Ti1为对 Ti 进行剪枝的结果
②从子树序列中根据真实的误差估计选择最佳决策树。
通常使用1-SE1 standard error of minimum error规则从步骤1产生的一系列剪枝树中选择一棵
最佳的剪枝决策树。方法为假定 一个含有N个样本的剪枝集分别用在步骤1中产生的剪枝树
Ti 对该剪枝集进行分类记 Ti 所有叶结点上长生的错分样本数为Ei令Emin Ei定义E
的标准错误为
所得的最佳剪枝树 Tbest 是满足条件 Ei ≤ E SEE且包含的接点数最少的那棵剪枝树 Ti。
几种后剪枝方法的比较
