决策树分类--ppt课件

决策树分类王成（副教授）计算机科学与技术学院1ppt课件主要内容什么是决策树ID3算法算法改进C4.5算法CART算法DecisionTreeModeling决策树是一种简单且应用广泛的预测方法决策树图3.1常见的决策树形式决策树主要有二元分支（binarysplit）树和多分支（multiwaysplit）树。一般时候采用二元分裂，因为二元分裂在穷举搜索中更加灵活。决策树形式决策树决策树（DecisionTree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internalnode）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（leaf）代表某个类（class）或者类的分布（classdistribution），最上面的结点是根结点决策树提供了一种展示在什么条件下会得到什么类别这类规则的方法。下例是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结点决策树下图给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买PC（buys_computer）的知识，用它可以预测某条记录（某个人）的购买意向Age?Credit_rating?student?yesnoyesyesno=30?4030…40yesnofairexcellent决策树这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机“buys_computer”。每个内部结点(方形框)代表对某个属性的一次检测。每个叶结点(椭圆框)代表一个类:buys_computers=yes或者buys_computers=no在这个例子中，特征向量为：(age,student,credit_rating,buys_computers)被决策数据的格式为:(age,student,credit_rating)输入新的被决策的记录，可以预测该记录隶属于哪个类。使用决策树进行分类第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类主要内容什么是决策树ID3算法算法改进C4.5算法CART算法如何从训练数据中学习决策树?IDAgeHas-jobOwn_houseCredit_ratingClass1YoungFalseFalseFairNo2YoungFalseFalseGoodNo3YoungTrueFalseGoodYes4YoungTrueTrueFairYes5YoungFalseFalseFairNo6MiddleFalseFalseFairNo7MiddleFalseFalseGoodNo8MiddleTrueTrueGoodYes9MiddleFalseTrueExcellentYes10MiddleFalseTrueExcellentYes11OldFalseTrueExcellentYes12OldFalseTrueGoodYes13OldTrueFalseGoodYes14OldTrueFalseExcellentYes15OldFalseFalsefairno贷款申请数据集如何从训练数据中学习决策树?Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:4Yes:1Own_house？truefalseNo:0Yes:6No:6Yes:3(a)(b)两种可能的根节点选取方式哪种更好？ID3算法ID3算法主要针对属性选择问题使用信息增益度选择测试属性ID3决策树建立算法1决定分类属性集合；2对目前的数据表，建立一个节点N3如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类(纯的类别)4如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别(不纯的类别)5否则，根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性6节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏7如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树信息熵(Entropy)我们常说信息很多，或信息很少，但却很难说清楚信息到底有多少比如一本50多万字的《史记》有多少信息量？或一套莎士比亚全集有多少信息量？这个问题几千年来都没有人给出很好的解答，直到1948年，香农(ClaudeShannon)在他著名的论文“通信的数学原理”中提出了信息熵的概念，才解决了信息的度量问题，并且量化出信息的作用信息熵(Entropy)一条信息的信息量和它的不确定性有着直接的关系比如，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量信息。相反，如果我们对某件事已经有了较多了解，那么不需要太多信息就能把它搞清楚从这个角度看，信息量就等于不确定性的多少如何量化信息的度量呢？信息熵(Entropy)假如我错过了一个有32支球队参加的足球赛，赛后我问一个知道比赛结果的观众“哪支球队是冠军”？他不愿意直接告诉我，而让我猜，每猜一次，他要收一元钱才肯告诉我是否猜对，那我需要付多少钱才能知道谁是冠军呢？我可以把球队编号，从1到32，然后问“冠军球队在1-16号中吗？”，假如他告诉我猜对了，我就接着问“冠军在1-8号中吗？”，假如他说猜错了，那我就知道冠军在9-16号中。这样只要5次，我就能知道哪支球队是冠军当然，香农不是用钱，而是用比特(bit)来度量信息量，在上例中，这条消息的信息量是5比特信息量的比特数和所有可能情况的对数有关，例如本例中，信息量=log(球队数)，即5=log(32)信息熵(Entropy)实际上可能不需要5次就能猜出谁是冠军，因为一些强队得冠的可能性更高，因此第一次猜测时可以把少数几支强队分成一组，其它球队分成另一组，然后猜冠军球队是否在那几支强队中这样，也许三次或四次就能猜出结果。因此，当每支球队夺冠的可能性(概率)不等时，这条信息的信息量比5比特少香农指出，它的准确信息量应该是)log...loglog(32322211ppppppHp1,p2,...,p32分别是这32支球队夺冠概率，香农把它称作信息熵，单位为比特；可以算出，当32支球队夺冠概率相同时，对应的信息熵为5比特。信息熵(Entropy)对于任意一个随机变量X(比如夺冠球队)，它的熵定义为XxxPxPXH)(log)()(变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大数据集的信息熵设数据集D中有m个不同的类C1,C2,C3,...,Cm设Ci,D是数据集D中Ci类的样本的集合,|D|和|Ci,D|分别是D和Ci,D中的样本个数21()logmiiiInfoDpp其中pi是数据集D中任意样本属于类Ci的概率，用估计||||,DCDi数据集D的信息熵:例:计算对下列数据集分类所需的信息熵年龄收入学生信用买了电脑30高否一般否30高否好否30-40高否一般是40中等否一般是40低是一般是40低是好否30-40低是好是30中否一般否30低是一般是40中是一般是30中是好是30-40中否好是30-40高是一般是40中否好否22()5599loglog141414140.940InfoD|D|=14|C1,D|=5|C2,D|=9使用熵衡量数据纯度假设有一个数据集合D，其中只有两个类，一个是正例类，一个是负例类计算D中正例类和负例类在三种不同的组分下熵的变化情况。（1）D中包含有50%的正例和50%的负例。H(D)=-0.5*log20.5-0.5*log20.5=1（2）D中包含有20%的正例和80%的负例。H(D)=-0.2*log20.2-0.8*log20.8=0.722（3）D中包含有100%的正例和0%的负例。H(D)=-1*log21-0*log20=0可以看到一个趋势，当数据变得越来越“纯”时，熵的值变得越来越小。当D中正反例所占比例相同时，熵取最大值。当D中所有数据都只属于一个类时，熵得到最小值。因此熵可以作为数据纯净度或混乱度的衡量指标。这正是决策树学习中需要的。数据集的信息熵假设按属性A划分D中的样本，且属性A根据训练数据的观测具有v个不同取值{a1,a2,...,aj,...,av}。如果A是离散值，可依属性A将D划分为v个子集{D1,D2,...,Dj,...,Dv}其中，Dj为D中的样本子集，它们在A上具有属性值aj这些划分将对应于从该节点A出来的分支。按属性A对D划分后，数据集的信息熵:1()*()vjAjjDInfoDInfoDD其中，充当第j个划分的权重。jDDInfoA(D)越小，表示划分的纯度越高信息增益()()()AGainAInfoDInfoD选择具有最高信息增益Gain(A)的属性A作为分裂属性按照能做“最佳分类”的属性A划分，使完成样本分类需要的信息量最小max()GainAmin()AInfoD确定第一次分裂的属性：按年龄划分年龄收入学生信用买了电脑30高否一般否30高否好否30-40高否一般是40中等否一般是40低是一般是40低是好否30-40低是好是30中否一般否30低是一般是40中是一般是30中是好是30-40中否好是30-40高是一般是40中否好否年龄30的有5个,其中3个为“否”年龄30-40的有4个,其中0个为“否”年龄40的有5个,其中2个为“否”694.0)53log5352log52(145)40log4044log44(144)52log5253log53(145Info年龄(D)Gain(年龄)=Info(D)-Info年龄(D)=0.940-0.694=0.246确定第一次分裂的属性：按收入划分年龄收入学生信用买了电脑30高否一般否30高否好否30-40高否一般是40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否30低是一般是40中是一般是30中是好是30-40中否好是30-40高是一般是40中否好否收入=高的有4个,其中2个为“否”收入=中的有6个,其中2个为“否”收入=低的有4个,其中1个为“否”911.0)43log4341log41(144)64log6462log62(146)42log4242log42(144Info收入(D)Gain(收入)=Info(D)-Info收入(D)=0.940-0.911=0.029确定第一次分裂的属性：按学生划分年龄收入学生信用买了电脑30高否一般否30高否好否30-40高否一般是40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否30低是一般是40中是一般是30中是好是30-40中否好是30-40高是一般是40中否好否是学生的有7个,其中1个为“否”不是学生的有7个,其中4个为“否”788.0)73log7374log74(147)76log7671log71(147Info学生(D)Gain(学生)=Info(D)-Info学生(D)=0.940-0.788=0.152确定第一次分裂的属性：按信用划分年龄收入学生信用买了电脑30高否一般否30高否好否30-40高否一般是40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否30低是一般是40中是一般是30中是好是30-40中否好是30-40高是一般是40中否好否信用好的有6个,其中3个为“否”信用一般的有8个,其中2个为“否”892.0)86log8682log82(148)63log6363log63