文档介绍：决策树学****的过拟合问题
姓名：
专业：通信与信号系统 学号:
一决策树学****简介
决策树学****是一种逼近离散值目标函数的方法，这种方法将从一组训练数据 中学****到的函数表示为一棵决策树。决策树叶子为类别名，其他的结点由实体的 特征组成据集，对这些经过修剪 的决策树的分类准确性进行评价，保留下预期分类错误率最小的(修剪后)决 策树。
与预剪枝相比，后剪枝倾向于产生更好的结果，因为与预剪枝不同，后剪枝 是根据完全生长的树做出的剪枝决策，预剪枝则可能过早终止决策树的生长。
下面介绍三种主要的后剪枝方法：悲观错误剪枝(Mistic Error Pruning， PEP)，最小错误剪枝(Minimum Error Pruning， MEP)，代价复杂度剪枝(Cost Complexity Pruning， CCP)。
⑴悲观错误剪枝(PEP)
悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了 统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加 了一个常数，假定每个叶结点都自动对实例的某个部分进行错误的分类。
该方法需要对决策树上所有的非叶子结点a进行计算分析。搜索时从决策树 的根结点开始，计算每个分枝结点被剪后或者是被子树替换后的期望错误率。为 了使数据源的数据特性得到最大限度的保留，把数据源作为一个整体，而不是将 其分为训练集和测试集两个部分。因此需要考虑最坏的情况，取置信区间的上限 作悲观情况下的错误估计。给定一个置信度c，错误总数服从N项贝努利 (Bernoulli)分布是很明显的，因而有概率等式如下：
「f q
q (1 - q)/n
在该公式中，q表示估计的错误率，N表示被修剪的子树下的实例总数，假
设E表示修剪后出现的错误实例数，那么f = E / N是实际观测到的错误率。令
z = R
，取置信区间的上限作为该结点的悲观错误率估计，则可得该结点的错
1 — c
误率计算公式如下:
■
” z2 ! / /2 z2
/ + + z — +
2 N N N 4 N 2
在该公式中，根号前的“+ ”号表示取置信区间的上限，q就是估计的悲观 错误率。给定一个期望错误率最高阈值C。当剪去结点A时，如果导致的错误率
q不高于给定的阀值C，则剪去结点A下的子树；否则，保留结点A下的子树。
⑵最小错误剪枝(MEP)
MEP算法希望通过剪枝得到一棵相对于独立数据集来说具有最小期望错误 率的决策树。所使用的独立数据集是用来简化对未知样本的错分样本率的估计 的，并不意味真正使用了独立的剪枝集，实际情况是无论早期版本还是改进版本 均只利用了训练集的信息。
对于k类问题，定义样本到达结点t且属于第i类的期望概率为：
P (t)= n⑴+ paim + m ；其中为由训练集得来的属于第i类的先验概率，m表示 i n (t)
先验概率对期望概率p (t)的影响程度，反映了剪枝的程度，为简单起见认为所
i
有类别的m均相同。当一个新样本到达结点t而被分类时，结点t的期望错误率 表示为
EER (t) = min [1 一 p (t)] = min {[n(t) 一 n (t) + (1 一 p )m] /[n(t) + m]}
i i ai
i i
当m = k且p