在決策樹生成以後，常常出現過拟合的問題。這是因為如果決策樹過于複雜，訓練樣本的每個屬性（變量）都被詳細的加以考慮，決策樹的每個葉節點所覆寫的樣本都是或接近“純”的。這種情況下，決策樹往往對訓練樣本拟合的很好，但是拟合驗證樣本時效果卻大打折扣。
舉一個栗子可以加深對過拟合的了解：在上學的時候，有一些同學準備考試的方法是“背題”，僅僅靠背解題過程卻無法掌握其中規律性的的東西，如果題目都押中了這類同學就可以考得很好，但是對于大多數情況他們卻以失敗告終；還有一些同學，他們擅長在題目中尋找規律，即使題目千變萬化他們也能得到高分。模型也是一樣，我們更希望它能夠展現規律性的東西，而不是訓練樣本中的細節。
這時，對決策樹進行剪枝就成為了一個必不可少的步驟。其實對決策樹而言，相對于樹的生成過程，剪枝的過程更為重要。今天介紹一種後剪枝算法——誤差降低剪枝(Reduced Error Pruning/REP)。
誤差降低剪枝是最簡單粗暴的剪枝方法。首先用訓練樣本生成決策樹後，自下而上對于每個節點決定是否修剪該節點。先假設我們要删除該節點下的子樹使其成為葉子節點并賦予訓練樣本最常見的分類，再用驗證樣本比較修剪前後的錯分率，當修剪後的錯分率不比修剪前的高時便真正删除該節點下的子樹。
舉個栗子，假設有個訓練樣本産生的決策樹長這樣（目标變量可分類為1或）：
其中T4節點中13和7表示該節點覆寫的樣本中目标變量為1和的個數。再假設用這個決策樹拟合驗證樣本後的結果長這樣：
自下而上，按照T5、T6、T4的順序來決定每個節點是否需要被修剪：
在判斷T4是否修剪前，T7、T8節點已被删除，T5成為新的葉子節點。可以看到最終T4節點下的全部子樹都被删除。
誤差降低剪枝使用了和訓練樣本獨立的驗證樣本，由于驗證樣本沒有參與決策樹的生成過程，是以一定程度上可以解決過拟合問題，但也可能會産生過剪枝的問題。