EBP（Error Based Pruning）：
下列算法轉(zhuǎn)載自鏈接：

weka3初體驗(yàn)以J48（C4.5）構(gòu)造決策樹以及setoptions各參賽含義

EBP算法的具體實(shí)現(xiàn)在
http://www.rulequest.com/Personal/c4.5r8.tar.gz
的prune.c文件中，由于是C寫的，所以我寫了個(gè)EBP剪枝算法的python接口：
https://github.com/appleyuchi/Decision_Tree_Prune

下面的BranchErrors、LeafErrors + ExtraLeafErrors、BranchErrors來自代碼中的prune.c中的變量
?第一步：計(jì)算葉節(jié)點(diǎn)的錯(cuò)分樣本率估計(jì)的置信區(qū)間上限U
?第二步：計(jì)算葉節(jié)點(diǎn)的預(yù)測錯(cuò)分樣本數(shù)
–葉節(jié)點(diǎn)的預(yù)測錯(cuò)分樣本數(shù)=到達(dá)該葉節(jié)點(diǎn)的樣本數(shù)*該葉節(jié)點(diǎn)的預(yù)測錯(cuò)分樣本率U
?第三步：判斷是否剪枝及如何剪枝
–分別計(jì)算三種預(yù)測錯(cuò)分樣本數(shù)：
?計(jì)算子樹t的所有葉節(jié)點(diǎn)預(yù)測錯(cuò)分樣本數(shù)之和，記為TreeErrors
?計(jì)算子樹t被剪枝以葉節(jié)點(diǎn)代替時(shí)的預(yù)測錯(cuò)分樣本數(shù)，記為LeafErrors + ExtraLeafErrors
?計(jì)算子樹t的最大分枝的預(yù)測錯(cuò)分樣本數(shù)，記為BranchErrors
–比較TreeErrors，LeafErrors + ExtraLeafErrors ，BranchErrors，如下：
?TreeErrors最小時(shí)，不剪枝
?LeafErrors + ExtraLeafErrors 最小時(shí)，進(jìn)行剪枝，以一個(gè)葉節(jié)點(diǎn)代替t
?BranchErrors最小時(shí)，采用“嫁接”(grafting)策略，即用這個(gè)最大分枝代替t

EBP算法的最早提出在
<Quinlan的C4.5:program for machine learning>
的37頁，
提出的時(shí)候沒有提到嫁接，分析案例時(shí)39頁提到了嫁接。

解釋下嫁接：
1.嫁接不是整個(gè)子樹剪掉，而是減掉其中的一些樹枝。
2.當(dāng)測試數(shù)據(jù)到達(dá)葉子節(jié)點(diǎn)的上面一個(gè)分割點(diǎn)的時(shí)候，如果樹枝的屬性取值與該測試數(shù)據(jù)的屬性取值不一致，那么此時(shí)測試數(shù)據(jù)的類別就以
“最初根節(jié)點(diǎn)到當(dāng)前分割節(jié)點(diǎn)”為止的數(shù)據(jù)集的比例最大的類別作為該測試數(shù)據(jù)的判定類別。

具體實(shí)例：
<Quinlan的C4.5:program for machine learning>
P37-39

上述結(jié)果可以采用上面的http://www.rulequest.com/Personal/c4.5r8.tar.gz
來重現(xiàn)，使用vote數(shù)據(jù)集,運(yùn)行方法：
1）c4.5.c中把DF改為vote，
并且在當(dāng)前路徑下放置vote.names,vote.data兩個(gè)文件
2）make all
3）./c4.5

運(yùn)行過程分析：
總共進(jìn)行了3次剪枝，1次嫁接。
其中：
physician fee free=n:這個(gè)分支進(jìn)行了2次剪枝，
1step:對adoption of the budget resolution=n進(jìn)行剪枝
2step:對pysician fee feeze=n進(jìn)行剪枝
注意是Bottom-Top

physician fee free=y:這個(gè)分支進(jìn)行了1次剪枝
physician fee free=u:這個(gè)分支進(jìn)行了1次嫁接

注意整個(gè)過程是down-top方式遍歷
例如physician fee free=n這個(gè)分支的剪枝過程就體現(xiàn)down-top

EBP是PEP更加悲觀的算法，所謂的“悲觀”到底體現(xiàn)在哪里？
例如16條數(shù)據(jù)中，一條數(shù)據(jù)預(yù)測錯(cuò)誤，那么錯(cuò)誤率是$\frac{1}{16}$
根據(jù)這個(gè)實(shí)際錯(cuò)誤率，使用置信區(qū)間25%估算得到“悲觀錯(cuò)誤率”（pessimistic error rate）：
$U_{0.25}(1,16)=0.157$
然后用這個(gè)"悲觀錯(cuò)誤率"來預(yù)測上面的悲觀錯(cuò)誤數(shù)量，
再把悲觀錯(cuò)誤疊加到實(shí)際錯(cuò)誤數(shù)量上，然后再進(jìn)行“維持原樣”、“剪枝”、“嫁接”的“悲觀錯(cuò)誤數(shù)量”進(jìn)行比較，哪個(gè)的“悲觀錯(cuò)誤數(shù)量”最小就用哪種。
關(guān)于$U_{0.25}(1,16)=0.157$的悲觀錯(cuò)誤率、悲觀錯(cuò)誤數(shù)量的估算方法如下：
https://blog.csdn.net/appleyuchi/article/details/83834101

另外J48的剪枝算法是EBP和REP，不是PEP，
Quinlan的C4.5-Release8的實(shí)現(xiàn)版本中，
http://www.rulequest.com/Personal/c4.5r8.tar.gz
使用的剪枝算法也是EBP，不是PEP。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的Error Based Pruning剪枝算法、代码实现与举例的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。