基于决策树规则分类算法的研究(12-15).ppt

基于决策树规则分类算法的研究 报告人 孙秀芳2010年12月15日 介绍内容 研究的主要内容数据挖掘及其分类方法概述C4 5算法基于规则排序的决策树分类算法CABRR的研究 一 研究的主要内容 研究的主要内容 从决策树入手 从中提取决策树规则 并通过对决策树规则进行有效地排序后生成分类器 应用于分类预测 二 数据挖掘及其分类方法概述 数据挖掘的理论分类概念及算法描述分类算法度量的方法与尺度 2 1数据挖掘的理论 数据挖掘的概念 所谓数据挖掘 又称数据库中的知识发现 是指从大量的 不完全的 有噪声的 模糊的 随机的海量数据中 或是大型数据库或数据仓库中提取隐含的 未知的 非平凡的 有潜在应用价值的信息或模式 数据挖掘的过程 确定挖掘目的 数据准备 数据挖掘 模式评估与知识表示 数据挖掘的具体过程如下图所示 数据源 清理 集成后数据 选择 变换后数据 模式 提供可供挖掘的知识 清理与集成 选择与变换 数据挖掘 评估与表示 2 2分类概念及算法描述 分类的概念 所谓分类 就是对己知现存的类别 建立类别的描述规则分类器 然后对未知新例的观察值进行判断归类 下图为分类过程图 训练集 分类模型 可接受的模型 预测结果 通过分类算法建立模型 评估模型 预测 未知数据元组 典型的分类算法 常用的分类方法包括 决策树分类 关联分类 神经网络 贝叶斯分类方法等 基于决策树分类的典型算法有 ID3算法 C4 5算法 PART算法 CABRR算法等 2 3分类算法度量的方法与尺度 每种分类方法都需要用一定的指标来进行评估 常用的分类算法的比较与评估标准有如下几个方面 预测的准确率可理解性可伸缩性速度强壮性 三 C4 5算法 决策树算法的基本理论决策树的基本算法C4 5算法 3 1决策树算法的基本理论 决策树 是一种结构 一种知识的表达形式 它由两种元素组成 节点和分支 在最终生成的决策树上 其中每个内部节点表示数据集的一个属性 每个分支代表对该属性的一个测试输出 每个叶结点代表划分的类别 最顶端节点为根节点 决策树的生成过程 主要分成两个步骤 一是生成树 二是树的修剪 树的修剪 即树的剪枝 最常用的剪枝技术有预剪枝和后剪枝 决策树的工作原理流程图如下 数据源 训练集 预处理 决策树分类算法归纳 生成决策树 分类规则 剪枝 3 2决策树的基本算法 Generate decision tree 根据给定数据集产生一个决策树输入 训练样本 各属性均取离散数值 可供归纳的候选属性集为 attribute list 输出 决策树 处理流程程 1 创建一个结点 2 若该结点中的所有样本均为同一类别C 则 3 返回N作为一个叶结点并标志为类别C 4 若attribute list为空 则 5 返回N作为一个叶结点并标记为该结点所含样本中类别个数最多的类别 6 从attribute list选择一个信息增益最大的属性test attribute 7 并将结点N标记为test attribute 8 对于test attribute中的每一个已知取值ai准备划分结点N所包含的样本集 9 根据test attribute ai条件 从结点N产生相应的一个分支 以表示该测试条件 10 设si为test attribute ai条件所获得的样本集合 11 若si为空 则将相应叶结点标记为该结点所含样本中类别个数最多的类别 12 否则将相应叶结点标志为Generate decision tree si attribute list test attribute 返回值 3 3C4 5算法 C4 5算法 是对ID3的改进算法 该算法采用信息增益率作为对选择分枝属性的分枝准则 计算各属性的信息增益率 然后选取信息增益率最大的属性作为结点 自顶向下生成决策树 对构造C4 5决策树的相关理论的描述如下 1 首先计算给定的样本所需的期望信息 设S为一个包含s个数据样本的集合 对于类别属性 可以取m个不同的值 对应于m个不同的类别Ci i 1 2 m 假设类别Ci中的样本个数为si 期望信息为 其中pi是任意样本属于Ci的概率 并用si s估计 2 接着计算当前样本集合所需要的信息嫡 设一个属性A具有v个不同的值 a1 a2 av 利用属性A可以将集合S划分为v个子集 S1 S2 Sv 其中Sj包含了S集合中属性A取aj值的数据样本 如果属性A被选为测试属性 最好的分裂属性 设Sij为子集Sj中属于Ci类别的样本集 根据A划分计算的熵为 其中项为第j个子集的权 也等于子集中样本个数除以S中的样本总数 熵值越小 子集划分的纯度越高 而对于子集sj有 其中 是子集sj中样本属于类别Ci的概率 然后利用属性A对当前分支结点进行相应样本集合划分计算信息增益 3 最后 求取信息增益率 其表达式为 其中 这个Gainratio A 值越大 分枝包含的有用信息越多 C4 5算法的工作流程图 开始 读取 存储类信息 读取属性信息 读取数据库 是连续属性 划分区域 存储至属性哈希表中 读取训练样本 有缺失数据 忽略或用最多的属性值来替代 存储样本表 次迭代交叉验证 将数据集划分成K个子集 对生成的树进行测试后打印分类信息 取K 1个子集用C4 5算法建构树 规则提取 结束 Y Y N 四 基于规则排序的决策树分类算法CABRR的研究 CABRR算法的产生CABRR算法基本概念CABRR算法的基本思想及规则排序算法CABRR算法的实例分析 4 1CABRR算法的产生 CABRR算法的产生 用规则构造分类器时 对规则的排序分为两种 基于规则的排序和基于类的排序 在使用基于类的排序中 一个质量较差的规则可能碰巧预测较高秩的类 从而导致较高质量的规则被忽略 而基于规则的排序则能弥补这一点的不足 于是出现了基于规则的决策树分类规则算法CABRR 基于类的排序 按照对类的规则的描述长度由小到大进行排序 基于规则的排序 结合规则的长度 准确率和覆盖率这三个度量值进行排序 4 2CABRR算法基本概念 规则前件 规则后件 每一个分类规则可以表示为如下形式 规则左边为规则前件 右边为规则后件 准确率 是指节点中正确预测的实例与分配给该节点的实例总数之比 度量的是该节点会正确预测目标值的可能性记为 覆盖率 是指节点中实例数量与构造数据集中实例总数之比 度量的是从构造数据集中分配了多少实例给该节点 记为 其中 A 是满足规则前件的记录数 Ay 是同时满足规则前件和后件的记录数 D 是记录总数 规则匹配 所谓规则匹配 就是对于新的对象 在规则集中查找匹配的规则 如果只有一条规则与之完全匹配 即各个属性值均相等 则将新对象归至匹配规则决策值对应的类别 如果有多个规则与之相匹配 必须对所有匹配规则进行排序 然后将新对象归至优先值最高的规则所定义的类别 4 3CABRR算法的基本思想及规则排序算法 CABRR分类算法的基本思想可用过程图表示如右 数据源 训练集 C4 5算法归纳 生成未剪枝的决策树 分类规则 规则排序 构造分类器 分类结果 分类 未知类别数据集 开始 读取未排好序的规则集Rules 计算Rules中每条规则的长度 按规则长度与准确率的乘积对Rules中规则进行排序 乘积大者优先 某些规则的长度与准确率的乘积是否相等 某些规则的长度是否相等 按规则长度对这些规则重新排序 按覆盖率对规则进行排序 排好序的规则集Rules 结束 Y N N 基于规则的排序算法的思想流程图 规则集排序后对测试数据集进行分类的流程图 开始 读取排好序的规则集Rules和测试数据集test data set for循环读取test data set中的对象 并为其寻找匹配的规则 设置一个Flag标志 赋初值为0 如果其值变为1 表示Rules中有与所读取对象相匹配得规则 从前往后扫描Rules 直到有匹配的规则出现 Rules中是否有匹配的规则 将新对象归至匹配规则所定义的类别 并使Flag 1 寻找覆盖率最大的规则所定义的类别 将新对象归至此类别中 分好类的数据集 结束 N Y 4 5CABRR算法的实例分析 接下来我们通过实验证明使用基于规则排序的CABRR算法的有效性 取脊椎动物数据集来做一个实验 具体的数据如下表 a 所示 表 a 脊椎动物数据集 从上表中得出的未截枝的决策树如下图所示 体温 胎生 水生动物 哺乳类 5 0 鸟类 2 0 爬行类 2 0 鱼类 3 0 两栖类 3 0 1 0 恒温 冷血 是 否 否 是 半 对规则进行截枝后 得到的规则如下图所示 具体的规则信息如下图所示 然后分别用基于规则的排序算法和基于类的排序算法对规则进行排序 排序后的规则按优先顺序从高到低排序后分别如下表 b c 所示 表 b 基于规则进行排序后的规则列表表 c 基于类进行排序后的规则列表 用表 b 和表 c 的规则构造分类器 分别对表 a 中的数据进行预测分