第一篇我們主要關(guān)注了根結(jié)點及內(nèi)部結(jié)點的選擇
第二篇主要關(guān)注如何處理“過擬合”現(xiàn)象
參考
大致了解機(jī)器學(xué)習(xí)——AI 算法 歸檔 - 產(chǎn)品經(jīng)理的人工智能學(xué)習(xí)庫 (easyai.tech)
醫(yī)學(xué)僧的科研日記之機(jī)器學(xué)習(xí)系列——決策樹與隨機(jī)森林（1）—— 決策樹算法數(shù)學(xué)推導(dǎo)與實例演練 (qq.com)
問題一、什么是過擬合？
個性化與泛化是一個相互矛盾概念，就像個體化診療與指南的矛盾一樣。
決策樹對訓(xùn)練數(shù)據(jù)可以得到很低的錯誤率，但是運(yùn)用到測試數(shù)據(jù)上卻得到非常高的錯誤率，這就是“過擬合現(xiàn)象”。
具體解釋如下：對于決策樹，我們希望每個葉子節(jié)點分的都是正確的答案，所以在不加限制的情況下，決策樹傾向于把每個葉子節(jié)點單純化，那如何最單純呢？極端情況下，就是每個葉子節(jié)點只有一個樣本，那這樣，這個模型在建模集的準(zhǔn)確率就非常高了。但是，這又帶來了一個問題——過擬合，這會導(dǎo)致該模型在建模集效果顯著，但是驗證集表現(xiàn)不佳。
這可能有以下幾個原因：
1、訓(xùn)練集里面有噪音數(shù)據(jù)，干擾了正常數(shù)據(jù)的分支
2、訓(xùn)練集不具有特征性
3、特征太多
使用信息增益來種樹時，為了得到最優(yōu)的決策樹，算法會不惜帶價傾向于將熵值降為最?。赡艿脑捝踔翞?），這顆樹會顯得非常的冗雜。
問題二、如何避免過擬合現(xiàn)象？
通過限制復(fù)雜度參數(shù)（complexity parameter），抓主要矛盾，來防止模型的過擬合。具體的計算過程可以參考<醫(yī)學(xué)僧的科研日記>，這里我直接引用
我們先不考慮模型的泛化能力，那么得到一棵表現(xiàn)最優(yōu)的樹可以根據(jù)所有葉結(jié)點中的預(yù)測誤差來衡量，即模型與訓(xùn)練數(shù)據(jù)的擬合程度。設(shè)樹 T 的葉結(jié)點個數(shù)為 N，n 是樹 T 的一個葉結(jié)點，該葉結(jié)點有 Nt個樣本，其中 k 類的樣本點有 Ntk 個，K=1，2，3......K, K 為樣本空間中的所屬分類數(shù)量。葉結(jié)點 t 上的熵 Ht(T) 為
圖片
這個代表了該葉節(jié)點 t 的混亂程度，極端來看，如果該葉節(jié)點 t 只有一個分類 kn 時，該節(jié)點的 Ht(T) 最終會等于0，那么可以說，Ht(T) 接代表了該葉節(jié)點對所屬路徑數(shù)據(jù)分類的徹底性。考慮到所有葉節(jié)點里面每個葉節(jié)點的樣例個數(shù)不同，所以，我們得到了決策樹損失函數(shù)的前體：
圖片
用 C(T) 來衡量模型對訓(xùn)練數(shù)據(jù)的整體測量誤差。
但是，問題來了，如果僅僅用 C(T) 來作為優(yōu)化目標(biāo)函數(shù)，如上所述，該模型就會走向過擬合的結(jié)果。因為模型會傾向?qū)⒚總€分支劃分到最細(xì)來使每一個葉節(jié)點的 Ht(T) = 0，最終使得 C(T) 最小。
為了避免過擬合，我們需要給優(yōu)化目標(biāo)函數(shù)增加一個正則懲罰項，正則項應(yīng)該包含模型的復(fù)雜度信息，對于決策樹來說，其葉節(jié)點的數(shù)量越多就越復(fù)雜，所以損失函數(shù)如下：
圖片
參數(shù) α 控制了 C(T) 和 T 兩者之間的影響程度，如果 α 越大，則傾向于形成簡單的樹，如果 α 越小，則傾向于形成較復(fù)雜的樹。注意，剪枝的目的不是為了最小化損失函數(shù)，剪枝的目的是提高模型的泛化能力。對于決策樹，如果其葉節(jié)點的數(shù)量越多，說明決策樹模型對訓(xùn)練數(shù)據(jù)的細(xì)節(jié)反應(yīng)的就越多，從而弱化了模型的泛化能力。所以，提高泛化能力需要進(jìn)行剪枝。而 α 的值衡量的是損失函數(shù)中葉節(jié)點數(shù)量的權(quán)重，α 越大，在最小化損失函數(shù)時候，需要對葉節(jié)點數(shù)量考慮更多一些，α 越小，考慮葉節(jié)點數(shù)量會更少一些。α 可以看作一個系數(shù)，不同的 α 對應(yīng)了不同的損失函數(shù)，而對于這些所有的損失函數(shù)來說，在訓(xùn)練集上進(jìn)行決策樹生成的步驟都一樣，差別只是在判斷某些節(jié)點是否進(jìn)行展開的結(jié)果不一樣罷了。
剪枝（pruning）則是決策樹算法對付過擬合的主要手段，剪枝的策略有兩種如下：
預(yù)剪枝：在構(gòu)建決策樹的過程中，提前停止
后剪枝：決策樹構(gòu)建好，才開始剪枝
一、預(yù)剪枝
定義：預(yù)剪枝就是在構(gòu)造決策樹的過程中，先對每個結(jié)點在劃分前進(jìn)行估計，如果當(dāng)前結(jié)點的劃分不能帶來決策樹模型泛化性能的提升，則不對當(dāng)前結(jié)點進(jìn)行劃分并且將當(dāng)前結(jié)點標(biāo)記為葉結(jié)點。
在 rpart 函數(shù)中，有個參數(shù)叫做 control，它可以控制 rpart 的各種細(xì)節(jié)參數(shù)，而預(yù)剪枝就是在這里設(shè)置的，比如我們可以規(guī)定 minsplit = 100，就是指每個內(nèi)部節(jié)點中所含樣本最小數(shù)最小為100；也可以設(shè)置 minbucket = 50，就是指葉節(jié)點中所含樣本最小數(shù)目為50，設(shè)置樹的深度 maxdepth = 3 就是最大不超過3，設(shè)置復(fù)雜度 cp = 0.2; 如果這些條件沒滿足，那么決策樹就是停止劃分下去，這就是預(yù)剪枝。
二、后剪枝
對于 rpart 生成的結(jié)果，使用 prune 函數(shù)對其進(jìn)行后剪枝，一般選擇最小交叉驗證誤差 xerror 對應(yīng)的復(fù)雜度參數(shù) cp 值，這種方法也叫做最小代價復(fù)雜度剪枝法。
總結(jié)
相比于預(yù)剪枝，后剪枝往往應(yīng)用更加廣泛，
后剪枝通常比預(yù)剪枝保留了更多的分支
后剪枝的欠擬合風(fēng)險很小，泛化能力往往高于預(yù)剪枝決策樹
后剪枝訓(xùn)練時間比未剪枝和預(yù)剪枝決策樹要長很多
