決策樹1：初識決策樹

2019 年 12 月 23 日
筆記

決策樹是一個非常有意思的模型，它的建模思路是儘可能模擬人做決策的過程。因此決策樹幾乎沒有任何抽象，完全通過生成決策規則來解決分類和回歸問題。因為它的運行機制能很直接地被翻譯成人類語言，即使對建模領域完全不了解的非技術人員也能很好地理解它。因此在學術上被歸為白盒模型（white box model）。

0x01 決策樹的思想

1.1 什麼是決策樹

決策樹是一種常見的機器學習算法，它的思想十分樸素，類似於我們平時利用選擇做決策的過程。它是類似流程圖的結構，其中每個內部節點表示一個測試功能，即類似做出決策的過程（動作），每個葉節點都表示一個類標籤，即在計算所有特徵之後做出的決定（結果）。標籤和分支表示導致這些類標籤的功能的連接。從根到葉的路徑表示分類規則。比如下面這個「相親決策樹」：

由此我們可以看到，決策樹的思想還是非常直觀的。

用決策樹分類：從根節點開始，對實例的某一特徵進行測試，根據測試結果將實例分配到其子節點，此時每個子節點對應着該特徵的一個取值，如此遞歸的對實例進行測試並分配，直到到達葉節點，最後將實例分到葉節點的類中。

1.2 決策樹與條件概率

在前面已經從直觀上了解決策樹，及其構造步驟了。現在從統計學的角度對決策樹進行定義能夠能好地幫助我們理解模型。

決策樹表示給定特徵條件下，類的條件概率分佈，這個條件概率分佈表示在特徵空間的劃分上，將特徵空間根據各個特徵值不斷進行劃分，就將特徵空間分為了多個不相交的單元，在每個單元定義了一個類的概率分佈，這樣，這條由根節點到達葉節點的路徑就成了一個條件概率分佈。

假設X表示特徵的隨機變量，Y表示類的隨機變量，那麼這個條件概率可以表示為，其中X取值於給定劃分下單元的集合，Y取值於類的集合。各葉結點（單元）上的條件概率往往偏向某一個類。根據輸入的測試樣本，由路徑找到對應單元的各個類的條件概率，並將該輸入測試樣本分為條件概率最大的一類中，就可以完成對測試樣本的分類。

下圖a，表示了特種空間的一個劃分。大正方形表示特徵空間。這個大正方形被若干個小矩形分割，每個小矩形表示一個單元。特徵空間劃分上的單元構成了一個集合，X取值為單元的集合。假設只有兩類正類負類，Y=+1 OR -1；小矩形中的數字表示單元的類。

下圖b表示特徵空間（圖a）劃分確定時，特徵（劃分單元）給定條件下類的條件概率分佈。圖b中的條件概率分佈對應於圖a的劃分；當某個單元C的條件概率滿足時，即認為該類屬於正類，落在該單元的實例都視為正例。

下圖c表示了根節點到各個葉子結點上不同劃分的條件分佈。

在理解了相關概念之後，提出兩個問題：

特徵空間的劃分是如何確定的？（根據一系列的評價係數確認分類特徵？）
該條件概率分佈的概率值是如何確定的？（根據各點數據集歸納出的分類規則？）

0x02 決策樹的學習

2.1 學習目標與本質

假設給定訓練數據集，其中為輸入實例（特徵向量），n為特徵個數，，，為類標記（label），，，，，N為樣本容量。

學習目標：根據給定的訓練數據集構建一個決策模型，使它能夠對實例進行正確的分類。

決策樹學習本質上是從訓練數據集中歸納出一組分類規則。與訓練數據集不相矛盾的決策樹（即能對訓練數據進行正確分類的決策樹）可能是0個或多個。我們需要找到一個與訓練數據矛盾較小的決策樹，同時具有很好的泛化能力。

從另一個角度看，決策樹學習是由訓練數據集估計條件概率模型。基於特徵空間劃分的類的條件概率模型有無窮多個。我們選擇的條件概率模型應該不僅對訓練數據有很好地擬合，而且對未知數據有很好地預測。

2.2 決策樹損失函數

與其他模型相同，決策樹學習用損失函數表示這一目標。決策樹學習的損失函數通常是正則化的極大似然函數。決策樹學習的策略是以損失函數為目標函數的最小化。

關於極大似然函數：極大似然法是屬於數理統計範疇，旨在由果溯因。把「極大似然估計」拆成三個詞：極大（最大的概率）、似然（看起來是這個樣子的）、估計（就是這個樣子的），連起來就是：大概率看起來是這樣的，那就是這樣。比如扔一枚骰子(骰子每個面上只標記1或2)，現在告訴你扔了n次骰子其中有k次朝上的是1；然後問你這個骰子標記為1的面所佔的比例w是多少?極大似然法的思想就是估計當w取值為多少的時候，k次朝上的可能性最大。具體計算方法就是對表達式求最大值，得到參數值估計值：一般就是對這個表達式求一階導=0(二階導<0)；這就是極大似然估計方法的原理：用使概率達到最大的那個概率值w來估計真實參數w。決策樹生成的過程可以理解成對決策樹模型的參數估計(就是基於特徵空間劃分的類的概率模型),根據訓練數據的特徵分佈，選擇使得模型最契合當前樣本分佈空間時的條件概率模型。

當損失函數確定以後，學習問題就變為在損失函數意義下選擇最優決策樹的問題。因為從所有可能的決策樹中選取最優決策樹是NP完全問題，所以現實中決策樹學習算法通常採用啟發式方法，近似求解這一最優化問題。這樣得到的決策樹是次最優的。

3 決策樹的構建

決策樹通常有三個步驟：

特徵選擇
決策樹的生成
決策樹的修剪

決策樹學習的算法通常是一個遞歸地選擇最優特徵，並根據該特徵對訓練數據進行分割，使得對各個子數據集有一個最好的分類的過程。這一過程對應着對特徵空間的劃分，也對應着決策樹的構建。

這一過程對應着對特徵空間的劃分，也對應着決策樹的構建。

開始：構建根節點，將所有訓練數據都放在根節點，選擇一個最優特徵，按照這一特徵將訓練數據集分割成子集，使得各個子集有一個在當前條件下最好的分類。
如果這些子集已經能夠被基本正確分類，那麼構建葉節點，並將這些子集分到所對應的葉子節點去。
如果還有子集不能夠被正確的分類，那麼就對這些子集選擇新的最優特徵，繼續對其進行分割，構建相應的節點，如此遞歸進行，直至所有訓練數據子集被基本正確的分類，或者沒有合適的特徵為止。
每個子集都被分到葉節點上，即都有了明確的類，這樣就生成了一顆決策樹。

以上方法就是決策樹學習中的特徵選擇和決策樹生成，這樣生成的決策樹可能對訓練數據有很好的分類能力，但對未知的測試數據卻未必有很好的分類能力，即可能發生過擬合現象。我們需要對已生成的樹自下而上進行剪枝，將樹變得更簡單，從而使其具有更好的泛化能力。具體地，就是去掉過於細分的葉結點，使其回退到父結點，甚至更高的結點，然後將父結點或更高的結點改為新的葉結點，從而使得模型有較好的泛化能力。。

決策樹生成和決策樹剪枝是個相對的過程，決策樹生成旨在得到對於當前子數據集最好的分類效果(局部最優)，而決策樹剪枝則是考慮全局最優，增強泛化能力。

在對此有一定了解之後，我們先看看，如何在sklearn中將決策樹用起來。然後再學習其中的細節。

0x04 sklearn中使用決策樹

4.1 數據引入及可視化

import numpy as npimport matplotlib.pyplot as pltfrom sklearn import datasets  iris = datasets.load_iris()X = iris.data[:,2:] # iris有四個特徵，這裡取後兩個，形成一個坐標點y = iris.target# 繪圖plt.scatter(X[y==0,0],X[y==0,1])plt.scatter(X[y==1,0],X[y==1,1])plt.scatter(X[y==2,0],X[y==2,1])plt.show()

4.2 進行分類

from sklearn.tree import DecisionTreeClassifier# 創建決策樹對象，最大深度max_depth為2層，criterion評判標準為entropy（熵）dt_clt = DecisionTreeClassifier(max_depth=2,criterion='entropy')# 將訓練數據送給模型dt_clt.fit(X,y)  # 繪製決策邊界def plot_decision_boundary(model, axis): # model是模型，axis是範圍    x0, x1 = np.meshgrid(        np.linspace(axis[0], axis[1],int((axis[1]-axis[0])*100)).reshape(-1,1),        np.linspace(axis[2], axis[3],int((axis[3]-axis[2])*100)).reshape(-1,1),    )    X_new = np.c_[x0.ravel(), x1.ravel()]      y_predict = model.predict(X_new)    zz = y_predict.reshape(x0.shape)      from matplotlib.colors import ListedColormap    custom_cmap = ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)  # 數據可視化    plot_decision_boundary(dt_clt, axis=[0.5,7.5,0,3])plt.scatter(X[y==0,0],X[y==0,1])plt.scatter(X[y==1,0],X[y==1,1])plt.scatter(X[y==2,0],X[y==2,1])plt.show()

4.3 總結&問題

對於上圖的數據可視化結果，我們可以直觀地看到。y=1.75這條直線為一條決策邊界，y大於1.75屬於A類；y小於1.75的區域，被y=0.8劃分，y<1.75||y>0.8屬於B類；y<0.8屬於C類。

決策樹是一個非參數的決策算法，決策樹可以解決分類問題，且天然支持多分類問題。決策樹也可以解決回歸問題，按照樹的路徑追蹤到葉子結點，最終葉子節點對應一個數值，且回歸問題的結果是一個具體的數值，就可以落在葉子結點的所有樣本的平均值，作為回歸的預測結果。

並且決策樹具有非常好的可解釋性。

那麼提出一個問題：在構建決策樹，進行特徵選擇劃分時，究竟選擇哪個特徵更好些？

這就要求確定選擇特徵的準則。直觀上，如果一個特徵具有更好的分類能力，或者說，按照這一特徵將訓練數據集分割成子集，使得各個子集在當前條件下有最好的分類，那麼就更應該選擇這個特徵。比如身高、長相、收入等。在找到特徵維度之後，還要確定劃分閾值，如收入定在多少，作為劃分標準比較合適？

因此，首先找到一個維度，然後在維度上找到一個閾值。然後以這個維度的這個閾值為依據進行劃分。核心問題是：

每個節點在哪個維度做劃分？選好了維度，如何確定閾值呢？