搜索
分类和回归树（CART）李保坤老师西南财经大学统计学院本节内容提要•CART算法•关于混杂度--基尼指数--二分指数•剪枝•CART对缺失值的处理CART算法•分类和回归树（ClassificationandRegressionTrees，CART）•有时被写作C&RT•Breiman,L.,J.H.Friedman,R.A.Oshen,andC.J.Stone,1984.Classificationandregressiontrees.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.当所有的终止标准被满足后生长过程停止。混杂度的几个测度•目标变量是类别变量（名义）–基尼指数（GiniIndex）–二分指数（TwoingIndex）•目标变量是类别变量（有序）–有序二分指数（OrderedTwoing）•目标变量是连续变量–最小平方偏差（Least-SquaredDeviation）混杂度：基尼指数•如果一个数据集合T的观测记录里包括n个类别，基尼指数的定义如下：其中是节点t的类别j的相对比例混杂度：基尼指数•如果一个数据集合T被划分为两个子集合T1和T2，对应的记录数量分别是N1和N2，划分(split)的基尼指数被定义为：•实际上，这是两个子集的基尼指数的加权平均值混杂度：基尼指数•基尼指数的最大值是1-1/k，在此k是类别的数量。当观测记录在k个类别上平均分布时基尼指数就会最大•基尼指数的最小值的0，这是当所有的观测记录都属于某一个类别时会发生的情况混杂度：基尼指数•一个分类成功的输入变量会把观测记录中的某一个类别在节点中占多数•输入变量在这方面越成功，从根节点到子节点的基尼指数的变化量就越大基尼指数的变化量•对于划分s，在节点t，基尼指数的变化量可以按以下公式计算：•能实现最大变化量的划分s（即在某输入变量某个值上把节点里观测记录划分到两个子节点）将被选用关于混杂度示例•后面的３个片子由Dr.HyunjoongKim,DeptofStatistics,UniversityofTennessee制作混杂度测量：基尼指数一个划分数据混杂度划分的优度基尼指数的变化量：另一个划分数据混杂度是更好的划分基尼指数的广义公式其中C(i|j)=把类别j的记录分类到类别i的错误分类代价π(j)=类别j的先验值基尼指数划分的特点•基尼指数关注的目标变量里面最大的类，它试图找到一个划分把它和其它类别区分开来。•完美的系列划分将会得到k个纯粹的子节点，每一个节点对应目标变量的一个类别。•如果误分类代价因素被加入，基尼指数试图把代价最大的类别区分开来。二分指数划分的特点•二分指数首先把目标变量的几个类别划分为2个超类别（或群），每个群加起来接近数据的一半。•二分指数然后搜寻把这两个超级群分成子节点的划分。二分指数的划分方法•对于在节点t的划分s，二分指数的改进量为：•产生两个子节点间最大差异的划分s被选择。基尼指数对二分指数•当目标变量的类别数很小时，2to4，使用基尼指数。•当目标变量的类别数较大时，4以上，使用二分指数。•注意当使用二分指标时，误分类代价因素不能使用。CART终止条件•一个节点中的所有记录其预测变量值相同•树的深度达到了预先指定的最大值•节点的记录量小于预先指定的最小节点记录量•节点是纯节点，即所有的记录的目标变量值相同•混杂度的最大下降值小于一个预先指定的值剪枝•在终止条件被满足，划分停止之后，下一步是剪枝：–给树剪枝就是剪掉“弱枝”，弱枝指的是在验证数据上误分类率高的树枝–为树剪枝会增加训练数据上的错误分类率，但精简的树会提高新记录上的预测能力–剪掉的是最没有预测能力的枝CART对缺失值的处理•一个代理划分将被用于处理预测变量中的缺失值•假定X*是节点t的最佳划分s*所在的预测输入变量，代理划分s使用另外一个输入变量X，s在t节点的划分效果最接近s*。CART对缺失值的处理•如果要预测一个新记录的目标变量值，它在节点t的X*对应的输入变量上有缺失值，预测将使用代理划分s如果该新记录在X变量上没有缺失值模型和评价•一旦树被生成，其预测值可以被评价如下–对名义和有序目标变量:•每一个节点为节点里的所有记录安排一个预测类别•模型优劣根据所有误分类记录的比率判断