决策树分类--ppt课件.ppt

《决策树分类--ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、决策树分类王成（副教授）计算机科学与技术学院1ppt课件主要内容什么是决策树ID3算法算法改进C4.5算法CART算法DecisionTreeModeling决策树是一种简单且应用广泛的预测方法决策树图3.1常见的决策树形式决策树主要有二元分支（binarysplit）树和多分支（multiwaysplit）树。一般时候采用二元分裂，因为二元分裂在穷举搜索中更加灵活。决策树形式决策树决策树（DecisionTree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internalnode）代表对某个属性的一次测试，每条边代表一个测试结果，

2、叶结点（leaf）代表某个类（class）或者类的分布（classdistribution），最上面的结点是根结点决策树提供了一种展示在什么条件下会得到什么类别这类规则的方法。下例是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结点决策树下图给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买PC（buys_computer）的知识，用它可以预测某条记录（某个人）的购买意向决策树这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机“buys_computer”。每个

3、内部结点(方形框)代表对某个属性的一次检测。每个叶结点(椭圆框)代表一个类:buys_computers=yes或者buys_computers=no在这个例子中，特征向量为：(age,student,credit_rating,buys_computers)被决策数据的格式为:(age,student,credit_rating)输入新的被决策的记录，可以预测该记录隶属于哪个类。使用决策树进行分类第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程第2步：利用生成完毕的决策树对输入数据进行

4、分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类主要内容什么是决策树ID3算法算法改进C4.5算法CART算法如何从训练数据中学习决策树?贷款申请数据集如何从训练数据中学习决策树?Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:4Yes:1Own_house？truefalseNo:0Yes:6No:6Yes:3(a)(b)两种可能的根节点选取方式哪种更好？ID3算法ID3算法主要针对属性选择问题使用信息增益度选择测试属性ID3决策树建立算法1决定分类属性集合；2对目前的数据表

5、，建立一个节点N3如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类(纯的类别)4如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别(不纯的类别)5否则，根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性6节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏7如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树信息熵(Entropy)我们常说信息很多，或信息很少，但却很难说清楚信息到底有

6、多少比如一本50多万字的《史记》有多少信息量？或一套莎士比亚全集有多少信息量？这个问题几千年来都没有人给出很好的解答，直到1948年，香农(ClaudeShannon)在他著名的论文“通信的数学原理”中提出了信息熵的概念，才解决了信息的度量问题，并且量化出信息的作用信息熵(Entropy)一条信息的信息量和它的不确定性有着直接的关系比如，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量信息。相反，如果我们对某件事已经有了较多了解，那么不需要太多信息就能把它搞清楚从这个角度看，信息量就等于不确定性的多少如何量化信息的度量呢？信息熵(E

7、ntropy)假如我错过了一个有32支球队参加的足球赛，赛后我问一个知道比赛结果的观众“哪支球队是冠军”？他不愿意直接告诉我，而让我猜，每猜一次，他要收一元钱才肯告诉我是否猜对，那我需要付多少钱才能知道谁是冠军呢？我可以把球队编号，从1到32，然后问“冠军球队在1-16号中吗？”，假如他告诉我猜对了，我就接着问“冠军在1-8号中吗？”，假如他说猜错了，那我就知道冠军在9-16号中。这样只要5次，我就能知道哪支球队是冠军当然，香农不是用钱，而是用比特(bit)来度量信息量，在上例中，这条消息的信息量是5比特信息量的比特数和所有可能情况的对数有关，例如本

8、例中，信息量=log(球队数)，即5=log(32)信息熵(Entropy)实际上可能不需要5次就能猜出谁是