機器學習筆記21——決策樹之CART算法原理及python實作案例

CART算法

• 引言
• 1、概述
• 2、CART算法
• • 2.1 CART生成
  • • 2.1.1 回歸樹的生成
    • 2.1.2 分類樹的生成
  • 2.2 CART剪枝
  • • 2.2.1 剪枝，形成一個子樹序列
    • 2.2.2 在剪枝得到的子樹序列 T 0 , T 1 , T 2 , T 3 . . . . . . T n T_0,T_1,T_2,T_3......T_n T0​,T1​,T2​,T3​......Tn​中通過交叉驗證選取最優子樹 T α T_\alpha Tα​
    • 2.2.3 CART剪枝算法
• 3、基于scikit-learn決策樹算法類庫實作CART算法
• • 3.1 scikit-learn決策樹算法類庫概述
  • 3.2 實戰1—分類樹
  • 3.3 實戰2—回歸樹
• 4、決策樹算法小結

引言

\quad \quad 在決策樹、ID3、C4.5算法一文中，簡單地介紹了決策樹模型，以及決策樹生成算法ID3算法和ID3算法的改進版C4.5算法；在決策時剪枝算法一文中，簡單地介紹了剪枝的算法。我們也提到了它的不足，比如模型是用較為複雜的熵來度量，使用了相對較為複雜的多叉樹，隻能處理分類不能處理回歸等。對于這些問題， CART算法大部分做了改進。CART算法也就是我們下面的重點了。由于CART算法可以做回歸，也可以做分類，我們分别加以介紹，先從CART分類樹算法開始，重點比較和C4.5算法的不同點。接着介紹CART回歸樹算法，重點介紹和CART分類樹的不同點。然後我們讨論CART樹的建樹算法和剪枝算法，最後總結決策樹算法的優缺點。

1、概述

\quad \quad 所謂CART算法，全名叫Classification and Regression Tree，即分類與回歸樹。顧名思義，相較于此前的ID3算法和C4.5算法，CART除了可以用于分類任務外，還可以完成回歸分析。完整的CART算法包括特征選擇、決策樹生成和決策樹剪枝三個部分。

\quad \quad 有以下特點：

（1）CART是一棵二叉樹；

（2）CART算法主要包括回歸樹和分類樹兩種。回歸樹用于目标變量為連續型的模組化任務，其特征選擇準則用的是平方誤差最小準則。分類樹用于目标變量為離散型的的模組化任務，其特征選擇準則用的是基尼指數(Gini Index)，這也有别于此前ID3的資訊增益準則和C4.5的資訊增益比準則。無論是回歸樹還是分類樹，其算法核心都在于遞歸地選擇最優特征建構決策樹。

（3）CART作為一種單模型，也是GBDT的基模型。當很多棵CART分類樹或者回歸樹內建起來的時候，就形成了GBDT模型。關于GBDT，筆者将在後續中進行詳細講述，這裡不再展開。

2、CART算法

\quad \quad CART算法由以下兩步生成：

（1）決策樹生成：遞歸地建構二叉決策樹的過程，基于訓練資料集生成決策樹，生成的決策樹要盡量大；自上而下從根開始建立節點，在每個節點處要選擇一個最好的屬性來分裂，使得子節點中的訓練集盡量的純。不同的算法使用不同的名額來定義"最好"。

（2）決策樹剪枝：用驗證資料集對已生成的樹進行剪枝并選擇最優子樹，這時用損失函數最小作為剪枝的标準。【剪枝可以視為決策樹算法的一種正則化手段，作為一種基于規則的非參數監督學習方法，決策樹在訓練很容易過拟合，導緻最後生成的決策樹泛化性能不高。】

2.1 CART生成

\quad \quad CART算法的決策樹生成實作過程如下：

• 使用CART算法選擇特征
  • 對回歸樹用平方誤差最小化準測，進行特征選擇；
  • 對分類樹用基尼指數（GINI）最小化準則，進行特征選擇，
• 根據特征切分資料集合
• 建構樹

【代碼實作】簡單例子：根據特征切分資料集合

import numpy as np
# 函數說明:根據給定特征和特征值，将資料集分為兩個區域
"""
Parameters:
	dataSet - 資料集合
	feature - 待切分的特征
	value - 特征的某個值
Returns:
    mat0-切分的資料集合0
    mat1-切分的資料集1
"""

def binSplitDataSet(dataSet,feature,value):
    mat0=dataSet[np.nonzero(dataSet[:,feature]>value)[0],:]
    mat1=dataSet[np.nonzero(dataSet[:,feature]<=value)[0],:]
    return mat0,mat1
if __name__=='__main__':
    testMat=np.mat(np.eye(4))
    mat0,mat1=binSplitDataSet(testMat,1,0.5)
    mat0, mat1 = binSplitDataSet(testMat, 1, 0.5)
    print("原始集合:\n", testMat)
    print("mat0：\n", mat0)
    print("mat1：\n", mat1)
           

原始集合:

[[1. 0. 0. 0.]

[0. 1. 0. 0.]

[0. 0. 1. 0.]

[0. 0. 0. 1.]]

mat0：

[[0. 1. 0. 0.]]

mat1：

[[1. 0. 0. 0.]

[0. 0. 1. 0.]

[0. 0. 0. 1.]]

2.1.1 回歸樹的生成

劃分的準則是平方誤差最小化

\quad \quad 假設X與Y分别為輸入和輸出變量，并且Y是連續變量，給定訓練資料集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y n ) } D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_n)\} D={(x1​,y1​),(x2​,y2​),...,(xN​,yn​)}

假定已将輸入空間劃分為M個單元 R 1 , R 2 , . . . , R M R_1,R_2,...,R_M R1​,R2​,...,RM​，并且在每個單元 R M R_M RM​上有一個固定的輸出值 c m c_m cm​,則

回歸模型：

f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) f(x)=\sum_{m=1}^Mc_mI(x\in R_m) f(x)=m=1∑M​cm​I(x∈Rm​)

預測誤差：平方誤差

∑ x i ∈ R m ( y i − f ( x i ) ) 2 \sum_{x_i\in R_m}(y_i-f(x_i))^2 xi​∈Rm​∑​(yi​−f(xi​))2

如何選擇每一個單元上的最優輸出值 c m c_m cm​？

\quad \quad 用平方誤差最小的準則求解每個單元上的最優輸出值得單元 R M R_M RM​上的 c m c_m cm​的最優值 c m ^ \hat{c_m} cm​^​是 R M R_M RM​上的所有輸入執行個體 x i x_i xi​對應的輸出 y i y_i yi​的均值，即

c m ^ = a v e ( y i ∣ x i ∈ R m ) \hat{c_m}=ave(y_i|x_i\in R_m) cm​^​=ave(yi​∣xi​∈Rm​)

如何對輸入空間進行劃分？

\quad \quad 采用啟發式即二進制切分的方法，假設選擇第j個變量 x ( j ) x^{(j)} x(j)和它的取值s，作為切分變量和切分點，那麼就會得到兩個區域：

R 1 ( j , s ) = { x ∣ x ( j ) ≤ s }   和   R 2 ( j , s ) = { x ∣ x ( j ) > s } R_1(j,s)=\{x|x^{(j)}\leq s\} \ 和\ R_2(j,s)=\{x|x^{(j)}> s\} R1​(j,s)={x∣x(j)≤s} 和 R2​(j,s)={x∣x(j)>s}

當j和s固定時，我們要找到兩個區域的代表值c1，c2使各自區間上的平方差最小：

m i n j , s [ m i n c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + m i n c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \mathop{min}\limits_{j,s}[\mathop{min}\limits_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\mathop{min}\limits_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2] j,smin​[c1​min​xi​∈R1​(j,s)∑​(yi​−c1​)2+c2​min​xi​∈R2​(j,s)∑​(yi​−c2​)2]

前面已經知道c1，c2為區間上的平均：

c 1 ^ = a v e ( y i ∣ x i ∈ R 1 ( j , s ) )   和   c 2 ^ = a v e ( y i ∣ x i ∈ R 2 ( j , s ) ) \hat{c_1}=ave(y_i|x_i\in R_1(j,s)) \ 和 \ \hat{c_2}=ave(y_i|x_i\in R_2(j,s)) c1​^​=ave(yi​∣xi​∈R1​(j,s)) 和 c2​^​=ave(yi​∣xi​∈R2​(j,s))

那麼對固定的 j 隻需要找到最優的s，然後通過周遊所有的變量，我們可以找到最優的j，這樣我們就可以得到最優對（j，s），并得到兩個區間。

\quad \quad 這樣的回歸樹通常稱為最小二乘回歸樹。算法具體流程如下：

算法5.5 （最小二乘回歸樹生成算法）

輸入：訓練資料集D

輸出：回歸樹 f ( x ) f(x) f(x)

\quad \quad 在訓練資料集所在的輸入空間中，遞歸地将每一個區域劃分為兩個子區域并決定每個子區域上的輸出值，建構二叉決策樹：

（1）選擇最優切分變量 j 和切分點 s，求解

m i n j , s [ m i n c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + m i n c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \mathop{min}\limits_{j,s}[\mathop{min}\limits_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\mathop{min}\limits_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2] j,smin​[c1​min​xi​∈R1​(j,s)∑​(yi​−c1​)2+c2​min​xi​∈R2​(j,s)∑​(yi​−c2​)2]

周遊變量j，對固定的切分變量j掃描切分點s,選擇使上式達到最小值的對(j,s)

（2）用標明的對 (j,s) 劃分區域，并決定相應的輸出值 c：

R 1 ( j , s ) = { x ∣ x ( j ) ≤ s }   ，   R 2 ( j , s ) = { x ∣ x ( j ) > s } c m ^ = 1 N m ∑ x i ∈ R m ( j , s ) y i   x ∈ R m , m = 1 , 2 R_1(j,s)=\{x|x^{(j)}\leq s\} \ ，\ R_2(j,s)=\{x|x^{(j)}> s\}\\ \hat{c_m}=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i\,x\in R_m,m=1,2 R1​(j,s)={x∣x(j)≤s} ， R2​(j,s)={x∣x(j)>s}cm​^​=Nm​1​xi​∈Rm​(j,s)∑​yi​x∈Rm​,m=1,2

（3）繼續對兩個子區域調用步驟（1）（2），直至滿足停止條件。

（4）将輸入空間劃分為M個區域 R 1 , R 2 , . . . , R M R_1,R_2,...,R_M R1​,R2​,...,RM​,生成決策樹：

f ( x ) = ∑ m = 1 M c m ^ I ( x ∈ R m ) f(x)=\sum_{m=1}^M\hat{c_m}I(x\in R_m) f(x)=m=1∑M​cm​^​I(x∈Rm​)

\quad \quad 除此之外，我們再定義兩個參數，tolS和tolN，分别用于控制誤差變化限制和切分特征最少樣本數。這兩個參數的意義是什麼呢？就是防止過拟合，提前設定終止條件，實際上是在進行一種所謂的預剪枝（prepruning）操作，在下一小節會進行進一步講解。

【python代碼實作CART回歸樹】

1、建立小資料集并可視化

#-*- coding:utf-8 -*-
import matplotlib.pyplot as plt
import numpy as np

def loadDataSet(fileName):
    """
    函數說明:加載資料
    Parameters:
        fileName - 檔案名
    Returns:
        dataMat - 資料矩陣
   
    """
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        fltLine = list(map(float, curLine))                    #轉化為float類型
        dataMat.append(fltLine)
    return dataMat

def plotDataSet(filename):
    """
    函數說明:繪制資料集
    Parameters:
        filename - 檔案名
    Returns:
        無
   
    """
    dataMat = loadDataSet(filename)                                        #加載資料集
    n = len(dataMat)                                                    #資料個數
    xcord = []; ycord = []                                                #樣本點
    for i in range(n):                                                    
        xcord.append(dataMat[i][0]); ycord.append(dataMat[i][1])        #樣本點
    fig = plt.figure()
    ax = fig.add_subplot(111)                                            #添加subplot
    ax.scatter(xcord, ycord, s = 20, c = 'blue',alpha = .5)                #繪制樣本點
    plt.title('DataSet')                                                #繪制title
    plt.xlabel('X')
    plt.show()

if __name__ == '__main__':
    filename = 'E:\jupyter-notebook\CARTdata.txt'
    plotDataSet(filename)
           

2、找到最佳切分函數

#-*- coding:utf-8 -*-
import numpy as np

def loadDataSet(fileName):#加載資料集
    """
    函數說明:加載資料
    Parameters:
        fileName - 檔案名
    Returns:
        dataMat - 資料矩陣
    
    """
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        fltLine = list(map(float, curLine))                    #轉化為float類型
        dataMat.append(fltLine)
    return dataMat

def binSplitDataSet(dataSet, feature, value):# 二進制法劃分資料集
    """
    函數說明:根據特征切分資料集合
    Parameters:
        dataSet - 資料集合
        feature - 帶切分的特征
        value - 該特征的值
    Returns:
        mat0 - 切分的資料集合0
        mat1 - 切分的資料集合1
   
    """
    mat0 = dataSet[np.nonzero(dataSet[:,feature] > value)[0],:]
    mat1 = dataSet[np.nonzero(dataSet[:,feature] <= value)[0],:]
    return mat0, mat1
def regLeaf(dataSet):
    """
    函數說明:生成葉結點
    Parameters:
        dataSet - 資料集合
    Returns:
        目标變量的均值
  
    """
    return np.mean(dataSet[:,-1])
def regErr(dataSet):
    """
    函數說明:誤差估計函數
    Parameters:
        dataSet - 資料集合
    Returns:
        目标變量的總方差
  
    """
    return np.var(dataSet[:,-1]) * np.shape(dataSet)[0]

def chooseBestSplit(dataSet, leafType = regLeaf, errType = regErr, ops = (1,4)):
    """
    函數說明:找到資料的最佳二進制切分方式函數
    Parameters:
        dataSet - 資料集合
        leafType - 生成葉結點
        regErr - 誤差估計函數
        ops - 使用者定義的參數構成的元組
    Returns:
        bestIndex - 最佳切分特征
        bestValue - 最佳特征值
    
    """
    import types
    #tolS允許的誤差下降值,tolN切分的最少樣本數
    tolS = ops[0]; tolN = ops[1]
    #如果目前所有值相等,則退出。(根據set的特性)
    if len(set(dataSet[:,-1].T.tolist()[0])) == 1:
        return None, leafType(dataSet)
    #統計資料集合的行m和列n
    m, n = np.shape(dataSet)
    #預設最後一個特征為最佳切分特征,計算其誤差估計
    S = errType(dataSet)
    #分别為最佳誤差,最佳特征切分的索引值,最佳特征值
    bestS = float('inf'); bestIndex = 0; bestValue = 0
    #周遊所有特征列
    for featIndex in range(n - 1):
        #周遊所有特征值
        for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]):
            #根據特征和特征值切分資料集
            mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
            #如果資料少于tolN,則退出
            if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN): continue
            #計算誤差估計
            newS = errType(mat0) + errType(mat1)
            #如果誤差估計更小,則更新特征索引值和特征值
            if newS < bestS:
                bestIndex = featIndex
                bestValue = splitVal
                bestS = newS
    #如果誤差減少不大則退出
    if (S - bestS) < tolS:
        return None, leafType(dataSet)
    #根據最佳的切分特征和特征值切分資料集合
    mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
    #如果切分出的資料集很小則退出
    if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):
        return None, leafType(dataSet)
    #傳回最佳切分特征和特征值
    return bestIndex, bestValue

if __name__ == '__main__':
    myDat = loadDataSet('E:\jupyter-notebook\CARTdata.txt')
    myMat = np.mat(myDat)
    feat, val = chooseBestSplit(myMat, regLeaf, regErr, (1, 4))
    print(feat)
    print(val)
           

3、建立回歸樹

#-*- coding:utf-8 -*-
import numpy as np

def loadDataSet(fileName):
    """
    函數說明:加載資料
    Parameters:
        fileName - 檔案名
    Returns:
        dataMat - 資料矩陣
   
    """
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        fltLine = list(map(float, curLine))                    #轉化為float類型
        dataMat.append(fltLine)
    return dataMat

def binSplitDataSet(dataSet, feature, value):
    """
    函數說明:根據特征切分資料集合
    Parameters:
        dataSet - 資料集合
        feature - 帶切分的特征
        value - 該特征的值
    Returns:
        mat0 - 切分的資料集合0
        mat1 - 切分的資料集合1
    
    """
    mat0 = dataSet[np.nonzero(dataSet[:,feature] > value)[0],:]
    mat1 = dataSet[np.nonzero(dataSet[:,feature] <= value)[0],:]
    return mat0, mat1

def regLeaf(dataSet):
    """
    函數說明:生成葉結點
    Parameters:
        dataSet - 資料集合
    Returns:
        目标變量的均值
    
    """
    return np.mean(dataSet[:,-1])

def regErr(dataSet):
    """
    函數說明:誤差估計函數
    Parameters:
        dataSet - 資料集合
    Returns:
        目标變量的總方差
   
    """
    return np.var(dataSet[:,-1]) * np.shape(dataSet)[0]

def chooseBestSplit(dataSet, leafType = regLeaf, errType = regErr, ops = (1,4)):
    """
    函數說明:找到資料的最佳二進制切分方式函數
    Parameters:
        dataSet - 資料集合
        leafType - 生成葉結點
        regErr - 誤差估計函數
        ops - 使用者定義的參數構成的元組
    Returns:
        bestIndex - 最佳切分特征
        bestValue - 最佳特征值
    
    """
    import types
    #tolS允許的誤差下降值,tolN切分的最少樣本數
    tolS = ops[0]; tolN = ops[1]
    #如果目前所有值相等,則退出。(根據set的特性)
    if len(set(dataSet[:,-1].T.tolist()[0])) == 1:
        return None, leafType(dataSet)
    #統計資料集合的行m和列n
    m, n = np.shape(dataSet)
    #預設最後一個特征為最佳切分特征,計算其誤差估計
    S = errType(dataSet)
    #分别為最佳誤差,最佳特征切分的索引值,最佳特征值
    bestS = float('inf'); bestIndex = 0; bestValue = 0
    #周遊所有特征列
    for featIndex in range(n - 1):
        #周遊所有特征值
        for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]):
            #根據特征和特征值切分資料集
            mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
            #如果資料少于tolN,則退出
            if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN): continue
            #計算誤差估計
            newS = errType(mat0) + errType(mat1)
            #如果誤差估計更小,則更新特征索引值和特征值
            if newS < bestS:
                bestIndex = featIndex
                bestValue = splitVal
                bestS = newS
    #如果誤差減少不大則退出
    if (S - bestS) < tolS:
        return None, leafType(dataSet)
    #根據最佳的切分特征和特征值切分資料集合
    mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
    #如果切分出的資料集很小則退出
    if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):
        return None, leafType(dataSet)
    #傳回最佳切分特征和特征值
    return bestIndex, bestValue

def createTree(dataSet, leafType = regLeaf, errType = regErr, ops = (1, 4)):
    """
    函數說明:樹建構函數
    Parameters:
        dataSet - 資料集合
        leafType - 建立葉結點的函數
        errType - 誤差計算函數
        ops - 包含樹建構所有其他參數的元組
    Returns:
        retTree - 建構的回歸樹
  
    """
    #選擇最佳切分特征和特征值
    feat, val = chooseBestSplit(dataSet, leafType, errType, ops)
    #r如果沒有特征,則傳回特征值
    if feat == None: return val
    #回歸樹
    retTree = {}
    retTree['spInd'] = feat
    retTree['spVal'] = val
    #分成左資料集和右資料集
    lSet, rSet = binSplitDataSet(dataSet, feat, val)
    #建立左子樹和右子樹
    retTree['left'] = createTree(lSet, leafType, errType, ops)
    retTree['right'] = createTree(rSet, leafType, errType, ops)
    return retTree  

if __name__ == '__main__':
    myDat = loadDataSet('E:\jupyter-notebook\CARTdata.txt')
    myMat = np.mat(myDat)
    print(createTree(myMat))
           

{‘spInd’: 0, ‘spVal’: 0.48813, ‘left’: 1.0180967672413792, ‘right’: -0.04465028571428572}

2.1.2 分類樹的生成

分類樹用基尼指數選擇最優特征，同時決定該特征的最優二值切分點。

定義（基尼指數）：

\quad \quad 分類問題中，假設有 K K K個類别，樣本點屬于第 k k k類别的機率為 p k p_k pk​, 則機率分布的基尼指數定義為：

G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2 Gini(p)=k=1∑K​pk​(1−pk​)=1−k=1∑K​pk2​

\quad \quad 對于二分類問題，若樣本點屬于第1個類的機率是p,則機率分布的基尼指數為 G i n i ( p ) = 2 p ( 1 − p ) Gini(p)=2p(1-p) Gini(p)=2p(1−p)

\quad \quad 對于給定的樣本集合 D D D,假設有 K K K個類别, 第k個類别的數量為 C k C_k Ck​,則樣本D的基尼系數表達式為：

G i n i ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2 Gini(D)=1−k=1∑K​(∣D∣∣Ck​∣​)2

\quad \quad 特别的，對于樣本 D D D,如果根據特征 A A A的某個值a,把 D D D分成 D 1 D_1 D1​和 D 2 D_2 D2​兩部分，則在特征 A A A的條件下， D D D的基尼指數表達式為：

G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)

\quad \quad 基尼指數 G i n i ( D ) Gini(D) Gini(D)表示集合 D D D的不确定性，基尼指數 G i n i ( D ， A ) Gini(D，A) Gini(D，A)表示經 A = a A=a A=a分割後集合 D D D的不确定性。基尼指數越大，樣本集合的不确定性也就越大，這一點與熵相似。

\quad \quad 對于二類分類，基尼指數和熵之半以及分類誤差率的曲線如下：

\quad \quad 從上圖可以看出，基尼系數和熵之半的曲線非常接近，僅僅在45度角附近誤差稍大。是以，基尼系數可以做為熵模型的一個近似替代。而CART分類樹算法就是使用的基尼系數來選擇決策樹的特征。同時，為了進一步簡化，CART分類樹算法每次僅僅對某個特征的值進行二分，而不是多分，這樣CART分類樹算法建立起來的是二叉樹，而不是多叉樹。這樣一可以進一步簡化基尼系數的計算，二可以建立一個更加優雅的二叉樹模型。

\quad \quad 分類樹生成算法具體如下：

輸入：訓練資料集，停止計算的條件

輸出：CART決策樹即分類樹

根據訓練資料集，從根結點開始，遞歸地對每個結點進行以下操作，建構二叉決策樹

（1）訓練資料集為D,計算現有特征對訓練資料集的基尼指數，此時對于每一個特征A,對其可能取得每一個值a，根據此值将訓練樣本切分為 D 1 D_1 D1​和 D 2 D_2 D2​兩部分，然後根據上式計算A=a基尼指數。

（2）在所有可能的特征A以及所有可能的切分點a中，選擇基尼指數最小的特征及其對應的切分點作為最優的特征及切分點，從結點生成兩個子結點，将訓練資料集配置設定到子結點中去。

（3）遞歸的調用（1 ），（2）， 直到滿足停止的條件

（4）生成分類決策樹

\quad \quad 算法停止計算的條件是節點中的樣本個數小于預定門檻值，或樣本集的基尼指數小于預定門檻值（樣本基本屬于同一類），或者沒有更多特征。

【python手寫實作CART分類樹】

from math import log
import operator
 
def createDataSet1():
    """
    創造示例資料/讀取資料
    @param dataSet: 資料集
    @return dataSet labels：資料集 特征集
    """
    # 資料集
    dataSet = [('青年', '否', '否', '一般', '不同意'),
               ('青年', '否', '否', '好', '不同意'),
               ('青年', '是', '否', '好', '同意'),
               ('青年', '是', '是', '一般', '同意'),
               ('青年', '否', '否', '一般', '不同意'),
               ('中年', '否', '否', '一般', '不同意'),
               ('中年', '否', '否', '好', '不同意'),
               ('中年', '是', '是', '好', '同意'),
               ('中年', '否', '是', '非常好', '同意'),
               ('中年', '否', '是', '非常好', '同意'),
               ('老年', '否', '是', '非常好', '同意'),
               ('老年', '否', '是', '好', '同意'),
               ('老年', '是', '否', '好', '同意'),
               ('老年', '是', '否', '非常好', '同意'),
               ('老年', '否', '否', '一般', '不同意')]
    # 特征集
    labels = ['年齡', '有工作', '有房子', '信貸情況']
    return dataSet,labels
 
def calcProbabilityEnt(dataSet):
    """
    樣本點屬于第1個類的機率p，即計算2p(1-p)中的p
    @param dataSet: 資料集
    @return probabilityEnt: 資料集的機率
    """
    numEntries = len(dataSet)  # 資料條數
    feaCounts = 0
    fea1 = dataSet[0][len(dataSet[0]) - 1]
    for featVec in dataSet:  # 每行資料
        if featVec[-1] == fea1:
            feaCounts += 1
    probabilityEnt = float(feaCounts) / numEntries
    return probabilityEnt
 
def splitDataSet(dataSet, index, value):
    """
    劃分資料集，提取含有某個特征的某個屬性的所有資料
    @param dataSet: 資料集
    @param index: 屬性值所對應的特征列
    @param value: 某個屬性值
    @return retDataSet: 含有某個特征的某個屬性的資料集
    """
    retDataSet = []
    for featVec in dataSet:
        # 如果該樣本該特征的屬性值等于傳入的屬性值，則去掉該屬性然後放入資料集中
        if featVec[index] == value:
            reducedFeatVec = featVec[:index] + featVec[index+1:] # 去掉該屬性的目前樣本
            retDataSet.append(reducedFeatVec) # append向末尾追加一個新元素，新元素在元素中格式不變，如數組作為一個值在元素中存在
    return retDataSet
 
def chooseBestFeatureToSplit(dataSet):
    """
    選擇最優特征
    @param dataSet: 資料集
    @return bestFeature: 最優特征所在列
    """
    numFeatures = len(dataSet[0]) - 1 # 特征總數
    if numFeatures == 1:  # 當隻有一個特征時
        return 0
    bestGini = 1  # 最佳基尼系數
    bestFeature = -1  # 最優特征
    for i in range(numFeatures):
        uniqueVals = set(example[i] for example in dataSet) # 去重，每個屬性值唯一
        feaGini = 0 # 定義特征的值的基尼系數
        # 依次計算每個特征的值的熵
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet,i,value) # 根據該特征屬性值分的類
                                                       # 參數：原資料、循環次數(目前屬性值所在列)、目前屬性值
            prob = len(subDataSet) / float(len(dataSet))
            probabilityEnt = calcProbabilityEnt(subDataSet)
            feaGini += prob * (2 * probabilityEnt * (1 - probabilityEnt))
        if (feaGini < bestGini):  # 基尼系數越小越好
            bestGini = feaGini
            bestFeature = i
    return bestFeature
 
def majorityCnt(classList):
    """
    對最後一個特征分類，出現次數最多的類即為該屬性類别，比如：最後分類為2男1女，則判定為男
    @param classList: 資料集，也是類别集
    @return sortedClassCount[0][0]: 該屬性的類别
    """
    classCount = {}
    # 計算每個類别出現次數
    for vote in classList:
        try:
            classCount[vote] += 1
        except KeyError:
            classCount[vote] = 1
    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True) # 出現次數最多的類别在首位
                                                    # 對第1個參數，按照參數的第1個域來進行排序（第2個參數），然後反序（第3個參數）
    return sortedClassCount[0][0] # 該屬性的類别
 
def createTree(dataSet,labels):
    """
    對最後一個特征分類，按分類後類别數量排序，比如：最後分類為2同意1不同意，則判定為同意
    @param dataSet: 資料集
    @param labels: 特征集
    @return myTree: 決策樹
    """
    classList = [example[-1] for example in dataSet]  # 擷取每行資料的最後一個值，即每行資料的類别
    # 當資料集隻有一個類别
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 當資料集隻剩一列（即類别），即根據最後一個特征分類
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    # 其他情況
    bestFeat = chooseBestFeatureToSplit(dataSet) # 選擇最優特征（所在列）
    bestFeatLabel = labels[bestFeat] # 最優特征
    del(labels[bestFeat]) # 從特征集中删除目前最優特征
    uniqueVals = set(example[bestFeat] for example in dataSet) # 選出最優特征對應屬性的唯一值
    myTree = {bestFeatLabel:{}} # 分類結果以字典形式儲存
    for value in uniqueVals:
        subLabels = labels[:] # 深拷貝，拷貝後的值與原值無關（普通複制為淺拷貝，對原值或拷貝後的值的改變互相影響）
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels) # 遞歸調用建立決策樹
    return myTree
 
 
if __name__ == '__main__':
    dataSet, labels = createDataSet1()  # 創造示列資料
    print(createTree(dataSet, labels))  # 輸出決策樹模型結果
           

2.2 CART剪枝

\quad \quad 由于決策時算法很容易對訓練集過拟合，而導緻泛化能力差，為了解決這個問題，我們需要對CART樹進行剪枝，即類似于線性回歸的正則化，來增加決策樹的泛化能力。但是，有很多的剪枝方法，我們應該這麼選擇呢？CART采用的辦法是後剪枝法，即先生成決策樹，然後産生所有可能的剪枝後的CART樹，然後使用交叉驗證來檢驗各種剪枝的效果，選擇泛化能力最好的剪枝政策。

\quad \quad CART回歸樹和CART分類樹的剪枝政策除了在度量損失的時候一個使用均方差，一個使用基尼系數，算法基本完全一樣。

\quad \quad CART剪枝算法由兩步組成：

• 首先從生成算法産生的決策樹 T 0 T_0 T0​底端開始不斷的剪枝，直到 T 0 T_0 T0​的根結點，形成子樹序列 { T 0 , T 1 , T 2 , T 3 . . . . . . T n } \{T_0,T_1,T_2,T_3......T_n\} {T0​,T1​,T2​,T3​......Tn​} T 0 T_0 T0​就是沒剪的，T1就是剪了一個葉結點的，T2就是又剪了一點的這樣子哦！
• 然後通過交叉驗證法在獨立的驗證資料集上對子樹序列進行測試，從中選擇最優子樹，具體操作如下。

2.2.1 剪枝，形成一個子樹序列

\quad \quad 在剪枝的過程中，對于任意的一刻子樹T,其損失函數為：

C α ( T ) = C ( T ) + α ∣ T ∣ C_\alpha(T)=C(T)+\alpha|T| Cα​(T)=C(T)+α∣T∣

\quad \quad 其中， T T T為任意子樹，C(T)為訓練資料的預測誤差，分類樹是用基尼系數度量，回歸樹是均方差度量， ∣ T ∣ |T| ∣T∣為子樹的葉節點個數， α ≥ 0 \alpha\geq0 α≥0為正則化參數，權衡訓練資料的拟合程度與模型的複雜度。

\quad \quad 當α=0時，即沒有正則化，原始的生成的CART樹即為最優子樹。當α=∞時，即正則化強度達到最大，此時由原始的生成的CART樹的根節點組成的單節點樹為最優子樹。當然，這是兩種極端情況。一般來說，α越大，則剪枝剪的越厲害，生成的最優子樹相比原生決策樹就越偏小。對于固定的α，一定存在使損失函數 C α ( T ) C_α(T) Cα​(T)最小的唯一子樹。

剪枝的思路:

\quad \quad 可以用遞歸的方法對樹進行剪枝。将 α \alpha α從小增大， 0 = α 0 < α 1 < . . . < α n < + ∞ 0=\alpha_0<\alpha_1<...<\alpha_n<+∞ 0=α0​<α1​<...<αn​<+∞,産生一系列的區間 [ α i , α i + 1 ) , i = 0 , 1 , . . . , n [\alpha_i,\alpha_{i+1}),i=0,1,...,n [αi​,αi+1​),i=0,1,...,n;剪枝得到的子樹序列對應着區間 α ∈ [ α i , α i + 1 ) , i = 0 , 1 , . . . , n \alpha\in[\alpha_i,\alpha_{i+1}),i=0,1,...,n α∈[αi​,αi+1​),i=0,1,...,n的最優子樹序列 { T 0 , T 1 , . . . , T n } \{T_0,T_1,...,T_n\} {T0​,T1​,...,Tn​},序列中的子樹是嵌套的。

\quad \quad 具體地，從整體數 T 0 T_0 T0​開始剪枝。

• 對 T 0 T_0 T0​的任意内部結點t,以t為單結點樹的損失函數為

  C α ( t ) = C ( t ) + α C_\alpha(t)=C(t)+\alpha Cα​(t)=C(t)+α

• 以t為根節點的子樹 T t T_t Tt​的損失函數是

  C α ( T t ) = C ( T t ) + α ∣ T t ∣ C_\alpha(T_t)=C(T_t)+\alpha|T_t| Cα​(Tt​)=C(Tt​)+α∣Tt​∣

• 當α=0或者α很小時， C α ( T t ) < C α ( t ) C_α(T_t)<C_α(t) Cα​(Tt​)<Cα​(t) , 當α增大到一定的程度時,在某一 α \alpha α有

  C α ( T t ) = C α ( t ) C_α(T_t)=C_α(t) Cα​(Tt​)=Cα​(t)

  當α繼續增大時不等式反向，也就是說，如果滿足下式：

α = C ( T ) − C ( T t ) ∣ T t ∣ − 1 α=\frac{C(T)−C(T_t)}{|T_t|−1} α=∣Tt​∣−1C(T)−C(Tt​)​

T t T_t Tt​和t有相同的損失函數，但是t節點更少，是以t比 T t T_t Tt​更可取，對 T t T_t Tt​進行剪枝。

\quad \quad 為此，對 T 0 T_0 T0​中每一内部結點t，計算

g ( t ) = C ( T ) − C ( T t ) ∣ T t ∣ − 1 g(t)=\frac{C(T)−C(T_t)}{|T_t|−1} g(t)=∣Tt​∣−1C(T)−C(Tt​)​

它表示剪枝後整體損失函數減少的程度。在 T 0 T_0 T0​中剪去 g ( t ) g(t) g(t)最小的 T t T_t Tt​，将得到的子樹作為 T 1 T_1 T1​，同時将最小的 g ( t ) g(t) g(t)設為 α 1 \alpha_1 α1​。 T 1 T_1 T1​為區間 [ α 1 , α 2 ) [\alpha_1,\alpha_2) [α1​,α2​)的最優子樹。

\quad \quad 如此剪枝下去，直至得到根結點。在這一過程中，不斷地增加 α \alpha α的值，産生新的區間。

2.2.2 在剪枝得到的子樹序列 T 0 , T 1 , T 2 , T 3 . . . . . . T n T_0,T_1,T_2,T_3......T_n T0​,T1​,T2​,T3​......Tn​中通過交叉驗證選取最優子樹 T α T_\alpha Tα​

\quad \quad 利用平方誤差準則或者是基尼指數準則，在新的驗證集中分别測試子樹序列，選取裡面最優的子樹進行輸出，便是裁剪之後的子樹，即得到最優決策樹

2.2.3 CART剪枝算法

算法 5.7 （CART 剪枝算法）

輸入：CART算法生成的決策樹

輸出：最優決策樹 T α T_\alpha Tα​

（1）設 k = 0 k=0 k=0, T = T 0 T=T_0 T=T0​

（2）設 α = + ∞ \alpha=+∞ α=+∞（正無窮）

（3）自下而上的對内部結點t進行計算 C ( T t ) C(T_t) C(Tt​), ∣ T t ∣ |T_t| ∣Tt​∣和 g ( t ) = C ( t ) − C ( T t ) ∣ T t ∣ − 1 ， α = m i n ( α , g ( t ) ) g(t)=\frac{C(t)-C(T_{t})}{|T_{t}|-1}，\alpha=min(\alpha,g(t)) g(t)=∣Tt​∣−1C(t)−C(Tt​)​，α=min(α,g(t))

其中， T t T_t Tt​表示以t為根結點的子樹， C ( T t ) C(T_t) C(Tt​)是對訓練資料的預測誤差， ∣ T t ∣ |T_t| ∣Tt​∣是 T t T_t Tt​的葉結點個數。

（4）自上而下地通路内部結點t，如果有 g ( t ) = α g(t)=\alpha g(t)=α的内部結點,則進行剪枝，并對葉結點t以多數表決法決定其類，得到樹T

（5） 設 k = k + 1 , α k = α ， T k = T k=k+1,\alpha_k=\alpha，T_k=T k=k+1,αk​=α，Tk​=T

（6 ）如果T不是由根結點單獨構成的樹，回到步驟4,

（7 ）采用交叉驗證法在子樹序列上進行驗證選取最優子樹 T α T_\alpha Tα​

# -*- coding: utf-8 -*-

import numpy as np
import pickle
import treePlotter


def loadDataSet(filename):
    '''
    輸入：檔案的全路徑
    功能：将輸入資料儲存在datamat
    輸出：datamat
    '''
    fr = open(filename)
    datamat = []
    for line in fr.readlines():
        cutLine = line.strip().split('\t')
        floatLine = map(float,cutLine)
        datamat.append(floatLine)
    return datamat


def binarySplitDataSet(dataset,feature,value):
    '''
    輸入：資料集，資料集中某一特征列，該特征列中的某個取值
    功能：将資料集按特征列的某一取值換分為左右兩個子資料集
    輸出：左右子資料集
    '''
    matLeft = dataset[np.nonzero(dataset[:,feature] <= value)[0],:]
    matRight = dataset[np.nonzero(dataset[:,feature] > value)[0],:]
    return matLeft,matRight

#--------------回歸樹所需子函數---------------#

def regressLeaf(dataset):
    '''
    輸入：資料集
    功能：求資料集輸出列的均值
    輸出：對應資料集的葉節點
    '''
    return np.mean(dataset[:,-1])


def regressErr(dataset):
    '''
    輸入：資料集(numpy.mat類型)
    功能：求資料集劃分左右子資料集的誤差平方和之和
    輸出: 資料集劃分後的誤差平方和
    '''
    #由于回歸樹中用輸出的均值作為葉節點，是以在這裡求誤差平方和實質上就是方差
    return np.var(dataset[:,-1]) * np.shape(dataset)[0]

def regressData(filename):
    fr = open(filename)
    return pickle.load(fr)

#--------------回歸樹子函數  END  --------------#

def chooseBestSplit(dataset,leafType=regressLeaf,errType=regressErr,threshold=(1,4)):#函數做為參數，挺有意思
    thresholdErr = threshold[0];thresholdSamples = threshold[1]
    #當資料中輸出值都相等時，feature = None,value = 輸出值的均值（葉節點）
    if len(set(dataset[:,-1].T.tolist()[0])) == 1:
        return None,leafType(dataset)
    m,n = np.shape(dataset)
    Err = errType(dataset)
    bestErr = np.inf; bestFeatureIndex = 0; bestFeatureValue = 0
    for featureindex in range(n-1):
        for featurevalue in dataset[:,featureindex]:
            matLeft,matRight = binarySplitDataSet(dataset,featureindex,featurevalue)
            if (np.shape(matLeft)[0] < thresholdSamples) or (np.shape(matRight)[0] < thresholdSamples):
                continue
            temErr = errType(matLeft) + errType(matRight)
            if temErr < bestErr:
                bestErr = temErr
                bestFeatureIndex = featureindex
                bestFeatureValue = featurevalue
    #檢驗在所選出的最優劃分特征及其取值下，誤差平方和與未劃分時的差是否小于門檻值，若是，則不适合劃分
    if (Err - bestErr) < thresholdErr:
        return None,leafType(dataset)
    matLeft,matRight = binarySplitDataSet(dataset,bestFeatureIndex,bestFeatureValue)
    #檢驗在所選出的最優劃分特征及其取值下，劃分的左右資料集的樣本數是否小于門檻值，若是，則不适合劃分
    if (np.shape(matLeft)[0] < thresholdSamples) or (np.shape(matRight)[0] < thresholdSamples):
        return None,leafType(dataset)
    return bestFeatureIndex,bestFeatureValue


def createCARTtree(dataset,leafType=regressLeaf,errType=regressErr,threshold=(1,4)):

    '''
    輸入：資料集dataset，葉子節點形式leafType：regressLeaf（回歸樹）、modelLeaf（模型樹）
         損失函數errType:誤差平方和也分為regressLeaf和modelLeaf、使用者自定義門檻值參數：
         誤差減少的門檻值和子樣本集應包含的最少樣本個數
    功能：建立回歸樹或模型樹
    輸出：以字典嵌套資料形式傳回子回歸樹或子模型樹或葉結點
    '''
    feature,value = chooseBestSplit(dataset,leafType,errType,threshold)
    #當不滿足門檻值或某一子資料集下輸出全相等時，傳回葉節點
    if feature == None: return value
    returnTree = {}
    returnTree['bestSplitFeature'] = feature
    returnTree['bestSplitFeatValue'] = value
    leftSet,rightSet = binarySplitDataSet(dataset,feature,value)
    returnTree['left'] = createCARTtree(leftSet,leafType,errType,threshold)
    returnTree['right'] = createCARTtree(rightSet,leafType,errType,threshold)
    return returnTree

#----------回歸樹剪枝函數----------#
def isTree(obj):#主要是為了判斷目前節點是否是葉節點
    return (type(obj).__name__ == 'dict')

def getMean(tree):#樹就是嵌套字典
    if isTree(tree['left']): tree['left'] = getMean(tree['left'])
    if isTree(tree['right']): tree['right'] = getMean(tree['right'])
    return (tree['left'] + tree['right'])/2.0

def prune(tree, testData):
    if np.shape(testData)[0] == 0: return getMean(tree)#存在測試集中沒有訓練集中資料的情況
    if isTree(tree['left']) or isTree(tree['right']):
        leftTestData, rightTestData = binarySplitDataSet(testData,tree['bestSplitFeature'],tree['bestSplitFeatValue'])
    #遞歸調用prune函數對左右子樹,注意與左右子樹對應的左右子測試資料集
    if isTree(tree['left']): tree['left'] = prune(tree['left'],leftTestData)
    if isTree(tree['right']): tree['right'] = prune(tree['right'],rightTestData)
    #當遞歸搜尋到左右子樹均為葉節點時，計算測試資料集的誤差平方和
    if not isTree(tree['left']) and not isTree(tree['right']):
        leftTestData, rightTestData = binarySplitDataSet(testData,tree['bestSplitFeature'],tree['bestSplitFeatValue'])
        errorNOmerge = sum(np.power(leftTestData[:,-1] - tree['left'],2)) +sum(np.power(rightTestData[:,-1] - tree['right'],2))
        errorMerge = sum(np.power(testData[:,1] - getMean(tree),2))
        if errorMerge < errorNOmerge:
            print 'Merging'
            return getMean(tree)
        else: return tree
    else: return tree

#---------回歸樹剪枝END-----------#    

#-----------模型樹子函數-----------#
def linearSolve(dataset):
    m,n = np.shape(dataset)
    X = np.mat(np.ones((m,n)));Y = np.mat(np.ones((m,1)))
    X[:,1:n] = dataset[:,0:(n-1)]
    Y = dataset[:,-1]
    xTx = X.T * X
    if np.linalg.det(xTx) == 0:
        raise NameError('This matrix is singular, cannot do inverse,\n\
        try increasing the second value of threshold')
        ws = xTx.I * (X.T * Y)
        return ws, X,Y

def modelLeaf(dataset):
    ws,X,Y = linearSolve(dataset)
    return ws

def modelErr(dataset):
    ws,X,Y = linearSolve(dataset)
    yHat = X * ws
    return sum(np.power(Y - yHat,2))

#------------模型樹子函數END-------#

#------------CART預測子函數------------#

def regressEvaluation(tree, inputData):
    #隻有當tree為葉節點時，才會輸出
    return float(tree)

def modelTreeEvaluation(model,inputData):
    #inoutData為采樣數為1的特征行向量
    n = np.shape(inputData)
    X = np.mat(np.ones((1,n+1)))
    X[:,1:n+1] = inputData
    return float(X * model)

def treeForeCast(tree, inputData, modelEval = regressEvaluation):
    if not isTree(tree): return modelEval(tree,inputData)
    if inputData[tree['bestSplitFeature']] <= tree['bestSplitFeatValue']:
        if isTree(tree['left']):
            return treeForeCast(tree['left'],inputData,modelEval)
        else:
            return modelEval(tree['left'],inputData)
    else:
        if isTree(tree['right']):
            return treeForeCast(tree['right'],inputData,modelEval)
        else:
            return modelEval(tree['right'],inputData)

def createForeCast(tree,testData,modelEval=regressEvaluation):
    m = len(testData)
    yHat = np.mat(np.zeros((m,1)))
    for i in range(m):
        yHat = treeForeCast(tree,testData[i],modelEval)
    return yHat

#-----------CART預測子函數 END------------#    

if __name__ == '__main__':

    trainfilename = 'e:\\python\\ml\\trainDataset.txt'
    testfilename = 'e:\\python\\ml\\testDataset.txt'

    trainDataset = regressData(trainfilename)
    testDataset = regressData(testfilename)

    cartTree = createCARTtree(trainDataset,threshold=(1,4))
    pruneTree=prune(cartTree,testDataset)
    treePlotter.createPlot(cartTree)
    y=createForeCast(cartTree,np.mat([0.3]),modelEval=regressEvaluation)

           

3、基于scikit-learn決策樹算法類庫實作CART算法

3.1 scikit-learn決策樹算法類庫概述

官方文檔

　 \quad \quad scikit-learn決策樹算法類庫内部實作是使用了調優過的CART樹算法，既可以做分類，又可以做回歸。分類決策樹的類對應的是DecisionTreeClassifier，而回歸決策樹的類對應的是DecisionTreeRegressor。兩者的參數定義幾乎完全相同，但是意義不全相同。下面就對DecisionTreeClassifier和DecisionTreeRegressor的重要參數做一個總結，重點比較兩者參數使用的不同點和調參的注意點。

中文詳情見此部落格

3.2 實戰1—分類樹

具體參數使用方法參考官方文檔

import numpy as np
import matplotlib.pyplot as plt

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier, plot_tree

# Parameters
n_classes = 3
plot_colors = "ryb"
plot_step = 0.02

# Load data
iris = load_iris()

for pairidx, pair in enumerate([[0, 1], [0, 2], [0, 3],
                                [1, 2], [1, 3], [2, 3]]):
    # We only take the two corresponding features
    X = iris.data[:, pair]
    y = iris.target

    # Train
    clf = DecisionTreeClassifier().fit(X, y)

    # Plot the decision boundary
    plt.subplot(2, 3, pairidx + 1)

    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
                         np.arange(y_min, y_max, plot_step))
    plt.tight_layout(h_pad=0.5, w_pad=0.5, pad=2.5)

    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    cs = plt.contourf(xx, yy, Z, cmap=plt.cm.RdYlBu)

    plt.xlabel(iris.feature_names[pair[0]])
    plt.ylabel(iris.feature_names[pair[1]])

    # Plot the training points
    for i, color in zip(range(n_classes), plot_colors):
        idx = np.where(y == i)
        plt.scatter(X[idx, 0], X[idx, 1], c=color, label=iris.target_names[i],
                    cmap=plt.cm.RdYlBu, edgecolor='black', s=15)

plt.suptitle("Decision surface of a decision tree using paired features")
plt.legend(loc='lower right', borderpad=0, handletextpad=0)
plt.axis("tight")

plt.figure()
clf = DecisionTreeClassifier().fit(iris.data, iris.target)
plot_tree(clf, filled=True)
plt.show()
           

3.3 實戰2—回歸樹

具體參數參考官方文檔

from sklearn.datasets import load_diabetes
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeRegressor
X, y = load_diabetes(return_X_y=True)
regressor = DecisionTreeRegressor(random_state=0)
cross_val_score(regressor, X, y, cv=10)
           

4、決策樹算法小結

首先我們看看決策樹算法的優點：

1）簡單直覺，生成的決策樹很直覺。

2）基本不需要預處理，不需要提前歸一化，處理缺失值。

3）使用決策樹預測的代價是O(log2m)。 m為樣本數。

4）既可以處理離散值也可以處理連續值。很多算法隻是專注于離散值或者連續值。

5）可以處理多元度輸出的分類問題。

6）相比于神經網絡之類的黑盒分類模型，決策樹在邏輯上可以得到很好的解釋

7）可以交叉驗證的剪枝來選擇模型，進而提高泛化能力。

8） 對于異常點的容錯能力好，健壯性高。

我們再看看決策樹算法的缺點:

1）決策樹算法非常容易過拟合，導緻泛化能力不強。可以通過設定節點最少樣本數量和限制決策樹深度來改進。

2）決策樹會因為樣本發生一點點的改動，就會導緻樹結構的劇烈改變。這個可以通過內建學習之類的方法解決。

3）尋找最優的決策樹是一個NP難的問題，我們一般是通過啟發式方法，容易陷入局部最優。可以通過內建學習之類的方法來改善。

4）有些比較複雜的關系，決策樹很難學習，比如異或。這個就沒有辦法了，一般這種關系可以換神經網絡分類方法來解決。

5）如果某些特征的樣本比例過大，生成決策樹容易偏向于這些特征。這個可以通過調節樣本權重來改善。

參考資料：

1、李航《統計學習方法》

2、https://www.cnblogs.com/pinard/p/6053344.html