决策树(详细易懂很多例子)ppt课件.ppt

《决策树(详细易懂很多例子)ppt课件.ppt》由会员分享，可在线阅读，更多相关《决策树(详细易懂很多例子)ppt课件.ppt（49页珍藏版）》请在三一办公上搜索。

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

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

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

4、oot of tree.,Apply Model to Test Data,Test Data,Apply Model to Test Data,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Test Data,Apply Model to Test Data,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Test Data,Apply Model to Test Data,Refund,

5、MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Test Data,Apply Model to Test Data,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Test Data,Assign Cheat to “No”,决策树原理,基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是离散值字段 (如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个

6、启发式规则或者一个统计的度量 (如, information gain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割,算法：Generate_decision_tree由给定的训练数据产生一棵决策树输入：训练数据集samples，用离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树方法：（1）创建结点N；（2）if samples 都在同一个类C then（3）返回N作为叶结点，用类C标记；（4）if attribute_list 为空 then （5）返回N作为叶结点，标记samples中最普通的类； /多数表决（6）选择attr

7、ibute_list中的最优分类属性test_attribute； /用信息增益作为属性选择度量（7）标记结点N为test_attribute；（8）for each test_attribute中的已知值ai /划分samples（9）由结点N生长出一个条件为test_attributeai的分枝；（10）设si为samples中test_attributeai的样本集合；/一个划分（11）if si为空 then（12）加上一个叶结点，标记为标记samples中最普通的类； /多数表决（13）else 加上一个由Generate_decision_tree（si, attribute_li

8、st-test_attribute）返回的结点；,例子：算法过程,Refund,Yes,No,1. 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 ,例子：算法过程,Refund,Yes,No,samples中所有样本属于同一个类Cheat=No,

9、2. samples = 1,4,7 attribute_list = MarSt, TaxInc ,NO,例子：算法过程,Refund,Yes,No,假设选择MarSt为最优分割属性：,3. samples = 2,3,5,6,8,9,10 attribute_list = MarSt, TaxInc ,NO,MarSt,Single,Married,Divorced,4. samples = 3,8,10 , attribute_list = TaxInc5. samples = 5,7 , attribute_list = TaxInc6. samples = 2,9 , attribu

10、te_list = TaxInc,例子：算法过程,Refund,Yes,No,选择TaxInc为最优分割属性：,4. samples = 3,8,10 attribute_list = TaxInc ,NO,MarSt,Single,Married,Divorced,TaxInc, 80K,= 80K,YES,NO,问题1：分类从哪个属性开始？ 选择分裂变量的标准问题2：为什么工资以80为界限？ 找到被选择的变量的分裂点的标准（连续变量情况）,分类划分的优劣用不纯性度量来分析。如果对于所有分支，划分后选择相同分支的所有实例都属于相同的类，则这个划分是纯的。对于节点m，令 为到达节点m的训练实例

11、数， 个实例中 个属于 类，而 。如果一个实例到节点m，则它属于 类的概率估计为： 节点m是纯的，如果对于所有i， 为0或1。当到达节点m的所有实例都不属于 类时， 为0，当到达节点m的所有实例都属于 类时， 为1。 一种度量不纯性的可能函数是熵函数（entropy)。,Father of information theory证明熵与信息内容的不确定程度有等价关系 系统科学领域三大论之一,C.Shannon的信息论,信息熵,熵(entropy),描述物质系统状态:该状态可能出现的程度。 平均信息量 若一个系统中存在多个事件E1,E2,En 每个事件出现的概率是p1,p2,pn 则这个系统的平均

12、信息量是,指的是系统的混乱的程度!,(bits), 系统越无序、越混乱，熵就越大。 构造决策树，熵定义为无序性度量。 选择一个属性划分数据，使得子女节点上数据的类值（例中“yes”或“no”）大部分都相同（低无序性）。 如果一个节点上的数据类值在可能的类值上均匀分布，则称节点的熵（无序性）最大。 如果一个节点上的数据的类值对于所有数据都相同，则熵最小。 通过分裂，得到尽可能纯的节点。这相当于降低系统的熵。,例子,气象数据集，都是标称属性,什么因素影响是否去打网球？,1.基于天气的划分,2.基于温度的划分,3.基于湿度的划分,4.基于有风的划分,构造树,训练样本的信息值第一棵树，属性，各叶节点的

13、信息值第一棵树，属性，导致的信息增益依次，计算每棵树导致的信息增益选择获得最大信息增益的属性进行划分以此类推，递归，继续划分当所有叶节点都是纯的，划分过程终止,（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

14、,2)=0.971位 rain,（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）选择获得最大信息增益的属性进行划分最大信息增益： gain(ou

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

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

17、实例。当数据不能进一步划分时，停止划分过程。,最终的决策树,Weather数据,ID3如何选择具有最高信息增益的属性：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 on attribute A,使用属性A得到准确分类所需信息,思考：如果考虑充当唯一识别的属性，如pro

18、duct_ID。对product_ID的分裂结果？Infoproduct_ID(D)=0 Gain(product_ID)最大有无实际意义？ 标识属性被选为分裂属性，但标识属性的分支对预测未知实例的类别并无任何帮助,C4.5,C4.5如何选择具有最高信息增益的属性：使用“分裂信息（split information）”值将gain规范化 表示属性A第j个划分的权重。信息率,C4.5算法概述,C4.5算法是ID3算法的扩展能够处理连续型的属性。首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个分裂点Gian值的大小。缺失数据的考虑：在构建决策树时，可以简单地忽略缺失数据，即在

19、计算增益时，仅考虑具有属性值的记录。,连续值的处理,选取(连续值的)哪个分界点？,贪婪算法！,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,实际上, 这就是“离散化”过程,连续值的处理,2. 对每个候选的分界点，分别计算熵,例子: 测试以80分界的情形,(1). TaxIn=80,(2). TaxIn80,(3). 加权平均,同理, 测

20、试以95分界的情形, Info(TaxIn|95)=0.600 bits,3. 比较取每个分界点的信息增益，选择最大的一个,C4.5算法中：有未知值的样本是按照已知值的相对频率随机分布的。用系数F修正增益参数F=数据库中一个给出的属性值具有已知值的样本数量/数据集中样本数量总和,未知属性值问题,新的增益标准：Gain(X) = F*(info(T) infox(T)同时，通过把具有未知值的样本看作分区的一个附加组来修改Split_Info (X)。如果检验x有n个输出， Split_Info (X)按照检验把数据集分区成n + 1个子集计算。,属性1的增益计算考虑13个数据，丢失的样本仅用来作

21、修正，属性1中有8个属于类1，5个属于类2，因此分区前的熵为：Info (T)-8/13 log2(8/13) -5/13 log2(5/13)=0.961比特用属性1把T分区成3个子集（A、B、C）后，得到的信息是：Info x1(T)5/13（-2/5 log2(2/5) -3/5 log2(3/5) ）+ 3/13（-3/3 log2(3/3) -0/3 log2(0/3) ）+ 5/13（-3/5 log2(3/5) -2/5 log2(2/5) ）=0.747比特用系数F进行修正得：Gain(X1) = 13/14（0.961 0.747）= 0.199比特,考虑未知值的影响：Spl

22、it_Info (X1)-5/13 log2(5/13) -3/13 log2(3/13) -5/13log2(5/13) -1/13 log2(1/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)为了处理大数据集或连续量的种种改进算法（离散化、取样）不仅增加了分类算法的额外开销，而且降低了分类的准确性，对连续性的字段比较难预测，当类别太多时，错误可能就会增加的比较快，对有时间顺序的数据，需要很多预处理的工作。,