分类和回归树CART
分类和回归树 (CART )
李保坤老师
西南财经大学
统计学院本节内容提要CART 算法关于混杂度 -- 基尼指数 -- 二分指数剪枝CART 对缺失值的处理 CART 算法分类和回归树(Classification and
Regression Trees ,CART )有时被写作 C&RTBreiman, L., J. H.
Friedman, R. A. Oshen,and C. J. Stone, 1984. Classification andregression
trees. Belmont, CA: Wadsworth.CART 算法 ? 概览二叉树算法把数据递进划分为两个子集 , 每一个子集
的记录会更纯这一算法把误分类代价、先验概率、成本
- 复杂性剪枝CART 算法
1. 基本思想是在每一个节点选择一个划分 ,
使得其每一个子集 ( 子节点 ) 的数据比父
节点的数据更“ 纯” 一些。CART 用一个混杂
度测度it 来测量一个划分的节点数据的混
杂度。CART 算法
2. 如果在节点t 的一个划分 s 把pL 比率的数据
送到左子节点tL , 把pR 比率的数据送到右子
节点tR , 在节点t 的划分 s 降低的混杂度被定
义为 :CART 算法3. CART 树的生长始于节点即, 全部训练数据 t1, 在所有可能的划分中选择一个划分
s* , 该划分导致混杂度的最大降低。
s* 把节点t1 划分为t2 和 t3 两个子节点。CART 算法
4. 以上的划分搜索过程为每一个子节点重复
使用。
5. 当所有的终止标准被满足后生长过程停止。混杂度的几个测度目标变量是类别变量 ( 名义 ) ? 基尼指数 ( Gini Index ) ? 二分指数 (Twoing Index )目标变量是类别变量 ( 有
序 ) ? 有序二分指数 (Ordered Twoing )目标变量是连续变量 ? 最小平方偏差 (Least-Squared Deviation )混杂度 : 基尼指数如果一个数据集合T 的观测记录里包括n
个类别 , 基尼指数的定义如下 : 其中是节点t 的类别j 的相对比例混杂度 : 基尼指数如果一个数据集合T 被划分
为两个子集合T
1
和T , 对应的记录数量分别是N 和N , 划分
2 1 2
split 的基尼指数被定义为 :实际上 , 这是两个子集的基尼指数的加权
平均值混杂度 : 基尼指数基尼指数的最大值是1-1/k , 在
此k 是类别的
数量。当观测记录在k 个类别上平均分布时
基尼指数就会最大基尼指数的最小值的0 , 这是当所有的观测
记录都属于某一个类别时会发生的情况混杂度 : 基尼
指数一个分类成功的输入变量会把观测记录中的某一个类别在节点中占多数输入变量在这方面越成功 , 从根节点到子
节点的基尼指数的变化量就越大基尼指数的变化量对
于划分s , 在节点t , 基尼指数的变化量可
以按以下公式计算 :能实现最大变化量的划分s ( 即在某输入变
量某个值上把节点里观测记录划分到两个
子节点 ) 将被选用关于混杂度示例后面的 3 个片子由Dr. Hyunjoong Kim, Dept
of Statistics, University of Tennessee 制作混杂度测量 : 基尼
指数
数据
混杂度
一个划分划分的优度
基尼指数的变化量:数据
混杂度
另一个
划分
是更好
的划分基尼指数的广义公式其中
Ci|j 把类别j 的记录分类到类别i 的错误分类代价πj 类别j 的先验值基尼指数划分的特点基尼指数关注的目标变量里面最大的类 , 它
试图找到一个划分把它和其它类别区分开
来。完美的系列划分将会得到k 个纯粹的子节点 ,
每一个节点对应目标变量的一个类别。如果误分类代价因素被加入 , 基尼指数试图
把代价最大的类别区分开来。二分指数划分的特点二
分指数首先把目标变量的几个类别划分为
2 个超类别 ( 或群 ) , 每个群加起来接近数
据的一半。二分指数然后搜寻把这两个超级群分成子节
点的划分。二分指数的划分方法对于在节点t 的划分s , 二分指数的改进量为 :产生两个子节点间最大差异的划分s 被选择。基尼指数对二分指数当目标变量的类别数很小时 ,2 to 4 , 使用
基尼指数。当目标变量的类别数较大时 ,4 以上 , 使用二分指数。注意当使用二分指标时 , 误分类代价因素
不
能使用。CART 终止条件一个节点中的所有记录其预测变量值相同树的深度达到了预先指定的最大值节点的记录量小于预先指定的最小节点记录量节点是纯节点 , 即所有的记录的目标变量值相同混杂度的最大下降值小于一个预
先指定的值剪枝在终止条件被满足 , 划分停止之后 , 下一步
是剪枝 : ? 给树剪枝就是剪掉“ 弱枝” , 弱枝指的是在验证数据上误分类率高的树枝 ? 为树剪枝会增加训练数据上的错误分类率 ,
但精简的树会提高新记录上的预测能力 ? 剪掉的是最没有预测能力的枝CART 对缺失值的处理一个代理划分将被用于处理预测变量中的缺
失值假定X* 是节点t 的最佳划分s* 所在的预测输
入变量 , 代理划分s 使用另外一个输入变量X ,
s 在t 节点的划分效果最接近s* 。CART 对缺失值的处理如果要预测一个新记录的目标变量值 , 它在
节点t 的X* 对应的输入变量上有缺失值 , 预
测将使用代理划分s 如果该新记录在X 变量上
没有缺失值
