决策树和决策规则.ppt

决策树和决策规则 第7章 本章目标 分析解决分类问题的基于逻辑的方法的特性信息论基础ID3算法了解何时以及怎样用修剪方法降低决策树和复杂度总结用决策树和决策规则表示一个分类模型的局限性 什么是分类 数据分类 dataclassfication 是数据挖掘的主要内容之一 主要是通过分析训练数据样本 产生关于类别的精确描述 这种类别通常由分类规则组成 可以用来对未来的数据进行分类和预测 数据分类的两个步骤 第1步 建立一个模型 描述给定的数据类集或概念集 简称训练集 第2步 使用模型对数据进行分类 包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类 7 1信息论基础 信息论是C E Shannon四十年代末期 以客观概率信息为研究对象 从通信的信息传输问题中总结和开拓出来的理论 主要研究的问题 信源的描述 信息的定量度量 分析与计算信道的描述 信道传输的定量度量 分析与计算 信源 信道与通信系统之间的统计匹配 以及通信系统的优化 Shannon的三个编码定理 信息论诞生五十年来 至今 仍然是指导通信技术发展的理论基础 是创新通信体制的源泉 香农信息 概率信息 信息是事物运动状态或存在方式的不确定性的描述 在通信系统中形式上传输的是消息 但实质上传输的是信息 信源 信宿 信道 消息 干扰或噪声 发信者 收信者 通信系统框图 样本空间 某事物各种可能出现的不同状态 即所有可能选择的消息的集合 对于离散消息的集合 概率测度是对每一个可能选择的消息指定一个概率 一个样本空间和它的概率测度称为一个概率空间 表示 X P 在离散情况下 其中 P ui 为选择符号ui作为消息的概率 称为先验概率 信源数学模型 后验概率 条件概率 接收端收到消息 符号 后而发送端发的是的概率 自信息 消息发生后所含有的信息量 反映了消息发生前的不确定性 信源熵定义 信源各个离散消息的自信息量的数学期望 即概率加权的统计平均值 为信源的平均信息量 一般称为信源的信息熵 也叫信源熵或香农熵 有时也称为无条件熵或熵函数 简称熵 公式 熵函数的自变量是X 表示信源整体 实质上是无记忆信源平均不确定性的度量 单位 以2为底 比特 符号 互信息 后验熵 当接收到输出符号V vj后 信源的平均不确定性 即输入符号U的信息度量条件熵 对后验熵在输出符号集V中求期望称为信道疑义度 表示在输出端收到全部输出符号V后 对于输入端的符号集U尚存有不确定性 有疑义 这是由于存在干扰 噪声 引起的 H U V H U 表明接收到符号集V的所有符号后 关于输入符号U的平均不确定性减少了 互信息 先验的不确定性减去收到输出符号集V后尚存在的不确定性 表示收信者获得的信息量 也称信息增益 7 2ID3算法 决策树 DecisionTree 方法 决策树方法的起源是概念学习系统CLS 然后发展到由Quiulan研制ID3方法 然后到著名的C4 5算法 C4 5算法的一个优点是它能够处理连续属性 决策树又称为判定树 是运用于分类的一种树结构 其中的每个内部结点代表对某个属性的一次测试 每条边代表一个测试结果 叶结点代表某个类或者类的分布 最上面的结点是根结点 7 2ID3算法 续 ID3算法思想 任意选取一个属性作为决策树的根结点 然后就这个属性所有的取值创建树的分支 用这棵树来对训练数据集进行分类 如果一个叶结点的所有实例都属于同一类 则以该类为标记标识此叶结点 如果所有的叶结点都有类标记 则算法终止 否则 选取一个从该结点到根路径中没有出现过的属性为标记标识该结点 然后就这个属性所有的取值继续创建树的分支 重复算法步骤step2显然 不同的属性选取顺序将生成不同的决策树 因此 适当地选取属性将生成一棵简单的决策树 在ID3算法中 采用了一种基于信息的启发式的方法来决定如何选取属性 启发式方法选取具有最高信息增益的属性 也就是说 生成最少分支决策树的那个属性 7 2ID3算法 续 7 2ID3算法 续 属性2 属性1 A 80 89 属性3 类1 真 属性1 60 69 属性3 类1 真 70 79 属性3 类1 属性1 类2 B 属性1 属性3 属性3 属性3 类2 类1 A 类2 真 类2 假 B C C 假 90 99 A 真 B 类1 真 属性3 C 类1 假 7 2ID3算法 续 表7 1的ID3算法实例计算 1 计算信息熵H C 类别Ci出现概率P Ci Ci X Ci 为类别Ci的样本数 X 为总的样本数 C1 9 C2 5 X 14 代入上式算得H C 0 940bit2 计算属性1的条件熵H C V 属性1取值vj时 类别Ci的条件概率 P Ci vj Ci vj 属性1取值v1 A v2 B v3 CP v1 5 14 P v2 4 14 P v3 5 14取值为A的5个例子中有2个类1 3个类2 所以 P C1 v1 2 5P C2 v1 3 5 7 2ID3算法 续 表7 1的ID3算法实例计算 同理有 P C1 v2 4 4P C2 v2 0 4P C1 v3 3 5P C2 v1 2 5代入上式得 H C V 0 694bit3 计算信息增益Gain 属性1 H C H C V 0 246bit同理可求得Gain 属性3 0 048bit根据增益准则 ID3算法将选择属性1做为根节点 因为该属性的信息增益最大 为了求得最优解 还应该分析属性2的信息增益 但因它是连续型数值 不能直接求 而要先进行离散化转换成分类型的数据 7 3修剪决策树 决策树修剪的主要任务是抛弃一个或更多的子树 并用叶子替换这些子树 使决策树简单化 在替换这些子树时 我们期望算法降低预测误差率来提高分类模型的质量剪枝操作有两种策略 预剪枝 在树生成过程中判断是否还继续扩展决策树 若停止扩展 相当于剪去该结点以下的分枝后剪枝 对于生成好的树剪去某些结点和分枝C4 5算法遵循基于误差的后剪枝 也叫悲观修剪 即如果使用叶子或树枝代替原来的子树后 误差率能够下降 则就使用此叶子或树枝代替原来的子树 7 3修剪决策树 续 准备知识 二项式分布在医学领域中 有一些随机事件是只具有两种互斥结果的离散型随机事件 称为二项分类变量 dichotomousvariable 如对病人治疗结果的有效与无效 某种化验结果的阳性与阴性 接触某传染源的感染与未感染等 二项分布 binomialdistribution 就是对这类只具有两种互斥结果的离散型随机事件的规律性进行描述的一种概率分布 考虑只有两种可能结果的随机试验 当成功的概率 是恒定的 且各次试验相互独立 这种试验在统计学上称为贝努里试验 Bernoullitrial 如果进行n次贝努里试验 取得成功次数为X X 0 1 n 的概率可用下面的二项分布概率公式来描述 其中表示在n次实验中出现X的各种组合情况 7 3修剪决策树 续 决策树的子树如图所示 这里根节点是关于属性A的3个可能值 1 2 3 的检验 根节点的子节点是用相应的类和参数 Ti E 表示的叶 问题是估计修剪子树并用它的替换根结点作为一个新的归纳根节点的概率 类1 16 1 7 3修剪决策树 续 如一个叶结点覆盖N个实例 其中E个为错误的 对于具有信任度CF的实例 计算一个2项式分布UCF E N 即是实例误判的概率 那么N个实例误判的数目为N UCF E N 子树的错误数目为所有叶结点的总和 设CF为25 从统计表中可查出E的上限置信极限 U25 0 6 0 206 U25 0 9 0 143 U25 0 1 0 750 U25 1 16 0 157则子树的实例误判数目为 6 U25 0 6 9 U25 0 9 1 U25 0 1 3 257若以一个叶子 类1 16 1 代替子树 则误判数目为 16 U25 1 16 16 0 157 2 512 3 257由于以一个叶子 类1 16 1 代替子树误判数目小于原子树 所以可以该叶子代替原子树 7 4从决策树生成决策规则 虽然修剪后的决策树比原来的更紧凑 但它们仍然是非常复杂的 为了使决策树模型更易读 可以把到达每个叶的路径转换成IF THEN生成规则 IF部分包括一条路径的所有检验 THEN部分是最终分类 7 4从决策树生成决策规则 续 从决策树抽取规则需要两个步骤 获得简单规则精简规则条件 在单个规则的前项中可能包括不相关的条件 即对结论没有任何影响的条件 可以删除这些不影响规则集的正确性的多余条件 对规则进行精简 规则精简准则 设规则R是 ifAthen类C精简后的规则为R 是 ifA then类C其中A A X 即表示条件X对结论 类C 没有任何影响 这样R 覆盖的实例可分为以下4个部分 满足条件A 满足条件A 但不满足条件X 7 4从决策树生成决策规则 续 规则R覆盖了Y1 E1个实例 其中误判数目为E1 规则R 覆盖了Y1 E1 Y2 E2个实例 其中误判数目为E1 E2 则规则R的误判概率为 UCF E1 Y1 E1 规则R 的误判概率为 UCF E1 E2 Y1 E1 Y2 E2 如果UCF E1 Y1 E1 UCF E1 E2 Y1 E1 Y2 E2 就可以从条件A中删除条件项X 如何获得最优条件集是一个全局优化问题 当决策属性较多的时候 这样做非常耗时 为此C4 5采用贪婪搜索方法 即每次从条件集中删除一个对当前预测效果影响最小的条件 如果删除该条件之后 误判概率减小 则继续上述过程 如果误判概率增加则不能删除该条件 而整个精简过程也同时结束 对所有的贪婪搜索方法 不能保证最终获得最优解 7 4从决策树生成决策规则 续 例如 有下列规则 ifTSH 6 FTI 64 TSH t T4U t THY tthencalssA 该规则覆盖3个实例 其中2个判断正确 1个误判 则误判概率为UCF 1 3 69 设删除其中各个条件之后的误判概率如表所示则选择误判概率最小的条件 即FTI 64 从原来条件中删除此条件 规则变为 ifTSH 6 TSH t T4U t THY tthencalssA重复上述过程 直到最后的误判概率大于前面规则的误判概率为止