建站
咨詢
售后
建站咨詢
新聞中心
決策樹是一種用于分類和回歸任務的非參數(shù)監(jiān)督學習算法。它是一種分層樹形結構，由根節(jié)點、分支、內部節(jié)點和葉節(jié)點組成。
10年積累的成都網(wǎng)站建設、網(wǎng)站建設經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先做網(wǎng)站設計后付款的網(wǎng)站建設流程，更有定南免費網(wǎng)站建設讓你可以放心的選擇與我們合作。
從上圖中可以看出，決策樹從根節(jié)點開始，根節(jié)點沒有任何傳入分支。然后，根節(jié)點的傳出分支為內部節(jié)點（也稱為決策節(jié)點）提供信息。兩種節(jié)點都基于可用功能執(zhí)行評估以形成同類子集，這些子集由葉節(jié)點或終端節(jié)點表示。葉節(jié)點表示數(shù)據(jù)集內所有可能的結果。
決策樹的類型
Hunt 算法于 20 世紀 60 年代提出，起初用于模擬心理學中的人類學習，為許多常用的決策樹算法奠定了基礎，例如：
ID3：該算法的開發(fā)歸功于 Ross Quinlan，全稱為"迭代二叉樹 3 代" ("Iterative Dichotomiser 3")。該算法利用信息熵與信息增益作為評估候選拆分的指標。
C4.5：該算法是 ID3 的后期擴展，同樣由 Quinlan 開發(fā)。它可以使用信息增益或增益率來評估決策樹中的切分點。
CART：術語 "CART" 的全稱是"分類和回歸"，提出者是 Leo Breiman。該算法通常利用"基尼不純度"來確定要拆分的理想屬性?；岵患兌群饬侩S機選擇的屬性被錯誤分類的頻率。使用該評估方法時，基尼不純度越小越理想。
決策樹的構建
詳細的構建過程可以參考：決策樹的構建原理
案例數(shù)據(jù)集準備
泰坦尼克號數(shù)據(jù)集
數(shù)據(jù)處理后的數(shù)據(jù)集
幸存者統(tǒng)計
決策樹構建及可視化
# 定于預測目標變量名
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)
## 先使用默認的參數(shù)建立一個決策樹模型
dtc1 = DecisionTreeClassifier(random_state=1)
## 使用訓練數(shù)據(jù)進行訓練
dtc1 = dtc1.fit(X_train, y_train)
## 輸出其在訓練數(shù)據(jù)和驗證數(shù)據(jù)集上的預測精度
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())
未剪枝決策樹
觀察上圖所示的模型結構可以發(fā)現(xiàn)，該模型是非常復雜的決策樹模型，而且決策樹的層數(shù)遠遠超過了10層，從而使用該決策樹獲得的規(guī)則會非常的復雜。通過模型的可視化進一步證明了獲得的決策樹模型具有嚴重的過擬合問題，需要對模型進行剪枝，精簡模型。
模型在訓練集上有74個錯誤樣本，而在測試集上存在50個錯誤樣本。
訓練數(shù)據(jù)集混淆矩陣
測試數(shù)據(jù)集混淆矩陣
觀察圖1所示的模型結構可以發(fā)現(xiàn)，該模型是非常復雜的決策樹模型，而且決策樹的層數(shù)遠遠超過了10層，從而使用該決策樹獲得的規(guī)則會非常的復雜。通過模型的可視化進一步證明了獲得的決策樹模型具有嚴重的過擬合問題，需要對模型進行剪枝，精簡模型。
決策樹的過擬合問題
決策樹學習采用"一一擊破"的策略，執(zhí)行貪心搜索 (greedy search) 來識別決策樹內的最佳分割點。然后以自上而下的回歸方式重復此拆分過程，直到所有或者大多數(shù)記錄都標記為特定的類別標簽。是否將所有數(shù)據(jù)點歸為同類子集在很大程度上取決于決策樹的復雜性。較小的決策樹更容易獲得無法分裂的葉節(jié)點，即單個類別中的數(shù)據(jù)點。然而，決策樹的體量越來越大，就會越來越難保持這種純度，并且通常會導致落在給定子樹內的數(shù)據(jù)過少。這種情況被稱為數(shù)據(jù)碎片，通常會引起數(shù)據(jù)過擬合。
因此通常選擇小型決策樹，這與奧卡姆剃刀原理的"簡單有效原理"相符，即"如無必要，勿增實體"。換句話說，我們應該只在必要時增加決策樹的復雜性，因為最簡單的往往是最好的。為了降低復雜性并防止過擬合，通常采用剪枝算法；這一過程會刪除不太重要的特征的分支。然后，通過交叉驗證評估模型的擬合。另一種保持決策樹準確性的方法是使用隨機森林算法形成一個集合；這種分類法可以得到更加準確的預測結果，特別是在決策樹分支彼此不相關的情況下。
決策樹的剪枝
決策樹的剪枝有兩種思路：
- 預剪枝（Pre-Pruning）
- 后剪枝（Post-Pruning）
預剪枝（Pre-Pruning）
預剪枝就是在構造決策樹的過程中，先對每個結點在劃分前進行估計，如果當前結點的劃分不能帶來決策樹模型泛化性能的提升，則不對當前結點進行劃分并且將當前結點標記為葉結點。
所有決策樹的構建方法，都是在無法進一步降低熵的情況下才會停止創(chuàng)建分支的過程，為了避免過擬合，可以設定一個閾值，熵減小的數(shù)量小于這個閾值，即使還可以繼續(xù)降低熵，也停止繼續(xù)創(chuàng)建分支。但是這種方法實際中的效果并不好。
決策樹模型的剪枝操作主要會用到DecisionTreeClassifier()函數(shù)中的
- max_depth：指定了決策樹的最大深度
- max_leaf_nodes：指定了模型的葉子節(jié)點的最大數(shù)目
- min_sample_split：指定了模型的節(jié)點允許分割的最小樣本數(shù)
- min_samples_leaf：指定了模型的一個葉節(jié)點上所需的最小樣本數(shù)
這里使用參數(shù)網(wǎng)格搜索的方式，對該模型中的四個參數(shù)進行搜索，并通過該在驗證集上的預測精度為準測，獲取較合適的模型參數(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)
## 可視化決策樹經(jīng)過剪剪枝后的樹結構
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())預剪枝后決策樹
從剪枝后決策樹模型中可以發(fā)現(xiàn)：該模型和未剪枝的模型相比已經(jīng)大大的簡化了。模型在訓練集上有95個錯誤樣本，但在測試集上只存在47個錯誤樣本。
訓練數(shù)據(jù)集混淆矩陣
測試數(shù)據(jù)集混淆矩陣
后剪枝（Post-Pruning）
決策樹構造完成后進行剪枝。剪枝的過程是對擁有同樣父節(jié)點的一組節(jié)點進行檢查，判斷如果將其合并，熵的增加量是否小于某一閾值。如果確實小，則這一組節(jié)點可以合并一個節(jié)點，其中包含了所有可能的結果。后剪枝是目前最普遍的做法。
后剪枝的剪枝過程是刪除一些子樹，然后用其葉子節(jié)點代替，這個葉子節(jié)點所標識的類別通過大多數(shù)原則(majority class criterion)確定。所謂大多數(shù)原則，是指剪枝過程中, 將一些子樹刪除而用葉節(jié)點代替,這個葉節(jié)點所標識的類別用這棵子樹中大多數(shù)訓練樣本所屬的類別來標識,所標識的類 稱為majority class ，（majority class 在很多英文文獻中也多次出現(xiàn)）。
后剪枝算法有很多種，這里簡要總結如下：
- Reduced-Error Pruning(REP)
- Pesimistic-Error Pruning(PEP)
- Cost-Complexity Pruning(CCP)
Reduced-Error Pruning (REP,錯誤率降低剪枝）
這個思路很直接，完全的決策樹不是過度擬合么，我再搞一個測試數(shù)據(jù)集來糾正它。對于完全決策樹中的每一個非葉子節(jié)點的子樹，我們嘗試著把它替換成一個葉子節(jié)點，該葉子節(jié)點的類別我們用子樹所覆蓋訓練樣本中存在最多的那個類來代替，這樣就產(chǎn)生了一個簡化決策樹，然后比較這兩個決策樹在測試數(shù)據(jù)集中的表現(xiàn)，如果簡化決策樹在測試數(shù)據(jù)集中的錯誤比較少，那么該子樹就可以替換成葉子節(jié)點。該算法以bottom-up的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測試數(shù)據(jù)集的表現(xiàn)得以改進時，算法就可以終止。
Pessimistic Error Pruning (PEP，悲觀剪枝）
PEP剪枝算法是在C4.5決策樹算法中提出的， 把一顆子樹（具有多個葉子節(jié)點）用一個葉子節(jié)點來替代（我研究了很多文章貌似就是用子樹的根來代替）的話，比起REP剪枝法，它不需要一個單獨的測試數(shù)據(jù)集。
PEP算法首先確定這個葉子的經(jīng)驗錯誤率（empirical）為（E+0.5）/N，0.5為一個調整系數(shù)。對于一顆擁有L個葉子的子樹，則子樹的錯誤數(shù)和實例數(shù)都是就應該是葉子的錯誤數(shù)和實例數(shù)求和的結果，則子樹的錯誤率為e
然后用一個葉子節(jié)點替代子樹，該新葉子節(jié)點的類別為原來子樹節(jié)點的最優(yōu)葉子節(jié)點所決定，J為這個替代的葉子節(jié)點的錯判個數(shù)，但是也要加上0.5，即KJ+0.5。最終是否應該替換的標準為
被替換子樹的錯誤數(shù)-標準差 > 新葉子錯誤數(shù)
出現(xiàn)標準差，是因為子樹的錯誤個數(shù)是一個隨機變量，經(jīng)過驗證可以近似看成是二項分布，就可以根據(jù)二項分布的標準差公式算出標準差，就可以確定是否應該剪掉這個樹枝了。子樹中有N的實例，就是進行N次試驗，每次實驗的錯誤的概率為e，符合 B(N,e) 的二項分布，根據(jù)公式，均值為Ne，方差為Ne(1-e)，標準差為方差開平方。
Cost-Complexity Pruning(CCP，代價復雜度剪枝)
在決策樹中，這種剪枝技術是由代價復雜性參數(shù)ccp_alpha來參數(shù)化的。ccp_alpha值越大，剪枝的節(jié)點數(shù)就越多。簡單地說，代價復雜性是一個閾值。只有當模型的整體不純度改善了一個大于該閾值的值時，該模型才會將一個節(jié)點進一步拆分為其子節(jié)點，否則將停止。
當CCP值較低時，即使不純度減少不多，該模型也會將一個節(jié)點分割成子節(jié)點。隨著樹的深度增加，這一點很明顯，也就是說，當我們沿著決策樹往下走時，我們會發(fā)現(xiàn)分割對模型整體不純度的變化沒有太大貢獻。然而，更高的分割保證了類的正確分類，即準確度更高。
當CCP值較低時，會創(chuàng)建更多的節(jié)點。節(jié)點越高，樹的深度也越高。
下面的代碼(Scikit Learn)說明了如何對alpha進行調整，以獲得更高精度分數(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")
從結果可知如果alpha設置為0.04得到的測試集精度最好，我們將從新訓練模型。
clf_ccp = DecisionTreeClassifier(random_state=1,ccp_alpha=0.04)
clf_ccp.fit(X_train,y_train)
后剪枝后決策樹
可以看到，模型深度非常淺，也能達到很好的效果。模型在訓練集上有140個錯誤樣本，但在測試集上只存在54個錯誤樣本。
訓練數(shù)據(jù)集混淆矩陣
測試數(shù)據(jù)集混淆矩陣
網(wǎng)頁名稱：Python實現(xiàn)決策樹的預剪枝與后剪枝
分享網(wǎng)址：http://m.fisionsoft.com.cn/article/dheogop.html
