決策樹是一種用于分類和回歸任務的非參數監督學習算法。它是一種分層樹形結構，由根節點、分支、內部節點和葉節點組成。

從上圖中可以看出，決策樹從根節點開始，根節點沒有任何傳入分支。然后，根節點的傳出分支為內部節點（也稱為決策節點）提供信息。兩種節點都基于可用功能執行評估以形成同類子集，這些子集由葉節點或終端節點表示。葉節點表示數據集內所有可能的結果。

決策樹的類型

Hunt 算法于 20 世紀 60 年代提出，起初用于模擬心理學中的人類學習，為許多常用的決策樹算法奠定了基礎，例如：

ID3：該算法的開發歸功于 Ross Quinlan，全稱為"迭代二叉樹 3 代" ("Iterative Dichotomiser 3")。該算法利用信息熵與信息增益作為評估候選拆分的指標。

C4.5：該算法是 ID3 的后期擴展，同樣由 Quinlan 開發。它可以使用信息增益或增益率來評估決策樹中的切分點。

CART：術語 "CART" 的全稱是"分類和回歸"，提出者是 Leo Breiman。該算法通常利用"基尼不純度"來確定要拆分的理想屬性?；岵患兌群饬侩S機選擇的屬性被錯誤分類的頻率。使用該評估方法時，基尼不純度越小越理想。

決策樹的構建

詳細的構建過程可以參考：決策樹的構建原理

案例數據集準備

泰坦尼克號數據集

數據處理后的數據集

幸存者統計

決策樹構建及可視化

# 定于預測目標變量名
Target = ["Survived"]
## 定義模型的自變量名
train_x = ["Pclass", "Sex", "SibSp", "Parch",
           "Embarked", "Age_band","re"]
##將訓練集切分為訓練集和驗證集
X_train, X_val, y_train, y_val = train_test_split(
    data[train_x], data[Target],
    test_size = 0.25,random_state = 1)
## 先使用默認的參數建立一個決策樹模型
dtc1 = DecisionTreeClassifier(random_state=1)
## 使用訓練數據進行訓練
dtc1 = dtc1.fit(X_train, y_train)
## 輸出其在訓練數據和驗證數據集上的預測精度
dtc1_lab = dtc1.predict(X_train)
dtc1_pre = dtc1.predict(X_val)

## 將獲得的決策樹結構可視化
dot_data = StringIO()
export_graphviz(dtc1, out_file=dot_data,
                feature_names=X_train.columns,
                filled=True, rounded=True,special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue()) 
Image(graph.create_png())

未剪枝決策樹

觀察上圖所示的模型結構可以發現，該模型是非常復雜的決策樹模型，而且決策樹的層數遠遠超過了10層，從而使用該決策樹獲得的規則會非常的復雜。通過模型的可視化進一步證明了獲得的決策樹模型具有嚴重的過擬合問題，需要對模型進行剪枝，精簡模型。

模型在訓練集上有74個錯誤樣本，而在測試集上存在50個錯誤樣本。

訓練數據集混淆矩陣

測試數據集混淆矩陣

觀察圖1所示的模型結構可以發現，該模型是非常復雜的決策樹模型，而且決策樹的層數遠遠超過了10層，從而使用該決策樹獲得的規則會非常的復雜。通過模型的可視化進一步證明了獲得的決策樹模型具有嚴重的過擬合問題，需要對模型進行剪枝，精簡模型。

決策樹的過擬合問題

決策樹學習采用"一一擊破"的策略，執行貪心搜索 (greedy search) 來識別決策樹內的最佳分割點。然后以自上而下的回歸方式重復此拆分過程，直到所有或者大多數記錄都標記為特定的類別標簽。是否將所有數據點歸為同類子集在很大程度上取決于決策樹的復雜性。較小的決策樹更容易獲得無法分裂的葉節點，即單個類別中的數據點。然而，決策樹的體量越來越大，就會越來越難保持這種純度，并且通常會導致落在給定子樹內的數據過少。這種情況被稱為數據碎片，通常會引起數據過擬合。

因此通常選擇小型決策樹，這與奧卡姆剃刀原理的"簡單有效原理"相符，即"如無必要，勿增實體"。換句話說，我們應該只在必要時增加決策樹的復雜性，因為最簡單的往往是最好的。為了降低復雜性并防止過擬合，通常采用剪枝算法；這一過程會刪除不太重要的特征的分支。然后，通過交叉驗證評估模型的擬合。另一種保持決策樹準確性的方法是使用隨機森林算法形成一個集合；這種分類法可以得到更加準確的預測結果，特別是在決策樹分支彼此不相關的情況下。

決策樹的剪枝

決策樹的剪枝有兩種思路：

• 預剪枝（Pre-Pruning）
• 后剪枝（Post-Pruning）

預剪枝（Pre-Pruning）

預剪枝就是在構造決策樹的過程中，先對每個結點在劃分前進行估計，如果當前結點的劃分不能帶來決策樹模型泛化性能的提升，則不對當前結點進行劃分并且將當前結點標記為葉結點。

所有決策樹的構建方法，都是在無法進一步降低熵的情況下才會停止創建分支的過程，為了避免過擬合，可以設定一個閾值，熵減小的數量小于這個閾值，即使還可以繼續降低熵，也停止繼續創建分支。但是這種方法實際中的效果并不好。

決策樹模型的剪枝操作主要會用到DecisionTreeClassifier()函數中的

• max_depth：指定了決策樹的最大深度
• max_leaf_nodes：指定了模型的葉子節點的最大數目
• min_sample_split：指定了模型的節點允許分割的最小樣本數
• min_samples_leaf：指定了模型的一個葉節點上所需的最小樣本數

這里使用參數網格搜索的方式，對該模型中的四個參數進行搜索，并通過該在驗證集上的預測精度為準測，獲取較合適的模型參數組合。

params = {'max_depth': np.arange(2,12,2),
          'max_leaf_nodes': np.arange(10,30,2),
          'min_samples_split': [2,3,4],
          'min_samples_leaf': [1,2]}

clf = DecisionTreeClassifier(random_state=1)
gcv = GridSearchCV(estimator=clf,param_grid=params)
gcv.fit(X_train,y_train)

model = gcv.best_estimator_
model.fit(X_train,y_train)

## 可視化決策樹經過剪剪枝后的樹結構
dot_data = StringIO()
export_graphviz(model, out_file=dot_data,
                feature_names=X_train.columns,
                filled=True, 
                rounded=True,
                special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue()) 
Image(graph.create_png())

預剪枝后決策樹

從剪枝后決策樹模型中可以發現：該模型和未剪枝的模型相比已經大大的簡化了。模型在訓練集上有95個錯誤樣本，但在測試集上只存在47個錯誤樣本。

訓練數據集混淆矩陣

測試數據集混淆矩陣

后剪枝（Post-Pruning）

決策樹構造完成后進行剪枝。剪枝的過程是對擁有同樣父節點的一組節點進行檢查，判斷如果將其合并，熵的增加量是否小于某一閾值。如果確實小，則這一組節點可以合并一個節點，其中包含了所有可能的結果。后剪枝是目前最普遍的做法。

后剪枝的剪枝過程是刪除一些子樹，然后用其葉子節點代替，這個葉子節點所標識的類別通過大多數原則(majority class criterion)確定。所謂大多數原則，是指剪枝過程中, 將一些子樹刪除而用葉節點代替,這個葉節點所標識的類別用這棵子樹中大多數訓練樣本所屬的類別來標識,所標識的類 稱為majority class ，（majority class 在很多英文文獻中也多次出現）。

后剪枝算法有很多種，這里簡要總結如下：

• Reduced-Error Pruning(REP)
• Pesimistic-Error Pruning(PEP)
• Cost-Complexity Pruning(CCP)

Reduced-Error Pruning (REP,錯誤率降低剪枝）

這個思路很直接，完全的決策樹不是過度擬合么，我再搞一個測試數據集來糾正它。對于完全決策樹中的每一個非葉子節點的子樹，我們嘗試著把它替換成一個葉子節點，該葉子節點的類別我們用子樹所覆蓋訓練樣本中存在最多的那個類來代替，這樣就產生了一個簡化決策樹，然后比較這兩個決策樹在測試數據集中的表現，如果簡化決策樹在測試數據集中的錯誤比較少，那么該子樹就可以替換成葉子節點。該算法以bottom-up的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測試數據集的表現得以改進時，算法就可以終止。

Pessimistic Error Pruning (PEP，悲觀剪枝）

PEP剪枝算法是在C4.5決策樹算法中提出的， 把一顆子樹（具有多個葉子節點）用一個葉子節點來替代（我研究了很多文章貌似就是用子樹的根來代替）的話，比起REP剪枝法，它不需要一個單獨的測試數據集。

PEP算法首先確定這個葉子的經驗錯誤率（empirical）為（E+0.5）/N，0.5為一個調整系數。對于一顆擁有L個葉子的子樹，則子樹的錯誤數和實例數都是就應該是葉子的錯誤數和實例數求和的結果，則子樹的錯誤率為e

然后用一個葉子節點替代子樹，該新葉子節點的類別為原來子樹節點的最優葉子節點所決定，J為這個替代的葉子節點的錯判個數，但是也要加上0.5，即KJ+0.5。最終是否應該替換的標準為

被替換子樹的錯誤數-標準差 > 新葉子錯誤數

出現標準差，是因為子樹的錯誤個數是一個隨機變量，經過驗證可以近似看成是二項分布，就可以根據二項分布的標準差公式算出標準差，就可以確定是否應該剪掉這個樹枝了。子樹中有N的實例，就是進行N次試驗，每次實驗的錯誤的概率為e，符合 B(N,e) 的二項分布，根據公式，均值為Ne，方差為Ne(1-e)，標準差為方差開平方。

Cost-Complexity Pruning(CCP，代價復雜度剪枝)

在決策樹中，這種剪枝技術是由代價復雜性參數ccp_alpha來參數化的。ccp_alpha值越大，剪枝的節點數就越多。簡單地說，代價復雜性是一個閾值。只有當模型的整體不純度改善了一個大于該閾值的值時，該模型才會將一個節點進一步拆分為其子節點，否則將停止。

當CCP值較低時，即使不純度減少不多，該模型也會將一個節點分割成子節點。隨著樹的深度增加，這一點很明顯，也就是說，當我們沿著決策樹往下走時，我們會發現分割對模型整體不純度的變化沒有太大貢獻。然而，更高的分割保證了類的正確分類，即準確度更高。

當CCP值較低時，會創建更多的節點。節點越高，樹的深度也越高。

下面的代碼(Scikit Learn)說明了如何對alpha進行調整，以獲得更高精度分數的模型。

path = model_gini.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities = path.ccp_alphas, path.impurities

fig, ax = plt.subplots(figsize=(16,8))
ax.plot(ccp_alphas[:-1], impurities[:-1], marker='o', drawstyle="steps-post")

從結果可知如果alpha設置為0.04得到的測試集精度最好，我們將從新訓練模型。

clf_ccp = DecisionTreeClassifier(random_state=1,ccp_alpha=0.04)
clf_ccp.fit(X_train,y_train)

后剪枝后決策樹

可以看到，模型深度非常淺，也能達到很好的效果。模型在訓練集上有140個錯誤樣本，但在測試集上只存在54個錯誤樣本。

訓練數據集混淆矩陣

測試數據集混淆矩陣