{决策管理}chap4决策树

《{决策管理}chap4决策树》由会员分享，可在线阅读，更多相关《{决策管理}chap4决策树（58页珍藏版）》请在金锄头文库上搜索。

1、Data Mining 第四章,分类：基本概念、决策树和模型评估,4.1 预备知识4.2 解决分类问题的一般方法,分类例子,预测癌细胞是良性还是恶性 将信用卡交易分为合法和欺诈 ,分类：定义,给定一个记录集 每个记录包含一个属性集，通常最后一个属性是该记录的分类（class ）属性. 目标：找到一个模型（从其余属性值到分类属性的转换函数），实现对未知分类的记录进行尽可能精确地分类。 通常，将给定的数据集分为训练集（training set ）和检验集（test set ） 。训练集用来创建模型，检验集用来验证模型的有效性。 分类性能度量：,分类过程,分类技术,基于决策树的方法 Decision

2、 Tree based Methods 基于规则的方法 Rule-based Methods 基于记忆的推理 Memory based reasoning 神经网络 Neural Networks 朴素贝叶斯和贝叶斯信念网络 Nave Bayes and Bayesian Belief Networks 支持向量机 Support Vector Machines,决策树定义,决策树是由结点和有向边组成的层次结构。 树中包含三种结点： 根结点 内部结点 叶结点,非终结点。包含属性测试条件，用于分开不同特性的记录,每个叶结点都赋予一个类标号,决策树 例1,二元属性,分类属性,连续属性,分类标号,训

3、练数据,模型：决策树,决策树 例2,对于相同的数据，能构造多种不同的决策树,决策树应用过程：使用模型测试数据1,检验数据,从树根开始,使用模型测试数据2,Test Data,使用模型测试数据3,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Test Data,使用模型测试数据4,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Test Data,使用模型测试数据5,Refund,MarSt,

4、TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Test Data,使用模型测试数据6,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Test Data,将Cheat赋值为“No”,决策树构造算法,多种算法: Hunt 算法(最早方法之一) CART（ classification and regression trees） ID3, C4.5 SLIQ,SPRINT,Hunt 算法结构,Hunt算法的思想是将训练记

5、录相继划分成“较纯”的子集，以递归方式建立决策树。 假设t表示结点， Dt 表示与结点t相关联的训练记录集，y=y1,y2,yc是类标号 Hunt算法的递归定义: 如果Dt 中所有记录都属于同一个类yt, 则t就是叶子节点，并用yt标号 如果Dt 是一个空集，那么t就是叶子节点，其标号为其父结点上训练记录中的多数类,如果Dt 中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成若干个子集。并对每个子集进行递归分类。,例 P93P95 预测拖欠银行贷款的贷款者,如何生成决策树？,贪婪策略. 每次选择属性划分条件时，选择划分数据的最优标准. 决策树归纳的设计问题 问题1：如何分裂记录？ 1

6、.1定义属性测试条件给不同类型的属性指定测试条件的方法 1.2找到最好的划分方法对每种测试条件进行评估测量 问题2：何时停止分裂过程？,决策树归纳的设计问题1：1.1 定义属性测试条件,4.4.3 表示属性测试条件的方法 根据属性类型 标称型 Nominal 序数型 Ordinal 连续型 Continuous 按划分路数 二元划分 2-way split 多路划分 Multi-way split,标称属性的划分方法：(数据集见P122习题2),多路划分法: 划分成几个不同的值输出数取决于该属性不同属性值的个数. 二分法: 划分为两个不同的值. （需要找到最佳的划分方法）,OR,多路划分法 二

7、分法（分组必须保留属性值之间的序关系） 注意：第三种划分方法合理吗?,序数属性的划分方法：,OR,连续属性的划分方法,多路划分：离散化属性值，每个离散化区间赋予一个新的序数值 二分法： (A v) or (A v) 需要从所有可能的划分点中选择产生最佳划分的点,决策树归纳的设计问题1：1.2 找到最好划分方法,划分前: 数据集有20个记录，标号为class 0和class 1的各有10个。哪个划分测试条件最佳？,为了度量不同的测试条件，常用划分前和划分后记录的类分布定义： p(i|t)表示结点t中，属于类i的记录所占的比例，常简记为pi。 在二元分类问题中，任意结点的类分布可以记作(p0，p1

8、)，其中p1 =1- p0 。,选择最佳划分的度量,选择最佳划分的度量通常是根据划分后子女结点不纯性的程度：不纯的程度越低，类分布就越倾斜，划分就越好。,不同类，具有较高的不纯度,同类，具有较低的不纯度,结点不纯度的度量方法：,熵 Entropy 基尼指数 Gini Index 分类差错率 Classification error,计算不纯性方法1: 熵,结点t的熵: 其中，c为结点t中不同类标号个数 p( i | t)是给定结点t中属于类i的记录所占比例，简记为pi 结点熵值的取值范围： 当记录均匀分布于各分类时，将取得最大值(log nc) 当所有记录都属于同一分类时，将取得最小值(0),

9、例：分别计算3个结点的熵,P(C0) = 0/6 = 0 P(C1) = 6/6 = 1 Entropy = 0log 0 1log 1 = 0 0 = 0,P(C0) = 1/6 P(C1) = 5/6 Entropy = (1/6)log2 (1/6) (5/6)log2 (5/6) = 0.65,P(C0) = 2/6 P(C1) = 4/6 Entropy = (2/6)log2 (2/6) (4/6)log2 (4/6) = 0.92,练习1,已知：数据见课本表4-7（ P122 题2），采用熵作为结点的不纯度度量。 问题： 整个训练样本集的不纯度是多少？ 如果对数据按车型属性进行多

10、路划分，则 （车型=运动）的结点的不纯度是多少？ （车型=豪华）的结点的不纯度是多少？ （车型=家用）的结点的不纯度是多少？,计算不纯性方法2: 基尼指数（gini）,结点t的吉尼指数: 其中，c为结点t中不同类标号个数 p( i | t)是给定结点t中属于类i的记录所占比例，简记为pi 结点Gini指数的取值范围： 当记录均匀分布于各分类时，将取得最大值(1 - 1/nc) 当所有记录都属于同一分类时，将取得最小值(0),例：分别计算3个结点的Gini指数,P(C0) = 0/6 = 0 P(C1) = 6/6 = 1 Gini = 1 P(C0)2 P(C1)2 = 1 0 1 = 0,P

11、(C0) = 1/6 P(C1) = 5/6 Gini = 1 (1/6)2 (5/6)2 = 0.278,P(C0) = 2/6 P(C1) = 4/6 Gini = 1 (2/6)2 (4/6)2 = 0.444,练习2,已知：数据见课本表4-7（ P122 题2），采用Gini指数作为结点的不纯度度量。 问题： 整个训练样本集的不纯度是多少？ 如果对数据按车型属性进行多路划分，则 （车型=运动）的结点的不纯度是多少？ （车型=豪华）的结点的不纯度是多少？ （车型=家用）的结点的不纯度是多少？,计算不纯性方法3:分类差错率,节点t的分类差错率: p(i|t)是给定结点t中属于类i的记录所占

12、比例，简记为pi 结点分类误差率指数的取值范围： 当记录均匀分布于各分类时，将取得最大值(1 - 1/nc) 当所有记录都属于同一分类时，将取得最小值(0),例：分别计算3个子女结点的分类差错率,P(C0) = 0/6 = 0 P(C1) = 6/6 = 1 Error = 1 max (0, 1) = 1 1 = 0,P(C0) = 1/6 P(C1) = 5/6 Error = 1 max (1/6, 5/6) = 1 5/6 = 1/6,P(C0) = 2/6 P(C1) = 4/6 Error = 1 max (2/6, 4/6) = 1 4/6 = 1/3,练习3,已知：数据见课本表

13、4-7（ P122 题2），采用分类误差率作为结点的不纯度度量。 问题： 整个训练样本集的不纯度是多少？ 如果对数据按车型属性进行多路划分，则 （车型=运动）的结点的不纯度是多少？ （车型=豪华）的结点的不纯度是多少？ （车型=家用）的结点的不纯度是多少？,二元分类问题结点不纯性度量之间的比较：,利用不纯性度量，选择最佳划分,方法：分别比较父节点（划分前）的不纯程度和子女结点（划分后）的不纯程度，它们的差值越大，测试条件的效果就越好。 用增益来作为确定划分效果的标准 其中：I(.)是结点不纯性度量,N是父节点上的记录总数，k是父节点的分支数，N(vj)是子女结点vj的记录个数。,决策树归纳算法

14、，通常就是选择最大化增益的测试条件，作为当前节点的属性测试条件。,利用增益来选择最佳划分示意：,B?,Yes,No,Node N3,Node N4,A?,Yes,No,Node N1,Node N2,划分前,M父亲,比较增益: A(M父亲MA) vs. B(M父亲MB),计算不纯性,计算不纯性,计算不纯性,计算不纯性,加权平均,加权平均,练习4,已知：数据见课本表4-7（ P122 题2）。 问题(a)(g),熵和Gini指数等不纯度趋向有利于具有大量不同值的属性 产生大量输出测试条件，从而导致与每个划分关联的记录很少。 极端情况如：以顾客ID进行划分，比其他划分方法能得到更“纯”的派生结点,

15、改进方法,信息增益（熵差）: ni = 孩子节点i的记录数 n = 节点p的记录数 用于ID3和C4.5算法,增益率: 将父节点p划分为k部分 n表示p的记录数 ni 表示第i部分（p的第i个节点）的记录数 调整信息增益，引入划分信息SplitInfo，把属性测试条件产生的输出数也考虑进去。 如果一个属性产生了大量的划分，它的划分信息SplitInfo将会很大，从而增益率降低。 用于C4.5算法,比较不同类型的属性的划分（以Gini指数为例）,二元属性 标称属性 离散属性,基于GINI指数的二元属性划分方法,划分为两部分,B?,Yes,No,Node N1,Node N2,Gini(N1) =

16、 1 (5/7)2 (2/7)2 = 0.194 Gini(N2) = 1 (1/5)2 (4/5)2 = 0.528,Gini(Children) = 7/12 * 0.194 + 5/12 * 0.528= 0.333,基于GINI指数的标称属性划分方法,用矩阵帮助选择最佳划分,Multi-way split,Two-way split (find best partition of values),基于GINI指数的连续属性划分方法,问题：需要选择候选划分点 方法1:穷举法 将记录中所有的属性值作为候选划分点，计算每个候选的Gini指标，并从中选择具有最小值的候选划分点。 效率低 计算代价昂贵,改进方法：,根据划分属性，先对记录进行排序 从两个相邻的排过序的属性值中选择中间值作为候选划分点(55、65、72、80、）。在计算相邻结点时值，部分类分布保持不变，减少计算量。 进一步优化：仅仅考虑位于具有不同类标号的两个相邻记录之间的候选划分点（55