為何要剪枝

決策樹遞歸地構(gòu)建樹，直到不能繼續(xù)分裂下去為止，這樣的樹對(duì)于訓(xùn)練集可能擬合的較好，但對(duì)于訓(xùn)練集可能產(chǎn)生過擬合現(xiàn)象，原因是過多的考慮對(duì)訓(xùn)練集的劃分精確度，從而構(gòu)建出了復(fù)雜的決策樹，緩解過擬合的方法是通過剪枝。

剪枝的思想

剪枝是通過極小化決策樹整體的損失函數(shù)或代價(jià)函數(shù)來實(shí)現(xiàn)的

剪枝的過程即在構(gòu)建新的模型，因此，可以將剪枝看作是模型選擇的一種方法。

預(yù)剪枝

通過提前停止樹的構(gòu)造來對(duì)決策樹進(jìn)行剪枝
一旦停止該節(jié)點(diǎn)下樹的繼續(xù)構(gòu)造，該節(jié)點(diǎn)就成了葉節(jié)點(diǎn)
該葉節(jié)點(diǎn)持有其數(shù)據(jù)集中樣本最多的類或者其概率分布。

后剪枝

先構(gòu)建完整的決策樹，允許決策樹過度擬合訓(xùn)練數(shù)據(jù)。
然后對(duì)那些置信度不夠的節(jié)點(diǎn)的子樹用葉節(jié)點(diǎn)來替代
該葉節(jié)點(diǎn)持有其子樹的數(shù)據(jù)集中樣本最多的類或者其概率分布。

后剪枝CCP

目前在CART、gbdt等集成樹模型中的剪枝方法是后剪枝，重點(diǎn)關(guān)注CCP剪枝的流程。

計(jì)算時(shí)，之所以選擇min(a, g(t))是因?yàn)閍=g(t)，同時(shí)g(t)又表達(dá)每一個(gè)葉節(jié)點(diǎn)能帶來的誤差減小量，那么每次迭代選擇誤差減少量最少的那一個(gè)進(jìn)行剪枝，因?yàn)檎`差減少量很少，則代表決策樹此時(shí)沒必要花力氣向下生長。

轉(zhuǎn)載注明：http://www.itdecent.cn/p/ff73374ebe6a