機器學習

一顆完全生長的決策樹會面臨一個很嚴重的問題，就是過擬合問題，解決過擬合問題我們就要降低模型複雜度，對決策樹進行剪枝，提升模型的泛化能力。

決策樹的剪枝通常有兩種方法，預剪枝和後剪枝。預剪枝，在生成決策樹的過程中提前停止樹的增長，後剪枝，在已生成的過擬合的決策樹上進行剪枝，得到簡化版本的剪枝決策樹。

預剪枝的核心思想是在樹中結點進行擴展之前，先計算當前的劃分是否能夠帶來模型泛化能力的提升，如果不能，則不再進行生長子樹。此時可能存在不同類別的樣本同時存在於結點中，按照多數投票的原則判斷該結點所屬類別，預剪枝對於何時停止決策樹的生長有以下幾種方法：

1 當樹達到一定深度的時候，停止樹的生長。

2 當到達當前結點的樣本數量小於某個閾值的時候，停止樹的生長。

3 計算每次分裂對測試集的準確度提升，當小於某個閾值的時候，不再繼續擴展。

預剪枝具有思想直接，算法簡單，效率高效等特點，適合解決大規模問題，但是如何準確的估計何時停止樹的生長，針對不同的問題會有很大的差別，需要一定的經驗判斷。而且預剪枝存在一定的侷限性，有欠擬合的風險，雖然當前的劃分會導致測試集準確率降低，但在之後的劃分中，準確率有可能會有顯著的上升。

後剪枝的核心思想是讓算法生成一顆完全生長的決策樹，然後從最底層向上計算是否剪枝。剪枝過程將子樹刪除，用一個葉子結點替代該結點的類別同一按照多數投票的原則進行判斷，同樣地，後剪枝也可以通過在測試集上的準確率進行判斷，如果剪枝過後準確率有所提升，則進行剪枝，相比於預剪枝，後剪枝方法通常可以得到泛化能力更強的決策樹，但是時間開銷會更大。

常見的後剪枝方法有錯誤率降低剪枝，悲觀剪枝，代價複雜度剪枝，最小誤差剪枝，CVP，OOP等方法，這些剪枝方法各有利弊，關注不同的優化角度。

剪枝過程在決策樹模型中佔有及其重要的位置，很多研究表明剪枝比樹的生成過程更爲關鍵，對於不同劃分標準生成的過擬合決策樹，在經過剪枝之後都能保留最重要的屬性劃分，因此最終的性能差距並不大。理解剪枝方法的理論，在實際應用中根據不同的數據類型，規模決定使用何種決策樹以及對應的剪枝策略，靈活變通，找到最優解決方案。