CART分類與回歸樹(shù)

1、CART分類與回歸樹(shù)本文結(jié)構(gòu)：CART算法有兩步回歸樹(shù)的生成分類樹(shù)的生成剪枝CART-ClassificationandRegressionT分類與回歸樹(shù)，是二叉樹(shù)，可以用于分類，也可以用于回歸問(wèn)題，最先由Breiman等提出。分類樹(shù)的輸出是樣本的類別，回歸樹(shù)的輸出是一個(gè)實(shí)數(shù)。CART算法有兩步：決策樹(shù)生成和剪枝。決策樹(shù)生成：遞歸地構(gòu)建二叉決策樹(shù)的過(guò)程，基于訓(xùn)練數(shù)據(jù)集生成決策樹(shù)，生成的決策樹(shù)要盡量大；自上而下從根開(kāi)始建立節(jié)點(diǎn)，在每個(gè)節(jié)點(diǎn)處要選擇一個(gè)最好的屬性來(lái)分裂，使得子節(jié)點(diǎn)中的訓(xùn)練集盡量的純。不同的算法使用不同的指標(biāo)來(lái)定義最好：分類問(wèn)題，可以選擇GINI，雙化或有序雙化；回歸問(wèn)題，可以使用最

2、小二乘偏差（LSD）或最小絕對(duì)偏差（LAD）。決策樹(shù)剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹(shù)進(jìn)行剪枝并選擇最優(yōu)子樹(shù)，這時(shí)損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。這里用代價(jià)復(fù)雜度剪枝Cost-ComplexityPruning（CCP）回歸樹(shù)的生成回歸樹(shù)模型表示為：其中，數(shù)據(jù)空間被劃分成了R1Rm單元，每個(gè)單元上有一個(gè)固定的輸出值cm。這樣就可以計(jì)算模型輸出值與實(shí)際值的誤差：我們希望每個(gè)單元上的cm，可以使得這個(gè)平方誤差最小化，易知當(dāng)cm為相應(yīng)單元上的所有實(shí)際值的均值時(shí)，可以達(dá)到最優(yōu):那么如何生成這些單元?jiǎng)澐郑考僭O(shè)，我們選擇變量xj為切分變量，它的取值s為切分點(diǎn)，那么就會(huì)得到兩個(gè)區(qū)域:W町=找10W科和&4巧=XI工

3、J當(dāng)j和s固定時(shí)，我們要找到兩個(gè)區(qū)域的代表值c1,c2使各自區(qū)間上的平方差最小,minmin工+min(y.-Cj)2L片曲】*前面已經(jīng)知道c1，c2為區(qū)間上的平均,&-ve(ytl咼e尺(人切和c;=ave(j(|x,場(chǎng)(/)那么對(duì)固定的j只需要找到最優(yōu)的S,然后通過(guò)遍歷所有的變量，我們可以找到最優(yōu)的j，這樣我們就可以得到最優(yōu)對(duì)(j，S)，并得到兩個(gè)區(qū)間。上述過(guò)程表示的算法步驟為:輸人iiiitMft掲集zh輸出I回歸W/(X).莊訓(xùn)練數(shù)據(jù)集所務(wù)怖輸入空間中，翅歸地將毎個(gè)區(qū)城創(chuàng)分為兩個(gè)子區(qū)壊井決定帚個(gè)子區(qū)域上的輸出值，構(gòu)建二叉決門)選祥矗憂切分變it,與切分點(diǎn)求解氐工3-*+価工(Vj-cJ

4、追歷變燉八對(duì)同定的切分變Sjfi描切分點(diǎn)乩選擇便式(5.21)達(dá)到股小值的對(duì)U/)*用選定的對(duì)GU)劃分區(qū)域并決定相應(yīng)的輸出値；耳(7翼|日)5*卻(M)匕中j竹)継續(xù)對(duì)兩個(gè)子區(qū)域調(diào)用步W(i).(2),H5W足秤止條件.將輸入空間劃分為個(gè)區(qū)域知&嚴(yán)，心*生成決AW：即：(1) 考慮數(shù)據(jù)集D上的所有特征j,遍歷每一個(gè)特征下所有可能的取值或者切分點(diǎn)s,將數(shù)據(jù)集D劃分成兩部分D1和D2(2) 分別計(jì)算上述兩個(gè)子集的平方誤差和，選擇最小的平方誤差對(duì)應(yīng)的特征與分割點(diǎn)，生成兩個(gè)子節(jié)點(diǎn)。(3) 對(duì)上述兩個(gè)子節(jié)點(diǎn)遞歸調(diào)用步驟(1)(2),直到滿足停止條件。分類樹(shù)的生成(1) 對(duì)每個(gè)特征A,對(duì)它的所有可能取值

5、a,將數(shù)據(jù)集分為A=a,和A!=a兩個(gè)子集，計(jì)算集合D的基尼指數(shù)：(2) 遍歷所有的特征A,計(jì)算其所有可能取值a的基尼指數(shù)，選擇D的基尼指數(shù)最小值對(duì)應(yīng)的特征及切分點(diǎn)作為最優(yōu)的劃分，將數(shù)據(jù)分為兩個(gè)子集。(3) 對(duì)上述兩個(gè)子節(jié)點(diǎn)遞歸調(diào)用步驟(1)(2),直到滿足停止條件。(4) 生成CART決策樹(shù)。其中GINI指數(shù)：1、是一種不等性度量；2、是介于01之間的數(shù)，0-完全相等，1-完全不相等；3、總體內(nèi)包含的類別越雜亂，GINI指數(shù)就越大(跟熵的概念很相似)定義：分類問(wèn)題中，假設(shè)有K個(gè)類，樣本屬于第k類的概率為pk，則概率分布的基尼指數(shù)為:1樣本集合D的基尼指數(shù)為:IGI其中Ck為數(shù)據(jù)集D中屬于第k

6、類的樣本子集。如果數(shù)據(jù)集D根據(jù)特征A在某一取值a上進(jìn)行分割，得到D1，D2兩部分后，那么在特征A下集合D的基尼指數(shù)為:其中算法的停止條件有:1、節(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閾值，2、樣本集的Gini系數(shù)小于預(yù)定閾值(此時(shí)樣本基本屬于同一類)3、或沒(méi)有更多特征。下面來(lái)看一下例子：最后一列是我們要分類的目標(biāo)。名禰表面惡益治生鏈飛水生有腿拱標(biāo)記Aa早0甫乳至例如，按照“體溫為恒溫和非恒溫”進(jìn)行劃分，計(jì)算如下：恒溫時(shí)包含哺乳類5個(gè)、鳥(niǎo)類2個(gè)非恒溫時(shí)包含爬行類3個(gè)、魚(yú)類3個(gè)、兩棲類2個(gè)4264得到特征體溫下數(shù)據(jù)集的GINI指數(shù):GINI_G1611216162-1st2的小，所以剪掉t2:并且令a(3)=1/8最后剩下t1，計(jì)算后gt=1/4,所以a(4)=1/4。如此我們得到：a(0)=