决策树(详细易懂,很多例子).pptx

《决策树(详细易懂,很多例子).pptx》由会员分享，可在线阅读，更多相关《决策树(详细易懂,很多例子).pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、Divorced80KTestDataStartfromtherootoftree.ApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80KTestDataApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80KTestDataApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80KTestDataApplyM

5、odeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80KTestDataApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80KTestDataAssignCheatto“No”决策树原理决策树原理基本算法（贪心算法）基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是离散值字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,

6、informationgain)停止分割的条件停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割算法：算法：Generate_decision_treeGenerate_decision_tree由给定的训练数据产生一棵决策树由给定的训练数据产生一棵决策树输入：训练数据集输入：训练数据集samplessamples，用离散值属性表示；候选属性的集合，用离散值属性表示；候选属性的集合attribute_listattribute_list。输出：一棵决策树输出：一棵决策树方法：方法：（1 1）创建结点）创建结点N N；（2 2）if samples if sampl

7、es 都在同一个类都在同一个类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

8、）标记结点）标记结点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

9、si为空为空 then then（1212）加上一个叶结点，标记为标记）加上一个叶结点，标记为标记samplessamples中最普通的类；中最普通的类；/多数表决多数表决（1313）else else 加上一个由加上一个由Generate_decision_treeGenerate_decision_tree（si,attribute_list-test_attributesi,attribute_list-test_attribute）返回的结点；）返回的结点；例子：算法过程例子：算法过程RefundYesNo1.samples=1,2,3,4,5,6,7,8,9,10attribute_

10、list=Refund,MarSt,TaxInc假设选择Refund为最优分割属性：2.samples=1,4,7attribute_list=MarSt,TaxInc3.samples=2,3,5,6,8,9,10attribute_list=MarSt,TaxInc例子：算法过程例子：算法过程RefundYesNosamples中所有样本属于同一个类Cheat=No2.samples=1,4,7attribute_list=MarSt,TaxIncNO例子：算法过程例子：算法过程RefundYesNo假设选择MarSt为最优分割属性：3.samples=2,3,5,6,8,9,10attr

11、ibute_list=MarSt,TaxIncNOMarStSingleMarriedDivorced4.samples=3,8,10,attribute_list=TaxInc5.samples=5,7,attribute_list=TaxInc6.samples=2,9,attribute_list=TaxInc例子：算法过程例子：算法过程RefundYesNo选择TaxInc为最优分割属性：4.samples=3,8,10attribute_list=TaxIncNOMarStSingleMarriedDivorcedTaxInc=80KYESNO问题1：分类从哪个属性开始？选择分裂变量

12、的标准问题2：为什么工资以80为界限？找到被选择的变量的分裂点的标准（连续变量情况）分类划分的优劣用不纯性度量不纯性度量来分析。如果对于所有分支，划分后选择相同分支的所有实例都属于相同的类，则这个划分是纯的。对于节点m，令为到达节点m的训练实例数，个实例中个属于类，而。如果一个实例到节点m，则它属于类的概率估计为：节点m是纯的，如果对于所有i，为0或1。当到达节点m的所有实例都不属于类时，为0，当到达节点m的所有实例都属于类时，为1。一种度量不纯性的可能函数是熵函数（entropy)。Father of information theory证明熵与信息内容的不确定程度有等价关系 系统科学领域三

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

14、的熵。例子例子气象数据集，都是标称属性什么因素影响是否去什么因素影响是否去打网球？打网球？1.基于天气的划分基于天气的划分2.基于基于温度温度的划分的划分3.基于基于湿度湿度的划分的划分4.基于基于有风有风的划分的划分构造树构造树训练样本的信息值训练样本的信息值第一棵树，属性，各叶节点的信息值第一棵树，属性，各叶节点的信息值第一棵树，属性，导致的信息增益第一棵树，属性，导致的信息增益依次，计算每棵树导致的信息增益依次，计算每棵树导致的信息增益选择获得最大信息增益的属性进行划分选择获得最大信息增益的属性进行划分以此类推，递归，继续划分以此类推，递归，继续划分当所有叶节点都是纯的，划分过程终止当所

15、有叶节点都是纯的，划分过程终止（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位sunnyinfo(4,0)=0.0位overcastinfo(3,2)=0.971位rain（3）第一棵树，属性，导致的信息增益计算平均信息值。根据天气的树导致的信息增益为：基于类比例原来信息需求-基于天气属性划分之

16、后得到的信息需求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）选择获得最大信息增益的属性进行划分最大信息增益：最大信息增益：gain(outlook)=0.247位位选择天气作为树的根节点的划分属性，其中一个子女节点是最纯的，并且这使它明显优于其他属性。湿度是次佳选择，它产生了一个几乎完全纯的

17、较大的子女节点。（6）以此类推，递归，继续划分递归继续选择当天气为晴时，所达到的节点上的可能的深一层的分支除天气外，其他属性产生的信息增益分别为：gain(temperature)=0.571位gain(humidity)=0.971位gain(windy)=0.020位继续再选择湿度(humidity)作为划分属性天气，晴分支天气，晴分支纯子节点（6）以此类推，递归，继续划分天气，晴分支，气温，gain(temperature)=0.571位天气，晴分支，湿度，gain(humidity)=0.971位位(纯的子女节点）天气，晴分支，有风，gain(windy)=0.020位天气，雨分支，气

18、温，gain(temperature)=0.020位天气，雨分支，湿度，gain(humidity)=0.020位天气，雨分支，有风，gain(windy)=0.971位位（纯的子女节点）天气天气雨分支雨分支有风有风纯的子节点纯的子节点（7）当所有叶节点都是纯的，划分过程终止当所有叶节点都是纯的，划分过程终止理想情况下，当所有叶节点都是纯的而使过程终止时，即当它们包含的实例都具有相同类时该过程终止。可能无法达到这种结果，因为无法避免训练集包含两个具有相同属性集，但具有不同类的实例。当数据不能进一步划分时，停止划分过程当数据不能进一步划分时，停止划分过程。最终的决策树最终的决策树Weather数

19、据overcasthighnormalfalsetruesunnyrainNoNoYesYesYesOutlookHumidityWindyID3如何选择具有最高信息增益的属性如何选择具有最高信息增益的属性：pi是D中任意元组属于类Ci的概率，用|Ci,D|/|D|估计D中的元组分类所需的期望信息中的元组分类所需的期望信息Expected information(entropy)：Information needed(after using A to split D into v partitions)to classify D:Information gained by branching

20、on attribute A使用属性使用属性A得到准确分得到准确分类所需信息类所需信息思考：思考：如果考虑充当唯一识别的属性，如如果考虑充当唯一识别的属性，如product_ID。对。对product_ID的分裂结果？的分裂结果？Infoproduct_ID(D)=0Gain(product_ID)最大最大有无实际意义？有无实际意义？标识属性被选为分裂属性，但标识属性的分支对预标识属性被选为分裂属性，但标识属性的分支对预测未知实例的类别并无任何帮助测未知实例的类别并无任何帮助C4.5C4.5如何选择具有最高信息增益的属性如何选择具有最高信息增益的属性：使用使用“分裂信息（分裂信息（spliti

21、nformation）”值将值将gain规范化规范化表示属性表示属性A第第j个划分的权重。个划分的权重。信息率信息率C4.5C4.5算法概述算法概述qC4.5算法是ID3算法的扩展q能够处理连续型的属性。首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个分裂点Gian值的大小。q缺失数据的考虑：在构建决策树时，可以简单地忽略缺失数据，即在计算增益时，仅考虑具有属性值的记录。连续值的处理连续值的处理选取(连续值的)哪个分界点？贪婪算法！1.排序排序 60 70 75 85 90 95 100 120 125 220若进行“二分二分”，则可能有9个分界点。例子例子：60 70

22、75 85 90 95 100 120 125 220 60 70 75 85 90 95 100 120 125 220分割成TaxIn80分割成TaxIn97.5实际上,这就是“离散化”过程连续值的处理连续值的处理2.对每个每个候选的分界点，分别计算熵 例子例子:测试以80分界的情形(1).TaxIn80(3).加权平均同理同理,测试以95分界的情形,Info(TaxIn|95)=0.600 bits3.比较取每个每个分界点的信息增益，选择最大的一个 C4.5C4.5算法中：有未知值的样本是按照已知值的相对频率随机分布的。算法中：有未知值的样本是按照已知值的相对频率随机分布的。算法中：有未

23、知值的样本是按照已知值的相对频率随机分布的。算法中：有未知值的样本是按照已知值的相对频率随机分布的。qq用系数用系数用系数用系数F F修正增益参数修正增益参数修正增益参数修正增益参数F=F=数据库中一个给出的属性值具有已知值的样本数量数据库中一个给出的属性值具有已知值的样本数量数据库中一个给出的属性值具有已知值的样本数量数据库中一个给出的属性值具有已知值的样本数量/数据集中样本数据集中样本数据集中样本数据集中样本数量总和数量总和数量总和数量总和未知属性值问题未知属性值问题新的增益标准：新的增益标准：Gain(X)=F*(info(T)infoGain(X)=F*(info(T)infox x(

24、T)(T)同时，同时，同时，同时，通过把具有未知值的样本看作分区的一个通过把具有未知值的样本看作分区的一个附加组附加组来修改来修改Split_Info(X X)。如果检验如果检验x有有n个输出，个输出，Split_Info(X)按照检验把数据集分区成按照检验把数据集分区成n+1个子集计算。个子集计算。属性属性1 1的增益计算考虑的增益计算考虑1313个数据，丢失的样本仅用来作修正，属性个数据，丢失的样本仅用来作修正，属性1 1中有中有8 8个属于类个属于类1 1，5 5个属于类个属于类2 2，因此分区前的熵为：，因此分区前的熵为：Info(T T)-8/13log2(8/138/13)-5/1

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

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