機器學(xué)習(xí)基礎(chǔ)：可視化方式理解決策樹剪枝

看了一些市面上的經(jīng)典教材，感覺決策樹剪枝這一部分講的都特別晦澀，很不好理解。本文以理論白話+具體案例的形式來講清楚這個重要知識點，打好決策樹這個基礎(chǔ)，有助于理解之后我們要講解的隨機森林、gbdt、xgboost、lightgbm等模型。

閱讀本文前，可以順便回顧一下前文：機器學(xué)習(xí)基礎(chǔ)：決策樹的可視化

剪枝

如果不對決策樹設(shè)置任何限制，它可以生成一顆非常龐大的樹，決策樹的樹葉節(jié)點所覆蓋的訓(xùn)練樣本都是“純”的。這樣決策樹在訓(xùn)練樣本上非常精準，但是在測試集上就沒那么好了。
層數(shù)越多，葉結(jié)點越多，分的越細致，對訓(xùn)練數(shù)據(jù)分的也越深，越容易過擬合，導(dǎo)致對測試數(shù)據(jù)預(yù)測時反而效果差。要解決這個問題就需要對決策樹進行「剪枝」。

剪枝的方案主流的有兩種，一種是預(yù)剪枝，一種是后剪枝。

所謂的預(yù)剪枝，即是在生成樹的時候就對樹的生長進行限制，防止過度擬合。比如我們可以限制決策樹在訓(xùn)練的時候每個節(jié)點的數(shù)據(jù)只有在達到一定數(shù)量的情況下才會進行分裂，否則就成為葉子節(jié)點保留?；蛘呶覀兛梢韵拗茢?shù)據(jù)的比例，當(dāng)節(jié)點中某個類別的占比超過閾值的時候，也可以停止生長。

下面我們重點講后剪枝，因為CART采用的就是用的這個方法。

CART剪枝算法流程

CART樹采用的是后剪枝方法，即先從訓(xùn)練集生成一顆完整的決策樹，然后自底向上地對非葉結(jié)點進行考察，若將該結(jié)點對應(yīng)的子樹替換為葉結(jié)點能帶來泛化性能提升，則將該子樹替換為葉結(jié)點。

李航老師《統(tǒng)計學(xué)習(xí)方法》中具體介紹了 CART 剪枝算法的步驟流程。

看起來是不是很復(fù)雜？其實核心思想就是對原始的決策時T0，從底部根節(jié)點不斷向上剪枝，直到根節(jié)點為止。在此過程中，就形成了很多子樹{T0，T1，...，Tn}；然后通過交叉驗證法在驗證集上對{T0，T1，...，Tn}測試，從中選擇最優(yōu)子樹。

怎么度量最優(yōu)呢？就要先了解一下決策樹損失函數(shù)：

剪枝前是以 t 為根結(jié)點的子樹 Tt 的損失函數(shù)是：

C(Tt)為訓(xùn)練數(shù)據(jù)的預(yù)測誤差，分類樹是用基尼系數(shù)度量，回歸樹是均方差度量。|Tt|是子樹T的葉子節(jié)點的數(shù)量。式中唯一的未知變量是正則化參數(shù) α ，其值越大，就意味著剪枝力度越大。當(dāng) α 從 0 慢慢增大到 ∞ 時，最優(yōu)子樹會慢慢從最開始的整體樹，一點一點剪枝，直到變成單結(jié)點樹。對于固定的 α，一定存在損失函數(shù)Cα(T)最小的子樹，我們稱之為最優(yōu)子樹，記為 Tα 。

兩種剪枝策略對比

后剪枝決策樹通常比預(yù)剪枝決策樹保留了更多的分支；
后剪枝決策樹的欠擬合風(fēng)險很小，泛化性能往往優(yōu)于預(yù)剪枝決策樹；
后剪枝決策樹訓(xùn)練時間開銷比未剪枝決策樹和預(yù)剪枝決策樹都要大的多。其實，只需掌握后剪枝就行了。

CART決策樹剪枝（參數(shù)解讀）

sklearn.tree.DecisionTreeClassifier (criterion=’gini’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

• max_depth：限制樹的最大深度

決策樹多生長一層，對樣本量的需求會增加一倍，所以限制樹深度能夠有效地限制過擬合。在高維度低樣本量時非常有效；建議從=3開始嘗試。

• min_samples_leaf：一個節(jié)點在分枝后，每個子節(jié)點都必須至少包含的訓(xùn)練樣本數(shù)量

一個節(jié)點在分枝后，每個子節(jié)點都必須包含至少min_samples_leaf個訓(xùn)練樣本，兩種取值：（1）整數(shù) （2）浮點型：如果葉節(jié)點中含有的樣本量變化很大，輸入浮點數(shù)表示樣本量的百分比。如果分支后的子節(jié)點不滿足參數(shù)條件，分枝就不會發(fā)生，或者，分枝會朝著滿足每個子節(jié)點都包含min_samples_leaf個樣本的方向去發(fā)生。

這個參數(shù)可以保證每個葉子的最小尺寸，在回歸問題中避免低方差，過擬合的葉子節(jié)點出現(xiàn)。搭配max_depth使用，在回歸樹中可以讓模型變得更加平滑；建議從=5開始；對于類別不多的分類問題，=1通常就是最佳選擇。

• min_samples_split：一個節(jié)點必須要至少包含的訓(xùn)練樣本數(shù)量

如果小于這個數(shù)量，這個節(jié)點才允許被分枝，否則分枝就不會發(fā)生。

• max_features：分枝時考慮的最大特征個數(shù)

即在分支時，超過限制個數(shù)的特征都會被舍棄。但是在不知道決策樹中的各個特征的重要性的情況下，強行設(shè)定這個參數(shù)可能會導(dǎo)致模型學(xué)習(xí)不足。

• min_impurity_decrease：子父節(jié)點信息增益的最小值

信息增益是父節(jié)點的信息熵與子節(jié)點信息熵之差，信息增益越大，說明這個分支對模型的貢獻越大；相反的，如果信息增益非常小，則說明該分支對模型的建立貢獻不大。又由于分支需要的計算量又非常大，所以如果信息增益非常小時，我們就選擇放棄該分支。

以上便是剪枝常用到的參數(shù)了。

實例

如果不對決策樹設(shè)置任何限制，生成結(jié)果如下：每個葉子結(jié)點gini指數(shù)都等于 0 。

iris?=?load_iris()
clf?=?tree.DecisionTreeClassifier(random_state=66,min_samples_leaf=15)
clf?=?clf.fit(iris.data,?iris.target)

dot_data?=?tree.export_graphviz(clf,?out_file=None,?
?????????????????????????feature_names=iris.feature_names,??
?????????????????????????class_names=iris.target_names,??
?????????????????????????filled=True,?rounded=True,??
?????????????????????????special_characters=True)??
graph?=?pydotplus.graph_from_dot_data(dot_data)??
Image(graph.create_png())

設(shè)置葉子節(jié)點最少樣本數(shù)min_samples_leaf=15，這個值限制了葉子節(jié)點最少的樣本數(shù)，如果某葉子節(jié)點數(shù)目小于樣本數(shù)，則會和兄弟節(jié)點一起被剪枝。