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

1、基于决策树规那么分类算法的研讨报告人：孙秀芳2021年12月15日.引见内容研讨的主要内容数据发掘及其分类方法概述C4.5算法基于规那么排序的决策树分类算法CABRR的研讨. 一、研讨的主要内容 研讨的主要内容：从决策树入手，从中提取决策树规那么，并经过对决策树规那么进展有效地排序后生成分类器，运用于分类预测。. 二、数据发掘及其分类方法概述数据发掘的实际分类概念及算法描画分类算法度量的方法与尺度.2.1 数据发掘的实际数据发掘的概念：所谓数据发掘又称数据库中的知识发现是指从大量的、不完全的、有噪声的、模糊的、随机的海量数据中，或是大型数据库或数据仓库中提取隐含的、未知的、非平凡的、有潜在运用

2、价值的信息或方式。数据发掘的过程：确定发掘目的、数据预备、数据发掘、方式评价与知识表示。. 数据发掘的详细过程如以下图所示：数据源 清理/集成后数据选择/变换后数据模式提供可供发掘的知识清理与集成选择与变换数据发掘评价与表示.2.2 分类概念及算法描画分类的概念：所谓分类，就是对己知现存的类别，建立类别的描画规那么分类器，然后对未知新例的察看值进展判别归类。以下图为分类过程图：训练集分类模型可接受的模型预测结果经过分类算法建立模型评价模型预测未知数据元组. 典型的分类算法: 常用的分类方法包括：决策树分类、关联分类、神经网络、贝叶斯分类方法等。 基于决策树分类的典型算法有:ID3算法、C4.5

3、算法、PART算法、CABRR算法等。.2.3 分类算法度量的方法与尺度每种分类方法都需求用一定的目的来进展评价，常用的分类算法的比较与评价规范有如下几个方面： 预测的准确率 可了解性 可伸缩性 速度 强健性 . 三、C4.5算法决策树算法的根本实际决策树的根本算法C4.5算法.3.1 决策树算法的根本实际决策树：是一种构造，一种知识的表达方式，它由两种元素组成:节点和分支。在最终生成的决策树上，其中每个内部节点表示数据集的一个属性，每个分支代表对该属性的一个测试输出，每个叶结点代表划分的类别，最顶端节点为根节点。决策树的生成过程：主要分成两个步骤:一是生成树，二是树的修剪。树的修剪：即树的剪

4、枝，最常用的剪枝技术有预剪枝和后剪枝。. 决策树的任务原理流程图如下：数据源训练集预处置决策树分类算法归纳生成决策树分类规那么剪枝.3.2 决策树的根本算法Generate_decision_tree/根据给定数据集产生一个决策树输入：训练样本，各属性均取离散数值，可供归纳的候选属性集为:attribute_list。输出：决策树。处置流程程：1创建一个结点；2假设该结点中的一切样本均为同一类别C，那么3 前往N作为一 个叶结点并标志为类别C；4假设attribute_list为空，那么5 前往N作为一个叶结点并标志为该结点所含样本中类别个 数最多的类别；6从attribute_list选择一

5、个信息增益最大的属性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.3 C4.5算法C4.

6、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

7、,S2,.,Sv，其中Sj包含了S集合中属性A取aj值的数据样本，假设属性A被选为测试属性(最好的分裂属性)，设Sij为子集Sj中属于Ci类别的样本集，根据A划分计算的熵为: . 其中项 为第j个子集的权，也等于子集中样本个数除以S中的样本总数。熵值越小，子集划分的纯度越高。而对于子集sj有： 其中， 是子集sj中样本属于类别Ci的概率;然后利用属性A对当前分支结点进展相应样本集合划分计算信息增益:. 3. 最后，求取信息增益率，其表达式为： 其中， 这个Gainratio(A)值越大，分枝包含的有用信息越多。. C4.5算法的任务流程图：开场读取、存储类信息读取属性信息读取数据库是延续属性划

8、分区域存储至属性哈希表中读取训练样本有缺失数据忽略或用最多的属性值来替代存储样本表次迭代交叉验证将数据集划分成K个子集对生成的树进展测试后打印分类信息取K-1个子集用C4.5算法建构树规那么提取终了YYN.四、基于规那么排序的决策树分类算法CABRR的研讨CABRR算法的产生 CABRR算法根本概念CABRR算法的根本思想及规那么排序算法CABRR算法的实例分析.4.1 CABRR算法的产生CABRR算法的产生：用规那么构造分类器时，对规那么的排序分为两种:基于规那么的排序和基于类的排序。在运用基于类的排序中，一个质量较差的规那么能够碰巧预测较高秩的类，从而导致较高质量的规那么被忽略。而基于规

9、那么的排序那么能弥补这一点的缺乏，于是出现了基于规那么的决策树分类规那么算法CABRR。基于类的排序：按照对类的规那么的描画长度由小到大进展排序。基于规那么的排序：结合规那么的长度、准确率和覆盖率这三个度量值进展排序。. 4.2 CABRR算法根本概念规那么前件、规那么后件：每一个分类规那么可以表示为如下方式： ，规那么左边为规那么前件，右边为规那么后件。准确率:是指节点中正确预测的实例与分配给该节点的实例总数之比，度量的是该节点会正确预测目的值的能够性记为：覆盖率:是指节点中实例数量与构造数据集中实例总数之比，度量的是从构造数据集中分配了多少实例给该节点，记为： 其中|A|是满足规那么前件的

10、记录数，|A y|是同时满足规那么前件和后件的记录数，|D|是记录总数。. 规那么匹配:所谓规那么匹配，就是对于新的对象，在规那么集中查找匹配的规那么，假设只需一条规那么与之完全匹配，即各个属性值均相等，那么将新对象归至匹配规那么决策值对应的类别;假设有多个规那么与之相匹配，必需对一切匹配规那么进展排序，然后将新对象归至优先值最高的规那么所定义的类别。. 4.3 CABRR算法的根本思想 及规那么排序算法CABRR分类算法的根本思想可用过程图表示如右：数据源训练集C4.5算法归纳生成未剪枝的决策树分类规那么规那么排序构造分类器分类结果分类未知类别数据集.开场读取未排好序的规那么集Rules计算

11、Rules中每条规那么的长度按规那么长度与准确率的乘积对Rules中规那么进展排序，乘积大者优先某些规那么的长度与准确率的乘积能否相等某些规那么的长度能否相等按规那么长度对这些规那么重新排序按覆盖率对规那么进展排序排好序的规那么集Rules终了YNN 基于规那么的排序算法的思想流程图：.规那么集排序后对测试数据集进展分类的流程图：开场读取排好序的规那么集Rules和测试数据集test-data-setfor循环读取test-data-set中的对象，并为其寻觅匹配的规那么 设置一个Flag标志，赋初值为0，假设其值变为1，表示Rules中有与所读取对象相匹配得规那么 从前往后扫描Rules，直

12、到有匹配的规那么出现Rules中能否有匹配的规那么将新对象归至匹配规那么所定义的类别，并使Flag=1寻觅覆盖率最大的规那么所定义的类别，将新对象归至此类别中分好类的数据集终了NY. 4.5 CABRR算法的实例分析 接下来我们经过实验证明运用基于规那么排序的CABRR算法的有效性。 取脊椎动物数据集来做一个实验，详细的数据如下表a所示：. 表a脊椎动物数据集名字体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类恒温毛发是否否是否哺乳类蟒蛇冷血鳞片否否否否是爬行类鲑鱼冷血鳞片否是否否否鱼类鲸恒温毛发是是否否否哺乳类青蛙冷血无否半否是是两栖类巨蜥冷血鳞片否否否是否爬行类蝙蝠恒温毛发是否是是是哺乳

13、类鸽子恒温羽毛否否是是否鸟类猫恒温软毛是否否是否哺乳类虹鱂冷血鳞片是是否否否鱼类美洲鳄冷血鳞片否半否是否爬行类企鹅恒温羽毛否半否是否鸟类豪猪恒温刚毛是否否是是哺乳类鳗鲡冷血鳞片否是否否否鱼类蝾螈冷血无否半否是是两栖类. 从上表中得出的未截枝的决策树如以下图所示：体温胎生水生动物哺乳类5.0鸟类2.0爬行类2.0鱼类3.0两栖类3.0/1.0)=恒温=冷血=是=否=否=是=半. 对规那么进展截枝后，得到的规那么如以下图所示：. 详细的规那么信息如以下图所示：然后分别用基于规那么的排序算法和基于类的排序算法对规那么进展排序，排序后的规那么按优先顺序从高到低排序后分别如下表b、c所示： . 表b基于

14、规那么进展排序后的规那么列表 表c基于类进展排序后的规那么列表 ruleclassconfsuplength体温=冷血 AND 水生动物=否爬行类50.00%22体温=恒温 AND 胎生=否鸟类50.00%22胎生=是哺乳类61.20%61水生动物=是鱼类45.30%21Default class: 两栖类 ruleclassconfsuplength胎生=是哺乳类61.20%61水生动物=是鱼类45.30%21体温=冷血 AND 水生动物=否爬行类50.00%22体温=恒温 AND 胎生=否鸟类50.00%22Default class: 两栖类. 用表b和表c的规那么构造分类器，分别对表a

15、中的数据进展预测分类，得出的分类结果如表d和表e所示：. 表d用基于规那么排序后的分类器进展预测分类的结果名字体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号类排序分类人类恒温毛发是否否是否哺乳类哺乳类蟒蛇冷血鳞片否否否否是爬行类爬行类鲑鱼冷血鳞片否是否否否鱼类鱼类鲸恒温毛发是是否否否哺乳类哺乳类青蛙冷血无否半否是是两栖类两栖类巨蜥冷血鳞片否否否是否爬行类爬行类蝙蝠恒温毛发是否是是是哺乳类哺乳类鸽子恒温羽毛否否是是否鸟类鸟类猫恒温软毛是否否是否哺乳类哺乳类虹鱂冷血鳞片是是否否否鱼类鱼类美洲鳄冷血鳞片否半否是否爬行类两栖类企鹅恒温羽毛否半否是否鸟类鸟类豪猪恒温刚毛是否否是是哺乳类哺乳类鳗鲡冷血鳞片否是否否否鱼类鱼类蝾螈冷血无否半否是是两栖类两栖类. 表e用基于类排序后的分类器进展预测分类的结果名字体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号类排序分类人类恒温毛发是否否是否哺乳类哺乳类蟒蛇冷血鳞片否否否否是爬行类爬行类鲑鱼冷血鳞片否是否否否鱼类鱼类鲸恒温毛发是是否否否哺乳类哺乳类青蛙冷血无否半否是是两栖类两栖类巨蜥冷血鳞片否否否是否爬行类爬行类蝙蝠恒温毛发是否是是是哺乳类哺乳类鸽子恒温羽毛否