CART分类与回归树

1、CART分类与回归树本文结构：CART算法有两步回归树的生成分类树的生成剪枝CART-ClassificationandRegressionT分类与回归树，是二叉树，可以用于分类，也可以用于回归问题，最先由Breiman等提出。分类树的输出是样本的类别，回归树的输出是一个实数。CART算法有两步：决策树生成和剪枝。决策树生成：递归地构建二叉决策树的过程，基于训练数据集生成决策树，生成的决策树要尽量大；自上而下从根开始建立节点，在每个节点处要选择一个最好的属性来分裂，使得子节点中的训练集尽量的纯。不同的算法使用不同的指标来定义最好：分类问题，可以选择GINI，双化或有序双化；回归问题，可以使用最

2、小二乘偏差（LSD）或最小绝对偏差（LAD）。决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。这里用代价复杂度剪枝Cost-ComplexityPruning（CCP）回归树的生成回归树模型表示为：其中，数据空间被划分成了R1Rm单元，每个单元上有一个固定的输出值cm。这样就可以计算模型输出值与实际值的误差：我们希望每个单元上的cm，可以使得这个平方误差最小化，易知当cm为相应单元上的所有实际值的均值时，可以达到最优:那么如何生成这些单元划分？假设，我们选择变量xj为切分变量，它的取值s为切分点，那么就会得到两个区域:W町=找10W科和&4巧=XI工

3、J当j和s固定时，我们要找到两个区域的代表值c1,c2使各自区间上的平方差最小,minmin工+min(y.-Cj)2L片曲】*前面已经知道c1，c2为区间上的平均,&-ve(ytl咼e尺(人切和c;=ave(j(|x,场(/)那么对固定的j只需要找到最优的S,然后通过遍历所有的变量，我们可以找到最优的j，这样我们就可以得到最优对(j，S)，并得到两个区间。上述过程表示的算法步骤为:输人iiiitMft掲集zh輸出I回归W/(X).庄训练数据集所務怖输入空间中，翅归地将毎个区城创分为两个子区壊井决定帚个子区域上的输出值，构建二叉决门)选祥矗忧切分变it,与切分点求解氐工3-*+価工(Vj-cJ

4、追历变燉八对同定的切分变Sjfi描切分点乩选择便式(5.21)达到股小值的对U/)*用选定的对GU)划分区域并决定相应的输出値；耳(7翼|日)5*却(M)匕中j竹)継续对两个子区域调用步W(i).(2),H5W足秤止条件.将输入空间划分为个区域知&严，心*生成决AW：即：(1) 考虑数据集D上的所有特征j,遍历每一个特征下所有可能的取值或者切分点s,将数据集D划分成两部分D1和D2(2) 分别计算上述两个子集的平方误差和，选择最小的平方误差对应的特征与分割点，生成两个子节点。(3) 对上述两个子节点递归调用步骤(1)(2),直到满足停止条件。分类树的生成(1) 对每个特征A,对它的所有可能取值

5、a,将数据集分为A=a,和A!=a两个子集，计算集合D的基尼指数：(2) 遍历所有的特征A,计算其所有可能取值a的基尼指数，选择D的基尼指数最小值对应的特征及切分点作为最优的划分，将数据分为两个子集。(3) 对上述两个子节点递归调用步骤(1)(2),直到满足停止条件。(4) 生成CART决策树。其中GINI指数：1、是一种不等性度量；2、是介于01之间的数，0-完全相等，1-完全不相等；3、总体内包含的类别越杂乱，GINI指数就越大(跟熵的概念很相似)定义：分类问题中，假设有K个类，样本属于第k类的概率为pk，则概率分布的基尼指数为:1样本集合D的基尼指数为:IGI其中Ck为数据集D中属于第k

6、类的样本子集。如果数据集D根据特征A在某一取值a上进行分割，得到D1，D2两部分后，那么在特征A下集合D的基尼指数为:其中算法的停止条件有:1、节点中的样本个数小于预定阈值，2、样本集的Gini系数小于预定阈值(此时样本基本属于同一类)3、或没有更多特征。下面来看一下例子：最后一列是我们要分类的目标。名祢表面惡益治生链飞水生有腿拱标记Aa早0甫乳至例如，按照“体温为恒温和非恒温”进行划分，计算如下：恒温时包含哺乳类5个、鸟类2个非恒温时包含爬行类3个、鱼类3个、两栖类2个4264得到特征体温下数据集的GINI指数:GINI_G1611216162-1st2的小，所以剪掉t2:并且令a(3)=1/8最后剩下t1，计算后gt=1/4,所以a(4)=1/4。如此我们得到：a(0)=