六、決策樹(shù)

譯者：@Lisanaaa、@y3534365

校對者：@飛龍、@YuWang

和支持向量機一樣， 決策樹(shù)是一種多功能機器學(xué)習算法， 即可以執行分類(lèi)任務(wù)也可以執行回歸任務(wù)， 甚至包括多輸出（multioutput）任務(wù).

它是一種功能很強大的算法，可以對很復雜的數據集進(jìn)行擬合。例如，在第二章中我們對加利福尼亞住房數據集使用決策樹(shù)回歸模型進(jìn)行訓練，就很好的擬合了數據集（實(shí)際上是過(guò)擬合）。

決策樹(shù)也是隨機森林的基本組成部分（見(jiàn)第 7 章），而隨機森林是當今最強大的機器學(xué)習算法之一。

在本章中，我們將首先討論如何使用決策樹(shù)進(jìn)行訓練，可視化和預測。

然后我們會(huì )學(xué)習在 Scikit-learn 上面使用 CART 算法，并且探討如何調整決策樹(shù)讓它可以用于執行回歸任務(wù)。

最后，我們當然也需要討論一下決策樹(shù)目前存在的一些局限性。

決策樹(shù)的訓練和可視化

為了理解決策樹(shù)，我們需要先構建一個(gè)決策樹(shù)并親身體驗它到底如何進(jìn)行預測。

接下來(lái)的代碼就是在我們熟知的鳶尾花數據集上進(jìn)行一個(gè)決策樹(shù)分類(lèi)器的訓練。

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)

你可以通過(guò)使用 export_graphviz()方法，通過(guò)生成一個(gè)叫做 iris_tree.dot的圖形定義文件將一個(gè)訓練好的決策樹(shù)模型可視化。

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"即可
參見(jiàn)https://github.com/ageron/handson-ml/blob/master/06_decision_trees.ipynb

然后，我們可以利用 graphviz package [1] 中的 dot命令行，將 .dot文件轉換成 PDF 或 PNG 等多種數據格式。例如，使用命令行將 .dot文件轉換成 .png文件的命令如下：

[1] Graphviz是一款開(kāi)源圖形可視化軟件包，http://www.graphviz.org/。

$ dot -Tpng iris_tree.dot -o iris_tree.png

我們的第一個(gè)決策樹(shù)如圖 6-1。

開(kāi)始預測

現在讓我們來(lái)看看在圖 6-1 中的樹(shù)是如何進(jìn)行預測的。假設你找到了一朵鳶尾花并且想對它進(jìn)行分類(lèi)，你從根節點(diǎn)開(kāi)始（深度為 0，頂部）：該節點(diǎn)詢(xún)問(wèn)花朵的花瓣長(cháng)度是否小于 2.45 厘米。如果是，您將向下移動(dòng)到根的左側子節點(diǎn)（深度為 1，左側）。 在這種情況下，它是一片葉子節點(diǎn)（即它沒(méi)有任何子節點(diǎn)），所以它不會(huì )問(wèn)任何問(wèn)題：你可以方便地查看該節點(diǎn)的預測類(lèi)別，決策樹(shù)預測你的花是 Iris-Setosa（class = setosa）。

現在假設你找到了另一朵花，但這次的花瓣長(cháng)度是大于 2.45 厘米的。你必須向下移動(dòng)到根的右側子節點(diǎn)（深度為 1，右側），而這個(gè)節點(diǎn)不是葉節點(diǎn)，所以它會(huì )問(wèn)另一個(gè)問(wèn)題：花瓣寬度是否小于 1.75 厘米？ 如果是，那么你的花很可能是一個(gè) Iris-Versicolor（深度為 2，左）。 如果不是，那很可能一個(gè) Iris-Virginica（深度為 2，右），真的是太簡(jiǎn)單了，對吧！

決策樹(shù)的眾多特性之一就是， 它不需要太多的數據預處理， 尤其是不需要進(jìn)行特征的縮放或者歸一化。

節點(diǎn)的 samples屬性統計出它應用于多少個(gè)訓練樣本實(shí)例。

例如，我們有一百個(gè)訓練實(shí)例是花瓣長(cháng)度大于 2.45 里面的（深度為 1， 右側），在這 100 個(gè)樣例中又有 54 個(gè)花瓣寬度小于 1.75cm（深度為 2，左側）。

節點(diǎn)的 value屬性告訴你這個(gè)節點(diǎn)對于每一個(gè)類(lèi)別的樣例有多少個(gè)。

例如：右下角的節點(diǎn)中包含 0 個(gè) Iris-Setosa，1 個(gè) Iris-Versicolor 和 45 個(gè) Iris-Virginica。

最后，節點(diǎn)的 Gini屬性用于測量它的純度：如果一個(gè)節點(diǎn)包含的所有訓練樣例全都是同一類(lèi)別的，我們就說(shuō)這個(gè)節點(diǎn)是純的（Gini=0）。

例如，深度為 1 的左側節點(diǎn)只包含 Iris-Setosa 訓練實(shí)例，它就是一個(gè)純節點(diǎn)，Gini 指數為 0。

公式 6-1 顯示了訓練算法如何計算第 i個(gè)節點(diǎn)的 gini 分數 G_i。例如， 深度為 2 的左側節點(diǎn)基尼指數為：$1-(0/54)^2-(49/54)^2-(5/54)^2=0.68$。另外一個(gè)純度指數也將在后文很快提到。
Equation 6-1. Gini impurity
G_i=1 - \sum_{k=1}^{n}P^2{i,k}

• p_{i,k}是第 i個(gè)節點(diǎn)中訓練實(shí)例為的k類(lèi)實(shí)例的比例

Scikit-Learn 用的是 CART 算法， CART 算法僅產(chǎn)生二叉樹(shù)：每一個(gè)非葉節點(diǎn)總是只有兩個(gè)子節點(diǎn)（只有是或否兩個(gè)結果）。然而，像 ID3 這樣的算法可以產(chǎn)生超過(guò)兩個(gè)子節點(diǎn)的決策樹(shù)模型。

圖 6-2 顯示了決策樹(shù)的決策邊界。粗的垂直線(xiàn)代表根節點(diǎn)（深度為 0）的決定邊界：花瓣長(cháng)度為 2.45 厘米。由于左側區域是純的（只有 Iris-Setosa），所以不能再進(jìn)一步分裂。然而，右邊的區域是不純的，所以深度為 1 的右邊節點(diǎn)在花瓣寬度為 1.75 厘米處分裂（用虛線(xiàn)表示）。又由于 max_depth設置為 2，決策樹(shù)在那里停了下來(lái)。但是，如果將 max_depth設置為 3，兩個(gè)深度為 2 的節點(diǎn)，每個(gè)都將會(huì )添加另一個(gè)決策邊界（用虛線(xiàn)表示）。

模型小知識：白盒與黑盒

正如我們看到的一樣，決策樹(shù)非常直觀(guān)，他們的決定很容易被解釋。這種模型通常被稱(chēng)為白盒模型。相反，隨機森林或神經(jīng)網(wǎng)絡(luò )通常被認為是黑盒模型。他們能做出很好的預測，并且您可以輕松檢查它們做出這些預測過(guò)程中計算的執行過(guò)程。然而，人們通常很難用簡(jiǎn)單的術(shù)語(yǔ)來(lái)解釋為什么模型會(huì )做出這樣的預測。例如，如果一個(gè)神經(jīng)網(wǎng)絡(luò )說(shuō)一個(gè)特定的人出現在圖片上，我們很難知道究竟是什么導致了這一個(gè)預測的出現：

模型是否認出了那個(gè)人的眼睛？ 她的嘴？ 她的鼻子？她的鞋？或者是否坐在沙發(fā)上？ 相反，決策樹(shù)提供良好的、簡(jiǎn)單的分類(lèi)規則，甚至可以根據需要手動(dòng)操作（例如鳶尾花分類(lèi)）。

估計分類(lèi)概率

決策樹(shù)還可以估計某個(gè)實(shí)例屬于特定類(lèi) k的概率：首先遍歷樹(shù)來(lái)查找此實(shí)例的葉節點(diǎn)，然后它返回此節點(diǎn)中類(lèi) k的訓練實(shí)例的比例。

例如，假設你發(fā)現了一個(gè)花瓣長(cháng) 5 厘米，寬 1.5 厘米的花朵。相應的葉節點(diǎn)是深度為 2 的左節點(diǎn)，因此決策樹(shù)應該輸出以下概率：Iris-Setosa 為 0%（0/54），Iris-Versicolor 為 90.7%（49/54），Iris-Virginica 為 9.3%（5/54）。當然，如果你要求它預測具體的類(lèi)，它應該輸出 Iris-Versicolor（類(lèi)別 1），因為它具有最高的概率。我們了測試一下：

>>> tree_clf.predict_proba([[5, 1.5]])
array([[ 0. , 0.90740741, 0.09259259]])
>>> tree_clf.predict([[5, 1.5]])
array([1])

完美！請注意，估計概率在任何地方都是相同的， 除了圖 6-2 中右下角的矩形部分，例如花瓣長(cháng) 6 厘米和寬 1.5 厘米（盡管在這種情況下它看起來(lái)很可能是 Iris-Virginica）。

CART 訓練算法

Scikit-Learn 用分裂回歸樹(shù)（Classification And Regression Tree，簡(jiǎn)稱(chēng) CART）算法訓練決策樹(shù)（也叫“增長(cháng)樹(shù)”）。這種算法思想真的非常簡(jiǎn)單：

首先使用單個(gè)特征 k和閾值 t_k]將訓練集分成兩個(gè)子集。它如何選擇 k和 t_k呢？它尋找到能夠產(chǎn)生最純粹的子集一對 (k, t_k)，然后通過(guò)子集大小加權計算。

算法會(huì )嘗試最小化成本函數。方法如公式 6-2

當它成功的將訓練集分成兩部分之后， 它將會(huì )繼續使用相同的遞歸式邏輯繼續的分割子集，然后是子集的子集。當達到預定的最大深度之后將會(huì )停止分裂（由 max_depth超參數決定），或者是它找不到可以繼續降低不純度的分裂方法的時(shí)候。幾個(gè)其他超參數（之后介紹）控制了其他的停止生長(cháng)條件（min_samples_split，min_samples_leaf，min_weight_fraction_leaf，max_leaf_nodes）。

正如您所看到的，CART 算法是一種貪婪算法：它貪婪地搜索最高級別的最佳分割方式，然后在每個(gè)深度重復該過(guò)程。 它不檢查分割是否能夠在幾個(gè)級別中的全部分割可能中找到最佳方法。貪婪算法通常會(huì )產(chǎn)生一個(gè)相當好的解決方法，但它不保證這是全局中的最佳解決方案。

不幸的是，找到最優(yōu)樹(shù)是一個(gè) NP 完全問(wèn)題（自行百度）：它需要 O(exp^m) 時(shí)間，即使對于相當小的訓練集也會(huì )使問(wèn)題變得棘手。 這就是為什么我們必須設置一個(gè)“合理的”（而不是最佳的）解決方案。

計算復雜度

在建立好決策樹(shù)模型后， 做出預測需要遍歷決策樹(shù)， 從根節點(diǎn)一直到葉節點(diǎn)。決策樹(shù)通常近似左右平衡，因此遍歷決策樹(shù)需要經(jīng)歷大致 O(log_2m)[2] 個(gè)節點(diǎn)。由于每個(gè)節點(diǎn)只需要檢查一個(gè)特征的值，因此總體預測復雜度僅為 O(log_2m)，與特征的數量無(wú)關(guān)。 所以即使在處理大型訓練集時(shí)，預測速度也非?？?。

[2] log_2 是二進(jìn)制對數，它等于 log_2 (m) = log(m) / log(2)。

然而，訓練算法的時(shí)候（訓練和預測不同）需要比較所有特征（如果設置了 max_features會(huì )更少一些）

在每個(gè)節點(diǎn)的所有樣本上。就有了 O(n×m log(m)) 的訓練復雜度。對于小型訓練集（少于幾千例），Scikit-Learn 可以通過(guò)預先設置數據（presort = True）來(lái)加速訓練，但是這對于較大訓練集來(lái)說(shuō)會(huì )顯著(zhù)減慢訓練速度。

基尼不純度或是信息熵

通常，算法使用 Gini 不純度來(lái)進(jìn)行檢測， 但是你也可以通過(guò)將標準超參數設置為 "entropy"來(lái)使用熵不純度進(jìn)行檢測。這里熵的概念是源于熱力學(xué)中分子混亂程度的概念，當分子井然有序的時(shí)候，熵值接近于 0。

熵這個(gè)概念后來(lái)逐漸被擴展到了各個(gè)領(lǐng)域，其中包括香農的信息理論，這個(gè)理論被用于測算一段信息中的平均信息密度 [3]。當所有信息相同的時(shí)候熵被定義為零。

在機器學(xué)習中，熵經(jīng)常被用作不純度的衡量方式，當一個(gè)集合內只包含一類(lèi)實(shí)例時(shí)， 我們稱(chēng)為數據集的熵為 0。

[3] 熵的減少通常稱(chēng)為信息增益。

公式 6-3 顯示了第 i個(gè)節點(diǎn)的熵的定義，例如，在圖 6-1 中， 深度為 2 左節點(diǎn)的熵為 -49/54log(49/54)-5/54log(5/54)=0.31。

Equation 6-3. Entropy

那么我們到底應該使用 Gini 指數還是熵呢？ 事實(shí)上大部分情況都沒(méi)有多大的差別：他們會(huì )生成類(lèi)似的決策樹(shù)。

基尼指數計算稍微快一點(diǎn)，所以這是一個(gè)很好的默認值。但是，也有的時(shí)候它們會(huì )產(chǎn)生不同的樹(shù)，基尼指數會(huì )趨于在樹(shù)的分支中將最多的類(lèi)隔離出來(lái)，而熵指數趨向于產(chǎn)生略微平衡一些的決策樹(shù)模型。

正則化超參數

決策樹(shù)幾乎不對訓練數據做任何假設（于此相反的是線(xiàn)性回歸等模型，這類(lèi)模型通常會(huì )假設數據是符合線(xiàn)性關(guān)系的）。

如果不添加約束，樹(shù)結構模型通常將根據訓練數據調整自己，使自身能夠很好的擬合數據，而這種情況下大多數會(huì )導致模型過(guò)擬合。

這一類(lèi)的模型通常會(huì )被稱(chēng)為非參數模型，這不是因為它沒(méi)有任何參數（通常也有很多），而是因為在訓練之前沒(méi)有確定參數的具體數量，所以模型結構可以根據數據的特性自由生長(cháng)。

于此相反的是，像線(xiàn)性回歸這樣的參數模型有事先設定好的參數數量，所以自由度是受限的，這就減少了過(guò)擬合的風(fēng)險（但是增加了欠擬合的風(fēng)險）。

DecisionTreeClassifier類(lèi)還有一些其他的參數用于限制樹(shù)模型的形狀:

min_samples_split（節點(diǎn)在被分裂之前必須具有的最小樣本數），min_samples_leaf（葉節點(diǎn)必須具有的最小樣本數），min_weight_fraction_leaf（和 min_samples_leaf相同，但表示為加權總數的一小部分實(shí)例），max_leaf_nodes（葉節點(diǎn)的最大數量）和max_features（在每個(gè)節點(diǎn)被評估是否分裂的時(shí)候，具有的最大特征數量）。增加 min_* hyperparameters或者減少 max_* hyperparameters會(huì )使模型正則化。

一些其他算法的工作原理是在沒(méi)有任何約束條件下訓練決策樹(shù)模型，讓模型自由生長(cháng)，然后再對不需要的節點(diǎn)進(jìn)行剪枝。

當一個(gè)節點(diǎn)的全部子節點(diǎn)都是葉節點(diǎn)時(shí)，如果它對純度的提升不具有統計學(xué)意義，我們就認為這個(gè)分支是不必要的。

標準的假設檢驗，例如卡方檢測，通常會(huì )被用于評估一個(gè)概率值 -- 即改進(jìn)是否純粹是偶然性的結果（也叫原假設）

如果 p 值比給定的閾值更高（通常設定為 5%，也就是 95% 置信度，通過(guò)超參數設置），那么節點(diǎn)就被認為是非必要的，它的子節點(diǎn)會(huì )被刪除。

這種剪枝方式將會(huì )一直進(jìn)行，直到所有的非必要節點(diǎn)都被刪光。

圖 6-3 顯示了對 moons數據集（在第 5 章介紹過(guò)）進(jìn)行訓練生成的兩個(gè)決策樹(shù)模型，左側的圖形對應的決策樹(shù)使用默認超參數生成（沒(méi)有限制生長(cháng)條件），右邊的決策樹(shù)模型設置為 min_samples_leaf=4。很明顯，左邊的模型過(guò)擬合了，而右邊的模型泛用性更好。

回歸

決策樹(shù)也能夠執行回歸任務(wù)，讓我們使用 Scikit-Learn 的 DecisionTreeRegressor類(lèi)構建一個(gè)回歸樹(shù)，讓我們用 max_depth = 2在具有噪聲的二次項數據集上進(jìn)行訓練。

from sklearn.tree import DecisionTreeRegressor
tree_reg = DecisionTreeRegressor(max_depth=2)
tree_reg.fit(X, y)

結果如圖 6-4 所示

這棵樹(shù)看起來(lái)非常類(lèi)似于你之前建立的分類(lèi)樹(shù)，它的主要區別在于，它不是預測每個(gè)節點(diǎn)中的樣本所屬的分類(lèi)，而是預測一個(gè)具體的數值。例如，假設您想對 x_1 = 0.6的新實(shí)例進(jìn)行預測。從根開(kāi)始遍歷樹(shù)，最終到達預測值等于 0.1106 的葉節點(diǎn)。該預測僅僅是與該葉節點(diǎn)相關(guān)的 110 個(gè)訓練實(shí)例的平均目標值。而這個(gè)預測結果在對應的 110 個(gè)實(shí)例上的均方誤差（MSE）等于 0.0151。

在圖 6-5 的左側顯示的是模型的預測結果，如果你將 max_depth=3設置為 3，模型就會(huì )如 6-5 圖右側顯示的那樣.注意每個(gè)區域的預測值總是該區域中實(shí)例的平均目標值。算法以一種使大多數訓練實(shí)例盡可能接近該預測值的方式分割每個(gè)區域。

譯者注：圖里面的紅線(xiàn)就是訓練實(shí)例的平均目標值，對應上圖中的 value

CART 算法的工作方式與之前處理分類(lèi)模型基本一樣，不同之處在于，現在不再以最小化不純度的方式分割訓練集，而是試圖以最小化 MSE 的方式分割訓練集。

公式 6-4 顯示了成本函數，該算法試圖最小化這個(gè)成本函數。

和處理分類(lèi)任務(wù)時(shí)一樣，決策樹(shù)在處理回歸問(wèn)題的時(shí)候也容易過(guò)擬合。如果不添加任何正則化（默認的超參數），你就會(huì )得到圖 6-6 左側的預測結果，顯然，過(guò)度擬合的程度非常嚴重。而當我們設置了 min_samples_leaf = 10，相對就會(huì )產(chǎn)生一個(gè)更加合適的模型了，就如圖 6-6 所示的那樣。

不穩定性

我希望你現在了解了決策樹(shù)到底有哪些特點(diǎn)：

它很容易理解和解釋?zhuān)子谑褂们夜δ茇S富而強大。然而，它也有一些限制，首先，你可能已經(jīng)注意到了，決策樹(shù)很喜歡設定正交化的決策邊界，（所有邊界都是和某一個(gè)軸相垂直的），這使得它對訓練數據集的旋轉很敏感，例如圖 6-7 顯示了一個(gè)簡(jiǎn)單的線(xiàn)性可分數據集。在左圖中，決策樹(shù)可以輕易的將數據分隔開(kāi)，但是在右圖中，當我們把數據旋轉了 45° 之后，決策樹(shù)的邊界看起來(lái)變的格外復雜。盡管兩個(gè)決策樹(shù)都完美的擬合了訓練數據，右邊模型的泛化能力很可能非常差。

解決這個(gè)難題的一種方式是使用 PCA 主成分分析（第八章），這樣通常能使訓練結果變得更好一些。

更加通俗的講，決策時(shí)的主要問(wèn)題是它對訓練數據的微小變化非常敏感，舉例來(lái)說(shuō)，我們僅僅從鳶尾花訓練數據中將最寬的 Iris-Versicolor 拿掉（花瓣長(cháng) 4.8 厘米，寬 1.8 厘米），然后重新訓練決策樹(shù)模型，你可能就會(huì )得到圖 6-8 中的模型。正如我們看到的那樣，決策樹(shù)有了非常大的變化（原來(lái)的如圖 6-2），事實(shí)上，由于 Scikit-Learn 的訓練算法是非常隨機的，即使是相同的訓練數據你也可能得到差別很大的模型（除非你設置了隨機數種子）。

我們下一章中將會(huì )看到，隨機森林可以通過(guò)多棵樹(shù)的平均預測值限制這種不穩定性。