数据挖掘-决策树.ppt

第4章 决策树—分类和回归树 程春明 chengcm@ 2010.4 4.1 引言 分类树是使用树结构算法将数据分成离散类的方法。Breiman在20世纪80年代早期创造了该术语。该技术在医疗、市场调查统计、营销和顾客关系方面得到了很好的应用。 例如，一个树结构分类器使用血压、年龄和先前的治疗情况将心脏病患者分成危险和不危险两类。 另一种工具可能使用与年龄相关的变量和其他人口统计量决定谁应该出现在邮件发送清单上。 预测对直接邮寄广告的反应和确定控制电信业顾客流失的方法都是具体行业的应用。 决策树作用(1) 下表的数据提供了什么信息？ 决策树作用(2) 决策树的主要作用是揭示数据中的结构化信息。 决策树汇总了数据，并揭示了其中隐藏的结构： 准确率、支持度、错误率 该例得到的规则和对应的准确率和支持度是： 如果血压高，则采用药物A(准确率100％，支持度3／12)。 如果血压低，则采用药物B(准确率100％，支持度3／12)。 如果血压正常并且年龄小于或等于40，则采用药物A(准确率100％，支持度3／12)。 如果血压正常并且年龄大于40。则采用药物B(准确率100％，支持度3／12)。 树生长的策略 对于树生长的策略，算法主要考虑的问题： 选择分裂变量的标准。 找到被选择的变量的分裂点的标准(连续变量情况)。 确定何时停止树生长过程的标准。 决策树的分类 目标变量和预测变量 决策树根据目标变量的类型可分成分类树与回归树 如果目标变量(也称为响应变量或类变量)是标称／分类变量(如处方药)，则称该树为分类树(classification tree)。 如果目标变量是连续的(如“收入”)，则称该树为回归树(regression tree)。 预测变量分类 预测变量也可以一般地分为标称的或连续的。 连续值变量的处理，大部分实际算法在构造树之前先将连续值变量转换成具有离散层次(或区间)的变量。 4.2 构造分类树 4.2.1 用于标称属性的lD3算法 ID3代表归纳决策树(induction decision—tree)版本3，它是一种用来由数据构造决策树的递归过程。 lD3算法的步骤 试探性地选择一个属性放置在根节点，并对该属性的每个值产生一个分支。 分裂根节点上的数据集，并移到子女节点，产生一棵局部树(partial tree)。 对该划分的质量进行评估。 对其他属性重复该过程。 每个用于划分的属性产生一棵局部树。 根据局部树的质量，选择一棵局部树。 对选定的局部树的每个子女节点重复以上1-6步。 这是一个递归过程。如果一个节点上的所有实例都具有相同的类，则停止局部树的生长。 气象数据集示例(1) 气象数据集示例(2) 有4个属性，因此有4棵可能的局部树，见图4-3所示。哪一棵局部树最好? 叶节点上显示了“yes”和“no”类的数目。只具有一个类( “yes”或“no”)的叶节点不必再进一步划分，并且到该分支的递归过程将结束。 由于我们寻找小树，因此希望停止划分尽可能早地发生。 如果我们具有节点纯度的度量，那么应当选择产生最纯子女节点的属性。 气象数据集示例(3) 观察4个图，并仔细思索你认为哪个属性是最佳选择。 我们需要一种度量来度量节点的纯度，并需要一种度量告诉我们根据一个变量的属性值将一个不纯的节点上的数据划分到其子女后，纯度提高了多少。最为广泛使用的度量是信息熵。 4.2.2 信息论和信息熵 信息论(information theory)是数学中的概率论和数理统计的一个分支，用于处理信息和信息熵、通信系统、数据传输率和失真理论、密码学、信噪比、数据压缩和相关课题。 Claude Shannon(1916--2001)被称为信息论之父。他的理论“将信息传输看作一种统计学现象”，并且为通信工程师提供了一种方法，使用普通的二进制位流确定通信信道的容量。 该理论的信息传输并不“关注信息或消息内容本身” 熵(entropy)是源于热力学的概念，随后出现信息论中。 热力学熵(thermodynamic entropy)S(在化学和热力学中简称熵)是物理系统中不能用来做功的能量的一种度量。它也是系统无序性的一种度量。 在构造决策树的过程中，熵定义为无序性度量很合适。 如果一个节点上的数据的类值在可能的类值上均匀分布，则称节点的熵(无序性)最大。 如果一个节点上的数据的类值对于所有数据都相同，则熵最小。 通过分裂，我们希望得到尽可能纯的节点。这相当于降低系统的熵： 1)当一个节点上的“yes”或“no”的个数为零时，信息熵为零。 2)当一个节点上的“yes”和“no”的个数相等时，信息熵最大。这样的节点是最不纯的节点。 信息值或熵 熵函数: 单位是位(bit) 4.2.3 划分的选择 信息增益（