姓名：崔升? ? 學(xué)號(hào)：14020120005
轉(zhuǎn)載自：http://www.cnblogs.com/en-heng/p/5173704.html
【嵌牛導(dǎo)讀】：
分類與回歸樹（Classification and Regression Trees, CART）是由四人幫Leo Breiman, Jerome Friedman, Richard Olshen與Charles Stone于1984年提出，既可用于分類也可用于回歸。本文將主要介紹用于分類的CART。CART被稱為數(shù)據(jù)挖掘領(lǐng)域內(nèi)里程碑式的算法。
【嵌牛鼻子】：經(jīng)典大數(shù)據(jù)算法之CART算法的簡單介紹
【嵌牛提問】：CART是一種怎么的算法，其數(shù)學(xué)原理又是如何？
【嵌牛正文】：
?1. 前言
不同于C4.5，CART本質(zhì)是對(duì)特征空間進(jìn)行二元?jiǎng)澐郑碈ART生成的決策樹是一棵二叉樹），并能夠?qū)?biāo)量屬性（nominal attribute）與連續(xù)屬性（continuous attribute）進(jìn)行分裂。
2. CART生成
前一篇提到過決策樹生成涉及到兩個(gè)問題：如何選擇最優(yōu)特征屬性進(jìn)行分裂，以及停止分裂的條件是什么。
特征選擇
CART對(duì)特征屬性進(jìn)行二元分裂。特別地，當(dāng)特征屬性為標(biāo)量或連續(xù)時(shí)，可選擇如下方式分裂：
An instance goes left if CONDITION, and goes right otherwise
即樣本記錄滿足CONDITION則分裂給左子樹，否則則分裂給右子樹。
標(biāo)量屬性
進(jìn)行分裂的CONDITION可置為不等于屬性的某值；比如，標(biāo)量屬性Car Type取值空間為{Sports, Family, Luxury}，二元分裂與多路分裂如下：
連續(xù)屬性
CONDITION可置為不大于εε；比如，連續(xù)屬性Annual Income，εε取屬性相鄰值的平均值，其二元分裂結(jié)果如下：
接下來，需要解決的問題：應(yīng)該選擇哪種特征屬性及定義CONDITION，才能分類效果比較好。CART采用Gini指數(shù)來度量分裂時(shí)的不純度，之所以采用Gini指數(shù)，是因?yàn)檩^于熵而言其計(jì)算速度更快一些。對(duì)決策樹的節(jié)點(diǎn)tt，Gini指數(shù)計(jì)算公式如下：
Gini(t)=1?∑k[p(ck|t)]2(1)(1)Gini(t)=1?∑k[p(ck|t)]2
Gini指數(shù)即為11與類別ckck的概率平方之和的差值，反映了樣本集合的不確定性程度。Gini指數(shù)越大，樣本集合的不確定性程度越高。分類學(xué)習(xí)過程的本質(zhì)是樣本不確定性程度的減少（即熵減過程），故應(yīng)選擇最小Gini指數(shù)的特征分裂。父節(jié)點(diǎn)對(duì)應(yīng)的樣本集合為DD，CART選擇特征AA分裂為兩個(gè)子節(jié)點(diǎn)，對(duì)應(yīng)集合為DLDL與DRDR；分裂后的Gini指數(shù)定義如下：
G(D,A)=|DL||D|Gini(DL)+|DR||D|Gini(DR)(2)(2)G(D,A)=|DL||D|Gini(DL)+|DR||D|Gini(DR)
其中，|?||?|表示樣本集合的記錄數(shù)量。如上圖中的表格所示，當(dāng)Annual Income的分裂值取87時(shí)，則Gini指數(shù)計(jì)算如下：
410[1?(14)2?(34)2]+610[1?(26)2?(46)2]=0.417410[1?(14)2?(34)2]+610[1?(26)2?(46)2]=0.417
CART算法
CART算法流程與C4.5算法相類似：
若滿足停止分裂條件（樣本個(gè)數(shù)小于預(yù)定閾值，或Gini指數(shù)小于預(yù)定閾值（樣本基本屬于同一類，或沒有特征可供分裂），則停止分裂；
否則，選擇最小Gini指數(shù)進(jìn)行分裂；
遞歸執(zhí)行1-2步驟，直至停止分裂。
3. CART剪枝
CART剪枝與C4.5的剪枝策略相似，均以極小化整體損失函數(shù)實(shí)現(xiàn)。同理，定義決策樹TT的損失函數(shù)為：
Lα(T)=C(T)+α|T|(3)(3)Lα(T)=C(T)+α|T|
其中，C(T)C(T)表示決策樹的訓(xùn)練誤差，αα為調(diào)節(jié)參數(shù)，|T||T|為模型的復(fù)雜度。
CART算法采用遞歸的方法進(jìn)行剪枝，具體辦法：
將αα遞增0=α0<α1<α2<?<αn0=α0<α1<α2<?<αn，計(jì)算得到對(duì)應(yīng)于區(qū)間[αi,αi+1)[αi,αi+1)的最優(yōu)子樹為TiTi；
從最優(yōu)子樹序列{T1,T2,?,Tn}{T1,T2,?,Tn}選出最優(yōu)的（即損失函數(shù)最小的）。
如何計(jì)算最優(yōu)子樹為TiTi呢？首先，定義以tt為單節(jié)點(diǎn)的損失函數(shù)為
Lα(t)=C(t)+αLα(t)=C(t)+α
以tt為根節(jié)點(diǎn)的子樹TtTt的損失函數(shù)為
Lα(Tt)=C(Tt)+α|Tt|Lα(Tt)=C(Tt)+α|Tt|
令Lα(t)=Lα(Tt)Lα(t)=Lα(Tt)，則得到
α=C(t)?C(Tt)|Tt|?1α=C(t)?C(Tt)|Tt|?1
此時(shí)，單節(jié)點(diǎn)tt與子樹TtTt有相同的損失函數(shù)，而單節(jié)點(diǎn)tt的模型復(fù)雜度更小，故更為可??；同時(shí)也說明對(duì)節(jié)點(diǎn)tt的剪枝為有效剪枝。由此，定義對(duì)節(jié)點(diǎn)tt的剪枝后整體損失函數(shù)減少程度為
g(t)=C(t)?C(Tt)|Tt|?1g(t)=C(t)?C(Tt)|Tt|?1
剪枝流程如下：
對(duì)輸入決策樹T0T0，自上而下計(jì)算內(nèi)部節(jié)點(diǎn)的g(t)g(t)；選擇最小的g(t)g(t)作為α1α1，并進(jìn)行剪枝得到樹T1T1，其為區(qū)間[α1,α2)[α1,α2)對(duì)應(yīng)的最優(yōu)子樹。
對(duì)樹T1T1，再次自上而下計(jì)算內(nèi)部節(jié)點(diǎn)的g(t)g(t)；……α2α2……T2T2……
如此遞歸地得到最優(yōu)子樹序列，采用交叉驗(yàn)證選取最優(yōu)子樹。
關(guān)于CART剪枝算法的具體描述請(qǐng)參看[1]，其中關(guān)于剪枝算法的描述有誤：
(6)如果T不是由根節(jié)點(diǎn)單獨(dú)構(gòu)成的樹，則回到步驟(4)
應(yīng)改為回到步驟(3)，要不然所有αα均一樣了。
4. 參考資料
[1] 李航，《統(tǒng)計(jì)學(xué)習(xí)方法》.
[2] Pang-Ning Tan, Michael Steinbach, Vipin Kumar,Introduction to Data Mining.
[3] Dan Steinberg, The Top Ten Algorithms in Data Mining.
