簡介
決策樹是當下使用的最流行的非線性架構之一。目前為止，我們學過的支援向量機和廣義線性都是線性模型的例子，核心化則是通過映射特征ϕ得出非線性假設函數。決策樹因其對噪聲的魯棒性和學習析取表達式的能力而聞名。實際上，決策樹已被廣泛運用于貸款申請人的信用風險測評中。
決策樹使用二進制規則将輸入映射到輸出y。從自上而下的角度，樹中的每個節點都有一個拆分規則。在最底部，每個葉節點輸出一個值或一個類。注意，輸出可以重複。每個拆分規則可以表征為：
對于某些次元和，我們可以從葉節點了解到預測結果。以下是一個決策樹的例子：
決策樹種類
與傳統預測模型類似，決策樹可以分為分類樹和回歸樹。分類樹用于對輸入進行分類，而回歸樹通過回歸輸出真實數值作為預測結果。
回歸樹
在這種情況下，決策樹的運作就像是對空間進行分割，并以此對結果進行預測。例如，我們有一個二維輸入空間，在這個空間内我們可以單獨對每個次元進行劃分，并為某個區域提供回歸值。具體可以參考下圖的左側。
回歸樹事實上是一個如上圖中的右側的樹形結構。為了預測，我們将配置設定給它們的相應路徑。在3D空間中，上面的回歸樹在3D空間中的分割是階梯式的，如下圖所示。
分類樹
讓我們看一下分類決策樹的例子。假設我們有兩個特征作為輸入，三個類标簽作為輸出，定義上也就是說 and ，在圖中我們可以看到：
現在，我們可以從第一個特征開始下手。那麼我們選擇1.7作為要分割的門檻值。是以，我們可以：
輸出的決策樹可以描述為：
我們可以對輸入的第二個特征執行類似的操作。我們在第二特征空間選擇另一個門檻值，其結果是：
生成的決策樹可以顯示為：
上述步驟顯示了從輸入空間建構分類決策樹的流程。
決策樹學習算法
在本節中，我們将讨論這兩種類型決策樹的學習算法。通常，學習樹使用自上而下的貪婪算法。在此算法中，我們從單個節點開始，找出可以最大程度上降低不确定性的門檻值。我們重複這一過程，直到找到所有的門檻值。
回歸樹學習算法
回到例子中：
在左圖中，我們有五個區域，兩個輸入特征和四個門檻值。讓我們推廣到個區域。那麼我們的預測公式可以是：
其中是所屬的區域，是預測值。
目标是盡量減少：
我們先來看看定義。這裡我們有兩個變量需要确定，，其中為預測結果。那麼如果基于給定的，我們是否可以更容易地預測呢？答案是肯定的。我們可以簡單地求出将該區域所有樣本的平均值，作為。現在的問題是：我們如何找出這些區域？
初始區域通常是整個資料集，首先我們在次元j的門檻值處分割一個區域。我們可以定義。那麼，對于每個次元，我們計算并找到最佳分裂點。我們應該為每個現有的區域（葉節點）執行此操作，并根據定義好的度量标準選擇出最佳區域分割。
簡而言之，我們需要選擇一個區域（葉節點），然後選擇一個特征，再之後選擇一個門檻值來形成一個新的分割。
分類樹學習算法
在回歸樹任務中，我們使用了平方誤差來确定分割規則的品質。在分類任務中，我們則有更多的選擇來評估分割品質。
總的來說，在決策樹生長中有三種常見的分類測量方法。
1, 分類誤差：
2, 基尼指數：
3, 資訊熵：
其中代表每個類的經驗機率（empirical portion），k表示類索引。對于二進制分類，如果我們繪制出每次評估相對于的值，我們可以看到：
這證明了：
1, 當在中的類上是均勻分布時，所有評估都是最大化的
2, 當或 0 時，所有評估都被最小化
一般而言，我們希望最大化原始損失與分割區域的基數權重損之差。定義上講，
然而，不同的損失函數各有利弊。對于分類誤差類型，它的問題是對分割區域的變化不敏感。例如，如果我們組成一個父區域，請看下圖：
雖然以上兩個分割是不同的，不過我們可以發現：
我們注意到，如果我們使用分類誤差類型，不同的拆分結果也會計算出相同的損失值。此外，我們還看到新的分割區域不會減少原始損失。這是因為，嚴格上來講，分類誤差損失并非凹函數（concave function）。是以，如果我們繪制上面的分割示例，我們可以看到：
從上圖中，我們看出分類誤差損失對我們并沒有多大的幫助。另一方面，如果我們使用資訊熵損失，在圖中的顯示則與其不同。
從圖中可以看出，我們使用資訊熵損失方法分割父區域後，得到的損失将減少。這是因為熵函數是凹函數。
讓我們看一個示例，這個示例将使用索引作為損失函數來生成分類樹。讓我們假設我們有一個2D空間，空間中繪制了一些分類點。圖像如下面所示：
在這種情況下，左邊區域被分類為标簽1。我們可以看到它被近似完美地分類，那麼我們可以确定對該區域的測量應該是不錯的。
區域2的話，由于基尼指數并不為零，我們需要下更多功夫。如果我們計算基尼指數，我們可以：
接下來，我們希望看到不同軸上不同位置的分割點如何根據某些評估函數影響該區域的基尼指數。這樣的評估函數，即不确定性函數，可以是：
其中是中的的占比，是新區域的基尼指數。那麼，我們希望新的分割區域的基尼指數為零。是以，我們希望最大化原始區域的基尼指數與新區域基尼指數的權重和之差。是以，我們希望将基尼指數上的減少量設為，不同的分裂點設為，并繪制出函數。
對于上面的例子，首先我們沿着水準軸來檢視不同的分裂點。
你可以看到圖的兩側有兩個明顯的切口，這是因為小于大約1.7左右的點屬于标簽1，大約在2.9之後就沒有任何點了。我們還可以嘗試通過沿另一個軸（即垂直軸）滑動來觀察結果。
從圖中可以看出，垂直分裂點在值為2.7附近有最大的改進。那麼，我們可以将資料樣本拆分為：
最終的決策樹：
正規化
那麼問題來了，我們什麼時候選擇停止決策樹的生長呢？當然，你可以說當葉子隻包含一種标簽時，我們就停止訓練。然而，這将導緻高方差和低偏差問題，也就是說過度拟合。一些現有的解決方式如下所示：
1，最小葉子結點大小：我們可以設定最小葉子結點大小。
2，最大深度：我們還可以在樹深度上設定門檻值。
3，最大節點數：當樹中的節點數達到葉節點的門檻值時，我們可以停止訓練。
然而，即便我們可以使用這些方法以避免過度拟合，仍然很難訓練一個在一般情況下表現良好的決策樹。是以，我們将在另一部分筆記中講解一種稱為內建方法的訓練技術。
缺少累加結構
在每個決策樹節點的決策階段，決策規則隻能有一個，且規則隻能基于某一個特征而制定。這個特征隻能從現有的兩個特征(x1 或 x2)中選擇，而不能用另一個建立的特征。這将會為決策樹帶來一些問題。如下圖所示，我們必須在每個軸上設定多個分裂點以保證準确性，因為每次隻允許分割一個特征空間。這就是為什麼下圖中總是出現平行線的原因。
但是，通過累加結構，我們可以很容易地繪制出此圖的線性邊界。