分类和回归树（CART）.ppt

文档介绍：分类和回归树(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的相对比例