PEP:Pessimistic Error Pruning
本文分為兩部分：
第一部分：1986年的PEP剪枝算法原理
第二部分：1997年的PEP剪枝算法原理以及與前者的對比
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
第一部分：

《Ｓｉｍｐｌｉｆｙｉｎｇ　Ｄｅｃｉｓｉｏｎ　Ｔｒｅｅｓ》－１９８６
作者：J.R. Quinlan
該論文的2.3 Pessimistic Pruning 首次提出了悲觀剪枝。
整理如下：
悲觀剪枝參考了一本統計書籍：
《Statistical Methods》(7th edition)　Snedecor,G.W. and Cochran,W.G.(1980)
論文相關部分如下：

整理成偽代碼如下：
K:當前子樹的總數據條數
J：當前子樹分錯的數據條數
E:剪枝后的分錯的數據條數
$\sum J$：一個葉子節點分類出錯的數據條數

$L(S)$：被判斷是否需要剪枝的子樹的所有葉子節點的數量

$\sum J+\frac{1}{2}L(S)$:悲觀地猜測,如果不剪枝，那么該子樹的所有葉子節點將會估計錯誤的數據條數
top to down方式剪枝
分錯的數量的分布視為二項分布
剪枝后的分錯的數據條數＝E+$\frac{1}{2}$
－－－－－－－－－－－－－－－
上面所有需要＋$\frac{1}{2}$的原因來自前面提到的參考文獻的：
《Statistical Methods》(7th edition)　Snedecor,G.W. and Cochran,W.G.(1980)的pp.117ff(這個到底是第幾頁的意思我也不知道，反正這本書似乎網上找不到ｐｄｆ了)
－－－－－－－－－－－－－－－
如果剪枝后的$E+\frac{1}{2}$<$\sum J+\frac{1}{2}L(S)$+$onestandarderrorof\sum J+\frac{1}{2}L(S)$
就把該子樹用該字數中出現類別頻率最高的葉子節點替換。
論文中的舉例是：

把上面這棵決策樹的黃色圓圈部分的子樹替換為一個葉子。
判斷過程如下：
１．由于該子樹中只有一個葉子是非ｎｅｇａｔｉｖｅ，其余都是ｎｅｇａｔｉｖｅ，假如剪枝，那么得到的判據是：
Ｅ＋$\frac{1}{2}$=1.5
２．假如不剪枝，那么判據是：
$\sum J+\frac{1}{2}L(S)$+$onestandarderrorof\sum J+\frac{1}{2}L(S)$
由于$\sum J$=0
且剪枝前的葉子數是４個，
所以該判據的結果是2+$\sqrt{2}$
所以有１．５<2+$\sqrt{2}$
所以剪去該分支。
ＰＥＰ剪枝后的結果如下：

我們前面提到的是PEP的剪枝，這里的截圖寫的是CCP的剪枝。文中提到
所以該篇文章中，PEP和CCP的剪枝效果是一樣的，都是Figure2

另外注意：這篇論文的
剪枝前數據有2238條
剪枝后數據有2241條
原有數據集是2541條
具體為什么會有這個差別，作者沒有明說，這個是由于ｕｎＫｎｏｗｎ（含缺失值）數據的處理方式沒有詳細闡述。

－－－－－－－－－－－－－－－－－－－－-－－
第二部分

論文是意大利人寫的：
《A Comparative Analysis of Methods　for Pruning Decision Trees》1997年，兩種算法各個組成部分的對應關系如下：

1986年版本－Quinlan1997年版本- Floriana Esposito

E+$\frac{1}{2}$	e’(t)＝e(t) + $\frac{1}{2}$
$\sum J+\frac{1}{2}L(S)$
one standard error of $\sum J+\frac{1}{2}L(S)$
E+$\frac{1}{2}<\sum J+\frac{1}{2}L(S)+standarderrorof(\sum J+\frac{1}{2}L(S))$

注意，這里第三欄的標準差是同一個意思
Quinlan是對分類錯的數據條數先修正，然后求標準差，
這里$\frac{1}{2}L(S)的標準差是\mathrm{０}，所以其實這里是是在計算\sum J的標準差$

Floriana Esposito是直接把ｅｒｒｏｒ的分布當做二項分布處理，使用了
$Var=\sqrt{npq}=\sqrt{\frac{分錯的數量?（總數－分錯的數量）}{總數}}$

這兩個版本的PEP剪枝的區別總共有１處：
Quinlan版本的PEP判據是＜，
Floriana Esposito版本的PEP判據是≤

《Simplifying Decision Trees》-1986的part 2.3 Pessimistic Pruning 中
,
計算one standard error of $\sum J+\frac{L(S)}{2}$時，
$\frac{L(S)}{2}$的方差肯定是0，因為L(S)是葉子數量。
所以：
standard error of $\sum J+\frac{L(S)}{2}$
=standard error of $\sum J$
=$\sqrt{\frac{n^{\prime }(T_t)?(N(t)?n^{\prime }(T_t))}{N(t)}}$
=$\sqrt{n^{\prime }(T_t)(1?\frac{n^{\prime }(T_t)}{N(t)})}$
≈$\sqrt{n^{\prime }(T_t)}$
=$\sqrt{2}$
=1.41

這個PEP的原理到底啥意思呢？
意思就是當前錯誤數被當做是一個變量的平均，當這個錯誤數量+這個變量的標準差時，就可以接近這個 變量的最大值。
把這個接近變量的最大值當做悲觀錯誤數。
那么，作者沒有解釋的是，為什么“當前錯誤數”被假設為“一個變量的平均呢”，這明明不是變量啊～！
這是因為：一套數據集我們都是reshuffle后隨機取其中的70~80%作為訓練集的，由此導致的一個結果就是，到達某個子樹的數據集被錯分的數量是不定的，所以把當前子樹的被錯分數據的數量“視為”（assumption）一個變量來處理。

再作一個總結：
Quinlan發布的C4.5-Release8中使用的剪枝算法是EBP(Error Based Pruning)
http://www.rulequest.com/Personal/c4.5r8.tar.gz
weka中的J48使用的兩種剪枝算法是EBP和REP

參考鏈接：
https://www.cnblogs.com/junyuhuang/p/4572408.html

總結

以上是生活随笔為你收集整理的Earliest PEP Algorithm Principles的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。