⼀，决策树剪枝
1. MEP(minimum error pruning)
MEP⽅法的基本思路是采⽤⾃底向上的⽅式，对于树中每个⾮叶节点。⾸先计算该节点的误差，然后，计算该节点每个分⽀的误差，并且加权相加，权为每个分⽀拥有的训练样本⽐例。如果⼤于，则保留该⼦树；否则，剪裁它。 nas1638
通常，的计算采⽤公式：
其中：n(t)为节点t中的样本总数；为t中主类的样本数⽬；k为类数⽬
黄镇将军2. REP(Reduced-Error Pruning 错误率降低剪枝)
REP⽅法是⼀种⽐较简单的后剪枝⽅法。在该⽅法中，数据被分成两个样例的集合：训练集和验证集。训练集⽤来评估这个决策树在后续数据上的精度。
判断是否剪枝的依据是精度。
精度是指对于某⼀个节点，测试集在剪枝前后正确分类的个数。
崔津渡
⾸先计算节点t的误差：，然后计算每个节点的误差并相加。如果⼤于，则保留该⼦树；否则，剪裁它。
其中：n(t)为节点t中的样本总数；为t中主类的样本数⽬
3. PEP(Pesimistic-Error Pruning 悲观错误剪枝)
PEP是根据剪枝前后的错误率来判定⼦树的修剪。
该⽅法引⼊了统计学上连续修正的概念弥补REP中的缺陷，在评价⼦树的训练错误公式中添加了⼀个常数，假定每个叶⼦节点都⾃动对实列的某个部分进⾏错误的分类。
把⼀颗⼦树（具有多个叶⼦节点）的分类⽤⼀个叶⼦节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不⼀定。于是我们需要把⼦树的误判计算加上⼀个经验性的惩罚因⼦。对于⼀颗叶⼦节点，它覆盖了N个样本，其中有E个错误，那么该叶⼦节点的错误率为（E+0.5）/N。这个0.5就是惩罚因⼦，那么⼀颗⼦树，它有L个叶⼦节点，那么该⼦树的误判率估计为： 其中：为该节点错误的个数，为该节点样本的个数,L为叶⼦节点个数
剪枝后，其概率误判率e为(E+0.5)/N，因此叶⼦节点的误判次数均值为：
剪枝前，误判均值E和标准差：
E (t )r E (T )r t E (t )r E (T )∑r t E (t )r E (t )=
r n (t )+k n (t )−n (t )+(k −1)
c n (t )c E (t )r E (T )r t E (t )r E (T )∑r t E (t )=r n (t )−n (t )
c n (t )c e =
N ∑i E +0.5∗L
∑i E i N i E t e =t N
E +0.5
E =t N ∗e =t N ∗=N
E +0.5
E +0.5N =N ∑i
判断是否剪枝条件：
剪枝：
例⼦：
注："T4"是节点， 9 和7 分别是类1和类2的个数
4.CCP （Cost-Complexity Pruning 代价复杂度剪枝）
N
∑e =T =N ∑i E +0.5∗L ∑i N
E +0.5∗L
∑i E =T N ∗e =T N ∗=N
E +0.5∗L
∑i E +∑i 0.5∗L δ==N ∗e ∗(1−e )T T E ∗(N −E )
T T E <t E +Ti δ
CCP算法为⼦树 定义了代价和复杂度，以及⼀个衡量代价与复杂度之间关系的参数α。代价指的是在剪枝过程中因⼦树 被叶节点替代⽽增加的错分样本;
复杂度表⽰剪枝后⼦树 减少的叶结点数;
α则表⽰剪枝后树的复杂度降低程度与代价间的关系，定义为:剑水蚤
注：亨利
C(t)为节点的预测误差：
为⼦树的预测误差：
为⼦树的节点个数
CCP算法可以分为两个步骤：大容量存储器
Step 1：
按照上述公式从下到上计算每⼀个⾮叶节点的值，然后每⼀次都剪掉具有最⼩值的⼦树。从⽽得到⼀个集合{T0,T1,T2,…,TM} ，其中，表⽰完整的决策树，表⽰根节点Step 2：
根据真实的错误率在集合{T0,T1,T2,…,TM} 选出⼀个最好的决策树T t T t T t α=
∣T ∣−1t C (t )−C (T )
t C (t )=N
E t
C (T )t T t C (T )=t N
E T t
∣T ∣t T t ααT 0T M
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议