Lesson 8.1 決策樹的核心思想與建模流程

從本節課開始，我們將介紹經典機器學習領域中最重要的一類有監督學習算法——樹模型（決策樹）。

可此前的聚類算法類似，樹模型也同樣不是一個模型，而是一類模型的概稱。樹模型不僅運算效率高、模型判別能力強、而且原理簡單過程清晰、可解釋性強，是機器學習領域內為數不多的“白箱模型”。并且就樹模型本身的功能來說，除了能夠同時進行分類和回歸預測外，還能夠產出包括特征重要性、連續變量分箱指標等重要附加結論，而在集成學習中，最為常用的基礎分類器也正是樹模型。正是這些優勢，使得樹模型成為目前機器學習領域最為重要的模型之一。

一、借助邏輯回歸構建決策樹

那到底什么是樹模型？接下來我們簡單介紹樹模型建模的基本思想。

盡管樹模型作為經典模型，發展至今已是算法數量眾多、流派眾多，但大多數樹模型的基本思想其實是相通的，我們可以用一句話來解釋樹模型的模型形態和建模目標，那就是：挖掘有效分類規則并以樹狀形式呈現。接下來我們就以一個簡單實例進行說明，我們借助此前所學的基本建模知識，嘗試復現決策樹的基本分類思想。

# 科學計算模塊 import numpy as np import pandas as pd# 繪圖模塊 import matplotlib as mpl import matplotlib.pyplot as plt# 自定義模塊 from ML_basic_function import *# Scikit-Learn相關模塊 # 評估器類 from sklearn.preprocessing import StandardScaler from sklearn.preprocessing import PolynomialFeatures from sklearn.linear_model import LogisticRegression from sklearn.pipeline import make_pipeline from sklearn.model_selection import GridSearchCV# 實用函數 from sklearn.model_selection import train_test_split from sklearn.metrics import accuracy_score# 數據準備 from sklearn.datasets import load_iris

在Lesson 6.5節中，我們曾圍繞鳶尾花數據集構建了多分類邏輯回歸模型并且采用網格搜索對其進行最優超參數搜索，其基本過程如下：

# 數據準備 X, y = load_iris(return_X_y=True) X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=24)# 模型訓練# 實例化模型 clf = LogisticRegression(max_iter=int(1e6), solver='saga') # 構建參數空間 param_grid_simple = {'penalty': ['l1', 'l2'],'C': [1, 0.5, 0.1, 0.05, 0.01]} # 構建網格搜索評估器 search = GridSearchCV(estimator=clf,param_grid=param_grid_simple)# 模型訓練 search.fit(X_train, y_train) #GridSearchCV(estimator=LogisticRegression(max_iter=1000000, solver='saga'), # param_grid={'C': [1, 0.5, 0.1, 0.05, 0.01], # 'penalty': ['l1', 'l2']})search.best_params_ #{'C': 1, 'penalty': 'l1'} search.best_estimator_.coef_ #array([[ 0. , 0. , -3.47337669, 0. ], # [ 0. , 0. , 0. , 0. ], # [-0.55511761, -0.34237661, 3.03227709, 4.12148646]]) search.best_estimator_.intercept_ #array([ 11.85884734, 2.65291107, -14.51175841])

我們發現，在參數組取值為{‘C’: 1, ‘penalty’: ‘l1’}的情況下，三個邏輯回歸方程中，第一個方程只包含一個系數，也就是說明第一個方程實際上只用到了原數據集的一個特征，第二個方程自變量系數均為0、基本屬于無用方程，而只有第三個方程自變量系數都不是0、看起來比較正常“正常”。我們知道，對于多分類問題，邏輯回歸所構建的模型方程實際上是每個方程對應預測一個類別，而由于總共只有三個類別，因此是允許存在一個類別的預測方程失效的，只要剩下的兩個類別能夠各自完成對應類別的預測，則剩下的樣本就屬于第三類。此處我們需要重點關注的是第一個方程，該方程只有一個非零系數，其背后含義是模型只借助特征矩陣中的第三個特征，就很好的將第一類鳶尾花和其他鳶尾花區分開了。

我們進一步觀察數據和第三個特征對于第一個類別的分類結果：

iris = load_iris(as_frame=True) iris.data

t = np.array(iris.target) t[50:] #array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, # 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, # 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, # 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, # 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]) # 將2、3類劃歸為一類 t[50:] = 1 t #array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, # 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, # 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, # 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, # 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, # 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, # 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) # 此處提取第3、4個特征放置二維空間進行觀察，用第三個特征和其他特征組合也是類似 d = np.array(iris.data.iloc[:, 2: 4]) plt.scatter(d[:, 0], d[:, 1], c=t) plt.plot(np.array([2.5]*25), np.arange(0, 2.5, 0.1), 'r--')

我們發現，確實可以通過第三個特征（橫坐標）很好的區分第一類（紫色點簇）和其他兩類（黃色點簇），也就是說，從分類結果來看，我們能夠簡單通過一個分類規則來區分第一類鳶尾花和其他兩類，例如從上圖可以看出，我們可以以petal length (cm) <= 2.5作為分類條件，當分類條件滿足時，鳶尾花屬于第一類，否則就屬于第二、三類。至此我們集完成了對上述數據集的初步分類，基本分類情況可以通過下圖來進行表示：

當然圍繞上述未分類的二、三類鳶尾花數據，我們能否進一步找到類似剛才的分類規則對其進行有效分類呢？當然此處由于我們希望分類規則能夠盡可能簡潔，我們力求找出根據某一個特征的取值劃分就能對數據集進行有效分類的方法，這時我們可以考慮先利用邏輯回歸的l1正則化挑選出對二、三類分類最有分類效力的特征（也就是最重要的特征），然后根據只有一個特征系數不為0的帶l1正則化的邏輯回歸建模結果、找到決策邊界，而該決策邊界就是依據該單獨特征劃分Iris二、三類子數據的最佳方法。我們可以通過下述代碼實現：

# 提取待分類的子數據集 X = np.array(iris.data)[t == 1] y = np.array(iris.target)[t == 1]

接下來，我們構建一個包含l1正則化的邏輯回歸模型，并通過不斷調整C的取值、通過觀察參數系數變化情況來挑選最重要的特征：

C_l = np.linspace(1, 0.1, 100) #C越小，經驗風險懲罰力度越小 coef_l = []for C in C_l:clf = LogisticRegression(penalty='l1', C=C, max_iter=int(1e6), solver='saga').fit(X, y)coef_l.append(clf.coef_.flatten())ax = plt.gca() ax.plot(C_l, coef_l) ax.set_xlim(ax.get_xlim()[::-1]) #橫坐標翻過來了 plt.xlabel('C') plt.ylabel('weights')

coef_l #[array([-1.12493251, -0.96058774, 3.23208646, 4.18486998]), # array([-1.10210628, -0.91621566, 3.23983307, 4.15696154]), # array([-1.09239629, -0.89555328, 3.23399288, 4.13377003]), # array([-1.08811789, -0.88498435, 3.22207551, 4.11256892]), # ... # array([0. , 0. , 2.05106895, 0. ]), # array([0. , 0. , 1.93251455, 0. ]), # array([0. , 0. , 1.80075548, 0. ])]

不難看出，在對鳶尾花數據集的二、三分類的子數據集進行分類時，仍然還是第三個特征會相對重要，因此我們根據上述結果，構建一個正則化項為l1、C取值為0.2的邏輯回歸模型進行訓練，此時由于其他三個特征的參數都被歸零，因此該模型訓練過程實際上就相當于帶入第三個特征進行建模：

clf = LogisticRegression(penalty='l1', C=0.2, max_iter=int(1e6), solver='saga').fit(X, y) clf.coef_, clf.intercept_ #(array([[0. , 0. , 2.84518611, 0. ]]), # array([-13.88186328])) clf.score(X, y) #0.93

此時模型準確率為93%，同樣，如果構建一個只包含第三、四個特征的特征空間，此時上述邏輯回歸建模結果的決策邊界為x=b，其中b的取值如下：

b = 13.88186328 / 2.84518611 b #4.87907038179657

我們可以通過可視化的方法觀察此時特征空間中樣本分布情況，以及x=b的決策邊界的分類效果：

plt.plot(X[:, 2][y==1], X[:, 3][y==1], 'ro') plt.plot(X[:, 2][y==2], X[:, 3][y==2], 'bo') plt.plot(np.array([b]*20), np.arange(0.5, 2.5, 0.1), 'r--')

當然，我們也可以簡單驗算下x=b的決策邊界是否是模型真實的分類邊界：

y_pred = clf.predict(X)plt.scatter(X[:, 2], X[:, 3], c=y_pred) plt.plot(np.array([b]*20), np.arange(0.5, 2.5, 0.1), 'r--')

注意，在確定第一個分類條件時我們沒有直接根據邏輯回歸的線性方程計算決策邊界的主要原因是彼時邏輯回歸方程是在mvm分類規則下的三個分類方程，其中每個方程其實都會一定程度上受到其他方程影響，導致決策邊界無法直接通過方程系數進行計算。

盡管x=b分類邊界的準確率不足100%，但其仍然不失為一個不錯的分類規則，即分類條件為petal length (cm) <= 4.879，當分類條件滿足時，鳶尾花屬于第二類、不滿足時鳶尾花屬于第三類，根據此分類條件進行的分類準確率為93%。我們可以將圍繞鳶尾花子數據集進行二、三類的分類過程進行如下方式表示：

至此，我們就根據兩個簡單的分類規則，對鳶尾花數據集進行了有效劃分，此時整體準確率為：

1-(y != y_pred).sum() / 150 #0.9533333333333334

• 決策樹簡單構建

而上述整個過程，我們是通過帶正則化項的邏輯回歸模型挖掘出的兩個分類規則，并且這兩個分類規則呈現遞進的關系，也就是一個分類規則是在另一個分類規則的分類結果下繼續進行分類，最終這兩個分類規則和對應劃分出來的數據集呈現出樹狀，而帶有不同層次分類規則的模型，其實就是決策樹模型，也就是說通過上面一系列的操作，我們就已經成功構建了一個決策樹模型。

• 決策樹的分類過程

對于上述已經構建好的一個決策樹來說，當對新數據進行判別時，任意進來一條數據我們都可以自上而下進行分類，先根據petal length (cm) <= 2.5判斷是否屬于第一類，如果不滿足條件則不屬于第一類，此時進一步考慮petal length (cm) <= 4.879是否滿足條件，并據此判斷是屬于第二類還是第三類。

當然，目前主流的決策樹并不是依據邏輯回歸來尋找分類規則，但上述構建決策樹模型的一般過程和核心思想和目前主流的決策樹模型并無二致，因此我們可以圍繞上述過程進行進一步總結：

• 決策樹模型本質

當決策樹模型構建好了之后，實際上一個決策樹就是一系列分類規則的疊加，換而言之，決策樹模型的構建從本質上來看就是在挖掘有效的分類規則，然后以樹的形式來進行呈現。

• 決策樹的樹生長過程

在整個樹的構建過程中，我們實際上是分層來對數據集進行劃分的，每當定下一個分類規則后，我們就可以根據是否滿足分類規則來對數據集進行劃分，而后續的分類規則的挖掘則進一步根據上一層劃分出來的子數據集的情況來定，逐層劃分數據集、逐數據集尋找分類規則再劃分數據集，實際上就就是樹模型的生長過程，并且不難看出，這個過程實際上也是一個迭代計算過程（上一層的數據集決定有效規律的挖掘、而有效規律的挖掘）。而停止生長的條件，我們也可以根據“繼續迭代對結果沒有顯著影響”這個一般思路來構建。

• 樹模型的基本結構

當然，在已經構建了決策樹之后，我們也能夠對一個樹模型的內部結構來進行說明。對上述決策樹來說，我們可以將其看成是點（數據集）和線構成的一個圖結構（準確來說應該是一種有向無環圖），而對于任何一個圖結構，我們都能夠通過點和線來構建對其的基本認知，對于決策樹來說，我們主要將借助邊的方向來定義不同類型點，首先我們知道如果一條邊從A點引向B點，則我們這條邊對于A點來說是出邊、對于B點來說是入邊，A節點是B節點的父節點，據此我們可以將決策樹中所有的點進行如下類別劃分：
(1)根節點（root node）：沒有入邊，但有零條或者多條出邊的點；
(2)內部點（internal node）：只有一條入邊并且有兩條或多條出邊的點；
(3)葉節點（leaf node）：只有入邊但沒有出邊的點；

因此，我們知道在一次次劃分數據集的過程中，原始的完整數據集對應著決策樹的根節點，而根結點劃分出的子數據集就構成了決策樹中的內部節點，同時迭代停止的時候所對應的數據集，其實就是決策樹中的葉節點。并且在上述二叉樹（每一層只有兩個分支）中，一個父節點對應兩個子節點。并且根據上述決策樹的建模過程不難理解，其實每個數據集都是由一系列分類規則最終劃分出來的，我們也可以理解成每個節點其實都對應著一系列分類規則，例如上述E節點實際上就是petal length (cm) <= 2.5和petal length (cm) <= 4.879同時為False時劃分出來的數據集。

在了解決策樹的一般建模過程和模型本質后，接下來我們來簡單說明一下目前樹模型的主流派系，然后詳細討論目前最通用的機器學習流派的決策樹模型的建模過程。

二、決策樹的分類與流派

正如此前所說，樹模型并不是一個模型，而是一類模型。需要知道的是，盡管樹模型的核心思想都是源于一種名為貪心算法的局部最優求解算法，但時至今日，樹模型已經有數十種之多，并且劃分為多個流派。目前主流的機器學習算法類別可劃分如下：

• ID3(Iterative Dichotomiser 3) 、C4.5、C5.0決策樹

是最為經典的決策樹算法、同時也是真正將樹模型發揚光大的一派算法。最早的ID3決策樹由Ross Quinlan在1975年（博士畢業論文中）提出，至此也奠定了現在決策樹算法的基本框架——確定分類規則判別指標、尋找能夠最快速降低信息熵的方式進行數據集劃分（分類規則提取），不斷迭代直至收斂；而C4.5則是ID3的后繼者，C4.5在ID3的基礎上補充了一系列基礎概念、同時也優化了決策樹的算法流程，一方面使得現在的樹模型能夠處理連續變量（此前的ID3只能處理分類變量），同時也能夠一定程度提高樹模型的生長速度，而C4.5也是目前最為通用的決策樹模型的一般框架，后續盡管有其他的決策樹模型誕生，但大都是在C4.5的基本流程上進行略微調整或者指標修改，甚至在C4.5還被IEEE評為10大數據挖掘算法之首，由此可見C4.5算法的巨大影響力。此外，由于C4.5開源時間較早，這也使得在過去的很長一段時間內，C4.5都是最通用的決策樹算法。當然在此后，Ross Quinlan又公布了C5.0算法，進一步優化了運行效率和預測流程，通過一系列數據結構的調整使得其能夠更加高效的利用內存、并提高執行速度。當然，由于C5.0在很長的一段時間是作為收費軟件存在、并且多集成與像SAS軟件中，因此并未被最廣泛的應用于各領域。

此外，值得一提的是，由于Ross Quinlan擁有非常深厚的數學背景，因此在設計決策樹算法的時候，盡管決策樹是一種非參數方法（無需提前進行數據訓練的假設檢驗），但在實際執行決策樹剪枝（一種防止過擬合的手段）時卻需要用到非常多統計學方法，在實際構建模型時也無需劃分訓練集和測試集，因此C4.5其實更像是一種統計學算法，而非機器學習算法。

需要知道的是，C4.5在樹的生長上還是更像機器學習算法，而這種半“統計學”半“機器學習”的狀態也是該算法存在爭議的地方。

• CART決策樹

CART全稱為Classification and Regression Trees，即分類與回歸決策樹，同時也被稱為C&RT算法，在1984年由Breiman、Friedman、Olshen和Stone四人共同提出。CART樹和C4.5決策樹的構造過程非常類似，但拓展了回歸類問題的計算流程（此前C4.5只能解決分類問題），并且允許采用更豐富的評估指標來指導建模流程，并且，最關鍵的是，CART算法其實是一個非常典型的機器學習算法，在早期CART樹的訓練過程中，就是通過劃分訓練集和驗證集（或者測試集）來驗證模型結果、并進一步據此來調整模型結構，當然，除此以外，CART樹還能夠用一套流程同時處理離散變量和連續變量、能夠同時處理分類問題和回歸問題，這些都符合一個機器學習領域要求算法有更普適的功能和更強的魯棒性的要求，這也是為何近幾年CART樹會更加流行的主要原因。當然，在skelarn中，決策樹模型評估器集成的也是CART樹模型，稍后我們在介紹決策樹建模流程的時候也將主要介紹CART樹的建模流程。

此處我們也可以參考sklearn中對于ID3、C4.5和CART樹的對比描述：

需要注意的是，sklearn中也并非實現的是完全的CART樹，通過相關評估器參數的調整，sklearn中也能實現“CART樹的建模流程+C4.5的決策樹生長指標”這種混合模型。

此外，與其說CART樹是一個非常“機器學習”的算法，不如說CART樹是一個更加適合使用機器學習的方法來進行建模的模型，機器學習或者統計學建模方法更大程度上是一種建模思路，很多模型（像邏輯回歸、包括樹模型在內）其實都有機器學習實現的方式和統計學模型實現的方法。

• CHAID樹

CHAID是Chi-square automatic interaction detection的簡稱，由Kass在1975年提出，如果說CART樹是一個典型的機器學習算法，那么CHAID樹就是一個典型的統計學算法。從該算法的名字就能看出，整個決策樹其實是基于卡方檢驗（Chi-square）的結果來構建的，并且整個決策樹的建模流程（樹的生長過程）及控制過擬合的方法（剪枝過程）都和C4.5、CART有根本性的區別，例如CART都只能構建二叉樹，而CHAID可以構建多分枝的樹（注：C4.5也可以構建多分枝的樹）；例如C4.5和CART的剪枝都是自下而上（Bottom-up）進行剪枝，也被稱為修剪法（Pruning Technique），而CHAID樹則是自上而下（Top-Down）進行剪枝，也被稱為盆栽法（Bonsai Technique）。當然，該決策樹算法目前并非主流樹模型，因此我們此處僅作簡單介紹，并不做更加深入的探討。

上述討論所涉及到的關鍵概念，如剪枝、劃分規則提取方式、劃分規則評估指標等內容，我們都將在下一小節進行詳細介紹。

在課程接下來的部分，我們將重點討論關于CART樹的建模流程，以及在Scikit-Learn中的實現方法。同時，ID3、C4.5決策樹作為經典模型，盡管我們無法在sklearn中實現相關模型的建模，但對這些算法的了解仍然會非常有助于我們理解樹模型的建模思想，因此我們后續也會以加餐形式介紹ID3、C4.5的基本建模流程。

Lesson 8.2 CART分類樹的建模流程與sklearn評估器參數詳解

根據上一小節的介紹我們知道，CART樹是目前機器學習領域內最通用的決策樹，并且CART樹能夠同時解決分類問題和回歸問題。本節我們將首先介紹關于CART樹在進行分類問題建模時的基本流程，同時詳細講解sklearn中相關評估器的參數情況與使用方法。

# 科學計算模塊 import numpy as np import pandas as pd# 繪圖模塊 import matplotlib as mpl import matplotlib.pyplot as plt# 自定義模塊 from ML_basic_function import *# Scikit-Learn相關模塊 # 評估器類 from sklearn.preprocessing import StandardScaler from sklearn.preprocessing import PolynomialFeatures from sklearn.linear_model import LogisticRegression from sklearn.pipeline import make_pipeline from sklearn.model_selection import GridSearchCV# 實用函數 from sklearn.model_selection import train_test_split from sklearn.metrics import accuracy_score# 數據準備 from sklearn.datasets import load_iris

一、CART決策樹的分類流程

從基本原理來說，決策樹是一種非常通用的模型，在模型訓練時可以帶入分類變量、也可以帶入連續變量，同時在進行預測時既能解決分類問題也能解決回歸問題，在介紹CART樹的原理時，我們先從簡單入手，先考慮自變量都是離散變量的分類預測問題，再逐步拓展連續變量的處理方法和回歸類問題的預測方法。

1.CART樹的基本生長過程

首先我們來看在特征都為分類變量時、圍繞分類問題構建CART的基本過程。

1.1 規則評估指標選取與設置

• 劃分規則評估指標概念

在引言部分中我們曾簡單構建了一個決策樹，我們曾強調，決策樹的建模過程實際上就是挖掘有效分類規律的過程，而這里的分類規律是否有效，其實是需要有一個評估標準的。此前我們是在邏輯回歸的模型結論的基礎上尋找分類規律，可以看成是根據分類結果的準確率來尋找分類規則，此時準確率就是評估分類條件好壞的評估指標，例如在決策樹開始生長的第一層，我們選取petal length (cm) <= 2.5作為分類條件將原始數據集一分為二，分出來的兩個數據集其中一個100%是一類數據，另一個則全是二、三類數據，此時如果我們根據準確率來判斷該分類規則是否能夠很好的區分一類和二、三類數據的話，那此時的準確率就是100%，此時的分類誤差就是0。

• 劃分規則評估指標構建的核心思路

當然，這種定義分類評估指標的方法并不通用并且在多分類問題時容易引發混亂，例如如果是四分類問題，1條件能夠100%區分A類和BCD類，2條件能夠100%區分AB類和CD類，此時如何還按照準確率來進行判別分類條件好壞的判別一句，則選擇哪個條件就成了問題。因此一般來說樹模型挑選分類規則的評估指標并不是看每個類別劃分后的準確率，而是父節點劃分子節點后子節點數據集標簽的純度。

注意，此處純度是一個非常重要的概念，一般來說如果一個數據集標簽都比較傾向于取得同一個值（不管是都取0還是都取1），則我們就說這個數據集的標簽純度高，反之則說這個這個數據集標簽純度不高。而決策樹的劃分規則的評估標準，其實都是根據純度來進行構建的。

其實，決策樹生長的方向也就是令每個劃分出來的子集純度越來越高的方向。

• 單獨一個數據集的標簽純度衡量指標

首先我們先來討論對于一個單獨的數據集來說，可以通過哪些指標來衡量該數據集標簽的純度。一般來說，用于衡量數據集標簽純度的數值指標一般有三種，分別是分類誤差、信息熵和基尼系數，對于每個單獨數據集來說，其基本計算公式如下：

(1)分類誤差（Classification error）：
$$Classificationerror(t)=1?\underset{1\le i\le c}{\max }[p(i|t)]$$

其中i表示第i類，當前數據集總共有c類，$p(i|t)$代表第i類數據占當前數據集中總數據的比例。而所謂的分類誤差，其實就是用1減去多數類的占比。例如某個包含10條數據的數據集，有6條0類數據、4條1類數據，此時該數據集分類誤差就是1-6/10 = 0.4。分類誤差在[0, 0.5]范圍內取值，分類誤差越小，說明數據集標簽純度越高。

此外，由于決策樹中每一個數據集實際上就代表一系列分類規則，因此分類誤差的另一種理解方法是，如果需要根據少數服從多數原則對當前數據集選取一個唯一的標簽（此前一系列分類規則輸出一個最終結果），則只能將所有少數類的標簽改成多數類的標簽，此時誤差（對應的分類規則的誤差）就是所有少數類的數據占比。

分類誤差實際上就是貪心算法所使用的決策樹劃分規則評估指標

(2)信息熵（Entropy）：
$$Entropy(t)=?\sum _{i=1}^{c}p(i|t)lo{g}_{2}p(i|t)$$

當然，我們此前所介紹的用于衡量數據混亂程度的信息熵也可以用于衡量數據集標簽純度，而信息熵的計算過程也正如此前介紹的一樣：每個類別的數據占比乘以以2為底的對數處理結果，然后再進行不同類別的累加，最后進行負值處理。例如還是針對一個包含了6個0類、4個1類的數據集，信息熵計算結果為：

- 4/10 * np.log2(4/10) - 6/10 * np.log2(6/10) #0.9709505944546686

當然，回顧此前內容，信息熵也是在[0,1]之間取值，并且信息熵越小則說明數據集純度越高。

信息熵的相關詳細介紹參見Lesson 4.2

ID3、C4.5、C5.0算法主要使用信息熵進行劃分規則的挑選

(3)基尼系數（Gini）：
$$Gini(t)=1?\sum _{i=1}^{c}p(i|t{)}^2$$

此外，還有一個和信息熵的計算過程比較類似的評估指標——基尼系數。基尼系數通過計算1減去每個類別占比的平方和來作為純度衡量指標，例如還是針對一個包含了6個0類、4個1類的數據集，基尼系數的計算結果為：

1 - np.power([4/10, 6/10], 2).sum() #0.48

而和信息熵不同的是，基尼系數在[0, 0.5]范圍內取值，并且基尼系數越小表示數據集標簽純度越高

p_l = np.arange(0, 1, 0.01)gini_l = []for p in p_l:gini_l.append(1 - np.power([p, 1-p], 2).sum()) plt.plot(p_l, gini_l)

在默認情況下，CART樹默認選擇Gini系數作為評估指標。

在隨后的建模試驗中，我們也默認采用基尼系數作為評估指標。

當然我們也可以簡單對比在二分類情況下三個評估指標伴隨某類樣本所占比例p值變化而變化的情況：

np.max([1, 2]) #2ce_l = [] gini_l = [] en_l = []for p in p_l:ce_l.append(1-np.max([p, 1-p]))gini_l.append(1 - np.power([p, 1-p], 2).sum())en_l.append(entropy(p)) plt.plot(ce_l, 'b-', gini_l, 'r-', en_l, 'r--')

• 多個數據集的平均指標

在很多時候，我們不僅需要衡量單獨數據集標簽的純度，我們還需要衡量多個數據集作為一個整體時的標簽的純度，例如一個父節點在劃分成兩個子節點時兩個子節點整體的評估指標。此處我們舉例說明：我們簡化一組后續建模會用到的客戶數據，簡化后的數據集A共有兩個特征、一個標簽，并且標簽只有0-1兩個類別，數據集特征分別是收入（income）和信用評級（credit_rating），同樣也都用有兩個分類水平的離散變量表示。

此時我們首先可以計算該數據集整體的基尼系數：

p = 3/8 gini_A = 1 - np.power([p, 1-p], 2).sum() gini_A #0.46875

然后我們隨意設置一個分類條件。例如我們設置分類條件為income <= 1.5，則可以將上述數據集進一步劃分成兩個子數據集B1、B2:

p = 2/5 gini_B1 = 1 - np.power([p, 1-p], 2).sum() gini_B1 #0.48

而B2數據集只包含一個標簽，因此B2的基尼系數為0

gini_B2 = 0

而此時如果要計算B1、B2整體的基尼系數，則需要在gini_B1、gini_B2的基礎上進行各自數據集樣本數量占整體數據集比例的加權求和，即根據如下方式進行計算：$$Gini(B)=\frac{|B_1|}{|A|}Gini(B_1)+\frac{|B_2|}{|A|}Gini(B_2)$$其中$\frac{|B_i|}{|A|}$為子數據集$B_i$數據個數占父類數據集A中數據個數的比例。因此上述$B_1$、$B_2$整體基尼系數為：

gini_B = gini_B1 * 5/8 + gini_B2 * 3/8 gini_B #0.3

至此，我們就構建了一個用于描述數據集劃分完后兩個子集的整體純度的方法，而我們知道，子集整體純度越高，其實也就說明對應分類規則越有效。接下來我們將詳細討論如何構建分類規則以及如何對這些分類規則進行評估。

1.2 決策樹備選規則創建方法

正如此前所說，決策樹模型的建模過程實際上就是在挑選有效分類規則的過程，而要挑選有效分類規則，首先就必須明確如何創建哪些備選規則，其實對于很多樹模型，特征是離散型變量還是連續性變量會直接影響備選規則的創建，（C4.5兩種情況不一樣對待）但對于CART樹以及sklearn中集成的方法來說，是將兩種情況合二為一來進行看待，也就是根據如下方式來進行備選規則的創建：

對于任何特征矩陣，首先需要逐列對其進行數值排序，例如上述數據集A，我們可以單獨提取income和credit_rating兩列來進行降序排序，排序結果如下：

據此，我們通過尋找這些特征不同取值之間的中間點作為切點，來構造備選規則。例如income有兩個取值1、2，因此只有一個切點就是1.5，那么我們就能創造一個income <= 1.5的規則來對數據集進行劃分，如此我們就能把income取值為1的數據劃歸一個子集、income取值為2的數據集劃歸另一個子集，實際上上面在介紹多數據集基尼系數計算過程時就是采用該規則。需要知道的是，在所構造的條件中不等號的方向實際上沒有任何影響。當然，income只有兩個取值只能找到一個切點只能構造一個規則，而credit_rating特征也有兩個取值，因此也能找到一個切點構造一個備選規則，即我們其實也可以根據credit_rating <= 1.5來切分出兩個子集。

而其實如果特征是三個取值的特征，則可以找到兩個切點、找到兩種劃分數據集的方式。更進一步的，如果該數據中某特征是連續變量，每條不同的數據取值都不同，例如：
則此時可以將其看成是擁有8個分類水平的分類變量，仍然還是尋找相鄰取值水平的中間值作為切點來構造劃分規則，此時由于age特征有8個不同的取值，因此可以構造7個備選的劃分數據集的方法，例如age <= 36、age <= 34.5等等。也就是說，對于任何一個特征無論是連續型變量還是分類變量，只要有N個取值，就可以創造N-1個劃分條件將原數據集劃分成兩份。

正是因為可以用一種方法就能同時處理連續變量和離散變量，因此在決策樹建模的過程中我們無需特別區分兩種類型特征的區別。

此外，需要注意的是，CART樹用這種方法同時處理離散變量和連續變量，而C4.5只用這種方式處理連續變量（離散變量采用另一種方法），因此這里我們可以理解成是CART樹將離散變量“連續化”，也就是將離散變量看成是連續變量，這也就是為何sklearn在說明文檔中強調，sklearn的樹模型無法處理分類變量的原因（原文：scikit-learn implementation does not support categorical variables for now.）。此處所謂的無法處理分類變量并不是不能帶入分類變量進行建模，而是不支持類似C4.5的方法從離散特征中提取備選劃分規則，而是會將離散變量也看成是連續變量，采用C4.5處理連續變量的方法處理離散變量。關于C4.5從離散特征中批量提取備選規則的方法我們會在課后閱讀中介紹詳細介紹。

實際上，機器學習不同統計算法，大多數時候都不會刻意區分特征的連續與離散。

1.3 挑選最佳分類規則劃分數據集

當然，對于上述A數據集，總共有兩個特征，每個特征有一個備選劃分規則，因此在對根結點劃分時，其實是有兩種數據集的劃分方法，我們已經簡單查看采用income <= 1.5進行分類的結果：
而如果我們采用credit_rating <= 1.5來對數據集進行劃分，則將出現下述結果：

從結果上來看，這兩個劃分條件都能切分出一個只包含一類標簽的數據集，結果區分不是很大，那么到底應該選用哪個分類規則對數據集進行第一次切分、讓決策樹完成第一步的生長呢？這個時候就要用到此前我們介紹的關于評價分類規則是否有效的評估指標了，一般來說對于多個規則，我們首先會計算父節點的基尼系數（Gini(A)），然后計算劃分出的兩個子節點整體基尼系數（Gini(B)），然后通過對比哪種劃分方式能夠讓二者差值更大，即能夠讓子節點的基尼系數下降更快，我們就選用哪個規則。例如對上述例子，我們知道在以income <= 1.5為規則劃分數據集時，基尼系數下降結果為：

gini_A - gini_B #0.16875

而如果采用第二個劃分規則來進行數據集切分，則此時基尼系數下降結果為：

p = 3/4 gini_B2 = 1 - np.power([p, 1-p], 2).sum() gini_B2 #0.375 gini_B1 = 0 gini_B = gini_B1 * 1/2 + gini_B2 * 1/2 gini_B #0.1875 gini_A - gini_B #0.28125

很明顯，第二個規則能夠讓父節點的基尼系數下降更快，因此第二個規則、即credit_rating <= 1.5劃分規則是一個更好的規則，在第一次數據集劃分時我們應該采用該規則。

注，如果是ID3或者C4.5，此處則是以信息熵計算結果為準。

1.4 決策樹的生長過程

當完成一次規則篩選與樹生長后，接下來需要考慮的問題是，面對當前劃分出的數據集B1、B2，是否還需要進一步尋找分類規則對其進行劃分。
首先，對于數據集B1來說，由于其基尼系數已經為0，無需再進行計算；而B2數據集基尼系數為0.375，還可以進一步提取有效分類規則對其進行分類，以降低其基尼系數。此時我們又可以完全重復數據集A的劃分過程，首先圍繞數據集B2進行備選規則的提取，對于B2來說備選規則只有income <= 1.5一條，因此我們就以該規則劃分數據集：
能夠看出，最終劃分出來的C1和C2基尼系數都是0，因此C的兩個數據集整體基尼系數也是0，當然我們也無需進一步劃分數據集，到此為止決策樹也停止生長。

• 決策樹生長與迭代運算

此前我們說到，決策樹的生長過程本質上也是在進行迭代運算，我們根據上一輪的到的結論（數據集劃分情況）作為基礎條件，來尋找子數據集的最佳分類規則，然后來進行數據集劃分，以此往復。既然是迭代運算，那就必然需要討論所有迭代運算都需要考慮的兩個問題，其一是每一輪的迭代目標、其二是迭代收斂條件。

首先是每一輪迭代計算的目標，在梯度下降的計算過程中，每一輪迭代其實都是為了能夠更大程度上降低損失函數值，在K-Means快速聚類中，每一輪迭代其實都是為了能夠盡快降低組內誤差平方和（SSE），而在決策樹的建模過程中，每一輪迭代實際上是為了更快速的降低基尼系數，也就是希望這一輪劃分出來的子數據集純度盡可能高，從而說明該規則會對分類更加有效。因此如果我們可以將每一輪迭代過程中父類的基尼系數看成是損失函數值，樹的迭代生長過程就是為了能夠更快速的降低父類的基尼系數值。

其次就是迭代計算的收斂條件。對于此前我們所介紹的收斂條件其實也同樣適用于決策樹模型，例如當兩輪迭代損失函數的差值小于某個值、或者直接限制最大迭代次數，其實都是可以用于決策樹模型的。此時所謂兩輪迭代的損失值小于某個值就停止迭代，其實就等價于如果進一步的劃分數據集、但基尼系數的減少少于某個值就暫時不做劃分；而最大迭代次數其實就相當于樹模型的最高生長層數，在實際建模過程中，我們也可以通過約束樹最多生長幾層來作為迭代收斂條件。當然，對于樹模型來說，還有可能出現類似上述備選規則都用完了的情況，此時也會停止迭代。

2.CART樹的剪枝

和邏輯回歸不同，決策樹在不進行特征衍生時就是一個分類效力更強的模型，因此其本身就是一個更容易過擬合的模型。并且通過觀察我們不難發現，決策樹生長的層數越多就表示樹模型越復雜，此時模型結構風險就越高、模型越容易過擬合。因此，很多時候如果我們不對樹的生長進行任何約束，即如果設置的收斂條件較為嚴格（例如要求最終基尼系數全為0），并且最大迭代次數不進行限制，則很有可能容易過擬合。因此在決策樹的建模流程當中，有非常重要的一個環節，就是需要討論限制決策樹模型過擬合傾向的方法。

當然，不同決策樹算法的剪枝策略也各有不同，總的來說樹模型的剪枝分為兩種，其一在模型生長前就限制模型生長，這種方法也被稱為預剪枝或者盆栽法；而另外一種方法則是先讓樹模型盡可能的生長，然后再進行剪枝，這種方法也被稱為后剪枝或者修建法。從算法的原生原理來講，目前主流的C4.5和CART樹都采用的是后剪枝的方法，其中C4.5是通過計算葉節點的期望錯誤率（一種區間估計的方法）來進行剪枝，而CART樹則是通過類似正則化的方法在損失函數（基尼系數計算函數）中加入結構復雜度的懲罰因子，來進行剪枝。

不過，無論采用何種方式來進行剪枝，最終的結果都是通過控制樹的結構復雜度來抑制過擬合傾向，而樹模型的結構復雜度其實完全可以用樹的層數、每一層分叉的節點數來表示，即內部節點和葉節點的數量來表示，因此我們也完全可以不采用這些樹模型原生原理的方式來進行剪枝，而是直接將這些決定樹模型的復雜度的因素視作超參數，然后通過網格搜索的方式來直接確定泛化能力最強的樹模型結構。當然這也是sklearn中進行決策樹剪枝的一般策略。

在sklearn 0.22版本之前，甚至沒有支持CART樹實現原生原理剪枝方式的參數。

二、CART分類樹的Scikit-Learn快速實現方法與評估器參數詳解

1.CART分類樹的sklearn快速實現

接下來我們嘗試在Scikit-Learn中構建分類樹模型。在sklearn中，回歸樹和分類樹是兩個不同的評估器，都在sklearn.tree模塊內，我們可以通過如下方式進行導入：

from sklearn.tree import DecisionTreeClassifier,DecisionTreeRegressor

然后嘗試圍繞上述簡單例子進行快速建模試驗：

# 準備數據集 X = np.array([[1, 1], [2, 2], [2, 1], [1, 2], [1, 1], [1, 2], [1, 2], [2, 1]]) y = np.array([0, 0, 0, 1, 0, 1, 1, 0]) # 調用決策樹評估器并進行訓練 clf = DecisionTreeClassifier().fit(X, y) clf.score(X, y) #1.0

當然，對于樹模型來說，我們不僅需要查看模型最終結果的評估指標，很多時候我們還希望能夠觀察到樹模型分類過程的樹狀圖，即類似于此前我們手動繪制的樹狀圖。根據sklearn說明文檔中的介紹，此處我們可以借助sklearn.tree模塊下的plot_tree函數直接輸入訓練好的評估器即可進行繪制：

• plot_tree繪制樹狀圖

# 首先導入tree模塊 from sklearn import tree # 然后調用plot_tree函數進行繪制 plt.figure(figsize=(6, 2), dpi=150) tree.plot_tree(clf)

由于plot_tree是sklearn中已經集成好的函數，因此調用過程非常簡單，我們只需要輸入訓練好的分類樹評估器即可。同時根據輸出的結果可知，sklearn中分類樹的建模過程和此前我們手動哦實現的過程是一樣的，先根據第一個特征的不同取值進行數據集劃分，然后在根據第二個特征的不同取值進行數據集劃分，最終形成一個三個葉節點、兩層的決策樹模型。

當然，sklearn中的評估器使用過程基本一致，決策樹模型評估器的簡單使用也非常類似于邏輯回歸評估器。此外，由于sklearn中優秀的參數默認值設置，使得很多時候我們直接使用其默認值就能完成不錯的建模結果。接下來我們詳細討論決策樹評估器中的相關參數，借此討論關于sklearn中的決策樹剪枝方法。

2.CART分類樹評估器的參數詳解

實際上DecisionTreeClassifier評估器參數眾多，并且大多和決策樹的模型結構相關：

DecisionTreeClassifier? # Init signature: # DecisionTreeClassifier( # *, # criterion='gini', # splitter='best', # max_depth=None, # min_samples_split=2, # min_samples_leaf=1, # min_weight_fraction_leaf=0.0, # max_features=None, # random_state=None, # max_leaf_nodes=None, # min_impurity_decrease=0.0, # min_impurity_split=None, # class_weight=None, #樹模型會經常被使用 # presort='deprecated', # ccp_alpha=0.0, # )

接下來圍繞一些重點參數進行詳細講解：

• criterion：不純度衡量指標

首先，我們發現盡管sklearn的樹模型在默認情況下是CART樹，但同樣支持使用信息熵來衡量不純度。不過需要注意的是，哪怕我們在criterion參數中選擇信息熵，實際樹模型的建模過程也不是按照ID3或者C4.5的流程執行，此時的樹模型只能算是一種混合模型。而關于到底應該選擇哪個指標來衡量數據集的不純度，其實大多數情況下選擇哪個指標并不會實質影響樹模型的結構，但相比信息熵，基尼系數復雜度更低、計算速度更快，一般情況下推薦使用基尼系數。而如果一定要尋找二者在使用上的不同，一般認為在有些情況下，基尼不純度更傾向于在數據集中分割出多數類，而信息熵則更傾向于生成出更加平衡的樹。

• ccp_alpha：結構風險權重（類似于邏輯回歸中正則化的參數）

ccp是復雜度剪枝（Cost-Complexity Pruning）的簡稱，這是一個在sklearn的0.22版本中才加入的參數，這也是唯一一個為實現CART原生原理中的剪枝過程所設置的參數。此處首先需要知道的是在sklearn中并不一定要通過該方法進行剪枝，因此該參數其實也并不是一個必選參數。其次，帶有ccp項的剪枝也被稱為最小復雜度剪枝，其原理是在決策樹的損失函數上加上一個結構風險項，類似于正則化項在線性方程的損失函數中作用相同。

我們可以設T為某決策樹，$R(T)$為決策樹在訓練集上整體不純度，即代表模型的經驗風險，令$\alpha |T|$表示模型結構風險，其中$\alpha$為參數，$|T|$為樹的葉節點數量，則我們可以修改模型損失函數如下：
$$R_{\alpha }(T)=R(T)+\alpha |T|$$

其中$R_{\alpha }(T)$就是加入風險結構項后的損失函數，而$\alpha$則是風險結構項的系數。由此可知，$\alpha$取值越大、對模型的結構風險懲罰力度就越大、模型結構就越簡單、過擬合就能夠被更好的抑制，反之亦反。（邏輯回歸alpha在經驗風險上，lasso嶺回歸決策樹alpha在結構風險上）

class_weight參數進行設置后，min_weight_fraction_leaf才能被使用
上面那個例子max_features就是所有features

• 控制樹結構的參數類

接下來就是關于控制樹模型結構的相關參數，同時這也是最多的一類參數。這類參數可以進一步細分成兩類，其一是限制模型整體結構，主要包括限制樹深度的max_depth參數和限制葉節點數量的max_leaf_nodes參數。此外第二類就是限制樹生長的參數，包括從節點樣本數量限制樹生長的參數，包括min_samples_split、min_samples_leaf兩個參數，當然也有從損失值降低角度出發限制樹生長的參數，包括min_impurity_split和min_impurity_decrease參數。通過這些參數的共同作用，可以從各角度有效限制樹的生長。

注意，所謂樹的最大深度，指的是樹的最多生長幾層，或者除了根節點外總共有幾層，并不是樹的總共的層數。

此處需要重點說明的是，對于樹模型來說，葉節點太多、單獨葉節點所包含的樣本數量太少、內部節點再劃分降低的基尼系數較少，都是可能是過擬合的表現，在建模時尤其需要注意。

并且需要知道的是，sklearn中在計算父節點和子節點的基尼系數（或信息熵）的差值時，會在計算結果的前面乘以一個父節點占根節點數據量比例的系數作為最終impurity_decrease的結果：
B2——>C1、C2（0.375*4/8）

而這會導致樣本比較少的某節點，哪怕再劃分時子節點純度提升更高，但由于當前節點樣本較少，因此impurity_decrease數值較低。這其實也是一種為了防止過擬合而采取的措施。

• 控制迭代隨機過程的參數類

最后，還有一類參數值得注意，那就是關于控制建模過程中隨機性的一些參數，主要包含兩個，其一是splitter參數，當該參數取值為random時其實是隨機挑選分類規則對當前數據集進行劃分，其二是max_features，該參數可以任意設置最多帶入幾個特征進行備選規律挖掘，只要該參數的設置不是帶入全部特征進行建模，就相當于是給備選特征隨機劃個范圍，也相當于是給樹模型的訓練增加了一定的隨機性。當然，這兩個參數的主要作用有兩個方面，其一是可以提升模型訓練速度，試想一下，如果我們只從個別特征中挑選最佳劃分規則，或者隨機生成一個劃分規則、不進行比較就直接使用，其實都能夠極大節省計算量，只不過這也是一種用精度換效率的方式，如此操作肯定會帶來模型結果精度的下降；不過隨機性其實也是一把雙刃劍，在集成學習中，為了讓各基礎分類器“和而不同”，就必須讓每個基分類器保證一定的隨機性，而決策樹就是最常作為基分類器參與到集成學習中的模型，因此樹模型中的這些控制其隨機性的參數，也會在集成學習中發揮作用。

更多關于決策樹的使用及各類參數的使用及調參方法，我們將在后續內容中進行詳細介紹。

總結

以上是生活随笔為你收集整理的Lesson 8.1Lesson 8.2 决策树的核心思想与建模流程CART分类树的建模流程与sklearn评估器参数详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。