决策树与模型评价课件

《决策树与模型评价课件》由会员分享，可在线阅读，更多相关《决策树与模型评价课件（91页珍藏版）》请在金锄头文库上搜索。

1、数据挖掘 分类：基本概念、决策树与模型评价,分类：基本概念、决策树与模型评价,分类的是利用一个分类函数（分类模型、分类器），该模型能把数据库中的数据影射到给定类别中的一个。,分类,训练集：数据库中为建立模型而被分析的数据元组形成训练集。 训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。 一个具体样本的形式可为:( v1, v2, ., vn; c );其中vi表示属性值,c表示类别。 测试集：用于评估分类模型的准确率,数据分类一个两步过程 (1),第一步，建立一个模型，描述预定数据类集和概念集 假定每个元组属于一个预定义的类，由一个类标号属性确定 学习模型可以用分类规则、决策树或数

2、学公式的形式提供,数据分类一个两步过程 (2),第二步，使用模型，对将来的或未知的对象进行分类 首先评估模型的预测准确率 对每个测试样本，将已知的类标号和该样本的学习模型类预测比较 模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比 测试集要独立于训练样本集，否则会出现“过分适应数据”的情况 如果准确性能被接受，则分类规则就可用来对新数据进行分类,有监督的学习 VS. 无监督的学习,有监督的学习（用于分类） 模型的学习在被告知每个训练样本属于哪个类的“监督”下进行 新数据使用训练数据集中得到的规则进行分类 无监督的学习（用于聚类） 每个训练样本的类编号是未知的，要学习的类集合或数量也

3、可能是事先未知的 通过一系列的度量、观察来建立数据中的类编号或进行聚类,分类模型的构造方法,1.机器学习方法： 决策树法 规则归纳 2.统计方法：知识表示是判别函数和原型事例 贝叶斯法 非参数法(近邻学习或基于事例的学习) 3.神经网络方法： BP算法,模型表示是前向反馈神经网络模型 4.粗糙集(rough set)知识表示是产生式规则,一个决策树的例子,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Splitting Attributes,训练数据,模型: 决策树,决策树的另一个例子,ca

4、tegorical,categorical,continuous,class,MarSt,Refund,TaxInc,YES,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,用决策树归纳分类,什么是决策树？ 类似于流程图的树结构 每个内部节点表示在一个属性上的测试 每个分枝代表一个测试输出 每个树叶节点代表类或类分布 决策树的生成由两个阶段组成 决策树构建 开始时，所有的训练样本都在根节点 递归的通过选定的属性，来划分样本 （必须是离散值） 树剪枝 许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝 决策树的使用：对未知样本进

5、行分类 通过将样本的属性值与决策树相比较,为了对未知数据对象进行分类识别，可以根据决策树的结构对数据集中的属性进行测试，从决策树的根节点到叶节点的一条路径就形成了相应对象的类别测试。决策树可以很容易转换为分类规则,决策树分类任务,Decision Tree,一个决策树的例子,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Splitting Attributes,训练数据,模型: 决策树,应用决策树进行分类,测试数据,Start from the root of tree.,应用决策树进行分类

6、,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,测试数据,应用决策树进行分类,Refund,MarSt,T

7、axInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,测试数据,Assign Cheat to “No”,决策树分类,Decision Tree,决策树,有许多决策树算法: Hunt算法 信息增益Information gain （ID3） 增益比率Gain ration（C4.5） 基尼指数Gini index (SLIQ，SPRINT),Hunt 算法,设 Dt 是与结点 t相关联的训练记录集 算法步骤: 如果Dt 中所有记录都属于同一个类 yt, 则t是叶结点，用yt标记 如果 Dt 中包含属于多个类的记录，则选择一个属

8、性测试条件，将记录划分成较小的子集。对于测试条件的每个输出，创建一个子结点，并根据测试结果将Dt中的记录分布到子结点中。然后，对于每个子结点，递归地调用该算法,Dt,?,Hunt算法,Dont Cheat,决策树,Hunt算法采用贪心策略构建决策树. 在选择划分数据的属性时，采取一系列局部最优决策来构造决策树. 决策树归纳的设计问题 如何分裂训练记录 怎样为不同类型的属性指定测试条件? 怎样评估每种测试条件? 如何停止分裂过程,决策树,Hunt算法采用贪心策略构建决策树. 在选择划分数据的属性时，采取一系列局部最优决策来构造决策树. 决策树归纳的设计问题 如何分裂训练记录 怎样为不同类型的属性

9、指定测试条件? 怎样评估每种测试条件? 如何停止分裂过程,怎样为不同类型的属性指定测试条件?,依赖于属性的类型 标称 序数 连续 依赖于划分的路数 2路划分 多路划分,基于标称属性的分裂,多路划分: 划分数（输出数）取决于该属性不同属性值的个数. 二元划分: 划分数为2，这种划分要考虑创建k个属性值的二元划分的所有2k-1-1种方法.,OR,多路划分: 划分数（输出数）取决于该属性不同属性值的个数. 二元划分: 划分数为2，需要保持序数属性值的有序性.,基于序数属性的划分,OR,基于连续属性的划分,多路划分:viAvi+1（i=1,k) 二元划分: (A v) or (A v) 考虑所有的划分

10、点，选择一个最佳划分点v,基于连续属性的划分,决策树,决策树归纳的设计问题 如何分裂训练记录 怎样为不同类型的属性指定测试条件? 怎样评估每种测试条件? 如何停止分裂过程,怎样选择最佳划分？,在划分前: 10 个记录 class 0, 10 个记录 class 1,怎样选择最佳划分？,选择最佳划分的度量通常是根据划分后子结点不纯性的程度。不纯性的程度越低，类分布就越倾斜 结点不纯性的度量:,不纯性大,不纯性小,怎样找到最佳划分？,B?,Yes,No,Node N3,Node N4,A?,Yes,No,Node N1,Node N2,划分前:,Gain = M0 M12 vs M0 M34,结点

11、不纯性的测量,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)

12、 = 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

13、* 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.,降低计算复杂性的方法,

14、将记录进行排序 从两个相邻的排过序的属性值之间选择中间值作为划分点 计算每个候选点的Gini值 时间复杂度为nlogn,定义：给定一个概率空间 事件,的自信息定义为 因,自信息反映了事件 发生所需要的信息量。 值越大说明需要越多的信息才能确定事件 的发生，其随机性也越大，而当 发生时所携带的信息量也越大。反过来， 值越小，需要较少信息量就能确定 的发生，即事件 随机性较小。当其发生时所携信息量就少。 是对不确定性大小的一种刻画,熵-定义,熵-定义,1.定义：在概率空间 上定义的随机变量 I( X)的数学期望,称为随机变量X的平均自信息，又称X的信息熵或熵记为H(x),非负性：H大于等于0 连续

15、性：H对任意q连续 极值性：当q都等于1K时 H达到最大值logK,熵-定义,基于 Information Gain的划分,给定结点t的 Entropy值计算 : (p( j | t) 是在结点t中，类j发生的概率). 当类分布均衡时， Entropy值达到最大值 (log nc) 相反当只有一个类时，Gini值达到最小值0 Entropy 与 GINI相似,计算 Entropy的例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Entropy = 0 log 0 1 log 1 = 0 0 = 0,P(C1) = 1/6 P(C2) = 5/6 Entropy = (1/6) log2 (1/6) (5/6) log2 (1/6) = 0.65,P(C1) = 2/6 P(C2) = 4/6 Entropy = (2/6) log2 (2/6) (4/6) log2 (4/6) = 0.92,基于 Information Gain的划分.,Information Gain: ni = 孩子结点 i的记录数, n = 结点 p的记录数. 在 ID3 and C4.5中使用,基于 Information Gain的划分.,增益率（Gain Ratio）: 熵和Gini指标等不纯性趋