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

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

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

剪枝是指將一顆子樹的子節點全部刪掉，根節點作爲葉子節點，以下圖爲例：

噪聲數據：指在一組數據中無法解釋的數據變動，就是一些不和其他數據相一致的數據。這些數據可能會干擾挖掘結果的質量，對於一些噪聲敏感的挖掘算法，這些數據可能會導致挖掘結果出現大的偏差。

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

二項式概率分佈：

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

二項分佈的正態逼近

　　　　如果np>=4 且nq>=4 ,二項概率分佈p(y)逼近於正態分佈。如下圖

　　

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

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，不屬於原創理論）

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

      

PEP後剪枝技術是由大師Quinlan提出的。它不需要像REP(錯誤率降低修剪)樣，需要用部分樣本作爲測試數據，而是完全使用訓練數據來生成決策樹，又用這些訓練數據來完成剪枝。 決策樹生成和剪枝都使用訓練集, 所以會產生錯分。現在我們先來介紹幾個定義。

　　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就會被裁減掉。