決策樹的優化-剪枝

爲什麼決策樹需要剪枝？我們可以類比於神經網絡的「過擬合」問題來進行思考。在神經網絡之中，會出現過擬合問題，即出思安對特定的樣本識別率升高，對其餘樣本的識別率降低。在決策樹中也會出現類似的問題，會出現枝條過多的現象，是問題複雜化，準確率卻得不到上升。

決策樹的剪枝分爲2種，一種是預剪枝，第二種是後剪枝。

預剪枝：在創建進行到某一個節點處，我們先計算當前節點的準確率，然後在按照該節點的屬性進行分類，在計算分類後的準確率，比較和，如果較大則該節點不需要進一步的分枝，否則如果較大則該節點需要進行分枝操作。

後剪枝：首先我們要有一顆完整的決策樹，然後從該決策樹的葉子節點的父節點開始，分別計算該父節點不分枝的準確率和分枝後的準確率，繼續和預剪枝的一樣的操作，決定是否進行剪枝操作，然後向上尋找，逐個判斷。

例子：

我們拿臍部作爲節點進行說明，臍部的好瓜有{4,5,8}共3個，壞瓜有{9,11,12,13}共4個，準確率爲3/7，大概爲42.9%。

分枝後我們有凹陷，稍凹，平坦三個屬性。我們認爲凹陷與稍凹是好的，平坦是壞的。凹陷有{4,5,13}共3個，其中2個判斷正確。稍凹有{8,9}共2個，1個判斷正確。平坦有{11,12}共2個，2個判斷正確。故最終準確率爲5/7，大概爲71.4%，大於42.9%，故該節點進行分枝操作。