{% raw %} # 六、決策樹 > 譯者：[@Lisanaaa](https://github.com/Lisanaaa)、[@y3534365](https://github.com/y3534365) > > 校對者：[@飛龍](https://github.com/wizardforcel)、[@YuWang](https://github.com/bigeyex) 和支持向量機一樣， 決策樹是一種多功能機器學習算法， 即可以執行分類任務也可以執行回歸任務， 甚至包括多輸出（multioutput）任務. 它是一種功能很強大的算法，可以對很復雜的數據集進行擬合。例如，在第二章中我們對加利福尼亞住房數據集使用決策樹回歸模型進行訓練，就很好的擬合了數據集（實際上是過擬合）。 決策樹也是隨機森林的基本組成部分（見第 7 章），而隨機森林是當今最強大的機器學習算法之一。 在本章中，我們將首先討論如何使用決策樹進行訓練，可視化和預測。 然后我們會學習在 Scikit-learn 上面使用 CART 算法，并且探討如何調整決策樹讓它可以用于執行回歸任務。 最后，我們當然也需要討論一下決策樹目前存在的一些局限性。 ## 決策樹的訓練和可視化 為了理解決策樹，我們需要先構建一個決策樹并親身體驗它到底如何進行預測。 接下來的代碼就是在我們熟知的鳶尾花數據集上進行一個決策樹分類器的訓練。 ```python from sklearn.datasets import load_iris from sklearn.tree import DecisionTreeClassifier iris = load_iris() X = iris.data[:, 2:] # petal length and width y = iris.target tree_clf = DecisionTreeClassifier(max_depth=2) tree_clf.fit(X, y) ``` 你可以通過使用`export_graphviz()`方法，通過生成一個叫做`iris_tree.dot`的圖形定義文件將一個訓練好的決策樹模型可視化。 ```python from sklearn.tree import export_graphviz export_graphviz( tree_clf, out_file=image_path("iris_tree.dot"), feature_names=iris.feature_names[2:], class_names=iris.target_names, rounded=True, filled=True ) ``` > 譯者注：原文中的image_path用于獲得示例程序的相對路徑。這里直接去掉改成`out_file="iris_tree.dot"`即可 > 參見https://github.com/ageron/handson-ml/blob/master/06_decision_trees.ipynb 然后，我們可以利用`graphviz package` [1] 中的`dot`命令行，將`.dot`文件轉換成 PDF 或 PNG 等多種數據格式。例如，使用命令行將`.dot`文件轉換成`.png`文件的命令如下： > [1] Graphviz是一款開源圖形可視化軟件包，<http://www.graphviz.org/>。 ``` $ dot -Tpng iris_tree.dot -o iris_tree.png ``` 我們的第一個決策樹如圖 6-1。  ## 開始預測 現在讓我們來看看在圖 6-1 中的樹是如何進行預測的。假設你找到了一朵鳶尾花并且想對它進行分類，你從根節點開始（深度為 0，頂部）：該節點詢問花朵的花瓣長度是否小于 2.45 厘米。如果是，您將向下移動到根的左側子節點（深度為 1，左側）。 在這種情況下，它是一片葉子節點（即它沒有任何子節點），所以它不會問任何問題：你可以方便地查看該節點的預測類別，決策樹預測你的花是 Iris-Setosa（`class = setosa`）。 現在假設你找到了另一朵花，但這次的花瓣長度是大于 2.45 厘米的。你必須向下移動到根的右側子節點（深度為 1，右側），而這個節點不是葉節點，所以它會問另一個問題：花瓣寬度是否小于 1.75 厘米？ 如果是，那么你的花很可能是一個 Iris-Versicolor（深度為 2，左）。 如果不是，那很可能一個 Iris-Virginica（深度為 2，右），真的是太簡單了，對吧！ > 決策樹的眾多特性之一就是， 它不需要太多的數據預處理， 尤其是不需要進行特征的縮放或者歸一化。 節點的`samples`屬性統計出它應用于多少個訓練樣本實例。 例如，我們有一百個訓練實例是花瓣長度大于 2.45 里面的（深度為 1， 右側），在這 100 個樣例中又有 54 個花瓣寬度小于 1.75cm（深度為 2，左側）。 節點的`value`屬性告訴你這個節點對于每一個類別的樣例有多少個。 例如：右下角的節點中包含 0 個 Iris-Setosa，1 個 Iris-Versicolor 和 45 個 Iris-Virginica。 最后，節點的`Gini`屬性用于測量它的純度：如果一個節點包含的所有訓練樣例全都是同一類別的，我們就說這個節點是純的（`Gini=0`）。 例如，深度為 1 的左側節點只包含 Iris-Setosa 訓練實例，它就是一個純節點，Gini 指數為 0。 公式 6-1 顯示了訓練算法如何計算第`i`個節點的 gini 分數 。例如， 深度為 2 的左側節點基尼指數為：。另外一個純度指數也將在后文很快提到。  -  是第`i`個節點中訓練實例為的`k`類實例的比例 > Scikit-Learn 用的是 CART 算法， CART 算法僅產生二叉樹：每一個非葉節點總是只有兩個子節點（只有是或否兩個結果）。然而，像 ID3 這樣的算法可以產生超過兩個子節點的決策樹模型。 圖 6-2 顯示了決策樹的決策邊界。粗的垂直線代表根節點（深度為 0）的決定邊界：花瓣長度為 2.45 厘米。由于左側區域是純的（只有 Iris-Setosa），所以不能再進一步分裂。然而，右邊的區域是不純的，所以深度為 1 的右邊節點在花瓣寬度為 1.75 厘米處分裂（用虛線表示）。又由于`max_depth`設置為 2，決策樹在那里停了下來。但是，如果將`max_depth`設置為 3，兩個深度為 2 的節點，每個都將會添加另一個決策邊界（用虛線表示）。  > 模型小知識：白盒與黑盒 > > 正如我們看到的一樣，決策樹非常直觀，他們的決定很容易被解釋。這種模型通常被稱為白盒模型。相反，隨機森林或神經網絡通常被認為是黑盒模型。他們能做出很好的預測，并且您可以輕松檢查它們做出這些預測過程中計算的執行過程。然而，人們通常很難用簡單的術語來解釋為什么模型會做出這樣的預測。例如，如果一個神經網絡說一個特定的人出現在圖片上，我們很難知道究竟是什么導致了這一個預測的出現： > > 模型是否認出了那個人的眼睛？ 她的嘴？ 她的鼻子？她的鞋？或者是否坐在沙發上？ 相反，決策樹提供良好的、簡單的分類規則，甚至可以根據需要手動操作（例如鳶尾花分類）。 ## 估計分類概率 決策樹還可以估計某個實例屬于特定類`k`的概率：首先遍歷樹來查找此實例的葉節點，然后它返回此節點中類`k`的訓練實例的比例。 例如，假設你發現了一個花瓣長 5 厘米，寬 1.5 厘米的花朵。相應的葉節點是深度為 2 的左節點，因此決策樹應該輸出以下概率：Iris-Setosa 為 0%（0/54），Iris-Versicolor 為 90.7%（49/54），Iris-Virginica 為 9.3%（5/54）。當然，如果你要求它預測具體的類，它應該輸出 Iris-Versicolor（類別 1），因為它具有最高的概率。我們了測試一下： ```python >>> tree_clf.predict_proba([[5, 1.5]]) array([[ 0. , 0.90740741, 0.09259259]]) >>> tree_clf.predict([[5, 1.5]]) array([1]) ``` 完美！請注意，估計概率在任何地方都是相同的， 除了圖 6-2 中右下角的矩形部分，例如花瓣長 6 厘米和寬 1.5 厘米（盡管在這種情況下它看起來很可能是 Iris-Virginica）。 ## CART 訓練算法 Scikit-Learn 用分裂回歸樹（Classification And Regression Tree，簡稱 CART）算法訓練決策樹（也叫“增長樹”）。這種算法思想真的非常簡單： 首先使用單個特征`k`和閾值 （例如，“花瓣長度`≤2.45cm`”）將訓練集分成兩個子集。它如何選擇`k`和  呢？它尋找到能夠產生最純粹的子集一對 ，然后通過子集大小加權計算。 算法會嘗試最小化成本函數。方法如公式 6-2  當它成功的將訓練集分成兩部分之后， 它將會繼續使用相同的遞歸式邏輯繼續的分割子集，然后是子集的子集。當達到預定的最大深度之后將會停止分裂（由`max_depth`超參數決定），或者是它找不到可以繼續降低不純度的分裂方法的時候。幾個其他超參數（之后介紹）控制了其他的停止生長條件（`min_samples_split`，`min_samples_leaf`，`min_weight_fraction_leaf`，`max_leaf_nodes`）。 > 正如您所看到的，CART 算法是一種貪婪算法：它貪婪地搜索最高級別的最佳分割方式，然后在每個深度重復該過程。 它不檢查分割是否能夠在幾個級別中的全部分割可能中找到最佳方法。貪婪算法通常會產生一個相當好的解決方法，但它不保證這是全局中的最佳解決方案。 不幸的是，找到最優樹是一個 NP 完全問題（自行百度）：它需要  時間，即使對于相當小的訓練集也會使問題變得棘手。 這就是為什么我們必須設置一個“合理的”（而不是最佳的）解決方案。 ## 計算復雜度 在建立好決策樹模型后， 做出預測需要遍歷決策樹， 從根節點一直到葉節點。決策樹通常近似左右平衡，因此遍歷決策樹需要經歷大致  [2] 個節點。由于每個節點只需要檢查一個特征的值，因此總體預測復雜度僅為 ，與特征的數量無關。 所以即使在處理大型訓練集時，預測速度也非常快。 > [2]  是二進制對數，它等于 。 然而，訓練算法的時候（訓練和預測不同）需要比較所有特征（如果設置了`max_features`會更少一些） 在每個節點的所有樣本上。就有了  的訓練復雜度。對于小型訓練集（少于幾千例），Scikit-Learn 可以通過預先設置數據（`presort = True`）來加速訓練，但是這對于較大訓練集來說會顯著減慢訓練速度。 ## 基尼不純度或是信息熵 通常，算法使用 Gini 不純度來進行檢測， 但是你也可以通過將標準超參數設置為`"entropy"`來使用熵不純度進行檢測。這里熵的概念是源于熱力學中分子混亂程度的概念，當分子井然有序的時候，熵值接近于 0。 熵這個概念后來逐漸被擴展到了各個領域，其中包括香農的信息理論，這個理論被用于測算一段信息中的平均信息密度 [3]。當所有信息相同的時候熵被定義為零。 在機器學習中，熵經常被用作不純度的衡量方式，當一個集合內只包含一類實例時， 我們稱為數據集的熵為 0。 > [3] 熵的減少通常稱為信息增益。 公式 6-3 顯示了第`i`個節點的熵的定義，例如，在圖 6-1 中， 深度為 2 左節點的熵為 。  那么我們到底應該使用 Gini 指數還是熵呢？ 事實上大部分情況都沒有多大的差別：他們會生成類似的決策樹。 基尼指數計算稍微快一點，所以這是一個很好的默認值。但是，也有的時候它們會產生不同的樹，基尼指數會趨于在樹的分支中將最多的類隔離出來，而熵指數趨向于產生略微平衡一些的決策樹模型。 ## 正則化超參數 決策樹幾乎不對訓練數據做任何假設（于此相反的是線性回歸等模型，這類模型通常會假設數據是符合線性關系的）。 如果不添加約束，樹結構模型通常將根據訓練數據調整自己，使自身能夠很好的擬合數據，而這種情況下大多數會導致模型過擬合。 這一類的模型通常會被稱為非參數模型，這不是因為它沒有任何參數（通常也有很多），而是因為在訓練之前沒有確定參數的具體數量，所以模型結構可以根據數據的特性自由生長。 于此相反的是，像線性回歸這樣的參數模型有事先設定好的參數數量，所以自由度是受限的，這就減少了過擬合的風險（但是增加了欠擬合的風險）。 `DecisionTreeClassifier`類還有一些其他的參數用于限制樹模型的形狀: > `min_samples_split`（節點在被分裂之前必須具有的最小樣本數），`min_samples_leaf`（葉節點必須具有的最小樣本數），`min_weight_fraction_leaf`（和`min_samples_leaf`相同，但表示為加權總數的一小部分實例），`max_leaf_nodes`（葉節點的最大數量）`和max_features`（在每個節點被評估是否分裂的時候，具有的最大特征數量）。增加`min_* hyperparameters`或者減少`max_* hyperparameters`會使模型正則化。 > > 一些其他算法的工作原理是在沒有任何約束條件下訓練決策樹模型，讓模型自由生長，然后再對不需要的節點進行剪枝。 > > 當一個節點的全部子節點都是葉節點時，如果它對純度的提升不具有統計學意義，我們就認為這個分支是不必要的。 > > 標準的假設檢驗，例如卡方檢測，通常會被用于評估一個概率值 -- 即改進是否純粹是偶然性的結果（也叫原假設） > > 如果 p 值比給定的閾值更高（通常設定為 5%，也就是 95% 置信度，通過超參數設置），那么節點就被認為是非必要的，它的子節點會被刪除。 > > 這種剪枝方式將會一直進行，直到所有的非必要節點都被刪光。 圖 6-3 顯示了對`moons`數據集（在第 5 章介紹過）進行訓練生成的兩個決策樹模型，左側的圖形對應的決策樹使用默認超參數生成（沒有限制生長條件），右邊的決策樹模型設置為`min_samples_leaf=4`。很明顯，左邊的模型過擬合了，而右邊的模型泛用性更好。  ## 回歸 決策樹也能夠執行回歸任務，讓我們使用 Scikit-Learn 的`DecisionTreeRegressor`類構建一個回歸樹，讓我們用`max_depth = 2`在具有噪聲的二次項數據集上進行訓練。 ```python from sklearn.tree import DecisionTreeRegressor tree_reg = DecisionTreeRegressor(max_depth=2) tree_reg.fit(X, y) ``` 結果如圖 6-4 所示  這棵樹看起來非常類似于你之前建立的分類樹，它的主要區別在于，它不是預測每個節點中的樣本所屬的分類，而是預測一個具體的數值。例如，假設您想對  的新實例進行預測。從根開始遍歷樹，最終到達預測值等于 0.1106 的葉節點。該預測僅僅是與該葉節點相關的 110 個訓練實例的平均目標值。而這個預測結果在對應的 110 個實例上的均方誤差（MSE）等于 0.0151。 在圖 6-5 的左側顯示的是模型的預測結果，如果你將`max_depth=3`設置為 3，模型就會如 6-5 圖右側顯示的那樣.注意每個區域的預測值總是該區域中實例的平均目標值。算法以一種使大多數訓練實例盡可能接近該預測值的方式分割每個區域。 > 譯者注：圖里面的紅線就是訓練實例的平均目標值，對應上圖中的`value`  CART 算法的工作方式與之前處理分類模型基本一樣，不同之處在于，現在不再以最小化不純度的方式分割訓練集，而是試圖以最小化 MSE 的方式分割訓練集。 公式 6-4 顯示了成本函數，該算法試圖最小化這個成本函數。  和處理分類任務時一樣，決策樹在處理回歸問題的時候也容易過擬合。如果不添加任何正則化（默認的超參數），你就會得到圖 6-6 左側的預測結果，顯然，過度擬合的程度非常嚴重。而當我們設置了`min_samples_leaf = 10`，相對就會產生一個更加合適的模型了，就如圖 6-6 所示的那樣。  ## 不穩定性 我希望你現在了解了決策樹到底有哪些特點： 它很容易理解和解釋，易于使用且功能豐富而強大。然而，它也有一些限制，首先，你可能已經注意到了，決策樹很喜歡設定正交化的決策邊界，（所有邊界都是和某一個軸相垂直的），這使得它對訓練數據集的旋轉很敏感，例如圖 6-7 顯示了一個簡單的線性可分數據集。在左圖中，決策樹可以輕易的將數據分隔開，但是在右圖中，當我們把數據旋轉了 45° 之后，決策樹的邊界看起來變的格外復雜。盡管兩個決策樹都完美的擬合了訓練數據，右邊模型的泛化能力很可能非常差。 解決這個難題的一種方式是使用 PCA 主成分分析（第八章），這樣通常能使訓練結果變得更好一些。  更加通俗的講，決策時的主要問題是它對訓練數據的微小變化非常敏感，舉例來說，我們僅僅從鳶尾花訓練數據中將最寬的 Iris-Versicolor 拿掉（花瓣長 4.8 厘米，寬 1.8 厘米），然后重新訓練決策樹模型，你可能就會得到圖 6-8 中的模型。正如我們看到的那樣，決策樹有了非常大的變化（原來的如圖 6-2），事實上，由于 Scikit-Learn 的訓練算法是非常隨機的，即使是相同的訓練數據你也可能得到差別很大的模型（除非你設置了隨機數種子）。  我們下一章中將會看到，隨機森林可以通過多棵樹的平均預測值限制這種不穩定性。 ## 練習 1. 在 100 萬例訓練集上訓練（沒有限制）的決策樹的近似深度是多少？ 2. 節點的基尼指數比起它的父節點是更高還是更低？它是通常情況下更高/更低，還是永遠更高/更低？ 3. 如果決策樹過擬合了，減少最大深度是一個好的方法嗎？ 4. 如果決策樹對訓練集欠擬合了，嘗試縮放輸入特征是否是一個好主意？ 5. 如果對包含 100 萬個實例的數據集訓練決策樹模型需要一個小時，在包含 1000 萬個實例的培訓集上訓練另一個決策樹大概需要多少時間呢？ 6. 如果你的訓練集包含 100,000 個實例，設置`presort=True`會加快訓練的速度嗎？ 7. 對`moons`數據集進行決策樹訓練并優化模型。 1. 通過語句`make_moons(n_samples=10000, noise=0.4)`生成`moons`數據集 2. 通過`train_test_split()`將數據集分割為訓練集和測試集。 3. 進行交叉驗證，并使用網格搜索法尋找最好的超參數值（使用`GridSearchCV`類的幫助文檔） 提示: 嘗試各種各樣的`max_leaf_nodes`值 4. 使用這些超參數訓練全部的訓練集數據，并在測試集上測量模型的表現。你應該獲得大約 85% 到 87% 的準確度。 8. 生成森林 1. 接著前邊的練習，現在，讓我們生成 1,000 個訓練集的子集，每個子集包含 100 個隨機選擇的實例。提示：你可以使用 Scikit-Learn 的`ShuffleSplit`類。 2. 使用上面找到的最佳超參數值，在每個子集上訓練一個決策樹。在測試集上測試這 1000 個決策樹。由于它們是在較小的集合上進行了訓練，因此這些決策樹可能會比第一個決策樹效果更差，只能達到約 80% 的準確度。 3. 見證奇跡的時刻到了！對于每個測試集實例，生成 1,000 個決策樹的預測結果，然后只保留出現次數最多的預測結果（您可以使用 SciPy 的`mode()`函數）。這個函數使你可以對測試集進行多數投票預測。 4. 在測試集上評估這些預測結果，你應該獲得了一個比第一個模型高一點的準確率，（大約 0.5% 到 1.5%），恭喜，你已經弄出了一個隨機森林分類器模型! {% endraw %}