分类和回归树CART教学.ppt

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