分类与回归树算法(CART)
分类与回归
分类 ——划分离散变量
回归——划分连续变量
什么是CART
分类与回归树
welcome to use these PowerPoint templates, New CART 采用一种二分递归分割的技术，将当前 Content design, 10 years experience 的样本集分为两个子样本集，使得生成的决
对记录的值从小到大排序，计算每个值作为临界点 产生的子节点的异质性统计量。能够使异质性减小程 度最大的临界值便是最佳的划分点。
分类型变量
列出划分为两个子集的所有可能组合，计算每种组合下 生成子节点的异质性。同样，找到使异质性减小程度最大 的组合作为最佳划分点。
有房 无房 否 是 3 0 4 3
Gini(t1)=1-(3/3)²-(0/3)²=0 Gini(t2)=1-(4/7)²-(3/7)²=0.4849 Gini=0.3×0+0.7×0.4898=0.343
单身或离异 已婚 Gini(t1)=1-(3/6)²-(3/6)²=0.5 3 4 Gini(t2)=1-(4/4)²-(0/4)²=0 否 3 0 Gini=6/10×0.5+4/10×0=0.3 是
离异或已婚 单身 Gini(t1)=1-(5/6)²-(1/6)²=0.2778 5 2 Gini(t2)=1-(2/4)²-(2/4)²=0.5 否 1 2 Gini=6/10×0.2778+4/10×0.5=0.3667 是
• 2）表面覆盖为鳞片和非鳞片 • 3）体温为恒温和非恒温 等等产生当前节点的左右两个孩子。 按哪种划分最好呢？
有3个标准可以用来衡量划分的好坏：GINI指数、双 化指数、有序双化指数。
• 体温为非恒温时包含爬行类3个、鱼类3个、两栖 类2个,则
• 体温为非恒温时包含爬行类3个、鱼类3个、两栖 类2个,则
j
2
p( j t ) 是结点t中样本输出取类别j的概率
最大值：(1 - 1/nc)，记录在所有类中等分布 最小值：0，所有记录属于同一个类
如何划分训练记录
如何表示测试条件
根据属性类型的不同： 标称属性 序数属性 连续属性 根据分割的数量 二元划分 多元化分
选择最佳分割点数值型变量Fra bibliotek决策树
如何划分训练记录？ 如何表示属性测试条件？ 如何确定最佳划分？ 如何构建测试条件效果最好的树？
如何确定最佳划分
贪婪法：根据子女结点类分布的一致性程度来 选择最佳划分 度量结点的不纯度 Gini 熵 误分类误差
不纯度度量——GINI
对于一个给定的结点t：
GINI (t ) 1 [ p( j t )]
如何确定叶子节点的类？
• 前面提到Tree-Growth终止的方式有2种，对于第 一种方式，叶子节点覆盖的样本都属于同一类， 那么这种情况下叶子节点的类自然不必多言。对 于第二种方式，叶子节点覆盖的样本未必属于同 一类，直接一点的方法就是，该叶子节点所覆盖 的样本哪个类占大多数，那么该叶子节点的类别 就是那个占大多数的类。
是 否
100 120 125 220 55 65 72 80 87 92 97 110 122 172 230 ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > 0 3 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0 3 0 0 7 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1 7 0
策树的每个非叶子节点都有两个分支。
CART算法生成的决策树是结构简洁的二叉树。
• 分类回归树是一棵二叉树，且每个非叶子节点都 有两个孩子，所以对于第一棵子树其叶子节点数 比非叶子节点数多1。
上例属性有8个，每个属性又有多少离散的值可取。 在决策树的每一个节点上我们可以按任一个属性的 任一个值进行划分。比如最开始我们按： • 1）表面覆盖为毛发和非毛发
节点达到完全纯度
树的深度达到用户所要的深度
节点中样本个数少于用户指定个数
异质性指标下降的最大幅度小于用户指定的幅度
决策树(Hunt算法)
有房者 拖欠贷款者=否 是 拖欠贷款者=是 否 拖欠贷款者=否
有房者 是 拖欠贷款者=否 单身 离异 年收入 <80K 拖欠贷款者=否 否 婚姻状况 是 已婚 拖欠贷款者=否 拖欠贷款者=否 ≥80K 拖欠贷款者=是 单身 离异 拖欠贷款者=是 婚姻状况 已婚 拖欠贷款者=否 有房者 否
单身 已婚 离异 Gini(t1)=1-(2/4)²-(2/4)²=0.5 Gini(t2)=1-(0/4)²-(4/4)²=0 4 1 Gini(t3)=1-(1/2)²-(1/2)²=0.5 否 2 0 1 Gini=4/10×0.5+4/10×0+2/10×0.5=0.3 是 2
单身或已婚 离异 Gini(t1)=1-(6/8)²-(2/8)²=0.375 6 1 Gini(t2)=1-(1/2)²-(1/2)²=0.5 否 2 1 Gini=8/10×0.375+2/10×0.5=0.4 是
分险
收益
利润
Thank you!
剪枝
当分类回归树划分得太细时，会对噪声数据产 生过拟合作用。因此我们要通过剪枝来解决
前剪枝：停止生长策略
后剪枝：在允许决策树得到最充分生长的基础上， 再根据一定的规则，自下而上逐层进行剪枝。
剪枝方法
2
最小误差剪枝
代价复杂性
1
悲观误差剪枝
3
代价复杂性剪枝
模型评价
减少在冒险因素或损失因素方面的不确定性。 不仅包括不同模型的比较，而且还要对模型产 生结果的商业价值进行比较。模型评价的角度 有：
60
70
75
85
90
95
Gini 0.420 0.400 0.375 0.343 0.417 0.400 0.300 0.343 0.375 0.400 0.420
测试条件效果
• 为确定测试条件划分，比较父节点（划分前）的 不纯度和子女结点的不纯度，差越大测试效果就 越好
•
不变值
决策树停止生长条件
• 所以如果按照“体温为恒温和非恒温”进行划分 的话，我们得到GINI的增益（类比信息增益）：
• 最好的划分就是使得GINI_Gain最小的划分。
终止条件
• 一个节点产生左右孩子后，递归地对左右孩子进行 划分即可产生分类回归树。这里的终止条件是什么 ？什么时候节点就可以停止分裂了？直观的情况， 当节点包含的数据记录都属于同一个类别时就可以 终止分裂了。这只是一个特例，更一般的情况我们 计算χ2值来判断分类条件和类别的相关程度，当χ2 很小时说明分类条件和类别是独立的，即按照该分 类条件进行分类是没有道理的，此时节点停止分裂 。注意这里的“分类条件”是指按照GINI_Gain最 小原则得到的“分类条件”。