数据挖掘决策树算法及应用拓展学习教案.pptx

《数据挖掘决策树算法及应用拓展学习教案.pptx》由会员分享，可在线阅读，更多相关《数据挖掘决策树算法及应用拓展学习教案.pptx（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据挖掘决策树算法数据挖掘决策树算法(sun f)及应用拓展及应用拓展第一页，共36页。第1页/共36页第二页，共36页。决策树生成决策树生成(shn chn)(shn chn)基本思想：基本思想：用途：提取用途：提取(tq)(tq)分类规则，进行分类预测分类规则，进行分类预测判定树分类算法output训练集决策树input第2页/共36页第三页，共36页。决策树示意图决策树示意图第3页/共36页第四页，共36页。使用决策树进行使用决策树进行(jnxng)(jnxng)分类分类决策树决策树 一个树性的结构一个树性的结构内部节点上选用一个属性进行分割内部节点上选用一个属性进行分割每个分叉都是分割

2、的一个部分每个分叉都是分割的一个部分叶子节点表示叶子节点表示(biosh)(biosh)一个分布一个分布决策树生成算法分成两个步骤决策树生成算法分成两个步骤树的生成树的生成开始，数据都在根节点开始，数据都在根节点递归的进行数据分片递归的进行数据分片树的修剪树的修剪去掉一些可能是噪音或者异常的数据去掉一些可能是噪音或者异常的数据决策树使用决策树使用:对未知数据进行分割对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到叶子节点按照决策树上采用的分割属性逐层往下，直到叶子节点第4页/共36页第五页，共36页。决策树算法决策树算法(sun f)(sun f)基本基本(jbn)(jbn)算法（贪

3、心算法）算法（贪心算法）自上而下分而治之的方法自上而下分而治之的方法开始时，所有的数据都在根节点开始时，所有的数据都在根节点属性都是种类字段属性都是种类字段(如果是连续的，将其离散化如果是连续的，将其离散化)所有记录用所选属性递归的进行分割所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量属性的选择是基于一个启发式规则或者一个统计的度量 (如如,information gain),information gain)停止分割的条件停止分割的条件一个节点上的数据都是属于同一个类别一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割没有属性可以再用于对数据

4、进行分割第5页/共36页第六页，共36页。伪代码伪代码(di m)(Building Tree)(di m)(Building Tree)Procedure BuildTree(S)Procedure BuildTree(S)用数据用数据(shj)(shj)集集S S初始化根节点初始化根节点R R 用根结点用根结点R R初始化队列初始化队列Q QWhile Q is not Empty do While Q is not Empty do 取出队列取出队列Q Q中的第一个节点中的第一个节点N Nif N if N 不纯不纯(Pure)(Pure)for for 每一个属性每一个属性 A A估计

5、该节点在估计该节点在A A上的信息增益上的信息增益 选出最佳的属性，将选出最佳的属性，将N N分裂为分裂为N1N1、N2N2 第6页/共36页第七页，共36页。属性属性(shxng)(shxng)选择的统计度量选择的统计度量信息增益信息增益Information gain(ID3/C4.5)Information gain(ID3/C4.5)所有属性假设都是种类字段所有属性假设都是种类字段经过修改之后可以经过修改之后可以(ky)(ky)适用于数值字段适用于数值字段基尼指数基尼指数Gini index(IBM IntelligentMiner)Gini index(IBM Intelligent

6、Miner)能够适用于种类和数值字段能够适用于种类和数值字段第7页/共36页第八页，共36页。信息信息(xnx)(xnx)增益度度量增益度度量(ID3/C4.5)(ID3/C4.5)任意任意(rny)(rny)样本分类的期望信息：样本分类的期望信息：I(s1,s2,sm)=I(s1,s2,sm)=Pi log2(pi)Pi log2(pi)(i=1.m)(i=1.m)其中，数据集为其中，数据集为S S，m m为为S S的分类数目，的分类数目，Pi PiCiCi为某分类标号，为某分类标号，PiPi为任意为任意(rny)(rny)样本属于样本属于CiCi的的概率，概率，si si为分类为分类CiC

7、i上的样本数上的样本数由由A A划分为子集的熵：划分为子集的熵：E(A)=(s1j+smj)/s*I(s1j+E(A)=(s1j+smj)/s*I(s1j+smj)+smj)A A为属性，具有为属性，具有V V个不同的取值个不同的取值信息增益：信息增益：Gain(A)=I(s1,s2,sm)Gain(A)=I(s1,s2,sm)E(A)E(A)第8页/共36页第九页，共36页。训练训练(xnlin)(xnlin)集集(举例举例)ID3算法(sun f)第9页/共36页第十页，共36页。使用信息使用信息(xnx)(xnx)增益进行属性选择增益进行属性选择ggClass P:buys_comput

8、er=Class P:buys_computer=“yesyes”ggClass N:buys_computer Class N:buys_computer=“nono”ggI(p,n)=I(9,5)=0.940I(p,n)=I(9,5)=0.940ggCompute the entropy for Compute the entropy for ageage:HenceHenceSimilarlySimilarly第10页/共36页第十一页，共36页。Decision Tree(Decision Tree(结果结果(ji gu)(ji gu)输出输出)age?overcaststudent?

9、credit rating?noyesfairexcellent40nonoyesyesyes30.40第11页/共36页第十二页，共36页。u符号描述u贝叶斯理论(lln)u贝叶斯分类器u实验结果与分析贝叶斯分类器贝叶斯分类器第12页/共36页第十三页，共36页。=A1A2.Am，是由所有未知类别的可能样本组成的集合；c=A1A2.AmC是由所有已知类别的样本组成的集合。D c是训练样例集合。中的元素(yun s)x表示为x=。c中的元素(yun s)x表示为x=。其中ai表示第i个属性的某个取值。描述描述(mio sh)(mio sh)用到的符号用到的符号 我们用Ai表示第i个属性(shx

10、ng)，C表示决策属性(shxng)；aik表示第i个属性(shxng)的第k个取值，cj表示第j类；加上绝对值则表示相应的个数，如|Ai|表示第i个属性(shxng)的取值个数，|cj|表示第j类样例个数。第13页/共36页第十四页，共36页。设x是一个(y)类别未知的数据样本，cj为某个类别，若数据样本x属于一个(y)特定的类别cj，那么分类问题就是决定P(cj|x)，即在获得数据样本x时，确定x的最佳分类。所谓最佳分类，一种办法是把它定义为在给定数据集D中不同类别cj先验概率的条件下最可能（most probable）分类。贝叶斯理论提供了计算这种可能性的一种直接方法 更精确地讲，贝叶斯

11、法则基于假设的先验概率、给定假设下观察(gunch)到不同数据的概率，提供了一种计算假设概率的方法贝叶斯定理贝叶斯定理(dngl)(dngl)第14页/共36页第十五页，共36页。贝叶斯公式贝叶斯公式(gngsh)(gngsh)u 先验概率P(cj)P(cj|x)=P(x|cj)P(cj)P(x)u 联合(linh)概率P(x|cj)u 后验概率(gil)P(cj|x)第15页/共36页第十六页，共36页。如果没有这一先验知识，那么可以简单地将每一候选类别赋予相同的先验概率。不过通常我们(w men)可以用样例中属于cj的样例数|cj|比上总样例数|D|来近似，即先验概率先验概率P(cP(cj

12、 j)P(cj)代表还没有训练数据前，cj拥有的初始概率。P(cj)常被称为cj的先验概率(prior probability)，它反映了我们所拥有的关于cj是正确分类机会的背景知识(zh shi),它应该是独立于样本的。第16页/共36页第十七页，共36页。联合概率是指当已知类别为cj的条件(tiojin)下，看到样本x出现的概率。联合联合(linh)(linh)概率概率P(x|cj)P(x|cj)若设x=则P(x|cj)=P(a1,a2am|cj)第17页/共36页第十八页，共36页。后验概率后验概率(gil)P(cj|x)(gil)P(cj|x)即给定数据样本x时cj成立的概率(gil)

13、,而这正是我们所感兴趣的 P(cj|x)被称为C的后验概率(gil)（posterior probability），因为它反映了在看到数据样本x后cj成立的置信度第18页/共36页第十九页，共36页。贝叶斯分类贝叶斯分类(fn li)(fn li)我们现在我们现在(xinzi)(xinzi)计算计算P(cMAP|x)=max P(cj|x)j(1,|C|)P(cMAP|x)=max P(cj|x)j(1,|C|)则则P(cMAP|x)P(cMAP|x)称为最大后验概率称为最大后验概率(gil)(gil)然后我们就把然后我们就把x x分到分到cMAPcMAP类中类中第19页/共36页第二十页，共

14、36页。朴素朴素(p s)(p s)贝叶斯分类器一贝叶斯分类器一设x=，为一个(y)有m个属性的样例=max P(a1,a2am|cj)P(cj)P(a1,a2am)=max P(a1,a2am|cj)P(cj)(1)P(cMAP|x)=max P(cj|x)j(1,|C|)j(1,|C|)=max P(cj|a1,a2am)第20页/共36页第二十一页，共36页。朴素贝叶斯分类器基于一个简单的假定：在给定目标值时属性值之间相互(xingh)条件独立。换言之，该假定说明给定实例的目标值情况下，观察到联合的a1,a2am的概率正好是对每个单独属性的概率乘积 朴素朴素(p s)(p s)贝叶斯分类

15、器二贝叶斯分类器二(2)将(2)式其代入(1)式中，可得到朴素(p s)贝叶斯分类器，如下第21页/共36页第二十二页，共36页。朴素朴素(p(p s)s)贝叶斯分类器三贝叶斯分类器三 概括地讲，朴素贝叶斯学习方法需要估计不同的P(cj)和P(ai|cj)项，也就是它们在训练数据上的频率。然后使用公式(gngsh)(3)来分类新实例。CNB=argmax P(cj)（3）其中CNB表示朴素贝叶斯分类器输出的目标值。注意在朴素贝叶斯分类器中，须从训练数据中估计的不同P(ai|cj)项的数量只是(zhsh)不同的属性值数量乘以不同目标值数量这比要估计P(a1,a2am|cj)项所需的量小得多第22

16、页/共36页第二十三页，共36页。举例说明举例说明目标概念(ginin)Play Tennis的训练样例 DayOutlookTemperatureHumidityWindPlay TennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWe

17、akYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo第23页/共36页第二十四页，共36页。第一步统计第一步统计(t(t ngj)ngj)个数个数表1 类别(libi)为cj及在cj条件下Ai取ai的样例数OutlookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong2

18、432433663Yes93022214123No5第24页/共36页第二十五页，共36页。估计先验概率和条件估计先验概率和条件(tiojin)(tiojin)概率概率表2 先验概率P(cj)和条件(tiojin)概率P(ai|cj)OutlookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong0.2220.4440.3330.2220.4440.3330.3330.6670.6670.333Yes0.6430.600.40.40.40.20.80.20.40.6No0.357第2

19、5页/共36页第二十六页，共36页。样例判别样例判别(pnbi)(pnbi)现在(xinzi)假设有一个样例xx=Sunny,Hot,High,Weak等于(dngy)yes的概率 P(Yes|x)=p(Yes)*p(Sunny|Yes)*p(Hot|Yes)*p(High|Yes)*p(Weak|Yes)*=0.643*0.222*0.222*0.333*0.667=0.007039等于No的概率 P(No|x)=p(No)*p(Sunny|No)*p(Hot|No)*p(High|No)*p(Weak|No)*=0.357*0.6*0.4*0.8*0.4=0.027418max(max(P

20、(Yes|x),P(No|x)=)=P(No|x),所以我们把x分类为No第26页/共36页第二十七页，共36页。概率概率(gil(gil)为零为零 在大多数情况下，观察到的比例P(ai|cj)是对其真实概率的一个良好估计，但当|Ai=aiC=cj|很小时估计较差。特别是当|Ai=aiC=cj|等于0时，P(ai|cj)也等于0，如果将来(jingli)的待估样例中，包含第i个属性的取值ai时，此概率项会在分类器中占统治地位。第27页/共36页第二十八页，共36页。概率概率(gil(gil)为零之为零之m-m-估计估计 一般采用(ciyng)m-估计来解决这个问题。m-估计定义如下：pi是将要

21、确定的概率P(ai|cj)的先验概率，而m是等效样本大小的常量，它确定了对于观察到的数据如何衡量 pi的作用。在缺少其他信息是选择 p的一种典型方法(fngf)是假定pi=1/|Ai|。也就是将nj个实际观察扩大，加上m个按pi分布的虚拟样本。第28页/共36页第二十九页，共36页。概率概率(gil(gil)为零之个为零之个数比较数比较在本次实现(shxin)中我们采用的不是m-估计，而是下面一种简单的0个数比较法。即下面的几条规则。在公式（3）中，对每一个类别j，统计P(ai|cj)=0的个数，记为zj。然后按以下3条规则得到CNB。1.如果对任意(rny)的j，zj都为0，则直接按公式（3

22、）得到CNB3.如果对任意的j，zj不为0且不相等，则取zj最小者对应的类别作为CNB。若zj最小者不唯一，则对这些最小值对应的j采用第二条规则进行判别。2.如果对任意的j，zj不为0且相等，则按公式（3）计算时只计算P(ai|cj)为非零的项,然后得到CNB第29页/共36页第三十页，共36页。实验实验(shyn)(shyn)结果结果数据库训练样例测试样例训练精度标准差测试精度标准差BALANCE5716391.40.00387.40.056Hatehi1481689.20.01187.10.053heart2512886.10.00583.90.033Mushroom654672799.5

23、0.00099.50.003TIC-TAC-TOE8719671.00.01070.00.055第30页/共36页第三十一页，共36页。结果结果(ji gu(ji gu)分析分析 从上面的实验结果(ji gu)我们可以得到朴素贝叶斯分类器的以下几个特点:训练精度测试精度 意义明确,便于理解 时间(shjin)复杂度低,可以应用大型数据库 易于实现增量第31页/共36页第三十二页，共36页。练 习一个销售的顾客一个销售的顾客一个销售的顾客一个销售的顾客(gk)(gk)数据集，对购买计算机的人员进行分类：数据集，对购买计算机的人员进行分类：数据集，对购买计算机的人员进行分类：数据集，对购买计算机的

24、人员进行分类：字段为：年龄（取值：字段为：年龄（取值：字段为：年龄（取值：字段为：年龄（取值：3040 40）;收入（高，中，低）收入（高，中，低）收入（高，中，低）收入（高，中，低）;学生否（学生否（学生否（学生否（Y Y，N N）;信用（一般，很好）信用（一般，很好）信用（一般，很好）信用（一般，很好）;购买计算机否（购买计算机否（购买计算机否（购买计算机否（Y Y，N N）;记录为记录为记录为记录为1414人，具体数据如下：人，具体数据如下：人，具体数据如下：人，具体数据如下：x1=x1=（30,30,高高高高,N,N,一般一般一般一般,N,N）;x2=;x2=（30,40,40,中中中

25、中,N,N,一般一般一般一般,Y,Y）;x5=x5=（40,40,低低低低,Y,Y,一般一般一般一般,Y,Y）;x6=;x6=（40,40,低低低低,Y,Y,很好很好很好很好,N,N）;x7=x7=（3040,3040,低低低低,Y,Y,高高高高,Y,Y）;x8=;x8=（30,30,中中中中,N,N,一般一般一般一般,N,N）;x9=x9=（30,40,40,中中中中,Y,Y,一般一般一般一般,Y,Y）;x11=x11=（30,40,40,中中中中,N,N,很好很好很好很好,N,N）;第32页/共36页第三十三页，共36页。第一步统计第一步统计(t(t ngj)ngj)个数个数表1 类别(l

26、ibi)为cj及在cj条件下Ai取ai的样例数年龄收入学生否信用购买计算机40高中低YN一般很好2432436363Yes93022211423No5第33页/共36页第三十四页，共36页。估计估计(gj)(gj)先验概率和条件概先验概率和条件概率率表2 先验概率P(cj)和条件(tiojin)概率P(ai|cj)年龄收入学生否信用购买计算机40高中低YN一般很好0.2220.4440.3330.2220.4440.3330.6660.3330.6660.333Yes0.6430.600.40.40.40.20.20.80.40.6No0.357第34页/共36页第三十五页，共36页。样例判别

27、样例判别(pnbi)(pnbi)现在假设有一个样例xx=年龄30，收入=中，学生(xu sheng)否=Y，信用=一般等于yes的概率 P(Yes|x)=p(Yes)*p(30|Yes)*p(收入=中|Yes)*p(学生=Y|Yes)*p(信用(xnyng)=一般|Yes)=0.643*0.222*0.444*0.666*0.666=0.028等于No的概率 P(No|x)=p(No)*p(30|Yes)*p(收入=中|Yes)*p(学生=Y|Yes)*p(信用=一般|Yes)=0.357*0.6*0.4*0.2*0.4=0.007max(max(P(Yes|x),P(No|x)=)=P(Yes|x),所以我们把x分类为Yes，即购买计算机第35页/共36页第三十六页，共36页。