《分类和回归树CART》由会员分享，可在线阅读，更多相关《分类和回归树CART（28页珍藏版）》请在金锄头文库上搜索。
1、分类和回归树CARTStillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望本节内容提要本节内容提要CART算法算法关于混杂度关于混杂度 -基尼指数基尼指数 -二分指数二分指数剪枝剪枝CART对缺失值的处理对缺失值的处理 CART算法算法 分类和回归树（分类和回归树（Classification and Regression Trees，CART） 有时被写作有时被写作 C&RT Breiman, L., J. H. Friedman, R. A. Oshen, and C. J. Ston
2、e, 1984. Classification and regression trees. Belmont, CA: Wadsworth.CART 算法算法 概览概览二叉树算法二叉树算法把数据递进划分为两个子集，每一个子集把数据递进划分为两个子集，每一个子集的记录会更纯的记录会更纯这一算法把误分类代价、先验概率、成本这一算法把误分类代价、先验概率、成本复杂性剪枝复杂性剪枝CART算法算法1. 基本思想是在每一个节点选择一个划分，基本思想是在每一个节点选择一个划分，使得其每一个子集（子节点）的数据比父使得其每一个子集（子节点）的数据比父节点的数据更节点的数据更“纯纯”一些。一些。CART 用一个
3、混用一个混杂度测度杂度测度i(t)来测量一个划分的节点数据的来测量一个划分的节点数据的混杂度。混杂度。CART算法算法2. 如果在节点如果在节点t的一个划分的一个划分 s 把把pL比率的数据比率的数据送到左子节点送到左子节点tL，把，把pR比率的数据送到右子比率的数据送到右子节点节点tR，在节点，在节点t的划分的划分 s 降低的混杂度被定降低的混杂度被定义为：义为：CART算法算法3. CART 树的生长始于节点树的生长始于节点 (即即, 全部训练数全部训练数据据) t=1, 在所有可能的划分中选择一个划分在所有可能的划分中选择一个划分s*，该划分导致混杂度的最大降低。，该划分导致混杂度的最大
4、降低。 s*把节点把节点t=1 划分为划分为t=2和和 t=3 两个子节点两个子节点。CART算法算法4. 以上的划分搜索过程为每一个子节点重复以上的划分搜索过程为每一个子节点重复使用。使用。5. 当所有的终止标准被满足后生长过程停止。当所有的终止标准被满足后生长过程停止。混杂度的几个测度混杂度的几个测度 目标变量是类别变量（名义）目标变量是类别变量（名义） 基尼指数（基尼指数（ Gini Index） 二分指数二分指数 （Twoing Index）目标变量是类别变量（有序）目标变量是类别变量（有序） 有序二分指数（有序二分指数（Ordered Twoing）目标变量是连续变量目标变量是连续变
5、量 最小平方偏差（最小平方偏差（Least-Squared Deviation）混杂度：基尼指数混杂度：基尼指数如果一个数据集合如果一个数据集合T的观测记录里包括的观测记录里包括n个类别，基尼指数的定义如下：个类别，基尼指数的定义如下： 其中其中 是节点是节点t的类别的类别j的相对比例的相对比例混杂度：基尼指数混杂度：基尼指数如果一个数据集合如果一个数据集合T被划分为两个子集合被划分为两个子集合T1和和T2，对应的记录数量分别是，对应的记录数量分别是N1和和N2 ，划，划分分(split)的基尼指数被定义为：的基尼指数被定义为：实际上，这是两个子集的基尼指数的加权实际上，这是两个子集的基尼指数
6、的加权平均值平均值混杂度：基尼指数混杂度：基尼指数基尼指数的最大值是基尼指数的最大值是1-1/k，在此，在此k是类别的是类别的数量。当观测记录在数量。当观测记录在k个类别上平均分布时个类别上平均分布时基尼指数就会最大基尼指数就会最大基尼指数的最小值的基尼指数的最小值的0，这是当所有的观测，这是当所有的观测记录都属于某一个类别时会发生的情况记录都属于某一个类别时会发生的情况混杂度：基尼指数混杂度：基尼指数一个分类成功的输入变量会把观测记录中一个分类成功的输入变量会把观测记录中的某一个类别在节点中占多数的某一个类别在节点中占多数输入变量在这方面越成功，从根节点到子输入变量在这方面越成功，从根节点到
7、子节点的基尼指数的变化量就越大节点的基尼指数的变化量就越大基尼指数的变化量基尼指数的变化量对于划分对于划分s，在节点，在节点t，基尼指数的变化量可，基尼指数的变化量可以按以下公式计算：以按以下公式计算：能实现最大变化量的划分能实现最大变化量的划分s（即在某输入变（即在某输入变量某个值上把节点里观测记录划分到两个量某个值上把节点里观测记录划分到两个子节点）将被选用子节点）将被选用关于混杂度示例关于混杂度示例后面的个片子由后面的个片子由Dr. Hyunjoong Kim, Dept of Statistics, University of Tennessee制作制作混杂度测量：基尼指数混杂度测量：
8、基尼指数一个划分数据混杂度划分的优度划分的优度基尼指数的变化量：基尼指数的变化量：另一个划分数据混杂度是更好的划分基尼指数的广义公式基尼指数的广义公式 其中 C(i|j)=把类别j的记录分类到类别i的错误分类代价 (j)=类别j的先验值基尼指数划分的特点基尼指数划分的特点 基尼指数关注的目标变量里面最大的类，它基尼指数关注的目标变量里面最大的类，它试图找到一个划分把它和其它类别区分开试图找到一个划分把它和其它类别区分开来。来。 完美的系列划分将会得到完美的系列划分将会得到k个纯粹的子节点，个纯粹的子节点，每一个节点对应目标变量的一个类别。每一个节点对应目标变量的一个类别。 如果误分类代价因素被
9、加入，基尼指数试图如果误分类代价因素被加入，基尼指数试图把代价最大的类别区分开来。把代价最大的类别区分开来。二分指数划分的特点二分指数划分的特点二分指数首先把目标变量的几个类别划分为二分指数首先把目标变量的几个类别划分为2个超类别（或群），每个群加起来接近数个超类别（或群），每个群加起来接近数据的一半。据的一半。二分指数然后搜寻把这两个超级群分成子节二分指数然后搜寻把这两个超级群分成子节点的划分。点的划分。二分指数的划分方法二分指数的划分方法对于在节点对于在节点t的划分的划分s，二分指数的改进量为：，二分指数的改进量为：产生两个子节点间最大差异的划分产生两个子节点间最大差异的划分s被选择。被选
10、择。基尼指数对二分指数基尼指数对二分指数 当目标变量的类别数很小时，当目标变量的类别数很小时，2 to 4，使用，使用基尼指数。基尼指数。当目标变量的类别数较大时，当目标变量的类别数较大时，4以上，使用以上，使用二分指数。二分指数。 注意当使用二分指标时，误分类代价因素不注意当使用二分指标时，误分类代价因素不能使用。能使用。CART 终止条件终止条件 一个节点中的所有记录其预测变量值相同一个节点中的所有记录其预测变量值相同 树的深度达到了预先指定的最大值树的深度达到了预先指定的最大值 节点的记录量小于预先指定的最小节点记录量节点的记录量小于预先指定的最小节点记录量 节点是纯节点，即所有的记录的
11、目标变量值相同节点是纯节点，即所有的记录的目标变量值相同 混杂度的最大下降值小于一个预先指定的值混杂度的最大下降值小于一个预先指定的值剪枝剪枝 在终止条件被满足，划分停止之后，下一步在终止条件被满足，划分停止之后，下一步是剪枝：是剪枝： 给树剪枝就是剪掉给树剪枝就是剪掉“弱枝弱枝”，弱枝指，弱枝指的是在验证数据上误分类率高的树枝的是在验证数据上误分类率高的树枝 为树剪枝会增加训练数据上的错误分类为树剪枝会增加训练数据上的错误分类率，但精简的树会提高新记录上的预测能率，但精简的树会提高新记录上的预测能力力 剪掉的是最没有预测能力的枝剪掉的是最没有预测能力的枝CART对缺失值的处理对缺失值的处理
12、一个代理划分将被用于处理预测变量中的缺一个代理划分将被用于处理预测变量中的缺失值失值 假定假定X* 是节点是节点t的最佳划分的最佳划分s*所在的预测输所在的预测输入变量，代理划分入变量，代理划分s使用另外一个输入变量使用另外一个输入变量X，s在在t节点的划分效果最接近节点的划分效果最接近s*。CART对缺失值的处理对缺失值的处理如果要预测一个新记录的目标变量值，它在如果要预测一个新记录的目标变量值，它在节点节点t的的X*对应的输入变量上有缺失值，预对应的输入变量上有缺失值，预测将使用代理划分测将使用代理划分s如果该新记录在如果该新记录在X变量上变量上没有缺失值没有缺失值模型和评价模型和评价 一旦树被生成，其预测值可以被评价如下一旦树被生成，其预测值可以被评价如下 对名义和有序目标变量对名义和有序目标变量: 每一个节点为节点里的所有记录安排一个预每一个节点为节点里的所有记录安排一个预测类别测类别 模型优劣根据所有误分类记录的比率判断模型优劣根据所有误分类记录的比率判断
