数据分类决策树课件.ppt
( 4.5 )《数据分类决策树课件.ppt》由会员分享，可在线阅读，更多相关《数据分类决策树课件.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据分类决策树2022/10/51第1页，此课件共65页哦 第5章章决策树和决策规则决策树和决策规则 5.1引例引例 n分类的定义n分类是指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类。2022/10/52第2页，此课件共65页哦AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1描述属性描述属性类别属性类别属性分类问题使用的数据集格式：分类问题使用的数据集格式：2022/10/53第3页，此课件共65页哦5.1 引例n分类问题使用的数据集格式n描述属性可以是连
2、续型属性，也可以是离散型属性；而类别属性必须是离散型属性。n连续型属性是指在某一个区间或者无穷区间内该属性的取值是连续的，例如属性“Age”n离散型属性是指该属性的取值是不连续的，例如属性“Salary”和“Class”2022/10/54第4页，此课件共65页哦5.1 引例n分类问题使用的数据集格式n分 类 问 题 中 使 用 的 数 据 集 可 以 表 示 为X=(xi,yi)|i=1,2,totalnxi=(xi1,xi2,xid)，其中xi1,xi2,xid分别对应d个描述属性A1,A2,Ad的具体取值nyi表示数据样本xi的类标号，假设给定数据集包含m个类别，则yic1,c2,cm，
3、其中c1,c2,cm是类别属性C的具体取值n未 知 类 标 号 的 数 据 样 本x用d维 特 征 向 量x=(x1,x2,xd)来表示2022/10/55第5页，此课件共65页哦5.2 分类问题概述n5.2.1 分类的过程n5.2.2 分类的评价准则2022/10/56第6页，此课件共65页哦5.2.1 分类的过程获取数据获取数据预处理预处理分类器设计分类器设计分类决策分类决策2022/10/57第7页，此课件共65页哦5.2.1 分类的过程n获取数据n输入数据、对数据进行量化n预处理n去除噪声数据、对空缺值进行处理n数据集成或者变换 n分类器设计n划分数据集、分类器构造、分类器测试n分类决
4、策n对未知类标号的数据样本进行分类2022/10/58第8页，此课件共65页哦5.2.2 分类的评价准则n给定测试集Xtest=(xi,yi)|i=1,2,NnN表示测试集中的样本个数nxi表示测试集中的数据样本nyi表示数据样本xi的类标号n对于测试集的第j个类别，假设n被正确分类的样本数量为TPjn被错误分类的样本数量为FNjn其他类别被错误分类为该类的样本数据量为FPj2022/10/59第9页，此课件共65页哦5.2.2 分类的评价准则n精确度：代表测试集中被正确分类的数据样本所占的比例 2022/10/510第10页，此课件共65页哦5.2.2 分类的评价准则n查全率：表示在本类样本
5、中被正确分类的样本所占的比例 n查准率：表示被分类为该类的样本中，真正属于该类的样本所占的比例 2022/10/511第11页，此课件共65页哦5.2.2 分类的评价准则nF-measure(加加权权调调合合平平均均数数)：是查全率和查准率的组合表达式 n是可以调节的，通常取值为1 2022/10/512第12页，此课件共65页哦5.2.2 分类的评价准则n几何均值：是各个类别的查全率的平方根 2022/10/513第13页，此课件共65页哦 决决策策树树方方法法的的起起源源是是亨亨特特（HuntHunt，19661966）的的概概念念学学习习系系统统CLSCLS方方法法，然然后后发发展展到到
6、由由QuinlanQuinlan研研制制ID3ID3方方法法，然然后后到到著著名名的的C4.5C4.5算算法法，C4.5C4.5算算法法的的一一个个优优点点是是它它能能够够处处理理连连续续属属性性。还还有有CARTCART算算法法和和AssistantAssistant算法也是比较有名的决策树方法。算法也是比较有名的决策树方法。5.3 5.3 决策树决策树2022/10/514第14页，此课件共65页哦n决策树的优点：n进行分类器设计时，决策树分类方法所需时间相对较少n决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式n可以将决策树中到达每个叶节点的路径转换为IFTHEN形式的分类规
7、则，这种形式更有利于理解2022/10/515第15页，此课件共65页哦1.1.什么是决策树什么是决策树q决决策策树树（Decision Decision TreeTree）又又称称为为判判定定树树，是是运运用用于于分分 类类 的的 一一 种种 树树 结结 构构。其其 中中 的的 每每 个个 内内 部部 结结 点点（internal internal nodenode）代代表表对对某某个个属属性性的的一一次次测测试试，每每条条边边代代表表一一个个测测试试结结果果，叶叶结结点点（leafleaf）代代表表某某个个类类（classclass）或或者者类类的的分分布布（class class dis
8、tributiondistribution），最最上面的结点是根结点。上面的结点是根结点。q决决策策树树提提供供了了一一种种展展示示类类似似在在什什么么条条件件下下会会得得到到什什么么值值这这类类规规则则的的方方法法。下下例例是是为为了了解解决决这这个个问问题题而而建建立立的的一一棵棵决决策策树树，从从中中可可以以看看到到决决策策树树的的基基本本组组成成部部分分：决决策策结点、分支和叶结点。结点、分支和叶结点。2022/10/516第16页，此课件共65页哦例例图图5-2给出了一个商业上使用的决策树的例子。它表示了给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买一个
9、关心电子产品的用户是否会购买PC（buys_computer）的知）的知识，用它可以预测某条记录（某个人）的购买意向。识，用它可以预测某条记录（某个人）的购买意向。图图5-2buys_computer的决策树的决策树 2022/10/517第17页，此课件共65页哦这这棵棵决决策策树树对对销销售售记记录录进进行行分分类类，指指出出一一个个电电子子产产品品消消费费者者是是否否会会购购买买一一台台计计算算机机“buys_computerbuys_computer”。每每个个内内部部结结点点（方方形形框框）代表对某个属性的一次检测。每个叶结点（椭圆框）代表一个类：代表对某个属性的一次检测。每个叶结点
10、（椭圆框）代表一个类：buys_computers=yes buys_computers=yes 或者或者 buys_computers=nobuys_computers=no在这个例子中，样本向量为：在这个例子中，样本向量为：（age,student,credit_rating;buys_computersage,student,credit_rating;buys_computers）被决策数据的格式为被决策数据的格式为:（age,student,credit_ratingage,student,credit_rating）输入新的被决策的记录，可以预测该记录隶属于哪个类。输入新的被决策的
11、记录，可以预测该记录隶属于哪个类。2022/10/518第18页，此课件共65页哦2.2.使用决策树进行分类使用决策树进行分类 构造决策树是采用自上而下的递归构造方法。以多叉树为例，构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。再依次递归处理各个子集。反之，则作为叶结点。决策树构造的结果是一棵二叉或多叉树，它的输入是一组决
12、策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为般表示为一个逻辑判断，如形式为(a=b)的逻辑判断，其中的逻辑判断，其中a是是属性，属性，b是该属性的某个属性值；树的边是逻辑判断的分支结是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。有几个属性值，就有几条边。树的叶结点都是类别标记。2022/10/
13、519第19页，此课件共65页哦使用决策树进行分类分为两步：使用决策树进行分类分为两步：q第第1 1步步：利利用用训训练练集集建建立立并并精精化化一一棵棵决决策策树树，建建立立决决策策树树模模型型。这这个过程实际上是一个从数据中获取知识，进行机器学习的过程。个过程实际上是一个从数据中获取知识，进行机器学习的过程。q第第2 2步步：利利用用生生成成完完毕毕的的决决策策树树对对输输入入数数据据进进行行分分类类。对对输输入入的的记记录录，从从根根结结点点依依次次测测试试记记录录的的属属性性值值，直直到到到到达达某某个个叶叶结结点点，从从而找到该记录所在的类。而找到该记录所在的类。2022/10/52
14、0第20页，此课件共65页哦问题的关键是建立一棵决策树。这个过程通常分为两个阶段：问题的关键是建立一棵决策树。这个过程通常分为两个阶段：q建建树树（Tree Tree BuildingBuilding）：决决策策树树建建树树算算法法见见下下，这这是是一一个个递归的过程，最终将得到一棵树。递归的过程，最终将得到一棵树。q剪剪枝枝（Tree Tree PruningPruning）：剪剪枝枝的的目目的的是是降降低低由由于于训训练练集集存存在在噪噪声而产生的起伏。声而产生的起伏。2022/10/521第21页，此课件共65页哦 由由Quinlan在在80年代中期提出的年代中期提出的ID3算法是分类规
15、则挖掘算算法是分类规则挖掘算法中最有影响的算法。法中最有影响的算法。ID3即决策树归纳（即决策树归纳（InductionofDecisionTree）。早期的）。早期的ID算法只能就两类数据进行挖掘（如正类和反类）；算法只能就两类数据进行挖掘（如正类和反类）；经过改进后，现在经过改进后，现在ID算法可以挖掘多类数据。待挖掘的数据必须是算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、一致的，也就是说，对具有相同属性的数据，其对应不矛盾的、一致的，也就是说，对具有相同属性的数据，其对应的类必须是唯一的。在的类必须是唯一的。在ID3算法挖掘后，分类规则由决策树来算法挖掘后，分类规则由决策树来表示。
16、表示。5.4 5.4 分类规则挖掘的分类规则挖掘的ID3ID3算法算法2022/10/522第22页，此课件共65页哦1.ID31.ID3算法的基本思想算法的基本思想 由训练数据集中全体属性值生成的所有决策树的集合称为搜索由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间，该搜索空间是针对某一特定问题而提出的。系统根据某个评空间，该搜索空间是针对某一特定问题而提出的。系统根据某个评价函数决定搜索空间中的哪一个决策树是价函数决定搜索空间中的哪一个决策树是“最好最好”的。评价函数一的。评价函数一般依据分类的准确度和树的大小来决定决策树的质量。如果两棵般依据分类的准确度和树的大小来决定决策树
17、的质量。如果两棵决策树都能准确地在测试集进行分类，则选择较简单的那棵。相决策树都能准确地在测试集进行分类，则选择较简单的那棵。相对而言，决策树越简单，则它对未知数据的预测性能越佳。寻找对而言，决策树越简单，则它对未知数据的预测性能越佳。寻找一棵一棵“最好最好”的决策树是一个的决策树是一个NP完全问题。完全问题。NPNP完全问题是这样的问题：用确定性的算法在多项式时间内完全问题是这样的问题：用确定性的算法在多项式时间内无法解决的问题。实际之中，解决这样的问题，往往是根据无法解决的问题。实际之中，解决这样的问题，往往是根据用启发式算法，求出近似的解。用启发式算法，求出近似的解。2022/10/52
18、3第23页，此课件共65页哦ID3ID3使使用用一一种种自自顶顶向向下下的的方方法法在在部部分分搜搜索索空空间间创创建建决决策策树树，同同时时保保证找到一棵简单的决策树证找到一棵简单的决策树可能不是最简单的。可能不是最简单的。ID3ID3算法的基本思想描述如下：算法的基本思想描述如下：step step 1 1任任意意选选取取一一个个属属性性作作为为决决策策树树的的根根结结点点，然然后后就就这这个个属性所有的取值创建树的分支；属性所有的取值创建树的分支；step step 2 2用用这这棵棵树树来来对对训训练练数数据据集集进进行行分分类类，如如果果一一个个叶叶结结点点的的所所有有实实例例都都属
19、属于于同同一一类类，则则以以该该类类为为标标记记标标识识此此叶叶结结点点；如如果果所所有有的的叶叶结结点都有类标记，则算法终止；点都有类标记，则算法终止；step step 3 3否否则则，选选取取一一个个从从该该结结点点到到根根路路径径中中没没有有出出现现过过的的属属性性为为标标记记标标识识该该结结点点，然然后后就就这这个个属属性性所所有有的的取取值值继继续续创创建建树树的的分分支支；重复算法步骤重复算法步骤step 2step 2；agestudentcredit_ratingbuys_computers25YESexcellantYES35NOfairYES2022/10/524第24页
20、，此课件共65页哦这个算法一定可以创建一棵基于训练数据集的正确的决策树，这个算法一定可以创建一棵基于训练数据集的正确的决策树，然而，这棵决策树不一定是简单的。显然，不同的属性选取顺序将然而，这棵决策树不一定是简单的。显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。树。在在ID3算法中，采用了一种基于信息的启发式的方法来决定如算法中，采用了一种基于信息的启发式的方法来决定如何选取属性。启发式方法选取具有最高信息量的属性，也就是说，生何选取属性。启发式方法选取具有最高信息量的属性，也就是说，生成最少分
21、支决策树的那个属性。成最少分支决策树的那个属性。2022/10/525第25页，此课件共65页哦算法：算法：Generate_decision_treeGenerate_decision_tree由给定的训练数据产生一棵决策树由给定的训练数据产生一棵决策树输入：训练数据集输入：训练数据集samplessamples，用离散值属性表示；候选属性的集合，用离散值属性表示；候选属性的集合attribute_listattribute_list。输出：一棵决策树输出：一棵决策树方法：方法：（1 1）创建结点）创建结点N N；（2 2）if samples if samples 都在同一个类都在同一个类
22、C thenC then（3 3）返回）返回N N作为叶结点，用类作为叶结点，用类C C标记；标记；（4 4）if attribute_list if attribute_list 为空为空 then then（5 5）返回）返回N N作为叶结点，标记作为叶结点，标记samplessamples中最普通的类；中最普通的类；/多数表决多数表决（6 6）选择）选择attribute_listattribute_list中具有最高信息增益的属性中具有最高信息增益的属性test_attributetest_attribute；/用信息增益作为属性选择度量用信息增益作为属性选择度量（7 7）标记结点）标
23、记结点N N为为test_attributetest_attribute；（8 8）for each test_attributefor each test_attribute中的已知值中的已知值ai /ai /划分划分samplessamples（9 9）由结点）由结点N N生长出一个条件为生长出一个条件为test_attributetest_attributeaiai的分枝；的分枝；（1010）设）设sisi为为samplessamples中中test_attributetest_attributeaiai的样本集合；的样本集合；/一个划分一个划分（1111）if siif si为空为空
24、thenthen（1212）加上一个叶结点，标记为标记）加上一个叶结点，标记为标记samplessamples中最普通的类；中最普通的类；/多数表决多数表决（1313）else else 加上一个由加上一个由Generate_decision_treeGenerate_decision_tree（si,attribute_list-test_attributesi,attribute_list-test_attribute）返回的结点；）返回的结点；2022/10/526第26页，此课件共65页哦2.2.属性选择度量属性选择度量在在Generate_decision_treeGenerate_
25、decision_tree算算 法法 的的Step Step 6 6，算算 法法 需需 选选 择择attribute_listattribute_list中中具具有有最最高高信信息息增增益益的的属属性性test_attributetest_attribute。ID3ID3算算法法在在树树的的每每个个结结点点上上以以信信息息增增益益（information information gaingain）作作为为度度量量来来选选择择测测试试属属性性。这这种种度度量量称称为为属属性性选选择择度度量量或或分分裂裂的的优优良良性性度度量量。选选择择具具有有最最高高信信息息增增益益（或或最最大大熵熵压压缩缩）
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 数据 分类 决策树 课件
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内