? ? ? ? 決策樹是完全利用現(xiàn)有數(shù)據(jù)信息的分類擬合，為了避免過擬合褪秀、提高模型泛化能力蓄诽，需要對建立好的樹進(jìn)行剪枝。尤其是當(dāng)訓(xùn)練數(shù)據(jù)量大媒吗、特征數(shù)量較多時仑氛，所構(gòu)建的決策樹可能很龐大且復(fù)雜，剪枝可以同時達(dá)到降低復(fù)雜度闸英，解決過擬合的目的调衰。這一篇就結(jié)合sklearn來看一下決策樹的剪枝操作。
????????決策樹的剪枝操作主要分為兩種：預(yù)剪枝（Pre-Pruning）自阱，后剪枝（Post-Pruning）嚎莉。
1.0 預(yù)剪枝
? ? ? ?預(yù)剪枝是指在決策樹生成過程中，對每個節(jié)點在劃分前先進(jìn)行估計沛豌，若當(dāng)前節(jié)點的劃分不能帶來決策樹泛化性能的提升趋箩，則停止劃分并將當(dāng)前節(jié)點標(biāo)記為葉節(jié)點。
? ? ? ?所謂的“決策樹泛化性能”如何判定加派，可以使用性能評估中的留出法叫确，即預(yù)留一部分?jǐn)?shù)據(jù)用作“驗證集”以進(jìn)行性能評估。
? ? ? ?通過一個經(jīng)典的西瓜分類的例子來看：
? ? ? ? 使用ID3算法芍锦，基于信息增益對西瓜分類的過程進(jìn)行決策樹構(gòu)建竹勉，得到的決策樹如下圖所示（計算過程略）：
? ? ? ? 預(yù)剪枝是在樹構(gòu)建過程中進(jìn)行剪枝的，此例從根節(jié)點娄琉，分別計算按照色澤（0.276）次乓、根蒂（0.115）吓歇、敲聲（0.174）、紋理（0.174）票腰、臍部（0.276）城看、觸感（0）劃分時的信息增益，括號內(nèi)即為信息增益量的大小杏慰。色澤和臍部的信息增益最大测柠，從中隨機(jī)挑選一個，如臍部作為劃分特征，此時產(chǎn)生三個分支，如下圖所示：
? ? ? ?然而是否應(yīng)該進(jìn)行這次劃分，需要對劃分前后的泛化性能進(jìn)行估計，若劃分后泛華性能有提升盗尸，則劃分；否則，不劃分。
? ? ? ?上例中凹耙，臍部劃分前所有樣本{1,2,3,6,7,10,14,15,16,17}都在根節(jié)點①姿现，把該結(jié)點標(biāo)記為葉結(jié)點肠仪，其類別標(biāo)記為訓(xùn)練集中樣本數(shù)量最多的類別。此例中的所有樣本5例為好瓜备典，5例為壞瓜异旧，此時隨意選擇一類即可，如好瓜提佣。然后使用驗證集{4,5,8,9,11,12,13}評估其性能吮蛹，依據(jù)決策樹規(guī)則將所有瓜都分為好瓜，此時只有{4,5,8}被正確分類拌屏，模型準(zhǔn)確率為3/7=42.9%潮针。
? ? ? ?劃分后的的決策樹如下，再使用驗證集評估倚喂，此時被正確分類的瓜有{4,5,8,11,12}每篷，正確率為5/7=71.4%，大于劃分前的準(zhǔn)確率端圈。泛化性能得到了提升焦读，因此用“臍部”進(jìn)行劃分。
? ? ? ?劃分后的的決策樹如下舱权，再使用驗證集評估矗晃，此時被正確分類的瓜有{4,5,8,11,12}，正確率為5/7=71.4%宴倍，大于劃分前的準(zhǔn)確率张症。泛化性能得到了提升仓技，因此用“臍部”進(jìn)行劃分。
? ? ? ? 接下來吠冤，再對結(jié)點 ② 進(jìn)行劃分浑彰，信息增益值最大的那個特征是“色澤”，則使用“色澤”劃分后決策樹如下：
? ? ? ? 那么是否應(yīng)該劃分這個結(jié)點拯辙，通過驗證集計算后郭变，被正確分類的為{4,9,11,12}（正確率是遵循決策樹的規(guī)則對驗證集的預(yù)測結(jié)果），正確率為4/7=0.571<0.714涯保，因此將禁止劃分結(jié)點 ② 诉濒。
? ? ? ? 這就是預(yù)剪枝的應(yīng)用思路。
2.0 后剪枝
? ? ? ? 后剪枝是先從訓(xùn)練集生成一顆完整的決策樹夕春，然后自底向上地對非葉節(jié)點進(jìn)行考察未荒，若將該節(jié)點對應(yīng)的子樹完全替換為葉節(jié)點能帶來決策樹泛化性的提升，則將該子樹替換為葉節(jié)點及志。
? ? ? ? 依舊以西瓜分類的為例片排，使用ID3算法生成完整的決策樹，如下：
? ? ? ? 后剪枝算法從樹結(jié)構(gòu)的下方向上速侈，首先檢查結(jié)點率寡，剪枝前對于驗證集的正確劃分樣本為{4,11,12}，準(zhǔn)確率為3/7=42.9%倚搬。
????????再將以?⑥為根節(jié)點的子樹刪除冶共，將結(jié)點?⑥ 原來包含的樣本{7,15}放入其中，使用投票法把該葉結(jié)點標(biāo)記為“好瓜”（這里同樣好瓜壞瓜的標(biāo)簽數(shù)量相等每界，所以隨便取一個類別標(biāo)記）捅僵，此時驗證集的準(zhǔn)確率為57.1%>42.9%，根據(jù)后剪枝策略決定剪枝眨层。
3.0 sklearn中的決策樹和剪枝
? ? ? ? sklearn中能夠?qū)崿F(xiàn)的是預(yù)剪枝庙楚，就是設(shè)置Classifier或者Regression里的參數(shù)max_depth, min_samples_split, min_samples_leaf。后剪枝目前在sklearn中是無法實現(xiàn)的趴樱。
"""數(shù)據(jù)準(zhǔn)備馒闷，并展示分布情況"""
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
X, y = datasets.make_moons(noise=0.25, random_state=666)? ? ?
plt.scatter(X[y==0,0], X[y==0,1])? ? ? # 數(shù)據(jù)展示
plt.scatter(X[y==1,0], X[y==1,1])
plt.show()
"""決策邊界繪制函數(shù)"""
def plot_decision_boundary(model, axis): # 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)
"""決策樹模型伊佃，不設(shè)置任何參數(shù)窜司，讓sklearn自動建樹"""
from sklearn.tree import DecisionTreeClassifier
dt_clf1 = DecisionTreeClassifier()
dt_clf1.fit(X,y)
plot_decision_boundary(dt_clf1, 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()? ? ??
? ? ? ? dt_clf1的決策邊界的形狀非常不規(guī)則，這就是典型的過擬合現(xiàn)象航揉。當(dāng)模型為了遷就現(xiàn)有的數(shù)據(jù)集樣本塞祈，才會出現(xiàn)這樣的結(jié)果。
? ? ? ?增加限制條件后帅涂，再構(gòu)建一個決策樹dt_clf2這里限制了決策樹的深度（max_depth）為2议薪，也就是劃分到第二層就停止了尤蛮。
"""決策樹模型2，限制樹的深度或?qū)訑?shù)"""
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()
? ? ? ? dt_clf2的結(jié)果就明顯”和諧“了很多斯议。
????????還可以指定其他參數(shù)产捞，比如設(shè)置樣本劃分的最小值（min_samples_split），即對于一個節(jié)點來說哼御，至少包含多少個樣本數(shù)量才會對這個節(jié)點繼續(xù)拆分下去坯临。數(shù)量越大越不容易過擬合，但太大的話容易欠擬合恋昼。
"""決策樹模型3看靠，限制分割節(jié)點所含樣本數(shù)的最小量"""
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()
????????還可以設(shè)置最小樣本葉節(jié)點（min_samples_leaf），即對于一個葉子節(jié)點來說要求包含樣本的最小數(shù)量液肌，越少越容易過擬合挟炬。
"""決策樹模型4，限制葉節(jié)點所含樣本數(shù)的最小量"""
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()
????????還可以設(shè)置最大葉子結(jié)點（max_leaf_nodes）嗦哆，即對于一個葉子節(jié)點來說谤祖，最多有幾個葉子結(jié)點，葉子越多老速，樹越復(fù)雜粥喜，越容易過擬合。
"""決策樹模型5烁峭，限制葉節(jié)點數(shù)量"""
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()
4.0 sklearn.中DecisionTreeClassifier的參數(shù)介紹
class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)
? ? ? ? 1）criterion：特征選擇標(biāo)準(zhǔn)容客，可選參數(shù)秕铛，默認(rèn)是gini约郁，可以設(shè)置為entropy。gini是基尼不純度但两，entropy是熵鬓梅。ID3算法使用的是entropy，CART算法使用的則是gini谨湘。
? ? ? ? 2）splitter：特征劃分點選擇標(biāo)準(zhǔn)绽快，可選參數(shù)，默認(rèn)是best紧阔，可以設(shè)置為random坊罢。best參數(shù)是根據(jù)算法選擇最佳的切分特征，例如gini擅耽、entropy活孩。random隨機(jī)的在部分劃分點中找局部最優(yōu)的劃分點。默認(rèn)的”best”適合樣本量不大的時候乖仇，而如果樣本數(shù)據(jù)量非常大憾儒，此時決策樹構(gòu)建推薦”random”询兴。
? ? ? ? 3）max_features：劃分時考慮的最大特征數(shù)，可選參數(shù)起趾，默認(rèn)是None诗舰。尋找最佳切分時考慮的最大特征數(shù)(n_features為總共的特征數(shù))，有如下6種情況：
????????如果max_features是整型的數(shù)训裆，則考慮max_features個特征眶根；
????????如果max_features是浮點型的數(shù)，則考慮int(max_features * n_features)個特征边琉；
????????如果max_features設(shè)為auto汛闸，那么max_features = sqrt(n_features)；
????????如果max_features設(shè)為sqrt艺骂，那么max_featrues = sqrt(n_features)诸老，跟auto一樣；
????????如果max_features設(shè)為log2钳恕，那么max_features = log2(n_features)别伏；
????????如果max_features設(shè)為None，那么max_features = n_features忧额，也就是所有特征都用厘肮。一般來說，如果樣本特征數(shù)不多睦番，比如小于50类茂，我們用默認(rèn)的”None”就可以了，如果特征數(shù)非常多托嚣，就可以靈活使用剛才描述的其他取值來控制劃分時考慮的最大特征數(shù)巩检，以控制決策樹的生成時間。
? ? ? ? 4）max_depth：決策樹最大深示启，可選參數(shù)兢哭，默認(rèn)是None。這個參數(shù)表示樹的層數(shù)夫嗓，如果這個參數(shù)設(shè)置為None迟螺，那么決策樹在建立子樹的時候不會限制子樹的深度。一般來說舍咖，數(shù)據(jù)少或者特征少的時候可以默認(rèn)這個值矩父。或者如果設(shè)置了min_samples_slipt或min_samples_leaf參數(shù)時排霉，這個參數(shù)也可以默認(rèn)為None窍株，效果是相近的。如果模型樣本量多，特征也多的情況下夹姥，推薦限制這個最大深度杉武，具體的取值取決于數(shù)據(jù)的分布。常用的可以取值10-100之間辙售。
? ? ? ? 5）min_samples_split：內(nèi)部節(jié)點再劃分所需最小樣本數(shù)轻抱，可選參數(shù)，默認(rèn)是2旦部。這個值限制了子樹繼續(xù)劃分的條件祈搜。如果min_samples_split為整數(shù)，那么在切分內(nèi)部結(jié)點的時候士八，min_samples_split作為最小的樣本數(shù)容燕，也就是說，如果樣本已經(jīng)少于min_samples_split個樣本婚度，則停止繼續(xù)切分蘸秘。如果min_samples_split為浮點數(shù)，那么min_samples_split就是一個百分比蝗茁，ceil(min_samples_split * n_samples)醋虏，數(shù)是向上取整的。如果樣本量不大哮翘，可以無視這個參數(shù)颈嚼。
? ? ? ? 6）min_weight_fraction_leaf：葉子節(jié)點最小的樣本權(quán)重和，可選參數(shù)饭寺，默認(rèn)是0阻课。這個值限制了葉子節(jié)點所有樣本權(quán)重和的最小值，如果小于這個值艰匙，則會和兄弟節(jié)點一起被剪枝限煞。一般來說，如果我們有較多樣本有缺失值旬薯，或者分類樹樣本的分布類別偏差很大晰骑，就會引入樣本權(quán)重适秩，這時需要注意這個值了绊序。
? ? ? ? 7）max_leaf_nodes：最大葉子節(jié)點數(shù)，可選參數(shù)秽荞，默認(rèn)是None骤公。通過限制最大葉子節(jié)點數(shù)，可以防止過擬合扬跋。如果加了限制阶捆，算法會建立在最大葉子節(jié)點數(shù)內(nèi)最優(yōu)的決策樹。如果特征不多，可以不考慮這個值洒试，但是如果特征分成多的話倍奢，可以加以限制，具體的值可以通過交叉驗證得到垒棋。
? ? ? ? 8）class_weight：類別權(quán)重卒煞，可選參數(shù)，默認(rèn)是None叼架，也可以字典畔裕、字典列表。指定樣本各類別的的權(quán)重乖订，主要是為了防止訓(xùn)練集某些類別的樣本過多扮饶，導(dǎo)致訓(xùn)練的決策樹過于偏向這些類別。類別的權(quán)重可以通過{class_label：weight}這樣的格式給出乍构，這里可以自己指定各個樣本的權(quán)重甜无，或者用balanced，如果使用balanced哥遮，則算法會自己計算權(quán)重毫蚓，樣本量少的類別所對應(yīng)的樣本權(quán)重會高。當(dāng)然昔善，如果你的樣本類別分布沒有明顯的偏倚元潘，則可以不管這個參數(shù)，選擇默認(rèn)的None君仆。
? ? ? ? 9）random_state：可選參數(shù)翩概，默認(rèn)是None。隨機(jī)數(shù)種子返咱，如果是整數(shù)钥庇，那么random_state會作為隨機(jī)數(shù)生成器的隨機(jī)數(shù)種子。如果沒有設(shè)置咖摹，隨機(jī)出來的數(shù)與當(dāng)前系統(tǒng)時間有關(guān)评姨，每個時刻都是不同的。如果設(shè)置了隨機(jī)數(shù)種子萤晴，那么相同隨機(jī)數(shù)種子吐句，不同時刻產(chǎn)生的隨機(jī)數(shù)也是相同的。如果是RandomState instance店读，那么random_state是隨機(jī)數(shù)生成器嗦枢。如果為None，則隨機(jī)數(shù)生成器使用np.random屯断。
? ? ? ? 10）min_impurity_split：節(jié)點劃分最小不純度,可選參數(shù)文虏，默認(rèn)是1e-7侣诺。這是個閾值，這個值限制了決策樹的增長氧秘，如果某節(jié)點的不純度(基尼系數(shù)年鸳，信息增益，均方差丸相，絕對差)小于這個閾值阻星，則該節(jié)點不再生成子節(jié)點。即為葉子節(jié)點 已添。
? ? ? ? 11）presort：數(shù)據(jù)是否預(yù)排序妥箕，可選參數(shù)，默認(rèn)為False更舞，這個值是布爾值畦幢，默認(rèn)是False不排序。一般來說缆蝉，如果樣本量少或者限制了一個深度很小的決策樹宇葱，設(shè)置為true可以讓劃分點選擇更加快，決策樹建立的更加快刊头。如果樣本量太大的話黍瞧，反而沒有什么好處。問題是樣本量少的時候原杂，速度本來就不慢印颤。所以這個參數(shù)一般沒有用處。
除了這些參數(shù)要注意以外穿肄，其他在調(diào)參時的注意點有：
????????當(dāng)樣本數(shù)量少但是樣本特征非常多的時候年局，推薦先做維度規(guī)約，否則很容易過擬合咸产，方法可以采用主成分分析（PCA）矢否，特征選擇（Lasso）或者獨立成分分析（ICA）。這樣特征的維度會大大減小脑溢。再來擬合決策樹模型效果會好僵朗。
????????推薦多用決策樹的可視化，同時先限制決策樹的深度屑彻，這樣可以先觀察下生成的決策樹里數(shù)據(jù)的初步擬合情況验庙，然后再決定是否要增加深度。
? ? ? ? 注意觀察樣本的類別情況是否均勻（主要指分類樹）酱酬。如果類別分布非常不均勻壶谒，就要考慮用class_weight來限制模型過于偏向樣本多的類別。
????????決策樹的數(shù)組使用的是numpy的float32類型膳沽，如果訓(xùn)練數(shù)據(jù)不是這樣的格式，算法會先做copy再運行。
????????如果輸入的樣本矩陣是稀疏的挑社，推薦在擬合前調(diào)用csc_matrix稀疏化陨界，在預(yù)測前調(diào)用csr_matrix稀疏化。
