第4章+分类：基本概念、决策树与模型评估.ppt

模型过分拟合和拟合不足 分类模型的误差大致分为两种： 训练误差：是在训练记录上误分类样本比例 泛化误差：是模型在未知记录上的期望误差 一个好的分类模型不仅要能够很好的拟合训练数据，而且对未知样本也要能准确分类。 换句话说，一个好的分类模型必须具有低训练误差和低泛化误差。 当训练数据拟合太好的模型，其泛化误差可能比具有较高训练误差的模型高，这种情况成为模型过分拟合 模型过分拟合和拟合不足 当决策树很小时，训练和检验误差都很大，这种情况称为模型拟合不足。出现拟合不足的原因是模型尚未学习到数据的真实结构。 随着决策树中结点数的增加，模型的训练误差和检验误差都会随之下降。 当树的规模变得太大时，即使训练误差还在继续降低，但是检验误差开始增大，导致模型过分拟合 模型模型过分拟合和拟合不足 过分拟合 导致过分拟合的原因 导致过分拟合的原因 噪声导致的过分拟合 例子：哺乳动物的分类问题 十个训练记录中有两个被错误标记：蝙蝠和鲸 如果完全拟合训练数据，决策树1的训练误差为0，但它在检验数据上的误差达30%.人和海豚，针鼹误分为非哺乳动物 相反，一个更简单的决策树2，具有较低的检验误差（10%），尽管它的训练误差较高，为20% 决策树1过分拟合了训练数据。因为属性测试条件4条腿具有欺骗性，它拟合了误标记的训练纪录，导致了对检验集中记录的误分类 噪声导致的过分拟合（例子） 噪声导致决策边界的改变 基于连续属性的划分 决策树 决策树归纳的设计问题 如何分裂训练记录 怎样为不同类型的属性指定测试条件? 怎样评估每种测试条件? 如何停止分裂过程 怎样选择最佳划分？ 在划分前: 10 个记录 class 0, 10 个记录 class 1 怎样选择最佳划分？ 选择最佳划分的度量通常是根据划分后子结点不纯性的程度。不纯性的程度越低，类分布就越倾斜 结点不纯性的度量: 不纯性大 不纯性小 怎样找到最佳划分？ B? Yes No Node N3 Node N4 A? Yes No Node N1 Node N2 划分前: M0 M1 M2 M3 M4 M12 M34 Gain = M0 – M12 vs M0 – M34 结点不纯性的测量 Gini Entropy classification error 不纯性的测量: GINI 给定结点t的Gini值计算 : (p( j | t) 是在结点t中，类j发生的概率). 当类分布均衡时，Gini值达到最大值 (1 - 1/nc) 相反当只有一个类时，Gini值达到最小值0 计算 GINI的例子 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Gini = 1 – P(C1)2 – P(C2)2 = 1 – 0 – 1 = 0 P(C1) = 1/6 P(C2) = 5/6 Gini = 1 – (1/6)2 – (5/6)2 = 0.278 P(C1) = 2/6 P(C2) = 4/6 Gini = 1 – (2/6)2 – (4/6)2 = 0.444 基于 GINI的划分 当一个结点 p 分割成 k 个部分 (孩子), 划分的质量可由下面公式计算 ni = 孩子结点 i的记录数, n = 父结点 p的记录数. 二元属性: 计算 GINI 对于二元属性，结点被划分成两个部分 得到的GINI值越小，这种划分越可行. B? Yes No Node N1 Node N2 Gini(N1) = 1 – (5/6)2 – (2/6)2 = 0.194 Gini(N2) = 1 – (1/6)2 – (4/6)2 = 0.528 Gini split= 7/12 * 0.194 +  5/12 * 0.528= 0.333 标称属性:计算Gini 多路划分 二元划分 一般多路划分的Gini值比二元划分小，这一结果并不奇怪，因为二元划分实际上合并了多路划分的某些输出，自然降低了子集的纯度 Multi-way split Two-way split (find best partition of values) 连续属性: 计算 Gini 使用二元划分 划分点v选择 N个记录中所有属性值作为划分点 对每个划分进行类计数, A v and A ? v 计算每个候选点v的Gini指标，并从中选择具有最小值的候选划分点 时间复杂度为(n2) 连续属性: 计算 Gini... 降低计算复杂性的方法, 将记录进行排序 从两个相邻的排过序的属性值之间选择中间值作为划分点 计算每个候选点的Gini值 时间复杂度为nlogn 划分点 排序后的值 定义：给定一个概率空间