cart分类和回归树算法

CART 分类和回归树算法

主讲人: 贾娜

摘

要

一递归划分自变量空间 二用验证数据进行剪枝 三总结 四遗留问题

分类与回归树 (Classification And RegressionTrees,CART) 是一种产生二叉决策树的技术. 分类树与回归树下面有两个重要的思想: 第一个:递归地划分自变量空间的想法; 第二个:用验证数据进行剪枝的想法.

一递归划分自变量空间

递归划分用Y表示因变量(分类变量); 用X1,X2,…,XP表示自变量. 通过递归的方式把关于X的P维空间划分为 不重叠的矩形.

划分步骤: 首先: 一个自变量被选择,例如Xi和Xi的一个 值Si,若选择Si把P维空间分为两部分:一部 分包含的点都满足Xi<=Si;另一部分包含的 点满足Xi>Si. 其次: 再把上步中得到的两部分中的一个部 分,通过选择一个变量和该变量的划分值以 相似的方式再划分. 重复上述步骤,直至把整个X空间划分成的 每个小矩形都尽可能的是同构的.

例示递归划分的过程 例1(Johnson和Wichern) 乘式割草机制造商意欲发现一个把城市 中的家庭分成那些愿意购买乘式割草机和 不愿意购买的两类的方法。在这个城市的 家庭中随机抽取12个拥有者和12个非拥有 者的家庭作为样本。这些数据如表1所示。 这里的自变量是收入(X1)和草地面积 (X2)。类别变量Y有两个类别：拥有者 和非拥有者。表1

CART如何选择划分点? 对于一个变量划分点是一对连续变量值的中点. 例如: X1可能划分点是{38.1,45.3,50.1…,109.5}; X2可能划分点是{14.4,15.4,16.2…23}. 这些划分点按照能减少杂质的多少来分级. 杂质度量方法:Gini指标. 矩形A的Gini不纯度可定义为: 其中K=1,2,…C,来表示类, Pk是观测点中属于类K的比例.

选择草地面积变量X2=19做第一次分割,由(X1,X2) 组成的空间被分成X2<=19和X2>19的两个矩形.

选择收入变量X1=84.75

我们能看到递归划分是如何精炼候选矩形,使之变得更 纯的算法过程.最后阶段的递归分析如图5所示

这个方法被称为分类树的原因是每次划分都可 以描述为把一个节点分成两个后续节点. 第一次分裂表示为树的根节点的分支,如图6

树的前三次划分如图7

整个树如下图8

二用验证数据进行剪枝 CART过程中第二个关键的思想是用独立的验证 数据集对根据训练集生成的树进行剪枝. CART剪枝目的:生成一个具有最小错误的树. 为什么要剪枝呢? 因为: 1 在树生成过程中可能存在不能提高 分类纯度的划分节点. 2 存在过拟合训练数据.