文档介绍：分类和回归树CART-精品
本节内容提要
CART算法
关于混杂度
--基尼指数
--二分指数
剪枝
CART对缺失值的处理
CART算法
分类和回归树（Classification and Regressi分类和回归树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）
关于混杂度示例
后面的３个片子由Dr. Hyunjoong Kim, Dept of Statistics, University of Tennessee制作
混杂度测量：基尼指数
一个划分
数据
混杂度
划分的优度
基尼指数的变化量：
另一个
划分
数据
混杂度
是更好
的划分
基尼指数的广义公式
其中
　
C(i|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变量上没有缺失值
模