(第一部分 機器學習基礎) 第01章 機器學習概覽 第02章 一個完整的機器學習項目(上) 第02章 一個完整的機器學習項目(下) 第03章 分類 第04章 訓練模型 第05章 支援向量機 第06章 決策樹 第07章 內建學習和随機森林 第08章 降維 (第二部分 神經網絡和深度學習) 第9章 啟動和運作TensorFlow
和支援向量機一樣, 決策樹是一種多功能機器學習算法, 即可以執行分類任務也可以執行回歸任務, 甚至包括多輸出(multioutput)任務.
它是一種功能很強大的算法,可以對很複雜的資料集進行拟合。例如,在第二章中我們對加利福尼亞住房資料集使用決策樹回歸模型進行訓練,就很好的拟合了資料集(實際上是過拟合)。
決策樹也是随機森林的基本組成部分(見第7章),而随機森林是當今最強大的機器學習算法之一。
在本章中,我們将首先讨論如何使用決策樹進行訓練,可視化和預測。
然後我們會學習在 Scikit-learn 上面使用 CART 算法,并且探讨如何調整決策樹讓它可以用于執行回歸任務。
最後,我們當然也需要讨論一下決策樹目前存在的一些局限性。
決策樹的訓練和可視化
為了了解決策樹,我們需要先建構一個決策樹并親身體驗它到底如何進行預測。
接下來的代碼就是在我們熟知的鸢尾花資料集上進行一個決策樹分類器的訓練。
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
的圖形定義檔案将一個訓練好的決策樹模型可視化。
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
)
然後,我們可以利用
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. 鸢尾花決策樹
開始預測
現在讓我們來看看在圖 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 的左側節點基尼指數為:
。另外一個純度指數也将在後文很快提到。
公式6-1. Gini分數
- 是第
個節點中訓練執行個體為的i
類執行個體的比例k
Scikit-Learn 用的是 CART 算法, CART 算法僅産生二叉樹:每一個非葉節點總是隻有兩個子節點(隻有是或否兩個結果)。然而,像 ID3 這樣的算法可以産生超過兩個子節點的決策樹模型。
圖 6-2 顯示了決策樹的決策邊界。粗的垂直線代表根節點(深度為 0)的決策邊界:花瓣長度為 2.45 厘米。由于左側區域是純的(隻有 Iris-Setosa),是以不能再進一步分裂。然而,右邊的區域是不純的,是以深度為 1 的右邊節點在花瓣寬度為 1.75 厘米處分裂(用虛線表示)。又由于
max_depth
設定為 2,決策樹在那裡停了下來。但是,如果将
max_depth
設定為 3,兩個深度為 2 的節點,每個都将會添加另一個決策邊界(用虛線表示)。
圖6-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),因為它具有最高的機率。我們了測試一下:
>>> 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所示。
公式6-2. CART進行分類的損失函數
當它成功的将訓練集分成兩部分之後, 它将會繼續使用相同的遞歸式邏輯繼續的分割子集,然後是子集的子集。當達到預定的最大深度之後将會停止分裂(由
max_depth
超參數決定),或者是它找不到可以繼續降低不純度的分裂方法的時候。幾個其他超參數(之後介紹)控制了其他的停止生長條件(
min_samples_split
,
min_samples_leaf
min_weight_fraction_leaf
max_leaf_nodes
警告
正如所見,CART 算法是一種貪婪算法:它貪婪地搜尋最進階别的最佳分割方式,然後在每個深度重複該過程。 它不檢查分割是否能夠在幾個級别中的全部分割可能中找到最佳方法。貪婪算法通常會産生一個相當好的解決方法,但它不保證這是全局中的最佳解決方案。
不幸的是,找到最優樹是一個 NP 完全問題:它需要
時間,即使對于相當小的訓練集也會使問題變得棘手。 這就是為什麼我們必須設定一個“合理的”(而不是最佳的)解決方案。
計算複雜度
在建立好決策樹模型後, 做出預測需要周遊決策樹, 從根節點一直到葉節點。決策樹通常近似左右平衡,是以周遊決策樹需要經曆大緻
個節點。由于每個節點隻需要檢查一個特征的值,是以總體預測複雜度僅為
,與特征的數量無關。 是以即使在處理大型訓練集時,預測速度也非常快。
然而,訓練算法的時候(訓練和預測不同)需要比較所有特征(如果設定了
max_features
會更少一些)。這就使得訓練複雜度為
。對于小訓練集(少于幾千例),Scikit-Learn 可以通過預先設定資料(
presort = True
)來加速訓練,但是這對于較大訓練集來說會顯着減慢訓練速度。
Gini不純度或資訊熵
通常,算法使用 Gini 不純度來進行檢測, 但是你也可以通過将标準超參數設定為
"entropy"
來使用熵不純度進行檢測。這裡熵的概念是源于熱力學中分子混亂程度的概念,當分子井然有序的時候,熵值接近于 0。
熵這個概念後來逐漸被擴充到了各個領域,其中包括香農的資訊理論,這個理論被用于測算一段資訊中的平均資訊密度(熵的減少通常稱為資訊增益)。當所有資訊相同的時候熵被定義為零。
在機器學習中,熵經常被用作不純度的衡量方式,當一個集合内隻包含一類執行個體時, 我們稱為資料集的熵為 0。
公式 6-3 顯示了第
i
個節點的熵的定義,例如,在圖 6-1 中, 深度為 2 左節點的熵為
公式6-3. 熵
那麼我們到底應該使用 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
。很明顯,左邊的模型過拟合了,而右邊的模型泛用性更好。
圖6-3. 使用min_samples_leaf正則化
回歸
決策樹也能夠執行回歸任務,讓我們使用 Scikit-Learn 的
DecisionTreeRegressor
類建構一個回歸樹,讓我們用
max_depth = 2
在具有噪聲的二次項資料集上進行訓練。
from sklearn.tree import DecisionTreeRegressor
tree_reg = DecisionTreeRegressor(max_depth=2)
tree_reg.fit(X, y)
結果如圖 6-4 所示
圖6-4. 用決策樹進行回歸
這棵樹看起來非常類似于你之前建立的分類樹,它的主要差別在于,它不是預測每個節點中的樣本所屬的分類,而是預測一個具體的數值。例如,假設你想對
的新執行個體進行預測。從根開始周遊樹,最終到達預測值等于 0.1106 的葉節點。該預測僅僅是與該葉節點相關的 110 個訓練執行個體的平均目标值。而這個預測結果在對應的 110 個執行個體上的均方誤差(MSE)等于 0.0151。
在圖 6-5 的左側顯示的是模型的預測結果,如果你将
max_depth=3
設定為 3,模型就會如 6-5 圖右側顯示的那樣.注意每個區域的預測值總是該區域中執行個體的平均目标值。算法以一種使大多數訓練執行個體盡可能接近該預測值的方式分割每個區域。
譯者注:圖裡面的紅線就是訓練執行個體的平均目标值,對應上圖中的 value
圖6-5. 兩個決策樹回歸模型的預測
CART 算法的工作方式與之前處理分類模型基本一樣,不同之處在于,現在不再以最小化不純度的方式分割訓練集,而是試圖以最小化 MSE 的方式分割訓練集。
公式 6-4 顯示了該算法試圖最小化的損失函數。
和處理分類任務時一樣,決策樹在處理回歸問題的時候也容易過拟合。如果不添加任何正則化(預設的超參數),你就會得到圖 6-6 左側的預測結果,顯然,過度拟合的程度非常嚴重。而當我們設定了
min_samples_leaf = 10
,相對就會産生一個更加合适的模型了,就如圖 6-6 所示的那樣。
圖6-6. 正則化一個決策樹回歸器
不穩定性
我希望你現在了解了決策樹到底有哪些特點:
它很容易了解和解釋,易于使用且功能豐富而強大。然而,它也有一些限制,首先,你可能已經注意到了,決策樹很喜歡設定正交化的決策邊界,(所有邊界都是和某一個軸相垂直的),這使得它對訓練資料集的旋轉很敏感,例如圖 6-7 顯示了一個簡單的線性可分資料集。在左圖中,決策樹可以輕易的将資料分隔開,但是在右圖中,當我們把資料旋轉了 45° 之後,決策樹的邊界看起來變的格外複雜。盡管兩個決策樹都完美的拟合了訓練資料,右邊模型的泛化能力很可能非常差。
解決這個難題的一種方式是使用 PCA 主成分分析(第八章),這樣通常能使訓練結果變得更好一些。
圖6-7. 對訓練集資料旋轉的敏感性
更加通俗的講,決策時的主要問題是它對訓練資料的微小變化非常敏感,舉例來說,我們僅僅從鸢尾花訓練資料中将最寬的 Iris-Versicolor 拿掉(花瓣長 4.8 厘米,寬 1.8 厘米),然後重新訓練決策樹模型,你可能就會得到圖 6-8 中的模型。正如我們看到的那樣,決策樹有了非常大的變化(原來的如圖 6-2),事實上,由于 Scikit-Learn 的訓練算法是非常随機的,即使是相同的訓練資料你也可能得到差别很大的模型(除非你設定了随機數種子)。
圖6-8. 對訓練集細節的敏感性
我們下一章中将會看到,随機森林可以通過多棵樹的平均預測值限制這種不穩定性。
練習
- 在 有100 萬個執行個體的訓練集上訓練(沒有限制)的決策樹的深度大概是多少?
- 節點的基尼指數比起它的父節點是更高還是更低?它是通常情況下更高/更低,還是永遠更高/更低?
- 如果決策樹過拟合了,減少最大深度是一個好的方法嗎?
- 如果決策樹對訓練集欠拟合了,嘗試縮放輸入特征是否是一個好主意?
- 如果對包含 100 萬個執行個體的資料集訓練決策樹模型需要一個小時,在包含 1000 萬個執行個體的教育訓練集上訓練另一個決策樹大概需要多少時間呢?
- 如果你的訓練集包含 100,000 個執行個體,設定
會加快訓練的速度嗎?presort=True
- 對
資料集進行決策樹訓練并優化模型。moons
- 通過語句
生成make_moons(n_samples=10000, noise=0.4)
資料集moons
- 通過
将資料集分割為訓練集和測試集。train_test_split()
- 進行交叉驗證,并使用網格搜尋法尋找最好的超參數值(使用
GridSearchCV
類的幫助文檔)
提示: 嘗試各種各樣的
值max_leaf_nodes
- 使用這些超參數訓練全部的訓練集資料,并在測試集上測量模型的表現。你應該獲得大約 85% 到 87% 的準确度。
- 通過語句
- 生成森林
- 接着前邊的練習,現在,讓我們生成 1,000 個訓練集的子集,每個子集包含 100 個随機選擇的執行個體。提示:你可以使用 Scikit-Learn 的
類。ShuffleSplit
- 使用上面找到的最佳超參數值,在每個子集上訓練一個決策樹。在測試集上測試這 1000 個決策樹。由于它們是在較小的集合上進行了訓練,是以這些決策樹可能會比第一個決策樹效果更差,隻能達到約 80% 的準确度。
- 見證奇迹的時刻到了!對于每個測試集執行個體,生成 1,000 個決策樹的預測結果,然後隻保留出現次數最多的預測結果(您可以使用 SciPy 的
函數)。這個函數使你可以對測試集進行多數投票預測。mode()
- 在測試集上評估這些預測結果,你應該獲得了一個比第一個模型高一點的準确率,(大約 0.5% 到 1.5%),恭喜,你已經弄出了一個随機森林分類器模型!
- 接着前邊的練習,現在,讓我們生成 1,000 個訓練集的子集,每個子集包含 100 個随機選擇的執行個體。提示:你可以使用 Scikit-Learn 的