Error Based Pruning剪枝算法与具体实现

EBP（Error Based Pruning）：
下列算法转载自链接：
https://login.sina.com.cn/crossdomain2.php?action=login&entry=blog&r=http%3A%2F%2Fblog.sina.com.cn%2Fs%2Fblog_64ecfc2f0101r3o5.html%3Fsudaref%3Dwww.baidu.com%26display%3D0&login_time=1541312241&sign=11e7e46674643370

•第一步：计算叶节点的错分样本率估计的置信区间上限U
•第二步：计算叶节点的预测错分样本数
–叶节点的预测错分样本数=到达该叶节点的样本数*该叶节点的预测错分样本率U
•第三步：判断是否剪枝及如何剪枝
–分别计算三种预测错分样本数：
•计算子树t的所有叶节点预测错分样本数之和，记为TreeErrors
•计算子树t被剪枝以叶节点代替时的预测错分样本数，记为LeafErrors + ExtraLeafErrors
•计算子树t的最大分枝的预测错分样本数，记为BranchErrors
–比较TreeErrors，LeafErrors + ExtraLeafErrors ，BranchErrors，如下：
•TreeErrors最小时，不剪枝
•LeafErrors + ExtraLeafErrors 最小时，进行剪枝，以一个叶节点代替t
•BranchErrors最小时，采用“嫁接”(grafting)策略，即用这个最大分枝代替t

EBP算法的具体实现在
http://www.rulequest.com/Personal/c4.5r8.tar.gz
的prune.c文件中，由于是C写的，所以我写了个python接口，稍后放出。

EBP算法的最早提出在
<Quinlan的C4.5:program for machine learning>
的37页，
提出的时候没有提到嫁接，但是他的代码实现中有嫁接。

解释下嫁接：
1.嫁接不是整个子树剪掉，而是减掉其中的一些树枝。
2.当测试数据到达叶子节点的上面一个分割点的时候，如果树枝的属性取值与该测试数据的属性取值不一致，那么此时测试数据的类别就以
“最初根节点到当前分割节点”为止的数据集的比例最大的类别作为该测试数据的判定类别。

具体实例：
<Quinlan的C4.5:program for machine learning>
P37-39

上述结果可以采用上面的http://www.rulequest.com/Personal/c4.5r8.tar.gz
来实现，使用vote数据集,运行方法：
1）c4.5.c中把DF改为vote，
并且在当前路径下放置vote.names,vote.data两个文件
2）make all
3）./c4.5

运行过程分析：
总共进行了3次剪枝，1次嫁接。
其中：
physician fee free=n:这个分支进行了2次剪枝，
1step:对adoption of the budget resolution=n进行剪枝
2step:对pysician fee feeze=n进行剪枝

physician fee free=y:这个分支进行了1次剪枝
physician fee free=u:这个分支进行了1次嫁接

注意整个过程是top-down的，算法一开始会试图剪掉整棵树，因为精度不满足，所以放弃后再继续遍历子树，所以整体呈现top-down
但是剪枝后进行递归检查，此时会体现down-top剪枝，
例如physician fee free=n这个分支的剪枝过程就体现down-top