決策樹(shù)之CART（分類回歸樹(shù)）詳解，具體內(nèi)容如下

1、CART分類回歸樹(shù)簡(jiǎn)介

  CART分類回歸樹(shù)是一種典型的二叉決策樹(shù)，可以處理連續(xù)型變量和離散型變量。如果待預(yù)測(cè)分類是離散型數(shù)據(jù)，則CART生成分類決策樹(shù)；如果待預(yù)測(cè)分類是連續(xù)型數(shù)據(jù)，則CART生成回歸決策樹(shù)。數(shù)據(jù)對(duì)象的條件屬性為離散型或連續(xù)型，并不是區(qū)別分類樹(shù)與回歸樹(shù)的標(biāo)準(zhǔn)，例如表1中，數(shù)據(jù)對(duì)象xi的屬性A、B為離散型或連續(xù)型，并是不區(qū)別分類樹(shù)與回歸樹(shù)的標(biāo)準(zhǔn)。

表1

2、CART分類回歸樹(shù)分裂屬性的選擇

  2.1 CART分類樹(shù)——待預(yù)測(cè)分類為離散型數(shù)據(jù)

  選擇具有最小Gain_GINI的屬性及其屬性值，作為最優(yōu)分裂屬性以及最優(yōu)分裂屬性值。Gain_GINI值越小，說(shuō)明二分之后的子樣本的“純凈度”越高，即說(shuō)明選擇該屬性（值）作為分裂屬性（值）的效果越好。
  對(duì)于樣本集S，GINI計(jì)算如下：

其中，在樣本集S中，Pk表示分類結(jié)果中第k個(gè)類別出現(xiàn)的頻率。

  對(duì)于含有N個(gè)樣本的樣本集S，根據(jù)屬性A的第i個(gè)屬性值，將數(shù)據(jù)集S劃分成兩部分，則劃分成兩部分之后，Gain_GINI計(jì)算如下：

其中，n1、n2分別為樣本子集S1、S2的樣本個(gè)數(shù)。

  對(duì)于屬性A，分別計(jì)算任意屬性值將數(shù)據(jù)集劃分成兩部分之后的Gain_GINI，選取其中的最小值，作為屬性A得到的最優(yōu)二分方案：

對(duì)于樣本集S，計(jì)算所有屬性的最優(yōu)二分方案，選取其中的最小值，作為樣本集S的最優(yōu)二分方案：

所得到的屬性A及其第i屬性值，即為樣本集S的最優(yōu)分裂屬性以及最優(yōu)分裂屬性值。

  2.2 CART回歸樹(shù)——待預(yù)測(cè)分類為連續(xù)型數(shù)據(jù)

  區(qū)別于分類樹(shù)，回歸樹(shù)的待預(yù)測(cè)分類為連續(xù)型數(shù)據(jù)。同時(shí)，區(qū)別于分類樹(shù)選取Gain_GINI為評(píng)價(jià)分裂屬性的指標(biāo)，回歸樹(shù)選取Gain_σ為評(píng)價(jià)分裂屬性的指標(biāo)。選擇具有最小Gain_σ的屬性及其屬性值，作為最優(yōu)分裂屬性以及最優(yōu)分裂屬性值。Gain_σ值越小，說(shuō)明二分之后的子樣本的“差異性”越小，說(shuō)明選擇該屬性（值）作為分裂屬性（值）的效果越好。

  針對(duì)含有連續(xù)型分類結(jié)果的樣本集S，總方差計(jì)算如下：

其中，μ表示樣本集S中分類結(jié)果的均值，Ck表示第k個(gè)分類結(jié)果。

  對(duì)于含有N個(gè)樣本的樣本集S，根據(jù)屬性A的第i個(gè)屬性值，將數(shù)據(jù)集S劃分成兩部分，則劃分成兩部分之后，Gain_σ計(jì)算如下：

  對(duì)于屬性A，分別計(jì)算任意屬性值將數(shù)據(jù)集劃分成兩部分之后的Gain_σ，選取其中的最小值，作為屬性A得到的最優(yōu)二分方案：

  對(duì)于樣本集S，計(jì)算所有屬性的最優(yōu)二分方案，選取其中的最小值，作為樣本集S的最優(yōu)二分方案：

所得到的屬性A及其第i屬性值，即為樣本集S的最優(yōu)分裂屬性以及最優(yōu)分裂屬性值。

3、CART分類回歸樹(shù)的剪枝

  由于決策樹(shù)的建立完全是依賴于訓(xùn)練樣本，因此該決策樹(shù)對(duì)訓(xùn)練樣本能夠產(chǎn)生完美的擬合效果。但這樣的決策樹(shù)對(duì)于測(cè)試樣本來(lái)說(shuō)過(guò)于龐大而復(fù)雜，可能產(chǎn)生較高的分類錯(cuò)誤率。這種現(xiàn)象就稱為過(guò)擬合。因此需要將復(fù)雜的決策樹(shù)進(jìn)行簡(jiǎn)化，即去掉一些節(jié)點(diǎn)解決過(guò)擬合問(wèn)題，這個(gè)過(guò)程稱為剪枝。

  剪枝方法分為預(yù)剪枝和后剪枝兩大類。預(yù)剪枝是在構(gòu)建決策樹(shù)的過(guò)程中，提前終止決策樹(shù)的生長(zhǎng)，從而避免過(guò)多的節(jié)點(diǎn)產(chǎn)生。預(yù)剪枝方法雖然簡(jiǎn)單但實(shí)用性不強(qiáng)，因?yàn)楹茈y精確的判斷何時(shí)終止樹(shù)的生長(zhǎng)。后剪枝是在決策樹(shù)構(gòu)建完成之后，對(duì)那些置信度不達(dá)標(biāo)的節(jié)點(diǎn)子樹(shù)用葉子結(jié)點(diǎn)代替，該葉子結(jié)點(diǎn)的類標(biāo)號(hào)用該節(jié)點(diǎn)子樹(shù)中頻率最高的類標(biāo)記。后剪枝方法又分為兩種，一類是把訓(xùn)練數(shù)據(jù)集分成樹(shù)的生長(zhǎng)集和剪枝集；另一類算法則是使用同一數(shù)據(jù)集進(jìn)行決策樹(shù)生長(zhǎng)和剪枝。常見(jiàn)的后剪枝方法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。其中，悲觀錯(cuò)誤剪枝法PEP(Pessimistic Error Pruning)在“決策樹(shù)之C4.5算法詳解”中有詳細(xì)介紹，感興趣的小童鞋可以了解學(xué)習(xí)。這里我們?cè)敿?xì)介紹CART分類回歸樹(shù)中應(yīng)用最廣泛的剪枝算法——代價(jià)復(fù)雜性剪枝法CCP(Cost Complexity Pruning)。

  代價(jià)復(fù)雜性剪枝法CCP(Cost Complexity Pruning)主要包含兩個(gè)步驟：（1）從原始決策樹(shù)T0開(kāi)始生成一個(gè)子樹(shù)序列{T0,T1,...,Tn}，其中，Ti+1從Ti產(chǎn)生，Tn為根節(jié)點(diǎn)。（2）從第1步產(chǎn)生的子樹(shù)序列中，根據(jù)樹(shù)的真實(shí)誤差估計(jì)選擇最佳決策樹(shù)。

  CCP剪枝法步驟（1）

  生成子樹(shù)序列{T0,T1,...,Tn}的基本思想是從T0開(kāi)始，裁剪Ti中關(guān)于訓(xùn)練數(shù)據(jù)集誤差增加最小的分枝來(lái)得到Ti+1。實(shí)際上，當(dāng)1棵樹(shù)T在節(jié)點(diǎn)t處剪枝時(shí)，它的誤差增加直觀上認(rèn)為是R(t)−R(Tt)，其中，R(t)為在節(jié)點(diǎn)t的子樹(shù)被裁剪后節(jié)點(diǎn)t的誤差，R(Tt)為在節(jié)點(diǎn)t的子樹(shù)沒(méi)被裁剪時(shí)子樹(shù)Tt的誤差。然而，剪枝后，T的葉子數(shù)減少了L(Tt)−1，其中， L(Tt)為子樹(shù)Tt的葉子數(shù)，也就是說(shuō)，T的復(fù)雜性減少了。因此，考慮樹(shù)的復(fù)雜性因素，樹(shù)分枝被裁剪后誤差增加率由下式?jīng)Q定：

其中，R(t)表示節(jié)點(diǎn)t的子樹(shù)被裁剪后節(jié)點(diǎn)t的誤差，R(t)=r(t)∗p(t)，r(t)是節(jié)點(diǎn)t的誤差率，p(t)是節(jié)點(diǎn)t上的樣本個(gè)數(shù)與訓(xùn)練集中樣本個(gè)數(shù)的比例。R(Tt)表示節(jié)點(diǎn)t的子樹(shù)沒(méi)被裁剪時(shí)子樹(shù)Tt的誤差，即子樹(shù)Tt上所有葉子節(jié)點(diǎn)的誤差之和。

  Ti+1就是選擇Ti中具有最小α值所對(duì)應(yīng)的剪枝樹(shù)。

  例如：圖1中ti表示決策樹(shù)中第i個(gè)節(jié)點(diǎn)，A、B表示訓(xùn)練集中的兩個(gè)類別，A、B之后的數(shù)據(jù)表示落入該節(jié)點(diǎn)分別屬于A類、B類的樣本個(gè)數(shù)。

  圖1，決策樹(shù)中訓(xùn)練樣本總個(gè)數(shù)為80。對(duì)于節(jié)點(diǎn)t4，其中，A類樣本46個(gè)，B類樣本4個(gè)，根據(jù)大多數(shù)原則，則節(jié)點(diǎn)t4中樣本為A類，故節(jié)點(diǎn)t4的子樹(shù)（t8、t9）被裁剪之后t4的誤差為：450∗5080=480。節(jié)點(diǎn)t4的子樹(shù)（t8、t9）被裁剪之前t4的誤差為：145∗4580+25∗580=380。故α(t4)=480−3802−1=0.0125。類似過(guò)程，依次得到所有節(jié)點(diǎn)的誤差增加率，如表2：

表2

  從表2可以看出，在原始樹(shù)T0行，4個(gè)非葉節(jié)點(diǎn)中t4的α值最小，因此，裁剪T0的t4節(jié)點(diǎn)的分枝得到T1；在T1行，雖然t2和t3的α值相同，但裁剪t2的分枝可以得到更小的決策樹(shù)，因此，T2是裁剪T1中的t2分枝得到的。

  CCP剪枝法步驟（2）

  如何根據(jù)第1步產(chǎn)生的子樹(shù)序列{T0,T1,...,Tn}，選擇出1棵最佳決策樹(shù)是CCP剪枝法步驟（2）的關(guān)鍵。通常采用的方法有兩種，一種是V番交叉驗(yàn)證(V-fold cross-validation)，另一種是基于獨(dú)立剪枝數(shù)據(jù)集。此處不在過(guò)分贅述，感興趣的小童鞋，可以閱讀參考文獻(xiàn)[1][2][3]等。

參考文獻(xiàn)

[1] 魏紅寧. 決策樹(shù)剪枝方法的比較[J]. 西南交通大學(xué)學(xué)報(bào), 2005, 40(1):44-48.
[2] 張宇. 決策樹(shù)分類及剪枝算法研究[D]. 哈爾濱理工大學(xué), 2009.
[3] Breiman L, Friedman J H, Olshen R, et al. Classification and Regression Trees[J]. Biometrics, 1984, 40(3):358.

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。