決策樹(shù)是一種用于分類和回歸任務(wù)的非參數(shù)監(jiān)督學(xué)習(xí)算法。它是一種分層樹(shù)形結(jié)構(gòu)，由根節(jié)點(diǎn)、分支、內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)組成。

從上圖中可以看出，決策樹(shù)從根節(jié)點(diǎn)開(kāi)始，根節(jié)點(diǎn)沒(méi)有任何傳入分支。然后，根節(jié)點(diǎn)的傳出分支為內(nèi)部節(jié)點(diǎn)（也稱為決策節(jié)點(diǎn)）提供信息。兩種節(jié)點(diǎn)都基于可用功能執(zhí)行評(píng)估以形成同類子集，這些子集由葉節(jié)點(diǎn)或終端節(jié)點(diǎn)表示。葉節(jié)點(diǎn)表示數(shù)據(jù)集內(nèi)所有可能的結(jié)果。

決策樹(shù)的類型

Hunt 算法于 20 世紀(jì) 60 年代提出，起初用于模擬心理學(xué)中的人類學(xué)習(xí)，為許多常用的決策樹(shù)算法奠定了基礎(chǔ)，例如：

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

C4.5：該算法是 ID3 的后期擴(kuò)展，同樣由 Quinlan 開(kāi)發(fā)。它可以使用信息增益或增益率來(lái)評(píng)估決策樹(shù)中的切分點(diǎn)。

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

決策樹(shù)的構(gòu)建

詳細(xì)的構(gòu)建過(guò)程可以參考：決策樹(shù)的構(gòu)建原理

案例數(shù)據(jù)集準(zhǔn)備

泰坦尼克號(hào)數(shù)據(jù)集

數(shù)據(jù)處理后的數(shù)據(jù)集

幸存者統(tǒng)計(jì)

決策樹(shù)構(gòu)建及可視化

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

## 將獲得的決策樹(shù)結(jié)構(gòu)可視化
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())

未剪枝決策樹(shù)

觀察上圖所示的模型結(jié)構(gòu)可以發(fā)現(xiàn)，該模型是非常復(fù)雜的決策樹(shù)模型，而且決策樹(shù)的層數(shù)遠(yuǎn)遠(yuǎn)超過(guò)了10層，從而使用該決策樹(shù)獲得的規(guī)則會(huì)非常的復(fù)雜。通過(guò)模型的可視化進(jìn)一步證明了獲得的決策樹(shù)模型具有嚴(yán)重的過(guò)擬合問(wèn)題，需要對(duì)模型進(jìn)行剪枝，精簡(jiǎn)模型。

模型在訓(xùn)練集上有74個(gè)錯(cuò)誤樣本，而在測(cè)試集上存在50個(gè)錯(cuò)誤樣本。

訓(xùn)練數(shù)據(jù)集混淆矩陣

測(cè)試數(shù)據(jù)集混淆矩陣

觀察圖1所示的模型結(jié)構(gòu)可以發(fā)現(xiàn)，該模型是非常復(fù)雜的決策樹(shù)模型，而且決策樹(shù)的層數(shù)遠(yuǎn)遠(yuǎn)超過(guò)了10層，從而使用該決策樹(shù)獲得的規(guī)則會(huì)非常的復(fù)雜。通過(guò)模型的可視化進(jìn)一步證明了獲得的決策樹(shù)模型具有嚴(yán)重的過(guò)擬合問(wèn)題，需要對(duì)模型進(jìn)行剪枝，精簡(jiǎn)模型。

決策樹(shù)的過(guò)擬合問(wèn)題

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

因此通常選擇小型決策樹(shù)，這與奧卡姆剃刀原理的"簡(jiǎn)單有效原理"相符，即"如無(wú)必要，勿增實(shí)體"。換句話說(shuō)，我們應(yīng)該只在必要時(shí)增加決策樹(shù)的復(fù)雜性，因?yàn)樽詈?jiǎn)單的往往是最好的。為了降低復(fù)雜性并防止過(guò)擬合，通常采用剪枝算法；這一過(guò)程會(huì)刪除不太重要的特征的分支。然后，通過(guò)交叉驗(yàn)證評(píng)估模型的擬合。另一種保持決策樹(shù)準(zhǔn)確性的方法是使用隨機(jī)森林算法形成一個(gè)集合；這種分類法可以得到更加準(zhǔn)確的預(yù)測(cè)結(jié)果，特別是在決策樹(shù)分支彼此不相關(guān)的情況下。

決策樹(shù)的剪枝

決策樹(shù)的剪枝有兩種思路：

• 預(yù)剪枝（Pre-Pruning）
• 后剪枝（Post-Pruning）

預(yù)剪枝（Pre-Pruning）

預(yù)剪枝就是在構(gòu)造決策樹(shù)的過(guò)程中，先對(duì)每個(gè)結(jié)點(diǎn)在劃分前進(jìn)行估計(jì)，如果當(dāng)前結(jié)點(diǎn)的劃分不能帶來(lái)決策樹(shù)模型泛化性能的提升，則不對(duì)當(dāng)前結(jié)點(diǎn)進(jìn)行劃分并且將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)。

所有決策樹(shù)的構(gòu)建方法，都是在無(wú)法進(jìn)一步降低熵的情況下才會(huì)停止創(chuàng)建分支的過(guò)程，為了避免過(guò)擬合，可以設(shè)定一個(gè)閾值，熵減小的數(shù)量小于這個(gè)閾值，即使還可以繼續(xù)降低熵，也停止繼續(xù)創(chuàng)建分支。但是這種方法實(shí)際中的效果并不好。

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

• max_depth：指定了決策樹(shù)的最大深度
• max_leaf_nodes：指定了模型的葉子節(jié)點(diǎn)的最大數(shù)目
• min_sample_split：指定了模型的節(jié)點(diǎn)允許分割的最小樣本數(shù)
• min_samples_leaf：指定了模型的一個(gè)葉節(jié)點(diǎn)上所需的最小樣本數(shù)

這里使用參數(shù)網(wǎng)格搜索的方式，對(duì)該模型中的四個(gè)參數(shù)進(jìn)行搜索，并通過(guò)該在驗(yàn)證集上的預(yù)測(cè)精度為準(zhǔn)測(cè)，獲取較合適的模型參數(shù)組合。

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)

## 可視化決策樹(shù)經(jīng)過(guò)剪剪枝后的樹(shù)結(jié)構(gòu)
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())

預(yù)剪枝后決策樹(shù)

從剪枝后決策樹(shù)模型中可以發(fā)現(xiàn)：該模型和未剪枝的模型相比已經(jīng)大大的簡(jiǎn)化了。模型在訓(xùn)練集上有95個(gè)錯(cuò)誤樣本，但在測(cè)試集上只存在47個(gè)錯(cuò)誤樣本。

訓(xùn)練數(shù)據(jù)集混淆矩陣

測(cè)試數(shù)據(jù)集混淆矩陣

后剪枝（Post-Pruning）

決策樹(shù)構(gòu)造完成后進(jìn)行剪枝。剪枝的過(guò)程是對(duì)擁有同樣父節(jié)點(diǎn)的一組節(jié)點(diǎn)進(jìn)行檢查，判斷如果將其合并，熵的增加量是否小于某一閾值。如果確實(shí)小，則這一組節(jié)點(diǎn)可以合并一個(gè)節(jié)點(diǎn)，其中包含了所有可能的結(jié)果。后剪枝是目前最普遍的做法。

后剪枝的剪枝過(guò)程是刪除一些子樹(shù)，然后用其葉子節(jié)點(diǎn)代替，這個(gè)葉子節(jié)點(diǎn)所標(biāo)識(shí)的類別通過(guò)大多數(shù)原則(majority class criterion)確定。所謂大多數(shù)原則，是指剪枝過(guò)程中, 將一些子樹(shù)刪除而用葉節(jié)點(diǎn)代替,這個(gè)葉節(jié)點(diǎn)所標(biāo)識(shí)的類別用這棵子樹(shù)中大多數(shù)訓(xùn)練樣本所屬的類別來(lái)標(biāo)識(shí),所標(biāo)識(shí)的類 稱為majority class ，（majority class 在很多英文文獻(xiàn)中也多次出現(xiàn)）。

后剪枝算法有很多種，這里簡(jiǎn)要總結(jié)如下：

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

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

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

Pessimistic Error Pruning (PEP，悲觀剪枝）

PEP剪枝算法是在C4.5決策樹(shù)算法中提出的， 把一顆子樹(shù)（具有多個(gè)葉子節(jié)點(diǎn)）用一個(gè)葉子節(jié)點(diǎn)來(lái)替代（我研究了很多文章貌似就是用子樹(shù)的根來(lái)代替）的話，比起REP剪枝法，它不需要一個(gè)單獨(dú)的測(cè)試數(shù)據(jù)集。

PEP算法首先確定這個(gè)葉子的經(jīng)驗(yàn)錯(cuò)誤率（empirical）為（E+0.5）/N，0.5為一個(gè)調(diào)整系數(shù)。對(duì)于一顆擁有L個(gè)葉子的子樹(shù)，則子樹(shù)的錯(cuò)誤數(shù)和實(shí)例數(shù)都是就應(yīng)該是葉子的錯(cuò)誤數(shù)和實(shí)例數(shù)求和的結(jié)果，則子樹(shù)的錯(cuò)誤率為e

然后用一個(gè)葉子節(jié)點(diǎn)替代子樹(shù)，該新葉子節(jié)點(diǎn)的類別為原來(lái)子樹(shù)節(jié)點(diǎn)的最優(yōu)葉子節(jié)點(diǎn)所決定，J為這個(gè)替代的葉子節(jié)點(diǎn)的錯(cuò)判個(gè)數(shù)，但是也要加上0.5，即KJ+0.5。最終是否應(yīng)該替換的標(biāo)準(zhǔn)為

被替換子樹(shù)的錯(cuò)誤數(shù)-標(biāo)準(zhǔn)差 > 新葉子錯(cuò)誤數(shù)

出現(xiàn)標(biāo)準(zhǔn)差，是因?yàn)樽訕?shù)的錯(cuò)誤個(gè)數(shù)是一個(gè)隨機(jī)變量，經(jīng)過(guò)驗(yàn)證可以近似看成是二項(xiàng)分布，就可以根據(jù)二項(xiàng)分布的標(biāo)準(zhǔn)差公式算出標(biāo)準(zhǔn)差，就可以確定是否應(yīng)該剪掉這個(gè)樹(shù)枝了。子樹(shù)中有N的實(shí)例，就是進(jìn)行N次試驗(yàn)，每次實(shí)驗(yàn)的錯(cuò)誤的概率為e，符合 B(N,e) 的二項(xiàng)分布，根據(jù)公式，均值為Ne，方差為Ne(1-e)，標(biāo)準(zhǔn)差為方差開(kāi)平方。

Cost-Complexity Pruning(CCP，代價(jià)復(fù)雜度剪枝)

在決策樹(shù)中，這種剪枝技術(shù)是由代價(jià)復(fù)雜性參數(shù)ccp_alpha來(lái)參數(shù)化的。ccp_alpha值越大，剪枝的節(jié)點(diǎn)數(shù)就越多。簡(jiǎn)單地說(shuō)，代價(jià)復(fù)雜性是一個(gè)閾值。只有當(dāng)模型的整體不純度改善了一個(gè)大于該閾值的值時(shí)，該模型才會(huì)將一個(gè)節(jié)點(diǎn)進(jìn)一步拆分為其子節(jié)點(diǎn)，否則將停止。

當(dāng)CCP值較低時(shí)，即使不純度減少不多，該模型也會(huì)將一個(gè)節(jié)點(diǎn)分割成子節(jié)點(diǎn)。隨著樹(shù)的深度增加，這一點(diǎn)很明顯，也就是說(shuō)，當(dāng)我們沿著決策樹(shù)往下走時(shí)，我們會(huì)發(fā)現(xiàn)分割對(duì)模型整體不純度的變化沒(méi)有太大貢獻(xiàn)。然而，更高的分割保證了類的正確分類，即準(zhǔn)確度更高。

當(dāng)CCP值較低時(shí)，會(huì)創(chuàng)建更多的節(jié)點(diǎn)。節(jié)點(diǎn)越高，樹(shù)的深度也越高。

下面的代碼(Scikit Learn)說(shuō)明了如何對(duì)alpha進(jìn)行調(diào)整，以獲得更高精度分?jǐn)?shù)的模型。

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")

從結(jié)果可知如果alpha設(shè)置為0.04得到的測(cè)試集精度最好，我們將從新訓(xùn)練模型。

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

后剪枝后決策樹(shù)

可以看到，模型深度非常淺，也能達(dá)到很好的效果。模型在訓(xùn)練集上有140個(gè)錯(cuò)誤樣本，但在測(cè)試集上只存在54個(gè)錯(cuò)誤樣本。

訓(xùn)練數(shù)據(jù)集混淆矩陣

測(cè)試數(shù)據(jù)集混淆矩陣