机器学习方法与实践 课件 CART

决策树：分类与回归树（CART）DecisionTrees：ClassificationAndRegressionTree主讲：耿阳李敖计算机与信息技术学院视觉智能实验室（VisInt）BeijingJiaotong

University分类与回归树(CART算法)回归树：用于预测连续目标（例如温度、湿度）分类树：用于预测离散的分类目标（例如晴天、阴天）利用树结构描述一组划分规则，其中每个非叶节点都定义了一个划分准则，叶子节点存储了预测值CART的生成回归树的生成设Y是连续变量，给定训练数据集：回归树将输入空间划分为M个区域R1,R2,…,RM，并且在每个区域Rm上定义一个固定的输出值cm，回归树模型表示为：其中cm可以用平方误差最小的准则求解：单元Rm上的cm的最优值

是Rm上的所有输入实例xi对应的输出yi的均值：CART的生成问题：如何对输入空间进行划分？贪心方法：选择第j个变量x(j)和它取的值s，作为切分变量和切分点，并定义两个区域：然后寻找最优切分变量j和最优切分点s：且遍历所有输入变量，找到最优的切分变量j，构成一个对(j,s)，依此将输入空间划分为两个区域对每个区域重复上述划分过程，直到满足停止条件为止将这样生成的回归树称为最小二乘回归树（leastsquaresregressiontree）CART的生成最小二乘回归树生成算法输入：训练数据集D输出：回归树f(x)（1）选择最优切分变量j与切分点s，求解遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对(j,s)CART的生成最小二乘回归树生成算法（2）用选定的对(j,s)划分区域并决定相应的输出值：（3）继续对两个子区域调用步骤（1），（2），直至满足停止条件（4）将输入空间划分为M个区域R1,R2,…,RM，生成回归树：分类与回归树(CART算法)例子：训练数据集如下：x1是离散特征，x2是连续特征，y是目标值例题来源：/u_15127518/3502056分类与回归树(CART算法)例子：训练数据集如下：如果选择离散特征x1，并将切分点s设置为x1是否小于等于0，这时R1={2}，R2={1,3,4}c1=8，c2=(10+12+18)/3=13.33再根据公式Error(x1,0)=m(s)=

=34.67例题来源：/u_15127518/3502056分类与回归树(CART算法)例子：训练数据集如下：如果选择连续特征x2，切分点s可以设置为2.5或3.5，最后求出的c1、c2、Error结果列举如下：例题来源：/u_15127518/3502056分类与回归树(CART算法)例子：训练数据集如下：可以看到，当前最优划分特征为x2，切分点为3.5。此时回归树T1为：例题来源：/u_15127518/3502056分类与回归树(CART算法)例子：训练数据集如下：用f(x)拟合数据集中的标签，得到的残差如下：例题来源：/u_15127518/3502056分类与回归树(CART算法)例子：训练数据集如下：针对R2节点（x2≤3.5）继续划分。例题来源：/u_15127518/3502056分类与回归树(CART算法)例子：训练数据集如下：整个回归树为：例题来源：/u_15127518/3502056CART的生成分类树的生成基尼系数对于给定的数据集D，对应的基尼系数定义为：

Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率

Gini(D)越小，数据集D的纯度越高属性a的基尼系数定义为：应选择那个使划分后基尼系数最小的属性作为当前的最优划分，即CART的生成分类树生成算法输入：训练数据集D，停止计算的条件输出：CART分类树根据训练数据集，从根结点开始，递归地对每个结点进行以下操作：（1）对于训练数据集为D，枚举每一个切分对（a,s），将D分割成D1和D2两部分，计算切分后对应的基尼系数（2）在所有的切分对中选择使得基尼系数最小的作为当前的切分规则（3）对两个子结点递归地调用（1），（2），直至满足停止条件（4）生成CART分类树

分类与回归树(CART算法)例子：贷款申请样本数据集

分类与回归树(CART算法)例子：贷款申请样本数据集

特征A1的基尼系数：由于Gini(D,A1=1)和Gini(D,A1=3)相等，且最小，所以A1=1和A1=3都可以选作A1的最优切分点。以A1，A2，A3，A4表示年龄、有工作、有自己的房子和信贷情况4个特征以1，2，3表示年龄的值为青年、中年和老年以1，2表示有工作和有自己的房子的值为是和否以1，2，3表示信贷情况的值为非常好、好和一般分类与回归树(CART算法)例子：贷款申请样本数据集

特征A2的基尼系数：特征A3的基尼系数：由于A2和A3只有一个切分点，所以它们就是最优切分点以A1，A2，A3，A4表示年龄、有工作、有自己的房子和信贷情况4个特征以1，2，3表示年龄的值为青年、中年和老年以1，2表示有工作和有自己的房子的值为是和否以1，2，3表示信贷情况的值为非常好、好和一般分类与回归树(CART算法)例子：贷款申请样本数据集

特征A4的基尼系数：Gini(D,A4=3)最小，所以A4=3为A4的最优切分点以A1，A2，A3，A4表示年龄、有工作、有自己的房子和信贷情况4个特征以1，2，3表示年龄的值为青年、中年和老年以1，2表示有工作和有自己的房子的值为是和否以1，2，3表示信贷情况的值为非常好、好和一般分类与回归树(CART算法)例子：贷款申请样本数据集

在A1，A2，A3，A4几个特征中，Gini(D,A3=1)=0.27最小，所以选择特征A3为最优特征，A3=1为其最优切分点。于是根结点生成两个子结点，一个是叶结点。对另一个结点继续使用以上方法在A1，A2，A4中选择最优特征及其最优切分点，结果是A2=1。依此计算得知，所得结点都是叶结点。以A1，A2，A3，A4表示年龄、有工作、有自己的房子和信贷情况4个特征以1，2，3表示年龄的值为青年、中年和老年以1，2表示有工作和有自己的房子的值为是和否以1，2，3表示信贷情况的值为非常好、好和一般参考文献参考资料李航.统计