• 1. CART 分类和回归树算法主讲人: 贾娜
  • 2. 摘 要一递归划分自变量空间 二用验证数据进行剪枝 三总结 四遗留问题
  • 3. 分类与回归树 (Classification And RegressionTrees,CART) 是一种产生二叉决策树的技术. 分类树与回归树下面有两个重要的思想: 第一个:递归地划分自变量空间的想法; 第二个:用验证数据进行剪枝的想法.
  • 4. 一递归划分自变量空间递归划分 用Y表示因变量(分类变量); 用X1,X2,…,XP表示自变量. 通过递归的方式把关于X的P维空间划分为 不重叠的矩形.
  • 5. 划分步骤: 首先: 一个自变量被选择,例如Xi和Xi的一个值Si,若选择Si把P维空间分为两部分:一部分包含的点都满足Xi<=Si;另一部分包含的点满足Xi>Si. 其次: 再把上步中得到的两部分中的一个部分,通过选择一个变量和该变量的划分值以相似的方式再划分. 重复上述步骤,直至把整个X空间划分成的每个小矩形都尽可能的是同构的.
  • 6. 例示递归划分的过程 例1(Johnson和Wichern) 乘式割草机制造商意欲发现一个把城市中的家庭分成那些愿意购买乘式割草机和不愿意购买的两类的方法。在这个城市的家庭中随机抽取12个拥有者和12个非拥有者的家庭作为样本。这些数据如表1所示。这里的自变量是收入(X1)和草地面积(X2)。类别变量Y有两个类别:拥有者和非拥有者。表1
  • 7. (本页无文本内容)
  • 8. CART如何选择划分点? 对于一个变量划分点是一对连续变量值的中点. 例如: X1可能划分点是{38.1,45.3,50.1…,109.5}; X2可能划分点是{14.4,15.4,16.2…23}. 这些划分点按照能减少杂质的多少来分级. 杂质度量方法:Gini指标. 矩形A的Gini不纯度可定义为: 其中K=1,2,…C,来表示类, Pk是观测点中属于类K的比例.
  • 9. 选择草地面积变量X2=19做第一次分割,由(X1,X2)组成的空间被分成X2<=19和X2>19的两个矩形.
  • 10. 选择收入变量X1=84.75
  • 11. (本页无文本内容)
  • 12. 我们能看到递归划分是如何精炼候选矩形,使之变得更纯的算法过程.最后阶段的递归分析如图5所示
  • 13. 这个方法被称为分类树的原因是每次划分都可以描述为把一个节点分成两个后续节点. 第一次分裂表示为树的根节点的分支,如图6
  • 14. 树的前三次划分如图7
  • 15. 整个树如下图8
  • 16. 二用验证数据进行剪枝CART过程中第二个关键的思想是用独立的验证数据集对根据训练集生成的树进行剪枝. CART剪枝目的:生成一个具有最小错误的树. 为什么要剪枝呢? 因为: 1 在树生成过程中可能存在不能提高 分类纯度的划分节点. 2 存在过拟合训练数据.
  • 17. CART 剪枝方法 CART用”成本复杂性”标准来剪枝. CART用的成本复杂性标准是分类树的简单误分(基于验证数据的) 加上一个对树的大小的惩罚因素. 即成本复杂性标准为Err(T)+α|L(T)| 其中: Err(T)是验证数据被树误分部分; L(T)是树T的叶节点数; α是每个节点惩罚成本, α是一个从0向上 变动的数字.
  • 18. 剪枝方法: 当我们从0增加α到某一值时,我们首先会遇到一个情形,对一些树T1通过在决策点剪掉子树得到的,和额外增加误分(由于有更少的叶子)而导致的成本与导致的惩罚成本的节约相平衡。我们剪掉在这个节点的子树来修剪整个树,并重新设计这个节点为叶节点。把这时的树称为T1。我们现在对T1重复先前用于整个树的过程,通过进一步增加α的值。持续这种方式,我们产生一些连续的带有节点数目减少的树直到只有一个节点的树。
  • 19. 从这个序列的树中选择一个在验证数据集上具有最小误分的树称为最小错误树。 让我们用Boston Housing数据来例示。下面是当用训练数据在树的生长阶段的算法时,XLMiner产生的输出。 表 训练记录
  • 20. 通过XLMiner在剪枝阶段产生的输出如下表所示 表 剪枝记录 树的规模对性能的影响
  • 21. (本页无文本内容)
  • 22. 最小错误树如下图9所示
  • 23. 从剪枝阶段XLMiner输出除了最小错误树以外,还有一个最佳剪枝树. 最佳剪枝树:它是在剪枝序列中含有误差在最小误差树的一个标准差之内最小的树. 最小误差率: 其中: Emin对最小误差树的错误率(作为一部分),Nval是验证数据集的数目. 最小误差率是一个带有标准差的随机变量的观测值.
  • 24. 最佳剪枝树如下图10所示
  • 25. 三 总结一. 直接把上面的错误率和其它只用训练数 据来构建分类规则的分类过程进行对比是不公平的。一个公平的比较是将训练数据(TDother)进一步划分为训练(TDtree)和测试数据(VDtree)。用TDtree构建的分类树,用VDtree修剪这个树.
  • 26. 二. 在上面描述的基本的递归划分方案中通常的变化是允许用不与坐标轴相垂直的直线来划分x变量空间(对p=3的平面和p>3的超平面)。这会导致当用线性分类函数进行分类时,整个树有很少的特殊节点,使得整个树很纯.
  • 27. 四 遗留问题先验概率和分类平衡 缺省值处理 动态特征架构 值敏感学习 概率树