機器學習：對決策樹剪枝
昨天推送中介紹了決策樹的基本思想，包括從衆多特徵中找出最佳的分裂點，剛開始大家都是用選擇這個特徵後帶來的信息增益爲基本方法，後來發現它存在一個嚴重的bug，因此提出來了信息增益率（即還要除以分裂出來的那些節點對應的自身熵的和），再後來，又提出來一個與熵概念類似的基尼係數，根據這些理論和訓練數據可以構建出一顆大樹了。但是這顆大樹的泛化能力一般，需要進行剪枝操作才能提升泛化能力，那麼常用的剪枝策略都有哪些呢。
01 這真的好嗎？
一個在訓練數據集上可以取得100%的準確率的分類器，一定很好嗎？未必好，因爲它在測試集上的測試結果未必好，又因爲分類器的好壞最重要的是要看在測試集上的表現效果。
那麼問題來了，爲什麼它在測試集上的效果就不好呢？ 試想這樣一種極端情況，我們手上有100個水果，其中包括三類：香蕉，蘋果，杏，它們常用的區分特徵比如：形狀，大小，外觀等，假如我們啓用了一個非常特殊的特徵，恰好把這100個水果樣本對應到了100個葉子節點，也就是說每個葉子都還有唯一的一個樣本，這在訓練集上的準確率一定是100%呀，但是在測試集上呢，第101個水果在這個極其特殊的特徵上，都有可能不在原100個特徵取值內，所以你根本找不到它的對應，所以它不屬於這100個葉子中之一。
當然，這個極端的例子雖然未必能在實際訓練測試中遇到，但是它卻很好的解釋了選擇合適的特徵，並且避免葉子節點過多，同時防止過多的葉子節點包含的樣本數過少的現象，纔是決策樹在測試集上表現良好的重要考量。
同時，還有一個因素也得考量，昨天推送分析過，決策樹本質上是 if-else的多層嵌套，每個遞歸構建的新的分裂點（節點）都會不斷地降低不純度（熵），最終在葉子節點上，不純度降爲0，但是，一個葉子節點的深度如果很大，說明經過的 if 就非常多，這樣就需要苛刻的條件才能滿足這個很深的葉子節點（即這個類別），言外之意，它缺少必要的泛化能力，測試集的數據有可能不會走到這裏。
爲了解決以上通過訓練構建出的決策樹的深度過大，葉子節點過多，葉子節點含有的樣本數過少的問題（實際上就是一棵樹多餘的樹枝），就需要想辦法剪去這些樹枝，從而得到一棵不高不胖的決策樹。
02 怎麼剪枝
上面談到了決策樹剪枝的必要性，通過剪枝提高，測試集上的數據在構建好的決策樹上找到自己對應所屬的葉子節點，即找到自己的對應分類。
應該怎麼做剪枝呢？ 一種思路是在衆多特徵中貪心地選擇最佳的信息增益率的那個特徵作爲根節點，依次遞歸地進行這種操作，在進行到某步操作時，發現樹的深度大於指定的深度了，此時這一枝遞歸返回；
或者發現此時已形成的葉子節點已經達到指定的最多葉子節點數，也遞歸返回；
或者發現某個分裂點（節點）的樣本數已經小於了指定的節點含有的最少樣本數時，也遞歸返回。
以上就是常用的在構建決策樹時的同時，進行剪枝操作，因爲是同時做，時間複雜度小，這種做法稱爲：預剪枝。
還有，等決策樹建立好了，我再修修補補一下，怎麼修補？看看那些葉子節點的父節點，好，如果我這個父節點不分裂，是不是泛化誤差會更小些呢，如果是這樣，我就沒有必要分裂了吧。
那麼這種情況下，該父節點是否分裂有沒有量化的公式呢：
其中 Tleaf 表示葉子節點的數目；
C(Node)表示某個節點的基尼係數乘以樣本數。
這樣比較下分裂Or不分裂誰的C值小，就選擇誰，這種方法就是後剪枝，顯然這種算法是在決策樹構建完後，再花時間去剪枝，時間上肯定沒有一邊建立樹，一邊剪枝的效率高。
03 可視化決策樹
下面我們在sklearn中，可視化決策樹，同時關鍵是要理解以上幾種剪枝策略。
我們直接用sklearn提供的一個數據集首先生成一棵不帶剪枝策略的樹，代碼如下：
#導入iris數據集
from sklearn.datasets import load_iris
from sklearn import tree
iris = load_iris()
#創建決策樹分類器
clf = tree.DecisionTreeClassifier()
#訓練
clf = clf.fit(iris.data, iris.target)
#graphviz 可視化樹
import graphviz
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 = graphviz.Source(dot_data)
生成的決策樹如下所示，每個節點包括的數據結構如下：
-
分類的不等式
-
基尼係數
-
樣本個數
-
每個類別的樣本數list
-
這個節點的類別
我們看到這棵樹，樹的深度，葉子節點數都很大，每個葉子節點含有的樣本數有的只有1個樣本，明顯需要剪枝，下面看下剪枝參數如何設置。
04 剪枝決策樹
clf = tree.DecisionTreeClassifier()這個構建決策樹的構造函數，帶有參數常用的包括如下：
-
criterion='gini', 選用基尼係數作爲選擇特徵的分裂點
-
max_depth=None, 樹的最大深度
-
min_samples_split=2, 分裂點的樣本個數
-
min_samples_leaf =1, 葉子節點的樣本個數
-
max_leaf_nodes=None，最大的葉子節點數
可以看到這個構造函數的參數，都包括了以上闡述的預剪枝的策略，sklearn強大。
如果參數的max_depth = 4，那麼得到的決策樹如下所示：
05 總結
以上我們分析了爲什麼需要對決策樹剪枝，以及常見的剪枝策略都有哪些，以及在sklearn中如何可視化決策樹，以及如何利用超參數剪枝決策樹。
目前決策樹都是用於數據集的分類的，那麼決策樹可不可以用於迴歸呢？
在用決策樹迴歸時，存在以上所謂的剪枝操作或者有沒有過擬合的風險呢？又怎麼避免？ 歡迎關注明天的推送。
讓我們看一下遠邊的大海，和巍峨的高山，放鬆一下吧！
歡迎關注《算法channel》
交流思想，注重分析，看重過程，包含但不限於：經典算法，機器學習，深度學習，LeetCode 題解，Kaggle 實戰，英語沙龍，定期邀請專家發推。期待您的到來！