第5章 数据分类 决策树解析课件.ppt

2022/12/11,1,数据仓库与数据挖掘技术,五邑大学信息学院 2009.06,何国辉 教授,2022/12/11,2,第5章 决策树和决策规则 ,5.1 引例,分类的定义分类是指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类。,2022/12/11,3,描述属性,类别属性,分类问题使用的数据集格式：,2022/12/11,4,5.1 引例,分类问题使用的数据集格式描述属性可以是连续型属性，也可以是离散型属性；而类别属性必须是离散型属性。 连续型属性是指在某一个区间或者无穷区间内该属性的取值是连续的 ，例如属性“Age” 离散型属性是指该属性的取值是不连续的 ，例如属性“Salary”和“Class”,2022/12/11,5,5.1 引例,分类问题使用的数据集格式分类问题中使用的数据集可以表示为X=(xi,yi)|i=1,2,totalxi=(xi1,xi2,xid) ，其中xi1,xi2,xid分别对应d个描述属性A1,A2,Ad的具体取值yi表示数据样本xi的类标号，假设给定数据集包含m个类别，则yic1,c2,cm，其中c1,c2,cm是类别属性C的具体取值未知类标号的数据样本x用d维特征向量x=(x1,x2,xd)来表示,2022/12/11,6,5.2 分类问题概述,5.2.1 分类的过程5.2.2 分类的评价准则,2022/12/11,7,5.2.1 分类的过程,2022/12/11,8,5.2.1 分类的过程,获取数据输入数据、对数据进行量化预处理去除噪声数据、对空缺值进行处理数据集成或者变换 分类器设计划分数据集、分类器构造、分类器测试分类决策对未知类标号的数据样本进行分类,2022/12/11,9,5.2.2 分类的评价准则,给定测试集Xtest=(xi,yi)|i=1,2,NN表示测试集中的样本个数xi表示测试集中的数据样本yi表示数据样本xi的类标号对于测试集的第j个类别，假设被正确分类的样本数量为TPj被错误分类的样本数量为FNj其他类别被错误分类为该类的样本数据量为FPj,2022/12/11,10,5.2.2 分类的评价准则,精确度：代表测试集中被正确分类的数据样本所占的比例,2022/12/11,11,5.2.2 分类的评价准则,查全率：表示在本类样本中被正确分类的样本所占的比例 查准率：表示被分类为该类的样本中，真正属于该类的样本所占的比例,2022/12/11,12,5.2.2 分类的评价准则,F-measure(加权调合平均数)：是查全率和查准率的组合表达式 是可以调节的，通常取值为1,2022/12/11,13,5.2.2 分类的评价准则,几何均值 ：是各个类别的查全率的平方根,2022/12/11,14,决策树方法的起源是亨特（Hunt，1966）的概念学习系统CLS方法，然后发展到由Quinlan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一个优点是它能够处理连续属性。还有CART算法和Assistant算法也是比较有名的决策树方法。,5.3 决策树,2022/12/11,15,决策树的优点：进行分类器设计时，决策树分类方法所需时间相对较少决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式可以将决策树中到达每个叶节点的路径转换为IFTHEN形式的分类规则，这种形式更有利于理解,2022/12/11,16,1. 什么是决策树决策树（Decision Tree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internal node）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（leaf）代表某个类（class）或者类的分布（class distribution），最上面的结点是根结点。决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。下例是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结点。,2022/12/11,17,例图5-2 给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买PC（buys_computer）的知识，用它可以预测某条记录（某个人）的购买意向。,图5-2 buys_computer的决策树,2022/12/11,18,这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机“buys_computer”。每个内部结点（方形框）代表对某个属性的一次检测。每个叶结点（椭圆框）代表一个类：buys_computers=yes 或者 buys_computers=no在这个例子中，样本向量为： （age, student, credit_rating; buys_computers）被决策数据的格式为:（age, student, credit_rating）输入新的被决策的记录，可以预测该记录隶属于哪个类。,2022/12/11,19,2. 使用决策树进行分类 构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。 决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为(a = b)的逻辑判断，其中a 是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。,2022/12/11,20,使用决策树进行分类分为两步：第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。,2022/12/11,21,问题的关键是建立一棵决策树。这个过程通常分为两个阶段：建树（Tree Building）：决策树建树算法见下，这是一个递归的过程，最终将得到一棵树。剪枝（Tree Pruning）：剪枝的目的是降低由于训练集存在噪声而产生的起伏。,2022/12/11,22,由Quinlan在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法。ID3即决策树归纳（Induction of Decision Tree）。早期的ID算法只能就两类数据进行挖掘（如正类和反类）；经过改进后，现在ID算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、一致的，也就是说，对具有相同属性的数据，其对应的类必须是唯一的。在ID3算法挖掘后，分类规则由决策树来表示。,5.4 分类规则挖掘的ID3算法,2022/12/11,23,1. ID3算法的基本思想 由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间，该搜索空间是针对某一特定问题而提出的。系统根据某个评价函数决定搜索空间中的哪一个决策树是“最好”的。评价函数一般依据分类的准确度和树的大小来决定决策树的质量。如果两棵决策树都能准确地在测试集进行分类，则选择较简单的那棵。相对而言，决策树越简单，则它对未知数据的预测性能越佳。寻找一棵“最好”的决策树是一个NP完全问题。,NP完全问题是这样的问题：用确定性的算法在多项式时间内无法解决的问题。实际之中，解决这样的问题，往往是根据用启发式算法，求出近似的解。,2022/12/11,24,ID3使用一种自顶向下的方法在部分搜索空间创建决策树，同时保证找到一棵简单的决策树可能不是最简单的。ID3算法的基本思想描述如下：step 1任意选取一个属性作为决策树的根结点，然后就这个属性所有的取值创建树的分支；step 2用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类为标记标识此叶结点；如果所有的叶结点都有类标记，则算法终止；step 3否则，选取一个从该结点到根路径中没有出现过的属性为标记标识该结点，然后就这个属性所有的取值继续创建树的分支；重复算法步骤step 2；,2022/12/11,25,这个算法一定可以创建一棵基于训练数据集的正确的决策树，然而，这棵决策树不一定是简单的。显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。在ID3算法中，采用了一种基于信息的启发式的方法来决定如何选取属性。启发式方法选取具有最高信息量的属性，也就是说，生成最少分支决策树的那个属性。,2022/12/11,26,算法：Generate_decision_tree由给定的训练数据产生一棵决策树输入：训练数据集samples，用离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树方法：（1）创建结点N；（2）if samples 都在同一个类C then（3）返回N作为叶结点，用类C标记；（4）if attribute_list 为空 then （5）返回N作为叶结点，标记samples中最普通的类； /多数表决（6）选择attribute_list中具有最高信息增益的属性test_attribute； /用信息增益作为属性选择度量（7）标记结点N为test_attribute；（8）for each test_attribute中的已知值ai /划分samples（9）由结点N生长出一个条件为test_attributeai的分枝；（10）设si为samples中test_attributeai的样本集合；/一个划分（11）if si为空 then（12）加上一个叶结点，标记为标记samples中最普通的类； /多数表决（13）else 加上一个由Generate_decision_tree（si, attribute_list-test_attribute）返回的结点；,2022/12/11,27,2. 属性选择度量在Generate_decision_tree算法的Step 6，算法需选择attribute_list中具有最高信息增益的属性test_attribute。ID3算法在树的每个结点上以信息增益（information gain）作为度量来选择测试属性。这种度量称为属性选择度量或分裂的优良性度量。选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需要的信息量最小，并确保找到一棵简单的（但不一定是最简单的）决策树。,2022/12/11,28,Information Gain指标的原理来自于信息论。1948年，香农（C. E. Shannon）提出了信息论。其中给出了关于信息量（Information）和熵（Entropy）的定义，熵实际上是系统信息量的加权平均，也就是系统的平均信息量。,2022/12/11,29,假设要选择有n个输出（所给属性的n个值）的检验，把训练样本集T分区成子集T1，T2，Tn。仅有的指导信息是在T和它的子集Ti中的类的分布。如果S是任意样本集，设freq(Ci,S)代表S中属于类Ci （k个可能的类中的一个）的样本数量， |S| 表示集合S中的样本数量。下面给出了集合S（单位为比特）的熵计算：,以2为底的原因是：信息按二进制位编码,2022/12/11,30,熵是一个衡量系统混乱程度的统计量。熵越大，表示系统越混乱。分类的目的是提取系统信息，使系统向更加有序、有规则组织的方向发展。所以最佳的分裂方案是使熵减少量最大的分裂方案。熵减少量就是Information Gain（信息增益），所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，这个最佳方案是用“贪心算法+深度优先搜索”得到的。,2022/12/11,31,现在考虑T被分区之后的一个相似度量标准，T按照一个属性检验X的几个输出进行分区。所需信息可通过这些子集的熵的加权和求得：,信息增益的计算公式：Gain(X) = Info(T) - Info x(T)通过计算求出具有最高增益的属性。,2022/12/11,32,以下分析有关度量标准的应用和创建决策树的一个简单例子，假设以平面文件形式给出的数据集T，其中有14个样本，通过3个输入属性描述且属于所给的两个类之一：类1或类2。,2022/12/11,33,2022/12/11,34,其中：9个样本属于类1，5个样本属于类2，因此分区前的熵为：info(T) -9/14.log2(9/14) -5/14.log2(5/14) = 0.940比特根据属性1把初始样本集分区成3个子集（检验x1表示从3个值A，B或C中选择其一）后，得出结果：Info x1(T)5/14（-2/5 log2(2/5) -3/5 log2(3/5) ）+ 4/14（-4/4 log2(4/4) -0/4 log2(0/4) ）+ 5/14（-3/5 log2(3/5) -2/5 log2(2/5) ）=0.694比特通过检验x1获得的信息增益是：Gain(x1) = 0.940 0.694 = 0.246比特,2022/12/11,35,如果该检验和分区是基于属性3的（检验x2表示从真或假两个值选择其一），类似地有：Info x2(T)6/14（-3/6 log2(3/6) -3/6 log2(3/6) ）+ 8/14（-6/8 log2(6/8) -2/8 log2(2/8) ）=0.892比特通过检验x2获得的增益是：Gain(x2) = 0.940 0.892 = 0.048比特按照增益准则，将选择x1作为分区数据库T的最初检验。为了求得最优检验还必须分析关于属性2的检验，它是连续取值的数值型属性。,2022/12/11,36,3. ID3算法的改进（1）离散化 为了解决该问题，在用ID3算法挖掘具有连续性属性的知识时，应该首先把该连续性属性离散化。最简单的方法就是把属性值分成 和 两段。如身高可以分为1米以下，1米以上或者分为1.5米以下，1.5米以上。如何选择最佳的分段值呢？对任何一个属性，其所有的取值在一个数据集中是有限的。假设该属性取值为，则在这个集合中，一共存在m-1个分段值，ID3算法采用计算信息量的方法计算最佳的分段值，然后进一步构建决策树。 ID3算法的扩展是C4.5算法， C4.5算法把分类范围从分类属性扩展到数字属性。,2022/12/11,37,1. C4.5算法概述C4.5算法是ID3算法的扩展，它的改进部分是：能够处理连续型的属性。首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个属性Gian值的大小。缺失数据的考虑：在构建决策树时，可以简单地忽略缺失数据，即在计算增益时，仅考虑具有属性值的记录。提供两种基本的剪枝策略：子树替代法：用叶结点替代子树。子树上升法：用一棵子树中最常用的子树来代替这棵子树。,5.5 分类规则挖掘的C4.5 算法,剪枝目的是降低由于训练集存在噪声而产生的起伏。,2022/12/11,38,2. 离散化的方法把连续型属性值离散化的具体方法是：1） 寻找该连续型属性的最小值，并把它赋值给MIN，寻找该连续型属性的最大值，并把它赋值给MAX；2） 设置区间 MIN，MAX 中的N个等分断点Ai，它们分别是 Ai = MIN + （MAX MIN）/ N）* i其中，i = 1 , 2 , . , N3） 分别计算把MIN，Ai和（Ai，MAX）（i = 1 ,2 , . , N）作为区间值时的Gain值，并进行比较。4）选取Gain值最大的Ak做为该连续型属性的断点，把属性值设置为MIN，Ak和（Ak，MAX）两个区间值。,2022/12/11,39,对于前面例子中的数据库T，分析属性2分区的可能结果，分类后得出属性2的值的集合是：65,70,75,78,80,85,90,95,96按照C4.5算法，选择每个区间的最小值作为阈值，即：65,70,75,78,80,85,90,95共8个值，从中选取最优的阈值。按照前述方法选取两区间，并分别计算其Gain值：6570757880859095如以第二种分段为例计算，计算其Gain值：,2022/12/11,40,2022/12/11,41,Info x2(T)4/14（-3/4 log2(3/4) -1/4 log2(1/4) ）+ 10/14（-6/10 log2(6/10) -4/10 log2(4/10) ） =比特Gain(x2) = 0.940 Info x2(T) = 比特,2022/12/11,42,找到最优的阈值（具有最高信息增益）Z=80相应的检验3（属性280)的信息增益计算为：Info x3(T)9/14（-7/9 log2(7/9) -2/9 log2(2/9) ）+ 5/14（-2/5 log2(2/5) -3/5 log2(3/5) ）=0.837比特通过检验x3获得的增益是：Gain(x3) = 0.940 0.837 = 0.103比特比较本例中3个属性的信息增益，可以看出属性1具有最高增益，选择该属性对决策树的结构进行首次分区。,2022/12/11,43,T1,检验X1:属性1=？,T2,T3,A,B,C,叶结点,2022/12/11,44,对于剩下的子结点T1、T3进行分析：对T1的属性进行检验：最优检验（具有最高的信息增益）有两个选择：属性270，定义为x4。Info (T1)-2/14 log2(2/5) -3/14 log2(3/5)=0.940比特用属性2把T1分成两个子集（检验x4），结果信息是：Info x4(T)2/5（-2/2 log2(2/2) -0/2 log2(0/2) ）+ 3/5（-0/3 log2(0/3) -3/3 log2(3/3) ）=0比特该检验的信息增益最大：Gain(x4) = 0.940 0 = 0.940比特这两个分枝将生成最终叶结点。,2022/12/11,45,对于剩下的子结点T3进行分析：对T3的属性进行检验：选择的最优检验为x5对属性3的值进行检验，树的分枝是属性3=真和属性3=假。最终决策树为：,2022/12/11,46,决策树可以用伪代码的形式表示，这种伪代码用IF-THEN结构对决策树进行分枝。,If 属性1 = Athen if 属性2=70then 类别 = 类1;else 类别 = 类2;Else if 属性1 = B then类别 = 类1;else if 属性1 = C thenif 属性3 = 真 then类别 = 类2;else类别 = 类1.,结果,2022/12/11,47,增益标准对紧凑型决策树的构造有很好的效果，但也存在一个严重缺陷：对具有多输出的检验有严重的偏差。解决方法：根据info(S)的定义，指定一个附加的参数：,含义：通过把集T分区成n个子集Ti而生成的潜在信息。新的增益标准-增益率：Gain_ratio(X) = Gain(X)/ Split_Info (X),新的增益标准表示分区所生成的有用信息的比例,2022/12/11,48,根据前面实例，求检验X1的增益比例。计算Split_Info (X1)Split_Info (X1)-5/14 log2(5/14) -4/14 log2(4/14) -5/14 log2(5/14) =1.577比特计算Gain_ratio(X1)Gain_ratio(X1) = 0.246/1.577 = 0.156检验过程，将采用最大增益率代替增益标准值,2022/12/11,49,在实际应用过程中，大量的现实世界中的数据都不是以人的意愿来定的，可能某些字段上缺值（missing values）；可能数据不准确含有噪声或者是错误的；可能是缺少必须的数据造成了数据的不完整。 解决丢失值问题有两种选择：抛弃数据库中有丢失数据的样本。定义一个新的算法或改进现有的算法来处理。,3. 未知属性值问题,如存在大量丢失数据?,2022/12/11,50,按照第二种选择，必须回答几个问题：怎样比较具有不同数目未知值的两个样本？具有未知值的训练样本和检验的具体值之间没有联系，它们不能被分配给任何子集，该如何处理这些样本？在分类的检验阶段，如果检验有丢失值的属性时，该怎样处理丢失值？C4.5算法中：有未知值的样本是按照已知值的相对频率随机分布的。除考虑到仅有的几个有已知属性值的样本以外用系数F修正增益参数F=数据库中一个给出的属性值具有已知值的样本数量/数据集中样本数量总和,通过一些方法补充数据？,2022/12/11,51,新的增益标准：Gain(X) = F*(info(T) infox(T)同时，通过把具有未知值的样本看作分区的一个附加组来修改Split_Info (X)。如果检验x有n个输出， Split_Info (X)按照检验把数据集分区成n + 1个子集计算。该值Split_Info (X)对修改后的标准Gain_ratio(X)的最终值有直接影响。,2022/12/11,52,2022/12/11,53,属性1的增益计算考虑13个数据，丢失的样本仅用来作修正，属性1中有8个属于类1，5个属于类2，因此分区前的熵为：Info (T)-8/13 log2(8/13) -5/13 log2(5/13)=0.961比特用属性1把T分区成3个子集（A、B、C）后，得到的信息是：Info x1(T)5/13（-2/5 log2(2/5) -3/5 log2(3/5) ）+ 3/13（-3/3 log2(3/3) -0/3 log2(0/3) ）+ 5/13（-3/5 log2(3/5) -2/5 log2(2/5) ）=0.747比特用系数F进行修正得：Gain(X1) = 13/14（0.961 0.747）= 0.199比特,原来为0.246比特,2022/12/11,54,考虑未知值的影响：Split_Info (X1)-5/13 log2(5/13) -3/13 log2(3/13) -5/13log2(5/13) -1/13 log2(1/13) =1.876比特由Gain_ratio(X) = Gain(X)/ Split_Info (X)计算，则：Gain_ratio(X) = 0.199/1.876=0.106同时，每个样本都有一个相关的新参数，即概率：当一个值已知的样本从T分配给Ti时，它属于Ti的概率是1，属于其它所有子集的概率是0；当一个值是未知的，只能得出不稳定的概率描述。,作为单独一组,2022/12/11,55,用属性1的检验X1把集T分区成子集后，丢失值的记录被表示在3个子集中。,T1：（属性1=A）,T2：（属性1=B）,T3：（属性1=C）,在子集中的权值,在C4.5中，|Ti|可以重新解释为子集Ti的所有权重w的和，而不再是集Ti中的元素数。,2022/12/11,56,因此有：|T1| = 5 + 5/13|T2| = 3 + 3/13|T3| = 5 + 5/13,2022/12/11,57,If 属性1 = Athen if 属性2=70then 类别 = 类1 （2.0/0）;else 类别 = 类2 （3.4/0.4）;Else if 属性1 = B then类别 = 类1 （3.2/0）;else if 属性1 = C thenif 属性3 = 真 then类别 = 类2 （2.4/0.4）;else类别 = 类1 （3.0/0）.,再把这些子集按属性2和属性3的检验进一步分区，最终得到的决策树如下左。因最终分类的不明确性，每个决策都用到|Ti|/E表示。 |Ti|是达到叶结点的部分样本和，E是属于除了指定类以外的类的样本数量。,其中：3.4/0.4的意思是3.4个部分训练样本达到叶结点，其中0.4（5/13）个并不属于分配给叶的类。,2022/12/11,58,剪枝常常利用统计学方法，去掉最不可靠、可能是噪音的一些枝条。提供两种基本的剪枝策略：子树替代法：用叶结点替代子树。子树上升法：用一棵子树中最常用的子树来代替这棵子树。结果：最终生成一个更简单、更容易理解的树,4. 修剪决策树（剪枝）,2022/12/11,59,（1）先剪枝（pre-pruning）在建树的过程中，如满足下列条件：Information Gain或者某些有效统计量达到某个预先设定的阈值时，结点不再继续分裂，内部结点成为一个叶结点。如果分区前后分类精度没有显著的不同，可用当前的点作为叶。由于决策在分区前提前做出，因此该方法也叫预剪枝。,2022/12/11,60,（2）后剪枝（pos-pruning）用所选的精度准则回头去除树的一些点。在构建完树之后做的决策，所以称之为后剪枝。当建树时的训练数据进入决策树并到达叶结点时，训练数据的class label与叶结点的class label不同，这时称为发生了分类错误。当树建好之后，对每个内部结点，算法通过每个枝条的出错率进行加权平均，计算如果不剪枝该结点的错误率。如果裁减能够降低错误率，那么该结点的所有儿子就被剪掉，而该结点成为一片叶。出错率用与训练集数据独立的测试数据校验。最终形成一棵错误率尽可能小的决策树。,2022/12/11,61,为了使决策树模型更易读，可以提取由决策树表示的分类规则，并以IFTHEN的形式表示。具体方法是：从根结点到叶结点的每一条路径创建一条分类规则，路径上的每一个“属性值”对为规则的前件（即IF部分）的一个合取项，叶结点为规则的后件（即THEN部分）。,5.6 生成决策规则,决策树,2022/12/11,62,例对于buys_computer的决策树可提取以下分类规则：,IF age40 AND credit_ratingexcellent THEN buys_computernoIF age40AND credit _ratingfair THEN buys_computeryes,2022/12/11,63,5.7 SQL Server 2005中的决策树应用,创建 Analysis Services 项目 创建数据源 创建数据源视图 创建决策树挖掘结构 设置决策树挖掘结构的相关参数 建立决策树挖掘模型 查看挖掘结果,2022/12/11,64,作业11、给出一个3维分类的样本的数据集X，表示如下：,用C4.5算法中的计算步骤构建一个决策树。,2022/12/11,65,作业22、给出一个训练数据集Y，表示如下：,A）求出属性A的最优阈值（根据最大增益）。B）求出属性B的最优阈值（根据最大增益）。C）求数据集Y的决策树。D）从决策树中导出决策规则。,