首先先介紹幾個基本概念：

決策樹(Decision Tree）：在已知各類狀況發生機率的基礎上，經過構成決策樹來求取淨現值的指望值大於等於零的機率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用機率分析的一種圖解法。因爲這種決策分支畫成圖形很像一棵樹的枝幹，故稱決策樹。html

擬合：所謂擬合是指已知某函數的若干離散函數值{f1,f2,…,fn}，經過調整該函數中若干待定係數f(λ1, λ2,…,λn)，使得該函數與已知點集的差異(最小二乘意義)最小。算法

剪枝是指將一顆子樹的子節點所有刪掉，根節點做爲葉子節點，如下圖爲例：函數

噪聲數據：指在一組數據中沒法解釋的數據變更，就是一些不和其餘數據相一致的數據。這些數據可能會干擾挖掘結果的質量，對於一些噪聲敏感的挖掘算法，這些數據可能會致使挖掘結果出現大的誤差。測試

置信區間：設θ'在大樣本下服從E(θ') = θ, 標準偏差爲σ'的正態分佈，那麼θ的(1 - α)100%置信區間是：　　θ' +/- (Zα/2) σ'優化

二項式機率分佈：ui

均值和方差分別是u = np, σ2=npq　,其中p=每次實驗成功的機率， q=1-p。spa

二項分佈的正態逼近htm

　　　　若是np>=4 且nq>=4 ,二項機率分佈p(y)逼近於正態分佈。以下圖blog

　　能夠看到P(Y<=2)是在正態曲線下Y=2.5的左端面積。注意到Y=2的左端面積是不合適的，由於它省略了相應於Y=2的一半機率的長方形。爲了修正，用連續機率分佈去近似離散機率分佈，在計算機率以前咱們須要將2增長0.5。值0.5稱爲二項機率分佈近似的連續性修正因子，所以ci

P(Y<=a) 約等於 P(Z<  (a+0.5 - np/ ( npq)1/2)   )；

P(Y>=a) 約等於 P(Z> (a-0.5 - np/ ( npq)1/2)   )

既然都建成了決策樹，爲何還要進行剪枝：

      決策樹是充分考慮了全部的數據點而生成的複雜樹，有可能出現過擬合的狀況，決策樹越複雜，過擬合的程度會越高。（理論來講，不該該是擬合程度越高，預測結果越準確嘛？爲何還要避免這種狀況？）

      考慮極端的狀況，若是咱們令全部的葉子節點都只含有一個數據點，那麼咱們可以保證全部的訓練數據都能準確分類，可是頗有可能獲得高的預測偏差，緣由是將訓練數據中全部的噪聲數據都」準確劃分」了，強化了噪聲數據的做用。（造成決策樹的目的做出合理的預測，儘量有效的排除噪聲數據干擾，影響正確預測的判斷）

      剪枝修剪分裂先後分類偏差相差不大的子樹，可以下降決策樹的複雜度，下降過擬合出現的機率。（換句話說就是把重負累贅的子樹用一個根節點進行替換，也就是說跟姐的數據意義徹底能夠代替又該節點衍生出的子樹的全部節點的意義）

既然決定剪枝，那麼怎麼進行剪枝呢?

兩種方案：先剪枝和後剪枝

      先剪枝說白了就是提早結束決策樹的增加，跟上述決策樹中止生長的方法同樣。

      後剪枝是指在決策樹生長完成以後再進行剪枝的過程。這裏介紹兩種後剪枝方案：

方案一：REP—錯誤消減剪枝

      錯誤消減剪枝是對「基於成本複雜度的剪枝」的一種優化，可是仍然須要一個單獨的測試數據集，不一樣的是在於這種方法能夠直接使用徹底誘導樹對測試集中的實例進行分類，對於誘導樹（什麼是誘導樹？）中的非葉子節樹，該策略是用一個葉子節點去代替該子樹，判斷是否有益，若是剪枝先後，其錯誤率降低或者是不變，而且被剪掉的子樹不包含具備相同性質的其餘子樹（爲何不能包含相同性質的其餘子樹？歡迎評論！），那麼就用這個葉子節點代替這個葉子樹，這個過程將一直持續進行，直至錯誤率出現上升的現象。

      簡單點說：該剪枝方法是根據錯誤率進行剪枝，若是一棵子樹修剪先後錯誤率沒有降低，就能夠認爲該子樹是能夠修剪的。REP剪枝須要用新的數據集，緣由是若是用舊的數據集，不可能出現分裂後的錯誤率比分裂前錯誤率要高的狀況。因爲使用新的數據集沒有參與決策樹的構建，可以下降訓練數據的影響，下降過擬合的程度，提升預測的準確率。

方案二：PEP-悲觀剪枝法（這一部分摘自http://www.cnblogs.com/junyuhuang/p/4572408.html，不屬於原創理論）

       不須要單獨的數據集進行測試，而是經過訓練數據集上的額錯誤分類數量來估算位置實力上的錯誤率。

　　T1爲決策樹T的全部內部節點(非葉子節點)，

　　T2爲決策樹T的全部葉子節點，

　　T3爲T的全部節點，有T3=T1∪T2,

　　n(t)爲t的全部樣本數,

　　ni(t)爲t中類別i的全部樣本數，

　　e(t)爲t中不屬於節點t所標識類別的樣本數

　　在剪枝時，咱們使用

　　　　r(t)=e(t)/n(t)

　　就是當節點被剪枝後在訓練集上的錯誤率，而

　　, 其中s爲t節點的葉子節點。

　　在此，咱們把錯誤分佈當作是二項式分佈，由上面「二項分佈的正態逼近」相關介紹知道，上面的式子是有誤差的，所以須要連續性修正因子來矯正數據，有

　　r‘(t)=[e(t) + 1/2]/n(t)

　　和

　　, 其中s爲t節點的葉子節點，你不認識的那個符號爲 t的全部葉子節點的數目

　　爲了簡單，咱們就只使用錯誤數目而不是錯誤率了，以下

　　e'(t) = [e(t) + 1/2]

　　接着求e'(Tt)的標準差，因爲偏差近似當作是二項式分佈，根據u = np, σ2=npq能夠獲得

　　當節點t知足

　　則Tt就會被裁減掉。