數(shù)據(jù)挖掘算法CART

1、1.數(shù)據(jù)挖掘算法-CART分類與回歸樹(ClassificationandRegressionTrees,CART)是由四人幫LeoBreiman,JeromeFriedman,RichardOlshen與CharlesStone于1984年提出，既可用于分類也可用于回歸。本文將主要介紹用于分類的CART。CART被稱為數(shù)據(jù)挖掘領(lǐng)域內(nèi)里程碑式的算法。不同于C4.5,CART本質(zhì)是對(duì)特征空間進(jìn)行二元?jiǎng)澐?即CART生成的決策樹是一棵二叉樹)，并能夠?qū)?biāo)量屬性(nominalattribute)與連續(xù)屬性(continuousattribute)進(jìn)行分裂。前一篇提到過(guò)決策樹生成涉及到兩個(gè)問(wèn)題：如何

2、選擇最優(yōu)特征屬性進(jìn)行分裂，以及停止分裂的條件是什么。CART對(duì)特征屬性進(jìn)行二元分裂。特別地，當(dāng)特征屬性為標(biāo)量或連續(xù)時(shí)，可選擇如下方式分裂:AninstancegoesleftifCONDITION,andgoesrightotherwise即樣本記錄滿足CONDITION則分裂給左子樹，否則則分裂給右子樹。標(biāo)量屬性，二元分裂與多路分裂如下:進(jìn)行分裂的CONDITION可置為；比如，標(biāo)量屬性取值空間為F&tni忙LuKUty-CdCarTypeSports,LuxuryF&mily卜g1Cl73Gini(CarType)Sports,JLuxuryCarTVpieSportsFflmily,Lu

3、xuiryCD2C1010Gini0.167CarTypeFaniltySportsLunjryCD181Cl307Gini0J3連續(xù)屬性CONDITION可置為不大于;比如，連續(xù)屬性AnnualIncomd,取屬性相鄰值的平均值，其二元分裂結(jié)果如下：接下來(lái)，需要解決的問(wèn)題：應(yīng)該選擇哪種特征屬性及定義CONDITION，才能分類效果比較好。CART采用Gini指數(shù)來(lái)度量分裂時(shí)的不純度，之所以采用Gini指數(shù)，是因?yàn)檩^于熵而言其計(jì)算速度更快一些。對(duì)決策樹的節(jié)點(diǎn)t,Gini指數(shù)計(jì)算公式如下：Gmi(t)-1-為風(fēng)站尸Gini(t)=1-Ikp(ck|t)2(1)Gini指數(shù)即為1與類別ck的概率平

4、方之和的差值，反映了樣本集合的不確定性程度。Gini指數(shù)越大，樣本集合的不確定性程度越高。分類學(xué)習(xí)過(guò)程的本質(zhì)是樣本不確定性程度的減少(即熵減過(guò)程)，故應(yīng)選擇最小Gini指數(shù)的特征分裂。父節(jié)點(diǎn)對(duì)應(yīng)的樣本集合為D,CART選擇特征A分裂為兩個(gè)子節(jié)點(diǎn)，對(duì)應(yīng)集合為DL與Dr;分裂后的Gini指數(shù)定義如下：A)=惜忘誡氐)+G(D,A)=|Dl|D|Gini(DL)+|Dr|D|Gini(Dr)(2)其中，|表示樣本集合的記錄數(shù)量。CART算法流程與C45算法相類似:若滿足停止分裂條件(樣本個(gè)數(shù)小于預(yù)定閾值，或Gini指數(shù)小于預(yù)定閾值(樣本基本屬于同一類，或沒(méi)有特征可供分裂)，則停止分裂；否則，選擇最小

5、Gini指數(shù)進(jìn)行分裂；遞歸執(zhí)行1-2步驟，直至停止分裂。CART剪枝與C4.5的剪枝策略相似，均以極小化整體損失函數(shù)實(shí)現(xiàn)。同理，定義決策樹T的損失函數(shù)為：2(f)=cm+o|T|(3)L(T)=C(T)+a|T|(3)a其中，C(T)表示決策樹的訓(xùn)練誤差，a為調(diào)節(jié)參數(shù)，|T|為模型的復(fù)雜度。CART算法采用遞歸的方法進(jìn)行剪枝，具體辦法：將a遞增0=a0a1a2-an,計(jì)算得到對(duì)應(yīng)于區(qū)間%5+1)的最優(yōu)子樹為T；從最優(yōu)子樹序列T,T2,TJ選出最優(yōu)的(即損失函數(shù)最小的)。如何計(jì)算最優(yōu)子樹為Ti呢？首先，定義以t為單節(jié)點(diǎn)的損失函數(shù)為L(zhǎng)a(t)=C(t)+a以t為根節(jié)點(diǎn)的子樹Tt的損失函數(shù)為L(zhǎng)a(T

6、t)=C(Tt)+a|Tt|令La(t)=La(Tt)，則得到理)-g),11-1a=C(t)-C(Tt)|Tt|-1此時(shí)，單節(jié)點(diǎn)t與子樹Tt有相同的損失函數(shù)，而單節(jié)點(diǎn)t的模型復(fù)雜度更小，故更為可??；同時(shí)也說(shuō)明對(duì)節(jié)點(diǎn)t的剪枝為有效剪枝。由此，定義對(duì)節(jié)點(diǎn)t的剪枝后整體損失函數(shù)減少程度為g(t)=C(t)-C(Tt)|Tt|-1N-i剪枝流程如下:對(duì)輸入決策樹T0,自上而下計(jì)算內(nèi)部節(jié)點(diǎn)的g(t);選擇最小的g(t)作為a1，并進(jìn)行剪枝得到樹匚，其為區(qū)間a1,a2)對(duì)應(yīng)的最優(yōu)子樹。對(duì)樹T1，再次自上而下計(jì)算內(nèi)部節(jié)點(diǎn)的g(t)；.a2.T2.如此遞歸地得到最優(yōu)子樹序列，采用交叉驗(yàn)證選取最優(yōu)子樹。關(guān)于CART剪枝算法的具體描述請(qǐng)參看1，其中關(guān)于剪枝算法的描述有誤：回到步驟(3)|(6)如果T不是由根節(jié)點(diǎn)單獨(dú)構(gòu)成的樹，則回至I步驟(4)應(yīng)改為回到步驟，要不然所有a均一樣了。4.參考資料李航，統(tǒng)計(jì)學(xué)習(xí)方法.Pang-NingTa