第6章分類預測決策樹分類原理什么是決策樹？【例】工廠準備擴大電視機生產(chǎn)。市場預測表明：產(chǎn)品銷路好的概率為0.7；銷路差的概率為0.3。三個方案：建大廠，需要投資600萬元，可使用10年；如銷路好，每年可贏利200萬元；如銷路不好，每年會虧損40萬元。建小廠，需投資280萬元；如銷路好，每年可贏利80萬元；如銷路不好，每年只贏利60萬元。先建小廠，但是如銷路好，3年后擴建，擴建需投資400萬元，可使用7年，擴建后每年會贏利190萬元。供選方案投資額(萬元)使用年限(年)盈利(萬元)銷路好P1=0.7銷路不好P2=0.3A1:建設大工廠60010200-40A2:建設小工廠280108060A3:先建小工廠，盈利好則3年后擴建4007190601719萬元2680萬元200萬元-40萬元34930萬元5930萬元6560萬元190萬元80萬元60萬元建大廠建小廠銷路好(0.7)銷路差(0.3)銷路好(0.7)擴建不擴建銷路好(0.7)銷路好(0.7)銷路差(0.3)XX719萬元X決策樹分類決策樹分類算法，是利用決策樹的原理和結(jié)構(gòu)，構(gòu)造和生成形如決策樹的分類模型，發(fā)現(xiàn)和定義數(shù)據(jù)中蘊涵的分類規(guī)則的過程。決策樹中每個內(nèi)部結(jié)點(非樹葉結(jié)點)表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個樹葉結(jié)點存放一個類標號。建立了決策樹，對于一個未給定類標號的元組，跟蹤一條有根結(jié)點到葉結(jié)點的路徑，該葉結(jié)點就存放著該元組的預測。決策樹分類的步驟：1)建立決策樹分類模型由訓練樣本數(shù)據(jù)集生成決策樹分類模型。訓練樣本數(shù)據(jù)集通常選用有一定積累的、有一定綜合程度的、用于數(shù)據(jù)分析處理的數(shù)據(jù)集。2)

測試并評估模型使用測試數(shù)據(jù)集，對決策樹模型進行測試，根據(jù)測試誤差對分類模型進行評估，并根據(jù)情況對模型通過剪枝等手段進行進行修正，以提高模型的預測準確性。是對所生成的決策樹模型進行檢驗、校正和修正的過程。3)使用決策樹模型對未知分類的樣本數(shù)據(jù)，利用決策樹進行分類判別。1.建立決策樹分類模型準備數(shù)據(jù)(b)測試數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat11yesMarried95Kno12noMarried100Kno13noSingle95Kno14yesSingle70Kno15noDivorced5Kyes16noSingle60Kno(c)未分類數(shù)據(jù)TidRefundMaritalStatusIncomeCheat1yesSingle125K?2noMarried100K?3noSingle70K?(a)訓練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyes1.建立決策樹分類模型根據(jù)訓練數(shù)據(jù)建立決策樹yesRefundno/3……no(a)訓練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no3noSingle70Kno5noDivorced95Kyes6noMarried60Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyes1.建立決策樹分類模型根據(jù)訓練數(shù)據(jù)建立決策樹yesRefundno/3no(a)訓練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no3noSingle70Kno5noDivorced95Kyes6noMarried60Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no6noMarried60Kno9noMarried75Kno3noSingle70Kno5noDivorced95Kyes8noSingle85Kyes10noSingle90KyesMarStno/3Single,Divorced………Married1.建立決策樹分類模型根據(jù)訓練數(shù)據(jù)建立決策樹yesRefundno/3no(a)訓練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no3noSingle70Kno5noDivorced95Kyes6noMarried60Kno8noSingle85Kyes9noMarried75Kno10noSingle90KyesTidRefundMaritalStatusIncomeCheat1yesSingle125Kno4yesMarried120Kno7yesDivorced220Kno2noMarried100no6noMarried60Kno9noMarried75Kno3noSingle70Kno5noDivorced95Kyes8noSingle85Kyes10noSingle90KyesMarStno/3Incomeyes/3no/1<85k≥85kSingle,DivorcedMarried1.建立決策樹分類模型按此原理，從不同屬性開始，建立不同的分類決策樹(a)訓練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat2noMarried100Kno6noMarried60Kno9noMarried75Kno4yesMarried120Kno1yesSingle125Kno7yesDivorced220Kno3noSingle70Kno8noSingle85Kyes10noSingle90Kyes5noDivorced95KyesyesMarStno/4RefundIncomeno/2no/1yes/3noSingle,DivorcedMarried<85K≥85K1.建立決策樹分類模型類似于流程圖的樹結(jié)構(gòu)每個內(nèi)部節(jié)點表示在一個屬性上的測試每個分枝代表一個測試輸出每個樹葉節(jié)點代表類或類分布yesMarStno/4RefundIncomeno/2no/1yes/3noSingle,DivorcedMarried<85K≥85K2.測試并評估模型測試(b)測試數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat11yesMarried95Kno12noMarried100Kno13noSingle95Kno14yesSingle70Kno15noDivorced95Kyes16noSingle60Kno

誤差率=1/6可以接受，模型確定yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85K3.使用決策樹模型(c)未分類數(shù)據(jù)TidRefundMaritalStatusIncomeCheat1yesSingle125K?2noMarried100K?3noSingle70K?yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85Knonono思考？yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85KyesMarStno/4RefundIncomeno/2no/1yes/3noSingle,DivorcedMarried<85K≥85K以哪個屬性開始？(a)訓練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyes思考？(a)訓練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyescategoricalcategoricalcontinuousclass不同類型的屬性，是否處理的方法不同？yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85K(a)訓練數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat1yesSingle125Kno2noMarried100Kno3noSingle70Kno4yesMarried120Kno5noDivorced95Kyes6noMarried60Kno7yesDivorced220Kno8noSingle85Kyes9noMarried75Kno10noSingle90Kyes思考？MarStSingle,divorcedMarriedIncome<60K70~75K60~70K75~85K≥220K125~200K……MarStSingleMarrieddivorced如何劃分多值屬性？Income<85K≥85K思考？yesRefundno/3MarStIncomeno/3no/1yes/3noSingle,divorcedMarried<85K≥85K(b)測試數(shù)據(jù)集TidRefundMaritalStatusIncomeCheat11yesMarried95Kno12noMarried100Kno13noSingle95Kno14yesSingle70Kno15noDivorced95Kyes16noSingle60Kno

錯誤率太大，如何解決？小結(jié)決策樹分類的基本概念決策樹分類應用的基本過程建模（訓練數(shù)據(jù)）檢驗評估（測試數(shù)據(jù)）使用（未分類數(shù)據(jù)）幾個問題開始劃分的屬性不同類型的屬性的劃分方法第6章分類預測決策樹分類模型不同屬性的劃分方法劃分方法CarTypeFamilySportsLuxuryCarType{Family,Luxury}{Sports}CarType{Sports,Luxury}{Family}CarType{Family,Sports}{Luxury}劃分數(shù)（輸出數(shù)）取決于該屬性不同屬性值的個數(shù)。

劃分數(shù)為2，這種劃分要考慮創(chuàng)建k個屬性值的二元劃分的所有2k-1-1種方法.多路劃分:二元劃分:劃分方法編號色澤根蒂敲聲紋理臍部觸感密度含糖率好瓜1青綠蜷縮濁響清晰凹陷硬滑0.4970.46是2烏黑蜷縮沉悶清晰凹陷硬滑0.5740.376是3烏黑蜷縮濁響清晰凹陷硬滑0.4340.264是4青綠蜷縮沉悶清晰凹陷硬滑0.6080.318是5青綠蜷縮濁響清晰凹陷硬滑0.3560.215是6青綠稍蜷濁響清晰稍凹軟粘0.4030.337是7烏黑稍蜷濁響稍糊稍凹軟粘0.4810.49是8烏黑蜷縮濁響清晰稍凹硬滑0.4370.511是9烏黑稍蜷沉悶稍糊平坦硬滑0.6660.091否10青綠硬挺清脆清晰平坦軟粘0.2430.067否11淺白硬挺清脆模糊平坦硬滑0.2450.057否12淺白蜷縮濁響模糊平坦軟粘0.3430.099否13青綠稍蜷濁響稍糊平坦硬滑0.6390.161否14淺白稍蜷沉悶稍糊凹陷硬滑0.6570.198否15烏黑稍蜷濁響清晰稍凹軟粘0.6360.37否16淺白硬挺濁響模糊平坦硬滑0.5930.042否17青綠蜷縮沉悶稍糊稍凹硬滑0.7190.103否劃分方法注意：二元劃分:Size{Medium,Large}{Small}Size{Small,Medium}{Large}ORSize{Small,Large}{Medium}劃分方法連續(xù)屬性多路劃分:vi≤A＜vi+1（i=1,…,k)二元劃分:(A<vi)or(A

vi)Income<50K>=50KIncome<10K>=80K{10K,25K}{25K,50K}{50K,80K}二元劃分多路劃分考慮所有的劃分點，選擇一個最佳劃分點v從哪個屬性開始：不純性20個記錄，未劃分時:10個記錄class0(C0),

10個記錄class1(C1)性別C0：6C1：4C0：4C1：6男女車型C0：1C1：3C0：8C1：0家用運動C0：1C1：7豪華客戶號C0：1C1：0C0：1C1：0v1v2C0：0C1：1v20C0：0C1：1…客戶號性別車型…Class1男豪華…C02女家用…C03男豪華…C04女運動…C05男運動…C1……………19男運動…C120女家用…C1從哪個屬性開始：不純性不純性不純性大不純性小思考：劃分后，應不純性大些較好，還是較小比較好？C0：5C1：5C0：9C1：1從哪個屬性開始：以劃分結(jié)果來衡量屬性BNodeN3NodeN4屬性Aa0a1NodeN1NodeN2劃分前:M0M1M2M3M4M12M34Gain=M0–M12

vs

Gain=M0

–M34C0N00C1N01C0N10C1N11C0N20C1N21C0N30C1N31C0N40C1N41b0b1衡量不純度熵Gini系數(shù)分類誤差

熵熵的概念最早起源于物理學，在物理學中是用來度量一個熱力學系統(tǒng)的無序程度在信息學里面，熵是對不確定性的度量。在1948年，香農(nóng)引入了信息熵將其定義為離散隨機事件出現(xiàn)的概率，信息熵是表示一個事件的不確定性的大小，不確定性越大那么該事件包含的信息熵就越大如果一個事件完全確定了，那么它所包含的信息熵就是0。-信息增益熵分類劃分n為數(shù)據(jù)類別的數(shù)目C為類別變量，取值為Ci，i=1,2,…,nCi類別出現(xiàn)的概率為

p(Ci)，i=1,2,…,n熵P(C0)=0/6=0P(C1)=6/6=1Entropy=–0

log20

–1

log21=–0–0=0P(C0)=1/6P(C1)=5/6Entropy=–(1/6)log2(1/6)

–(5/6)log2(1/6)=0.65P(C0)=2/6P(C1)=4/6Entropy=–(2/6)log2(2/6)

–(4/6)log2(4/6)=0.92C00C16C01C15C02C14P(C0)=3/6P(C1)=3/6Entropy=–(3/6)log2

(3/6)

–(3/6)log2

(3/6)=1C03C13信息增益根據(jù)熵來定義信息增益對于特征

t，系統(tǒng)具有或沒有該特征時的信息量的差值，就是這個特征給系統(tǒng)帶來的信息量，即信息增益。對于某一屬性

T，進行屬性劃分的信息增益定義為：劃分前，數(shù)據(jù)的信息熵按屬性T

劃分后的信息熵信息增益具體可寫成：

其中

v是屬性

T的某個屬性值S為全部樣本集合Sv是

S中屬性

T的值為

v的樣例集合|Sv|為

Sv中所含樣例數(shù)信息增益【例】NO.OutlookTemperatureWindyHumidityPlay1sunnyhotfalseHighno2sunnyhottrueHighno3overcasthotfalseHighyes4rainmildfalseHighyes5raincoolfalseNormalyes6raincooltrueNormalno7overcastcooltrueNormalyes8sunnymildfalseHighno9sunnycoolfalseNormalyes10rainmildfalseNormalyes11sunnymildtrueNormalyes12overcastmildtrueHighyes13overcasthotfalseNormalyes14rainmildtrueHighno屬性“Outlook”sunnyrainyovercastOutlook分裂后的信息熵：信息增益：從哪個屬性開始：信息增益【例】計算所有屬性的信息增益從哪個屬性開始劃分決策樹的分支？

信息增益率信息增益率GainRatio計算信息增益時，不同分類的樣本的數(shù)量，會影響信息熵或信息增益的計算，即存在歸納偏置的問題。采用信息增益率可減弱不同類別的樣本數(shù)量對不純性度量的影響。信息增益率GainRatio計算公式前面所定義的信息增益

信息增益率【例】NO.OutlookTemperatureWindyHumidityPlay1sunnyhotfalseHighno2sunnyhottrueHighno3overcasthotfalseHighyes4rainmildfalseHighyes5raincoolfalseNormalyes6raincooltrueNormalno7overcastcooltrueNormalyes8sunnymildfalseHighno9sunnycoolfalseNormalyes10rainmildfalseNormalyes11sunnymildtrueNormalyes12overcastmildtrueHighyes13overcasthotfalseNormalyes14rainmildtrueHighno從哪個屬性開始：信息增益率【例】

GINI系數(shù)指標GINI系數(shù)是20世紀初意大利經(jīng)濟學家基尼，根據(jù)勞倫斯曲線所定義的判斷收入分配公平程度的指標。GINI系數(shù)是一個比例數(shù)值，在0到1之間，是國際上用來綜合考察居民收入分配差異狀況的一個重要分析指標，GINI系數(shù)越接近1就表示收入分配差距越大。GINI系數(shù)指標GINI系數(shù)也是反映一組數(shù)據(jù)離散程度的指標，其功能類似于標準差。GINI系數(shù)越大，則平均指標（如平均數(shù)、中位數(shù)和眾數(shù)）對一組數(shù)據(jù)的代表性越差；反之則越好。在決策樹分類中，使用GINI系數(shù)來反映一組數(shù)據(jù)的類別(class)的雜亂程度，即度量不純度。GINI系數(shù)指標給定結(jié)點

t的Gini值計算：當類分布均衡時，Gini值達到最大值(1-1/Nc)相反當只有一個類時，Gini值達到最小值0類別的數(shù)量在結(jié)點t中，類ci發(fā)生的概率結(jié)點t中出現(xiàn)的各個類別GINI系數(shù)指標P(C0)=0/6=0P(C1)=6/6=1Gini=1–(P(C0)2+P(C1)2)=1–(0+1)=0

P(C0)=1/6P(C1)=5/6Gini=1–((1/6)2+(5/6)2)=0.278P(C0)=2/6P(C1)=4/6Gini=1–((2/6)2+(4/6)2)=0.444P(C0)=3/6P(C1)=3/6Gini=1–((3/6)2+(3/6)2)=0.5GINI系數(shù)指標不同的劃分結(jié)果，可以利用GiniSplit參數(shù)來衡量。當一個結(jié)點p

分割成k

個部分(子結(jié)點)，

劃分的質(zhì)量公式：ni=孩子結(jié)點i的記錄數(shù),n=父結(jié)點p的記錄數(shù).分類誤差ClassificationError

P(C0)=0/6=0P(C1)=6/6=1Error=1–max(0,1)=1–1=0P(C0)=1/6P(C1)=5/6Error=1–max(1/6,5/6)=1–5/6=1/6P(C0)=2/6P(C1)=4/6Error=1–max(2/6,4/6)=1–4/6=1/3C00C16C01C15C02C14分類誤差P(C0)=3/6P(C1)=3/6Error=1–max(3/6,3/6)=1–3/6=1/2C02C14連續(xù)屬性的劃分方法如何劃分？NoOutlookTemperatureHumidityWindyplay1sunny8585falseno2sunny8090trueno3overcast8386falseyes4rainy7096falseyes5rainy6880falseyes6rainy6570trueno7overcast6465trueyes8sunny7295falseno9sunny6970falseyes10rainy7580falseyes11sunny7570trueyes12overcast7290trueyes13overcast8175falseyes14rainy7191trueNo連續(xù)屬性的劃分方法多元劃分Humidityplay85no90no86yes96yes80yes70no65yes95no70yes80yes70yes90yes75yes91No連續(xù)屬性的劃分方法多元劃分

Humidity

……96≤65(6570](7075](…](9195]Humidity8590869680706595708070907591Humidity6570707075808085869090919596連續(xù)屬性的劃分方法二元劃分劃分點v選擇N個記錄中所有屬性值作為劃分點，取N-1個劃分點按照每個劃分點（A<vi

andA

vi）進行類計數(shù)，計算每個候選點vi的GiniSplit指標選擇最優(yōu)劃分點Humidity

≤A>A連續(xù)屬性的劃分方法481.數(shù)據(jù)排序，N=102.N-1=9個劃分點≤65>70≤70>75≤75>80≤80>85……≤91>95≤95>963.比較GiniSplit(≤65,>70)GiniSplit(≤70,>75)GiniSplit(≤75,>80)GiniSplit(≤80,>85)……GiniSplit(≤91,>95)GiniSplit(≤95,96)GiniSplit(≤80,>85)【例】Humidity8590869680706595708070907591Humidity6570707075808085869090919596連續(xù)屬性的劃分方法49【例】Humidity

>85≤80Humidity8590869680706595708070907591從兩個相鄰的排過序的屬性值之間選擇中間值作為劃分點

Humidity

>82.5≤82.5連續(xù)屬性的劃分方法50如果連續(xù)數(shù)值取值較為分散，則運算量較大?？刹扇∫恍┨幚矸椒▉斫档陀嬎懔俊ε判蚝蟮倪B續(xù)數(shù)值屬性所對應的決策屬性值進行分類的方法。連續(xù)屬性的劃分方法511.對屬性值由低到高進行排序；2.對分類屬性在屬性值排序的基礎上進行排序；3.將屬性值或分類值不發(fā)生變化的數(shù)值視為同一組；4.找出屬性值和分類值均發(fā)生變化的邊界點；5.按邊界點為劃分點進行劃分增益計算比較連續(xù)屬性的劃分方法52只要對較少的劃分點進行計算比較，有效地降低了計算復雜度。Humidity則從10次減少為只需6次。小結(jié)決策樹分類的過程建立模型評估（測試數(shù)據(jù)集，精確度）應用模型討論不純度-信息增益-從哪個屬性開始多差劃分、二叉劃分連續(xù)屬性劃分第6章分類預測決策樹剪枝模型評價一個好的分類模型不僅要能夠很好的擬合訓練數(shù)據(jù)，而且對未知樣本也要能準確分類。對模型的評估可以通過多項準確率指標來綜合評價：一個好的分類模型必須具有較低的訓練誤差和較低的泛化誤差。訓練誤差在訓練數(shù)據(jù)集上誤分類樣本比例檢驗誤差在測試數(shù)據(jù)集上誤分類樣本比例泛化誤差分類模型在未知樣本上的期望誤差交叉驗證【例】訓練誤差較低檢驗誤差？泛化誤差？xValueyValue【例】如果不那么“細致”？【例】哺乳動物的分類問題10個訓練記錄中有2個被錯誤標記：蝙蝠和鯨完全擬合訓練數(shù)據(jù)，訓練誤差為0【例】哺乳動物的分類問題但它在檢驗數(shù)據(jù)上的誤差達30%。人和海豚，鼴鼠誤分為非哺乳動物【例】哺乳動物的分類問題更簡單的決策樹，檢驗誤差較低10%，盡管它的訓練誤差較高20%前決策樹過度擬合了訓練數(shù)據(jù)。因為屬性測試條件4條腿具有欺騙性，它擬合了誤標記的訓練紀錄，導致了對檢驗集中記錄的誤分類過度擬合原因噪聲噪聲導致決策邊界的改變過度擬合原因噪聲缺乏代表性樣本根據(jù)少量訓練記錄做出分類決策的模型也容易受過度擬合的影響。由于訓練數(shù)據(jù)缺乏具有代表性的樣本，在沒有多少訓練記錄的情況下，學習算法仍然細化模型就會產(chǎn)生過度擬合。過度擬合原因噪聲缺乏代表性樣本【例】五個訓練記錄，所有的記錄都是正確標記的，對應的決策樹盡管訓練誤差為0，但檢驗誤差高達30%。人、大象和海豚被誤分類，因為決策樹把恒溫但不冬眠的動物分為非哺乳動物。決策樹做出這樣的分類決策是因為只有一個訓練記錄（鷹）具有這些特征。當決策樹的葉結(jié)點沒有足夠的代表性樣本時，很可能做出錯誤的預測。剪枝剪枝奧卡姆剃刀（Occam'sRazor）：“如無必要，勿增實體”，即“簡單有效原理”。在能夠保證泛化誤差的前提下，對決策樹模型進行剪枝給定兩個具有相同泛化誤差的模型，較簡單的模型比復雜的模型更可取剪枝先剪枝后剪枝先剪枝使樹增長算法在產(chǎn)生完全擬合整個訓練數(shù)據(jù)集的之前就停止決策樹的生長。當決策樹的構(gòu)建過程中，達到某一預先設定的條件，則停止樹的生長，用該結(jié)點子集元組中最頻繁的類，即主導類，作為其類別標號，該結(jié)點也設置為葉節(jié)點。先剪枝剪枝的條件主要有以下幾種限制性結(jié)束條件：

定義一個決策樹樹高上限，當決策樹達到這個上限時，就停止生長；定義一定的實例個數(shù)閾值，當結(jié)點的記錄數(shù)少于該閾值，則停止生長；當不純性度量的增益(例如信息增益informationgain)低于某個確定的閾值時，則停止生長；實例具有相同的特征向量的時候，停止決策樹的生長，即使這些屬性不屬于同一類。這種方法能夠較為有效地處理數(shù)據(jù)中的沖突問題。先剪枝方法相對簡單，具有較高的效率，而且不需要生成整個決策樹，適合于解決數(shù)據(jù)規(guī)模較大所帶來的問題。要精確地估計決策樹生長的停止時間并不容易，選取一個恰當?shù)拈撝蹈欠浅＠щy。閾值太低，無法充分解決過度擬合的問題；閾值太高，則會導致擬合不足。后剪枝減少錯誤剪枝REP(Reduced-ErrorPruning)悲觀錯誤剪枝法PEP(Pesimistic-ErrorPruning)代價-復雜度剪枝CCP(Cost-ComplexityPruning)最小錯誤剪枝MEP(MinimumErrorPruning)減少錯誤剪枝REP一種較為簡單的基于測試檢驗結(jié)果的后剪枝的方法使用測試數(shù)據(jù)集來對過度擬合訓練集中的虛假特征進行檢驗將決策樹上的每個結(jié)點都列為剪枝的候選結(jié)點，再根據(jù)算法確定是否對結(jié)點進行剪枝：【算法6?2】REP算法（給定由訓練集數(shù)據(jù)生成的決策樹T）1:repeat2:

找到最靠近葉結(jié)點的子樹Ts，使Ts變成為葉結(jié)點N，得到一棵新樹T’；3:

利用測試集測試T’，計算分類誤差；4:ifT’的分類誤差較T的分類誤差有所下降then5:T=T’//即刪除子樹Ts，用葉結(jié)點N代替6:until任意一棵子樹被葉結(jié)點替代而不增加其在測試集上的分類錯誤減少錯誤剪枝REP【例】減少錯誤剪枝REP【例】WEKA未剪枝進行了REP剪枝減少錯誤剪枝REP用測試數(shù)據(jù)集，來對剪枝前后的錯誤率進行測試和比對，以確定是否進行剪枝。悲觀錯誤剪枝法PEPPEP僅使用訓練數(shù)據(jù)，根據(jù)剪枝前后數(shù)據(jù)集錯誤率的變化來判定是否對子樹進行修剪。引入了統(tǒng)計學上連續(xù)性修正的概念彌補REP中的缺陷，在評價子樹的訓練錯誤公式中添加了一個常數(shù)，來假定每個葉結(jié)點都一定程度上對實例的某個部分進行錯誤的分類。悲觀錯誤剪枝法PEPPEP的基本原理也是試著用葉結(jié)點代替一顆子樹，如果這樣可使數(shù)據(jù)集分類誤差減低，則確定這個替換，否則則不替換。但是，這樣的替換必定會導致其訓練集分類誤差上升（測試數(shù)據(jù)集分類誤差不一定會上升），所以需要進行一定的修正，以保證這個方法有效。修正的方法就是在分類誤差上加上一個經(jīng)驗性的懲罰因子。

悲觀錯誤剪枝法PEP對于子樹，假定其有

NLeaf

個葉結(jié)點，則其經(jīng)過修正后的子樹的錯誤率為：ELeafi

為子樹中各葉結(jié)點的誤判個數(shù)NLeaf

為子樹中葉結(jié)點數(shù)Ni為子樹中各葉結(jié)點的樣本數(shù)加入懲罰因子，在一定程度上消除了因子樹換為葉結(jié)點時固有的分類誤差增長。如果剪枝，內(nèi)部結(jié)點下的子樹變成了葉節(jié)點J，其誤判個數(shù)EJ也要加上這個懲罰因子，變?yōu)镋J+0.5。A1A2c163c132c202c197正確分類的樣本數(shù)量誤判的樣本數(shù)量悲觀錯誤剪枝法PEP是否剪枝（替換）？？對于訓練數(shù)據(jù)，子樹總是比替換后的葉結(jié)點誤差小，但校正后并非如此。如果剪枝后的誤判個數(shù)在剪枝前的誤判個數(shù)的標準誤差之內(nèi)，則可剪枝A1A2c163c132c202c197悲觀錯誤剪枝法PEP錯誤率eTree

的分布，可根據(jù)經(jīng)驗估計為多種分布模型（二項式、正態(tài)分布）。

A1A2c163c132c202c197悲觀錯誤剪枝法PEP【例】圖示決策樹子樹，確定這個子樹是否應被剪枝（用一個葉結(jié)點代替）。子樹誤差率子樹誤判次數(shù)的標準差：子樹替換為葉結(jié)點后，誤判次數(shù)：因有：所以可以