機(jī)器學(xué)習(xí)——決策樹(shù)

決策樹(shù)基礎(chǔ)概念

決策樹(shù)分為分類(lèi)樹(shù)和回歸樹(shù)兩種掠归，分類(lèi)樹(shù)對(duì)離散變量做決策樹(shù)，回歸樹(shù)對(duì)連續(xù)變量做決策樹(shù)悄泥。

每個(gè)內(nèi)部節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）表示一個(gè)屬性上的測(cè)試條件虏冻，每個(gè)分支代表一個(gè)測(cè)試輸出結(jié)果，每個(gè)葉節(jié)點(diǎn)代表一種類(lèi)別

決策樹(shù)分為分類(lèi)樹(shù)和回歸樹(shù)兩種弹囚，分類(lèi)樹(shù)對(duì)離散變量做決策樹(shù)厨相，回歸樹(shù)對(duì)連續(xù)變量做決策樹(shù)。

決策樹(shù)的構(gòu)造過(guò)程就是找到這些具有決定性作用的特征，根據(jù)其決定性程度來(lái)構(gòu)造一個(gè)倒立的樹(shù)--決定性作用最大的那個(gè)特征作為根節(jié)點(diǎn)蛮穿，然后遞歸找到各分支下子數(shù)據(jù)集中次大的決定性特征庶骄，直至子數(shù)據(jù)集中所有數(shù)據(jù)都屬于同一類(lèi)。

特征：

有監(jiān)督的學(xué)習(xí)
非參數(shù)學(xué)習(xí)算法
自頂向下遞歸方式構(gòu)造決策樹(shù)
在每一步選擇中都采取在當(dāng)前狀態(tài)下最好\優(yōu)的選擇

決策樹(shù)生成過(guò)程

一棵決策樹(shù)的生成過(guò)程主要分為以下3個(gè)部分:

特征選擇：特征選擇是指從訓(xùn)練數(shù)據(jù)中眾多的特征中選擇一個(gè)特征作為當(dāng)前節(jié)點(diǎn)的分裂標(biāo)準(zhǔn)践磅，如何選擇特征有著很多不同量化評(píng)估標(biāo)準(zhǔn)標(biāo)準(zhǔn)单刁，從而衍生出不同的決策樹(shù)算法。
決策樹(shù)生成：根據(jù)選擇的特征評(píng)估標(biāo)準(zhǔn)府适，從上至下遞歸地生成子節(jié)點(diǎn)羔飞，直到數(shù)據(jù)集不可分則停止決策樹(shù)停止生長(zhǎng)。樹(shù)結(jié)構(gòu)來(lái)說(shuō)檐春，遞歸結(jié)構(gòu)是最容易理解的方式逻淌。
剪枝：決策樹(shù)容易過(guò)擬合，一般來(lái)需要剪枝疟暖，縮小樹(shù)結(jié)構(gòu)規(guī)模卡儒、緩解過(guò)擬合。剪枝技術(shù)有預(yù)剪枝和后剪枝兩種誓篱。

基于信息論的三種決策樹(shù)算法

劃分?jǐn)?shù)據(jù)集的最大原則是：使無(wú)序的數(shù)據(jù)變的有序。

熵降低的速度越快越好==>樹(shù)的高度最矮

基于信息論的決策樹(shù)算法有ID3凯楔、CART和C4.5等算法窜骄，其中C4.5和CART兩種算法從ID3算法中衍生而來(lái)。

ID3算法

信息增益作為評(píng)估標(biāo)準(zhǔn)摆屯，分支節(jié)點(diǎn)選擇特征X信息增益最大的

可用于劃分標(biāo)稱(chēng)型數(shù)據(jù)集邻遏，沒(méi)有剪枝的過(guò)程，為了去除過(guò)度數(shù)據(jù)匹配的問(wèn)題虐骑，可通過(guò)裁剪合并相鄰的無(wú)法產(chǎn)生大量信息增益的葉子節(jié)點(diǎn)（例如設(shè)置信息增益閥值）准验。使用信息增益的話(huà)，其實(shí)是有一個(gè)缺點(diǎn)廷没，那就是它偏向于具有大量值的屬性--就是說(shuō)在訓(xùn)練集中糊饱，某個(gè)屬性所取的不同值的個(gè)數(shù)越多，那么越有可能拿它來(lái)作為分裂屬性

C4.5算法

C4.5是ID3的一個(gè)改進(jìn)算法颠黎，繼承了ID3算法的優(yōu)點(diǎn)另锋。

C4.5算法用信息增益率來(lái)選擇屬性，
克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足在樹(shù)構(gòu)造過(guò)程中進(jìn)行剪枝狭归；
能夠完成對(duì)連續(xù)屬性的離散化處理夭坪；能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。

CART算法（Classification And Regression Tree）

采用的是Gini指數(shù)（選Gini指數(shù)最小的特征s）作為分裂標(biāo)準(zhǔn)
同時(shí)它也是包含后剪枝操作
ID3和C4.5雖可盡可能挖掘數(shù)據(jù)信息过椎，但生成的決策樹(shù)分支較大室梅。CART可以簡(jiǎn)化決策樹(shù)的規(guī)模，提高生成決策樹(shù)的效率

決策樹(shù)優(yōu)缺點(diǎn)

決策樹(shù)適用于數(shù)值型和標(biāo)稱(chēng)型（離散型數(shù)據(jù)，變量的結(jié)果只在有限目標(biāo)集中取值）亡鼠，能夠讀取數(shù)據(jù)集合赏殃，提取一些列數(shù)據(jù)中蘊(yùn)含的規(guī)則。在分類(lèi)問(wèn)題中使用決策樹(shù)模型有很多的優(yōu)點(diǎn)拆宛，1.決策樹(shù)計(jì)算復(fù)雜度不高嗓奢、便于使用、而且高效浑厚，2.決策樹(shù)可處理具有不相關(guān)特征的數(shù)據(jù)股耽、3.可很容易地構(gòu)造出易于理解的規(guī)則，而規(guī)則通常易于解釋和理解钳幅。

決策樹(shù)模型也有一些缺點(diǎn)物蝙，比如1.處理缺失數(shù)據(jù)時(shí)的困難、2.過(guò)度擬合以及3.忽略數(shù)據(jù)集中屬性之間的相關(guān)性等敢艰。

ID3數(shù)學(xué)原理

信息熵(香農(nóng)熵)：

一種度量不確定性的方式诬乞，是用來(lái)衡量隨機(jī)變量不確定性的，熵就是信息的期望值

如果待分類(lèi)的事物可能劃分在多個(gè)分類(lèi)之中钠导，則符號(hào)xi的信息定義為 $\mathrm{I}\left(x_{i}\right)=-\log _{2} p\left(x_{i}\right)$ 震嫉，其中p(xi)是選擇該分類(lèi)的概率。

有人可能會(huì)問(wèn)牡属，信息為啥這樣定義捌倍隆？答曰：前輩得出的結(jié)論逮栅。這就跟1+1等于2一樣悴势，記住并且會(huì)用即可。上述式中的對(duì)數(shù)以2為底措伐，也可以e為底(自然對(duì)數(shù))特纤。

若隨機(jī)事件發(fā)生的結(jié)果記為X，且待分類(lèi)的事物可能劃分在N類(lèi)中侥加，分別是x1捧存，x2，……担败，xn矗蕊，每一種取到的概率分別是P1，P2氢架，……傻咖，Pn，那么X的熵就定義為：

$\mathrm{H}=-\sum_{\mathrm{i}=1}^{n} \mathrm{p}\left(x_{i}\right) \log _{2} p\left(x_{i}\right)$

反映了每一個(gè)元素在該類(lèi)別下的不純度岖研，如{1,2,3,4}跟{1,1,1,2}相比,每個(gè)元素1-4的logPi都很大,因此sum的熵就要大很多卿操。

注：有"某個(gè)類(lèi)別的結(jié)果"的熵（某個(gè)特征有多個(gè)值）警检，也有"某事件結(jié)果"的熵（該事件有多個(gè)特征）。直觀(guān)來(lái)講害淤，結(jié)果種類(lèi)越多扇雕，熵值越大。

當(dāng)熵中的概率由數(shù)據(jù)估計(jì)(特別是最大似然估計(jì))得到時(shí)窥摄，所對(duì)應(yīng)的熵稱(chēng)為經(jīng)驗(yàn)熵(empirical entropy)镶奉。什么叫由數(shù)據(jù)估計(jì)？比如有10個(gè)數(shù)據(jù)崭放，一共有兩個(gè)類(lèi)別哨苛，A類(lèi)和B類(lèi)。其中有7個(gè)數(shù)據(jù)屬于A類(lèi)币砂，則該A類(lèi)的概率即為十分之七建峭。其中有3個(gè)數(shù)據(jù)屬于B類(lèi)，則該B類(lèi)的概率即為十分之三决摧。淺顯的解釋就是亿蒸，這概率是我們根據(jù)數(shù)據(jù)數(shù)出來(lái)的。

經(jīng)驗(yàn)熵舉例：

我們定義貸款申請(qǐng)樣本數(shù)據(jù)表中的數(shù)據(jù)為訓(xùn)練數(shù)據(jù)集D掌桩，則訓(xùn)練數(shù)據(jù)集D的經(jīng)驗(yàn)熵為H(D)边锁。|D|表示其樣本容量，即樣本個(gè)數(shù)波岛。設(shè)有K個(gè)類(lèi)Ck, = 1,2,3,...,K,|Ck|為屬于類(lèi)Ck的樣本個(gè)數(shù)茅坛，因此經(jīng)驗(yàn)熵公式就可以寫(xiě)為：

$\mathrm{H}(\mathrm{D})=-\sum_{k=1}^{K} \frac{\left|c_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$ ，即 $p(C_k)=\frac{\left|C_{k}\right|}{|D|}$ 由樣本數(shù)據(jù)出來(lái)的結(jié)果盆色。

根據(jù)此公式計(jì)算經(jīng)驗(yàn)熵H(D)灰蛙，分析貸款申請(qǐng)樣本數(shù)據(jù)表中的數(shù)據(jù)祟剔。最終分類(lèi)結(jié)果只有兩類(lèi)隔躲，即放貸和不放貸。根據(jù)表中的數(shù)據(jù)統(tǒng)計(jì)可知物延，在15個(gè)數(shù)據(jù)中宣旱，9個(gè)數(shù)據(jù)的結(jié)果為放貸，6個(gè)數(shù)據(jù)的結(jié)果為不放貸叛薯。所以數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)為：

$\mathrm{H}(\mathrm{D})=-\frac{9}{15} \log _{2} \frac{9}{15}-\frac{6}{15} \log _{2} \frac{6}{15}=0.971$

經(jīng)過(guò)計(jì)算可知浑吟，數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)的值為0.971。

▲熵值越高耗溜，則數(shù)據(jù)混合的種類(lèi)越高组力，其蘊(yùn)含的含義是一個(gè)變量可能的變化越多（反而跟變量具體的取值沒(méi)有任何關(guān)系，只和值的種類(lèi)多少以及發(fā)生概率有關(guān)）

條件熵

表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性抖拴，其定義為X在給定條件下Y的條件概率分布的熵對(duì)X的數(shù)學(xué)期望:

$H(Y | X)=\sum_{i=1}^{n} p_{i} H\left(Y | X=x_{i}\right)$ ,其中 $p_{i}=P\left(X=x_{i}\right), i=1,2, \cdots, \mathrm{n}$

經(jīng)驗(yàn)條件熵舉例：

設(shè)特征A有n個(gè)不同的取值{a1,a2,···,an}燎字，根據(jù)特征A的取值將D劃分為n個(gè)子集{D1,D2腥椒，···,Dn}，|Di|為Di的樣本個(gè)數(shù)候衍。記子集Di中屬于Ck的樣本的集合為Dik笼蛛，即Dik = Di ∩ Ck，|Dik|為Dik的樣本個(gè)數(shù)

$\begin{align*}\mathrm{H}(\mathrm{D} | \mathrm{A}) & =\sum_{i=1}^{\mathrm{n}} \frac{\left|D_{i}\right|}{|D|} \mathrm{H}\left(D_{i}\right) \\ & =-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}\end{align*}$

信息增益

信息增益(information gain)表示得知特征X的信息后蛉鹿，而使得Y的不確定性減少的程度滨砍。定義為集合D的經(jīng)驗(yàn)熵H(D)與給定特征A條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差:

$g(D, A)=H(D)-H(D| A)$

一般地，熵H(D)與條件熵H(D|A)之差稱(chēng)為互信息(mutual information)妖异。決策樹(shù)學(xué)習(xí)中的信息增益等價(jià)于訓(xùn)練數(shù)據(jù)集中類(lèi)與特征的互信息惋戏。

舉例：以貸款申請(qǐng)樣本數(shù)據(jù)表為例進(jìn)行說(shuō)明∷婀耄看下年齡這一列的數(shù)據(jù)日川，也就是特征A1，一共有三個(gè)類(lèi)別矩乐，分別是：青年龄句、中年和老年。我們只看年齡是青年的數(shù)據(jù)散罕，年齡是青年的數(shù)據(jù)一共有5個(gè)分歇，所以年齡是青年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率是5\15，也就是1\3欧漱。同理职抡，年齡是中年和老年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率也都是1\3。現(xiàn)在我們只看年齡是青年的數(shù)據(jù)的最終得到貸款的概率為2\5误甚，因?yàn)樵谖鍌€(gè)數(shù)據(jù)中缚甩，只有兩個(gè)數(shù)據(jù)顯示拿到了最終的貸款，同理窑邦，年齡是中年和老年的數(shù)據(jù)最終得到貸款的概率分別為3\5擅威、4\5。所以計(jì)算年齡的信息增益冈钦，過(guò)程如下：

$\begin{aligned} \mathrm{g}\left(\mathrm{D}, A_{1}\right) &=H(D)-H\left(D | A_{1}\right) \\ &=H(D)-\sum_{i=1}^{\mathrm{n}} \frac{\left|D_{i}\right|}{|D|} \mathrm{H}\left(D_{i}\right) \\ &=H(D)-\left[\frac{\left|D_{1}\right|}{|D|}H\left(\mathrm{D}_{1}\right)+\frac{\left|D_{2}\right|}{|D|} H\left(D_{2}\right)+\frac{\left|D_{3}\right|}{|D|} H\left(D_{3}\right)\right] \\ &=H(D)- \frac{\left|D_{i}\right|}{|D|} \sum_{i=1}^{3} p_{i} * \log _{2} p_{i} \\ &=0.971-\left[\frac{5}{15}\left(-\frac{2}{5} \log _{2} \frac{2}{5}-\frac{3}{5} \log _{2} \frac{3}{5}\right)+\frac{5}{15}\left(-\frac{3}{5} \log _{2} \frac{3}{5}-\frac{2}{5} \log _{2} \frac{2}{5}\right)\right.\\ &\left.+\frac{5}{15}\left(-\frac{4}{5} \log _{2} \frac{4}{5}-\frac{1}{5} \log _{2} \frac{1}{5}\right)\right] \\ &=0.971-0.888=0.083 \end{aligned}$

其中|Di|為特征該類(lèi)別的數(shù)量郊丛，Pi為該類(lèi)別下為true（事件發(fā)生）的概率

C4.5數(shù)學(xué)原理

以信息增益進(jìn)行分類(lèi)決策時(shí)，存在偏向于取值較多的特征的問(wèn)題瞧筛。于是有了基于信息增益比的分類(lèi)決策方法C4.5厉熟。C4.5與ID3都是利用貪心算法進(jìn)行求解，不同的是分類(lèi)決策的依據(jù)不同较幌。

信息增益比率度量:信息增益比率度量Gain(D揍瑟，X) \ 分裂信息度量SplitInformation(D，X)

$SplitInformation(D乍炉，X） = -\sum_{i=1}^{n}{P_{x_i} }*log_2{P_{x_i} }$

$GainRatio(D,X) = Gain(D,X) \div SplitInformation(D,X)$

CART數(shù)學(xué)原理

基尼指數(shù)GINI

1绢片、是一種不等性度量嘁字，表示一個(gè)隨機(jī)選中的樣本在子集中被分錯(cuò)的可能性；
2杉畜、通常用來(lái)度量收入不平衡纪蜒，可以用來(lái)度量任何不均勻分布；
3此叠、是介于0~1之間的數(shù)纯续，0-完全相等，1-完全不相等灭袁；
4猬错、總體內(nèi)包含的類(lèi)別越雜亂，GINI指數(shù)就越大（跟熵的概念很相似）

Gini系數(shù)的計(jì)算方式如下 $Gini(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}$

上面式子表述的意思就是茸歧，加入特征X以后倦炒，數(shù)據(jù)不純度減小的程度.

如果D為樣本數(shù)據(jù)集， $Gini(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}$ 其中Ck是D中屬于第k類(lèi)的樣本子集软瞎，K是類(lèi)的個(gè)數(shù)逢唤。

如果D被特征A劃分為D1、D2兩部分涤浇，這個(gè)時(shí)候就是統(tǒng)計(jì)均值鳖藕，樣本數(shù)據(jù)集D的基尼系數(shù)：

$Gini(D, A)=\frac{\left|D_{1}\right|}{|D|} Gini\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} Gini\left(D_{2}\right)$

統(tǒng)計(jì)學(xué)習(xí)方法：CART算法

最小二乘回歸樹(shù)

一個(gè)回歸樹(shù)對(duì)應(yīng)著輸入空間（即特征空間）的一個(gè)劃分以及在劃分的單元上的輸出值。假設(shè)已將輸入空間劃分為M個(gè)單元R1,R2,...Rm只锭，并且在每個(gè)單元Rm上有一個(gè)固定的輸出值Cm著恩，于是回歸樹(shù)模型可表示為：

$f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right)$

模型輸出值與實(shí)際值的誤差： $\sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right)^{2}$

我們希望每個(gè)單元上的Cm，可以是的這個(gè)平方誤差最小化蜻展。易知喉誊，當(dāng)Cm為相應(yīng)單元的所有實(shí)際值的均值時(shí)，可以到最優(yōu)：

$\hat{c}_{m}=ave\left(y_{i} | x_{i} \in R_{m}\right)$

假設(shè)纵顾，我們選擇變量 xj 為切分變量伍茄，它的取值 s 為切分點(diǎn)，那么就會(huì)得到兩個(gè)區(qū)域：

$\mathrm{R}_{1}(j, s)=\left\{x | x^{(j)} \leq s\right\}, \mathrm{R}_{2}(j, s)=\left\{x | x^{(j)}>s\right\}$

當(dāng)j和s固定時(shí)片挂，我們要找到兩個(gè)區(qū)域的代表值c1幻林，c2使各自區(qū)間上的平方差最姓甓ⅰ：

$\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]$

前面已經(jīng)知道c1音念，c2為區(qū)間上的平均：

$\hat{c}_{1}=ave\left(y_{i} | x_{i} \epsilon R_{1}(j, s)\right), \hat{c}_{2}=ave\left(y_{i} | x_{i} \epsilon R_{1}(j, s)\right)$

那么對(duì)固定的 j 只需要找到最優(yōu)的s，然后通過(guò)遍歷所有的變量躏敢，我們可以找到最優(yōu)的j闷愤，這樣我們就可以得到最優(yōu)對(duì)（j，s）,（特征j件余，特征分類(lèi)值s）讥脐，并s得到兩個(gè)區(qū)間遭居。

這樣的回歸樹(shù)通常稱(chēng)為最小二乘回歸樹(shù)（least squares regression tree）。

上述過(guò)程表示的算法步驟為:

[圖片上傳失敗...(image-16b3b4-1570443243559)]

處理連續(xù)數(shù)值型特征

C4.5和CART既可以處理離散型屬性旬渠，也可以處理連續(xù)性屬性俱萍。對(duì)于離散型描述屬性，處理方法與ID3相同告丢。對(duì)于連續(xù)分布的特征枪蘑，其處理方法是：

以C4.5為例子，在C4.5中岖免，對(duì)連續(xù)屬性的處理如下：

1岳颇、對(duì)特征的取值進(jìn)行升序排序

2、兩個(gè)特征取值之間的中點(diǎn)作為可能的分裂點(diǎn)颅湘，從分裂點(diǎn)將數(shù)據(jù)集分成兩部分话侧，計(jì)算每個(gè)可能的分裂點(diǎn)的信息增益（InforGain）。優(yōu)化算法就是只計(jì)算分類(lèi)屬性發(fā)生改變的那些特征取值闯参。

3瞻鹏、選擇修正后信息增益(InforGain)最大的分裂點(diǎn)作為該特征的最佳分裂點(diǎn)

4、計(jì)算最佳分裂點(diǎn)的信息增益率（Gain Ratio）作為特征的Gain Ratio鹿寨。注意乙漓，此處需對(duì)最佳分裂點(diǎn)的信息增益進(jìn)行修正：減去log2(N-1)|D|（N是連續(xù)特征的取值個(gè)數(shù)，D是訓(xùn)練數(shù)據(jù)數(shù)目释移，此修正的原因在于：當(dāng)離散屬性和連續(xù)屬性并存時(shí)叭披，C4.5算法傾向于選擇連續(xù)特征做最佳樹(shù)分裂點(diǎn)）

Q：為什么這邊是使用的信息增益率？

A：經(jīng)證明，在決定連續(xù)特征的分界點(diǎn)時(shí)采用增益這個(gè)指標(biāo)（因?yàn)槿舨捎迷鲆媛剩瑂plittedinfo影響分裂點(diǎn)信息度量準(zhǔn)確性决乎，若某分界點(diǎn)恰好將連續(xù)特征分成數(shù)目相等的兩部分時(shí)其抑制作用最大）肌稻，而選擇屬性的時(shí)候才使用增益率這個(gè)指標(biāo)能選擇出最佳分類(lèi)特征。

剪枝

預(yù)剪枝(Pre-pruning)

在構(gòu)建決策樹(shù)的過(guò)程時(shí)咙俩，提前停止。

根據(jù)一些原則及早的停止樹(shù)增長(zhǎng)，如樹(shù)的深度達(dá)到用戶(hù)所要的深度误窖、節(jié)點(diǎn)中樣本個(gè)數(shù)少于用戶(hù)指定個(gè)數(shù)、不純度指標(biāo)下降的最大幅度小于用戶(hù)指定的幅度等
采用檢驗(yàn)技術(shù)對(duì)當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的樣本集合進(jìn)行檢驗(yàn)秩贰，如果該樣本集合的樣本數(shù)量已小于事先指定的最小允許值霹俺，那么停止該結(jié)點(diǎn)的繼續(xù)生長(zhǎng)，并將該結(jié)點(diǎn)變?yōu)槿~子結(jié)點(diǎn)毒费，否則可以繼續(xù)擴(kuò)展該結(jié)點(diǎn)丙唧。
▲核心問(wèn)題是如何事先指定樹(shù)的最大深度，如果設(shè)置的最大深度不恰當(dāng)觅玻，那么將會(huì)導(dǎo)致過(guò)于限制樹(shù)的生長(zhǎng)想际，使決策樹(shù)的表達(dá)式規(guī)則趨于一般培漏，不能更好地對(duì)新數(shù)據(jù)集進(jìn)行分類(lèi)和預(yù)測(cè)

后剪枝(Post-pruning)

決策樹(shù)構(gòu)建好后，然后才開(kāi)始裁剪胡本。

代價(jià)復(fù)雜性剪枝牌柄、最小誤差剪枝、悲觀(guān)誤差剪枝等等
是一個(gè)邊修剪邊檢驗(yàn)的過(guò)程侧甫。
- 在決策樹(shù)的不斷剪枝操作過(guò)程中友鼻，將原樣本集合或新數(shù)據(jù)集合作為測(cè)試數(shù)據(jù)，檢驗(yàn)決策樹(shù)對(duì)測(cè)試數(shù)據(jù)的預(yù)測(cè)精度闺骚，并計(jì)算出相應(yīng)的錯(cuò)誤率彩扔，如果剪掉某個(gè)子樹(shù)后的決策樹(shù)對(duì)測(cè)試數(shù)據(jù)的預(yù)測(cè)精度或其他測(cè)度不降低，那么剪掉該子樹(shù)僻爽。
- ▲關(guān)鍵就是用獨(dú)立的驗(yàn)證數(shù)據(jù)集對(duì)訓(xùn)練集生長(zhǎng)的樹(shù)進(jìn)行剪枝

CART剪枝

先來(lái)看看剪枝用到的準(zhǔn)則函數(shù)： $C_{\alpha}(T)=C(T)+\alpha|T_{leaf}|$

C（T）是葉節(jié)點(diǎn)特性的度量虫碉，C4.3里它是熵的均值，CART決策樹(shù)里它是基尼系數(shù)的概率均值胸梆，原理類(lèi)似敦捧。多一個(gè)正則項(xiàng)，就是稀疏性約束碰镜。 $T_{leaf}$ 為葉子節(jié)點(diǎn)個(gè)數(shù)兢卵，越多，損失越大

ID3绪颖、C4.5算法中的剪枝原理是給定α秽荤，事實(shí)上很難一次給出理想的α。CART剪枝不再給定一個(gè)α柠横，然后選擇最優(yōu)決策樹(shù)窃款，而是通過(guò)設(shè)定不同的α，通過(guò)交叉驗(yàn)證選擇最優(yōu)CART樹(shù)牍氛，也就是：

訓(xùn)練集：得到不同的子樹(shù);

測(cè)試集：交叉驗(yàn)證選擇最優(yōu)樹(shù).

從有限個(gè)子樹(shù) $\left\{T_{0}, T_{1}, \ldots, T_{n}\right\}$ 中計(jì)算最優(yōu)子樹(shù)晨继，最優(yōu)子樹(shù)由驗(yàn)證集得出的測(cè)試誤差決定，哪個(gè)最小就是哪個(gè)搬俊。

這里就引出了一個(gè)問(wèn)題紊扬，每次剪哪一個(gè)節(jié)點(diǎn)呢？如何讓 $T_{leaf}$ 到達(dá)一個(gè)合適的點(diǎn)呢唉擂？先看分析剪枝的兩個(gè)極端情況：

1）完全沒(méi)剪：

$C_{\alpha}\left(T_{t}\right)=C\left(T_{t}\right)+\alpha\left|T_{t}\right|$

2）只剩根節(jié)點(diǎn)：

$C_{\alpha}(t)=C(t)+\alpha$

在α較小或者為0時(shí)餐屎，有：

$C_{\alpha}\left(T_{t}\right)<C_{\alpha}(t)$

在α取+∞大時(shí)，有：

$C_{\alpha}\left(T_{t}\right)>C_{\alpha}(t)$

α是連續(xù)變量楔敌，因此總有臨界點(diǎn)：

$C_{\alpha}\left(T_{t}\right)=C_{\alpha}(t)$

為了不混淆變量啤挎，重新定義：

$g(t)=\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1}$

α大于g(t)就是該剪驻谆。簡(jiǎn)而言之：

對(duì)于同一棵樹(shù)的結(jié)點(diǎn)卵凑，α都是一樣的庆聘，當(dāng)α從0開(kāi)始緩慢增大（或者從+∞慢慢減小）勺卢，總會(huì)有某棵子樹(shù)該剪伙判，其他子樹(shù)不該剪的情況，即α超過(guò)了某個(gè)結(jié)點(diǎn)的g(t)黑忱，但還沒(méi)有超過(guò)其他結(jié)點(diǎn)的g(t)宴抚。這樣隨著alpha不斷增大，不斷地剪枝甫煞，就得到了n+1棵子樹(shù)菇曲，接下來(lái)只要用獨(dú)立數(shù)據(jù)集測(cè)試這n+1棵子樹(shù)，試試哪棵子樹(shù)的誤差最小就知道那棵是最好的方案了抚吠。

CART剪枝的算法過(guò)程

CART剪枝.png

代碼編寫(xiě)注意點(diǎn)

遞歸的結(jié)束條件：

一.到達(dá)葉節(jié)點(diǎn)

1.當(dāng)某集合的值全是同一類(lèi)時(shí)常潮，那么該子集直接可作為葉子節(jié)點(diǎn)，為一個(gè)類(lèi)別楷力，此時(shí)不再下探喊式。

2.在決策樹(shù)構(gòu)造過(guò)程中可能會(huì)出現(xiàn)這種情況：所有特征都作為分裂特征用光了，但子集還不是純凈集（集合內(nèi)的元素不屬于同一類(lèi)別）萧朝。在這種情況下岔留，由于沒(méi)有更多信息可以使用了，一般對(duì)這些子集進(jìn)行“多數(shù)表決”检柬，即使用此子集中出現(xiàn)次數(shù)最多的類(lèi)別作為此節(jié)點(diǎn)類(lèi)別献联，然后將此節(jié)點(diǎn)作為葉子節(jié)點(diǎn)，此時(shí)不再下探

二.預(yù)剪枝條件

1.樹(shù)的深度達(dá)到用戶(hù)所要的深度

2.節(jié)點(diǎn)中樣本個(gè)數(shù)少于用戶(hù)指定個(gè)數(shù)

附錄

image

借鑒：

機(jī)器學(xué)習(xí)實(shí)戰(zhàn)教程（三）：決策樹(shù)實(shí)戰(zhàn)篇之為自己配個(gè)隱形眼鏡
決策樹(shù)算法原理及實(shí)現(xiàn)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末何址，一起剝皮案震驚了整個(gè)濱河市酱固，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌头朱，老刑警劉巖运悲，帶你破解...
沈念sama閱讀 216,692評(píng)論 6贊 501
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異项钮，居然都是意外死亡班眯，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,482評(píng)論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)烁巫，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)署隘，“玉大人，你說(shuō)我怎么就攤上這事亚隙〈挪停” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 162,995評(píng)論 0贊 353
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵，是天一觀(guān)的道長(zhǎng)诊霹。經(jīng)常有香客問(wèn)我羞延，道長(zhǎng)，這世上最難降的妖魔是什么脾还？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,223評(píng)論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任伴箩，我火速辦了婚禮，結(jié)果婚禮上鄙漏，老公的妹妹穿的比我還像新娘嗤谚。我一直安慰自己，他們只是感情好怔蚌，可當(dāng)我...
茶點(diǎn)故事閱讀 67,245評(píng)論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布巩步。她就那樣靜靜地躺著，像睡著了一般桦踊。火紅的嫁衣襯著肌膚如雪渗钉。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 51,208評(píng)論 1贊 299
城市分裂傳說(shuō)
那天钞钙，我揣著相機(jī)與錄音鳄橘，去河邊找鬼。笑死芒炼，一個(gè)胖子當(dāng)著我的面吹牛瘫怜，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播本刽，決...
沈念sama閱讀 40,091評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼鲸湃，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了子寓？” 一聲冷哼從身側(cè)響起暗挑，我...
開(kāi)封第一講書(shū)人閱讀 38,929評(píng)論 0贊 274
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎斜友，沒(méi)想到半個(gè)月后炸裆，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,346評(píng)論 1贊 311
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡鲜屏，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,570評(píng)論 2贊 333
?白月光啟示錄
正文我和宋清朗相戀三年烹看，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片洛史。...
茶點(diǎn)故事閱讀 39,739評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡惯殊，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出也殖，到底是詐尸還是另有隱情土思，我是刑警寧澤，帶...
沈念sama閱讀 35,437評(píng)論 5贊 344
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站己儒，受9級(jí)特大地震影響崎岂，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜址愿，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,037評(píng)論 3贊 326
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一该镣、第九天我趴在偏房一處隱蔽的房頂上張望冻璃。院中可真熱鬧响谓，春花似錦、人聲如沸省艳。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,677評(píng)論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)跋炕。三九已至赖晶，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間辐烂，已是汗流浹背遏插。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,833評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留纠修，地道東北人胳嘲。一個(gè)月前我還...
沈念sama閱讀 47,760評(píng)論 2贊 369
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像扣草，于是被迫代替她去往敵國(guó)和親了牛。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,647評(píng)論 2贊 354