機器學習入門 12-5 CART與決策樹中的超參數

2021-02-21 AI機器學習與深度學習算法
CART

前面介紹的決策樹通常還有一個名字，叫做 CART（讀音與cut相近）。CART 是 Classification And Regression Tree 的首字母縮寫，通過 Classification And Regression Tree 的字面意思可以看出，CART 這種決策樹既能夠解決分類問題（Classification）也能夠解決回歸問題（Regression）。每個節點根據某種衡量系統不確定性的指標（信息熵或基尼係數）來找到某個合適的維度 d 以及維度 d 上的閾值 v，根據 d 和 v 對當前節點中的數據進行二分，通過這種方式得到的決策樹一定是一顆二叉樹，這也是 CART 這種決策樹的特點。

在 sklearn 中的決策樹都是 CART。在文獻或者資料中看到的 ID3、C4.5 和 C5.0 都是構建決策樹的不同方法。

CART的複雜度

決策樹的預測時間複雜度為 O(logm)，訓練的時間複雜度為 O(n*m*logm)，「需要注意我們介紹的都是 CART 這種決策樹。」

通過之前對決策樹上的各個節點上的數據進行劃分的模擬，對於構建好的一棵決策樹進行預測，平均而言的時間複雜度為 O(logm)，其中 m 為樣本個數。每次在一個節點上都是對當前的數據進行對半劃分，因此最終這棵決策樹的高度大概為 logm，當構建好了這棵高度為 logm 的決策樹之後，來了一個新樣本，這個新樣本就需要從這棵決策樹的根節點開始一步一步進行決策判斷，最終走到葉子節點。根據對應葉子節點上的數據來決定新樣本的標籤（分類問題）和目標（回歸問題）。

由於決策樹算法屬於無參數學習，因此構造決策樹的過程就是決策樹的訓練過程，決策樹訓練的時間複雜度為 O(n*m*logm)。在模擬構建決策樹的過程中，需要對樣本中的每一個維度 n 和每一個樣本 m 進行遍歷，最終找到在哪個維度上的哪個閾值上進行劃分的最佳劃分點，訓練的時間複雜度相對來說還是比較高的。

CART的剪枝

決策樹和 kNN 算法一樣都屬於非參數學習算法，所有的非參數學習算法都非常容易發生過擬合。因此對於決策樹來說，不僅訓練的時間複雜度比較高，而且非常容易發生過擬合。基於決策樹的高時間複雜度以及容易產生過擬合的問題，實際在構建決策樹的時候必須要對決策樹進行剪枝的操作，剪枝操作有兩個目的：

其實前面構建決策樹的例子中一直在使用剪枝操作。在使用 sklearn 創建決策樹的對象時傳入的 max_depth 參數，指定 max_depth 參數一直是 2，即構建決策樹的最大深度，這其實就是剪枝的一種手段。換句話說，所謂的剪枝，其實就是在創建決策樹對象時傳入參數的平衡。

除了前面一直使用的 max_depth 最大深度這個參數外，還有很多參數可以用於剪枝，這些參數既可以降低決策樹訓練過程的時間複雜度，同時也可以減輕過擬合的問題。

首先導入相應的庫函數。

 In[1]: import numpy as np
        import matplotlib.pyplot as plt
本小節使用的是由 sklearn.datasets 中的 make_moons 函數生成的噪聲為 0.25 的非線性虛擬數據集。使用非線性數據集是為了能夠更好的看出決策樹發生過擬合的樣子，以及使用超參數解決過擬合後的結果。
 In[2]: from sklearn import datasets
        X, y = datasets.make_moons(noise = 0.25, random_state = 666)
通過散點圖繪製數據集的分布。
 In[3]: plt.scatter(X[y == 0, 0], X[y == 0, 1])
        plt.scatter(X[y == 1, 0], X[y == 1, 1])
        plt.show()
 In[4]: from sklearn.tree import DecisionTreeClassifier
        
        dt_clf = DecisionTreeClassifier()
        dt_clf.fit(X, y)
        
Out[4]: DecisionTreeClassifier(class_weight=None, criterion='gini', max_depth=None,
            max_features=None, max_leaf_nodes=None,
            min_impurity_decrease=0.0, min_impurity_split=None,
            min_samples_leaf=1, min_samples_split=2,
            min_weight_fraction_leaf=0.0, presort=False, random_state=None,
            splitter='best')
使用 sklearn 中的決策樹不傳入任何參數，默認節點上的劃分標準使用基尼係數。默認 max_depth = None，對決策樹的深度不做限定，決策樹會一直向下劃分，直到劃分後的節點的基尼係數都為 0 為止。
訓練好了默認參數的決策樹，接下來使用前面一直使用的 plot_decision_boundary 函數繪製決策邊界。
 In[5]: def plot_decision_boundary(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)
選擇合適的繪製範圍，在繪製決策邊界的同時將數據集以散點圖的形式也繪製出來。
 In[6]: plot_decision_boundary(dt_clf, axis=[-1.5, 2.5, -1.0, 1.5])
        plt.scatter(X[y==0,0], X[y==0,1])
        plt.scatter(X[y==1,0], X[y==1,1])
        plt.show()
此時繪製出來的決策邊界的形狀相對不規則，顯然默認參數的決策樹模型發生了過擬合。
指定 max_depth 參數為 2，限制整個決策樹的最大深度為 2
 In[7]: dt_clf2 = DecisionTreeClassifier(max_depth=2)
        dt_clf2.fit(X, y)
        
        plot_decision_boundary(dt_clf2, axis=[-1.5, 2.5, -1.0, 1.5])
        plt.scatter(X[y==0,0], X[y==0,1])
        plt.scatter(X[y==1,0], X[y==1,1])
        plt.show()
此時繪製出來的決策邊界非常清晰，沒有那種特別不規則的邊界。換句話說，決策樹模型不會針對某幾個特別的樣本點進行特殊的變化。相對於前面默認參數的決策樹，顯然指定參數max_depth = 2 的決策樹模型的過擬合程度降低。當然此時的模型又可能欠擬合，所以對於這些參數，我們需要進行比較精細的調整，讓決策樹模型處在一個既不過擬合又不欠擬合的位置上。
指定 min_samples_split 參數為 10，節點再劃分所需要的最小樣本數為 10
 In[8]: dt_clf3 = DecisionTreeClassifier(min_samples_split=10)
        dt_clf3.fit(X, y)
        
        plot_decision_boundary(dt_clf3, axis=[-1.5, 2.5, -1.0, 1.5])
        plt.scatter(X[y==0,0], X[y==0,1])
        plt.scatter(X[y==1,0], X[y==1,1])
        plt.show()
此時繪製出來的決策邊界非常清晰，沒有那種特別不規則的邊界。換句話說，決策樹模型不會針對某幾個特別的樣本點進行特殊的變化。相對於前面默認參數的決策樹，顯然指定參數min_samples_split = 10 的決策樹模型的過擬合程度降低。
「將 min_samples_split 參數的值設置的越低，決策樹模型越容易發生過擬合。」 考慮極端情況下，如果將 min_samples_split 設置的值大於等於樣本總數，此時僅有的根節點不需要進行劃分，顯然此時僅有一個根節點的決策樹模型欠擬合。
指定 min_samples_leaf 參數為 6，葉子節點最少樣本數為 6
 In[9]: dt_clf4 = DecisionTreeClassifier(min_samples_leaf=6)
        dt_clf4.fit(X, y)
        
        plot_decision_boundary(dt_clf4, axis=[-1.5, 2.5, -1.0, 1.5])
        plt.scatter(X[y==0,0], X[y==0,1])
        plt.scatter(X[y==1,0], X[y==1,1])
        plt.show()
此時繪製出來的決策邊界非常清晰，沒有那種特別不規則的邊界。換句話說，決策樹模型不會針對某幾個特別的樣本點進行特殊的變化。相對於前面默認參數的決策樹，顯然指定參數min_samples_leaf = 6 的決策樹模型的過擬合程度降低。
「將 min_samples_leaf 參數的值設置的越低，決策樹模型越容易發生過擬合。」 考慮極端情況下，如果將 min_samples_leaf 設置為 1，對於只有一個樣本點的葉子節點，在具體預測的時候，測試樣本點需要根據所到達的葉子節點上的樣本點來決定預測的類別（或目標），而如果此時葉子節點僅有一個樣本點，那麼測試樣本點非常容易受到這一個樣本點的影響，測試樣本點的預測類別（或目標）會變得非常敏感。
指定 max_leaf_nodes 參數為 4，最大葉子節點數為 4
 In[10]: dt_clf5 = DecisionTreeClassifier(max_leaf_nodes=4)
         dt_clf5.fit(X, y)

         plot_decision_boundary(dt_clf5, axis=[-1.5, 2.5, -1.0, 1.5])
         plt.scatter(X[y==0,0], X[y==0,1])
         plt.scatter(X[y==1,0], X[y==1,1])
         plt.show()
此時繪製出來的決策邊界非常清晰，沒有那種特別不規則的邊界。換句話說，決策樹模型不會針對某幾個特別的樣本點進行特殊的變化。相對於前面默認參數的決策樹，顯然指定參數max_leaf_nodes = 4 的決策樹模型的過擬合程度降低。
「將 max_leaf_nodes 參數的值設置的越高，決策樹模型越容易發生過擬合。」
小結
「決策樹這種非參數學習很容易過擬合，所以在實際使用這些參數的時候，要注意避免決策樹模型被過渡調節參數，從而導致決策樹模型欠擬合。同時這些參數並不是相互獨立的，它們之間可以相互組合，所以可以使用網格搜索的方式尋找最優的參數組合。」
對於決策樹算法來說，可以調節的參數還有很多，「但是需要注意，無論將決策樹用於分類問題，還是用於回歸問題，可能無論怎樣調節這些參數都不能得到特別好的效果，這就是決策樹的局限性。」 儘管如此，決策樹依然非常重要，因為機器學習中非常重要的算法隨機森林，使用了決策樹的思想，所以本小節介紹的這些參數，也能夠用於隨機森林的調參。

相關焦點

  • 機器學習 | 決策樹之分類樹
    目前，機器學習在疾病的鑑別診斷，藥物的生產研究，臨床試驗研究，放射影像學等醫學領域已有十分廣泛的應用。今天推出機器學習系列筆記第1期，本期分享內容為：機器學習之決策樹中的分類樹。（筆者使用的是Mac系統）決策樹（Decision Tree)：是一種非參數的有監督學習算法，在已知各種情況發生概率的基礎上，通過構成決策樹來取淨現值的期望值大於等於零的概率，是直觀運用概率分析的圖解法，以解決分類和回歸問題。分為分類樹和回歸樹。
  • 機器學習決策樹:sklearn分類和回歸
    作者：alg-flody編輯：Emily昨天的推送機器學習：對決策樹剪枝，分析了決策樹需要剪枝，今天再就這個話題，藉助 sklearn 進一步分析決策樹分類和回歸時過擬合發生後，該如何解決的問題。上周推送的機器學習：談談決策樹，介紹了利用邏輯回歸算法，二分類一個擁有2個特徵的數據集，模擬的結果如下所示：
  • 機器學習中決策樹的原理與算法 | 科普
    我們知道，在機器學習中有兩類十分重要的問題，一類是分類問題，一類是回歸問題。我們今天所要探討的就是在分類和回歸問題中所用到的一種非常基本的方法，叫決策樹。決策樹也是重要的標籤學習方法。這篇文章裡面的部分內容來自於 AI 慕課學院的《機器學習理論與實戰高級特訓班》課程筆記。
  • 【機器學習】決策樹總結|ID3 C4.5/C5.0 CHAID CART與QUEST
    ● 決策樹剪枝● 決策樹算法     ● ID3     ● C4.5/C5.0     ● CHAID     ● CART     ● QUEST概要決策樹作為一種基本的分類與回歸方法（更多時候指分類），是學習數據挖掘與機器學習的首要算法
  • 進化決策樹:當機器學習從生物學中汲取靈感時
    圖1-日本的高速鐵路，新幹線，來源生物學知識也可以成為機器學習中靈感的來源。內容本文重點關注的一個例子是進化決策樹。然而，EDT的優勢在於它能提供這樣一棵決策樹：可以呈現多顆決策樹聚集的位點（與RF模型相比），並且具有魯棒性（與簡單DT模型相比），因為它是一群樹中表現最好的那顆。在訓練過程中，將最大深度設為2，獲得的EDT群體中表現最好的決策樹可以表徵為如下形式：
  • ID3、C4.5、CART決策樹介紹
    決策樹是一類常見的機器學習方法，它可以實現分類和回歸任務。決策樹同時也是隨機森林的基本組成部分，後者是現今最強大的機器學習算法之一。
  • 機器學習入門之決策樹1
    決策樹基本流程¶決策樹（Decision Tree）是一類常見的機器學習算法，其基本流程圖遵循簡單且直觀的 D&C策略。下面以西瓜問題來展示決策樹基本流程：西瓜屬性包含：[色澤, 根蒂, 敲聲]我們可能首先看「它是什麼顏色的？」，如果是「青綠色」「它的根蒂是什麼形態？」
  • 【量化課堂】決策樹入門及Python應用
    決策樹在機器學習領域的應用在於可以把人從浩如煙海的數據中解放出來，讓計算機去尋找數據之間的內在規律用於下一步研究，也可以直接使用決策樹的結論進行判斷，但不需要可視化的情況下目前更多的會去選擇Randomforest，Boosting等決策樹的改進。決策樹基於的假設較少，適用於大部分情況。
  • ​機器學習 | 決策樹之回歸樹
    目前，機器學習在疾病的鑑別診斷，藥物的生產研究，臨床試驗研究，放射影像學等醫學領域已有十分廣泛的應用。今天推出機器學習系列筆記第2期，本期分享內容為：機器學習之決策樹中的回歸樹。(random_state=25)#網格搜索的重要接口GS.best_params_ #返回輸入的的參數和參數取值的列表中的最佳組合GS.best_score_ #網格搜索後的模型的評判標準報錯：1）導入下載數據時路徑有問題，Mac的文件路徑不能只從簡介中找。
  • 機器學習實戰:決策樹原來這麼簡單
    上一篇：機器學習實戰-監督學習、無監督學習上一篇的文章中，我們主要對監督學習與無監督學習進行了講解，其實還有一個半監督學習，這個可以自行百度，也是比較簡單。這一篇中，我們來講解監督學習中經常用到的算法，決策樹。
  • 決策樹學習筆記(三):CART算法,決策樹總結
    ，旨在從最簡單的決策樹開始學習，循序漸進，最後理解並掌握複雜模型GBDT，Xgboost，為要想要深入了解機器學習算法和參加數據挖掘競賽的朋友提供幫助。本篇根據上面我們介紹兩個特徵類型情況重新給出一個算法流程（主要就是區分兩種不同特徵類型）：輸入：訓練數據集D，停止計算的參數條件。 輸出：CART決策樹。根據訓練數據集，從根結點開始，遞歸地對每個結點進行以下操作，構建二叉決策樹：1：如果樣本個數小於閾值或者沒有特徵，   則返回決策子樹，當前節點停止遞歸。
  • XGboost基礎之損失函數logloss和CART決策樹
    我們知道在邏輯回歸模型中，類別到XGboost，一般來說XGboost的基分類器為CART，這裡就可以求出能是LL最小的決策樹的參數了。決策樹的參數跟線性回歸公式又很不一樣，我這邊理解的是，其實決策樹也是函數，與數學上的示性函數類似（如下圖），所以決策樹的參數就是指它劃分的空間。
  • Python 環境下的自動化機器學習超參數調優
    機器學習算法的性能高度依賴於超參數的選擇，對機器學習超參數進行調優是一項繁瑣但卻至關重要的任務。本文介紹了一個使用「Hyperopt」庫對梯度提升機（GBM）進行貝葉斯超參數調優的完整示例，並著重介紹了其實現過程。由於機器學習算法的性能高度依賴於超參數的選擇，對機器學習超參數進行調優是一項繁瑣但至關重要的任務。
  • 機器學習入門 12-2 信息熵
    前言上一小節介紹了什麼是決策樹以及如何通過決策樹來進行具體的分類。構造決策樹的時候，每個節點其實都是一個判斷條件，為了得到這個判斷條件我們需要知道兩個信息：當確定某個維度之後，具體要在這個維度上的哪個值上進行劃分？這些信息該如何確定呢？本小節首先介紹一種方式：信息熵。
  • Python機器學習入門實例
    決策樹sklearn.tree類機器學習庫sklearn中的決策樹tree可用於分類決策算法，也可用於回歸決策算法。分類決策樹的類需要使用DecisionTreeClassifier（）方法。4.根據實驗檢測數據，得到實驗訓練數據列表：feature = [ [178,1], [155,0],[177,0], [165, 0], [169,1], [160, 0] ]對應的性別分類列表為：label = ['man', 'woman','man', 'woman', 'man', 'woman']    （2）創建決策樹對象
  • python分類-決策樹
    嘿嘿，這禮拜隨便研究了個入門的知識點，python決策樹。這次學會的只是一個入門級別的python決策樹案例，還是給大家分享下吧。
  • 機器學習入門 12-7 決策樹的局限性
    決策樹第一個局限性通過前幾個小節繪製使用決策樹來解決分類問題的決策邊界可以看出，決策樹的決策邊界都是橫平豎直的直線。上圖為決策樹在鳶尾花數據集（為了可視化方便，只選取後兩個特徵）上訓練後繪製的決策邊界。
  • 數據分析技術:決策樹分析;機器學習入門模型
    決策樹分析從上面介紹的內容可知，決策樹分析適用於有明確的研究對象分類結果，研究每種類別群體的屬性特點和性質，換種說法就是通過建立模型，可以通過某個研究對象身上的屬性特點，判斷該研究對象最可能落在那個分類群體中。決策樹分析在很多行業中應用得非常廣泛，同時也是機器學習中最基礎也是應用最廣泛的算法模型。
  • 極簡機器學習課程:使用決策樹計算圖像中的手指數
    Welch Labs的機器學習課程，是YouTube網紅頻道 3Blue1Brown力推的。這個系列課程通過計算機視覺領域的一個示例，來探索機器學習和人工智慧的複雜場景:使用決策樹來計算圖像中的手指數。
  • 數據挖掘從入門到放棄(二):決策樹
    」決策樹算法理解決策樹是直觀運用概率分析的樹形分類器，是很常用的分類方法，屬於監管學習，決策樹分類過程是從根節點開始，根據特徵屬性值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。比如說買瓜的時候，根據瓜的某些特徵屬性直觀判斷瓜的好壞，下圖依次根據紋理清晰度、根蒂、色澤、觸感4個進行分類，生活中我們會將某個最重要或最明顯的分類屬性放在第一位，然後是次重要屬性，這很符合我們平常的判斷思維，這就是決策樹！在特徵屬性非常大的時候，就出現了首選哪個特徵屬性進行分類？如何剪枝？分類的層次是多少？....