33.3K
8354
剪枝
在決策樹學習過程中，為了盡可能正確分類訓練樣本，結點劃分過程將不斷重復，有時會造成決策樹分支過多，從而把訓練集自身的一些特點當作所有數據都具有的一般性質，即出現過擬合。剪枝是主動去掉一些分支來降低過擬合的風險，是決策樹學習算法對付過擬合的主要手段。只有少量問題有此類算法。
決策樹剪枝的基本策略有預剪枝（prepruning）和后剪枝（postpruning）。預剪枝是指在決策樹生成過程中，對每個結點在劃分前先進行估計，若當前結點的劃分不能帶來決策樹泛化性能提升，則停止劃分并將當前結點標記為葉結點。后剪枝則是先從訓練集生成一棵完整的決策樹，然后自底向上地對非葉結點進行考察，若將此結點對應的子樹替換為葉結點能夠帶來決策樹泛化能力的提升，則將此樹替換為葉結點。常用的后剪枝策略包括：降低錯誤剪枝(reduced error pruning，REP)、悲觀錯誤剪枝(pessimistic error pruning，PEP)、基于錯誤剪枝(error based pruning，EBP)、代價復雜度剪枝(cost complexity pruning，CCP)和最小錯誤剪枝(minimum error pruning，MEP)等。
通常后剪枝決策樹比預剪枝決策樹保留更多的分支。在一般情形下，后剪枝決策樹的欠擬合風險很小，其泛化性能往往優于預剪枝決策樹。但是，后剪枝過程是在生成完整決策樹之后進行的，并且要自底向上地對樹中的所有非葉結點進行逐一考察，因此其訓練時間開銷比未剪枝決策樹和預剪枝決策樹都要大得多。
