一、剪枝
1. 為什么要剪枝
在決策樹(shù)生成的時(shí)候仗岸，更多考慮的是訓(xùn)練數(shù)據(jù)允耿，而不是未知數(shù)據(jù)，這會(huì)導(dǎo)致過(guò)擬合扒怖，使樹(shù)過(guò)于復(fù)雜较锡，對(duì)于未知的樣本不準(zhǔn)確。
2. 剪枝的依據(jù)——通過(guò)極小化決策樹(shù)的損失函數(shù)
定義：
設(shè)樹(shù)的葉節(jié)點(diǎn)個(gè)數(shù)為
盗痒，
是樹(shù)
的葉節(jié)點(diǎn)蚂蕴，該葉節(jié)點(diǎn)有
個(gè)樣本,
其中屬于類(lèi)的樣本點(diǎn)有
個(gè)，
是葉節(jié)點(diǎn)的經(jīng)驗(yàn)熵
是超參數(shù)
損失函數(shù)的定義為：
經(jīng)驗(yàn)熵為：
代入簡(jiǎn)化：
令：
則：
的作用：
- 控制著預(yù)測(cè)誤差和樹(shù)復(fù)雜度之間的平衡
-
大，促使選擇更為簡(jiǎn)單的樹(shù)
-
-
3. 剪枝算法
- 輸入：未剪枝的決策樹(shù)T朦蕴，超參數(shù)
- 輸出： 修剪好的樹(shù)
（1）計(jì)算每個(gè)葉節(jié)點(diǎn)的經(jīng)驗(yàn)熵篮条。
（2）遞歸的從樹(shù)的葉節(jié)點(diǎn)向上回溯弟头。 設(shè)一組葉節(jié)點(diǎn)回溯到其父節(jié)點(diǎn)之前和之后的整體樹(shù)分別為和
，若他們的損失函數(shù)：
即若修剪后的子樹(shù)的損失函數(shù)比原來(lái)更小涉茧，則進(jìn)行剪枝赴恨，將父節(jié)點(diǎn)作為新的葉節(jié)點(diǎn)。
（3）返回（2）伴栓，知道不能繼續(xù)進(jìn)行伦连，得到損失函數(shù)最小的子樹(shù)。
二钳垮、基尼指數(shù)
分類(lèi)過(guò)程中惑淳，假設(shè)有K個(gè)類(lèi)，樣本點(diǎn)屬于第k個(gè)類(lèi)的概率為Pk扔枫，則概率分布的基尼指數(shù)定義為：
對(duì)于二分類(lèi)的問(wèn)題汛聚，若k=1時(shí)，概率是p短荐，k=2時(shí)倚舀，概率是（1-p），則：
對(duì)于給定的樣本集合D忍宋，其基尼指數(shù)為：
三痕貌、CART樹(shù)
CART樹(shù)全稱(chēng)是 classification and regression tree，既可以分類(lèi)（離散數(shù)據(jù)）糠排，也可以用于回歸（連續(xù)數(shù)據(jù)）舵稠。
3.1 分類(lèi)樹(shù)
如果數(shù)據(jù)集D根據(jù)特征A在某一取值a上進(jìn)行分割，得到D1,D2兩部分后入宦，那么在特征A下集合D的基尼系數(shù)如下所示哺徊。
其中基尼系數(shù)Gini(D)表示集合D的不確定性，基尼系數(shù)Gini(D,A)表示A=a分割后集合D的不確定性乾闰÷渥罚基尼指數(shù)越大，樣本集合的不確定性越大涯肩。這一點(diǎn)與熵相似轿钠。
對(duì)于屬性A，分別計(jì)算任意屬性值將數(shù)據(jù)集劃分為兩部分之后的Gini病苗，選取其中的最小值疗垛，作為屬性A得到的最優(yōu)二分方案。然后對(duì)于訓(xùn)練集S硫朦，計(jì)算所有屬性的最優(yōu)二分方案贷腕，選取其中的最小值，作為樣本及S的最優(yōu)二分方案。
實(shí)例詳解
針對(duì)上述離散型數(shù)據(jù)花履，按照體溫為恒溫和非恒溫進(jìn)行劃分芽世。其中恒溫時(shí)包括哺乳類(lèi)5個(gè)、鳥(niǎo)類(lèi)2個(gè)诡壁，非恒溫時(shí)包括爬行類(lèi)3個(gè)、魚(yú)類(lèi)3個(gè)荠割、兩棲類(lèi)2個(gè)妹卿，如下所示我們計(jì)算D1,D2的基尼指數(shù)。然后計(jì)算得到特征體溫下數(shù)據(jù)集的Gini指數(shù)蔑鹦，最后我們選擇Gini最小的特征和相應(yīng)的劃分夺克。
3.2 回歸樹(shù)
CART回歸樹(shù)預(yù)測(cè)回歸連續(xù)型數(shù)據(jù)，假設(shè)X與Y分別是輸入和輸出變量嚎朽，并且Y是連續(xù)變量铺纽。在訓(xùn)練數(shù)據(jù)集所在的輸入空間中，遞歸的將每個(gè)區(qū)域劃分為兩個(gè)子區(qū)域并決定每個(gè)子區(qū)域上的輸出值哟忍，構(gòu)建二叉決策樹(shù)狡门。選擇最優(yōu)切分變量j與切分點(diǎn)s：遍歷變量j，對(duì)規(guī)定的切分變量j掃描切分點(diǎn)s锅很，選擇使下式得到最小值時(shí)的(j,s)對(duì)其馏。其中Rm是被劃分的輸入空間，cm是空間Rm對(duì)應(yīng)的固定輸出值爆安。
用選定的(j,s)對(duì)叛复，劃分區(qū)域并決定相應(yīng)的輸出值
繼續(xù)對(duì)兩個(gè)子區(qū)域調(diào)用上述步驟，將輸入空間劃分為M個(gè)區(qū)域R1,R2,…,Rm扔仓，生成決策樹(shù)褐奥。
當(dāng)輸入空間劃分確定時(shí)，可以用平方誤差來(lái)表示回歸樹(shù)對(duì)于訓(xùn)練數(shù)據(jù)的預(yù)測(cè)方法翘簇，用平方誤差最小的準(zhǔn)則求解每個(gè)單元上的最優(yōu)輸出值撬码。
實(shí)例詳解
考慮如上所示的連續(xù)性變量，根據(jù)給定的數(shù)據(jù)點(diǎn)缘揪，考慮1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5切分點(diǎn)耍群。對(duì)各切分點(diǎn)依次求出R1,R2,c1,c2及m(s)，例如當(dāng)切分點(diǎn)s=1.5時(shí)找筝，得到R1={1},R2={2,3,4,5,6,7,8,9,10}蹈垢，其中c1,c2,m(s)如下所示。
依次改變(j,s)對(duì)袖裕，可以得到s及m(s)的計(jì)算結(jié)果曹抬，如下表所示。
我們利用f1(x)擬合訓(xùn)練數(shù)據(jù)的殘差(將原始訓(xùn)練數(shù)據(jù)減去f1(X)）触创，如下表所示:
接下來(lái)繼續(xù)對(duì)兩個(gè)子區(qū)域重復(fù)調(diào)用上述步驟，直到平方差滿足要求為止为牍。
最后哼绑，將輸入空間分為M個(gè)子區(qū)域R1...Rm，生成決策樹(shù)：
