基于决策树规则分类算法的研究.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