决策树课题ppt课件.ppt

《决策树课题ppt课件.ppt》由会员分享，可在线阅读，更多相关《决策树课题ppt课件.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、决策树决策树 决策树算法是一种归纳分类算法,它通过对训练集的学习,挖掘出有用的规则,用于对新集进行预测。 有监督的学习。 非参数学习算法。对每个输入使用由该区域的训练数据计算得到的对应的局部模型。 决策树归纳的基本算法是贪心算法，自顶向下递归方式构造决策树。贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。 在其生成过程中，分割方法即属性选择度量属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。 简介简介决策树的结构决策树的结构 决策树算法以树状结构表示数据分类的结果。每个决策点实现一个具有离散输出的测试函数，记为分支。 根节点 非叶子节点（决策点） 叶子节点 分支决

2、策树的结构决策树的结构4根部节点(root node)非叶子节点(non-leaf node)(代表测试的条件，对数据属性的测试)分支(branches)(代表测试的结果)叶节点(leaf node)(代表分类后所获得的分类标记)2022-8-8单变量树单变量树 每个内部节点中的测试只使用一个输入维。如果使用的输入维 是离散的，取n个可能的值之一，则该节点检测 的值，并取相应的分支，实现一个n路划分。 决策点具有离散分支，而数值输入应当离散化。如果 是数值的（有序的），则测试函数是比较： 其中 是适当选择阈值。该决策节点将输入空间一份为二： 和 ，称为一个二元划分。 决策树根据所选取的属性是数

3、值型还是离散型，每次将数据划分成两个或n个子集。然后使用对应的子集递归地进行划分，直到不需要划分，此时，创建一个树叶节点标记它。jxjxjx0: )(mjmwxxf0mw0 | mjmwxxL0 | mjmwxxR决策树分类决策树分类1.训练阶段 从给定的训练数据集DB，构造出一棵决策树 class = DecisionTree( DB )2.分类阶段 从根开始，按照决策树的分类属性逐层往下划分，直到叶节点，获得概念（决策、分类）结果。 y = DecisionTree( x )Example of a Decision Tree Another Example of Decision Tre

4、e Apply Model to Test DataRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 Test DataStart from the root of tree.Apply Model to Test DataRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable In

5、come Cheat No Married 80K ? 10 Test DataApply Model to Test DataRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 Test DataApply Model to Test DataRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status

6、Taxable Income Cheat No Married 80K ? 10 Test DataApply Model to Test DataRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 Test DataApply Model to Test DataRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marit

7、al Status Taxable Income Cheat No Married 80K ? 10 Test DataAssign Cheat to “No”决策树原理决策树原理基本算法（贪心算法）基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是离散值字段 (如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量 (如, information gain)停止分割的条件停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割算法：算法：Generate_decision_treeGene

8、rate_decision_tree由给定的训练数据产生一棵决策树由给定的训练数据产生一棵决策树输入：训练数据集输入：训练数据集samplessamples，用离散值属性表示；候选属性的集合，用离散值属性表示；候选属性的集合attribute_listattribute_list。输出：一棵决策树输出：一棵决策树方法：方法：（1 1）创建结点）创建结点N N；（2 2）if samples if samples 都在同一个类都在同一个类C thenC then（3 3）返回）返回N N作为叶结点，用类作为叶结点，用类C C标记；标记；（4 4）if attribute_list if attr

9、ibute_list 为空为空 then then （5 5）返回）返回N N作为叶结点，标记作为叶结点，标记samplessamples中最普通的类；中最普通的类； / /多数表决多数表决（6 6）选择）选择attribute_listattribute_list中的最优分类属性中的最优分类属性test_attributetest_attribute； / /用信息增益作为属性选择度量用信息增益作为属性选择度量（7 7）标记结点）标记结点N N为为test_attributetest_attribute；（8 8）for each test_attributefor each test_at

10、tribute中的已知值中的已知值ai /ai /划分划分samplessamples（9 9）由结点）由结点N N生长出一个条件为生长出一个条件为test_attributetest_attributeaiai的分枝；的分枝；（1010）设）设sisi为为samplessamples中中test_attributetest_attributeaiai的样本集合；的样本集合；/一个划分一个划分（1111）if siif si为空为空 then then（1212）加上一个叶结点，标记为标记）加上一个叶结点，标记为标记samplessamples中最普通的类；中最普通的类； / /多数表决多数表

11、决（1313）else else 加上一个由加上一个由Generate_decision_treeGenerate_decision_tree（si, attribute_list-test_attributesi, attribute_list-test_attribute）返回的结点）返回的结点；例子：算法过程例子：算法过程TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo

12、7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundYesNo1. samples = 1,2,3,4,5,6,7,8,9,10 attribute_list = Refund, MarSt, TaxInc 假设选择Refund为最优分割属性：2. samples = 1,4,7 attribute_list = MarSt, TaxInc 3. samples = 2,3,5,6,8,9,10 attribute_list = MarSt, TaxInc 例子：算法过程例子：算法过程TidRefund

13、MaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundYesNosamples中所有样本属于同一个类Cheat=No2. samples = 1,4,7 attribute_list = MarSt, TaxInc NO例子：算法过程例子：算法过程TidRe

14、fundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundYesNo假设选择MarSt为最优分割属性：3. samples = 2,3,5,6,8,9,10 attribute_list = MarSt, TaxInc NOMarStSingleMarr

15、iedDivorced4. samples = 3,8,10 , attribute_list = TaxInc5. samples = 5,7 , attribute_list = TaxInc6. samples = 2,9 , attribute_list = TaxInc例子：算法过程例子：算法过程TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorce

16、d220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundYesNo选择TaxInc为最优分割属性：4. samples = 3,8,10 attribute_list = TaxInc NOMarStSingleMarriedDivorcedTaxInc= 80KYESNO问题1：分类从哪个属性开始？ 选择分裂变量的标准问题2：为什么工资以80为界限？ 找到被选择的变量的分裂点的标准（连续变量情况） 分类划分的优劣用不纯性度量不纯性度量来分析。如果对于所有分支，划分后选择相同分支的所有实例都属于相同的类，则这个划分是纯的。对于节

17、点m，令 为到达节点m的训练实例数， 个实例中 个属于 类，而 。如果一个实例到节点m，则它属于 类的概率估计为： 节点m是纯的，如果对于所有i， 为0或1。当到达节点m的所有实例都不属于 类时， 为0，当到达节点m的所有实例都属于 类时， 为1。 一种度量不纯性的可能函数是熵函数（entropy)。mNimNiCmiimNNmimimiNNpmxCp),|( mNiCimpiCiCimpimp Father of information theory证明熵与信息内容的不确定程度有等价关系 系统科学领域三大论之一p C.Shannon的信息论信息熵信息熵p 熵(entropy)12121222

18、2entropy( ,)logloglognnnp pppppppp 描述物质系统状态:该状态可能出现的程度。 平均信息量 若一个系统中存在多个事件E1,E2,En 每个事件出现的概率是p1,p2,pn 则这个系统的平均信息量是 指的是系统的混乱的程度!(bits) 系统越无序、越混乱，熵就越大。 构造决策树，熵定义为无序性度量。 选择一个属性划分数据，使得子女节点上数据的类值（例中“yes”或“no”）大部分都相同（低无序性）。 如果一个节点上的数据类值在可能的类值上均匀分布，则称节点的熵（无序性）最大。 如果一个节点上的数据的类值对于所有数据都相同，则熵最小。 通过分裂，得到尽可能纯的节点

19、。这相当于降低系统的熵。例子例子气象数据集，都是标称属性什么因素影响是否去什么因素影响是否去打网球？打网球？OutlookTemperatureHumidityWindyPlay?sunnyhothighfalseNosunnyhothightrueNoovercasthothighfalseYesrainmildhighfalseYesraincoolnormalfalseYesraincoolnormaltrueNoovercastcoolnormaltrueYessunnymildhighfalseNosunnycoolnormalfalseYesrainmildnormalfalseY

20、essunnymildnormaltrueYesovercastmildhightrueYesovercasthotnormalfalseYesrainmildhightrueNo1.基于天气的划分基于天气的划分2.基于基于温度温度的划分的划分3.基于基于湿度湿度的划分的划分4.基于基于有风有风的划分的划分构造树构造树训练样本的信息值训练样本的信息值第一棵树，属性，各叶节点的信息值第一棵树，属性，各叶节点的信息值第一棵树，属性，导致的信息增益第一棵树，属性，导致的信息增益依次，计算每棵树导致的信息增益依次，计算每棵树导致的信息增益选择获得最大信息增益的属性进行划分选择获得最大信息增益的属性进行

21、划分以此类推，递归，继续划分以此类推，递归，继续划分当所有叶节点都是纯的，划分过程终止当所有叶节点都是纯的，划分过程终止（1）训练样本的信息值(基于类的比例） 训练样本（用来创建树的数据集）在包含9个yes和5个no的根节点上，对应于信息值 info(9,5)=0.940位位 总的信息（2） 第一棵树，属性，各叶节点的信息值 基于天气(outlook)的划分，在叶节点的yes和no类的个数分别是2,3，4,0，和3,2，而这些节点的信息值分别是： info(2,3)=0.971位 sunny info(4,0)=0. 0位 overcast info(3,2)=0.971位 rainYESNo

22、合计sunny235overcast404rain325合计95（3）第一棵树，属性，导致的信息增益计算平均信息值。根据天气的树导致的信息增益为：基于类比例原来信息需求-基于天气属性划分之后得到的信息需求gain(outlook)=info(9,5)-info(2,3,4,0,3,2)=0.940-0.693=0.247位位（4）依次，计算每棵树导致的信息增益为每个属性计算信息增益 gain(outlook)=0.247位 gain(temperature)=0.029位 gain(humidity)=0.152位 gain(windy)=0.048位（5）选择获得最大信息增益的属性进行划分最

23、大信息增益：最大信息增益： gain(outlook)=0.247位位选择天气作为树的根节点的划分属性，其中一个子女节点是最纯的，并且这使它明显优于其他属性。湿度是次佳选择，它产生了一个几乎完全纯的较大的子女节点。（6）以此类推，递归，继续划分递归继续选择当天气为晴时，所达到的节点上的可 能的深一层的分支除天气外，其他属性产生的信息增益 分别为： gain(temperature)=0.571位 gain(humidity)=0.971位 gain(windy)=0.020位继续再选择湿度(humidity)作为划分属性天气，晴分支天气，晴分支纯子节点（6）以此类推，递归，继续划分 天气，晴分

24、支，气温，gain(temperature)=0.571位 天气，晴分支，湿度，gain(humidity)=0.971位位(纯的子女节点） 天气，晴分支，有风，gain(windy)=0.020位 天气，雨分支，气温，gain(temperature)=0.020位 天气，雨分支，湿度，gain(humidity)=0.020位 天气，雨分支，有风，gain(windy)=0.971位位（纯的子女节点）天气天气 雨分支雨分支 有风有风纯的子节点纯的子节点（7）当所有叶节点都是纯的，划分过程终止当所有叶节点都是纯的，划分过程终止理想情况下，当所有叶节点都是纯的而使过程终止时，即当它们包含的实例

25、都具有相同类时该过程终止。可能无法达到这种结果，因为无法避免训练集包含两个具有相同属性集，但具有不同类的实例。当数据不能进一步划分时，停止划分过程当数据不能进一步划分时，停止划分过程。最终的决策树最终的决策树Weather数据OutlookTemperatureHumidityWindyPlay?sunnyhothighfalseNosunnyhothightrueNoovercasthothighfalseYesrainmildhighfalseYesraincoolnormalfalseYesraincoolnormaltrueNoovercastcoolnormaltrueYessunn

26、ymildhighfalseNosunnycoolnormalfalseYesrainmildnormalfalseYessunnymildnormaltrueYesovercastmildhightrueYesovercasthotnormalfalseYesrainmildhightrueNoovercasthighnormalfalsetruesunnyrainNoNoYesYesYesOutlookHumidityWindynID3如何选择具有最高信息增益的属性如何选择具有最高信息增益的属性：npi 是D中任意元组属于类Ci 的概率，用|Ci,D|/|D| 估计nD中的元组分类所需的期

27、望信息中的元组分类所需的期望信息Expected information (entropy)：nInformation needed (after using A to split D into v partitions) to classify D:nInformation gained by branching on attribute A)(log)(21imiippDInfo)(|)(1jvjjADIDDDInfo(D)InfoInfo(D)Gain(A)A使用属性使用属性A得到准确分得到准确分类所需信息类所需信息思考：思考：如果考虑充当唯一识别的属性，如如果考虑充当唯一识别的属性，如

28、product_ID。对。对product_ID的分裂结果？的分裂结果？Infoproduct_ID(D)=0 Gain(product_ID)最大最大有无实际意义？有无实际意义？ 标识属性被选为分裂属性，但标识属性的分支对标识属性被选为分裂属性，但标识属性的分支对预测未知实例的类别并无任何帮助预测未知实例的类别并无任何帮助C4.5nC4.5如何选择具有最高信息增益的属性如何选择具有最高信息增益的属性：使用使用“分裂信息（分裂信息（split information）”值将值将gain规范化规范化 表示属性表示属性A第第j个划分的权重。个划分的权重。信息率信息率DDDDDSplitInfojv

29、jjA21log)()()()(ASplitInfoAGainAGainRatio|DDjC4.5C4.5算法概述算法概述qC4.5算法是ID3算法的扩展q能够处理连续型的属性。首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个分裂点Gian值的大小。q缺失数据的考虑：在构建决策树时，可以简单地忽略缺失数据，即在计算增益时，仅考虑具有属性值的记录。连续值的处理连续值的处理TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo

30、5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10选取(连续值的)哪个分界点？n贪婪算法！1. 排序排序 60 70 75 85 90 95 100 120 125 220若进行“二分二分”，则可能有9个分界点。例子例子： 60 70 75 85 90 95 100 120 125 220 60 70 75 85 90 95 100 120 125 220分割成TaxIn80分割成TaxIn97.5实际上, 这就是“离散化”过程连续值的处理连续值的处

31、理TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes102. 对每个每个候选的分界点，分别计算熵 例子例子: 测试以80分界的情形entropy()0bitscheat 37Info(TaxIn|80)00.9850.670bits1010 (1).

32、TaxIn80223344entropy()loglog=0.985bits7777cheat (3). 加权平均同理同理, 测试以95分界的情形, Info(TaxIn|95)=0.600 bits3. 比较取每个每个分界点的信息增益，选择最大的一个 未知属性值问题未知属性值问题新的增益标准：新的增益标准：Gain(X) = FGain(X) = F* *(info(T) info(info(T) infox x(T)(T)通过把具有未知值的样本看作分区的一个通过把具有未知值的样本看作分区的一个附加组附加组来修改来修改Split_Info (X X)。如果检验如果检验x有有n个输出，个输出，

33、 Split_Info (X)按照检验把数据集分区成按照检验把数据集分区成n + 1个子集计算。个子集计算。有一个丢失值的简单平面数据库有一个丢失值的简单平面数据库数据库T：属性1属性2属性3类别A70真类1A90真类2A85假类2A95假类2A70假类1？90真类1B78假类1B65真类1B75假类1C80真类2C70真类2C80假类1C80假类1C96假类1属性属性1 1的增益计算考虑的增益计算考虑1313个数据，丢失的样本仅用来作修正，属性个数据，丢失的样本仅用来作修正，属性1 1中有中有8 8个属于类个属于类1 1，5 5个属于类个属于类2 2，因此分区前的熵为：，因此分区前的熵为：I

34、nfo (T T)-8/13 log2(8/138/13) -5/13 log2(5/135/13)=0.961比特用属性用属性1 1把把T T分区成分区成3 3个子集（个子集（A A、B B、C C）后，得到的信息是：）后，得到的信息是：Info x1(T)5/13（-2/5 log2(2/52/5) -3/5 log2(3/53/5) ）+ 3/13（-3/3 log2(3/33/3) -0/3 log2(0/3/3) ）+ 5/13（-3/5 log2(3/53/5) -2/5 log2(2/5/5) ）=0.747比特用系数用系数F F进行修正得：进行修正得：Gain(XGain(X1

35、 1) = 13/14) = 13/14（0.961 0.7470.961 0.747）= 0.199= 0.199比特比特考虑未知值的影响：考虑未知值的影响：Split_Info (X X1 1)-5/13 log2(5/135/13) -3/13 log2(3/133/13) -5/13log2(5/135/13) -1/13 log2(1/131/13) =1.876比特由由Gain_ratio(X) = Gain(X)/ Split_Info (X)计算，则：计算，则：Gain_ratio(X) = 0.199/1.876=0.106作为单独一组作为单独一组 优点优点 ： (1) 速度

36、快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。 (2) 准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。 (3) 非参数学习，不需要设置参数。 缺点：缺点： (1) 缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在 Irvine 机器学习知识库中，最大可以允许的数据集仅仅为 700KB ， 2000 条记录。而现代的数据仓库动辄存储几个 G-Bytes 的海量数据。用以前的方法是显然不行的。 (2) 为了处理大数据集或连续量的种种改进算法（离散化、取样）不仅增加了分类算法的额外开销，而且降低了分类的准确性，对连续性的字段比较难预测，当类别太多时，错误可能就会增加的比较快，对有时间顺序的数据，需要很多预处理的工作。